CodeChef March Challenge 2020 简要题解_综合

做不动Challenge，垫底了。

Lasers Everywhere

略

Chef and DAG

略

Lasers Everywhere Alternative

略

Winning Ways 2

这是个NIM游戏，先求出SG值。
考虑离线莫队算法。先求出SG值，这个给每种权值维护一个计数器即可简单在莫队插入删除时维护。再考虑求方案数，枚举第一步操作的权值。注意到每种权值对答案的贡献只跟它的出现次数有关，考虑把出现次数相同的元素合并在一起处理，这样只有 $N\sqrt N$ 种，暴力枚举即可。为了快速枚举，我们需要在莫队修改的同时维护一个列表，保存当前出现过的出现次数和对应的权值种类数，用链表可以 $O(1)\mathcal O(1)$ 完成。
单组数据时间复杂度为 $O((N+Q)N)\mathcal O((N+Q)\sqrt N)$ 。

#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;
}ll facd[100005],facv[100005];void prepare(int n) {
    facd[0]=1;for(int i=1;i<=n;i++) facd[i]=facd[i-1]*i%MOD;facv[n]=pow_mod(facd[n],MOD-2);for(int i=n-1;i>=0;i--) facv[i]=facv[i+1]*(i+1)%MOD;
}inline ll C(int n,int m) {
    return (n<m)?0:facd[n]*facv[m]%MOD*facv[n-m]%MOD;
}int S;struct Query {
    int l,r,id,bl;Query() {
    }Query(int a,int b,int c):l(a),r(b),id(c) {
    bl=(l-1)/S+1;}bool operator < (const Query & b) const {
    return (bl!=b.bl)?bl<b.bl:r<b.r;}
};Query q[100005];
int ans[100005];int size[100005],cnt[100005];
int pre[100005],nxt[100005];void add(int x) {
    if (size[x]<=S) cnt[size[x]]--;size[x]++;if (size[x]<=S) cnt[size[x]]++;else if (size[x]==S+1) {
    pre[x]=0;nxt[x]=nxt[0];pre[nxt[0]]=x;nxt[0]=x;}
}void del(int x) {
    if (size[x]<=S) cnt[size[x]]--;else if (size[x]==S+1) {
    nxt[pre[x]]=nxt[x];pre[nxt[x]]=pre[x];pre[x]=nxt[x]=0;}size[x]--;assert(size[x]>=0);if (size[x]<=S) cnt[size[x]]++;
}int query() {
    int sg=0;for(int i=1;i<=S;i++)if (cnt[i]&1) sg^=i;for(int i=nxt[0];i;i=nxt[i]) sg^=size[i];if (!sg) return 0;int ans=0;for(int i=1;i<=S;i++)if (cnt[i]&&(i^sg)<i) ans=(ans+C(i,i^sg)*cnt[i])%MOD;for(int i=nxt[0];i;i=nxt[i]) if ((size[i]^sg)<size[i]) ans=(ans+C(size[i],size[i]^sg))%MOD;return ans;
}int num[100005],val[100005];void solve(int n) {
    sort(q+1,q+n+1);int l=1,r=0;for(int i=1;i<=n;i++) {
    while (l>q[i].l) add(num[--l]);while (r<q[i].r) add(num[++r]);while (l<q[i].l) del(num[l++]);while (r>q[i].r) del(num[r--]);ans[q[i].id]=query();}
}void init() {
    memset(size,0,sizeof(size));memset(cnt,0,sizeof(cnt));memset(pre,0,sizeof(pre));memset(nxt,0,sizeof(nxt));
}int main() {
    prepare(1e5);int cases;scanf("%d",&cases);for(;cases;cases--) {
    init();int n;scanf("%d",&n);S=(int)(sqrt(n)+0.5);for(int i=1;i<=n;i++) {
    scanf("%d",&num[i]);val[i]=num[i];}sort(val+1,val+n+1);for(int i=1;i<=n;i++) num[i]=lower_bound(val+1,val+n+1,num[i])-val;int m;scanf("%d",&m);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);q[i]=Query(x,y,i);}solve(m);for(int i=1;i<=m;i++) printf("%d\n",ans[i]);}return 0;
}

Break

令Chef的序列为 $A$ ，他的朋友的序列为 $B$ 。

$S = 1$ ：

注意到合法的一个必要条件是能够将 $A$ 和 $B$ 重排后 $A_i<B_i$ ，于是最优方案显然为将 $A$ 和 $B$ 排序，从小往大依次取，如果存在 $Ai≥BiA_i\geq B_i$ 或某个 $A_i>A_1$ 在之前没出现过就不合法。

