HDU 5072 Coprime 同色三角形问题
好吧，我承认就算当时再给我五个小时我也做不出来。首先解释同色三角形问题：给出n(n >= 3)个点，这些点中的一些被涂上了红色，剩下的被涂上了黑色。然后将这些点两两相连，于是每三个点都会组成一个三角形，即总共有sum = C(3,n)个三角形。对于一个三角形，如果三个点颜色一样则称其为同色三角形。那么一个很直观的思路就是容斥，sum - 非同色三角形个数ans。ans = (sigma (Xi*Yi) ) / 2;(1 <= i <= n,Xi,Yi分别表示与第 i 个点相连的红色点和黑色点的个数。)
状态不好的时候，代码写的就像屎一样。
#include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000")#define EPS (1e-8)#define LL long long#define ULL unsigned long long#define INF 0x3f3f3f3fusing namespace std;int divi;bool is;int num;int mem;int ch;int Check(int x){ int ans = 0; while(x) ans += (x&1),x >>= 1; return ans&1 ? 1:-1;}int main(){ int n = 100000,i,j,k; for(i = 0;i <= 1000; ++i) ch = Check(i); for(i = 1;i <= n; ++i) divi = 0; memset(is,false,sizeof(is)); for(i = 2;i <= n; ++i) { if(is == false) { divi[++divi] = i; for(j = i+i;j <= n; j += i) { divi[++divi] = i; is = true; } } } int Max,Mul,t; int wf; for(i = 1;i <= n; ++i) { Max = (1<<divi) -="" 1;="" wf="divi;" for(j="1;j" = 1; --k,t <<= 1) { if((j&t) && j != t) Mul *= divi; } if(Mul != 1) divi[++divi] = Mul*ch; } } int T,tmp; LL ans,sum; int Top; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(is,false,sizeof(is)); for(i = 1,Top = 0;i <= n; ++i) { scanf("%d",&num); is] = true; Top = max(Top,num); } ans = 0; memset(mem,-1,sizeof(mem)); LL anw = 0; for(i = 1;i <= n; ++i) { tmp = num; ans = 0; for(j = divi;j >= 1; --j) { if(mem)] != -1) sum = mem)]*(divi/abs(divi)); else { sum = 0; for(k = abs(divi);k <= Top; k += abs(divi)) sum += is ? 1 : 0; mem)] = sum; sum *= (divi/abs(divi)); } ans += sum;
页:
[1]