Codeforces Round #688 (Div. 2) CF1453A-F 题解

57 阅读 0 评论 38 点赞

我是靠谱客的博主灵巧发夹，最近开发中收集的这篇文章主要介绍Codeforces Round #688 (Div. 2) CF1453A-F 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A.
答案就是在行和列中同时出现的数的个数。

代码：

#include <iostream>
#include <cstdio>
const int maxn=107;
using namespace std;
int n,m,T,x,ans;
int a[maxn];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=100;i++) a[i]=0;
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
a[x]++;
}
ans=0;
for (int i=1;i<=m;i++)
{
scanf("%d",&x);
if (a[x]) ans++;
}
printf("%dn",ans);
}
}

B.
考虑差分，那么每一步就是把差分后的数组的一位 $+ 1$ 或者 $- 1$ 。
所以不修改的答案就是 $sum_{i=2}^{n}abs(a[i]-a[i-1])$ 。
考虑修改，如果改的是第一位，减少的步数为 $a b s (a [2] - a [1])$ ；
如果改的是第 $n$ 位，减少的步数为 $a b s (a [n] - a [n - 1])$ ；
否则减少的步数为 $a b s (a [i] - a [i - 1]) + a b s (a [i] - a [i + 1]) - a b s (a [i + 1] - a [i - 1])$ 。取最小即可。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#define LL long long
const int maxn=2e5+7;
using namespace std;
int T,n;
LL sum,maxx;
LL a[maxn];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
LL sum=0,maxx=0;
for (int i=2;i<=n;i++) sum+=abs(a[i]-a[i-1]);
maxx=abs(a[2]-a[1]);
for (int i=2;i<n;i++)
{
LL x=abs(a[i]-a[i-1])+abs(a[i+1]-a[i])-abs(a[i+1]-a[i-1]);
maxx=max(maxx,x);
}
LL x=abs(a[n]-a[n-1]);
maxx=max(maxx,x);
printf("%lldn",sum-maxx);
}
}

C.
考虑 $x_1,y_1)$ ， $x_2,y_2)$ 的最大三角形面积的 $2$ 倍。
考虑平行于 $x$ 轴， $S=max(x_1-1,n-x_1,x_2-1,n-x_2)*abs(y_1-y_2)$ 。
平行于 $y$ 轴同理。
我们设 $f [a] [0 . . 9]$ 表示所有纵坐标的 $a$ 的点的 $m a x (x - 1, n - x)$ 的最大值。
枚举 $i$ 与 $j$ 表示三角形的点在这两行处，
$S = m a x (f [i] [k], f [j] [k]) * a b s (i - j)$
列同样处理即可。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
const int maxn=2007;
using namespace std;
int T,n;
int a[maxn][maxn];
char s[maxn];
int b[maxn][10],c[maxn][10],ans[10];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%s",s+1);
for (int j=1;j<=n;j++) a[i][j]=s[j]-'0';
}
for (int i=1;i<=n;i++)
{
for (int k=0;k<=9;k++) b[i][k]=c[i][k]=0;
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
b[i][a[i][j]]=max(b[i][a[i][j]],max(j-1,n-j));
c[j][a[i][j]]=max(c[j][a[i][j]],max(i-1,n-i));
}
}
for (int k=0;k<=9;k++)
{
ans[k]=0;
for (int i=1;i<=n;i++)
{
for (int j=i+1;j<=n;j++)
{
if ((b[i][k]) && (b[j][k]))
{
ans[k]=max(ans[k],(j-i)*max(b[i][k],b[j][k]));
}
}
}
for (int i=1;i<=n;i++)
{
for (int j=i+1;j<=n;j++)
{
if ((c[i][k]) && (c[j][k]))
{
ans[k]=max(ans[k],(j-i)*max(c[i][k],c[j][k]));
}
}
}
printf("%d ",ans[k]);
}
printf("n");
}2
}

