CSP-J模拟赛(2)补题报告

前言：

           1.下棋（chess）：70

           2.汪洋（BigWater）：0

           3,删数（delnum）：0

           4.平分糖果（candy）：0

总结一下：昨天的flag立住了(甚至还多了20分），下次继续努力，A掉一题！

下棋

题意：

棋盘上一局有 个玩家一起游戏。
我们的棋子称为"英雄"，英雄分为 1、2 、 3星。 1个2 星英雄可以由 3个 2星英雄合成， 1个 1星英雄可以由 3个 2星英雄合成。
现在给出每名玩家的英雄阵容，我们定义阵容强度为 18x+3y+z，( x为 1星英雄个数， y为2星英雄个数， z为3星英雄个数)其中可以用低星英雄合成高星英雄后再计算阵容强度。
根据玩家的阵容强度，将玩家序号进行排序，并按阵容强度从大到小的顺序输出玩家的序号（若阵容强度相同，则把玩家序号（第 个输入的玩家序号为 ）小的排在前面）。

考试回顾：

想到了正解，但计算的时候少了些优化，数组结构体也没开longlong（不然我就AC啦！）。今天学一下计算时间和空间复杂度。

题解：

带式子进去硬算，将3星，2星英雄尽可能转成1星英雄，再手动cmp一下。（注意输入的顺序是z,y,x不是x,y,z）

AC: 

 #include<iostream>
#include<iomanip>
#include<cmath> 
#include<string>
#include<algorithm> 
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
using namespace std;
struct node{long long x,y,z;
}a[110000];
struct d{long long qd,xh;
}b[110000];
int cmp(d a,d b){if(a.qd<b.qd){return 0;}else if(a.qd==b.qd&&a.xh>b.xh){return 0;}else return 1;
}int main(){//freopen("chess.in","r",stdin);//freopen("chess.out","w",stdout);long long n;scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&a[i].z,&a[i].y,&a[i].x);a[i].y+=a[i].z/3;a[i].z%=3;a[i].x+=a[i].y/3;a[i].y%=3;}for(int i=1;i<=n;i++){b[i].qd=a[i].x*18 + 3*a[i].y+a[i].z;b[i].xh=i;}sort(b+1,b+1+n,cmp);for(int i=1;i<=n;i++){printf("%lld ",b[i].xh);}return 0;
}

汪洋

题意：

      场馆可以看成一张由 个格子构成的矩阵。场馆内的格子可能被水淹没，Meowowco 趟水走过去可能会影响心情，因此这些格子上的值为 负数。但是另外的一些格子上站着可爱的 coser，如果Meowowco 可以与那些 coser 合影，那么她就会变得开心，因此这些格子的值为 正数。
Meowowco 最开始的心情为10021 点，她在逛 BW 的过程中：
1.如果走到值为正数的格子，说明可以和可爱的 coser 拍照，因此会增加心情。如果走到值为负数的格子，说明 Meowowco 需要趟水，因此心情值会下降。
2.Meowowco 从 （1，1）点向右出发她每次移动只能移动到 一个相邻的格子，并且她需要按照下面的路线逛一圈：
（1）沿着上一步的方向继续移动
（2）进行顺时针 度转向 (注意不可以在同一个格子内连续转向)
（3）不再逛那些逛过的格子（除了起点）

那么逛完 BW 之后，肯定是要从（1，1） 点离开然后回家的，那么问题来了，Meowowco 离开时心情值最大是多少。

考试回顾：

用的dfs暴搜，但是不知道为什么一分没得。正解是前缀和O(n^2)的解法，暴搜不过也在情理之中，（思维还是不够灵活呀）

题解：

二维前缀和，累加矩阵四周的和（因为要回到起点，所以必须绕矩阵内一圈）。

AC: 

#include<iostream>
#include<iomanip>
#include<cmath> 
#include<string>
#include<algorithm> 
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
using namespace std;
const int N=1005;
int n,a[N][N],r[N][N],c[N][N];
int main(){//freopen("BigWater.in","r",stdin);//freopen("BigWater.out","w",stdout);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;
}

删数

题意：

有一个集合，初始状态里面有数字 11、22、33、44、55、…… ，正无穷。你可以理解为很多正整数。现在给你一个长度为 n 数组 a(1≤ai≤109)，每次操作将当前集合中第 a1小、第 a2 小、……、第 an小的数同时移除。有q次询问，每次询问包含一个整数 x，查询从初始状态到删除 x需要操作多少次。若无法删除，输出 0。

考试回顾：

真不会了，本来想骗分来着，一看多组输入心凉了。写了输入输出就没再管它。

题解：

如果x比数组最大的元素还大，用x减去n，（减到比最大的数小就继续减去在它前面的数组里的数，一直减到0或和数组中的某个元素相等为止），再累加它们的和，最后输出。

AC: 

#include<iostream>
#include<iomanip>
#include<cmath> 
#include<string>
#include<algorithm> 
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
using namespace std;
int n,q,x,a[110000];
int main(){//freopen("BigWater.in","r",stdin);//freopen("BigWater.out","w",stdout);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}cin>>q;while(q--){cin>>x;int ans=0,flag;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) cout<<ans<<"\n";else cout<<"0"<<"\n";}return 0;
}

平分糖果

题意：

   小可的妈妈给了小可很多的糖果，已经糖果都有美味程度，美味程度用1~6的整数表示。

   有一天达达来小可家做客，小可要把糖果分给达达，现在已知了美味程度为 i 的糖果有 a[i] 个，请问小可能不能把糖果平分成美味程度之和相同的两部分。

   多组输入，每行输入6个数字，表示美味程度为 i 的糖果有 a[i] 个。以输入一行6个0作为终止条件。对于每组输入，第一行输出为： Collection #k: ，k为第几组输入。第二行输出为：如果可以平均分，则输出Can be divided.，否则输出Can't be divided. 。

考试回顾：

当时看到题，天都塌了！完全没学过，只能骗分了（最后还没骗到~）

题解：

多重背包的二进制优化，采用位运算。（我还没听懂呢）

AC: 

#include<iostream>
#include<iomanip>
#include<cmath> 
#include<string>
#include<algorithm> 
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
using namespace std;
const int N=1.2e5+5;
int mark,a[10];
bool f[N];
int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);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;else{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*a[i]];}}}if(!(m&1)&&f[m>>1])  printf("Can be divided.\n");else  printf("Can't be divided.\n");printf("\n");}return 0;
}