题意：
长度为
n
(
1
≤
n
≤
1
0
5
)
n(1\leq n\leq 10^5)
n(1≤n≤105)的序列
a
(
0
≤
a
i
≤
2
31
)
a(0\le a_i\le 2^{31})
a(0≤ai≤231)，满足
a
i
<
a
i
+
1
a_i<a_{i+1}
ai<ai+1
找到一个最小的
x
x
x，满足
a
i
&
x
<
a
i
+
1
&
x
a_i\&x<a_{i+1}\&x
ai&x<ai+1&x
思路：
对于答案
x
x
x，贪心的从高位到低位判断每一位是否可以为
0
0
0
典型的错误思路：如果将
x
x
x某一位变为
0
0
0后发现无法满足单调性要求，则直接认为
x
x
x该位不能为
0
0
0，时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)
实际上判断第
i
i
i位是否为
0
0
0时，应该额外用
O
(
n
log
n
)
O(n\log n)
O(nlogn)的时间去判断剩下的
i
−
1
i-1
i−1位以及已经处理好的
31
−
i
31-i
31−i位能否有满足单调的情况，如果可以则为
0
0
0。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
ll a[maxn];int n;
bool check(ll p,int num)
{
for(int i=num-1;i>=0;i--)
{
p^=(1ll<<i);
int ok=1;
for(int j=1;j<n;j++)
{
if((a[j]&p)>(a[j+1]&p))
{
ok=0;break;
}
}
if(ok) continue;
p^=(1ll<<i);
}
for(int i=1;i<n;i++)
{
if((a[i]&p)>=(a[i+1]&p))
{
return false;
}
}
return true;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll ans=0;
for(int i=31;i>=0;i--)
{
ll p=ans;
if(check(p,i)) continue;
ans|=(1ll<<i);
}
printf("%lld\n",ans);
}
题意：
n
(
1
≤
n
≤
1
0
5
)
n(1\le n \le 10^5)
n(1≤n≤105)个点
m
m
m条边的无向连通图，给图上的边规定方向，使每个点从
i
i
i出发至少移动
f
i
f_i
fi次
思路：
如果
m
>
n
−
1
m>n-1
m>n−1则一定有环，只需要环上连通，其余点指向环，即可有无限的移动方式
否则为一颗树，考虑树形
d
p
dp
dp，
d
p
i
≥
0
dp_i\ge 0
dpi≥0表示以
i
i
i为根的子树下均满足要求，且从
i
i
i出发向下走能走
d
p
i
dp_i
dpi步，若
d
p
i
<
0
dp_i<0
dpi<0，代表子树内无法满足要求，至少应该向上移动
∣
d
p
i
∣
|dp_i|
∣dpi∣步才可以满足要求
如果整棵树的根
d
p
1
<
0
dp_1<0
dp1<0代表无解
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<cstring>
#include<string>
#include<sstream>
#define fi first
#define gcd __gcd
#define se second
#define pb push_back
#define lowbit(x) x&-x
#define inf 0x3f3f3f3f
#define mem(x,y) memset(x,y,sizeof(x))
#define lrb666 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<int,int> PII;
const int maxn=1e5+7;
int num,head[maxn],n,m,f[maxn],g[maxn],vis[maxn],c[maxn];
struct road{int b,c,nex;}r[4*maxn];
void add(int a,int b,int c){r[num].b=b;r[num].c=c;r[num].nex=head[a];head[a]=num++;}
void dfs1(int u,int fa)
{
g[u]=-f[u];
for(int i=head[u];~i;i=r[i].nex)
{
int v=r[i].b;
if(v==fa) continue;
dfs1(v,u);
if(g[v]<0)
{
r[i].c=1;
if(-g[v]-1>g[u]) g[u]=min(g[u],g[v]+1);
}
else
{
r[i^1].c=1;
if(g[u]+1+g[v]>=0) g[u]=max(g[u],g[v]+1);
}
}
}
int dfs2(int u,int fa)
{
if(vis[u]) return u;vis[u]=1;
for(int i=head[u];~i;i=r[i].nex)
{
int v=r[i].b;
if(v==fa) continue;
int p=dfs2(v,u);
if(p==0) continue;
c[u]=1;r[i^1].c=1;
if(p==u) return -1;
return p;
}
return 0;
}
void dfs3(int u,int fa)
{
if(vis[u]) return; vis[u]=1;
for(int i=head[u];~i;i=r[i].nex)
{
int v=r[i].b;
if(v==fa || c[v]) continue;
r[i].c=1;
dfs3(v,u);
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&f[i]);
for(int i=1;i<=m;i++)
{
int a,b;scanf("%d%d",&a,&b);add(a,b,0);add(b,a,0);
}
if(m==n-1)
{
dfs1(1,-1);
if(g[1]<0)
{
puts("-1");return 0;
}
}
else
{
dfs2(1,-1);
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
if(c[i]) dfs3(i,-1);
}
}
for(int i=0;i<2*m;i+=2)
{
printf("%d",r[i].c);
}
}
题意：
洪水从
1
1
1出发，在时刻为
t
t
t时达到的高度为
n
n
n，在
n
(
1
≤
n
≤
3000
)
n(1\le n\le3000)
n(1≤n≤3000)个点
m
(
1
≤
m
≤
2
∗
1
0
4
)
m(1\le m\le2*10^4)
m(1≤m≤2∗104)条边的图中，每双向条边都有高度，当洪水到达边两侧任何一个城市，且高度大于边时，就会淹没另一个城市，洪水高度会在到达恰好将所有城市淹没的高度前停下来，现在可以给任意一条边操作一次使其高度加一，求最少操作多少次不会淹没
n
n
n点
思路：
通过最小生成树建树，可以得知淹没全图的最小高度，那么只需将所有
1
1
1到
m
m
m路径上的最小边提高即可，最小割即可实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e4+7;
int fa[maxn],num,head[maxn],depth[maxn],now[maxn],s,t;
struct road{int b,c,nex;}r[200005];
void add(int a,int b,int c){r[num].b=b;r[num].c=c;r[num].nex=head[a];head[a]=num++;}
struct node
{
int a,b,c;
}e[maxn];
bool cmp(node a,node b)
{
return a.c<b.c;
}
int find(int x)
{
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
void lianjie(int x,int y)
{
int px=find(x),py=find(y);
fa[px]=py;
}
int make_level()
{
memset(depth,-1,sizeof(depth));
queue<int>q;
q.push(s);
depth[s]=1;
now[s]=head[s];
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];~i;i=r[i].nex)
{
int v=r[i].b;
if(depth[v]!=-1 || r[i].c<=0) continue;
now[v]=head[v];
depth[v]=depth[u]+1;
q.push(v);
}
}
return depth[t]!=-1;
}
int dinic(int u,int flow)
{
if(u==t) return flow;
int sum=0;
for(int i=now[u];~i;i=r[i].nex)
{
now[u]=i;
int v=r[i].b;
if(depth[v]!=depth[u]+1 || r[i].c<=0) continue;
int use=dinic(v,min(flow-sum,r[i].c));
if(use)
{
r[i].c-=use;
r[i^1].c+=use;
sum+=use;
}
if(sum==flow) return flow;
}
if(sum==0) depth[u]=-1;
return sum;
}
signed main()
{
memset(head,-1,sizeof(head));
int n,m;scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&e[i].a,&e[i].b,&e[i].c);
sort(e+1,e+1+m,cmp);
int mx=0;
for(int i=1;i<=m;i++)
{
if(find(e[i].a)==find(e[i].b)) continue;
mx=e[i].c;lianjie(e[i].a,e[i].b);
}
for(int i=1;i<=m;i++)
{
if(e[i].c>=mx) continue;
add(e[i].a,e[i].b,mx-e[i].c);add(e[i].b,e[i].a,mx-e[i].c);
}
s=1,t=n;
int ans=0;
while(make_level()) ans+=dinic(s,1e9);
printf("%lld\n",ans);
}