D.
设 $f [i]$ 为从 $1$ 走到 $i$ 且中途没有记录点的期望步数。
可以推出 $f [1] = 2$ ， $f [i] = f [i - 1] * 2 + 2$ ，通项即为 $f[i]=2^{i+1}-2$ 。
也就是一段长为 $l e n$ 的 $10000 . . . . . 001$ 的期望就是 $2^{len}$ 。
根据这个构造即可。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#define LL long long
const int maxn=2007;
using namespace std;
int T,cnt;
int a[maxn];
LL n,bit[maxn];
int main()
{
bit[1]=2;
for (int i=2;i<=60;i++) bit[i]=bit[i-1]*2;
scanf("%d",&T);
while (T--)
{
scanf("%lld",&n);
if (n&1)
{
printf("-1n");
continue;
}
cnt=0;
for (int i=60;i>=3;i--)
{
if (n>=bit[i])
{
a[++cnt]=1;
for (int j=1;j<=i-2;j++) a[++cnt]=0;
a[++cnt]=1;
n-=bit[i];
}
}
while (n>0)
{
a[++cnt]=1;
n-=2;
}
printf("%dn",cnt);
for (int i=1;i<=cnt;i++) printf("%d ",a[i]);
printf("n");
}
}

E.
先二分一个答案 $m i d$ ，设 $f [x]$ 表示遍历完以 $x$ 为根的子树最后停下的点距离 $x$ 的最小值。
显然，如果 $x$ 为叶子节点， $f [x] = 0$ 。
如果 $x$ 有子节点 $f [x] > = m i d$ ，或者有两个子节点 $f [x] = m i d - 1$ （遍历完一棵子树无法跳到另一棵），那么 $x$ 就无法到达。
如果只有一个子节点 $f [x] = m i d - 1$ ，那么 $f [x] = m i d$ 。
否则 $f[x]=min_{yin x.son}f[y]+1$ 。
如果可以到达根，则 $m i d$ 合法。

代码：

#include <iostream>
#include <cstdio>
const int maxn=2e5+7;
using namespace std;
int n,x,y,cnt,T,ans,mid;
int f[maxn],ls[maxn],size[maxn];
struct edge{
int y,next;
}g[maxn*2];
void add(int x,int y)
{
g[++cnt]=(edge){y,ls[x]};
ls[x]=cnt;
}
void dfs(int x,int fa)
{
int num=0;
for (int i=ls[x];i>0;i=g[i].next)
{
int y=g[i].y;
if (y==fa) continue;
dfs(y,x);
size[x]+=size[y];
if ((f[y]==-1) || (f[y]>=mid))
{
f[x]=-1;
return;
}
if (f[y]==mid-1) num++;
f[x]=min(f[x],f[y]+1);
}
if (size[x]==1)
{
f[x]=0;
return;
}
if (num>1) f[x]=-1;
else if (num==1) f[x]=mid;
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++) ls[i]=0;
for (int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
int l=1,r=n;
ans=n;
while (l<=r)
{
mid=(l+r)/2;
for (int i=1;i<=n;i++)
{
f[i]=1e9;
size[i]=1;
}
dfs(1,0);
if (f[1]==-1) l=mid+1;
else ans=mid,r=mid-1;
}
printf("%dn",ans);
}
}

F.
设 $f [i] [j]$ 为最后一步是从 $i$ 到 $j$ ，且路径唯一需要删除的点的最小值。
令 $c n t$ 表示 $i$ 到 $j$ 间有多少个位置能到达 $j$ ，如果能到达都需要删去，显然 $i$ 都可以到达这些位置。
$f[i][j]=min_{k=1}^{i-1}f[k][i]+cnt (k+a[k]<j)$
可以知道，这样处理可以保证路径唯一。
其中 $c n t$ 可以通过倒着枚举 $i$ 统计。
我们设 $g[i]=min_{k=1}^{i-1}f[k][i] (k+a[k]<j)$
我们可以在 $k + a [k]$ 处打一个标记，当枚举到这个标记时，更新 $g$ 即可。
复杂度为 $O(n^2)$ 。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
const int maxn=3007;
using namespace std;
int n,T;
int f[maxn][maxn],g[maxn];
int a[maxn],v[maxn];
vector <int> b[maxn];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i+a[i]].push_back(i);
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++) f[i][j]=0x3f3f3f3f;
g[i]=0x3f3f3f3f;
v[i]=0;
}
g[1]=0;
for (int j=2;j<=n;j++)
{
int cnt=0;
for (int i=j-1;i>0;i--)
{
if (i+a[i]>=j)
{
f[i][j]=g[i]+cnt;
if (v[i]) g[j]=min(g[j],f[i][j]);
cnt++;
}
}
for (int i=0;i<b[j].size();i++)
{
v[b[j][i]]=1;
for (int k=b[j][i]+1;k<=j;k++) g[k]=min(g[k],f[b[j][i]][k]);
}
b[j].clear();
}
printf("%dn",g[n]);
}
}