前言
端午和中考假连在一起了，放六天假，好耶！ヽ(✿ﾟ▽ﾟ)ノ
个人认为难度：
T1（难在读题）<T4（代码较长，思路简单）<T2（有一定的思维量，较为经典的要排序的 01 背包问题）<T5（广搜）<T3（难在读题 + 坑点较多的模拟）<T6（线性 DP）<T7（紫题劝退）
$AC\ \ on\ \ 2021.06.11$
这题是来考语文的吗？
题目老长，愣是看了半天才看懂。
读懂题后：这不就是给一串数处理之后加在一起咩？？
处理也很简单 （事实证明这道题最难的地方在读题），直接看灯是什么颜色：如果是绿的就变为 $0$，如果是红的就不变，如果是黄的就加上 $r$。
结果打完之后代码 CE 了后来我才发现 time 是 c++ 的关键词，无语……
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<bits/stdc++.h>
using namespace std;
int n,a,b,r,y,g,Time;
int main(){
scanf("%d %d %d %d",&r,&y,&g,&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&a,&b);
if(!a||a==1) Time+=b;
else if(a==2) Time+=b+r;
}
printf("%d",Time);
return 0;
}
|
$AC\ \ on\ \ 2021.06.13$
吃石头可海星。
背包，考点是怎么排序。
假设要吃两个石头 $x$ 和 $y$，先吃 $x$ 比先吃 $y$ 好。
设 $first$ 为石头的初始能量值，$lost$ 为每秒石头会浪费的能量值，$time$ 为吃一块石头要用的时间。
为了方便我们不考虑石头能量值流完的情况。
那么先吃 $x$ 的表达式为：
先吃 $y$ 的表达式为：
我们知道 $energy1>energy2$
代入原式：
把相同的地方抵消了就变成：
把负号搞掉：
嗯，式子出来了，排序后再用一个 01 背包就可以了。
注意两点：
- 背包 dp 初始化是 $128$（因为这代表的是时间点要算还剩多少能量值），只有 $dp_0$ 初始化为 $0$；
- 开
long long。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,ans,dp[10005];
struct rock{int t,lost,first;}a[105];
bool cmp(rock x,rock y){return x.t*y.lost<y.t*x.lost;}
signed main(){
scanf("%d",&T);
for(int r=1;r<=T;r++){
ans=0;
memset(dp,128,sizeof(dp));
dp[0]=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].t,&a[i].first,&a[i].lost);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
for(int j=10000;j>=a[i].t;j--){
dp[j]=max(dp[j],dp[j-a[i].t]+a[i].first-(j-a[i].t)*a[i].lost);
}
}
for(int i=0;i<=10000;i++) ans=max(ans,dp[i]);
printf("Case #%lld: %lld\n",r,ans);
}
return 0;
}
|
$AC\ \ on\ \ 2021.06.13$
就大模拟，没啥好说的，代码调了一个下午。
一定要注意几点（踩过的坑）：
- 读题。（数字里不能有 $0$，也不能有相同数字）；
- 循环里要先
n++；
- 注意反转数串；
- 每个数都只能走一遍。
橙题调这么久我还有救吗 qwq
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
bool check(ll i){
int a[15]={},c[15]={};
int weishu=0;
while(i){
c[++weishu]=(int)i%(ll)10;
i/=(ll)10;
}
for(int i=1;i<=weishu;i++) a[i]=c[weishu-i+1];
for(int i=1;i<=weishu;i++)
for(int j=1;j<i;j++)
if(a[i]==a[j]) return false;
for(int i=1;i<=weishu;i++) if(!a[i]) return false;
int x=1;
bool b[15]={};
for(int i=1;i<=weishu;i++){
int t=a[x];
while(t--){
x++;
if(x==weishu+1) x=1;
}
if(b[x]&&x!=1) return false;
b[x]=1;
if(x==1){
bool flag=1;
for(int i=1;i<=weishu;i++) flag&=b[i];
if(flag) return true;
else return false;
}
}
return false;
}
int main(){
scanf("%lld",&n);
while(1){
n++;
if(check(n)){
printf("%lld",n);
return 0;
}
}
return 0;
}
|
$AC\ \ on\ \ 2021.06.13$
嗯，看来 mjl 是爱上大模拟了（逃。
直接模拟，每一步根据横，竖，左上右下斜，右上左下斜四个方向判断赢了没有。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include<bits/stdc++.h>
using namespace std;
int n,x,y,a[20][20];
char zt='A';
int main(){
scanf("%d",&n);
for(int t=1;t<=n;t++){
scanf("%d %d",&x,&y);
if(t&1) zt='A',a[x][y]=1;
else zt='B',a[x][y]=2;
for(int i=1;i<=15;i++){
for(int j=1;j<=15;j++){
if(i>=5){
if(a[i][j]==1&&a[i-1][j]==1&&a[i-2][j]==1&&a[i-3][j]==1&&a[i-4][j]==1){
printf("A %d",t);
return 0;
}
if(a[i][j]==2&&a[i-1][j]==2&&a[i-2][j]==2&&a[i-3][j]==2&&a[i-4][j]==2){
printf("B %d",t);
return 0;
}
}
if(i<=11){
if(a[i][j]==1&&a[i+1][j]==1&&a[i+2][j]==1&&a[i+3][j]==1&&a[i+4][j]==1){
printf("A %d",t);
return 0;
}
if(a[i][j]==2&&a[i+1][j]==2&&a[i+2][j]==2&&a[i+3][j]==2&&a[i+4][j]==2){
printf("B %d",t);
return 0;
}
}
if(j>=5){
if(a[i][j]==1&&a[i][j-1]==1&&a[i][j-2]==1&&a[i][j-3]==1&&a[i][j-4]==1){
printf("A %d",t);
return 0;
}
if(a[i][j]==2&&a[i][j-1]==2&&a[i][j-2]==2&&a[i][j-3]==2&&a[i][j-4]==2){
printf("B %d",t);
return 0;
}
}
if(j<=11){
if(a[i][j]==1&&a[i][j+1]==1&&a[i][j+2]==1&&a[i][j+3]==1&&a[i][j+4]==1){
printf("A %d",t);
return 0;
}
if(a[i][j]==2&&a[i][j+1]==2&&a[i][j+2]==2&&a[i][j+3]==2&&a[i][j+4]==2){
printf("B %d",t);
return 0;
}
}
if(i>=5&&j>=5){
if(a[i][j]==1&&a[i-1][j-1]==1&&a[i-2][j-2]==1&&a[i-3][j-3]==1&&a[i-4][j-4]==1){
printf("A %d",t);
return 0;
}
if(a[i][j]==2&&a[i-1][j-1]==2&&a[i-2][j-2]==2&&a[i-3][j-3]==2&&a[i-4][j-4]==2){
printf("B %d",t);
return 0;
}
}
if(i<=11&&j<=11){
if(a[i][j]==1&&a[i+1][j+1]==1&&a[i+2][j+2]==1&&a[i+3][j+3]==1&&a[i+4][j+4]==1){
printf("A %d",t);
return 0;
}
if(a[i][j]==2&&a[i+1][j+1]==2&&a[i+2][j+2]==2&&a[i+3][j+3]==2&&a[i+4][j+4]==2){
printf("B %d",t);
return 0;
}
}
if(j>=5&&i<=11){
if(a[i][j]==1&&a[i+1][j-1]==1&&a[i+2][j-2]==1&&a[i+3][j-3]==1&&a[i+4][j-4]==1){
printf("A %d",t);
return 0;
}
if(a[i][j]==2&&a[i+1][j-1]==2&&a[i+2][j-2]==2&&a[i+3][j-3]==2&&a[i+4][j-4]==2){
printf("B %d",t);
return 0;
}
}
if(i>=5&&j<=11){
if(a[i][j]==1&&a[i-1][j+1]==1&&a[i-2][j+2]==1&&a[i-3][j+3]==1&&a[i-4][j+4]==1){
printf("A %d",t);
return 0;
}
if(a[i][j]==2&&a[i-1][j+1]==2&&a[i-2][j+2]==2&&a[i-3][j+3]==2&&a[i-4][j+4]==2){
printf("B %d",t);
return 0;
}
}
}
}
}
printf("Tie");
return 0;
}
|
据说有个小五打了 5.6K，好可怕
$AC\ \ on\ \ 2021.06.14$
广搜（数据范围很水），不过要注意，在算这个点能不能走到终点的时候，必须老老实实地从这个点出发走到终点，不能从终点倒回来枚举 （别问我怎么知道的）。
不会 T 掉，数据范围是真的水。
这里我打了两个差不多的 bfs 函数，只不过一个没有返回值一个是 bool 型的。其实这里可以用数组实现，一个 bfs 函数就够了，但是我懒得打，反正能 A。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include<bits/stdc++.h>
using namespace std;
char a[55][55];
int m,n,sx,sy,tx,ty;
bool b[55][55],c[55][55];
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
struct node{int x,y;}t1,t2;
void bfs(int x,int y){
queue<node> q;
t1.x=x,t1.y=y;
q.push(t1);
while(!q.empty()){
t1=q.front();
q.pop();
int dx,dy;
int start,end;
if(a[t1.x][t1.y]=='.'&&a[t1.x+1][t1.y]=='#') continue;
if(a[t1.x][t1.y]=='+'||a[t1.x][t1.y]=='S'||a[t1.x][t1.y]=='T') start=0,end=4;
else if(a[t1.x][t1.y]=='-') start=0,end=2;
else if(a[t1.x][t1.y]=='|') start=2,end=4;
else if(a[t1.x][t1.y]=='.') start=3,end=4;
else continue;
for(int i=start;i<end;i++){
dx=t1.x+dir[i][0];
dy=t1.y+dir[i][1];
if(dx>=1&&dx<=m&&dy>=1&&dy<=n&&a[dx][dy]!='#'){
if(b[dx][dy]) continue;
b[dx][dy]=1;
t2.x=dx,t2.y=dy;
q.push(t2);
}
}
}
return;
}
bool bfs2(int x,int y){
memset(c,0,sizeof(c));
queue<node> q;
t1.x=x,t1.y=y;
q.push(t1);
while(!q.empty()){
t1=q.front();
q.pop();
if(t1.x==tx&&t1.y==ty) return true;
int dx,dy;
int start,end;
if(a[t1.x][t1.y]=='.'&&a[t1.x+1][t1.y]=='#') continue;
if(a[t1.x][t1.y]=='+'||a[t1.x][t1.y]=='S'||a[t1.x][t1.y]=='T') start=0,end=4;
else if(a[t1.x][t1.y]=='-') start=0,end=2;
else if(a[t1.x][t1.y]=='|') start=2,end=4;
else if(a[t1.x][t1.y]=='.') start=3,end=4;
else continue;
for(int i=start;i<end;i++){
dx=t1.x+dir[i][0];
dy=t1.y+dir[i][1];
if(dx>=1&&dx<=m&&dy>=1&&dy<=n&&a[dx][dy]!='#'){
if(c[dx][dy]) continue;
c[dx][dy]=1;
t2.x=dx,t2.y=dy;
q.push(t2);
}
}
}
return false;
}
int main(){
scanf("%d %d",&m,&n);
for(int i=1;i<=m;i++){
scanf("\n");
for(int j=1;j<=n;j++){
scanf("%c",&a[i][j]);
if(a[i][j]=='S') sx=i,sy=j;
else if(a[i][j]=='T') tx=i,ty=j;
}
}
bfs(sx,sy);
if(!b[tx][ty]){
printf("I'm stuck!");
return 0;
}
int sum=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(!bfs2(i,j)&&b[i][j]) sum++;
}
}
printf("%d",sum);
return 0;
}
|
$AC\ \ on\ \ 2021.06.15$（只可惜比赛已经结束了 qwq）
30 分一定是万恶的全排列了 qwq
不！我们不能思想只停留在部分分！
好吧这题是道 DP。
思路和大家的差不多，不讲！
话说我竟然不看 TJ 想到了这个思路就很那啥。
最关键的是我竟然没想到区间求和的优化就很那啥。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<bits/stdc++.h>
using namespace std;
int n,m,sum,dp[1005][1005];
const int p=10000;
int main(){
scanf("%d %d",&n,&m);
dp[1][0]=1;
for(int i=2;i<=n;i++){
sum=0;
for(int j=0;j<=m;j++){
sum=(sum+dp[i-1][j])%p;
dp[i][j]=sum;
if(j+1>=i) sum=(sum-dp[i-1][j-i+1]+p)%p;
}
}
printf("%d",dp[n][m]);
return 0;
}
|
易证：mjl 爱上了大模拟之后一定又爱上了 HAOI……
紫题搞毛线啊。
溜了溜了。
The end.
