CSP-S 9月模拟赛标程

魏晟伦

建议优先自行思考。
不建议直接copy代码。

T1

1. #include<iostream>
   
2. #include<cstring>
   
3. #define int long long
   
4. #define end endd
   
5. #define INF 5005
   
6. using namespace std;
   
7. int n,v,h,start[5005],sum[5005],end[5005],t,dp[5005];
   
8. string s;
   
9. signed main(){
   
10.     //freopen("dance.in","r",stdin);
    
11.     //freopen("dance.out","w","stdout);
    
12.     cin>>n>>h;
    
13.     for (int i=1;i<=n;i++){
    
14.         scanf("%lld",&t);
    
15.         sum[i]=sum[i-1]+t;
    
16.     }
    
17.     for (int i=1;i<=h;i++){
    
18.         cin>>s;
    
19.         int x=0,y=0,j=1;
    
20.         while (s[j]!=',')
    
21.             x+=s[j]-'0',x*=10,j++;
    
22.         j++;
    
23.         while ('0'<=s[j]&&s[j]<='9')
    
24.             y+=s[j]-'0',y*=10,j++;
    
25.         x/=10,y/=10;
    
26.         if (s[j]=='I')
    
27.             y=INF;
    
28.         if (s[0]=='[')
    
29.             start[i]=x;
    
30.         if (s[0]=='(')
    
31.             start[i]=x+1;
    
32.         if (s[s.length()-1]==']')
    
33.             end[i]=y;
    
34.         if (s[s.length()-1]==')')
    
35.             end[i]=y-1;
    
36.     }
    
37.     memset(dp,0x3f,sizeof(dp));
    
38.     const int cord=dp[0];
    
39.     dp[0]=0;
    
40.     for (int i=1;i<=n;i++){
    
41.         for (int j=1;j<=h;j++){
    
42.             if (start[j]<=i&&i<=end[j])
    
43.                 dp[i]=min(dp[i],dp[start[j]-1]+min(n,end[j])-start[j]+1+sum[min(n,end[j])]-sum[start[j]-1]);
    
44.         }
    
45.         if (dp[i]>=cord)
    
46.             v++,dp[i]=0;
    
47.     }
    
48.     if (!v)
    
49.         printf("1\n%lld\n",dp[n]);
    
50.     else
    
51.         printf("0\n%lld\n",n-v);
    
52.     //fclose(stdin);
    
53.     //fclose(stdout);
    
54.     return 0;
    
55. }

复制代码

魏晟伦

T2

1. #include <iostream>
   
2. #include <cstring>
   
3. #define int long long
   
4. using namespace std;
   
5. int size,m,ans=-1e9,ans_r,mycon,pos,poss,a[500001],anss[500001][3],c[500001][3];
   
6. bool vis[1500001];
   
7. void dfs(register int m){
   
8.     int tm=m;
   
9.     if (m<0)
   
10.         return;
    
11.     int tmp=0;
    
12.     for (register int i=1;i<=pos;i++){
    
13.         if (vis[i])
    
14.             continue;
    
15.         if (a[i]>1){
    
16.             for (register int j=1;j<=(a[i]>>1);j++){
    
17.                 vis[i]=true;
    
18.                 a[++pos]=j,c[++poss][0]=1,c[poss][1]=j,a[++pos]=c[poss][2]=a[i]-j;
    
19.                 dfs(m-a[i]+j);
    
20.                 pos-=2,poss--;
    
21.                 vis[i]=false;
    
22.             }
    
23.         }
    
24.         for (register int j=i+1;j<=pos;j++)
    
25.             if ((!vis[j])){
    
26.                 tm+=max(a[i],a[j])-min(a[i],a[j]);
    
27.                 c[++poss][0]=2,c[poss][1]=min(a[i],a[j]),c[poss][2]=max(a[i],a[j]),tmp++;
    
28.             }
    
29.     }
    
30.     if (tm>ans){
    
31.         ans_r=poss;
    
32.         mycon=poss-tmp;
    
33.         ans=tm;
    
34.         memcpy(&anss,&c,sizeof(c));
    
35.     }
    
36.     poss-=tmp;
    
37.     return;
    
38. }
    
