背景
2024-10-2上午打的比赛（CSP-J模拟2），作赛后总结报告。
下棋（\(chess\)）
赛时AC。
概述
高星 \(x\)
中星 \(y\)
低星 \(z\)
\(3\times z=y\)
\(3\times y=x\)
阵容强度：\(18 \times x + 3 \times y + z\)
求转换完后强度的顺序
思路
１.将能转的低星英雄转高星
２.结构体排序输出
我的代码
代码(点左边三角展开)
#include <string>
#include <cstring>
#include <string.h>
#include <iostream>
#include <algorithm>
#define fa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn = 1e5+999;
struct node {
long long sum;
int id;
} e[maxn];
int n;
bool cmp(node x,node y) {
if(x.sum != y.sum) return x.sum > y.sum;
return x.id < y.id;
}
signed main() {
// freopen("chess.in","r",stdin);
// freopen("chess.out","w",stdout);
cin >> n;
for(int i=1; i<=n; ++i) {
long long x,y,z;
cin >> x >> y >> z;
if(x >= 3) {
y+= x/3;
x%=3;
}
if(y >= 3) {
z += y/3;
y%=3;
}
e[i].id = i;
e[i].sum = z*18+y*3+x;
}
sort(e+1,e+n+1,cmp);
for(int i=1; i<=n; ++i)
cout << e[i].id << " ";
// fclose(stdin);
// fclose(stdout);
return 0;
}
汪洋（\(BigWater\)）
赛时0分(悲)
概述
从(1,1)出发，初始方向为右，每次可沿上一步方向，也可顺时针旋转90°一次,最后要回到(1,1)。
除(1,1)，其余点仅能到一次
每个点都有一个值，(1,1)一定是\(0\)
求从(1,1)离开时最大值。
思路(我的)
DFS
又 炸 了（玄学输出）
我的代码
Code(错)
#include <string>
#include <cstring>
#include <string.h>
#include <iostream>
#include <algorithm>
#define long long int
#define fa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn = 1001;
int zx[5] = {9,-1,0,1,0};
int zy[5] = {9,0,1,0,-1};
int g[maxn][maxn];
bool vis[maxn][maxn];
int n;
int ans = -111111111;
void dfs(int x,int y,int f,int sum) { //横纵坐标，方向(上1右2下3左4)，心情值
if(x == 1 && y == 1 && vis[1][1]) {
ans = max(ans,sum);
return ;
}
if(vis[x][y]) return ;
vis[x][y] = 1;
//沿上一步方向走
int x1 = x + zx[f];
int y1 = y + zy[f];
//旋转90°
int f2 = f+1;
if(f2 == 5) f2 = 1;
int x2 = x + zx[f2];
int y2 = y + zy[f2];
if(x1 >= 1 & x1 <= n && y1 >= 1 && y1 <= n) {
dfs(x1,y1,f,sum + g[x][y]);
}
if(x2 >= 1 & x2 <= n && y2 >= 1 && y2 <= n) {
dfs(x2,y2,f2,sum + g[x][y]);
}
return ;
}
signed main() {
// freopen("BigWater.in","r",stdin);
// freopen("BigWater.out","w",stdout);
fa;
cin >> n;
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
cin >> g[i][j];
dfs(1,1,2,100);
cout << ans << "\n";
// fclose(stdin);
// fclose(stdout);
return 0;
}
正解
因只能顺时针旋转，所以最后回去的路径一定是矩形
可用前缀和芝士解决
正解代码
Code(对)
#include <iostream>
using namespace std;
const int maxn = 1999;
int n;
int ans;
//行和列求前缀和
int h[maxn][maxn];
int l[maxn][maxn];
int a[maxn][maxn];
int main(){
cin >> n;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cin >> a[i][j];
h[i][j] = h[i][j-1] + a[i][j];
l[i][j] = l[i-1][j] + a[i][j];
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
//矩形一圈=上行+下行+左列+右列-四顶点
ans=max(ans,h[1][j] + h[i][j] + l[i][1] + l[i][j] - a[i][1] - a[1][j] - a[1][1] - a[i][j]);
}
}
cout << ans+100;//初始100
return 0;
}
删数（\(delnum\)）
赛时不会QuQ
赛后听懂了
概述
给定一个自然数上升集合
给定数组\(a\)，每次从集合中删去第\(a_1\)个，第\(a_2\)个……第\(a_n\)个。
再给出\(q\)个数
求这\(q\)个数第几次能被删除
若无法删除，输出0
正解思路
从最大的\(a_i\)找(倒序遍历)
每次\(ans\)+删除\(a_i\)次\(i\)个数字
输出！！！
代码
Code
#include <iostream>
using namespace std;
const int maxn = 1e5+111;
int n,q;
int a[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i=1; i<=n; ++i)
cin >> a[i];
cin >> q;
while(q--) {
int x,ans=0;
bool flag = 0;
cin >> x;
for(int i=n; i>=1; --i) {
if(a[i] <= x) {
//最大值为a[i]，从数据中减去多个a[i]的子集，形如x-_*i,ans存个数
ans += (x - a[i]) / i;
x = a[i] + (x - a[i]) % i;
if (x > a[i]) {//还是大就再减一次
++ans;
x -= i;
}
}
if(a[i] == x) {
cout << ans + 1 << "\n";
flag = 1;
break;
}
}
if(!flag)
cout << 0 << "\n";
}
return 0;
}
平分糖果（\(candy\)）
概述
有6种糖果，每次给出6种糖果的个数，以6个0结束输入
在每一次中，求能否将糖果分成两份，使价值相同(糖果价值为\(i\))
思路
特判
超级\(if\)判断喜得35分 ：）
有点骇人
#include <string>
#include <cstring>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int cnt;
int a[9];
int flag;
int sum;
signed main(){
// freopen("candy.in","r",stdin);
// freopen("candy.out","w",stdout);
while(1){
for(int i=1;i<=6;++i){
cin >> a[i];
if(a[i] == 0) ++flag;
}
if(flag == 6) break;
for(int i=1; i<=6; ++i) {
a[i] %= 2;
sum += (a[i] == 1);
}
if(cnt != 0) cout << "\n";
cout << "Collection #" << ++cnt << ":\n";
if(a[1] == 1 && a[2] == 1 && a[3] == 1 && a[4] == 0 && a[5] == 0 && a[6] == 0) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 0 && a[3] == 1 && a[4] == 1 && a[5] == 0 && a[6] == 0) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 0 && a[3] == 0 && a[4] == 1 && a[5] == 1 && a[6] == 0) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 0 && a[3] == 0 && a[4] == 0 && a[5] == 1 && a[6] == 1) cout << "Can be divided.";
else if(a[1] == 0 && a[2] == 1 && a[3] == 1 && a[4] == 0 && a[5] == 1 && a[6] == 0) cout << "Can be divided.";
else if(a[1] == 0 && a[2] == 1 && a[3] == 0 && a[4] == 1 && a[5] == 0 && a[6] == 1) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 1 && a[3] == 1 && a[4] == 0 && a[5] == 0 && a[6] == 1) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 0 && a[3] == 1 && a[4] == 1 && a[5] == 0 && a[6] == 1) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 1 && a[3] == 0 && a[4] == 1 && a[5] == 1 && a[6] == 0) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 1 && a[3] == 1 && a[4] == 1 && a[5] == 0 && a[6] == 0) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 1 && a[3] == 0 && a[4] == 0 && a[5] == 1 && a[6] == 1) cout << "Can be divided.";
else if(a[1] == 0 && a[2] == 1 && a[3] == 1 && a[4] == 1 && a[5] == 1 && a[6] == 0) cout << "Can be divided.";
else if(a[1] == 0 && a[2] == 1 && a[3] == 1 && a[4] == 0 && a[5] == 1 && a[6] == 1) cout << "Can be divided.";
else if(a[1] == 0 && a[2] == 0 && a[3] == 1 && a[4] == 1 && a[5] == 1 && a[6] == 1) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 1 && a[3] == 1 && a[4] == 1 && a[5] == 0 && a[6] == 1) cout << "Can be divided.";
else if(a[1] == 1 && a[2] == 1 && a[3] == 0 && a[4] == 1 && a[5] == 1 && a[6] == 1) cout << "Can be divided.";
else cout << "Can't be divided.";
cout << "\n";
flag = 0;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
正解
多重背包，判断是否有一些糖果价值之和为总价值一半
能就能平分，不能就无法。
超级无敌代码
#include <iostream>
#include <cstring>
#define long long int
using namespace std;
int cnt;
int a[9];
bool f[9][200909];
//多重背包
signed main() {
while(1) {
memset(f,0,sizeof(f));
f[0][0] = 1;
int sum = 0;
for(int i=1; i<=6; ++i) {
cin >> a[i];
sum += a[i] * i;//统计总数
}
if(sum == 0)//结束符
break;
cout << "Collection #" << ++cnt << ":\n";
if(sum % 2 == 1) {//若总数为奇数，一定无法平分
cout << "Can't be divided.\n\n";
continue;
}
for(int i=1; i<=6; ++i)//枚举每个物品
for(int k=0; k<=a[i]; ++k)//每种物品能拿0~a[i]个
for(int j=k*i; j<=sum/2+1; ++j)//价值 (k*i指该糖果全拿，sum/2指总价值一半)
f[i][j] |= f[i-1][j-k*i];//第i种物品凑j价值从自身和i-1种物品凑j-k*i价值转换来，有一个行就可行
if(f[6][sum/2] == 1)//如果6种糖果存在有几个糖果正好够一半就可行
cout << "Can be divided.\n\n";
else
cout << "Can't be divided.\n\n";
}
return 0;
}