前言
最SB的一次&做的最差的一次
T1：
A
C
100
p
t
s
\color{green}AC 100pts
AC100pts
T2:
0
p
t
s
\color{red}0pts
0pts
T3:
0
p
t
s
\color{red}0pts
0pts
T4:
喜报!
//freopen("candy.in","r",stdin);
//freopen("candy.out","w",stdout);
100 p t s \color{green}100pts 100pts → \color{yellow}\rightarrow → 0 p t s \color{red}0pts 0pts
⇑
\Uparrow
⇑
\hspace{20em}
有史以来最大傻逼
T1 下棋（chess）
题面
时间限制：1秒 内存限制：256M
1.1 问题描述
Meowowco 最近沉迷下棋。
众所周知，棋盘上一局有 n n n 个玩家一起游戏。
我们的棋子称为”英雄”，英雄分为1、2、3星。
1 个 3 星英雄可以由 3 个 2 星英雄合成，1 个 2 星英雄可以由 3 个 1 星英雄合成。
现在给出每名玩家的英雄阵容，我们定义阵容强度为 18 x + 3 y + z 18x+3y+z 18x+3y+z，其中 x x x 为 3 星英雄个数， y y y 为两星英雄个数， z z z 为一星英雄个数，其中可以用低星英雄合成高星英雄后再计算阵容强度。
根据玩家的阵容强度，将玩家序号进行排序，并按阵容强度从大到小的顺序输出玩家的序号（若阵容强度相同，则把玩家序号（第 i i i个输入的玩家序号为 i i i）小的排在前面）。
1.2 输入格式
从文件chess.in中读取数据。
第一行输入一个整数 n n n ( 1 ≤ n ≤ 100000 1≤n≤100000 1≤n≤100000)，表示有 n n n名玩家参加游戏。
接下来n行，每行包含三个整数，代表玩家 i i i 的一星、二星、三星英雄的数量。
1.3 输出格式
输出到文件chess.out中。
将玩家序号进行排序，并按阵容强度顺序输出玩家的序号（若阵容强度相同，则按玩家序号排序）。
1.4 输入样例1
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 2
1.5 输出样例1
5 4 7 8 2 3 9 6 1
1.6 输入样例2
2
1 2 0
1 2 2
1.7 输出样例2
2 1
1.8 数据描述
保证所有数据点均满足 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105， 0 ≤ x , y , z ≤ 1 0 9 0≤x,y,z≤10^9 0≤x,y,z≤109
思路
暴力秒了
注意输入顺序是 x , y , z x,y,z x,y,z
AC Code：
#include<bits/stdc++.h>
using namespace std;
struct node
{
long long c;
int id;
}a[100005];
bool cmp(node x,node y)
{
if(x.c!=y.c)
{
return x.c>y.c;
}
return x.id<y.id;
}
int main()
{
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
long long x,y,z,t;
scanf("%lld%lld%lld",&z,&y,&x);
t=z/3;
y+=t;
z%=3;
t=y/3;
x+=t;
y%=3;
a[i].id=i;
a[i].c=18*x+3*y+z;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
printf("%d ",a[i].id);
}
return 0;
}
T2 汪洋（BigWater)
时间限制：1秒 内存限制：256M
题面
2.1 问题描述
Meowowco 连夜坐飞机去参加上海国家会展中心的 BilibiliWorld 2023，可是到现场时，已经是一片汪洋。。。
就算是这样，Meowowco 也不算白来一趟，因为场馆里还有许多可爱的 coser，她可以和这些 coser 一起合影，然后发说说羡慕她那可怜的队友。
场馆可以看成一张由 n × n n×n n×n个格子构成的矩阵。场馆内的格子可能被水淹没，Meowowco 趟水走过去可能会影响心情，因此这些格子上的值为 负数。但是另外的一些格子上站着可爱的 coser，如果 Meowowco 可以与那些 coser 合影，那么她就会变得开心，因此这些格子的值为 正数。
Meowowco 最开始的心情为 100 点，她在逛 BW 的过程中：
⋆ \star ⋆如果走到值为正数的格子，说明可以和可爱的 coser 拍照，因此会增加心情。
⋆ \star ⋆如果走到值为负数的格子，说明 Meowowco 需要趟水，因此心情值会下降。
Meowowco 从 ( 1 , 1 ) (1,1) (1,1) 点向右出发，即朝 ( 1 , 2 ) (1,2) (1,2) 点出发，她每次移动只能移动到 一个相邻的格子，并且她需要按照下面的路线逛一圈：
沿着上一步的方向继续移动
进行顺时针 90 度转向，(注意不可以在同一个格子内连续转向)
不再逛那些逛过的格子（除了起点）
其中转向指的是：如果上一步向右走，那么转向之后则为向下走；如果上一步向左走，那么转向之后则为向上走……
那么逛完 BW 之后，肯定是要从 ( 1 , 1 ) (1,1) (1,1) 点离开然后回家的，那么问题来了，Meowowco 离开时心情值最大是多少。
2.2 输入格式
从文件BigWater.in中读取数据。
第一行输入一个整数 n n n，表示地图的大小。
第二到 N + 1 N+1 N+1 行，每行包含 n n n 个整数 a i j a_{ij} aij，表示每个格子的值。
保证 ( 1 , 1 ) (1,1) (1,1) 点为 0 0 0。
2.3 输出格式
输出到文件BigWater.out中。
输出一个整数，表示 Meowowco 最大的心情值。
2.4 输入样例1
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 -5
2.5 输出样例1
129
2.6 输入样例2
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
2.7 输出样例2
142
2.8 数据描述
保证所有数据点均满足 1 ≤ n ≤ 1 0 3 1≤n≤10^3 1≤n≤103 1 ≤ ∣ a i ∣ ≤ 100 1\leq∣a_i∣ ≤100 1≤∣ai∣≤100。
思路
走出来的路径一定是正方形（要回到起点）
起点正好是
(
1
,
1
)
(1,1)
(1,1),用前缀和
AC Code
#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],r[1005][1005],c[1005][1005],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;
}
T3 删数（delnum）
题面
时间限制：1秒 内存限制：256M
3.1 问题描述
有一个集合，初始状态里面有数字 1 、 2 、 3 、 4 、 5 、 … … 、 11451 4 1919810 1、2、3、4、5、……、114514^{1919810} 1、2、3、4、5、……、1145141919810，你可以理解为很多正整数。
现在给你一个长度为 n n n 数组 a ( 1 ≤ a i ≤ 1 0 9 ) a(1≤ai≤10^9) a(1≤ai≤109)，每次操作将当前集合中第 a 1 a_1 a1小、第 a 2 a_2 a2小、……、第 a n a_n an小的数同时移除。
现在有 q q q 次询问，每次询问包含一个整数 x x x，查询从初始状态到删除 x x x 需要操作多少次。若无法删除，输出 0。
3.2 输入格式
从文件delnum.in中读取数据。
第一行包含两个正整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1≤n≤10^5) n(1≤n≤105)，表示数组大小。
接下来一行包含 n 个正整数 a 1 ， a 2 ， … … ， a n a_1，a_2，……，a_n a1，a2，……，an ，含义如题目描述所述。
接下来一行包含一个正整数 q q q，表示查询次数。
接下来 q q q 行，每行包含一个正整数 x x x。
数据保证
a
1
<
a
2
<
.
.
.
.
.
<
a
n
≤
1
0
9
a1<a2<.....<an≤10^9
a1<a2<.....<an≤109
3.3 输出格式
输出到文件delnum.out中。
对于每次询问，输出占一行，包含一个整数，表示删除 x x x 需要操作多少次。若无法删除，输出 0。
3.4 输入样例
5
1 2 3 4 5
1
100
3.5 输出样例
20
3.6 输入样例
5
1 3 9 14 20
5
114
514
1919
810
233
3.7 输出样例
27
107
388
159
45
3.8 数据描述
保证所有数据点均满足 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105， 1 ≤ a i ≤ 1 0 9 1≤ai ≤10^9 1≤ai≤109， 1 ≤ q ≤ 50 1≤q≤50 1≤q≤50, 1 ≤ x ≤ 1 0 9 1≤x≤10^9 1≤x≤109
AC Code
#include<bits/stdc++.h>
using namespace std;
int a[100005],n,q;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&q);
while(q--)
{
int x;
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");
}
}
}
T4 平分糖果（candy）
赛时注释 freopen 导致 100 p t s → 0 p t s \color{green}100pts\color{yellow}\rightarrow\color{red}0pts 100pts→0pts
正解多重背包
不正确但AC解：贪心
题面
4.1 问题描述
小可的妈妈给了小可很多的糖果，已经糖果都有美味程度，美味程度用1~6的整数表示。
有一天达达来小可家做客，小可要把糖果分给达达，现在已知了美味程度为 i 的糖果有 a[i] 个，请问小可能不能把糖果平分成美味程度之和相同的两部分。
4.2 输入格式
多组输入，每行输入6个数字，表示美味程度为 i 的糖果有 a[i] 个。
以输入一行6个0作为终止条件。
4.3 输出格式
对于每组输入，第一行输出为： Collection #k: ，k为第几组输入。
第二行输出为：如果可以平均分，则输出Can be divided.，否则输出Can’t be divided. 。
4.4 输入样例
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
4.5 输出样例
Collection #1:
Can't be divided.
Collection #2:
Can be divided.
4.6 数据描述
20%的数据：糖果总数不超过100
100%的数据：糖果总数不超过 20000
AC Code
AC且正确：
#include<bits/stdc++.h>
using namespace std;
const int N=1.2e5+5;
bool f[N];
int mark,a[10];
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;
}
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*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");
}
return 0;
}
AC不正确：
#include<bits/stdc++.h>
using namespace std;
int a[10];
bool check()
{
for(int i=1;i<=6;i++)
{
if(a[i]!=0)
{
return 1;
}
}
return 0;
}
int main()
{
//freopen("candy.in","r",stdin);
//freopen("candy.out","w",stdout);
int a1,a2,n=6,cnt=1;
while(1)
{
for(int i=1;i<=6;i++)
{
scanf("%d",&a[i]);
}
if(!check())
{
return 0;
}
a1=a2=0;
for(int i=6;i>=1;i--)
{
for(int j=1;j<=a[i];j++)
{
if(a1>a2)
{
a2+=i;
}
else
{
a1+=i;
}
}
}
printf("Collection #%d:\n",cnt);
if(a1!=a2)
{
printf("Can't be divided.\n\n");
}
else
{
printf("Can be divided.\n\n");
}
cnt++;
}
return 0;
}
