杭州多校2023“钉耙编程”中国大学生算法设计超级联赛（4）

1003	Simple Set Problem

首先将元素的值 x 以及所属集合的编号 y 作为二元组 (x,y) 存入数组，然后按照 x 升序排列，
之后使用双指针扫描数组（尺取法），当区间内出现了所有编号时更新答案的最小值，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <tuple>
#include<functional>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
int n,k,m;
int a[N];
void solve()
{cin>>n;vector<PII> a;for(int i=1;i<=n;i++){int cnt;cin>>cnt;for(int j=1;j<=cnt;j++){int x;cin>>x;a.push_back({x,i});}}sort(a.begin(),a.end());int res=2e18;int l=0,r=0;vector<int> cnt(n+10,0);int now=0;m=a.size();while(r<m){if(cnt[a[r].second]==0) now++;cnt[a[r].second]++;while(now>=n){if(cnt[a[l].second]-1==0){break;}    cnt[a[l].second]--;l++;}if(now==n){res=min(res,a[r].first-a[l].first);}r++;}cout<<res<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();}

1009

WO MEI K

k=2，相当于所有两个不同的点之间只出现过一条边的个数的和,可以考虑每条边的贡献，答案就是所有边的贡献的和,

大于2的时候只是乘上C(N-2,K-2)而已，因为求得是期望最后除上总数C（N,K）即可

所以问题就变成当k=2的时候如何求每个边的贡献和

首先因为是树,n点n-1边，我们可以把u-v的边，当成是v点的权值，把边权变成点权，

然后问题就可以转换成计算每个点不重复的情况下的贡献总和

我们可以使用树上启发式合并 DSG（英文好像是这样的忘了....）

我们每次把信息合并到父亲节点，且顺便计算子树节点中的贡献

我们需要一个cnt数组记录当前子树而言有多少个点是必定经过C边权的个数

sum数组记录当前子树而言没经过当前节点的边权