$S = 2$ ：

特判一下 $N≤2N\leq 2$ ，接下来仅考虑 $N≥3N\geq 3$ 。
我们仍然需要将 $2 N$ 张牌分成 $N$ 对，每对大小不同，因此若某种权值出现 $> N$ 次显然无解。否则将 $A$ 和 $B$ 排序后，若有 $A1≥BNA_1\geq B_N$ ，显然不可能一轮出完，此时如果有 $A$ 全部相同或 $B$ 全部相同（打完一轮后有至少 $N$ 张相同的牌）显然也无解。
我们断言其他情况均有解。此时我们一定可以令Chef打掉两张牌（可能需要传 $A_N$ 给朋友），使得剩下的牌不存在 $N$ 张相同的。那么我们随意让Chef保留一张手牌，其他的传给朋友（这一步应该在打掉两张牌之前，实际上保留需要打出的牌），这时候朋友可以给剩下的牌配对，恰当地传回 $N ? 2$ 张牌给Chef，然后两人交替 $N ? 1$ 轮打完即可。
单组数据时间复杂度是排序的 $O(Nlog?N)\mathcal O(N\log N)$ 。

#include <bits/stdc++.h>using namespace std;int a[100005],b[100005];bool solve1(int n) {
    for(int i=1;i<=n;i++)if (a[i]>=b[i]) return 0;int r=1;for(int i=2;i<=n;i++)if (a[i]!=a[i-1]) {
    while (r<=n&&b[r]!=a[i]) r++;if (r>n) return 0;}return 1;
}bool solve2(int n) {
    if (n==1) return a[1]<b[1];if (n==2) return (a[1]<b[2]&&b[1]<a[2])||(a[1]<b[1]&&a[2]<b[2]&&(a[2]==a[1]||a[2]==b[1]));int r=0,s1=0,s2=0;for(int i=1;i<=n;i++) {
    if (a[i]!=a[i-1]) s1=0;s1++;while (r<n&&b[r+1]<=a[i]) {
    r++;if (b[r]!=b[r-1]) s2=0;s2++;}if (s1+((b[r]==a[i])?s2:0)>n) return 0;}if (a[1]>=b[n]) {
    bool ok=0;for(int i=1;i<=n;i++)if (a[i]!=a[1]) {
    ok=1;break;}if (!ok) return 0;ok=0;for(int i=1;i<=n;i++)if (b[i]!=b[1]) {
    ok=1;break;}if (!ok) return 0;}return 1;
}int main() {
    int cases,S;scanf("%d%d",&cases,&S);for(;cases;cases--) {
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]);sort(a+1,a+n+1);sort(b+1,b+n+1);if (S==1) puts((solve1(n))?"YES":"NO");else puts((solve2(n))?"YES":"NO");}return 0;
}

Inverse of a Function

先特判一些corner case。
对于一般情况，简单分析可知对于一个序列 $A$ ，得到的beauty值为 $2N?1?(A1∨A2∨...∨AN)2^{N-1}\cdot(A_1 \lor A_2\lor ...\lor A_N)$ 。于是对于 $F(N,B)≠0F(N,B)\neq 0$ ，有 $2^{N-1}|B$ ，且令 $B=2^{N-1}C$ ，有 $F(N,B)=2^{L=popcount(C)}$ 。
于是问题变为给定 $2LmodM2^L \bmod M$ ，最小化 $L$ 。这是经典的离散对数问题，注意到因为 $M$ 可以是合数，需要用扩展BSGS算法求解。
单组数据时间复杂度为 $O(N+M)\mathcal O(N+\sqrt M)$ 。

#include <bits/stdc++.h>
#define MOD 998244353
#define inv2 499122177using 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;
}char str[10005];ll pow_str(int n,int mod) {
    ll mi[10];mi[0]=1;for(int i=1;i<10;i++) mi[i]=mi[i-1]*2LL%mod;ll s=1;for(int i=1;i<=n;i++) {
    ll ns=s;for(int j=1;j<10;j++) s=s*ns%mod;s=s*mi[str[i]-'0']%mod;}return s;
}unordered_map <int,int> mp;int bsgs(ll a,int mod,int d) {
    mp.clear();ll s1=1;for(int i=0;i<40;i++) {
    if (s1==d) return i;s1=s1*a%mod;}int t=__gcd((int)s1,mod);if (d%t!=0) return -1;int S=(int)sqrt(mod)+1;ll s2=1;for(int i=1;i<=S;i++) {
    s2=s2*a%mod;mp[s2*d%mod]=i;}for(int i=1;i<=S;i++) {
    s1=s1*s2%mod;if (mp.count(s1)) return 40+i*S-mp[s1];}return -1;
}int solve(int n,int m,int d) {
    if (m==1) return 0;if (n==1&&str[1]=='1') return (d==1)?0:-1;if (!d) return 1;int v=(pow_str(n,m)-1+m)%m;int t=bsgs(v,m,d);if (t==-1) return -1;else return pow_str(n,MOD)*inv2%MOD*(pow_mod(2LL,t)-1+MOD)%MOD;
}int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    int m,k;scanf("%s%d%d",str+1,&k,&m);int n=strlen(str+1);printf("%d\n",solve(n,m,k));}return 0;
}

