死亡回放模考过程
9:00~9:05写第一题，过了小样例
9:05~9:06发现过不了大样例
9:06~9:15调试过程中发现问题，修改后两个大样例都过了（能A吗？）
9:15~9:36烧烤T2没烧出来，做T3去了
9:36~10:00打T3暴力，但是错了
10:00~10:17打出了T2错误解，但不会正解qwq（骗分代码）
10:17~10:35修改T3暴力，成功过样例1和2（耶）
10:35~10:47写出了T3中n=1的情况
10:47~11.18写出了T4“暴力”
预计得分：(73,100)+(0,100)+(50,70)+(0,100)=(123,370)
实际得分：0+20+50+0=70
秒订：100+20+50+0=170
最终订正得分：100+100+100+62=362
死亡原因失分原因
1.T1子任务一特判打错了，痛失 100 分。（哭死）
2.T4没打真正的暴力。
题目正解
T1 序列
考场代码：
跟正解差不多，但不是最优解。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int tt[1000005];
priority_queue<int>no;
int n;
bool flag;
signed main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
cin>>n;
int mx = -1;
int mn = 1e6+100;
flag = 1;
int t = 0;
for(int i = 1;i<=n;i++){
int x;
cin>>x;
if(i==1)t=x;
if(x!=t)flag = 0;
tt[x]++;
mx = max(x,mx);
mn = min(x,mn);
}
if(mx==0){
cout<<0;
return 0;
}
if(flag){//子任务一，就是这里写错了导致0分
int ans = 0;
for(int i = 2;i<=n;i++){
if(mx<=i){
ans+=mx;
}else{
ans+=i;
}
}
cout<<ans<<'\n';
return 0;
}
for(int i = 1;i<=mx;i++){
if(tt[i]==0){
no.push(i);//空的数字
}
}
int ans = 0;
for(int i = mx;i>=mn;i--){//节省一点点时间
if(tt[i]>1){
//cout<<tt[i]<<" "<<i<<'\n';
if(no.size()){
for(int j = 2;j<=tt[i];j++){
while(no.size()&&no.top()>=i)no.pop();
if(no.empty()){
ans+=i*(tt[i]-j+1);
break;
}
int now = no.top();
no.pop();
ans+=i-now;
//cout<<ans<<'\n';
//cout<<i<<" "<<now<<'\n';
}
}else{
ans+=i*(tt[i]-1);//bian'cheng'0
//cout<<i*(tt[i]-1)<<" ";
}
//cout<<ans<<" ";
}
}
cout<<ans;
return 0;
}
正解
用桶存储数组，再计算空的部分，把多的地方填入空的部分，如果不能填，则变为0。
代码不放了。
T2 密钥
考场代码
变为全0串，再变成全1串（居然得了20分）
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct www{
int c;
char a,b;
};
www x[5005];
int n;
bool cmp(www x,www y){
if(x.a=='1'&&y.a=='1'){
return x.c>y.c;
}
return x.a>y.a;
}
bool cmp2(www x,www y){
if(x.b=='1'&&y.b=='1'){
return x.c<y.c;
}
return x.b>y.b;
}
signed main(){
freopen("key.in","r",stdin);
freopen("key.out","w",stdout);
cin>>n;
for(int i = 1;i<=n;i++){cin>>x[i].c;}
int sum = 0;
for(int i = 1;i<=n;i++){
cin>>x[i].a;
if(x[i].a=='1'){
sum+=x[i].c;
}
}
for(int i = 1;i<=n;i++){cin>>x[i].b;}
sort(x+1,x+n+1,cmp);
int ans = 0;
for(int i = 1;i<=n;i++){
if(x[i].a=='1'){
sum-=x[i].c;
ans+=sum;
}
}
sort(x+1,x+n+1,cmp2);
for(int i = 1;i<=n;i++){
if(x[i].b=='1'){
sum+=x[i].c;
ans+=sum;
}
}
cout<<ans;
return 0;
}
正解
使用multiset（不去重的set）维护1变0，0变1，1变1的情况。
如果没有1变1的情况，只需计算1变0，0变1要的花费。
如果有1变1的情况，那么就要考虑是否要1变0再变1。
核心代码：
//sum表示所有a[i]='1'的c[i]总和。
//a1表示1变0的情况。
//a2表示0变1的情况。
//a3表示1变1的情况。
for(auto it:a1){
sum-=it;
ans+=sum;
}
for(auto it:a2){
sum+=it;
ans+=sum;
}
for(auto it:a3){
a1.insert(it);
a2.insert(it);
int tt = 0;
sum = te;
for(auto ti:a1){
sum-=ti;
tt+=sum;
}
for(auto ti:a2){
sum+=ti;
tt+=sum;
}
ans=min(tt,ans);
}
T3 管道
考场代码
特判了 n,m<=3 与 n=1 的情况。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[105][105];
int vis[105][105];
int dp[5][105];
//1:右下
//2:左下
//3:右上
//4:左上
int ans = 0;
void dfs1(int x,int y){
//cout<<x<<" "<<y<<'\n';
if(x>n){
int sum = 0;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
//cout<<vis[i][j]<<" ";
if(vis[i][j]==1){
if(j<m&&(vis[i][j+1]==2||vis[i][j+1]==4)){
sum+=max(0ll,a[i][j]+a[i][j+1]);
}
if(i<n&&(vis[i+1][j]==3||vis[i+1][j]==4)){
sum+=max(0ll,a[i][j]+a[i+1][j]);
}
}
if(vis[i][j]==2){
if(j>1&&(vis[i][j-1]==1||vis[i][j-1]==3)){
sum+=max(0ll,a[i][j]+a[i][j-1]);
}
if(i<n&&(vis[i+1][j]==3||vis[i+1][j]==4)){
sum+=max(0ll,a[i][j]+a[i+1][j]);
}
}
if(vis[i][j]==3){
if(j<m&&(vis[i][j+1]==2||vis[i][j+1]==4)){
sum+=max(0ll,a[i][j]+a[i][j+1]);
}
if(i>1&&(vis[i-1][j]==1||vis[i-1][j]==2)){
sum+=max(0ll,a[i][j]+a[i-1][j]);
}
}
if(vis[i][j]==4){
if(j>1&&(vis[i][j-1]==1||vis[i][j-1]==3)){
sum+=max(0ll,a[i][j]+a[i][j-1]);
}
if(i>1&&(vis[i-1][j]==1||vis[i-1][j]==2)){
sum+=max(0ll,a[i][j]+a[i-1][j]);
}
}
}
//cout<<'\n';
}
/*if(vis[1][1]==1&&vis[1][2]==2&&vis[1][3]==4&&vis[2][1]==1&&vis[2][2]==4&&vis[2][3]==4&&vis[2][1]==3&&vis[2][2]==3&&vis[2][3]==2){
cout<<sum<<" ";
}*/
//cout<<sum<<" ";
ans = max(sum/2,ans);
return ;
}
for(int i = 1;i<=4;i++){
vis[x][y]=i;
if(y==m){
dfs1(x+1,1);
}else{
dfs1(x,y+1);
}
}
}
signed main(){
freopen("tunnel.in","r",stdin);
freopen("tunnel.out","w",stdout);
cin>>n>>m;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>a[i][j];
}
}
if(n==1){
//1:朝左
//2:朝右
for(int i = 1;i<=m;i++){
if(i==1){
dp[1][i]=0;
}else dp[1][i]=dp[2][i-1]+a[1][i]+a[1][i-1];
dp[2][i]=max(dp[2][i-1],dp[1][i-1]);
//cout<<dp[1][i]<<" "<<dp[2][i]<<'\n';
}
cout<<max(dp[1][m],dp[2][m]);
}
if(n<=3&&m<=3){
dfs1(1,1);
cout<<ans;
}
if(n==2){
dfs1(1,1);
cout<<ans;
}
return 0;
}
正解
对于 n,m<=3 的情况，直接暴力枚举每个水管的状态即可。
对于 n=1 的情况，简单dp即可。
对于其他情况：
可以发现，每一行和每一列动态规划的结果都不会有关联（无后效性）
于是，dp每一行与每一列即可。
dp代码：
for(int j = 1;j<=n;j++){
for(int i = 2;i<=m;i++){
dp[j][i]=max(dp[j][i-1],dp[j][i-2]+max(a[j][i]+a[j][i-1],0ll));
}
ans+=dp[j][m];
}
for(int j = 1;j<=m;j++){
for(int i = 2;i<=n;i++){
dp1[j][i]=max(dp1[j][i-1],dp1[j][i-2]+max(a[i][j]+a[i-1][j],0ll));
}
ans+=dp1[j][n];
//cout<<j<<":"<<dp1[j][n]<<endl;
}
T4 生存
还没AC。