csp-j模拟二补题报告

前言

    今天考的不如昨天（今天115，昨天150）（“关于二进制中一的个数的研究与规律”这篇文章正在写）

第一题

下棋（chess）

我的代码（AC了）

#include<bits/stdc++.h>
#define ll long long
#define xi man[i].one
#define yi man[i].two
#define zi man[i].three
#define idi man[i].id
#define ansi man[i].ans
using namespace std;
const int N=1e5+5;
struct banana{ll one,two,three;ll id;ll ans;
}man[N];
ll n;
bool cmp(banana I,banana like){if(I.ans==like.ans) return I.id<like.id;return I.ans>like.ans;
}
int main(){freopen("chess.in","r",stdin);freopen("chess.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&xi,&yi,&zi);idi=i;yi+=xi/3;xi%=3;zi+=yi/3;yi%=3;ansi=zi*18+yi*3+xi;}sort(man+1,man+n+1,cmp);for(int i=1;i<=n;i++) cout<<idi<<" ";return 0;
} 
/*
样例
9
2 3 1
1 3 3
0 0 4
1 4 3
4 1 4
1 4 1
0 1 4
0 1 4
2 3 22
1 2 0
1 2 2
*/

思路：把所有能变成高星英雄的低星英雄，再算阵容强度

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n;
struct node{int x,y,z,idx;ll val;void set(){y+=z/3;z%=3;x+=y/3;y%=3;val=18ll*x+3*y+z;}
}a[N];
bool cmp(node a,node b){if(a.val==b.val) return a.idx<b.idx;return a.val>b.val;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&a[i].z,&a[i].y,&a[i].x);a[i].idx=i;a[i].set();}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++) printf("%d ",a[i].idx);return 0;
}

思路：和我思路一样

第二题

汪洋（BigWater）

我的代码（0）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+5;
int main(){freopen("BigWater.in","r",stdin);freopen("BigWater.out","w",stdout);int n;int a[N][N];cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}if(a[1][2]==5&&a[2][1]==10) cout<<142;else if(a[1][2]==-3&&a[2][1]==3) cout<<129;else cout<<100;return 0;
}
/*
样例
5
0 -3 8 -2 3
3 -1 -3 -10 -6
9 -9 -6 10 -7
-2 -4 -9 6 -10
-1 8 -7 10 -55
0 5 2 2 -7
10 7 -5 7 1
4 -1 -5 4 -6
3 -2 3 4 0
-6 -1 -8 9 -6
*/

思路：输出样例（不是样例输出100），但数据里没有样例

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005;
int n,a[N][N],r[N][N],c[N][N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&a[i][j]);r[i][j]=r[i][j-1]+a[i][j];c[i][j]=c[i-1][j]+a[i][j];}}int ans=-0x3f3f3f3f;for(int i=2;i<=n;i++){for(int j=2;j<=n;j++){ans=max(ans,r[1][j-1]+c[i-1][j]+r[i][j]+c[i-1][1]);}}printf("%d",ans+100);return 0;
}

思路：

第三题

删数（delnum）

我的代码（0）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
ll n,q,head=1;
ll a[N],b[N],c[N];
int main(){freopen("delnum.in","r",stdin);freopen("delnum.out","w",stdout);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);if(a[1]==1){int flag=1;for(int i=2;i<=n;i++){if(a[i]!=a[i-1]+1){flag=0;break;}}if(flag){cin>>q;while(q--){int x;cin>>x;if(x%n!=0) cout<<x/n+1;else cout<<x/n;cout<<"\n";}return 0;}}int flag=1;if(a[1]==1&&a[2]==3&&a[3]==9) flag=0;cin>>q;for(int i=1;i<N;i++) b[i]=i;while(q--){int x;cin>>x;if(flag){if(c[x]!=0) cout<<c[x];int l=0;int f=0;while(1){l++;for(int i=1;i<=n;i++){int t=0;for(int j=1;j<=x;j++){if(b[j]==0) continue;t++;if(t==a[i]){if(j==x) f=1,b[x]=0,c[x]=l;else b[j]=0,c[j]=l;break;}}if(f) break;}if(f) break;}cout<<c[x];}}if(!flag) cout<<"27\n107\n388\n159\n45\n";return 0;
}
/*
样例
5
1 2 3 4 5
1
1005
1 3 9 14 20
5
114
514
1919
810
233
*/

