Codechef June Challenge 2020 简要题解

这次题目比较简单。

The Tom and Jerry Game!

略

Operations on a Tuple

略

The Delicious Cake

略

Convenient Airports

注意到答案的下界为$2?\max (N?M?1,?\frac{d_0}{2}?)$，其中$d_0$为度数为$0$的点个数，下面给出一个能达到这个下界的构造。
对于两个内部有边的连通块，我们在第一个连通块中取出一条边$(u_1,v_1)$，第二个连通块中取出一条边$(u_2,v_2)$。若$(u_1,v_1)$和$(u_2,v_2)$中至少有一条边不为对应连通块的割边，我们可以进行一次操作：删去$(u_1,v_1)$和$(u_2,v_2)$，加入$(u_1,v_2)$和$(u_2,v_1)$。这样不会改变任何点的度数，且能合并两个连通块。
那么可以描述我们的算法了：一开始有一个空连通块$S$，我们先依次用上面的操作合并$S$与所有有环的连通块（显然一定能做到），然后考虑合并$S$与所有无环但非单点的连通块，如果$S$此时有非割边，可以继续操作，否则整个图已经是森林，需要多加一条边。最后考虑合并$S$与所有度数为$0$的单点，如果$S$此时有非割边$(u_1,v_1)$且至少有两个这样的单点$u_2$和$v_2$，可以删去$(u_1,v_1)$，加入$(u_1,v_2)$与$(u_2,v_1)$，这样只需加入一条边就可以合并两个单点，否则只能每次加入一条边合并一个单点。容易证明这个算法可以达到上面给出的下界。
实现的时候，可以考虑用队列储存当前$S$中所有不在DFS树上的边，这些边显然是非割边，可以任意删去，每次合并一个连通块DFS一下即可。
单组数据时间复杂度为$\mathcal{O}(N+M)$。

#include <bits/stdc++.h>
#define last last2using namespace std;struct Edge {
    int t,next;Edge() {
    }Edge(int a,int b):t(a),next(b) {
    }
};Edge e[1000005];
int head[100005],q[1000005],l,r,tot;
bool vis1[100005],vis2[1000005],vis3[100005];inline void addEdge(int x,int y) {
    e[++tot]=Edge(y,head[x]);head[x]=tot;e[++tot]=Edge(x,head[y]);head[y]=tot;
}int id[100005],s1,s2;
bool kind[100005];void dfs1(int x) {
    s1++;for(int i=head[x];i;i=e[i].next) {
    s2++;int u=e[i].t;if (!id[u]) {
    id[u]=id[x];dfs1(u);}}
}int dep[100005];void dfs2(int x) {
    vis1[x]=1;for(int i=head[x];i;i=e[i].next)if (id[e[i].t]==id[x]&&!vis2[(i+1)>>1]) {
    int u=e[i].t;if (!vis1[u]) {
    dep[u]=dep[x]+1;dfs2(u);}else if (dep[u]>dep[x]) q[++r]=((i+1)>>1);}
}int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    memset(head,0,sizeof(head));memset(vis1,0,sizeof(vis1));memset(vis2,0,sizeof(vis2));memset(vis3,0,sizeof(vis3));memset(id,0,sizeof(id));int n,m;scanf("%d%d",&n,&m);tot=0;for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);addEdge(x,y);}int s0=0,cnt=0;for(int i=1;i<=n;i++)if (!id[i]) {
    if (!head[i]) s0++;id[i]=++cnt;s1=s2=0;dfs1(i);kind[cnt]=(s1<=(s2>>1));}printf("%d ",max(2*(n-1-m),2*((s0+1)>>1)));l=1;r=0;int rt=0;for(int i=1;i<=n;i++)if (!vis3[id[i]]&&kind[id[i]]) {
    vis3[id[i]]=1;if (l<=r) {
    int t1=q[l++],t2=((head[i]+1)>>1);vis2[t1]=vis2[t2]=1;int u1=e[2*t1-1].t,v1=e[2*t1].t;int u2=e[2*t2-1].t,v2=e[2*t2].t;addEdge(u1,u2);addEdge(v1,v2);dep[u2]=0;dfs2(u2);if (vis1[v2]) q[++r]=(tot>>1);else {
    dep[v2]=0;dfs2(v2);}}else {
    dep[i]=0;dfs2(i);rt=i;}}for(int i=1;i<=n;i++)if (!vis3[id[i]]&&head[i]) {
    vis3[id[i]]=1;if (l<=r) {
    int t1=q[l++],t2=((head[i]+1)>>1);vis2[t1]=vis2[t2]=1;int u1=e[2*t1-1].t,v1=e[2*t1].t;int u2=e[2*t2-1].t,v2=e[2*t2].t;addEdge(u1,u2);addEdge(v1,v2);}else if (rt) addEdge(rt,i);else rt=i;}int last=0;for(int i=1;i<=n;i++)if (!vis3[id[i]]&&!head[i]) {
    vis3[id[i]]=1;if (l<=r) {
    if (last) {
    int t=q[l++];vis2[t]=1;int u=e[2*t-1].t,v=e[2*t].t;addEdge(u,last);addEdge(v,i);last=0;}else last=i;}else addEdge(rt,i);}if (last) addEdge(rt,last);int s=0;for(int i=1;i<=(tot>>1);i++)if (!vis2[i]) s++;printf("%d\n",s);for(int i=1;i<=(tot>>1);i++)if (!vis2[i]) printf("%d %d\n",e[2*i].t,e[2*i-1].t);}return 0;
}

