2020 CCPC Wannafly Winter Camp Day5 (部分题解)

这场是英文题面QAQ，dlstql

7-1 5A. Alternative Accounts

每个数字有一个状态表示它在各个集合的情况：0表示不在任何集合，1表示在第一个集合，3表示在第一个和第二个集合……
显然，状态为0的数字可以不用管，状态为$2^k-1$2k−1的数字必定单独一个占一个集合。
那么当k=2，状态为1的和为2的可以彼此配对，构成$max(num[1],num[2])$max(num[1],num[2])个集合（num[state]表示状态为state的数字个数）。
当k=3的时候，二进制中有两个1的状态只能和另一种和它互补的状态合并，而且合并掉肯定比不合并要优，所以贪心的合并之后取$max(num[1], num[2],num[4])$max(num[1],num[2],num[4])就可以了。

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
int n, k;
const int maxn = 1e5 + 50;
int state[maxn];
int num[8];
int t[3];
int main()
{
    cin>>n>>k;
    for(int i = 0; i < k; ++i){
        cin>>t[i];
        for(int j = 0; j < t[i]; ++j){
            int x; scanf("%d", &x); state[x] |= (1<<i);
        }
    }
    for(int i = 1; i <= n; ++i) num[state[i]]++;
    if(k == 1){
        cout<<t[0]<<endl;
    }else if(k == 2){
        cout<<max(num[1] , num[2])+num[3]<<endl;
    }else{
        int ans = num[7];
        for(int i = 0; i < 3; ++i){
            int t = 7^(1<<i);
            ans += num[t];
            if(num[t] <= num[(1<<i)]) num[(1<<i)] -= num[t];
            else num[1<<i] = 0;
        }
        int temp = max(num[1], num[2]);
        temp = max(temp, num[4]);
        ans += temp;
        cout<<ans<<endl;
    }
}

7-5 5E. Matching Problem

注意到数据范围很小，$O(N^3)$O(N3)枚举前3个数字然后直接判断第四个数字就可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 330;
int cnt[maxn][maxn];
int a[maxn], b[10];
int n;
void read_data(){
    scanf("%d",&n);
    memset(cnt,0,sizeof(cnt));
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            cnt[i][j]=cnt[i-1][j];
        }
        scanf("%d",&a[i]);
        cnt[i][a[i]]++;
    }
    for (int i=1;i<=4;++i){
        scanf("%d",&b[i]);
    }
    return ;
}

int calc(int pos, int x1, int x2, int x3){
    int res=pos;
    res-=cnt[pos][x1];
    if (x2!=x1){
        res-=cnt[pos][x2];
    }
    if ((x3!=x1)&&(x3!=x2)){
        res-=cnt[pos][x3];
    }
    return res;
}

void sol(){
    long long ans=0;
    long long lcnt=0;
    for(int i=n;i>=1;--i){
        for(int j=i-1;j>=1;--j){
            if ((b[4]==b[3])^(a[i]==a[j])){
                continue;
            }
            for (int k=j-1;k>=1;--k){
                if ((b[3]==b[2])^(a[j]==a[k])){
                    continue;
                }
                if ((b[4]==b[2])^(a[i]==a[k])){
                    continue;
                }
                lcnt++;
                if (b[1]==b[2]){
                    ans+=cnt[k-1][a[k]];
                    continue;
                }
                if (b[1]==b[3]){
                    ans+=cnt[k-1][a[j]];
                    continue;
                }
                if (b[1]==b[4]){
                    ans+=cnt[k-1][a[i]];
                    continue;
                }
                ans+=calc(k-1,a[i],a[j],a[k]);
            }
        }
    }
    cout<<ans<<"\n";
    return ;
}

int main(){
    read_data();
    sol();
    return 0;
}

7-7 5G. Cryptographically Secure Pseudorandom Number Generator

可以双向枚举$i$i：
从2开始枚举$i$i获取$i$i的逆元$j$j，那么逆元为i的数字j也就得到了,维护一个枚举上限$u$u，当$j$j小于$u$u的时候就获得了一个答案并更新$u$u。因为逆元为$2,3,..j$2,3,..j的数字位置都已经在$u$u后面获得，所以u后面必然不会再有新答案产生。枚举到$i$i大于等于$u$u的时候终止就可以了。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6+10;

long long _inv[maxn];