Egg-free DAG

注意到若图中存在长度 $> 3$ 的无弦环显然无解，因此有解的必要条件是原图是弦图。可以发现这个条件也是充分的，一个构造是取原图的一个完美消除序列 $v$ ，对于一条 $v_i$ 与 $v_j$ （ $i < j$ ）间的无向边，我们定向为 $v_i→v_j$ 。这样显然是一个DAG，且根据完美消除序列的性质， $v_i$ 在 $v_i,v_{i+1},...,v_n$ 的诱导子图中为单纯点，即 $v_i$ 在后缀中相邻点形成一个团，因此一定合法。
实现的时候可以考虑先跑一遍最大势算法求出一个序列，若这个序列不是完美消除序列，则原图不是弦图，因此无解。判定的过程也可以用弦图性质加速到线性。
单组数据时间复杂度为 $O(N+M)\mathcal O(N+M)$ 。
一开始没看到DAG的条件，对于一般有向图的情况只会一个 $O((N+M)M)\mathcal O((N+M)\sqrt M)$ 的枚举三元环后跑2-sat的做法，如果有更优复杂度的做法欢迎在评论区留言。

#include <bits/stdc++.h>using namespace std;struct Edge {
    int t,next;Edge() {
    }Edge(int a,int b):t(a),next(b) {
    }
};Edge e[400005];
int head[200005];int num[200005],id[200005];int d[200005],H[200005];
int pre[200005],nxt[200005];
bool vis[200005];void mcs(int n) {
    memset(d,0,sizeof(d));memset(H,0,sizeof(head));memset(pre,0,sizeof(pre));memset(nxt,0,sizeof(nxt));memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) {
    if (H[0]) pre[H[0]]=i;nxt[i]=H[0];H[0]=i;}int r=0;for(int i=1;i<=n;i++) {
    while (!H[r]) r--;int x=H[r];vis[x]=1;num[i]=x;id[x]=i;if (nxt[x]) pre[nxt[x]]=0;H[r]=nxt[x];for(int i=head[x];i;i=e[i].next)if (!vis[e[i].t]) {
    int u=e[i].t;if (!pre[u]) H[d[u]]=nxt[u];if (pre[u]) nxt[pre[u]]=nxt[u];if (nxt[u]) pre[nxt[u]]=pre[u];d[u]++;r=max(r,d[u]);if (H[d[u]]) pre[H[d[u]]]=u;nxt[u]=H[d[u]];pre[u]=0;H[d[u]]=u;}}
}vector <int> vt[200005];
int vis2[200005];bool check(int n) {
    memset(vis2,0,sizeof(vis2));for(int i=1;i<=n;i++) vt[i].clear();for(int i=1;i<=n;i++) {
    int maxn=0;for(int j=head[i];j;j=e[j].next)if (id[e[j].t]<id[i]&&id[e[j].t]>id[maxn]) maxn=e[j].t;if (maxn) vt[maxn].push_back(i);}for(int i=1;i<=n;i++) {
    for(int j=head[i];j;j=e[j].next)if (id[e[j].t]<id[i]) vis2[e[j].t]=i;for(int j=0;j<vt[i].size();j++) {
    int x=vt[i][j];for(int k=head[x];k;k=e[k].next)if (id[e[k].t]<id[i]&&vis2[e[k].t]<i) return 0;}}return 1;
}int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    memset(head,0,sizeof(head));int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);e[2*i-1]=Edge(y,head[x]);head[x]=2*i-1;e[2*i]=Edge(x,head[y]);head[y]=2*i;}mcs(n);if (!check(n)) puts("No solution");else {
    for(int i=1;i<=m;i++) putchar((id[e[2*i-1].t]>id[e[2*i].t])?'v':'^');printf("\n");}}return 0;
}

Good Subsequences