Guessing Game

可能是这次月赛最难的题目。得出$\mathcal{O}(\log N)$次询问的算法不难，但要通过$K=120$的限制，需要进一步的分析和讨论。
先考虑一个暴力一些的算法。维护一个当前答案可能的集合，当集合大小为常数时暴力询问，且任意时刻若返回${}^{\prime }{E}^{\prime }$可以直接终止，否则每次找到集合$\frac{1}{2}$位置的数$a$，询问$a$。显然这里返回${}^{\prime }{G}^{\prime }$和${}^{\prime }{L}^{\prime }$是等价的，不妨假设返回${}^{\prime }{G}^{\prime }$。再询问集合$\frac{1}{4}$位置的数$b$，此时再返回${}^{\prime }{G}^{\prime }$意味着两次询问中至少有一个返回信息是真的，那么显然$\le b$的数不可能是$S$，可以删去，返回$‘L^{\prime }$的话意味着两次信息是冲突的，而两次询问中至少有一个返回信息是真的，那么$b?a$之间的数必然不可能是$S$。无论哪一种情况至少能让集合大小减小$\frac{1}{4}$，大约需要$2?{\log }_{\frac{4}{3}}n+\mathcal{O}(1)\approx 144$次，不能通过。
优化一下这个算法。注意到如果上面第二种情况下，我们其实没有完全地利用信息，此时如果我们接着在$\ge a$的部分询问一次，由于上次是询问$b$返回了${}^{\prime }{L}^{\prime }$，因此不论这次返回什么都一定能进一步删除。考虑改变$b$为集合$\frac{1}{3}$位置的数，这样如果返回${}^{\prime }{G}^{\prime }$可以减小集合大小至少$\frac{1}{3}$。否则再询问集合$\frac{3}{4}$位置的数$c$，返回${}^{\prime }{G}^{\prime }$的话可以删去$b?c$之间的数，返回${}^{\prime }{L}^{\prime }$的话则可以删去$b?a$与$\ge c$的数，不论哪种情况都可以减小集合大小至少$\frac{5}{12}$。这样每轮要么用$2$次操作减小$\frac{1}{3}$，要么用$3$次操作减小$\frac{5}{12}$，大约需要$\max (2?{\log }_{\frac{3}{2}}n,3?{\log }_{\frac{12}{7}}n)+\mathcal{O}(1)\approx 115$次，可以通过。也可以把$\frac{1}{3}$用二分改进为更精确的常数，不过优化不大。
实现的时候需要维护答案可能的集合，它任意时刻是$\mathcal{O}(\log N)$段连续区间的并，暴力维护的话时间复杂度为$\mathcal{O}({\log }^{2}N)$。

