2015Multi-UniversityTrainingContest2

hdu5301Buildings机智题，卡了好久，最后小坤纸上去敲过了。。做法：假设nm，定义ans(n+1)2，retmin(b,m-b+1)。

hdu 5301Buildings

机智题，卡了好久，最后小坤纸上去敲过了。。做法：假设n 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f12 #define eps 1e-913 #define FOR(i,s,t) for(int i = s; i ans 41 printf("%d\n", ans);42 }43 return 0;44 } View Code

hdu 5302Connect the Graph

构造题。当n >= 5时肯定有解。n为奇数，假设b2 = n, w2 = n，直接可以构造出1，2，3……n一个环满足b2 = n，构造1，3，5……2，4……1这样的环满足w2 = n。n为偶数，假设b2 = n, w2 = n，可以构造出1，2，3……n满足b2 = n，构造1，3，5……2，n，n-2，n-4……4满足w2 = n。对于b2 != n, w2 != n直接拆环就好了。对于n <= 4爆搜一下就好了。（实际上b0, b1, b2, w0, w1, w2都大于等于1，小于5的情况好像只有1,2,1,1,2,1才有解，其他无解，不需要搜）

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f 12 #define eps 1e-6 13 #define MP make_pair 14 #define LL long long 15 #define N 1000010 16 #define M 200020 17 #define mod 1000000007 18 19 int n, a[2][3], c[N]; 20 void work(int col){ 21 if(a[col][2] == n){ 22 for(int i = 1; i 2) return ; 48 ww[use[i][0]]++, bb[use[i][1]]++; 49 } 50 for(int i = 0; i <3; ++i) 51 if(a[0][i] != ww[i] || a[1][i] != bb[i]) return ; 52 ok = 1; 53 printf("%d\n", a[0][1]/2 + a[0][2] + a[1][1]/2 + a[1][2]); 54 for(int i = 0; i hdu 5303Delicious Apples

一道十分好的贪心题。最多只能绕一次环。

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f12 #define eps 1e-913 #define FOR(i,s,t) for(int i = s; i hdu 5307He is Flying

一道FFT的题目。用复数模板的FFT会因为精度误差而wa，又找了一个用快速数论变换的模板。中间有一个O(1)longlong内的乘法，我也不知道为什么这样算是对的。。

设所有的答案为 sigma(j - i +1) * X^(Sj - Si)，拓展开来就可以得到题解的式子，可以用FFT求出所有正数的答案。ans0再另外处理一下。

（c++交上去是超时的，g++才能过）

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f 12 #define eps 1e-5 13 #define pii pair 14 #define MP make_pair 15 #define LL long long 16 #define N 100010 17 #define M 200020 18 #define mod 1000000007 19 20 int read(){ 21 int ret = 0; char ch = getchar(); 22 while(ch '9') ch = getchar(); 23 while(ch >= '0' 28 putchar(x % 10 + '0'); 29 } 30 const LL P = 50000000001507329LL, NN = 1LL<>= 1; 42 } 43 return ret; 44 } 45 LL wn[25]; 46 void getWn(){ 47 for(int i = 0; i <= 20; ++i){ 48 int t = 1 << i; 49 wn[i] = qpow(G, (P - 1) / t, P); 50 } 51 } 52 void Rader(LL *a, int len){ 53 int k; 54 for(int i = 1, j = len / 2; i = P) a[k+h/2] -= P; 75 w = Mul(w, wn[id]); 76 } 77 } 78 } 79 if(on == -1){ 80 for(int i = 1; i hdu 5308I Wanna Become A 24-Point Master

算24点。傻逼了，7个7竟然没算出来。。贴纬哥的代码

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f 12 #define eps 1e-9 13 #define FOR(i,s,t) for(int i = s; i n ) {140 getchar();141 for( int i = 1; i <= n; ++i )142 A[i] = n;143 memset( vis, 0, sizeof( vis ));144 bool e = 1;145 int k = n + 1;146 for( int z = 1; z <= n - 1; ++z ) {147 gets(s);148 int len = strlen( s );149 int a = 0, b = 0;150 int i;151 for( i = 0; i = k ) e = 0;163 vis[a] = vis[b] = 1;164 if( s[j] == '+') A[k++] = A[a] + A[b];165 if( s[j] == '-') A[k++] = A[a] - A[b];166 if( s[j] == '*' ) A[k++] = A[a] * A[b];167 if( s[j] == '/') A[k++] = A[a] / A[b];168 }169 for( int i = 1; i = 14 i <= 7; i += 2 )189 printf("%d + %d\n", i, i + 1 );190 for( int i = 1; i <= 4; ++i )191 printf("%d / %d\n", n+i, i + 8 );192 printf("%d / %d\n", 13, 14 );// n + 9 == 1193 194 printf("%d + %d\n", n + 5, n + 6 ); // a[n+10] = 4195 printf("%d + %d\n", n + 7, n + 9 ); // a[n+11] = 3196 printf("%d * %d\n", n + 11, n + 8 ); // a[n+12] = 6;197 198 printf("%d * %d\n", n+10, n + 12 ); // a[n+13] = 24;199 200 if( n == 14 ) continue;201 printf("%d - %d\n", 15, 16 ); //a[n+14] = 0;202 int j = n + 14;203 for( int i = 17; i <= n; ++i )204 printf("%d * %d\n", i, j++ );205 printf("%d + %d\n", j, n + 13 );206 207 }208 else out( n );209 }210 211 } View Code