考虑先构造出原序列对应的析合树。
注意到对于一组合法的pair，一定是在某个合点的儿子按顺序构成的序列中取两个相交且不包含的连续子序列，要求相交部分对应长度 $≥X\geq X$ ，这个可以简单地用two pointer实现。
时间复杂度瓶颈在构造析合树上。这里为了实现方便用了一个 $O(Nlog?N)\mathcal O(N\log N)$ 的构造算法，实际上也存在一个 $O(N)\mathcal O(N)$ 的构造算法（参见lca的WC 2019营员交流课件）。

#include <bits/stdc++.h>
#define MOD 998244353
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<int,int> pr;namespace SGT {
    pr minn[1200000];
int addv[1200000];inline void pushdown(int o) {
    if (addv[o]) {
    addv[o*2]+=addv[o];minn[o*2].FR+=addv[o];addv[o*2+1]+=addv[o];minn[o*2+1].FR+=addv[o];addv[o]=0;}
}inline void pushup(int o) {
    minn[o]=min(minn[o*2],minn[o*2+1]);
}void build(int l,int r,int o) {
    if (l==r) minn[o]=pr(0,l);else {
    int m=((l+r)>>1);build(l,m,o*2);build(m+1,r,o*2+1);pushup(o);}
}void update(int l,int r,int o,int lx,int rx,int p) {
    if (l>=lx&&r<=rx) {
    addv[o]+=p;minn[o].FR+=p;}else {
    pushdown(o);int m=((l+r)>>1);if (m>=lx) update(l,m,o*2,lx,rx,p);if (m<rx) update(m+1,r,o*2+1,lx,rx,p);pushup(o);}
}int query() {
    return minn[1].SE;
}}struct Node {
    int l,r,minn,maxn,kind;Node() {
    }Node(int a,int b,int c,int d,int e):l(a),r(b),minn(c),maxn(d),kind(e) {
    }
}; Node a[600005];
vector <int> e[600005];int num[300005],lpos[300005];
int st1[300005],st2[300005];inline Node merge(Node x,Node y,int t) {
    return Node(x.l,y.r,min(x.minn,y.minn),max(x.maxn,y.maxn),t);
}int build(int n) {
    int top1=0,top2=0;SGT::build(1,n,1);for(int i=1;i<=n;i++) {
    if (i>1) SGT::update(1,n,1,1,i-1,-1);while (top1&&num[st1[top1]]<num[i]) {
    SGT::update(1,n,1,st1[top1-1]+1,st1[top1],num[i]-num[st1[top1]]);top1--;}st1[++top1]=i;while (top2&&num[st2[top2]]>num[i]) {
    SGT::update(1,n,1,st2[top2-1]+1,st2[top2],num[st2[top2]]-num[i]);top2--;}st2[++top2]=i;lpos[i]=SGT::query();}int top=0,sz=0;for(int i=1;i<=n;i++) {
    a[++sz]=Node(i,i,num[i],num[i],0);int cur=sz;while (a[st1[top]].l>=lpos[i]) {
    Node u=a[st1[top]];if (max(u.maxn,a[cur].maxn)-min(u.minn,a[cur].minn)==a[cur].r-u.l) {
    if (u.kind==((a[cur].minn>u.minn)?1:2)) {
    a[st1[top]]=merge(u,a[cur],u.kind);e[st1[top]].push_back(cur);cur=st1[top--];}else {
    a[++sz]=merge(u,a[cur],((a[cur].minn>u.minn)?1:2));e[sz].push_back(st1[top--]);e[sz].push_back(cur);cur=sz;}}else {
    a[++sz]=a[cur];a[sz].kind=3;e[sz].push_back(cur);do {
    a[sz]=merge(a[st1[top]],a[sz],3);e[sz].push_back(st1[top--]);} while (a[sz].maxn-a[sz].minn!=a[sz].r-a[sz].l);reverse(e[sz].begin(),e[sz].end());cur=sz;}}st1[++top]=cur;}return st1[1];
}inline ll S(ll n) {
    return (n*(n+1)>>1)%MOD;
}int dfs(int x,int k) {
    if (!e[x].size()) return 0;int ans=0;for(int i=0;i<e[x].size();i++)ans=(ans+dfs(e[x][i],k))%MOD;if (a[x].kind!=3) {
    int l=0;for(int i=0;i<e[x].size();i++) {
    int u=e[x][i];while (l<i&&a[u].r-a[e[x][l+1]].l+1>=k) l++;if (a[u].r-a[e[x][l]].l+1>=k) ans=(ans+(ll)S(l)*(e[x].size()-i-1))%MOD;}}return ans;
}int main() {
    int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&num[i]);int rt=build(n);printf("%lld\n",2LL*dfs(rt,k)%MOD);return 0;
}

CodeChef March Challenge 2020 简要题解