验题报告 by idle_onlooker
T1sword
比较简单晦气的模拟。
注意点：
- 1.输出的 \(id\) 是初始编号而不是当前位置。
- 2.使用【寒川映月】时记得判断两边是否都有人。
- 3.如果受到伤害大于当前血量则输出为当前血量。
最后按照题意模拟即可。
\(code:\)
//为什么要攀登？因为山就在那里。
#include<bits/stdc++.h>
#define mrx 0x7f7f7f7f7f7f7f7f
#define int long long
using namespace std;
inline int read(){int num=0,flag=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}return num*flag;
}
inline void write(int num){if(num<0) putchar('-'),num=-num;if(num>9) write(num/10);putchar(num%10+'0');
}
inline void print(int num){write(num);putchar('\n');
}
inline void out(int num){write(num);putchar(' ');
}
inline int ksm(int a,int b,int mod){int ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;
}
int n,x,y;
struct per{int hea,id;
}a[110];
int now;
int flag;
void solve(){for(int i=1;i<=now;i++){if(a[i].hea<=0){now--;for(int j=i;j<=now;j++) a[j]=a[j+1];i=0;//进行下一次循环时i会自动++，所以从头开始要把i赋值成0。}}
}
void harm(int id,int x){if(a[id].hea>=x) cout<<"T="<<flag<<" id="<<a[id].id<<" d="<<x<<'\n';else cout<<"T="<<flag<<" id="<<a[id].id<<" d="<<a[id].hea<<'\n';a[id].hea-=x;
}
signed main(){now=n=read(),x=read(),y=read();for(int i=1;i<=n;i++) a[i].hea=read(),a[i].id=i;while(1){flag++;if(!now) break;if(flag%3==0){int k=(now+1)>>1;if(k!=1) harm(k-1,y);harm(k,y);if(k!=now) harm(k+1,y);}else harm(1,x);solve();}return 0;
}
/**/
注意代码不要写的太屎山，尽量写的逻辑清楚一些。
难度：
代码难度：\(CSP-J\;T2+eps\)
阅读难度：\(CSP-J\;T2+eps\)
思维难度：\(CSP-J\;T1.5\)
有点难了，但是问题不大。
*注：\(T1\) 题目改了 \(6\) 遍，std 还错了一次，我验题的时候差点崩溃了。
T2climb
直接枚举使用第二种方式的次数即可，时间复杂度\(O(\frac{w}{k})\)。
当然，你枚举第一种方式也是可以的。
\(code:\)
//为什么要攀登？因为山就在那里。
#include<bits/stdc++.h>
#define mrx 0x7f7f7f7f7f7f7f7f
#define int long long
using namespace std;
inline int read(){int num=0,flag=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}return num*flag;
}
inline void write(int num){if(num<0) putchar('-'),num=-num;if(num>9) write(num/10);putchar(num%10+'0');
}
inline void print(int num){write(num);putchar('\n');
}
inline void out(int num){write(num);putchar(' ');
}
inline int ksm(int a,int b,int mod){int ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;
}
int w,h,k,t;
int ans1=mrx,ans2;
signed main(){w=read(),h=read(),k=read(),t=read();for(int i=0;i*k<=w;i++){int num=max(0ll,h-t*i)+i*k;int tms=i*2+max(0ll,h-t*i);if(num>w) continue;if(tms<ans1){ans1=tms;ans2=w-num;}if(tms==ans1) ans2=min(ans2,w-num);}if(ans1==mrx) write(-1);else out(ans1),write(ans2);return 0;
}
/**/
值得一提的是，这道题搜索+卡时+大力剪枝能够获得\(98pts\)。
\(code:\)
//为什么要攀登？因为山就在那里。
#include<bits/stdc++.h>
#define mrx 0x7f7f7f7f7f7f7f7f
#define int long long
using namespace std;
inline int read(){int num=0,flag=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar_unlocked();}while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar_unlocked();}return num*flag;
}
inline void write(int num){if(num<0) putchar_unlocked('-'),num=-num;if(num>9) write(num/10);putchar_unlocked(num%10+'0');
}
inline void print(int num){write(num);putchar('\n');
}
inline void out(int num){write(num);putchar(' ');
}
inline int ksm(int a,int b,int mod){int ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;
}
int w,h,k,t;
int ans1=mrx,ans2;
int solve(int x){if(x<=0) return 0;return min({x,x/t*2+(x-x/t*t),((x-1)/t+1)*2});
}
int use_min(int x){if(x<=0) return 0;return min({x,x/t*k+(x-x/t*t),((x-1)/t+1)*k});
}
void dfs(int now,int num,int tim){if((double)clock()/CLOCKS_PER_SEC>0.08) return;//卡时，代码运行时间>0.08s直接退出搜索。if(num<0) return ;if(tim>ans1) return ;if(tim==ans1&&num>=ans2) return ;if(tim+solve(h-now)>ans1) return ;if(use_min(h-now)>num) return ;if(now>=h){if(tim<ans1){ans1=tim;ans2=num;}else if(tim==ans1) ans2=max(ans2,num);return ;}if(k<t){dfs(now+t,num-k,tim+2);dfs(now+1,num-1,tim+1);}else{dfs(now+1,num-1,tim+1);dfs(now+t,num-k,tim+2);}
}
signed main(){w=read(),h=read(),k=read(),t=read();//w:体力h:山的高度k:消耗体力t:爬升高度dfs(0,w,0);if(ans1==mrx) write(-1);else out(ans1),write(ans2);return 0;
}
/**/
原本此题的数据范围是现在的十分之一，时间也是现在的十倍，但是由于我太会剪枝，导致搜索能够直接\(AC\),出题人迫不得已做出了更改。
难度：
代码难度：\(CSP-J\;T1.5\)
阅读难度：\(CSP-J\;T1.5\)
思维难度：\(CSP-J\;T2\)
还算是比较友好的，感觉把这道题放\(T1\)会好一些。
T3decipher
考虑统计所有\(y\)对答案的贡献,对于下标为\(i\)的\(s_i=y\),他对答案的贡献为\(s_1\sim s_{i-1}\)中\(x\)的数量乘上\(s_{i+1}\sim s_{n}\)中\(z\)的数量，可以直接使用一个前缀和，一个后缀和预处理，这样就能\(O(n)\)算出一次修改的答案，此时如果代码写得好大概有\(45pts\)。