39. signed main(){
    
40.     //freopen("arknights.in","r",stdin);
    
41.     //freopen("arknights.out","w",stdout);
    
42.     cin>>size>>m;
    
43.     a[1]=size,pos=1;
    
44.     dfs(m);
    
45.     cout<<ans<<endl;
    
46.       
    
47.     if(ans==m){
    
48.         printf("3\n");
    
49.         return 0;
    
50.     }
    
51.     for (int i=mycon+1;i<=ans_r;i++)
    
52.         for (int j=i+1;j<=ans_r;j++)
    
53.             if (anss[i][1]>anss[j][1]||(anss[i][1]==anss[j][1]&&anss[i][2]>anss[j][2])){
    
54.                 swap(anss[i][1],anss[j][1]);
    
55.                 swap(anss[i][2],anss[j][2]);
    
56.             }
    
57.       
    
58.     for(int i=1;i<=ans_r;i++)
    
59.         if (!(anss[i][0]==2&&(i<=mycon||anss[i][1]==anss[i][2])))
    
60.             printf("%lld %lld %lld\n",anss[i][0],anss[i][1],anss[i][2]);
    
61.     printf("3\n");
    
62.     //fclose(stdin);
    
63.     //fclose(stdout);
    
64.     return 0;
    
65. }

复制代码

魏晟伦

T3

1. #include<bits/stdc++.h>
   
2. #define vis viss
   
3. #define check checkk
   
4. #define stop stopp
   
5. #define int long long
   
6. using namespace std;
   
7. int a,b,p,q,num,T,fn[50001],pow_ab[55],pow_p[55],pow_q[55];
   
8. bool stop;
   
9. bool u=true;
   
10. inline bool check(int yours[],int expected[],bool flag){
    
11.     if (flag){
    
12.         for(int i=1;i<=num;i++)
    
13.             if (yours[i]>expected[i])
    
14.                 return true;
    
15.         return false;
    
16.     }
    
17.     for(int i=1;i<=num;i++)
    
18.         if (yours[i]!=expected[i])
    
19.             return false;
    
20.     return true;
    
21. }
    
22. bool dfs(int now,int depth,int yours[],int expected[]){
    
23.      if (now==depth){
    
24.          stop=stop&&check(yours,expected,1);
    
25.          return check(yours,expected,0);
    
26.      }
    
27.      if (u){
    
28.         for (int i=1;i<=num;i++)
    
29.             yours[i]+=pow_p[i];
    
30.         if (dfs(now+1,depth,yours,expected))
    
31.             return true;
    
32.      }
    
33.      for (int i=1;i<=num;i++)
    
34.         yours[i]=(yours[i]-u*pow_p[i])<<1;
    
35.      if (dfs(now+1,depth,yours,expected))
    
36.         return true;
    
37.      for (int i=1;i<=num;i++)
    
38.         yours[i]=yours[i]>>1;
    
39.      return false;
    
40. }
    
41. signed main(){
    
42.     //freopen("digital.in","r",stdin);
    
43.     //freopen("digital.out","w",stdout);
    
44.     scanf("%lld",&T);
    
45.     while (T--){
    
46.         scanf("%lld%lld%lld%lld",&a,&b,&p,&q);
    
47.         int w,v;
    
48.         num=0;
    
49.         memset(fn,0,sizeof(fn));
    
50.         for (int i=1;i<=q;i++){
    
51.             scanf("%lld,%lld",&w,&v);
    
52.             //floor(sqrt(50000))=223
    
53.             for (int j=2;j<=223;j++){
    
54.                 if (w%j)
    
55.                     continue;
    
56.                 if ((!fn[j])&&v)
    
57.                     num++,pow_q[num]=0,fn[j]=num;
    
58.                 while (!(w%j))
    
59.                     w/=j,pow_q[fn[j]]+=v;
    
60.             }
    
61.             if (w>1&&v&&(!fn[w]))
    
62.                 num++,pow_q[num]=v,fn[w]=num;
    
63.             else if (w>1)
    
64.                 pow_q[fn[w]]+=v;
    
65.         }
    
66.         u=true;
    
67.         bool vis;
    
68.         if (p==1)
    
69.             u=false;
    
70.         for (int i=2;i<50000;i++){
    
71.             vis=false;
    
72.             int num=fn[i];
    
73.             if (!(a%i))
    
74.                 pow_ab[num]=pow_p[num]=0;
    
75.             while (!(a%i)) a/=i,vis=true,pow_ab[num]++;
    
76.             while (!(b%i)) b/=i,pow_ab[num]++;
    
77.             while (!(p%i)) p/=i,u=u&&vis,pow_p[num]++;
    
78.         }
    
79.         int numm=0;
    
80.         if (a<50000)
    
81.             numm=fn[a];
    
82.         pow_ab[numm]=pow_p[numm]=0;
    
83.         if (a>1) pow_ab[numm]++;
    
84.         if (b>1) pow_ab[numm]++;
    
85.         if (u&&p>1) u=u&&(p==a),pow_p[numm]++;
    
86.         int depth=-1;
    
87.         while (1){  
    
88.             depth++;        
    
89.             stop=true;
    
90.             bool k=dfs(0,depth,pow_ab,pow_q);
    
91.             if (k){
    
92.                 printf("%lld\n",depth);
    
93.                 break;
    
94.             }
    
95.             if (stop){
    
96.                 printf("-1\n");
    
97.                 break;  
    
98.             }
    
99.         }
    
100.     }
     
101.     //fclose(stdin);
     
102.     //fclose(stdout);
     
103.     return 0;
     
104. }

