普及组集训【模拟二】—

题目分数

第一题：100

第二题：100

第三题：60（加一个一就过了）

第四题：85

总分：345

考试过程

第一题5分钟写完，调bug的时间有点长，本题大约用了15分钟，第二题本人感觉有点难，一开始我以为是很难的，所以我一开始想要用dfs，最后我仔细看一眼题，所以就想到了用前缀和，第三题我看了一眼就想到了，所以本人以为做出来了，但是并没有，第四题直接暴力枚举，所以拿了部分分。

题目解析

第一题：下棋（chess）

上一题下一题

题目大意：一个合成类小游戏，就是一个合成+排序的过程

我的思路：一目了然，不言而喻就是模拟，如果有3个以上的1星就合成2星，有3个以上的2星就合成3星，根据题目中的式子x+3y+18z可以知道，怎么做都不会亏，所以模拟即可

我的代码：

#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define f first #define s second #define PII pair<int,int> #define pll pair<ll,ll> int n; const int N = 1e6+10; struct node{ ll x,y,z,num; ll fen; }a[N]; bool cmp(node a,node b){ if(a.fen==b.fen) return a.num<b.num; return a.fen>b.fen; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen("chess.in","r",stdin); freopen("chess.out","w",stdout); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y>>a[i].z; if(a[i].x>=3) a[i].y+=a[i].x/3,a[i].x%=3; if(a[i].y>=3) a[i].z+=a[i].y/3,a[i].y%=3; // cout<<endl<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<endl; a[i].fen=a[i].x+3*a[i].y+18*a[i].z,a[i].num=i; } // for(int i=1;i<=n;i++) cout<<a[i].fen<<endl; sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) cout<<a[i].num<<" "; return 0; } //2 //1 2 0 //1 2 2

第二题：汪洋（BigWater）

题目大意：long long ago 有一个人一开始有100的开心值，每次可以按照当前方向走一步，或者是可以按照顺时针走90°，就是往右走转了以后为往下走，但是在一个格子中不能连续转两次，一开始是往右走的，同一个格子只能走一遍（除了（1，1）），路过的每一个格子，都是需要加起来，路径为从起点（1，1）开始转一圈回到（1，1），要求开心值最大。

我的思路：因为他是只能顺时针旋转并且一个格子只能走一遍，所以我们可以想到就是走一个环直接绕回来，所以我么们可以想到用二维前缀和，用容斥原理就可以知道这一个环的路径大小，最后这个环的大小求一个最大的环的路径大小（以（i，j）为右下角顶点的环的值为sum[i][j]-sum[i-1][j-1]+sum[1][j-1]+sum[i-1][1]），中间要确定把一个点会转两次的情况给排除掉即可

我的代码;

#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define f first #define s second #define PII pair<int,int> #define pll pair<ll,ll> const int N = 1005; int cnt=1,n,a[N][N]; ll sum[N][N]; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen("BigWater.in","r",stdin); freopen("BigWater.out","w",stdout); cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j]; } } ll maxx=LONG_LONG_MIN; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==1||j==1) continue; maxx=max(maxx,sum[i][j]-sum[i-1][j-1]+sum[1][j-1]+sum[i-1][1]); } } cout<<100+maxx; return 0; } //5 //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

第三题：拯救小精灵（gremlin）

题目大意：有x个精灵，有y个恶魔，有m条绳子，只要绳子的两端不是恶魔，就要割下来，那个绳子的强度是可以加强的，用一点魔法能量就可以，如果有两个恶魔被拴在一起，就不用管他，剩下的恶魔要用绳子捆起来，如果不行输出-1，最后用最少的魔力可以全部解决。

我的思路：把所有的能割下来的绳子割下来，用一个数组存起来，把所有的不用捆起来的恶魔给单独标记一下，最后把恶魔的恶魔值从大到小排序，用一个计数器看看需要捆起来几个恶魔，如果绳子的个数如果不如需要捆起来的恶魔多的话，直接输出-1，否则把绳子的能力值也是从小到大排序，最后拿大绳子捆住大恶魔，如果大绳子不行就用魔法能量去加强，最后输出用了多少魔法能量

我的错因：遍历所有的恶魔的时候，把最后一个精灵也算进去了，所以多了一个，我加上了这（+1）两个字符，就从60分变成100分了

我的代码：

#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define f first #define s second #define PII pair<int,int> #define pll pair<ll,ll> const int N = 1e6+10; ll x,y,m,cnt,b[N],cntt; pair<ll,bool> a[N]; bool cmp(pair<ll,bool> a,pair<ll,bool> b){ return a.f>b.f; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen("gremlin.in","r",stdin); freopen("gremlin.out","w",stdout); cin>>x>>y>>m; for(int i=1;i<=y;i++) cin>>a[i+x].f; for(int i=1;i<=m;i++){ ll u,v,w; cin>>u>>v>>w; if(u<=x||v<=x) b[++cnt]=w; if(u>x&&v>x) a[u].s=a[v].s=1; } sort(b+1,b+1+cnt,greater<int> ()); sort(a+1+x,a+x+1+y,cmp); for(int i=x;i<=x+y;i++){ if(a[i].s==0) cntt++; } ll cnttt=1,ans=0; if(cntt>cnt){ cout<<-1; return 0;} // for(int i=x+1;i<=x+y;i++) cout<<a[i].f<<" "<<a[i].s<<endl; // cout<<endl; // for(int i=1;i<=cnt;i++) cout<<b[i]<<endl; for(int i=x+1;i<=x+y;i++){ if(a[i].s==0&&b[cnttt]>=a[i].f) cnttt++,a[i].s=1; else if(a[i].s==0&&b[cnttt]<a[i].f) ans+=(a[i].f-b[cnttt]),cnttt++; } cout<<ans; return 0; } //1 3 1 //5 6 7 //1 2 100

