Codeforces Round 902 Div 1 (CF 1876)

A. Helmets in Night Light

按花费 sort 一下，b<p" role="presentation" style="position: relative;">b<p$b<p$ 就让他用 b" role="presentation" style="position: relative;">b$b$ 的花费告诉别人，剩下的人一开始用 p" role="presentation" style="position: relative;">p$p$ 的花费告诉即可。

B. Effects of Anti Pimples

发现一个数会被所有它的因数贡献，O(nn)" role="presentation" style="position: relative;">O(nn−−√)$O(n\sqrt{n})$ 随便算一算，式子略。

---

C. Autosynthesis

Solution 1

想到了建图但没有完全想到，于是有了这个神秘做法。

题意等价于选择一个 下标集合，使它和 它补集对应的值域集合 相等。设它们分别为 S,T" role="presentation" style="position: relative;">S,T$S,T$。
由于不同位置的 ai" role="presentation" style="position: relative;">ai$a_i$ 有可能相等，设 |S|" role="presentation" style="position: relative;">|S|$|S|$ 表示 S" role="presentation" style="position: relative;">S$S$ 的元素个数，则有 |T|≤|S|" role="presentation" style="position: relative;">|T|≤|S|$|T|\le |S|$。

考虑 |S|>|T|" role="presentation" style="position: relative;">|S|>|T|$|S|>|T|$ 的情况，则一定至少存在一个下标 i∈[1,n]" role="presentation" style="position: relative;">i∈[1,n]$i\in [1,n]$，i" role="presentation" style="position: relative;">i$i$ 没在值域集合里出现过。那么如果在 S" role="presentation" style="position: relative;">S$S$ 集合选择下标 i" role="presentation" style="position: relative;">i$i$，没法找到一个数在 T" role="presentation" style="position: relative;">T$T$ 集合里与它对应。根据这一点我们可以判断哪些下标一定不选。
对于一定不选的下标 i" role="presentation" style="position: relative;">i$i$，则根据补集的定义值为 ai" role="presentation" style="position: relative;">ai$a_i$ 的数一定在 T" role="presentation" style="position: relative;">T$T$ 中被选，同时下标为 aai" role="presentation" style="position: relative;">aai$a_{a_i}$ 的数一定在 S" role="presentation" style="position: relative;">S$S$ 中被选。以此类推，只要还满足 |S|>|T|" role="presentation" style="position: relative;">|S|>|T|$|S|>|T|$ 我们就可以一直把已经确定选不选的数从集合里去掉，直到 |S|=|T|" role="presentation" style="position: relative;">|S|=|T|$|S|=|T|$。

考虑 |S|=|T|" role="presentation" style="position: relative;">|S|=|T|$|S|=|T|$ 的情况，这等价于 T" role="presentation" style="position: relative;">T$T$ 是一个 1∼n" role="presentation" style="position: relative;">1∼n$1\sim n$ 的排列。如果把值 ai" role="presentation" style="position: relative;">ai$a_i$ 选进 T" role="presentation" style="position: relative;">T$T$，下标 ai" role="presentation" style="position: relative;">ai$a_i$ 就必须在 S" role="presentation" style="position: relative;">S$S$。限制等价于下标 i" role="presentation" style="position: relative;">i$i$ 和 ai" role="presentation" style="position: relative;">ai$a_i$ 只能选一个，连边 i→ai" role="presentation" style="position: relative;">i→ai$i\to a_i$，判图上有没有奇环即可。

Solution 2

一开始就考虑按 i→ai" role="presentation" style="position: relative;">i→ai$i\to a_i$ 的方式建图，那么每个点有一条出边，图是一个内向基环树森林。

分类讨论下标 i" role="presentation" style="position: relative;">i$i$ 选不选：

• 不选点 i" role="presentation" style="position: relative;">i$i$，则点 ai" role="presentation" style="position: relative;">ai$a_i$ 一定被选。
• 选点 i" role="presentation" style="position: relative;">i$i$，则至少有一个 aj=i" role="presentation" style="position: relative;">aj=i$a_j=i$ 的下标 aj" role="presentation" style="position: relative;">aj$a_j$ 不被选。

只考虑树上的答案，限制就变成在树上选择一些点，每个点要么儿子和父亲全被选，自己不选；要么儿子不全被选，自己被选。

显然所有叶子都不能选，从叶子向根依次考虑答案即可。然后图上就只剩下了若干个环，回到了 Solution 1 的第二种情况。

代码是 Solution 1。

Code