void sol(){
    long long P,MXINV,inv;
    scanf("%lld",&P);
    MXINV=P;
    stack<pair<long long,long long> > limit;
    queue<pair<long long,long long> > ans;
    for (long long i=2;i<P;++i){
        if (!limit.empty()){
            if(i>=limit.top().first){
                while(!limit.empty()){
                    ans.push(limit.top());  limit.pop();
                }
                break;
            }
        }
        _inv[i]=((P-P/i)*_inv[P%i])%P;
        inv=_inv[i];
        if (inv<MXINV){
            ans.push(make_pair(i,inv));
            MXINV=inv;
            if (limit.empty()){
                limit.push(make_pair(inv,i));
            }else{
                if (limit.top().first>inv){
                    limit.push(make_pair(inv,i));
                }
            }
        }
    }
    printf("%d\n",ans.size());
    while(!ans.empty()){
        printf("%lld %lld\n",ans.front().first,ans.front().second); ans.pop();
    }
    return ;
}
int main(){
    _inv[0]=_inv[1]=1;
    int T;
    scanf("%d",&T);
    while(T--){
        sol();
    }
    return 0;
}

7-9 5I. Practice for KD Tree

先差分获得操作后的矩形，然后用4叉树或者二维线段树查询。
注意4叉树要加剪枝，查询到结点最大值小于等于答案就跳出。当然也可以对线段树加剪枝。
四叉树版本：
9600ms

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
const int maxn = 2e3+5;
ll a[maxn][maxn];
int n, m1, m2;
ll val[maxn*maxn*8];
void build(int rt, int x1, int y1, int x2, int y2){

    //cout<<"rt:"<<rt<<" x1:"<<x1<<" y1:"<<y1<<" x2:"<<x2<<" y2:"<<y2<<endl;//<<" val:"<<val[rt]<<endl;
    if(x1 > x2 || y1 > y2) return;
    if(x1 == x2 && y1 == y2){
        val[rt] = a[x1][y1];
        //cout<<"~rt:"<<rt<<" x1:"<<x1<<" y1:"<<y1<<" x2:"<<x2<<" y2:"<<y2<<" val:"<<val[rt]<<endl;
        return;
    }
    int midx = (x1+x2)>>1;
    int midy = (y1+y2)>>1;
    build(4*rt+1, x1, y1, midx, midy);
    build(4*rt+2, midx+1, y1, x2, midy);

    build(4*rt+3, x1, midy+1, midx, y2);
    build(4*rt+4, midx+1, midy+1, x2, y2);
    val[rt] = max(val[rt], val[rt*4+1]);
    val[rt] = max(val[rt], val[rt*4+2]);
    val[rt] = max(val[rt], val[rt*4+3]);
    val[rt] = max(val[rt], val[rt*4+4]);
    //cout<<"rt:"<<rt<<" x1:"<<x1<<" y1:"<<y1<<" x2:"<<x2<<" y2:"<<y2<<" val:"<<val[rt]<<endl;

}
ll ans;
void qry(int rt, int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2){
    if(x1 > x2 || y1 > y2) return ;
    if(x1 > X2 || x2 < X1) return ;
    if(y1 > Y2 || y2 < Y1) return ;
    if(val[rt] <= ans) return;
    //cout<<"rt:"<<rt<<" x1:"<<x1<<" y1:"<<y1<<" x2:"<<x2<<" y2:"<<y2<<" val:"<<val[rt];
    //cout<<" X1:"<<X1<<" X2:"<<X2<<" Y1:"<<Y1<<" Y2:"<<Y2<<endl;
    if(X1 <= x1 && x2 <= X2 && Y1 <= y1 && y2 <= Y2){
        //cout<<"rt:"<<rt<<" x1:"<<x1<<" y1:"<<y1<<" x2:"<<x2<<" y2:"<<y2<<" val:"<<val[rt]<<endl;;
        //return val[rt];
        ans = max(ans, val[rt]);
        return;
    }
    //cout<<"x1:"<<x1<<" y1:"<<y1<<" x2:"<<x2<<" y2:"<<y2<<endl;
    int midx = (x1+x2)>>1;
    int midy = (y1+y2)>>1;
    //if(X1 <= midx && Y1 <= midy)
     //   temp = max(temp, qry(4*rt+1, x1, y1, midx, midy, X1, Y1, X2, Y2));
     qry(4*rt+1, x1, y1, midx, midy, X1, Y1, X2, Y2);
    //if(X2 > midx && Y1 <= midy)
     //   temp = max(temp, qry(4*rt+2, midx+1, y1, x2, midy, X1, Y1, X2, Y2));
     qry(4*rt+2, midx+1, y1, x2, midy, X1, Y1, X2, Y2);
  //  if(X1 <= midx && Y1 > midy)
     //   temp = max(temp, qry(4*rt+3, x1, midy+1, midx, y2, X1, Y1, X2, Y2));
     qry(4*rt+3, x1, midy+1, midx, y2, X1, Y1, X2, Y2);
    //if(X1 > midx && Y1 > midy)
       // temp = max(temp, qry(4*rt+4, midx+1, midy+1, x2, y2, X1, Y1, X2, Y2));
       qry(4*rt+4, midx+1, midy+1, x2, y2, X1, Y1, X2, Y2);
    return ;
}
int main()
{
    cin>>n>>m1>>m2;
    while(m1--){
        int x1, x2, y1, y2; ll w;
        scanf("%d%d%d%d%lld", &x1, &y1, &x2, &y2, &w);
        a[x1][y1] += w;
        a[x1][y2+1] -= w;
        a[x2+1][y1] -= w;
        a[x2+1][y2+1] += w;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j<= n; ++j){
             a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
             //cout<<a[i][j]<<" ";
        }//cout<<endl;
    }
    build(0, 1, 1, n, n);
    //cout<<"?"<<endl;
    while(m2--){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        ans = 0;
        qry(0, 1, 1, n, n, x1, y1, x2, y2);
        printf("%lld\n", ans);
    }
}
/*
5 5 5
1 1 4 5 4
4 1 4 1 10
1 3 3 3 3
1 1 5 5 8
2 4 4 5 8
*/

