Codeforces Round 911 (Div. 2)（C dp D gcd 分解+容斥 E tarjan+dp）

A.手玩题：

可以通过最后一个样例，如果是长度为3的连续O，直接在两边放就行，然后一直用中间的水填到其他地方

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod= 998244353;
#define int long long
int n,m,k;void solve()
{cin>>n;string s;cin>>s;s="?"+s;int res=0;int now=0;s+="#";for(int i=1;i<=n+1;i++){if(s[i]=='#'){if(now>=3){cout<<2<<"\n";return ;}res+=min(2ll,now);now=0;}else now++;}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

B：

直接每个数字都去判定能不能成为最后一个

假设都变成 a

然后目标变成 让 b c的数量相同

假设只操作b c，那么他们的差都减一，差奇偶性不变

如果操作a c或者a b，那么他们的差还是不变，因为-b -a ,+c,差变化2

所以如果差是奇数没法操作，

再想一下，那么对a的数量有没有啥要求呢

可以发现没要求，

因为b c可以操作自己变出一个a，然后再用 a去操作自己，他们可以独立自主

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod= 998244353;
#define int long long
int n,m,k;void solve()
{int a,b,c;auto ok=[&](int a,int b,int c){int need=abs(b-c);if(need%2==0) return true;return false;};cin>>a>>b>>c;if(ok(a,b,c)) cout<<"1 ";else cout<<"0 "; if(ok(b,a,c)) cout<<"1 ";else cout<<"0 "; if(ok(c,a,b)) cout<<"1 ";else cout<<"0 "; cout<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

C：

感觉很裸的dp

dp状态：通过u这个子树到达叶子节点的最少次数

那么如果是叶子节点无需代价

如果不是叶子节点，判断走的左右子树的方向和当前根方向是否相同，不同代价+1

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod= 998244353;
#define int long long
typedef long long LL;
typedef pair<int, char> PII;int n,m,k;
string s;
vector<PII> g[N];
int f[N];
void dfs(int u){//if(s[u]=='U') f[u]=1;if(g[u].empty()){f[u]=0;return ;}for(auto [v,w]:g[u]){dfs(v);f[u]=min(f[u],f[v]+(w!=s[u]));}
}
void solve()
{cin>>n>>s;s="?"+s;for(int i=1;i<=n;i++){g[i].clear();f[i]=2e18;}for(int i=1;i<=n;i++){int a,b;cin>>a>>b;if(a) g[i].emplace_back(a,'L');if(b) g[i].emplace_back(b,'R');}dfs(1);cout<<f[1]<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

D：

首先先排序，排序不影响答案

然后问题变成了

当前数（a[i]和前面数的gcd之和）*后面的个数（就是k嘛）

然后难点是前面

我们可以分开求a[x]的因数的贡献，

通过一个调和级数求1到10w的每个数的因子（不是质因子哦，而是因子，比如16的因子有1 2 4 8 16）

然后a[i]和前面数因子的贡献计算

这里举例说明一下

假设

a[i]=20 a[j]=4

a[i]的因子有 1 2 4 510 20 

a[j]因子有 1 2 4

那么他们gcd的贡献是gcd(20,4)=4

直接求他们里面最大的共同的的因子不好求（n^2超时间嘛）

但是我们知道每个数的因子最多就128个？ n*128够了

然后我们可以求当前数的当前因子能和前面数的因子的总贡献

比如上面例子的1和1配对 2和2配对 4和4配对

但是注意到我们贡献其实只有一个4

那么咋办呢可以用容斥来解决

4的因子里面有2 1

2的因子有1

1的因子只有自己

所以我们求完后还要减去这个因子的倍数

设当前数组f[x]表示因子x有多少个（i，j）的对数

根据上面那个例子a[i]=20 a[j]=4

f[4]=1 f[2]=1 f[1]=1（因为只有两个数嘛，所以只有一对）

然后计算完这个f数组，我们要用容斥减去当前x的倍数的对数

比如上面例子的f[2]要减去f[4]  f[1]要减去f[1]减去f[2]减去f[4]（这里的f[2]要先减去f[4]哦）

然后当前f[x]数组就是名副其实的因子是x的对数

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,mod= 998244353;
#define int long long
typedef long long LL;
typedef pair<int, char> PII;int n,m,k;
int a[N];
vector<int> g[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
void init(){for(int i=1;i<N;i++){for(int j=i;j<N;j+=i){g[j].push_back(i);}}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);vector<int> c(N),f(N);for(int i=1;i<=n;i++){for(auto x:g[a[i]]){f[x]+=c[x]*(n-i);c[x]++;}}int res=0;for(int i=100000;i>=1;i--){for(int j=i+i;j<=100000;j+=i){f[i]-=f[j];}res+=f[i]*i;}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;init();cin>>t;while(t--) solve();
}

E：

手完可以发现如果是强联通分量最后会变成一个有向完全图

代表着如果进来了，因为要求路径最长，所以这个强联通分量的点都要走一遍且保证点不重复，

然后直接dp一下即可

然后因为是拓扑序大的 scc_cnt小，因为tarjan是先到底部的，底部的点会先缩，再回溯到上面缩，所以dp直接从1开始即可

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod= 998244353;
#define int long long
typedef long long LL;
typedef pair<int, char> PII;int n,m,k;vector<int> g[N],h[N];
int dfn[N],low[N];
int scc_cnt,timestamp;
int stk[N],id[N];
bool in_stk[N];
int sz[N];
int top;
stack<int> s;
int b[N],a[N],c[N],f[N],gg[N];
void tarjan(int u){dfn[u] = low[u] = ++ timestamp;stk[ ++ top] = u, in_stk[u] = true;for (auto j:g[u]){if (!dfn[j]){tarjan(j);low[u] = min(low[u], low[j]);}else if (in_stk[j]) low[u] = min(low[u], dfn[j]);}if (dfn[u] == low[u]){++ scc_cnt;int y;do {y = stk[top -- ];in_stk[y] = false;id[y] = scc_cnt;} while (y != u);}}
void solve()
{cin>>n>>m;scc_cnt=timestamp=top=0;for(int i=0;i<=n;i++){g[i].clear();dfn[i]=low[i]=0;in_stk[i]=false;h[i].clear();id[i]=b[i]=c[i]=0;f[i]=gg[i]=0;}for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){int a,b;cin>>a>>b;g[a].push_back(b);}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int i=1;i<=n;i++){b[id[i]]+=a[i];c[id[i]]++;}for(int u=1;u<=n;u++){//cout<<id[u]<<" ";for(auto v:g[u]){if(id[u]!=id[v]){h[id[u]].push_back(id[v]);}}}int ans1=0,ans2;for(int i=1;i<=scc_cnt;i++){f[i]=c[i],gg[i]=b[i];for(auto j:h[i]){int t1=f[j]+c[i],t2=gg[j]+b[i];if(t1>f[i]||t1==f[i]&&t2<gg[i]){f[i]=t1,gg[i]=t2;}}if (f[i] > ans1 || f[i] == ans1 && gg[i] < ans2) ans1 = f[i], ans2 = gg[i];}cout<<ans1<<" "<<ans2<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}