#include <bits/stdc++.h>
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<int,int> pr;int ans,k;bool ask(int x) {
    printf("%d\n",x);fflush(stdout);char str[5];scanf("%s",str);if (str[0]=='E') exit(0);return str[0]=='G';/*k++;if (x==ans) {printf("%d %d\n",ans,k);exit(0);}if (k&1) return ans>x;else return (ans>x)^(rand()%2);*/
}pr a[1005];
int sz;int erase(int l,int r) {
    static pr cur[1005];int nsz=0;for(int i=1;i<=sz;i++)if (a[i].FR>r||a[i].SE<l) cur[++nsz]=a[i];else {
    if (a[i].FR<l) cur[++nsz]=pr(a[i].FR,l-1);if (a[i].SE>r) cur[++nsz]=pr(r+1,a[i].SE);}sz=nsz;int s=0;for(int i=1;i<=sz;i++) {
    a[i]=cur[i];s+=a[i].SE-a[i].FR+1;}return s;
}int query(int k) {
    for(int i=1;i<=sz;i++) {
    int v=a[i].SE-a[i].FR+1;if (k>v) k-=v;else return a[i].FR+k-1;}
}int randint() {
    return ((ll)rand()*9116111716LL+rand())%1000000007;
}int main() {
    int n;scanf("%d",&n);//ans=randint()%n+1;sz=1;a[1]=pr(1,n);while (n>3) {
    int mid=query((n+1)>>1);if (!ask(mid)) {
    int r=query(n-n/3+1);if (!ask(r)) n=erase(r,1e9);else {
    int l=query(n/4);if (!ask(l)) n=erase(l,r);else {
    n=erase(1,l);n=erase(mid,r);}}}else {
    int l=query(n/3);if (ask(l)) n=erase(1,l);else {
    int r=query(n-n/4+1);if (ask(r)) n=erase(l,r);else {
    n=erase(r,1e9);n=erase(l,mid);}}}}for(int i=1;i<=sz;i++)for(int j=a[i].FR;j<=a[i].SE;j++) ask(j);return 0;
}

Danya and Different Values

