模拟11 A层联测24
100+0+20+10=130pts rk32
T1 签到题
T2 最大值的最小竟然没想到二分，退役吧。。爆搜所有路径不知道哪写挂了赛后被卡成零蛋。。。
T3 暴力枚举
T4 二维前缀差分暴力
T1 花菖蒲
首先有解一定满足 \(b\le a-2\)。
当 \(b=0\) 时，可以想到构造菊花图。
当 \(b=a-2\) 时，可以想到构造毛毛虫
所以正解就是毛毛虫套菊花图。
需要特盘菊花图的度数正好也为 \(3\) 时，度数为 \(3\) 的点的个数会加一，即 \(b=a-3\) 一定无解。
总点数为 \(a+b+1\)。
T2 百日草
求最大值的最小，明显是二分答案。
那么对于一个确定的答案合法当且仅当对于所有经过的边，需要满足 \(w_i\times dis\le ans\)，其中 \(dis\) 为到 \(1\) 的距离。
那么就只走符合条件的边，看是否能走到 \(n\)，然后是 \(01\) 最短路，直接用 \(bfs\) 求即可。
需要注意：因为会有重边，所以不能在 \(v\) 入队时判断是否访问，而是要在取出队首时判断，复杂度 \(\mathit{\Theta}(n\log V)\)。
T3 紫丁香
很有意思的一道题。这里说说官解做法。
首先有一个结论：若 \(n\) 为偶数，则答案为 \(n\)；若 \(n\) 为奇数，则答案为 \(n-1\)。
证明：
先考虑原图是颗树的情况，我们以任意点为根，那么对于所有非根节点，都有一条从父亲连过来的边，通过决定选（\(0\)）或不选（\(1\)）该父边，来调整该点度数的奇偶性，即若该点加上父边后现在的度数为偶数，则断掉父边，否则保留。
那么只有根节点的奇偶性无法保证。
若 \(n\) 为偶数，则除根节点外有 \(n-1\) 个点的度数已经为奇数，又因为总度数为为偶数（每加一条边都会使总度数加 \(2\)），则根节点的度数也为奇数，所以答案再加 \(1\)，为 \(n\) 。
若 \(n\) 为奇数，则根节点的度数为偶数，答案就是 \(n-1\)。
然后我们考虑加上所有非数边，发现这样只可能影响每个点的初始度数，而我们仍可以通过上述方法构造，即对最后答案没有影响。
证毕。
如果没有要求构造方法这道题就没了，接下来我们考虑如何构造字典序最大的方案。
根据这个结论我们就可以先把原图的所有的非树边全选上，再去和生成树斗智斗勇。为了让字典序尽可能大，我们的生成树选择最大生成树（这里每条边的边权即为该边的编号），这样我们就可以让编号小的点尽可能多的被选，而需要作出决策的点的编号尽可能大。
我们先来考虑对于一个已知的决策，修改（即每条边的选择是 \(0\) 则变为 \(1\)，是 \(1\) 则变为 \(0\)）一条链会改变什么？ 对于链两端的边奇偶性改变，非两端的边奇偶性都不变，这个比较显然。
然后就先 \(dfs\) 一遍从叶子节点往上作出决策（即该点的父边是否需要选择），然后我们发现如果 \(n\) 为偶数，那么我们以任何一点作为根节点遍历得到的决策都是相同的，因为根节点的度数也为奇数，就和其它点一样了，我们不管修改哪一条链，都会产生两个度为偶数的点，这样答案就不优了。所以此时直接输出答案即可。
若 \(n\) 为偶数，则度为偶数的点只有一个，且不一定是钦定的根节点。考虑怎么将该点转移到其他位置来使答案最优。
一个简单的方法就是修改一个点 \(x\) 到根节点的链，这样偶数点就转移到了 \(x\)。
发现只有原来没被选的边才需要修改，所以我们只考虑为 \(0\) 的边。按编号从小到大考虑每一条边，假设我们当前想要修改 \(x\) 的父边，那么该链的端点一定在 \(x\) 的子树内。我们就只在子树内继续考虑下一个修改的边，且该边的编号一定比当前修改的编号大。
那么我们考虑给所有 \(0\) 边建一个树，定义一个虚拟节点 \(rt\)，对于每一个边 \(v\)，找到从它到根路径上第一个编号小于 \(w_v\) 的边（设为 \(u\)），从 \(u\) 向 \(v\) 连一条边，表示以 \(v\) 为端点的链同时还能覆盖 \(u\)。如果找不到则向虚拟节点连边，表示以 \(v\) 为端点的链只能覆盖 \(v\)。
这样我们只需在建好的树上每次选择编号最小的点往下递归，一直到叶子节点，就选出了最优的链顶，最后暴力修改链上的边即可。
“根路径上第一个编号小于 \(w_v\) 的边” 可以线段树二分，以深度为下标，找最靠右的点即可。
然后就做完了。复杂度 \(\mathit{\Theta}(n\log n)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
il int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int inf=1ll<<30;
const int M=6e5+10;
const int V=9e5+10;
int n,m;
struct node{
int u,v,w;
}ee[V];
int fa[M];
int find(int x){
if(x==fa[x])return x;
else return fa[x]=find(fa[x]);
}
struct EDG1{
int v,nxt,w;
}e[M<<1];
int head[M],cnt(0);
il void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int deg[M],ans[V];
void dfs(int x,int fat,int edg){
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].v;
if(y==fat)continue;
dfs(y,x,i);
}
if(!fat)return;
if(deg[x]%2==0){
deg[x]--;
deg[fat]--;
ans[e[edg].w]=0;
}
}
namespace Segment_Tree{
int t[M<<3];
il void push_up(int k){
t[k]=min(t[k<<1],t[k<<1|1]);
}
void build(int k,int l,int r){
if(l==r){
t[k]=inf;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void update(int k,int l,int r,int pos,int val){
if(l==r){
t[k]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)update(k<<1,l,mid,pos,val);
else update(k<<1|1,mid+1,r,pos,val);
push_up(k);
}
int query(int k,int l,int r,int val){
if(l==r)return t[k];
int mid=(l+r)>>1;
if(val>t[k<<1|1])return query(k<<1|1,mid+1,r,val);
else return query(k<<1,l,mid,val);
}
}
int to[V];
int f[M],pos[M],son[V];
void dfs2(int x,int fat,int edg,int dep){
f[x]=fat;
pos[x]=e[edg].w;
son[e[edg].w]=x;
int fm=Segment_Tree::query(1,1,n,e[edg].w);
if(fm==inf)fm=m+1;
if(x!=1&&ans[e[edg].w]==0&&e[edg].w<to[fm])to[fm]=e[edg].w;
if(fat)Segment_Tree::update(1,1,n,dep,e[edg].w);
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].v;
if(y==fat)continue;
dfs2(y,x,i,dep+1);
}
if(fat)Segment_Tree::update(1,1,n,dep,inf);
}
int main(){
freopen("lilac.in","r",stdin);
freopen("lilac.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++)fa[i]=i;
fill(ans+1,ans+1+m,1);
for(int i=1;i<=m;i++){
ee[i].u=read(),ee[i].v=read();
ee[i].u++;
ee[i].v++;
ee[i].w=i;
deg[ee[i].u]++;
deg[ee[i].v]++;
}
int t=0;
for(int i=m;i>=1;i--){
int fx=find(ee[i].u),fy=find(ee[i].v);
if(fx==fy)continue;
fa[fx]=fy;
add(ee[i].u,ee[i].v,ee[i].w);
add(ee[i].v,ee[i].u,ee[i].w);
t++;
if(t==n-1)break;
}
dfs(1,0,0);
if(n%2==0) for(int i=1;i<=m;i++)cout<<ans[i];
else{
Segment_Tree::build(1,1,n);
for(int i=1;i<=m+1;i++)to[i]=inf;
dfs2(1,0,0,1);
int now=m+1;
while(to[now]!=inf) now=to[now];
now=son[now];
while(now){
ans[pos[now]]^=1;
now=f[now];
}
for(int i=1;i<=m;i++)cout<<ans[i];
}
return 0;
}
T4 麒麟草
10pts：
修改的时候二维差分修改，查询的时候二维前缀和查询，复杂度 \(n^2\)。
正解不会，咕。
标签：11,度数,ch,NOIP,ee,偶数,编号,节点,模拟 From： https://www.cnblogs.com/cccomfy/p/17809852.html