Winner Prediction(网络流)
Problem
\(n\)个人进行比赛，赢最多的人获胜，保证一定可以分出胜负，现在已知\(m_1\)场对决结果，还有\(m_2\)场对决结果未知，但知道比赛的两个人是谁，问\(1\)号选手是否可能获得胜利
\(1\le n\le 500\)，\(1\le m_1,m_2\le 1000\)
Solve
首先我们根据\(m_1\)场比赛确定\(1\)号和其他选手已经获胜多少场，然后\(m_2\)场中如果存在\(1\)号选手的比赛就让\(1\)号选手赢，剩下的问题就是如何分配\(m_2\)场不存在\(1\)号选手的比赛的胜负了。其实是一个网络流问题
建图方式
- 源点\(S\)向每一场还未确定胜负的比赛(不包括\(1\)参加的比赛，因为如果有\(1\)参加的比赛肯定默认\(1\)必胜)向连一条流量为\(1\)的边，表示胜场
- 每场比赛(满足上述条件)向两个参赛者连流量为\(1\)的边，表示只能有\(1\)个人获胜
- 每个参赛选手(不包括\(1\)号选手)向汇点连他当前最多可以再获胜多少场并且不超过\(1\)获胜的场的流量的边
Code
#include <bits/stdc++.h>
using namespace std;
const int N=2005,M=4005,INF=1e9;
int S,T,cnt;
int head[N],d[N],cur[N];
struct edges
{
int v,nxt,f;
}e[M*2];
void add(int u,int v,int f)
{
e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=f,head[u]=cnt++;
e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,head[v]=cnt++;
}
bool bfs()
{
memset(d,-1,sizeof d);
queue<int>q;
q.push(S);
d[S]=0,cur[S]=head[S];
while(q.size())
{
int u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].nxt)
{
int v=e[i].v,f=e[i].f;
if(d[v]==-1&&f)
{
d[v]=d[u]+1;
cur[v]=head[v];
if(v==T) return true;
q.push(v);
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=e[i].nxt)
{
cur[u]=i;
int v=e[i].v,f=e[i].f;
if(d[v]==d[u]+1&&f)
{
int t=find(v,min(f,limit-flow));
if(!t) d[v]=-1;
e[i].f-=t,e[i^1].f+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int ans=0,flow;
while(bfs()) while(flow=find(S,INF)) ans+=flow;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--){
memset(head,-1,sizeof head);
memset(cur,0,sizeof cur);
memset(d,0,sizeof d);
cnt=0;
int n,m1,m2;
cin>>n>>m1>>m2;
S=0,T=n+m2+1;
vector<int>s(n+1);
for(int i=1;i<=m1;i++){
int x,y,z;
cin>>x>>y>>z;
if(z==1) s[x]++;
else s[y]++;
}
int rem=0;
for(int i=1;i<=m2;i++){
int u,v;
cin>>u>>v;
if(u>v) swap(u,v);
if(u==1) s[1]++;
else{
rem++;
add(S,n+i,1);
add(n+i,u,1);
add(n+i,v,1);
}
}
bool ok=true;
for(int i=2;i<=n;i++)
if(s[1]<s[i]){
ok=false;
break;
}
if(!ok){
cout<<"NO\n";
}else{
for(int i=2;i<=n;i++)
add(i,T,s[1]-s[i]);
int ans=dinic();
if(ans==rem) cout<<"YES\n";
else cout<<"NO\n";
}
}
return 0;
}
Wavy Tree(差分、贪心)
Problem
给定一个长度为\(n\)的序列\(a\)，问把\(a\)变成$a_1\gt a_2 \lt a_3 \gt a_4 \cdots \(或\)a_1\lt a_2 \gt a_3 \lt a_4 \cdots$这样波浪型的序列的最小代价是多少，代价是每个数字改变的差值绝对值和。
Solve
差分后每个数要满足要求，差分数组一定是正负交替的，所以如果一个数不满足要求，把它变成\(+1\)或\(-1\)是最优的，由于是差分数组，所以第\(i\)项更改，第\(i+1\)项要相反地更改。两种情况都算一遍去最小值即可。
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
auto up_to_down=[&]()->ll{
vector<int>d(n+1);
d[1]=a[1];
for(int i=2;i<=n;i++) d[i]=a[i]-a[i-1];
ll res=0;
for(int i=2;i<=n;i++){
if(i%2==0){
if(d[i]<=0){
res+=(1-d[i]);
d[i+1]-=(1-d[i]);
d[i]=1;
}
}else{
if(d[i]>=0){
res+=(1+d[i]);
d[i+1]+=(1+d[i]);
d[i]=-1;
}
}
}
return res;
};
auto down_to_up=[&]()->ll{
vector<int>d(n+1);
d[1]=a[1];
for(int i=2;i<=n;i++) d[i]=a[i]-a[i-1];
ll res=0;
for(int i=2;i<=n;i++){
if(i%2==0){
if(d[i]>=0){
res+=(1+d[i]);
d[i+1]+=(d[i]+1);
d[i]=-1;
}
}else{
if(d[i]<=0){
res+=(1-d[i]);
d[i+1]-=(1-d[i]);
d[i]=1;
}
}
}
return res;
};
cout<<min(up_to_down(),down_to_up())<<'\n';
}
}
Average Replacement(图论、数学、结论)
Problem
给定一个\(n\)个点\(m\)条边的无向图\(G(V,E)\)，每个点一开始有个初始权值\(a_i\)。可以进行若干次操作，每次对于每个点\(i\)，将其度数变为\(\frac{a_i+\sum_{(i,j)\in E}a_j}{deg_i+1}\)。问经过无穷次操作后，每个点的点权收敛到多少
\(1\le n,m\le 10^5\)
Solve
hit1：处于同一连通块里面的点，最后权值都会变成同一个hit2：记\(deg_i\)表示\(i\)的度数，则每个连通块内\(\sum a_i(deg_i+1)\)是定值
于是对于一个连通块\(G\)，里面每个点的点权最终会收敛于\(\frac{\sum_{u\in V}a_u(deg_u+1)}{\sum_{u\in V}deg_u}\)
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
struct edges{
int v,nxt;
}e[N*2];
int head[N],cnt;
void add(int u,int v){
e[cnt]={v,head[u]},head[u]=cnt++;
e[cnt]={u,head[v]},head[v]=cnt++;
}
ll a[N];
int deg[N];
double res[N];
bool vis[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
cnt=0;
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) vis[i]=0,deg[i]=0,res[i]=0.0,head[i]=-1;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
deg[u]++,deg[v]++;
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
queue<int>q;
vector<int>vec;
ll degsum=0,sum=0;
q.push(i);
vis[i]=1;
while(q.size()){
int u=q.front();
q.pop();
vec.push_back(u);
degsum+=deg[u]+1,sum+=(deg[u]+1)*a[u];
for(int j=head[u];~j;j=e[j].nxt){
int v=e[j].v;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
double ans=1.0*sum/degsum;
for(auto x:vec) res[x]=ans;
}
for(int i=1;i<=n;i++) printf("%.6lf\n",res[i]);
}
return 0;
}
Even Tree Split(计数、DFS)
Problem
给定一棵大小为\(n\)的树，问有多少种断边的方案，使得断边之后每个连通块的的大小是偶数。保证\(n\)是偶数
\(1\le n\le 10^5\)
Solve
从根开始DFS，如果一条边连接着的两个连通块都是偶数大小，那么这条边就可以删掉。而在DFS的时候，如果一个点\(u\)的所在子树的大小是偶数，那么它和父亲的边就可以断开，因为总点数\(n\)也是偶数。假设可以删掉的边的条数是\(m\)，那么答案就是\(2^m-1\)，要除去什么都不删的情况
Code
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int power(int x,int y){
int res=1;
while(y){
if(y&1) res=1LL*res*x%mod;
x=1LL*x*x%mod;
y>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
int n;
cin>>n;
vector<vector<int>>E(n+1);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
E[u].push_back(v);
E[v].push_back(u);
}
int cnt=0;
vector<int>sz(n+1);
auto dfs=[&](auto self,int u,int fa)->void{
sz[u]=1;
for(auto v:E[u]){
if(v==fa) continue;
self(self,v,u);
sz[u]+=sz[v];
}
if(u!=1 && sz[u]%2==0) cnt++;
};
dfs(dfs,1,1);
int ans=(mod-1LL+power(2,cnt))%mod;
cout<<ans<<'\n';
}
}
Painting Game(博弈论)
Problem
水平上有一排长度为\(n\)的格子，初始每个格子的颜色都是白色。\(Alice\)和\(Bob\)轮流操作，每次一个人可以选择一个白色格子染黑，但要保证不能有相邻两个格子的颜色是黑色。现在\(Alice\)希望黑色格子数尽量少，\(Bob\)希望黑色格子数尽量大。有\(q\)次询问，每次给出格子个数和先手的人，问最终的黑色格子数
Solve
- Alice的最优策略是选定连续三个白色并把中间的涂黑
- Bob的最优策略是选定连续的三个白色并把最右边的涂黑
- 设Alice面临的状态是\(f(n)\)，Bob面临的状态是\(g(n)\)。则\(f(n)=g(n-3)+1\)，\(g(n)=f(n-4)+2\)(\(n\ge 7\))
- 前面\(7\)种状态都很容易计算，把上面的再替换一下\(f(n)=g(n-7)+3\)，\(g(n)=f(n-7)+3\)。因此如果\(f(n)=3\times \frac{n}{7}+g(n\%7)\)，\(g(n)\)的计算同理
Code
#include <bits/stdc++.h>
using namespace std;
int a[8],b[8];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
a[1]=a[2]=a[3]=1,a[4]=2; //Alice先手
b[1]=b[2]=1,b[3]=b[4]=2; //Bob先手
for(int i=5;i<=6;i++){
a[i]=b[i-3]+1;
b[i]=a[i-4]+2;
}
cin>>T;
while(T--){
int n;
string s;
cin>>n>>s;
int ans=n/7*3;
n=n%7;
if(s=="Alice"){
ans+=a[n];
}else ans+=b[n];
cout<<ans<<'\n';
}
}