CSP-S 9月模拟赛标程

魏晟伦 · 发表于 2021-10-17 15:28:45

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

T1

#include<iostream>
#include<cstring>
#define int long long
#define end endd
#define INF 5005
using namespace std;
int n,v,h,start[5005],sum[5005],end[5005],t,dp[5005];
string s;
signed main(){
//freopen("dance.in","r",stdin);
//freopen("dance.out","w","stdout);
cin>>n>>h;
for (int i=1;i<=n;i++){
scanf("%lld",&t);
sum[i]=sum[i-1]+t;
}
for (int i=1;i<=h;i++){
cin>>s;
int x=0,y=0,j=1;
while (s[j]!=',')
x+=s[j]-'0',x*=10,j++;
j++;
while ('0'<=s[j]&&s[j]<='9')
y+=s[j]-'0',y*=10,j++;
x/=10,y/=10;
if (s[j]=='I')
y=INF;
if (s[0]=='[')
start[i]=x;
if (s[0]=='(')
start[i]=x+1;
if (s[s.length()-1]==']')
end[i]=y;
if (s[s.length()-1]==')')
end[i]=y-1;
}
memset(dp,0x3f,sizeof(dp));
const int cord=dp[0];
dp[0]=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=h;j++){
if (start[j]<=i&&i<=end[j])
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]);
}
if (dp[i]>=cord)
v++,dp[i]=0;
}
if (!v)
printf("1\n%lld\n",dp[n]);
else
printf("0\n%lld\n",n-v);
//fclose(stdin);
//fclose(stdout);
return 0;
}

复制代码

魏晟伦 · 发表于 2021-10-17 15:29:26

T2

#include <iostream>
#include <cstring>
#define int long long
using namespace std;
int size,m,ans=-1e9,ans_r,mycon,pos,poss,a[500001],anss[500001][3],c[500001][3];
bool vis[1500001];
void dfs(register int m){
int tm=m;
if (m<0)
return;
int tmp=0;
for (register int i=1;i<=pos;i++){
if (vis[i])
continue;
if (a[i]>1){
for (register int j=1;j<=(a[i]>>1);j++){
vis[i]=true;
a[++pos]=j,c[++poss][0]=1,c[poss][1]=j,a[++pos]=c[poss][2]=a[i]-j;
dfs(m-a[i]+j);
pos-=2,poss--;
vis[i]=false;
}
}
for (register int j=i+1;j<=pos;j++)
if ((!vis[j])){
tm+=max(a[i],a[j])-min(a[i],a[j]);
c[++poss][0]=2,c[poss][1]=min(a[i],a[j]),c[poss][2]=max(a[i],a[j]),tmp++;
}
}
if (tm>ans){
ans_r=poss;
mycon=poss-tmp;
ans=tm;
memcpy(&anss,&c,sizeof(c));
}
poss-=tmp;
return;
}
signed main(){
//freopen("arknights.in","r",stdin);
//freopen("arknights.out","w",stdout);
cin>>size>>m;
a[1]=size,pos=1;
dfs(m);
cout<<ans<<endl;
if(ans==m){
printf("3\n");
return 0;
}
for (int i=mycon+1;i<=ans_r;i++)
for (int j=i+1;j<=ans_r;j++)
if (anss[i][1]>anss[j][1]||(anss[i][1]==anss[j][1]&&anss[i][2]>anss[j][2])){
swap(anss[i][1],anss[j][1]);
swap(anss[i][2],anss[j][2]);
}
for(int i=1;i<=ans_r;i++)
if (!(anss[i][0]==2&&(i<=mycon||anss[i][1]==anss[i][2])))
printf("%lld %lld %lld\n",anss[i][0],anss[i][1],anss[i][2]);
printf("3\n");
//fclose(stdin);
//fclose(stdout);
return 0;
}

复制代码

魏晟伦 · 发表于 2021-10-17 15:30:07

T3