const int N=2e5+5;
int flag[N],a[N],n,cnt[N];
queue<int> q;
void dfs(int u)
{
	if(flag[a[u]]==flag[u]) {printf("-1\n");exit(0);}
	else if(flag[a[u]]!=-1) return;
	flag[a[u]]=flag[u]^1;
	dfs(a[u]);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),cnt[a[i]]++;
	for(int i=1;i<=n;i++) flag[i]=-1;
	for(int i=1;i<=n;i++) if(!cnt[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front(); q.pop()，flag[u]=0;
		if(flag[a[u]]==0) {printf("-1\n");return 0;}
		int lst=flag[a[u]]; flag[a[u]]=1;
		if(lst==-1)
		{
			cnt[a[a[u]]]--;
			if(!cnt[a[a[u]]]) q.push(a[a[u]]);
		}
	}
	for(int i=1;i<=n;i++) if(flag[i]==-1) flag[i]=1,dfs(i); 
	int qwq=0;
	for(int i=1;i<=n;i++) if(!flag[i]) qwq++;
	printf("%d\n",qwq);
	for(int i=1;i<=n;i++) if(!flag[i]) printf("%d ",a[i]); 
	cout<return 0;
}

---

D. Lexichromatography

被诈骗了 & 不能觉得不会下分就过完 C 摆烂啊！

Description

给定长度为 n" role="presentation" style="position: relative;">n$n$ 的序列 a" role="presentation" style="position: relative;">a$a$，要求将序列每个位置染成红色或蓝色，且满足以下条件：

• 将染成红色和蓝色的数分别拼成两个序列，蓝色序列的字典序小于红色；
• a" role="presentation" style="position: relative;">a$a$ 的每个子段都满足对于子段内任意的 x" role="presentation" style="position: relative;">x$x$，ai=x" role="presentation" style="position: relative;">ai=x$a_i=x$ 的所有位置 i" role="presentation" style="position: relative;">i$i$ 染成红色和蓝色的数量相差不超过 1" role="presentation" style="position: relative;">1$1$。

求不同的染色方案数，答案对 998244353" role="presentation" style="position: relative;">998244353$998244353$ 取模。n,ai≤2×105" role="presentation" style="position: relative;">n,ai≤2×105$n,a_i\le 2\times {10}^5$。

Solution

有字典序大小的限制是不好计算答案的，但是这条性质是诈骗。对于任意一种两序列不相等的染色方案，我们把红蓝对调一下，发现这两种方案里一定恰好有一个满足字典序的限制。

也就是说在满足第二条限制的情况下，设总染色方案数为 All" role="presentation" style="position: relative;">All$All$，两序列相等的方案数为 cnt" role="presentation" style="position: relative;">cnt$cnt$，则 ans=All−cnt2" role="presentation" style="position: relative;">ans=All−cnt2$ans=\frac{All-cnt}{2}$。

第二条限制实际就是说我们对于每个 x" role="presentation" style="position: relative;">x$x$，把 ai=x" role="presentation" style="position: relative;">ai=x$a_i=x$ 的位置取出来拼成一个序列，序列里相邻的两个数颜色相反。令不同的 ai" role="presentation" style="position: relative;">ai$a_i$ 为 col" role="presentation" style="position: relative;">col$col$，对于每种 ai" role="presentation" style="position: relative;">ai$a_i$ 确定第一个的颜色就可以确定所有，即 All=2col" role="presentation" style="position: relative;">All=2col$All=2^{col}$。

考虑如何求红蓝序列相同的方案数。

首先如果某种 ai" role="presentation" style="position: relative;">ai$a_i$ 出现了奇数次就直接寄了，否则我们把 ai" role="presentation" style="position: relative;">ai$a_i$ 相同的位置从左到右两两分组形成一些线段，限制是每条线段的左右端点不同色。

分类讨论线段 [a,b]" role="presentation" style="position: relative;">[a,b]$[a,b]$ 和 [c,d]" role="presentation" style="position: relative;">[c,d]$[c,d]$ 的位置关系。
如果两条线段没有交集，它们怎么染色互不影响；如果有包含关系，怎么染色都不能让序列相等，令 cnt=0" role="presentation" style="position: relative;">cnt=0$cnt=0$。
否则就是它们有交集的情况，设 a<c<b<d" role="presentation" style="position: relative;">a<c<b<d$a<c<b<d$。那么 a,c" role="presentation" style="position: relative;">a,c$a,c$ 一定同色，b,d" role="presentation" style="position: relative;">b,d$b,d$ 一定同色。

发现我们的限制的形式都是某两点颜色相同 / 相反，使用形如食物链一题的扩展域并查集维护。那么设连通块个数为 block" role="presentation" style="position: relative;">block$block$，则 cnt=2block" role="presentation" style="position: relative;">cnt=2block$cnt=2^{block}$。

实现上，我们对每个线段不用向所有与它有交的线段连边。因为两个与它有交的线段之间也有交，它们一定之前已经连通。所以在其中随便找一个连即可，这样时间复杂度就对了，为 O(nlog⁡n)" role="presentation" style="position: relative;">O(nlogn)$O(n\log n)$。

Code