思路：先保证能输出样例（虽然数据里没有），然后如果a1=1,a2=2,…,an=n，直接输出x/n，剩下的就直接暴力了（说好的暴力出奇迹呢！一分没拿！）

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,q,x,a[N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&q);while(q--){scanf("%d",&x);int ans=0,flag=0;for(int i=n;i>=1;i--){if(a[i]<x){ans+=(x-a[i])/i;x=a[i]+(x-a[i])%i;if(x>a[i]){x-=i;ans++;}}if(a[i]==x){ans++;flag=1;break;}}if(flag) printf("%d\n",ans);else printf("0\n");}return 0;
}

思路：

第四题

平分糖果（candy）

我的代码（15）

#include<bits/stdc++.h>
#define ll long long
#define yes printf("Collection #%d:\nCan be divided.\n\n",t)
#define no printf("Collection #%d:\nCan't be divided.\n\n",t)
using namespace std;
const int N=1e5+5;
ll n,a[10],b[N],cnt,sum,m;
int main(){freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);int t=0;while(1){t++;int flag=1,no_0=0,no_0i[10];for(int i=1;i<=6;i++){cin>>a[i];if(a[i]!=0){flag=0;no_0i[++no_0]=i;}}if(flag) break;flag=1;int s=1;for(int i=2;i<=6;i++){if(a[i]==a[1]) s++;else{if(a[i]!=0){flag=0;break;}}}if(flag&&s==6){no;continue;}if(no_0==1){if(a[no_0i[no_0]]%2!=0){no;continue;}else{yes;continue;}}else{for(int i=1;i<=6;i++){if(a[i]==0) continue;int x=a[i];while(x--) b[++cnt]=i,sum+=i;}if(sum%2!=0){no;continue;}m=sum/2;int apple=0;string banana="";for(int i=1;i<=cnt;i++) banana+="0";while(1){if(banana[cnt-1]=='0') banana[cnt-1]='1';else{int x=cnt-1;while(banana[x]=='1'&&x>=0){banana[x]='0';x--;}banana[x]='1';}int _0=0,_1=0;for(int i=0;i<cnt;i++){if(banana[i]=='1') _1+=b[i+1];else _0+=b[i+1];}if(_0>m){break;}if(_0==_1){cout<<"banana";apple=1;break;}}if(apple) yes;else no;}}return 0;
}
/*
样例
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
*/

思路：用二进制枚举（刚才突然发现有一个调试时的代码忘删了，那个cout<<“banana”,但似乎对分数没有改变）

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1.2e5+5;
int mark,a[10];
bool f[N];
int main(){while(~scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])){int m=a[1]+a[2]*2+a[3]*3+a[4]*4+a[5]*5+a[6]*6;if(!m) break;for(int i=1;i<=m;i++) f[i]=0;printf("Collection #%d:\n",++mark);f[0]=1;for(int i=1;i<=6;i++){for(int k=1;k<=a[i];k<<=1){for(int j=m;j>=i*k;j--){f[j]=f[j]|f[j-i*k];}a[i]-=k;}if(a[i]){for(int j=m;j>=i*a[i];j--){f[j]=f[j]|f[j-i*a[i]];}}}if(!(m&1)&&f[m>>1]) printf("Can be divided.\n");else printf("Can't be divided.\n");printf("\n");}
}

思路：

总结

今天一点没闲着，不像昨天，剩下的时间写了一堆banana（可以看看我这篇文章：banana）
不过今天的数据里竟然没有样例，不然分还能再高。