Wannafly Winter Camp 2020-Day5

w 本文总阅读量次

今天不自闭了 rk31

队里的罚时提供者 非ac的全是我交的(
开场写G 当时范围还是1e16 打了个表 等表的时候去看A(
一看 啊 啥玩意啊 咋写啊 我学不来啊
再一看 k<=3啊 那没事了
然后傻逼错误wa了3次 哈哈
然后表打完了 对着2e8想了一下 然后看看群 哦哦杜爹说改范围了
我对队友:”哦,我会!”
然后复杂度算错 -3 哈哈
数组开小re一次 最后+4
这时候是第七个过的!猛猛猛男
我:”反正别人有+11的!我的+4也还好8”
然后划水划了1h(?
帮队友康了康E 找到了几个bug 调了一下 过样例了!
我:”要不要交?”
队友:”交交交”
wa6
演 wz 演
然后写代码的队友找到了真正的bug!ac!
快乐地离场了

5A. Alternative Accounts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
int q[3][maxn];
vector<int>vv[6];
int main(){
    int n,k,m,a,cnt(0); sc(n); sc(k); rep(i,0,k){
        sc(m); rep(j,0,m) sc(a),q[i][a]++;
    } if(k==1) pf("%d",m);
    else if(k==2){
        rep(i,1,n+1){
            if(q[0][i]+q[1][i]==2) cnt++;
            else if(q[0][i]) vv[0].push_back(i);
            else if(q[1][i]) vv[1].push_back(i);
        } cnt+=max(vv[0].size(),vv[1].size());
        pf("%d\n",cnt);
    }
    else if(k==3){
        rep(i,1,n+1){
            if(q[0][i]+q[1][i]+q[2][i]==3) cnt++;
            else if(q[0][i]+q[1][i]+q[2][i]==2){
                if(q[0][i]&&q[1][i]) vv[0].push_back(i);
                if(q[0][i]&&q[2][i]) vv[1].push_back(i);
                if(q[1][i]&&q[2][i]) vv[2].push_back(i);
            } else if(q[0][i]+q[1][i]+q[2][i]==1){
                if(q[2][i]) vv[3].push_back(i);
                if(q[1][i]) vv[4].push_back(i);
                if(q[0][i]) vv[5].push_back(i);
            }
        } int sz[3]; mst(sz,0); rep(i,0,3) sz[i]=vv[i+3].size();
        rep(i,0,3) cnt+=vv[i].size(),sz[i]-=vv[i].size();
        rep(i,0,3) if(sz[i]<0) sz[i]=0;
        cnt+=max(sz[0],max(sz[1],sz[2]));
        pf("%d\n",cnt);
    }
}

5E. Matching Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
int n,ans,a[305],b[5],sum[305][305];
map<int,int>aaa;
int getsum(int x,int y,int z){
    int res=n-x; res-=sum[x+1][a[x]];
    if(a[x]!=a[y]) res-=sum[x+1][a[y]];
    if(a[x]!=a[z]&&a[y]!=a[z]) res-=sum[x+1][a[y]];
    return res;
}
int main(){
    sc(n); rep(i,1,n+1) sc(a[i]),aaa[a[i]]++;
    rep(i,1,5) sc(b[i]); dep(i,n,1){
        for(auto &x:aaa) sum[i][x.first]=sum[i+1][x.first];
        sum[i][a[i]]++;
    } int pos(0); rep(i,1,4) if(b[i]==b[4]) pos=i;
    rep(i,1,n+1) rep(j,i+1,n+1) rep(k,j+1,n+1){
        int ff=(pos==1?i:pos==2?j:k);
        if((a[i]==a[j])==(b[1]==b[2])&&(a[j]==a[k])==(b[2]==b[3])&&(a[i]==a[k])&&(b[1]==b[3]))
            ans+=ff?sum[k+1][a[ff]]:getsum(k,j,i);
    } pf("%d\n",ans);
}

5G. Cryptographically Secure Pseudorandom Number Generator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5e5 + 5;
pii a[2000]; int inv[maxn];
int solve(){
    int p,cnt(0),ff(0),mn; sc(p); if(p==1||p==2) return pf("0\n");
    inv[0]=0,inv[1]=1,inv[2]=p/2+1,mn=inv[2]; rep(i,2,p){
        inv[i]=1ll*(p-p/i)*inv[p%i]%p;
        if(inv[i]<=mn){
            if(inv[i]==a[cnt-1].first) break;
            mn=inv[i]; a[cnt++]=pii(i,inv[i]);
            if(i==inv[i]){ ff++; break; }
        }
    } pf("%d\n",cnt*2-ff);
    rep(i,0,cnt) pf("%d %d\n",a[i].first,a[i].second);
    dep(i,cnt-1-ff,0) pf("%d %d\n",a[i].second,a[i].first);
    return 0;
}
int main(){
    int _; sc(_); while(_--) solve();
}

补题：

5A. Alternative Accounts

短的

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int n,m,k,t,a,b,q[100005];
int main(){
    cin>>n>>k; while(k--){
        cin>>m; a=max(a,m);
        while(m--) cin>>t,q[t]++;
    } while(n--) if(q[n+1]>1) b++;
    cout<<max(a,b)<<'\n'; 
}

5J. Xor on Figures

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
char s[50][50];
bitset<1050>p[1050],q;
int n,cnt,ans=1,mod=1e9+7;
void change(int x,int y){
    rep(i,0,n) rep(j,0,n) q[(i+x)%n*n+(j+y)%n]=s[i][j]-'0';
    rep(i,0,n*n) if(q[i]==1){
        if(!p[i].count()){ p[i]=q; cnt++; break; } q^=p[i];
    }
}
int main(){
    sc(n); n=1<<n; rep(i,0,n) scs(s[i]);
    rep(i,0,n) rep(j,0,n) change(i,j); 
    rep(i,0,cnt) ans=2ll*ans%mod; pf("%d\n",ans); 
}
w