V容器是记录当前子树下每个不同权值c的最近儿子节点

 每个合并信息的时候顺便计算出当前子树下面有多少个点的权值和其根节点权值一样，先把子树内的贡献先计算了，其贡献就是sum[v]*(siz[u]-cnt[col[u]]

然后把和根节点权值相同的信息给更新即可

树上启发式合并简单说就是优先遍历轻儿子，最后遍历重儿子，重儿子信息不清空，轻儿子信息清空

dfs0函数就是-1就是清空轻儿子信息，1是合并轻儿子信息

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <tuple>
#include<functional>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
int n,k,m;
int a[N];
int fact[N],infact[N];
int son[N],siz[N],col[N],sum[N];
int tot,ans;
bool vis[N];
int cnt[N];
vector<PII> g[N];
vector<int> V[N];
int qmi(int a, int k, int p)  // 求a^k mod p
{int res = 1 % p;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}
void init(){fact[0]=infact[0]=1;for(int i=1;i<N;i++){fact[i]=(LL)fact[i-1]*i%mod;infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;}
}
int C(int n,int m){if(m<0||n<0||n<m) return 0;return (LL)fact[n] * infact[m] % mod * infact[n - m] % mod;
}
void dfs1(int u,int fa){siz[u]=1;son[u]=0;for(auto [v,w]:g[u]){if(v==fa) continue;dfs1(v,u);siz[u]+=siz[v];col[v]=w;if(siz[v]>siz[son[u]]) son[u]=v;}
}
void dfs0(int u,int fa,int ty){if(ty==-1){V[col[u]].clear();cnt[col[u]]-=sum[u];}else{//col[u]就是fa到u边的权值，把每个边的权值记录下来点if(!vis[u]) V[col[u]].push_back(u);cnt[col[u]]+=sum[u];}for(auto [v,w]:g[u]){if(v==fa) continue;dfs0(v,u,ty);}
}
void dfs2(int u,int fa){for(auto[v,w]:g[u]){if(v==fa||v==son[u]) continue;dfs2(v,u);dfs0(v,u,-1);}if(son[u]) dfs2(son[u],u);for(auto [v,w]:g[u]){if(v==fa||v==son[u]) continue;dfs0(v,u,1);}if(u==1) return ;sum[u]=siz[u]-cnt[col[u]];//sum[u]就是u子树的大小减去子树有多少条边是一样的权值for(auto v:V[col[u]]){vis[v]=true;tot=(tot+sum[v]*(siz[u]-cnt[col[u]]%mod))%mod;}V[col[u]].clear();V[col[u]].push_back(u);cnt[col[u]]=siz[u];
}
void solve()
{cin>>n;ans=tot=0;for(int i=1;i<=n;i++){cnt[i]=0;vis[i]=false;g[i].clear();}for(int i=1;i<n;i++){int x,y,w;cin>>x>>y>>w;g[x].emplace_back(y,w);g[y].emplace_back(x,w);}dfs1(1,0);dfs2(1,0);for(int i=1;i<=n;i++){for(auto v:V[i]){tot=(tot+sum[v]*(n-cnt[i])%mod)%mod;}//n-cnt[i] 就是除了这个子树外的点V[i].clear();}int d=qmi(n-1,mod-2,mod)*qmi(n,mod-2,mod)%mod;for(int i=2;i<=n;i++){int res=d*(i-1)%mod*i%mod*tot%mod;ans^=res;}cout<<ans<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;init();cin>>t;while(t--) solve();}

1011

Circuit

额题目就是个例题，有向图的最小环用弗洛伊德求解即可

把问题分解为一个dp问题，子集就是最大编号使用1，2，3，...，k的点

这些情况的总和相加

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <tuple>
#include<functional>
using namespace std;
const int N = 510,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
int n,k,m;
int sum[N][N];
int dis[N][N];
vector<PII> g1[N],g2[N];void solve()
{cin>>n>>m;int len=2e18;int ans=0;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){dis[i][j]=1e18;if(i==j)    dis[i][j]=0;sum[i][j]=1;}for(int i=1;i<=n;++i)   g1[i].clear(),g2[i].clear();for(int i=1;i<=m;++i){int x,y,w;cin>>x>>y>>w;dis[x][y]=w;    sum[x][y]=1;g1[x].push_back({y,w});g2[y].push_back({x,w});}for(int k=1;k<=n;++k){for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){if(i==k||j==k)    continue;if(dis[i][j]<dis[i][k]+dis[k][j])   continue;if(dis[i][j]>dis[i][k]+dis[k][j])   sum[i][j]=0;dis[i][j]=dis[i][k]+dis[k][j];sum[i][j]=(sum[i][j]+sum[i][k]*sum[k][j]%mod)%mod;}for(auto x:g1[k])for(auto y:g2[k]){if(x.first>k)   continue;if(y.first>k)   continue;int C=dis[x.first][y.first]+x.second+y.second;int S=sum[x.first][y.first];if(C>len)   continue;if(len>C)   ans=0;len=C;  ans=(ans+S)%mod;}}if(len>=1e15)   cout<<"-1 -1\n";else    cout<<len<<" "<<ans<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();}

1012	a-b Problem

首先贪心的想拿走一个石头，等于自己得到ai分，对面失去bi分

所以直接按照ai+bi大小拿即可，每次第一个人能这个总和最大，第二个人拿这个总和最小，我用平衡树来动态查找删除了

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <tuple>
#include<functional>
using namespace std;
const int N = 2e5+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;int n,m,k;
vector<PII>g[N];
PII a[N];
void solve()
{set<PII> st1,st2;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].first>>a[i].second;st1.insert({a[i].first+a[i].second,i});st2.insert({-a[i].second-a[i].first,i});}int res=0;for(int i=1,now=0;i<=n;i++,now^=1){int id=0;if(now==0){auto it=st1.rbegin();id=(*it).second;res+=a[id].first;}else{auto it=st2.begin();id=(*it).second;res-=a[id].second;}st1.erase(st1.lower_bound({a[id].first+a[id].second,id}));st2.erase(st2.lower_bound({-a[id].second-a[id].first,id}));}cout<<res<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();}