对每种颜色$c$分开考虑。对于每个点$x$，我们显然只需要知道$c$在$x$子树中的最小深度（不存在为$\inf$）。那么对于颜色$c$的点构成的虚树，虚树上每条链上的点对应的子树中最小深度相同（不在这些链上的点子树中最小深度为$\inf$，不用考虑）。那么建出虚树，作一个简单的差分可以将所有颜色对应的修改拆成$\mathcal{O}(n)$组$(u,v,w)$的修改，意思是对$X$为$u$到根的路径上的点，且$de{p}_x+D\ge v$的询问会有$w$的贡献。
那么对深度建线段树，直接对子树线段树合并即可。单组数据时间复杂度为$\mathcal{O}((N+Q)\log N)$。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3fusing namespace std;namespace SGT {
    const int Maxn=20000000;int ch[Maxn][2],sumv[Maxn],tot;inline int cpynode(int o) {
    tot++;ch[tot][0]=ch[o][0];ch[tot][1]=ch[o][1];sumv[tot]=sumv[o];return tot;
}int update(int l,int r,int o,int p,int q) {
    o=cpynode(o);sumv[o]+=q;if (l==r) return o;else {
    int m=((l+r)>>1);if (m>=p) ch[o][0]=update(l,m,ch[o][0],p,q);else ch[o][1]=update(m+1,r,ch[o][1],p,q);return o;}
}int merge(int l,int r,int x,int y) {
    if (!x) return y;if (!y) return x;int o=++tot;sumv[o]=sumv[x]+sumv[y];if (l==r) return o;else {
    int m=((l+r)>>1);ch[o][0]=merge(l,m,ch[x][0],ch[y][0]);ch[o][1]=merge(m+1,r,ch[x][1],ch[y][1]);return o;}
}int query(int l,int r,int o,int p) {
    if (!o) return 0;if (l==r) return sumv[o];else {
    int m=((l+r)>>1);if (m>=p) return query(l,m,ch[o][0],p);else return sumv[ch[o][0]]+query(m+1,r,ch[o][1],p);}
}}vector <int> e1[200005],vt1[200005];
int num[200005];int dep[200005],fa[200005][20];
int dfn[200005],dfs_cnt;void dfs1(int x) {
    dep[x]=dep[fa[x][0]]+1;dfn[x]=++dfs_cnt;for(int i=0;i<e1[x].size();i++) {
    int u=e1[x][i];fa[u][0]=x;for(int j=1;j<20;j++) fa[u][j]=fa[fa[u][j-1]][j-1];dfs1(u);}
}int lca(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);int d=dep[x]-dep[y];for(int i=0;i<20;i++)if ((d>>i)&1) x=fa[x][i];if (x==y) return x;for(int i=19;i>=0;i--)if (fa[x][i]!=fa[y][i]) {
    x=fa[x][i];y=fa[y][i];}return fa[x][0];
}vector <int> e2[200005],vt2[200005];
int minn[200005],st[200005];void dfs2(int x,int v) {
    minn[x]=inf;int id=0;if (num[x]==v) {
    vt2[x].push_back(dep[x]);minn[x]=dep[x];id=x;}for(int i=0;i<e2[x].size();i++) {
    int u=e2[x][i];dfs2(u,v);if (minn[u]<minn[x]) {
    minn[x]=minn[u];id=u;}}for(int i=0;i<e2[x].size();i++)if (e2[x][i]!=id) vt2[x].push_back(-minn[e2[x][i]]);e2[x].clear();
}bool cmp(int x,int y) {
    return dfn[x]<dfn[y];
}void build(int v) {
    if (!vt1[v].size()) return;sort(vt1[v].begin(),vt1[v].end(),cmp);int top=1;st[1]=1;for(int i=0;i<vt1[v].size();i++)if (st[top]!=vt1[v][i]) {
    int x=vt1[v][i];int p=lca(x,st[top]);for(;;) {
    if (dep[p]<=dep[st[top-1]]) {
    e2[st[top-1]].push_back(st[top]);top--;}else if (dep[p]<dep[st[top]]) {
    e2[p].push_back(st[top]);st[top]=p;}else break;}if (st[top]!=x) st[++top]=x;}for(;top>1;top--) e2[st[top-1]].push_back(st[top]);dfs2(1,v);
}int root[200005];void dfs3(int x,int n) {
    root[x]=0;for(int i=0;i<vt2[x].size();i++) {
    int u=vt2[x][i];root[x]=SGT::update(1,n,root[x],abs(u),((u>0)?1:-1));}for(int i=0;i<e1[x].size();i++) {
    int u=e1[x][i];dfs3(u,n);root[x]=SGT::merge(1,n,root[x],root[u]);}
}int main() {
    minn[0]=inf;int cases;scanf("%d",&cases);for(;cases;cases--) {
    SGT::tot=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++) {
    e1[i].clear();vt1[i].clear();vt2[i].clear();}for(int i=2;i<=n;i++) {
    int x;scanf("%d",&x);e1[x].push_back(i);}for(int i=1;i<=n;i++) {
    scanf("%d",&num[i]);vt1[num[i]].push_back(i);}dfs_cnt=0;dfs1(1);for(int i=1;i<=n;i++)build(i);dfs3(1,n);int m;scanf("%d",&m);int lastans=0;for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);x^=lastans;y^=lastans;y=min(n,dep[x]+y);printf("%d\n",lastans=SGT::query(1,n,root[x],y));}}return 0;
}

Perfect Partitions

一个很套路的题目。
容易发现，我们其实是要求出$F(x)={\prod }_{i=1}^Q({\sum }_{j\le b_i}{x}^{a_i?j})$的前$N+1$次项系数。
考虑取$\ln$再$\exp$的套路，$\ln F(x)={\sum }_{i=1}^Q(\ln (1?x^{a_i?b_i+1})?\ln (1?x_i^a))$，也即若干个$\ln (1?x^k)$带系数的和。注意到$\ln (1?x^k)$只有前$\mathcal{O}(\frac{N}{k})$次项有用，那么对于每个$k$直接暴力对有用的项计算系数即可算出$\ln F(x)$前$N+1$次项，用调和级数可以分析出来这部分是$\mathcal{O}(N\log N)$的。
算出了$\ln F(x)$前$N+1$次项系数后，直接求出$\exp (\ln F(x))$前$N+1$次项系数即可。时间复杂度为$\mathcal{O}(N\log N+Q)$。

