CF 981 Review
打的最差的一场 Div.3
虽然可能有Div.3是ICPC赛制的原因，但是本质上还是自己太菜了。
A
模拟
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
int n,m,T;
int main()
{
re(T);
while(T--)
{
re(n);
int pos=0,upd=-1;
while(1)
{
pos+=upd;
if(pos<-n||pos>n)
{
puts(upd<0?"Sakurako":"Kosuke");
break;
}
if(upd<0)upd=-upd+2;
else upd=-upd-2;
}
}
return 0;
}
B
稍微难写一点的模拟
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
int n,m,T;
const int N=1000;
int mp[N][N];
inline int expand(int x,int y)
{
int ans=0;
for(;1<=x&&x<=n&&1<=y&&y<=n;x++,y++)
if(mp[x][y]<0)ans=min(ans,mp[x][y]);
return -ans;
}
int main()
{
re(T);
while(T--)
{
re(n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
re(mp[i][j]);
long long ans=0;
for(int st=1;st<=n;++st)
ans+=expand(st,1);
for(int st=2;st<=n;++st)
ans+=expand(1,st);
wr(ans),putchar('\n');
}
return 0;
}
C
分析
据锚具所说应该是可以直接构造，但是我还是没有想出来，不过对于我来，即使DP的水平确实很低，但是这个DP还是很显然的吧。
拆成两半分开进行DP，把“是否交换”塞进状态里，然后最后合起来的时候统计一下合并的代价就好了。
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
int n,m,T;
const int N=2e5+10,INF=2005120700;
int a[N];
int check(int x,int y)
{
return x==y;
}
int main()
{
re(T);
while(T--)
{
re(n);
for(int i=1;i<=n;++i)re(a[i]);
vector<vector<int>>dp(n+1,vector<int>(3,INF));
dp[0][0]=dp[0][1]=0;
a[0]=a[n+1]=0;
for(int i=1;i<=n/2;++i)
{
dp[i][0]=min(dp[i-1][0]+check(a[i],a[i-1])+check(a[n-i+1],a[n-i+2]),dp[i][0]);
dp[i][0]=min(dp[i-1][1]+check(a[i],a[n-i+2])+check(a[n-i+1],a[i-1]),dp[i][0]);
dp[i][1]=min(dp[i-1][0]+check(a[n-i+1],a[i-1])+check(a[i],a[n-i+2]),dp[i][1]);
dp[i][1]=min(dp[i-1][1]+check(a[n-i+1],a[n-i+2])+check(a[i],a[i-1]),dp[i][1]);
}
if(n&1)
wr(min(dp[n/2][0],dp[n/2][1])+check(a[n+1>>1],a[n/2])+check(a[n/2+2],a[n+1>>1]));
else
wr(min(dp[n/2][0],dp[n/2][1])+check(a[n/2],a[n/2+1]));
putchar('\n');
}
return 0;
}
D
最烦的一集，赛时四十分钟写完前三题，五十分钟想到D的DP做法，以为要上大分了，结果发现好像死活调不出来优化以后的做法，最后发现从暴力DP到优化后的DP需要多加一步初始化，实在是逆天，一直到最后两三分钟才改出来。
分析
也可以定义 \(dp[i][0/1]\) 为，考虑完前 \(i\) 个数 ，第 \(i\) 个是否作为右端点的最大合法段数，然后就很好 DP 了。
暴力做法是 \(O(N^2)\) 的，当然只需要开一个 map 来记录最大值就可以做到 \(O(n\log n)\) ，然而由于我实在是太喜欢 unordered_map 了，所以没写普通的 map ，导致赛后被卡了 umap ，hack 掉了 D 题，我真的会谢。
AC Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
int n,m,T;
const int N=2e5+10;
int s[N];
map<int,int>maxdp,vis;
int main()
{
re(T);
while(T--)
{
re(n);maxdp.clear(),vis.clear();
for(register int i=1;i<=n;++i)re(s[i]),s[i]+=s[i-1];
vector<vector<int>> dp(n+1,vector<int>(3,0));
dp[0][0]=dp[0][1]=0,vis[0]=1;
int ans=-1;
for(register int i=1;i<=n;++i)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
if(vis[s[i]])dp[i][1]=maxdp[s[i]]+1;
maxdp[s[i]]=max(maxdp[s[i]],max(dp[i][1],dp[i][0]));
ans=max(ans,max(dp[i][1],dp[i][0]));
vis[s[i]]=1;
}
wr(ans),putchar('\n');
}
return 0;
}
E
还是挺考验思维的一道题，大概想一想的话，应该半个小时左右能做出来，但是这题放的位置似乎有点过于逆天了，通过数和 C 题差不多。
顺便吐槽一句，为什么 D 过的人比 C 多了这么多？
分析
可以很显然地想到，如果一个点，或者是一个点对已经符合条件了，那么我肯定不会去操作它/它们了。
那么又怎样通过最小的代价把剩下的进行操作呢？
可以想到通过“成对”的方式来构造，代价是最小的，而且也没有最小的代价了。（因为交换本就是基于“成对”而存在）
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
int n,m,T;
const int N=1e6+10;
int p[N],id[N];
int main()
{
re(T);
while(T--)
{
re(n);
for(register int i=1;i<=n;++i)
re(p[i]),id[p[i]]=i;
int ans=0,p1,p2;
for(register int i=1;i<=n;++i)
{
if(p[i]==i||p[i]==id[i])continue;
ans++;
p1=i,p2=id[id[i]];
id[p[p1]]=p2,id[p[p2]]=p1;
swap(p[p1],p[p2]);
}
wr(ans),putchar('\n');
}
return 0;
}
总结
复杂度正确的时候，能直接用 map 就直接用 map，不要什么时候都写 umap，在数据极限的情况下单次操作可以被卡成 \(o(n)\)
标签：10,int,Review,981,CF,re,while,wr,void From： https://www.cnblogs.com/Hanggoash/p/18502279