Brief description:

Problem A. jabuke
星莲船。

Problem B. matrix
给定一个 N * N 的方阵，定义子矩阵的 beautiful_value = {主对角线和 – 副对角线和}。
求最大值。
( .. N <= 400 . .) Problem C. X3 给定 N 个数，求所有这些数两两之间的异或和。 ( .. N <= 10^6 .. .) Problem D. ples 给定 N 名男生和 N 名女生的身高，其中正数表示其只愿意和比自己高的异性跳舞， 负数表示其只愿意和比自己矮的异性跳舞，求最大匹配。 ( .. N <= 10^5 .. .) Problem E. sort 给出以下的一个排序算法.. while (未完成){ 将所有递减序列分离出来，进行 reverse() 操作。 } 给定一个 {1..N} 的排列，问这个排序算法会执行多少次 reverse() 操作。 ( .. N <= 10^5 .. ) Problem F. skakac 给定一块 N * N 的 chess 棋盘，每个格子上面标注一个数字，{aij} 表示这个格子在步数是 K 的倍数的时候会被 blocked。 现在给你一个 knight 的初始位置，问 T 步之后所有可能占据的位置。 ( .. N <= 30 ., T <= 10^6, aij <= 10^9 . ..)

Analysis:

A 略、B 略 （注意 MLE 的问题）、C 略 （按位统计）、D 略（排序、贪心，注意不要往图论方面想。。。)

E 模拟几个小数据。。发现用树状数组就行了。。

F 至于最后一题。。

#include<iostream>
using namespace std;
int n,m,k,col,l,r,ans;
int main(){
    for(cin>>n>>m>>k,l=1,r=l+m-1;k--;)
    if(cin>>col,col<l)ans+=l-col,l=col,r=l+m-1;
    else if(col>r)ans+=col-r,r=col,l=r-m+1;
    cout<<ans<<endl;
}

const int N = 409;
int A[N][N], L[N][N], R[N][N];
int n, res;
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    RD(n); REP_2(i, j, n, n) cin >> A[i][j];
 
    res = 0; REP(i, n){
 
        REP(j, n){
            L[j][0] = A[i][j], R[j][0] = A[i][j];
            REP_1(k, n){
                if (i+k==n||j+k==n) break;
                L[j][k] = L[j][k-1] + A[i+k][j+k];
            }
            REP_1(k, n){
                if (i+k==n||j-k==-1) break;
                R[j][k] = R[j][k-1] + A[i+k][j-k];
            }
        }
 
        REP(j, n) REP(k, n){
            if (j+k == n) break;
            checkMax(res, L[j][k] - R[j+k][k]);
        }
    }
 
    cout << res << endl;
}

#include<iostream>
using namespace std;
#define LL long long
const int N=20;
LL i,t,n,sum,a[N][2];
int main(){
    for(cin>>n;n--;)for(scanf("%d",&t),i=0;i<N;++a[i][!!(t&1<<i)],++i);
    for(i=0;i<N;++i)sum+=a[i][0]*a[i][1]*(1<<i);
    cout<<sum<<endl;
}

VI A1, A2, B1, B2;
int n, res;
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    RD(n);
 
    int ai; REP(i, n){
        RD(ai); if (ai > 0) A1.PB(ai); else A2.PB(ai);
    }
 
    int bi; REP(i, n){
        RD(bi); if (bi > 0) B1.PB(bi); else B2.PB(bi);
    }
 
    SRT(A1), SRT(A2), SRT(B1), SRT(B2);
 
    int j = 0; DWN(i, SZ(A1), 0){
        if (j < SZ(B2) && abs(B2[j]) > A1[i]) ++j;
    }
 
    res += j;
 
    j = 0; DWN(i, SZ(B1), 0){
        if (j < SZ(A2) && abs(A2[j]) > B1[i]) ++j;
    }
 
    res += j;
 
    cout << res << endl;
}

const int N = 100009;
int A[N], C[N], n;
 
int S(int x){
    int res = 0; while (x){res += C[x]; x ^= low_bit(x);}
    return res;
}
 
void M(int x){
    while (x <= n){++C[x], x += low_bit(x);}
}
 
int main(){
 
    REP_C(i, _RD(n)) RD(A[i]);
 
    LL ans = 0 ;
 
    for (int i=0,j=1;i<n;i=j,++j){
        while (j<n&&A[j]<A[j-1]) ++j; if (i+1<j) ++ans;
        DWN(k, j, i) ans += (i+j-k-1) - S(A[k]), M(A[k]);
    }
 
    cout << ans << "\n" ;
}

const int TT = 1000009, N = 32;
vector<short> mask[N];
short _[2], A[2][N]; int K[N], M[N];
int n, T, U, bj;
 
int lcm(LL a, LL b){
    LL t = a / __gcd(a, b) * b;
    if (t > T) return T + 1;
    return t;
}
 
void no_solution(){
    cout << 0 << endl;
    exit(0);
}
 
void init(){
    RD(n, T); int x0, y0; RD(x0, y0), --x0, --y0, A[0][x0] = _1(y0/2);
    bj = x0 ^ y0;
 
    int k, kk; REP(i, n){
 
        REP(j, n) RD(K[j]); M[i] = 2; REP(j, n) M[i] = lcm(M[i], K[j]);
        mask[i].resize(M[i]);
 
        REP(j, n){
            k = K[j]; if ((i^j^bj)&1){
                if (!(k&1)) continue; kk = k << 1;
                for (int t=k;t<M[i];t+=kk) mask[i][t] |= _1(j/2);
                if (M[i] <= T && T&1) mask[i][0] |= _1(j/2);
            }
            else {
                k = k & 1 ? k << 1 : k;
                for (int t=k;t<M[i];t+=k) mask[i][t] |= _1(j/2);
                if (M[i] <= T && !(T&1)) mask[i][0] |= _1(j/2);
            }
 
        }
    }
 
}
 
#define p (t&1)
#define q !p
 
void solve(){
    int S, op; REP_1(t, T){
        RST(A[p]); int tt = t ^ bj; REP(i, n) if (A[q][i]){
            op = (A[q][i] << 1) | (A[q][i] >> 1);
            A[p][i-1] |= op, A[p][i+1] |= op;
            if ((i^tt)&1) op = (A[q][i] >> 1) | A[q][i];
            else op = (A[q][i] << 1) | A[q][i];
            A[p][i-2] |= op, A[p][i+2] |= op;
        }
 
        REP(i, n) A[p][i] &= mask[i][t%M[i]];
    }
}
 
#undef p
 
void print(){
    int res = 0, p = T & 1;
    REP(i, n) res += count_bits(A[p][i]); cout << res << endl;
    REP_2(i, j, n, n) if (!((i^j^bj^T)&1) && _1(A[p][i], j/2)){
        cout << i+1 << " " << j+1 << endl;
    }
}
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    init(); solve();
    print();
}

Posted by xiaodao
Category: COCI