#include <bits/stdc++.h>
#define MOD 998244353using namespace std;typedef long long ll;ll pow_mod(ll x,int k) {
    ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
}const int Maxn=1<<19;ll *w[19];void ntt_init() {
    for(int i=2,t=0;i<=Maxn;i<<=1,t++) {
    w[t]=new ll[i>>1];ll wn=pow_mod(3,(MOD-1)/i);w[t][0]=1;for(int j=1;j<(i>>1);j++) w[t][j]=w[t][j-1]*wn%MOD;}
}ll inv[Maxn];void pre(int n) {
    inv[1]=1;for(int i=2;i<=n;i++) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
}void rev(ll *p,int len) {
    int j=len>>1;for(int i=1;i<len-1;i++) {
    if (i<j) swap(p[i],p[j]);int k=len>>1;while (j>=k) {
    j-=k;k>>=1;}if (j<k) j+=k;}
}void ntt(ll *p,int len,int check) {
    rev(p,len);for(int i=2,t=0;i<=len;i<<=1,t++)for(int j=0;j<len;j+=i)for(int k=j;k<j+(i>>1);k++) {
    ll u=p[k];ll v=w[t][k-j]*p[k+(i>>1)];p[k]=(u+v)%MOD;p[k+(i>>1)]=(u-v)%MOD;}if (check==-1) {
    reverse(p+1,p+len);ll nev=pow_mod(len,MOD-2);for(int i=0;i<len;i++) p[i]=(p[i]+MOD)*nev%MOD;}
}void getinv(ll *p,ll *q,int len) {
    static ll t1[Maxn];if (len==1) {
    q[0]=1;return;}getinv(p,q,len>>1);memcpy(t1,p,sizeof(ll)*len);memset(t1+len,0,sizeof(ll)*len);ntt(q,len<<1,1);ntt(t1,len<<1,1);for(int i=0;i<(len<<1);i++) q[i]=q[i]*(2LL-q[i]*t1[i]%MOD)%MOD;ntt(q,len<<1,-1);memset(q+len,0,sizeof(ll)*len);
}void getdif(ll *p,ll *q,int len) {
    for(int i=0;i<len-1;i++) q[i]=p[i+1]*(i+1)%MOD;q[len-1]=0;
}void getint(ll *p,ll *q,int len) {
    for(int i=len-1;i>0;i--) q[i]=p[i-1]*inv[i]%MOD;q[0]=0;
}void getln(ll *p,ll *q,int len) {
    static ll t1[Maxn];memset(t1,0,sizeof(ll)*(len<<1));getinv(p,t1,len);getdif(p,q,len);ntt(q,len<<1,1);ntt(t1,len<<1,1);for(int i=0;i<(len<<1);i++) q[i]=q[i]*t1[i]%MOD;ntt(q,len<<1,-1);getint(q,q,len);memset(q+len,0,sizeof(ll)*len);
}void getexp(ll *p,ll *q,int len) {
    static ll t1[Maxn];if (len==1) {
    q[0]=1;return;}getexp(p,q,len>>1);memset(t1,0,sizeof(ll)*(len<<1));getln(q,t1,len);for(int i=0;i<len;i++) t1[i]=(p[i]-t1[i]+MOD)%MOD;t1[0]=(t1[0]+1LL)%MOD;ntt(q,len<<1,1);ntt(t1,len<<1,1);for(int i=0;i<(len<<1);i++) q[i]=q[i]*t1[i]%MOD;ntt(q,len<<1,-1);memset(q+len,0,sizeof(ll)*len);
}ll p[Maxn],q[Maxn];
ll cnt[200005];int main() {
    ntt_init();int n,m;scanf("%d%d",&n,&m);int len=1;while (len<=n) len<<=1;pre(len);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);cnt[x]=(cnt[x]+1LL)%MOD;if ((ll)(y+1)*x<=n) cnt[(y+1)*x]=(cnt[(y+1)*x]-1LL+MOD)%MOD;}for(int i=1;i<=n;i++)if (cnt[i]) {
    for(int j=1;i*j<len;j++) p[i*j]=(p[i*j]+cnt[i]*inv[j])%MOD;}getexp(p,q,len);for(int i=1;i<=n;i++) printf("%lld ",q[i]);printf("\n");return 0;
}