二维线段树版本
1991ms

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const int maxn = 2005;
ll a[maxn][maxn];
ll val[maxn<<2][maxn<<2];
int n;
inline int id(int l, int r){
    return (l + r | l != r);
}
void build_y(int L, int l, int r){
    int rt = id(l, r);
    int pos = id(L, L);
    if(l == r){
        val[pos][rt] = a[L][l];
        //cout<<"i:"<<L<<" j:"<<l<<" a:"<<a[L][l]<<endl;
        return;
    }
    build_y(L, l, mid); build_y(L, mid+1, r);
    val[pos][rt] = max(val[pos][id(l, mid)], val[pos][id(mid+1, r)]);
    return;
}
void merge(int p, int p1, int p2, int l, int r){
    int rt = id(l, r);
    val[p][rt] = max(val[p1][rt], val[p2][rt]);
    if(l == r) return;
    merge(p, p1, p2, l, mid);
    merge(p, p1, p2, mid+1, r);
}
void build_x(int l, int r){
    if(l == r){
        build_y(l, 1, n);
        return;
    }
    build_x(l, mid); build_x(mid+1, r);
    merge(id(l, r), id(l, mid), id(mid+1, r), 1, n);
}
int lx, rx, ly, ry;
ll qry_y(int pos, int l, int r){
    int rt = id(l, r);
    if(ly <= l && r <= ry){
        return val[pos][rt];
    }
    ll ans = 0;
    if(ly <= mid) ans = max(ans, qry_y(pos, l, mid));
    if(ry > mid) ans = max(ans, qry_y(pos, mid+1, r));
    return ans;
}
ll qry_x(int l, int r){
    if(lx <= l && r <= rx){
        return qry_y(id(l, r), 1, n);
    }
    ll ans = 0;
    if(lx <= mid) ans = max(ans, qry_x(l, mid));
    if(rx > mid) ans = max(ans, qry_x(mid+1, r));
    return ans;
}
int m1, m2;
int main()
{
    cin>>n>>m1>>m2;
    while(m1--){
        int x1, x2, y1, y2; ll w;
        scanf("%d%d%d%d%lld", &x1, &y1, &x2, &y2, &w);
        a[x1][y1] += w;
        a[x1][y2+1] -= w;
        a[x2+1][y1] -= w;
        a[x2+1][y2+1] += w;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j<= n; ++j)
             a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
    build_x(1, n);
    while(m2--){
        scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
        printf("%lld\n", qry_x(1, n));
    }
}

7-10 5J. Xor on Figures

可以把$2^k*2^k$2k∗2k个导致的结果都弄出来，最多是1024个1024位的向量，然后求这些01向量任意异或能组合成多少个不同的向量，求一下线性基的个数$r$r，$2^r$2r就是答案

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define ull unsigned long long
using namespace std;
const int maxn = 1050;
bitset<maxn> p[1050];
ull sed = 131;
int a[maxn][maxn];
char s[maxn][maxn];
int n, k;
void sol(int x, int y){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(s[i][j] == '1'){
                a[(x+i)%n][(y+j)%n] = 1;
            }
            else a[(x+i)%n][(y+j)%n] = 0;
        }
    }
    bitset<maxn> v; v.reset();
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            v[i*n+j] = a[i][j];
        }
    }
    for(int i = 0; i < n*n; ++i){
        if(v[i] && p[i].count()){
            v = v^p[i];
        }else if(v[i]){
            p[i] = v;
            break;
        }
    }
}
const ll mod = 1e9 + 7;
ll qm(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b >>= 1;
    } return res;
}
int main()
{
    cin>>k; n = 1<<k;
    for(int i = 0; i < n; ++i){
        scanf("%s", s[i]);
    }
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            sol(i, j);
        }
    }
    ll ans = 0;
    for(int i = 0; i < n*n; ++i) if(p[i][i]) ans++;
    ans = qm(2, ans);
    cout<<ans<<endl;
}