A. Painting水题，容斥原理，小心又可能有0高度的。B. WarCraft III暴力C(24,5)。C. Apple有意思的题，问说n个数中有多少种方法，使得连续的数的和与0模m同余。将前缀和按模m等价类划分。
代码 #include < iostream > #include < string > #include < stdio.h > #include < string .h > #include < map > #include < algorithm > #include < vector > using namespace std;typedef long long int64; const int64 MAX = 100005 ;int64 num[MAX], n, m;int64 cnt[MAX];int64 go(){ int64 res = 0 , tsum = 0 ; memset(cnt, 0 , sizeof (cnt)); for (int64 i = 0 ; i < n; i ++ ) { tsum += num[i]; cnt[tsum % m] ++ ; } for ( int i = 0 ; i < m; i ++ ) { res += cnt[i] * (cnt[i] - 1 ) / 2 ; } res += cnt[ 0 ]; return res;} int main(){ int64 T, c = 0 ; scanf( " %lld " , & T); while (T -- ) { scanf( " %lld%lld " , & n, & m); for (int64 i = 0 ; i < n; i ++ ) scanf( " %lld " , & num[i]); printf( " Case #%lld: %lld\n " , ++ c, go()); }}D. Bolts And Nuts将(i,j)看为状态，一边情况可向(i-1,j-1),(i-1,j),(i,j-1)扩展，然后结合SG原理，根据必胜必败态判断就可以了。
E. A Card Game模拟后，求逆序数，又看了遍树状数组，很有意思。i+lowbit(i)，其中lowbit(i)是以i为根的树的节点数，扩展扩展可以添加虚拟节点来证明。见http://fqq11679.blog.hexun.com/21722866_d.html
代码 #include < iostream > #include < string > #include < stdio.h > #include < string .h > #include < map > #include < algorithm > #include < vector > using namespace std;typedef long long int64; const int MAX = 1000005 ; int n, k;int64 c[MAX]; int q[MAX]; int lowbit( int t){ return t & ( - t);} void insert( int i){ while (i <= n){ c[i] ++ ; i += lowbit(i); }}int64 query( int i){ int64 res = 0 ; while (i > 0 ) { res += c[i]; i -= lowbit(i); } return res;} int main(){ int T, cc = 0 ; scanf( " %d " , & T); while (T -- ) { scanf( " %d%d " , & n, & k); int h = 0 , t = 0 ; for ( int i = n; i >= 1 ; i -- ) { q[t] = i; t = (t + 1 ) % MAX; for ( int j = 0 ; j < k; j ++ ) { q[t] = q[h]; h = (h + 1 ) % MAX; t = (t + 1 ) % MAX; } } int64 ans = 0 ; memset(c, 0 , sizeof (c)); while (h != t) { ans += query(q[h]); insert(q[h]); h = (h + 1 ) % MAX; } printf( " Case #%d: %lld\n " , ++ cc, ans); }}
转载于:https://www.cnblogs.com/litstrong/archive/2010/12/25/1916961.html