正确代码（不仔细看根本看不出来和我的代码的差异）

#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define f first #define s second #define PII pair<int,int> #define pll pair<ll,ll> const int N = 1e6+10; ll x,y,m,cnt,b[N],cntt; pair<ll,bool> a[N]; bool cmp(pair<ll,bool> a,pair<ll,bool> b){ return a.f>b.f; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen("gremlin.in","r",stdin); freopen("gremlin.out","w",stdout); cin>>x>>y>>m; for(int i=1;i<=y;i++) cin>>a[i+x].f; for(int i=1;i<=m;i++){ ll u,v,w; cin>>u>>v>>w; if(u<=x||v<=x) b[++cnt]=w; if(u>x&&v>x) a[u].s=a[v].s=1; } sort(b+1,b+1+cnt,greater<int> ()); sort(a+1+x,a+x+1+y,cmp); for(int i=x;i<=x+y;i++){ if(a[i].s==0) cntt++; } ll cnttt=1,ans=0; if(cntt>cnt){ cout<<-1; return 0;} // for(int i=x+1;i<=x+y;i++) cout<<a[i].f<<" "<<a[i].s<<endl; // cout<<endl; // for(int i=1;i<=cnt;i++) cout<<b[i]<<endl; for(int i=x+1;i<=x+y;i++){ if(a[i].s==0&&b[cnttt]>=a[i].f) cnttt++,a[i].s=1; else if(a[i].s==0&&b[cnttt]<a[i].f) ans+=(a[i].f-b[cnttt]),cnttt++; } cout<<ans; return 0; } //1 3 1 //5 6 7 //1 2 100

第四题：平分糖果（candy）

题目大意：有6种糖果有不同的得分，给你他们的数量，最后问你能不能把他们平均分成两堆，使他们的得分相等

我的思路：每个糖果都分类讨论，如果是第一堆分少，就给第一堆，否则就给第二堆

我的错因：想到了这个感觉是01背包并且是全部装满的背包，但是我的时间复杂度可能会爆炸，所以我就写了一个随缘代码，没想到85分

我的代码：

#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define f first #define s second #define PII pair<int,int> #define pll pair<ll,ll> const int N = 1e6+10; int a[10]; ll sum,cnt=1,cntt; bool flag=0; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen("candy.in","r",stdin); freopen("candy.out","w",stdout); while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]){ if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0) return 0; cout<<"Collection #"<<cnt<<":"<<endl; cnt++; ll sum1=0,sum2=0; for(int i=6;i>=1;i--){ for(int j=1;j<=a[i];j++){ if(sum1<sum2) sum1+=i; else sum2+=i; } } if(sum1!=sum2) cout<<"Can't be divided."<<endl; else cout<<"Can be divided."<<endl; cout<<endl; } return 0; } //1 0 1 2 0 0 //1 0 0 0 1 1 //0 0 0 0 0 0

正确思路：用多重背包（完全装满的），中间需要用二进制拆位，去优化他。所以最后看看，如果最终的得分数是个偶数，并且得分总数的1/2是可以拆出来的，我们就说他是可以的，否则，就是不可以的

正确代码：

#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define f first #define s second #define PII pair<int,int> #define pll pair<ll,ll> const int N = 1.2e5+10; int a[10]; ll dp[N],sum,cnt=1,cntt; bool flag=0; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("candy.in","r",stdin); // freopen("candy.out","w",stdout); while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]){ if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0) return 0; cout<<"Collection #"<<cnt<<":"<<endl; cnt++; sum=0; for(int i=1;i<=6;i++) sum+=i*a[i];//统计得分 // assert(sum<=120000); for(int i=1;i<=sum;i++) dp[i]=0;//初始化 dp[0]=1;//是否装满的初始化 for(int i=1;i<=6;i++){ for(int k=1;k<=a[i];k<<=1){//二进制 for(int j=sum;j>=i*k;j--) dp[j]=dp[j]|dp[j-i*k];//或的意思是这次装满或者是之前装满 a[i]-=k;//把装满的减去 } if(a[i]){//如果还有剩下的 for(int j=sum;j>=i*a[i];j--) dp[j]=dp[j]|dp[j-i*a[i]];//做一次不同的01背包，用或的理由和上面一样 } } if(!(sum&1)&&dp[sum>>1]) cout<<"Can be divided."<<endl<<endl;//如果这个得分是一个偶数，并且可以平均分成两份，就是可以 else cout<<"Can't be divided."<<endl<<endl;//否则就是不可以 } return 0; } //1 0 1 2 0 0 //1 0 0 0 1 1 //0 0 0 0 0 0