Niuke Practice 101

C Reasoning clown

The question ：
The length is $n(1\le n\le 10^5)$ Sequence $a(0\le a_i\le 2^{31})$, Satisfy $a_i<a_{i+1}$
Find the smallest $x$, Satisfy $a_i\&x<a_{i+1}\&x$
Ideas ：
For the answer $x$, Greedy from high to low to judge whether everyone can be $0$
Typical wrong thinking ： If you will $x$ Someone becomes $0$ It was found that the monotonicity requirements could not be met , Directly think $x$ This bit cannot be $0$, Time complexity $O(n\log n)$
In fact, it is judged that $i$ Whether a is $0$ when , It should be used extra $O(n\log n)$ Time to judge the rest $i-1$ Bits and already handled $31-i$ Can bits satisfy monotony , If yes, it is $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);
}

D Capital of crime

The question ：
$n(1\le n\le 10^5)$ A little bit $m$ Undirected connected graph of strip edge , Give directions to the edges on the graph , Make each point from $i$ Start at least move $f_i$ Time
Ideas ：
If $m>n-1$ Then there must be a ring , Just connect on the ring , The rest points to the ring , There are unlimited ways to move
Otherwise it will be a tree , Consider the tree shape $dp$,$d{p}_i\ge 0$ Said to $i$ Under the subtree that is the root, it meets the requirements , And from $i$ Start and walk down $d{p}_i$ Step , if $d{p}_i<0$, Represents that the requirements cannot be met in the subtree , At least move up $|d{p}_i|$ Step can meet the requirements
If the root of the whole tree $d{p}_1<0$ Represents no solution

#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);
    }
}

E There is no water in the city

The question ：
Flood from $1$ set out , At time $t$ The height reached is $n$, stay $n(1\le n\le 3000)$ A little bit $m(1\le m\le 2\ast 10^4)$ In a graph with edges , Each two-way side has a height , When the flood reaches any city on both sides , And the height is greater than the edge , Will inundate another city , The flood height will stop before reaching the height that just submerges all cities , Now you can operate any edge once to increase its height by one , Ask how many times you can operate at least without flooding $n$ spot
Ideas ：
Build a tree through the minimum spanning tree , We can know the minimum height of flooding the whole map , Then just put all $1$ To $m$ The minimum edge on the path can be raised , The minimum cut can be achieved

#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);
}