#include<bits/stdc++.h>
#define vis viss
#define check checkk
#define stop stopp
#define int long long
using namespace std;
int a,b,p,q,num,T,fn[50001],pow_ab[55],pow_p[55],pow_q[55];
bool stop;
bool u=true;
inline bool check(int yours[],int expected[],bool flag){
if (flag){
for(int i=1;i<=num;i++)
if (yours[i]>expected[i])
return true;
return false;
}
for(int i=1;i<=num;i++)
if (yours[i]!=expected[i])
return false;
return true;
}
bool dfs(int now,int depth,int yours[],int expected[]){
if (now==depth){
stop=stop&&check(yours,expected,1);
return check(yours,expected,0);
}
if (u){
for (int i=1;i<=num;i++)
yours[i]+=pow_p[i];
if (dfs(now+1,depth,yours,expected))
return true;
}
for (int i=1;i<=num;i++)
yours[i]=(yours[i]-u*pow_p[i])<<1;
if (dfs(now+1,depth,yours,expected))
return true;
for (int i=1;i<=num;i++)
yours[i]=yours[i]>>1;
return false;
}
signed main(){
//freopen("digital.in","r",stdin);
//freopen("digital.out","w",stdout);
scanf("%lld",&T);
while (T--){
scanf("%lld%lld%lld%lld",&a,&b,&p,&q);
int w,v;
num=0;
memset(fn,0,sizeof(fn));
for (int i=1;i<=q;i++){
scanf("%lld,%lld",&w,&v);
//floor(sqrt(50000))=223
for (int j=2;j<=223;j++){
if (w%j)
continue;
if ((!fn[j])&&v)
num++,pow_q[num]=0,fn[j]=num;
while (!(w%j))
w/=j,pow_q[fn[j]]+=v;
}
if (w>1&&v&&(!fn[w]))
num++,pow_q[num]=v,fn[w]=num;
else if (w>1)
pow_q[fn[w]]+=v;
}
u=true;
bool vis;
if (p==1)
u=false;
for (int i=2;i<50000;i++){
vis=false;
int num=fn[i];
if (!(a%i))
pow_ab[num]=pow_p[num]=0;
while (!(a%i)) a/=i,vis=true,pow_ab[num]++;
while (!(b%i)) b/=i,pow_ab[num]++;
while (!(p%i)) p/=i,u=u&&vis,pow_p[num]++;
}
int numm=0;
if (a<50000)
numm=fn[a];
pow_ab[numm]=pow_p[numm]=0;
if (a>1) pow_ab[numm]++;
if (b>1) pow_ab[numm]++;
if (u&&p>1) u=u&&(p==a),pow_p[numm]++;
int depth=-1;
while (1){
depth++;
stop=true;
bool k=dfs(0,depth,pow_ab,pow_q);
if (k){
printf("%lld\n",depth);
break;
}
if (stop){
printf("-1\n");
break;
}
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}

复制代码

魏晟伦 · 发表于 2021-10-17 15:31:08

T4

#include<bits/stdc++.h>
#define vis viss
#define int long long
using namespace std;
int Q,v0,p,MOD,num,pri[15];
bool vis[505];
struct node{
int deg,val,cnt;
int pow[11];
}mytree[11];
int qpow(int a,int b){
int k=b?qpow(a,b/2):0;
k=((k%MOD)*(k%MOD))%MOD;
return b?((k*((b&1)?a:1))%MOD):1;
}
void get(){
for (int i=2;num<10;i++){
if (vis[i])
continue;
pri[++num]=i;
for (int j=i<<1;j<500;j+=i)
vis[j]=true;
}
}
int dfs(int pts,int s){
if (pts==p)
return s;
int ans=2e18;
bool flag=true;
for (int i=1;i<=pts;i++){
if (!ans)
break;
if (mytree[i].deg==2)
continue;
pts++;
int news;
for (int j=1;j<=mytree[i].cnt;j++)
mytree[pts].pow[j]=mytree[i].pow[j];
//memcpy(&mytree[pts].pow,&mytree[i].pow,sizeof(mytree[pts].pow));
for (int j=1;j<=mytree[i].cnt;j++){
mytree[pts].val=(mytree[i].val*qpow(pri[j],mytree[i].pow[j]+1))%MOD;
news=(s*mytree[pts].val)%MOD;
mytree[i].deg++;
mytree[pts].deg=0,mytree[pts].cnt=mytree[i].cnt;
mytree[pts].pow[j]+=mytree[pts].pow[j]+1;
ans=min(ans,dfs(pts,news));
mytree[pts].pow[j]-=mytree[pts].pow[j]+1;
mytree[i].deg--;
}
//printf("%lld\n",mytree[i].val);
mytree[pts].val=(mytree[i].val*pri[mytree[i].cnt+1])%MOD;
news=(s*mytree[pts].val)%MOD;
mytree[i].deg++;
mytree[pts].deg=0,mytree[pts].cnt=mytree[i].cnt+1;
mytree[pts].pow[mytree[pts].cnt]=1;
if (ans)
ans=min(ans,dfs(pts,news));
mytree[pts].pow[mytree[pts].cnt]=0;
mytree[i].deg--;
pts--;
}
return ans;
}
signed main(){
//freopen("goodtree.in","r",stdin);
//freopen("goodtree.out","w",stdout);
get();
scanf("%lld",&Q);
while (Q--){
scanf("%lld %lld %lld",&v0,&p,&MOD);
node root;
root.val=v0%MOD,root.deg=0,root.cnt=1,root.pow[1]=-1;
while (v0)
v0=v0>>1,root.pow[1]++;
mytree[1]=root;
printf("%lld\n",dfs(1,root.val));
}
//fclose(stdin);
//fclose(stdout);
return 0;
}

复制代码