#define int long long 
const int N=4e5+5,mod=998244353;
const int inv2=((mod+1)>>1);
int n,a[N];
int lst[N],tot[N],fa[N];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
    if(find(x)==find(y)) return;
    fa[find(x)]=find(y);
}
struct node{int l,r;} e[N];
vector<int> t[N];
int cnt,all=1,ans=1,b[N];
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=b[i]=read();
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    for(int i=1;i<=(n<<1);i++) fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        if(lst[a[i]])
        {
            merge(lst[a[i]],i+n),merge(lst[a[i]]+n,i);
            if(tot[a[i]]&1) e[++cnt]={lst[a[i]],i};
        }
        tot[a[i]]++,lst[a[i]]=i;
    }
    for(int i=1;i<=cnt;i++) t[e[i].l].push_back(e[i].r);
    for(int i=1;i<=n;i++) if(tot[i]) all=all*2%mod;
    for(int i=1;i<=n;i++) if(tot[i]&1) {printf("%lld\n",all*inv2%mod);return 0;}
    set<int> s;
    for(int i=1;i<=n;i++)
    {
        for(auto j:t[i])    
        {
            if(s.upper_bound(j)!=s.end()) {printf("%lld\n",all*inv2%mod);return 0;}
            if(!s.empty())
            {
                int r=*s.begin();
                merge(j,r),merge(j+n,r+n);
            }
            s.insert(j);
        }
        s.erase(i);
    }
    for(int i=1;i<=n;i++) if(find(i)==i) ans=(ans<<1)%mod;
    ans=(all-ans+mod)%mod*((mod+1)/2)%mod;
    printf("%lld\n",ans);
    return 0;
}

---

E. Ball-Stackable

Description

给你一棵 n" role="presentation" style="position: relative;">n$n$ 个点的树，其中有一些边方向给定，剩下的边由你来决定方向。同时你要给每条边染一个颜色。

现在有一个人在树上走，他有一个栈，当他经过一条边时会进行如下操作：

• 如果他走的方向与边的方向相同，往栈里放一个与该边颜色相同的球。
• 如果他走的方向与边的方向相反，从栈顶取出一个球丢掉。

一个路径合法当且仅当每次走相反的边之前栈都不为空。

你构造的方案要满足对于任意合法路径，每次走反向边时取出的球都恰好与该边颜色相同。在此基础上使边的颜色数最多，并输出方案，无解输出 -1。

n≤105" role="presentation" style="position: relative;">n≤105$n\le {10}^5$。

Solution

首先让所有边都是一个颜色肯定是符合条件的，不可能无解。

考虑什么样的东西会对总颜色数产生限制，手玩样例可以发现如果一个点有很多条入边，那么这些入边的颜色必须都相同(否则从一个走向另一个就会没有对应颜色的球)。我们定向的时候希望这样的点尽量少。

知道这一点，如果没有已经定向的边就好做了，我们选一个根把树定向成外向树，那么没有点入度大于 1" role="presentation" style="position: relative;">1$1$，颜色数可以达到 n−1" role="presentation" style="position: relative;">n−1$n-1$。

对于有定向边的情况，假设已经确定了根，那么我们把未定向的边按外向树方向定向。这时树中会出现一些反向边。
那么对于任意从根出发的路径，走一个反向边之前栈顶的球颜色都是确定的，维护从根直着走下来的栈顶颜色，把它设为该颜色即可。证明很简单，因为如果中间走过别的子树肯定是每条边正反走两遍，贡献会在出子树时都退掉。

使用换根 dp 求出每个点作为根的答案即可。

对于每次栈不能为空的限制，我们考虑如果当前根是 rt" role="presentation" style="position: relative;">rt$rt$，不合法的点是 x" role="presentation" style="position: relative;">x$x$。不合法代表这条路径上反向边比正向边多，那么把根换成 x" role="presentation" style="position: relative;">x$x$ 只会取反 rt→x" role="presentation" style="position: relative;">rt→x$rt\to x$ 路径上的所有边，一定可以使路径合法，且答案更优。所以我们找到的最优答案所在的根一定满足栈不为空的限制条件。

Code

const int N=1e5+5;
int n;
struct edge{int nxt,to,w;} e[N<<1];
int head[N],cnt,col;
il void add(int u,int v,int w) {e[++cnt]={head[u],v,w};head[u]=cnt;}
int f[N],mx,rt;
void dfs1(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nxt)
        if(e[i].to^fa) f[1]+=(e[i].w!=-1),dfs1(e[i].to,u);
}
void dfs2(int u,int fa)
{
    if(f[u]>mx) mx=f[u],rt=u;
    for(int i=head[u];i;i=e[i].nxt)
        if(e[i].to^fa) f[e[i].to]=f[u]-e[i].w,dfs2(e[i].to,u);
}
vector<int> q;
void dfs3(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to,c=0; if(v==fa) continue;
        if(e[i].w==-1) printf("%d %d %d\n",v,u,c=q[q.size()-1]),q.pop_back();
        else printf("%d %d %d\n",u,v,++col),q.push_back(col);
        dfs3(v,u);
        if(e[i].w==-1) q.push_back(c); else q.pop_back();
    }
}
int main()
{
    n=read();
    for(int i=1;i
    {
        int u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,-w);
    }
    dfs1(1,0),dfs2(1,0); printf("%d\n",mx);
    dfs3(rt,0);
    return 0;
}

F/G

没有官方题解。没有洛谷题解。咕。