复制代码

魏晟伦

T4

1. #include<bits/stdc++.h>
   
2. #define vis viss
   
3. #define int long long
   
4. using namespace std;
   
5. int Q,v0,p,MOD,num,pri[15];
   
6. bool vis[505];
   
7. struct node{
   
8.     int deg,val,cnt;
   
9.     int pow[11];
   
10. }mytree[11];
    
11. int qpow(int a,int b){
    
12.     int k=b?qpow(a,b/2):0;
    
13.     k=((k%MOD)*(k%MOD))%MOD;
    
14.     return b?((k*((b&1)?a:1))%MOD):1;
    
15. }
    
16. void get(){
    
17.     for (int i=2;num<10;i++){
    
18.         if (vis[i])
    
19.             continue;
    
20.         pri[++num]=i;
    
21.         for (int j=i<<1;j<500;j+=i)
    
22.             vis[j]=true;
    
23.     }
    
24. }
    
25. int dfs(int pts,int s){
    
26.     if (pts==p)
    
27.         return s;
    
28.     int ans=2e18;
    
29.     bool flag=true;
    
30.     for (int i=1;i<=pts;i++){
    
31.         if (!ans)
    
32.             break;
    
33.         if (mytree[i].deg==2)
    
34.             continue;
    
35.         pts++;
    
36.         int news;
    
37.         for (int j=1;j<=mytree[i].cnt;j++)
    
38.              mytree[pts].pow[j]=mytree[i].pow[j];
    
39.         //memcpy(&mytree[pts].pow,&mytree[i].pow,sizeof(mytree[pts].pow));
    
40.         for (int j=1;j<=mytree[i].cnt;j++){
    
41.             mytree[pts].val=(mytree[i].val*qpow(pri[j],mytree[i].pow[j]+1))%MOD;
    
42.             news=(s*mytree[pts].val)%MOD;
    
43.             mytree[i].deg++;
    
44.             mytree[pts].deg=0,mytree[pts].cnt=mytree[i].cnt;
    
45.             mytree[pts].pow[j]+=mytree[pts].pow[j]+1;
    
46.             ans=min(ans,dfs(pts,news));
    
47.             mytree[pts].pow[j]-=mytree[pts].pow[j]+1;
    
48.             mytree[i].deg--;
    
49.         }
    
50.         //printf("%lld\n",mytree[i].val);
    
51.         mytree[pts].val=(mytree[i].val*pri[mytree[i].cnt+1])%MOD;
    
52.         news=(s*mytree[pts].val)%MOD;
    
53.         mytree[i].deg++;
    
54.         mytree[pts].deg=0,mytree[pts].cnt=mytree[i].cnt+1;
    
55.         mytree[pts].pow[mytree[pts].cnt]=1;
    
56.         if (ans)
    
57.             ans=min(ans,dfs(pts,news));
    
58.         mytree[pts].pow[mytree[pts].cnt]=0;
    
59.         mytree[i].deg--;
    
60.         pts--;
    
61.     }
    
62.     return ans;
    
63. }
    
64. signed main(){
    
65.         //freopen("goodtree.in","r",stdin);
    
66.         //freopen("goodtree.out","w",stdout);
    
67.     get();
    
68.     scanf("%lld",&Q);
    
69.     while (Q--){
    
70.         scanf("%lld %lld %lld",&v0,&p,&MOD);
    
71.         node root;
    
72.         root.val=v0%MOD,root.deg=0,root.cnt=1,root.pow[1]=-1;
    
73.         while (v0)
    
74.             v0=v0>>1,root.pow[1]++;
    
75.         mytree[1]=root;
    
76.         printf("%lld\n",dfs(1,root.val));
    
77.     }
    
78.         //fclose(stdin);
    
79.         //fclose(stdout);
    
80.     return 0;
    
81. }

复制代码