总结
今天这把多校应该是这个暑假打的最爽的一把多校了（虽然排名不是很高），开局队友发现树形dp签到题1009，我想了想猜了个”找子节点为偶数的边“，我盯着队友写了十几分钟一发A了，然后我们又去看1003，队友跟我说完题之后我猜了个贪心结论“第一个是顶或者底扫两次”，队友2想了想觉得没啥问题就跑去写了，我和队友1去看1009的小博弈论，在博弈了几次之后我们得出了个假结论，直接莽了一发wa，这时队友2写完1003，跑过来跟我们一起hack之前的假结论，我推了一会发现狡猾的Bob可以每次多给自己预留一个位置，队友2得到hack样例直接开写，最后因为一些小细节t了2发（我让他检查他不检查）后ac了，接着我们又一起看1001，队友1看了一会说是网络流，作为图论选手的我一开始并没有马上想出怎么建图，但队友说完网络流之后直接给我造了个样例就跑了，我只能埋头苦想，想了一会之后发现好像是一个有源汇上下界网络流问题，在调出板子建好图跑完样例之后，又把队友之前造的样例跑了，过了队友的样例后我直接提交ac了。此时两个队友已经对着1004捣鼓了一个多小时了，我遂加入讨论，经过我们自己造的数据多次（长达两个多小时）与暴力对拍后，我们推出了一个自我感觉非常对的式子，写好后交结果显示tle（这题卡cin），遂改来改去，最后我发现队友因为换成scanf后没开long long导致有个地方爆int，改了之后终于通过了。
题解
1007 - Even Tree Split
题意：
给你一个 n n n 节点的树（ n n n是偶数），你可以从树中删除至少一条边，使得删除后各个连通块节点的个数为偶数，问有多少种删除方案。答案对 998244353 998244353 998244353 取模。
做法：
由观察我们可以知道，包含一条边所连的点在内的子树节点个数为偶数是，这条边是可删边，我们可以用 d f s dfs dfs 找出所有的这些边，答案即为 2 n u m − 1 2^{num}-1 2num−1
代码：
/*
author:wuzx
*/
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
const int mod = 998244353;
int n,m,k;long long POW(long long a,long long b,long long p)
{
a%=p;
long long res=1;
while(b){
if(b&1)
res=res*a%p;
a=a*a%p;
b=b>>1;
}
return res%p;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
vector<vector<int>> g(n);
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
u--;v--;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vector<int> vis(n,0);
int ans=0;
function<int(int)> dfs = [&](int now)
{
int num = 1;
vis[now]=1;
for(auto x:g[now])
{
if(!vis[x])
{
int son = dfs(x);
if(son%2==0)
ans++;
num+=son;
}
}
return num;
};
dfs(1);
cout<<POW(2,ans,mod)-1<<endl;
}
return 0;
}
1003 - Wavy Tree
题意：
给你一个长度为 n n n 的数组，你可以对数组中任一一个元素进行+1/-1的操作，问至少要做多少次操作才能使数组变成波浪数组，波浪数组，即对于每一个数 i i i 都有 a [ i ] < m i n ( a [ i − 1 ] , a [ i + 1 ] ) a[i]<min(a[i-1],a[i+1]) a[i]<min(a[i−1],a[i+1]) 或 a [ i ] > m a x ( a [ i + 1 ] , a [ i − 1 ] ) a[i]>max(a[i+1],a[i-1]) a[i]>max(a[i+1],a[i−1])
做法：
贪心，我们假设第一个元素为波浪的顶峰或低谷，直接扫两遍去最小值即可
代码：
/*
author:wuzx
*/
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
vector<int> a(n),b(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
}
int cnt1=0,cnt2=0;
for(int i=1;i<n;i++)
{
if(i%2==0)
{
if(a[i]>=a[i-1])
{
cnt1+=a[i]-a[i-1]+1;
a[i]=a[i-1]-1;
}
if(b[i]<=b[i-1])
{
cnt2+=b[i-1]-b[i]+1;
b[i]=b[i-1]+1;
}
}
else
{
if(a[i]<=a[i-1])
{
cnt1+=a[i-1]-a[i]+1;
a[i]=a[i-1]+1;
}
if(b[i]>=b[i-1])
{
cnt2+=b[i]-b[i-1]+1;
b[i]=b[i-1]-1;
}
}
}
cout<<min(cnt1,cnt2)<<endl;
}
return 0;
}
1001 - Winner Prediction
题意：
有 n n n 个人在打比赛，现在已经有 m 1 m1 m1 场比赛胜负已定， 有 m 2 m2 m2 场比赛胜负未知，一个人获得冠军的条件是没有人赢得比赛的次数大于他，问 1 1 1 号选手是否有可能赢得冠军
做法：
我们可以先将 m 2 m2 m2 场比赛中有 1 1 1 号选手的比赛判 1 1 1 号赢，然后将剩下的胜负未知的比赛建图跑有源汇上下界网络流。
我们知道，如果 1 1 1 号选手想要获得冠军，那么其他选手的胜利次数是不能大于 1 1 1 号选手的胜利次数的，因此我们可以对每个胜负未定的比赛 ( u , v ) (u,v) (u,v) 建这么一个图，源点S向v连一条下界为 0 0 0，上界为 n u m [ 1 ] − n u m [ v ] num[1]-num[v] num[1]−num[v] 的边， u , v u,v u,v 分别向比赛 i ( g a m e i ) i\space (gamei) i (gamei) 连一条下界为 0 0 0 ，上界为 1 1 1 的边，比赛 i ( g a m e i ) i\space (gamei) i (gamei) 再向汇点连一条上下界均为 1 1 1 的边（这样我们就可以保证每个比赛都有一个人获胜），最后我们再源点S向u连一条下界为 0 0 0 ，上界为 n u m [ 1 ] − n u m [ i ] ( 2 ≤ i ≤ n ) num[1]-num[i](2\le i\le n) num[1]−num[i](2≤i≤n) 的边（这条边保证了把剩余比赛比完之后每个人的获胜次数都不会大于 1 1 1 号选手）
建好图后，我们对这个图跑一个有源汇上下界可行流判断是否有可行流即可。
代码：
/*
author:wuzx
*/
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
struct dinic{
const int nn;
int INF = inf*inf;
struct Edge{
int to,cap,flow;
Edge(int to,int cap,int flow):to(to),cap(cap),flow(flow){}
};
vector<int> dis,cur;
vector<Edge> e;
vector<vector<int>> g;
dinic(int n1):nn(n1),dis(n1+1),cur(n1+1),g(n1+1){}
void add(int u,int v,int w)
{
g[u].emplace_back((int)e.size());
e.emplace_back(v,w,0);
g[v].emplace_back((int)e.size());
e.emplace_back(u,0,0);
}
void add1(int u,int v,int w)
{
g[u].emplace_back((int)e.size());
e.emplace_back(v,w,0);
}
bool bfs(int st,int end)
{
fill(dis.begin(),dis.end(),-1);
dis[st]=0;
queue<int> q;
q.push(st);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i:g[u])
{
// auto [v,w,fo]=e[i];
int v=e[i].to,w=e[i].cap,fo=e[i].flow;
// tie(v,w,fo)=e[i];
if(dis[v]==-1&&w>0)
{
q.push(v);
dis[v]=dis[u]+1;
}
}
}
return dis[end]!=-1;//若不可以到终点（起点）就返回false
}
int dfs(int st,int end,int flo)//dfs就是求节点u在残量为flo时的最大增量
{
if(st==end)
return flo;
int delta=flo;
for(int i=cur[st];i<(int)g[st].size();i++)
{
int j=g[st][i];
// auto [v,w,fo]=e[j];
int v=e[j].to,w=e[j].cap,fo=e[j].flow;
cur[st]++;
if((dis[v]==dis[st]+1)&&w>0)
{
int d=dfs(v,end,min(delta,w));
e[j].cap-=d;
e[j^1].cap+=d;
e[j].flow+=d;
e[j^1].flow-=d;
delta-=d;
if(delta==0)
break;
}
}
return flo-delta;
}
int max_flow(int st,int end)
{
int maxflow=0;
while(bfs(st,end))
{
fill(cur.begin(),cur.end(),0);
maxflow+=dfs(st,end,INF);
}
return maxflow;
}
};
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
int m1,m2,u,v,z;
while(t--)
{
cin>>n>>m1>>m2;
vector<int> num(n+1);
for(int i=1;i<=m1;i++)
{
cin>>u>>v>>z;
if(z==1)
num[u]++;
else
num[v]++;
}
int st1=n+m2+1,end1=n+m2+2;
int st=n+m2+3,end=n+m2+4;
dinic solve(n+m2+10);
vector<int> sum(n+m2+10);
auto ad1 = [&](int u,int v,int w,int low)
{
solve.add(u,v,w);
sum[u]-=low;
sum[v]+=low;
};
for(int i=1;i<=m2;i++)
{
cin>>u>>v;
if(u==1||v==1)
num[1]++;
else
{
ad1(u+m2,i,1,0);
ad1(v+m2,i,1,0);
ad1(i,end1,1,1);
}
}
if(num[1]<*max_element(num.begin(),num.end()))
{
cout<<"NO"<<endl;
continue;
}
for(int i=2;i<=n;i++)
ad1(st1,i+m2,num[1]-num[i],0);
ad1(end1,st1,inf,0);
int tot=0;
for(int i=1;i<=n+m2+2;i++)
{
if(sum[i]<0)
solve.add(i,end,-sum[i]);
else
{
solve.add(st,i,sum[i]);
tot+=sum[i];
}
}
int flow = solve.max_flow(st,end);
if(flow!=tot)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
return 0;
}
1009 - Painting Game
题意：
给一个 1 × n 1\times n 1×n 的网格，Alice 和 Bob 轮流给一个网格涂成黑色，要求不能在已经涂成黑色的网格旁涂色，Alice 想最小化黑色网格数量，Bob想最大化黑色网格数量，给出 n n n 和先手的人，输出黑色网格数量。
做法：
通过模拟他俩的博弈可以知道，每七个网格都会有三个被涂成黑色，因此我们可以先对答案进行 a n s + = ( n / 7 ) ∗ 3 , n % = 7 ans+=(n/7)*3\space ,n\%=7 ans+=(n/7)∗3 ,n%=7 再对剩余的 n n n 进行特判即可。
代码：
/*
author:wuzx
*/
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
vector<int> a(7),b(7);
a[1]=a[2]=a[3]=1;a[4]=2;
b[1]=b[2]=1;b[3]=b[4]=2;
for(int i=5;i<=6;i++)
{
a[i]=b[i-3]+1;
b[i]=a[i-4]+2;
}
cin>>t;
while(t--)
{
string ss;
cin>>n>>ss;
int ans=n/7*3;
n%=7;
if(ss[0]=='A')
ans+=a[n];
else
ans+=b[n];
cout<<ans<<endl;
}
return 0;
}