Preface
开始裸泳咯这个A题给我写的头皮发麻，后面发现我就是个智障儿童
比赛的时候E题想了半天感觉天皇老子来了也是\(\frac{1}{n^2}\)，赛后发现我是小丑
感觉中间做J的时候因为看错题目浪费了很长时间，不过再给一个小时思博题该不会还是不会
A. Paint the Middle
比赛的时候一眼贪心，每次选最长的区间然后把中间改成\(1\)，但是有可能中间的数字是其它区间的端点，这样就要减去\(1\)的贡献，然后排序后贪心发现假了
考虑用DP来解决，首先某个位置最后出现的位置一定是区间的右端点，不妨用\(pos_i\)来表示\(i\)最后出现的位置
设\(f_i\)表示前\(i\)个数中\(0\)的个数，而至于为什么记录\(0\)而不是\(1\)的个数是因为\(0\)作为端点，比较方便我们的转移
由于每个数都可以取\(0\)，所以显然有\(f_i=\min(f_i,f_{i-1}+1)\)，然后我们设\(cur\)表示当前右端点的最大值
由于每个时刻\(cur\)对应的左端点一定\(\le i\)，所以总可以把\((i,cur)\)中的所有数都置为\(1\)，因此有转移\(f_{cur}=\min(f_{cur},f_i+1)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=200005,INF=1e9;
int n,a[N],pos[N],f[N],cur;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i) f[i]=INF,scanf("%d",&a[i]),pos[a[i]]=i;
for (i=1;i<=n;++i) f[i]=min(f[i],f[i-1]+1),cur=max(cur,pos[a[i]]),f[cur]=min(f[cur],f[i]+1);
return printf("%d",n-f[n]),0;
}
B. Game on Sum (Easy Version)
题目乍一看比较哈人，其实细想很简单
不妨设\(f_{i,j}\)表示还剩\(i\)轮，其中有\(j\)次加法操作时最后得到的数的期望
首先考虑清边界条件，这题的边界有两种情况：
- \(i=j\)，此时剩下的数都是加法，故直接贪心取最大的：\(f_{i,j}=i\times k\)
- \(j=0\)，此时剩下的数都是减法，故直接都取\(0\)：\(f_{i,j}=0\)
否则考虑假设这一轮选了数\(t\)，那么它会转移到两个局面，一个是\(f_{i-1,j}-t\)，一个是\(f_{i-1,j-1}+t\)
很显然trade-off一下就能得到\(f_{i,j}=\frac{f_{i-1,j}+f_{i-1,j-1}}{2}\)，复杂度\(O(n^2)\)
感觉这个转移式其实和组合数关系很密切，优化下应该可以降掉一个\(O(n)\)的复杂度
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=2005,mod=1e9+7,inv2=(mod+1)/2;
int t,n,m,k,f[N][N];
inline int DP(CI x,CI y)
{
if (x==y) return 1LL*x*k%mod; if (!x||!y) return 0;
if (~f[x][y]) return f[x][y];
return f[x][y]=1LL*(DP(x-1,y)+DP(x-1,y-1))*inv2%mod;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%d%d",&n,&m,&k),i=0;i<=n;++i)
for (j=0;j<=m;++j) f[i][j]=-1; printf("%d\n",DP(n,m));
}
return 0;
}
C. Dwarves, Hats and Extrasensory Abilities
一般确实这种操作自由的题目就越要给它加上点限制才好做
这道题我们首先可以想到，如果所有点都在一个数轴上，但是如果我们已经知道了之前的黑白点划分在哪一块内，只要每次在中间取一个数，然后视它的黑白情况缩小接下来的划分即可
那么我们考虑先询问\((0,0),(10^9,0)\)，如果得到的是两个不同的颜色，那么直接套用上面的做法在\(x\)轴上做即可
否则我们转而在\(y\)轴上划分，根据已知的两个点颜色也可以确定上下两个区域，这道题就做完了
第一发写完发现WA on 72就有点搞，后面冷静思考发现因为我二分的时候写的mid=l+r>>1，这样左边的区间永远都偏小，这样就可能会在最后一次导致划分的线和之前的点重合
后面修改了下保证每次中点的选择轮流偏左偏右即可通过
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=35,INF=1e9;
int n; char s[10];
inline int ask(CI x,CI y)
{
printf("%d %d\n",x,y); fflush(stdout);
scanf("%s",s+1); return s[1]=='b'?0:1;
}
inline void x_solve(CI a,CI b,CI l,CI r,CI lst=0)
{
int mid=l+r+lst>>1; if (!n) return (void)(printf("%d %d %d %d\n",mid,0,mid,INF),fflush(stdout));
int c=ask(mid,0); --n; if (c==b) x_solve(a,b,l,mid-1,lst^1); else x_solve(a,b,mid+1,r,lst^1);
}
inline void y_solve(CI a,CI b,CI l,CI r,CI lst=0)
{
int mid=l+r+lst>>1; if (!n) return (void)(printf("%d %d %d %d\n",0,mid,INF,mid),fflush(stdout));
int c=ask(0,mid); --n; if (c==b) y_solve(a,b,l,mid-1,lst^1); else y_solve(a,b,mid+1,r,lst^1);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
scanf("%d",&n); if (n==1) return ask(0,0),printf("0 1 1 0\n"),fflush(stdout),0;
int a=ask(0,0),b=ask(INF,0); n-=2; if (a!=b) x_solve(a,b,0,INF); else y_solve(a,a^1,0,INF);
return 0;
}
D. Make It Equal
由于\(h_i\)的范围不是很大，直接按题意模拟即可，每层有多少个方块可以差分求出
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=200005,INF=1e9;
int n,k,h[N],num[N],mi=INF,mx;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%lld%lld",&n,&k),i=1;i<=n;++i)
scanf("%lld",&h[i]),++num[h[i]],mi=min(mi,h[i]),mx=max(mx,h[i]);
for (i=mx;i>mi;--i) num[i]+=num[i+1];
int cur=0,ans=0; for (i=mx;i>mi;--i)
if (cur+num[i]>k) ++ans,cur=num[i]; else cur+=num[i];
return printf("%lld",ans+(cur!=0)),0;
}
E. Harmony in Harmony
考虑把题意转化下，存在⼀个两侧各有\(n\)个结点的带边权的满二分图，边权为实数，并且对任何⼀个结点，其所连边的权值和等于\(\frac{1}{n}\)
要求寻找一个尽可能大的\(k\)，使得在任何满⾜上述条件的二分图下，都能够找到二分图的完美匹配，使得匹配边的权值都不低于\(k\)
考虑如下构造产生的答案的上界，取\(t\)个白点，令前\(t-1\)个黑点每个和这\(t\)个白点连边的权值都是\(\frac{1}{nt}\)，这些白点剩下的\(\frac{1}{n\times t}\)权值平分给剩下的\(n-(t-1)\)个黑点，则一定有一个黑点的匹配边权为\(\frac{1}{n\times t\times (n+1-t)}\)
取\(t=\lfloor\frac{n+1}{2}\rfloor\)，即可得到答案的一个上界，结合霍尔定理不难发现这个上界一定能取到
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
int n;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
scanf("%d",&n); int t=(n+1)/2;
return printf("%.9lf",1.0/(n*t*(n+1-t))),0;
}
F. Life is a Game
很经典的克鲁斯卡尔重构树的题，这种边权限制的题目反正先把重构树建出来然后再思考题目要干什么
设\(sum_x\)表示点\(x\)子树内的点权和，不难发现\(x\)能向上跳的条件就是\(k+sum_x\ge w_{fa(x)}\)，其中\(w\)表示重构树上对应原来的边的边权
不难发现这个东西可以倍增优化，所以就可以做到\(O(n\log n)\)了
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=200005,INF=1e9;
struct Edge
{
int x,y,v;
inline Edge(CI X=0,CI Y=0,CI V=0)
{
x=X; y=Y; v=V;
}
friend inline bool operator < (const Edge& A,const Edge& B)
{
return A.v<B.v;
}
}E[N]; int n,m,q,a[N],tot,fa[N],w[N],sum[N],anc[N][20],f[N][20],x,k; vector <int> v[N];
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void DFS1(CI now,CI fa=0)
{
sum[now]=a[now]; for (int to:v[now]) if (to!=fa) DFS1(to,now),sum[now]+=sum[to];
if (fa) f[now][0]=w[fa]-sum[now]; anc[now][0]=fa;
}
inline void DFS2(CI now,CI fa=0)
{
for (RI i=0;i<19;++i) if (anc[now][i])
anc[now][i+1]=anc[anc[now][i]][i],f[now][i+1]=max(f[now][i],f[anc[now][i]][i]); else break;
for (int to:v[now]) if (to!=fa) DFS2(to,now);
}
inline int jump(int x,CI k)
{
for (RI i=19;i>=0;--i) if (anc[x][i]&&f[x][i]<=k) x=anc[x][i]; return x;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%d",&n,&m,&q),i=1;i<=2*n;++i) fa[i]=i;
for (i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=m;++i) scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].v);
for (sort(E+1,E+m+1),tot=n,i=1;i<=m;++i)
{
if (tot==2*n-1) break; int x=getfa(E[i].x),y=getfa(E[i].y);
if (x==y) continue; ++tot; fa[x]=fa[y]=tot;
v[tot].push_back(x); v[tot].push_back(y); w[tot]=E[i].v;
}
for (DFS1(tot),DFS2(tot),i=1;i<=q;++i) scanf("%d%d",&x,&k),printf("%d\n",k+sum[jump(x,k)]);
return 0;
}
G. Nastya and an Array
签到，求不等于\(0\)的数有多少种即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=100005;
int n,x; set <int> s;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),s.clear(),i=1;i<=n;++i)
if (scanf("%d",&x),x) s.insert(x);
return printf("%d\n",s.size()),0;
}
H. Replacement
签到，很经典的用set来维护区间的题目
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=300005;
int n,m,x,ans; set <pi> s; char str[N],ch[10];
inline void add(CI x)
{
auto nxt=s.lower_bound(pi(x,x)),pre=nxt; int l=x,r=x,flag=1;
if (pre!=s.begin()) --pre; else flag=0;
if (nxt!=s.end()&&nxt->fi==r+1) ans-=nxt->se-nxt->fi,r=nxt->se,s.erase(nxt);
if (flag&&pre->se==l-1) ans-=pre->se-pre->fi,l=pre->fi,s.erase(pre);
ans+=r-l; s.insert(pi(l,r));
}
inline void del(CI x)
{
auto it=s.upper_bound(pi(x,n)); --it; int l=it->fi,r=it->se; ans-=r-l; s.erase(it);
if (l<=x-1) ans+=x-1-l,s.insert(pi(l,x-1));
if (x+1<=r) ans+=r-(x+1),s.insert(pi(x+1,r));
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%s",&n,&m,str+1),i=1;i<=n;++i) if (str[i]=='.') add(i);
//for (auto [l,r]:s) printf("%d %d\n",l,r);
for (i=1;i<=m;++i)
{
scanf("%d%s",&x,ch+1); if (str[x]=='.') del(x);
if (ch[1]=='.') add(x); str[x]=ch[1]; printf("%d\n",ans);
}
return 0;
}
I. Beautiful Function
这题比赛的时候题面都懒得看，经典一堆话直接劝退
首先还是经典把限制加大，考虑能不能让函数直接穿过每个圆心
考虑类似于拉格朗日插值的思想，我们令函数为若干个函数的复合，比如\(f(t)=h_1(t)+h_2(t)+\cdots +h_n(t)\)
只要\(h_1(t)\)满足只有当\(t=x_1\)时有值，对于其它的\(t=x_2,x_3,\cdots,x_n\)都为\(0\)时就是正确的
而怎么找到这样的函数呢，考虑利用绝对值，因为题目中给出的看起来能搞出操作的函数只有绝对值函数了
以寻找\(h_1(t)\)为例，不妨设\(d=|t-x_1|\)，则考虑类似于开关函数，做出\(1-d+|1-d|\)
当\(d\ge 1\)时后面这个东西的值永远为\(0\)，否则当\(t=x_1\)时值为\(2\)
那么我们只要令\(h_1(t)=\lfloor\frac{x_1}{2}\rfloor\times (1-d+|1-d|)\)即可，注意虽然因为有下取整的原因这个点不一定经过圆心了，但由于保证了\(r_i\ge 2\)所以最多只有横纵各\(1\)的偏差，总共\(\sqrt 2\)偏差，依然在圆内
然后\(g(t)\)也是同理，总体来说还是很巧妙的
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
string X,Y; int n,x,y,r;
const string L="(((1-abs((t-",M=")))+abs((abs((t-",R="))-1)))";
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<n;++i) X+="(",Y+="(";
for (i=1;i<=n;++i)
{
scanf("%d%d%d",&x,&y,&r);
X+=L+to_string(i)+M+to_string(i)+R+"*"+to_string(x/2)+")";
Y+=L+to_string(i)+M+to_string(i)+R+"*"+to_string(y/2)+")";
if (i!=1) X+=")",Y+=")";
if (i!=n) X+="+",Y+="+";
}
return cout<<X<<endl<<Y,0;
}
J. Image Preview
刚开始看错题面了，以为skip掉一张照片就可以不用花费\(a\)的代价滑动，就变成每次在两边选一个数扩展，就变成和字符串专题的一个题很像了
后面正确理解题意后其实就先枚举下向左看\(i\)张然后回来需要的时间，然后再枚举向右看的张数即可
当然这个过程还要反着做一遍，每次就是二分找一下最多能看多少张
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=1000005;
int n,a,b,t,tim[N],ans; char s[N];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; scanf("%lld%lld%lld%lld%s",&n,&a,&b,&t,s+1);
if ((s[1]=='w')*b+1>t) return puts("0"),0;
for (t-=(s[1]=='w')*b+1,i=n+1;i<=2*n;++i) s[i]=s[i-n];
for (i=1;i<=n-1;++i)
{
tim[i]=tim[i-1]+a+(s[n+1-i]=='w')*b+1;
if (tim[i]<=t) ans=max(ans,i);
}
for (i=1;i<=n-1;++i) tim[i]+=i*a;
int cur=0; for (i=1;i<=n-1;++i)
{
cur+=a+(s[n+1+i]=='w')*b+1;
if (cur>t) break; ans=max(ans,i);
int pos=upper_bound(tim+1,tim+(n-1)+1,t-cur)-tim-1;
ans=max(ans,i+pos); ans=min(ans,n-1);
}
for (i=1;i<=n-1;++i)
{
tim[i]=tim[i-1]+a+(s[n+1+i]=='w')*b+1;
if (tim[i]<=t) ans=max(ans,i);
}
for (i=1;i<=n-1;++i) tim[i]+=i*a;
for (cur=0,i=1;i<=n-1;++i)
{
cur+=a+(s[n+1-i]=='w')*b+1;
if (cur>t) break; ans=max(ans,i);
int pos=upper_bound(tim+1,tim+(n-1)+1,t-cur)-tim-1;
ans=max(ans,i+pos); ans=min(ans,n-1);
}
return printf("%lld",ans+1),0;
}
K. New Year and Finding Roots
2800的交互，思路还是很妙的，不过代码写起来细节太多了就口胡一下思路了（才不是因为看TES打EDG导致懒得写呢）
考虑一个naive的想法，先随便问一个点，然后任意找一个没走过的相邻点走
这样如果不是运气好一路走到根的话最后都会走到某个叶节点，而重复两遍后就可以扩展出一条从叶子到叶子的链，就可以向上扩展答案了
计算一下这样的询问此时大概是\(1+2+3+\cdots+6=21\)次，考虑怎么压下剩下的询问
考虑上面的做法在距根节点较近的时候要花费比较大的代价，但换句话说此时我们如果用类似于BFS的思路会发现代价变得可观
trade-off一下会发现如果我们在到根的距离为\(2\)时换用BFS，只有最多\(7\)个点要check，但是如果我们已经查了前\(6\)个点都不是答案，那么根节点也就确定了，所以实际要用的询问次数是\(6\)次
这样\(1+2+3+4+6=16\)，恰好可以通过此题
L. Broken Keyboard
签到，所有连续段长度为奇数的字符一定是好的
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=505;
int t,n; char s[N]; bool c[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (i=0;i<26;++i) c[i]=0;
for (scanf("%s",s+1),n=strlen(s+1),i=1;i<=n;i=j)
{
for (j=i;j<=n&&s[j]==s[i];++j);
if ((j-i)%2==1) c[s[i]-'a']=1;
}
for (i=0;i<26;++i) if (c[i]) putchar(i+'a'); putchar('\n');
}
return 0;
}
Postscript
好好好写完博客喜闻TES3:2EDG，去抗吧开香槟去咯