POI 2011 切题记

POI 2011 Conspiracy

Description:
有 $n$ 个人,他们当中有些互相认识.现在将他们分成两个部分,第一部分的人必须互相认识,第二部分的人必须互相不认识.求分配的方案数.
$n\le 5000$

Solution:

这一眼看上去就是 $2-sat$ 问题,但常规的 $2-sat$ 问题都是判解或者求一组解.但这题居然求方案数,按理是比较奇葩的,那么此题必然有可解之处.
整理一下思绪:我们可以求一组解,要求方案数.那么我们可不可以将这一组解来稍作修改为其它解呢?
将第一部分的人其中一人去第二部分,若要满足条件,即此人与原来第二部分的人互相不认识.同理,将第二部分的人其中一人去第一部分,即此人与原来第一部分的人互相认识.
进而两个部分的人各交换一人,也是存在的.
那么统计一下可交换的人数,简单的乘积一下即可求出方案.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(a) sizeof(a)
#define mcl(a,b) memset(a,b,Sz(a))
#define mcp(a,b) memcpy(a,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 10005/*2-sat方案数一般只能判定，但此题要统计，那么就有存在规律，发现在一种解下，分三种可以转换成另外一种新的方案1.后勤的一个人->同谋2.同谋的一个人->后勤3.后勤同谋各换一人那么就需要预处理一方去另一方是否满足题意即可 
*/int n;
bool mark[N][N]; int dfn[N],low[N],tim;
int stk[N],top;
int Id[N],tot;
bool vis[N];vector<int>E[N];int kind[N],cnt[N],can[N];void tarjan(int x,int f){dfn[x]=low[x]=++tim;stk[++top]=x;vis[x]=1;bool flag=1;SREP(i,0,E[x].size()){int y=E[x][i];if(flag && y==f){flag=0;continue;}if(!dfn[y]){tarjan(y,x);chkmin(low[x],low[y]);  }else if(vis[y])chkmin(low[x],dfn[y]);}if(dfn[x]==low[x]){++tot;do{Id[stk[top]]=tot;vis[stk[top]]=0;}while(x!=stk[top--]);}
} int main(){scanf("%d",&n);SREP(i,0,n){int k,x;scanf("%d",&k);while(k--)scanf("%d",&x),mark[i][x-1]=mark[x-1][i]=1;}SREP(i,0,n) SREP(j,0,i){int x0=i<<1,x1=i<<1|1;int y0=j<<1,y1=j<<1|1;if(mark[i][j])E[x1].pb(y0),E[y1].pb(x0);else E[x0].pb(y1),E[y0].pb(x1);}SREP(i,0,n<<1) if(!dfn[i]) tarjan(i,-1);bool f=1;SREP(i,0,n) if(Id[i<<1]==Id[i<<1|1]) {f=0;break;} if(!f){puts("0");return 0;}   int sum1=0,sum0=0;SREP(i,0,n){kind[i]=(Id[i<<1]>Id[i<<1|1]);sum1+=(kind[i]);sum0+=(!kind[i]);}SREP(i,0,n) SREP(j,0,n) if(i!=j && kind[i]!=kind[j] && mark[i][j]!=kind[i]) cnt[i]++,can[i]=j;int ans=(sum1&&sum0),cnt1=0,cnt0=0; SREP(i,0,n) {if(!cnt[i]){cnt1+=(kind[i]);cnt0+=(!kind[i]);ans+=(kind[i] && sum1>1);ans+=(!kind[i] && sum0>1);}else if(cnt[i]==1) ans+=(can[can[i]]==i && cnt[can[i]]==1 && i<can[i] || !cnt[can[i]]);}ans+=cnt1*cnt0;printf("%d\n",ans);return 0;
}

POI 2011 Lollipop

Description:
由 $1$ , $2$ 构成的序列 $A$ ,有m个询问,询问是否存在一个区间和为 $q$ .若存在,输出该区间的 $L$ , $R$ ,否则输出”NIE”.
$n,m \le 10^6$

Solution:

实际上一个 $\sum_L^R{Ai}=R-L+1+Cnt$ ,(Cnt为[L,R]中2出现的个数).
那么问题就是如何找到 $[L,R]$ 的 $Cnt=q-(R-L+1)$ ，再接着还有m个询问,我们就只能先预处理所有的 $sum$ 的 $[L,R]$ .
我们可以先找到 $[1,x]$ 的 $sum>q$ ,再然后找到 $pos_1$ 后面第一个 $1$ 和 $pos_x$ 后面第一个 $1$ ，移过去即可或者无解。

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(a) sizeof(a)
#define mcl(a,b) memset(a,b,Sz(a))
#define mcp(a,b) memcpy(a,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 1000005int n,m;
char str[N];int sum[N],cnt[N];
int L[N<<1],R[N<<1];int main(){scanf("%d%d",&n,&m);scanf("%s",str+1);REP(i,1,n)sum[i]=sum[i-1]+(str[i]=='W'?1:2);DREP(i,n,1)cnt[i]=(str[i]=='T'?cnt[i+1]+1:0);REP(i,1,n){L[sum[i]]=1,R[sum[i]]=i;if(str[i]=='T'){if(cnt[1]<cnt[i])L[sum[i]-1]=cnt[1]+2,R[sum[i]-1]=cnt[1]+i;else if(cnt[i]+i<=n)L[sum[i]-1]=cnt[i]+1,R[sum[i]-1]=cnt[i]+i;}}while(m--){int q;scanf("%d",&q);if(!L[q] || q>sum[n])puts("NIE");else printf("%d %d\n",L[q],R[q]);}return 0;
}

POI 2011 Lightning Conductor

Description:
给你一个序列 $A$ ,对于 $i \in [1,n]$ ,找到最小的非负整数p满足再对于 $j\in [1,n]$ , $A_j \le A_i + p - \sqrt{|i-j|}$ .
$n\le 500000 , A_i\le 10^9$

Solution:

首先规定 $j<i$ ,那么不难发现对于每个 $i$ 的 $j$ ,都存在单调决策,即可分治来求解 $p_{max}$ ,同理 $j\ge i$ 时,即序列 $A$ 翻转,再求解一次.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(a) sizeof(a)
#define mcl(a,b) memset(a,b,Sz(a))
#define mcp(a,b) memcpy(a,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 500002int n;
int A[N];
db ans[N];void solve(int L,int R,int l,int r,int op){if(L==R)return; int mid=(L+R)>>1;int m=-1;db mx=-1;REP(i,max(l,mid),r){if(sqrt(i-mid)+A[i]-A[mid]>mx){mx=sqrt(i-mid)+A[i]-A[mid];m=i;}}chkmax(ans[op?n-mid+1:mid],mx);solve(L,mid,l,m,op);solve(mid+1,R,m,r,op);
}int main(){scanf("%d",&n);REP(i,1,n)scanf("%d",&A[i]);solve(1,n,1,n,0);REP(i,1,n/2)swap(A[i],A[n-i+1]);solve(1,n,1,n,1);REP(i,1,n)printf("%d\n",(int)ceil(ans[i]));return 0;
}

POI 2011 Shift

Description:
一个 $1~n$ 的排列.
有 $2$ 种操作:
$a$ .将最后一个数移动到最前面.
$b$ . 将第 $3$ 个数移动到最前面.
我们将连续进行 $k$ 次同一个操作称为“一块操作”,表示为 $ka$ 或 $kb$ .
找到一个操作序列使得进行这些操作后,排列变为 $1,2,3,...,n$ .
若不存在这样的操作序列,输出”NIE DA SIE”,否则输出操作次数 $m$ 以及该操作序列.
$n\le 2000 , m\le n^2$

Solution:

经过不断的模拟…
可以发现这是在一个环上进行旋转和翻转队头的前3个数.
对于旋转操作,即 $a$ 操作,只要计算出需要将队头移动的位数即可.
对于翻转操作,即 $b$ 操作,只要特判翻转 $1$ 个还是 $2$ 个,再进行 $swap$ .
然后再模拟…模拟…发现是有一定的规律的.
我们假设 $1$ ~ $i$ 已经有序,那么我们只能去找 $i+1$ 和 $i+2$ 的位置,仅这 $2$ 个来进行不断的 $a$ 操作和 $1$ ~ $2$ 的 $b$ 操作.
对于无解的情况,必须满足上述操作直到 $n-1$ 和 $n-2$ 为逆序且 $n$ 为奇数时.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(a) sizeof(a)
#define mcl(a,b) memset(a,b,Sz(a))
#define mcp(a,b) memcpy(a,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 2002int n;
int A[N];
int top;
int cnt,ans[N*N];void go_a(int x){if(top==x)return;ans[++cnt]=(top-x+n)%n;top=x;
}void go_b(int x){ans[++cnt]=-x;if(x==1){swap(A[top%n+1],A[(top+1)%n+1]);swap(A[top],A[top%n+1]);}else {swap(A[top],A[top%n+1]);swap(A[top%n+1],A[(top+1)%n+1]);}
}void move(int x,int y){int step=(x-y+n)%n;while(step>1){x=(x-3+n)%n+1;go_a(x),go_b(1);step-=2;}if(step)go_a(y),go_b(2);
}int main(){scanf("%d",&n);REP(i,1,n)scanf("%d",&A[i]);top=1;int k=1;while(k<=n && A[k]!=1)++k;k=k%n+1;SREP(i,2,n-1){int j=1;while(j<=n && A[j]!=i)++j;move(j,k);k=k%n+1;}k=k%n+1;if(A[k]!=n){if(n&1){puts("NIE DA SIE");return 0;}SREP(i,1,n/2){go_a(k);go_b(2);k=(k+1)%n+1;}}REP(i,1,n) if(A[i]==1) {go_a(i);break;}printf("%d\n",cnt);REP(i,1,cnt)printf("%d%c%c",abs(ans[i]),ans[i]>0?'a':'b',i<cnt?' ':'\n');return 0;
}

POI 2011 Plot

(未解决…)
Description:

Solution:

Code:

POI 2011 Strongbox

Description:
$0$ ~ $n-1$ 中某些数是密码.
满足若 $a$ , $b$ 为密码,则 $(a+b)%n$ 也是密码.
已知 $k-1$ 个非密码的数和 $1$ 个是密码的数.
$k\le 250000 , k\le n \le 10^{14}$

Solution:

通过模拟,不难发现若 $a$ , $b$ 为密码,则在模数 $n$ 下 $gcd(a,b)$ 的倍数的数都为密码.
相反,若 $a$ , $b$ 不为密码,则在模数 $n$ 下 $gcd(a,b)$ 的倍数的数都不为密码.
那么就是求已知x,也就是求最小的y|n且y|x，使得不存在y的倍数不是密码.答案即是n/y.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 250002ll n,A[N],Q[N];
int m,cnt,top;ll gcd(ll x,ll y){return(y)?gcd(y,x%y):x;}bool check(ll x){DREP(i,cnt,1)if(!(A[i]%x))return 0;return 1;
}int main(){scanf("%lld%d",&n,&m);REP(i,1,m)scanf("%lld",&A[i]),A[i]=gcd(A[i],n);sort(A+1,A+m);cnt=unique(A+1,A+m)-A-1;//优化,去重 ll ans=0;for(int i=1;1ll*i*i<=A[m];++i)if(!(A[m]%i)){if(check(i)){ans=n/i;break;}if(1ll*i*i<A[m])Q[++top]=A[m]/i;}if(!ans)while(top){if(check(Q[top])){ans=n/Q[top];break;}--top;}printf("%lld\n",ans);return 0;
}

POI 2011 Difference

Description:
在长度为 $n$ 的字符串中,求一个区间(出现最多的字符数-出现最少的字符数)的最大值.
$n\le 10^6$

Solution:
(待更新)

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 1000002
#define M 28int n;
char str[N];
int sum[M],dt[M][M];
int f1[M][M],f2[M][M],g1[M][M],g2[M][M];int main(){
    scanf("%d",&n);
    scanf("%s",str+1);    mcl(f2,INF);
    int ans=0;    REP(i,1,n){
        int k=str[i]-'a';
        ++sum[k];
        SREP(j,0,M-2){
            if(j==k)continue;
            dt[k][j]++,dt[j][k]--;            if(g1[k][j]!=sum[j]) chkmax(ans,dt[k][j]-f1[k][j]);
            else chkmax(ans,dt[k][j]-f2[k][j]);
            if(g1[j][k]!=sum[k]) chkmax(ans,dt[j][k]-f1[j][k]);
            else chkmax(ans,dt[j][k]-f2[j][k]);            if(f2[k][j]>dt[k][j] && g1[k][j]!=sum[j]){
                f2[k][j]=dt[k][j];
                g2[k][j]=sum[j];
            }
            if(dt[j][k]<f1[j][k]){
                if(g1[j][k]==sum[k]) f1[j][k]=dt[j][k];
                else {
                    f2[j][k]=f1[j][k];
                    g2[j][k]=g1[j][k];
                    f1[j][k]=dt[j][k];
                    g1[j][k]=sum[k];
                }
            }
            else if(dt[j][k]<f2[j][k] && g1[j][k]!=sum[k]){
                f2[j][k]=dt[j][k];
                g2[j][k]=sum[k];
            }
        }   
    }    printf("%d\n",ans);    return 0;
}

POI 2011 Garbage

Description:
给你一个 $n$ 个点, $m$ 条边的仅存在简单环的图.每条边都有初始状态和目标状态.经过每条边都会翻转改该边的状态.求用最少的简单环使图的每条边都变为目标状态.若无解,输出 $NIE$
$n \le 10^5 , m \le 10^6$

Solution:

对于每条边,我们只关心初始状态与目标状态不同的边,即存下这些边.
因为仅用简单环.即跑欧拉回路
对于无解的情况,即欧拉回路的判定——度数都为偶数.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 100002
#define M 1000002int n,m;int ans;
vector<int>G[M];
int degree[N];
bool mark[M<<1],vis[N];int qwq,head[N<<1];
struct edge{int to,nxt;
}E[M<<1];
void addedge(int x,int y){E[qwq]=(edge){y,head[x]};head[x]=qwq++;degree[x]++;}int dfs(int x){vis[x]=1;for(int &i=head[x];~i;i=E[i].nxt) if(!mark[i]){int y=E[i].to;mark[i]=mark[i^1]=1;if (vis[y]){G[++ans].pb(y);G[ans].pb(x);vis[x]=0;return y;} else{int z=dfs(y);G[ans].pb(x);if(x!=z){vis[x]=0;return z;}}}vis[x]=0;return 0;
} int main(){qwq=0;mcl(head,-1);scanf("%d%d",&n,&m);REP(i,1,m){int a,b,s,t;scanf("%d%d%d%d",&a,&b,&s,&t);if(s^t)addedge(a,b),addedge(b,a);}REP(i,1,n) if(degree[i]&1){puts("NIE");return 0;}REP(i,1,n) if(head[i]) dfs(i);printf("%d\n",ans);REP(i,1,ans) {printf("%d ",G[i].size()-1);SREP(j,0,G[i].size()) printf("%d ",G[i][j]);puts("");}return 0;
}

POI 2011 Tree Rotations

Description:
给你一棵树,它的非叶子节点都有 $2$ 个儿子,共有 $n$ 个叶子节点,在叶子节点上都有一个权值.且这些权值是 $1$ ~ $n$ 的排列.现在可以任意交换非叶子节点的左右儿子.求最终遍历得到的权值的序列的逆序对数最少.
$n \le 200000$

Solution:

首先我们可以贪心地想,若一个非叶子节点交换后,该子树内的逆序对数减少,便交换.
这里我们统计逆序对可以用BIT
再是合并左右儿子,可以是启发式合并.保证一个 $log$ .
这样的复杂度是 $\Theta(nlog^2n)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 2000002int n,rt;
int ls[N],rs[N],sz[N];
int A[N],B[N],tim;
ll ans;void Rd(int &p){int x;scanf("%d",&x);if(!x){p=++n;Rd(ls[p]),Rd(rs[p]);sz[p]=sz[ls[p]]+sz[rs[p]];}else {p=x;A[++tim]=x;sz[p]=1;}
}struct BIT{#define lowbit(x) (x&-x)int bit[N];void add(int x){while(x<=n){++bit[x];x+=lowbit(x);}}int query(int x){int res=0;while(x){res+=bit[x];x-=lowbit(x);}return res;}}T;struct node{int L,R,p;
};void solve(node now){if(sz[now.p]==1){T.add(now.p);return;}ll tmp=0;int ni;if (sz[ls[now.p]]<sz[rs[now.p]]) {solve((node){now.L+sz[ls[now.p]],now.R,rs[now.p]});SREP(i,now.L,now.L+sz[ls[now.p]]){ni=T.query(A[i]);tmp+=ni-B[A[i]];B[A[i]]=ni;}solve((node){now.L,now.L+sz[ls[now.p]]-1,ls[now.p]});} else {solve((node){now.L,now.L+sz[ls[now.p]]-1,ls[now.p]});REP(i,now.L+sz[ls[now.p]],now.R){ni=T.query(A[i]);tmp+=ni-B[A[i]];B[A[i]]=ni;}   solve((node){now.L+sz[ls[now.p]],now.R,rs[now.p]});}ans+=min(tmp,(ll)sz[ls[now.p]]*sz[rs[now.p]]-tmp);
}void Pr(int p){if(!sz[p])return;printf("p=%d sz=%d\n",p,sz[p]);Pr(ls[p]);Pr(rs[p]);
}int main(){scanf("%d",&n);Rd(rt);
//  Pr(1);solve((node){1,tim,rt});printf("%lld\n",ans);return 0;
}

POI 2011 Tree Rotations 2

Description:
与上题题意一样.
但 $n \le 10^6$

Solution:
正解应该是 $Splay$ 或 $Treap$ ,但 $2$ 个 $log$ 还是可以卡一卡的.(手动滑稽…

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 2000002int n,rt;
int ls[N],rs[N],sz[N];
int A[N],B[N],tim;
ll ans;void Rd(int &p){int x;scanf("%d",&x);if(!x){p=++n;Rd(ls[p]),Rd(rs[p]);sz[p]=sz[ls[p]]+sz[rs[p]];}else {p=x;A[++tim]=x;sz[p]=1;}
}struct BIT{#define lowbit(x) (x&-x)int bit[N];void add(int x){while(x<=n){++bit[x];x+=lowbit(x);}}int query(int x){int res=0;while(x){res+=bit[x];x-=lowbit(x);}return res;}}T;ll tmp;
int ni;
void solve(int L,int R,int p){if(sz[p]==1){T.add(p);return;}if (sz[ls[p]]<sz[rs[p]]) {solve(L+sz[ls[p]],R,rs[p]);tmp=0;SREP(i,L,L+sz[ls[p]]){ni=T.query(A[i]);tmp+=ni-B[A[i]];B[A[i]]=ni;}ans+=min(tmp,(ll)sz[ls[p]]*sz[rs[p]]-tmp);solve(L,L+sz[ls[p]]-1,ls[p]);} else {solve(L,L+sz[ls[p]]-1,ls[p]);tmp=0;REP(i,L+sz[ls[p]],R){ni=T.query(A[i]);tmp+=ni-B[A[i]];B[A[i]]=ni;}   ans+=min(tmp,(ll)sz[ls[p]]*sz[rs[p]]-tmp);solve(L+sz[ls[p]],R,rs[p]);}
}void Pr(int p){if(!sz[p])return;printf("p=%d sz=%d\n",p,sz[p]);Pr(ls[p]);Pr(rs[p]);
}int main(){scanf("%d",&n);Rd(rt);
//  Pr(1);solve(1,tim,rt);printf("%lld\n",ans);return 0;
}

POI 2011 Temperature

Description:
有连续 $n$ 天的温度的区间 $[l_i,r_i]$ .找出最长的连续的一段,满足该段的温度可能不降.
$n \le 10^6$

Solution:

小数据模拟不难发现具有单调性.即单调队列维护.再看看数据范围,应该就是标准的 $\Theta(n)$ 了.
对于出队的情况.
若 $l_i \ge l_{q[R]}$ ,即弹出队尾.
若 $r_i \le l_{q[L]}$ ,即弹出队头.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 1000002int n;
int l[N],r[N];
int Q[N];int main(){scanf("%d",&n);REP(i,1,n)scanf("%d%d",&l[i],&r[i]);int L=1,R=0,ans=1;REP(i,1,n){while (L<=R && l[i]>=l[Q[R]]) R--;Q[++R]=i;while (L<=R && l[Q[L]]>r[i]) L++;chkmax(ans,i-Q[L-1]);}printf("%d\n",ans);return 0;
}

POI 2011 Dynamite

Description:
给你一颗 $n$ 个点的树,一些点上有炸药.现在引燃 $m$ 个点.求引燃所有炸药的最小时间.
注意:已引燃的点传递到与该点相连的点的时间为 $1$ .
$n \le 300000$

Solution:

不难发现,这个时间具有单调性.那么我们先二分一个答案.
对于 $check$ 的 $t$ ,即为限制的时间.我们可以贪心地想.
若该点没被引燃点覆盖,即为新的引燃点.
然后每个点 $x$ 有三种状态:有一个距离 $x$ 为 $t$ 的点没有被覆盖;没有点未被覆盖且 $x$ 所在子树有个点可以向外延伸长度为 $t$ ;不能延伸也唯有未被覆盖的点. $dfs$ 一下即可.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(mx) sizeof(mx)
#define mcl(mx,b) memset(mx,b,Sz(mx))
#define mcp(mx,b) memcpy(mx,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 300002int n,m;
int mark[N],mx[N];
vector<int>E[N];
int sum;void dfs(int x,int f,int t){int u=-INF,v=mark[x]-1;SREP(i,0,E[x].size()){int y=E[x][i];if(y==f)continue;dfs(y,x,t);if(mx[y]>0) chkmax(u,mx[y]-1);if(mx[y]<0) chkmax(v,-mx[y]);}if(u>=v)mx[x]=u;else if (v==t){sum++;mx[x]=t;}else mx[x]=-v-1;
}bool check(int t){sum=0;dfs(1,0,t);if(mx[1]<0)sum++;return sum<=m;
}int main(){scanf("%d%d",&n,&m);REP(i,1,n)scanf("%d",&mark[i]);SREP(i,1,n){int a,b;scanf("%d%d",&a,&b);E[a].pb(b);E[b].pb(a);}int L=0,R=n,ans=0;while(L<=R){int mid=(L+R)>>1;if(check(mid))ans=mid,R=mid-1;else L=mid+1;}printf("%d\n",ans);return 0;
}

POI 2011 Party

Description:
有一个n个点,m条边的存在一个大小至少为 $\frac{2}{3}n$ 的团.找出一个任意大小为 $\frac{n}{3}$ 的团.
$n \le 3000 , \frac{\frac{3}{2}n(\frac{2}{3}n-1)}{2} \le m \le \frac{n(n-1)}{2}$

Solution:

既然找一个团比较困难.
那就正难则反嘛.找多余的边进行删边.
那么剩下一定是一个团,且大小一定大于 $\frac{n}{3}$ .

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(mx) sizeof(mx)
#define mcl(mx,b) memset(mx,b,Sz(mx))
#define mcp(mx,b) memcpy(mx,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 3002int n,m;
bool vis[N],mark[N][N];int main(){scanf("%d%d",&n,&m);REP(i,1,m){int a,b;scanf("%d%d",&a,&b);mark[a][b]=mark[b][a]=1; }REP(i,1,n){if(vis[i])continue;REP(j,1,n){if(i==j || vis[j] || mark[i][j])continue;vis[i]=vis[j]=1;break;}}int i=1,j=1;while(i<=n && j<=n/3){if(!vis[i]){printf("%d ",i);++j;}++i;}return 0;
}

POI 2011 Inspection

Description:
在一棵 $n$ 个节点的树上,你需要检查每个点.但每次只能检查一个点,且检查完一个点必须走回起点 $1$ ,特殊的,最后一个检查的点不需要回到起点.并且相邻两次的检查的路径不能有交集.
$n \le 10^6$

Solution:

首先这种题就是要模拟小数据,不能发现,如果去掉 $x$ 后还有个连通块大小超过 $\frac{n}{2}$ 就无解了.
否则就需要维护一下 $x$ 的最长链及以重儿子为根的子树大小.
注意小细节是还要在当前检查路径上的子树大小与另外一端的点数比较,需要分类讨论一下.以及最后一个点不再用回起点.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(mx) sizeof(mx)
#define mcl(mx,b) memset(mx,b,Sz(mx))
#define mcp(mx,b) memcpy(mx,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 1000002int n;int qwq,head[N];
struct edge{int to,nxt;
}E[N<<1];
void addedge(int x,int y){E[qwq]=(edge){y,head[x]};head[x]=qwq++;}
#define LREP(x) for(int i=head[x];~i;i=E[i].nxt)int dis[N],sz[N],son[N];
int mx[N][2],Id[N],dp[N];
ll ans[N];void update(int x,int y,int d){if(mx[x][0]<d){mx[x][1]=mx[x][0];mx[x][0]=d;Id[x]=y;}else chkmax(mx[x][1],d);
}void dfs(int x,int f){sz[x]=1;son[x]=0;LREP(x){int y=E[i].to;if(y==f)continue;dis[y]=dis[x]+1;dfs(y,x);sz[x]+=sz[y];if(sz[son[x]]<sz[y])son[x]=y;update(x,y,mx[y][0]+1);}
}void solve(int x,int f){LREP(x){int y=E[i].to;if(y==f)continue;ans[y]=ans[x]+n-2*sz[y];dp[y]=max(dp[x],Id[x]==y?mx[x][1]:mx[x][0])+1;solve(y,x);}ans[x]<<=1;int s,d;if(sz[son[x]]>n-sz[x])s=sz[son[x]],d=mx[son[x]][0]+1;else s=n-sz[x],d=dp[x];if((s<<1)>n)ans[x]=-1;else if((s<<1)==n)ans[x]-=d;else ans[x]-=max(dp[x],mx[x][0]);
}int main(){qwq=0;mcl(head,-1);scanf("%d",&n);SREP(i,1,n){int a,b;scanf("%d%d",&a,&b);addedge(a,b);addedge(b,a);   }dfs(1,0);REP(i,1,n)ans[1]+=dis[i];solve(1,0);REP(i,1,n)printf("%lld\n",ans[i]);return 0;
}

POI 2011 Meteors

Description:
在一个长度为 $m$ 个环上,一个单位都属于一个国家,有 $q$ 次操作,每次操作是在环上一个区间上加上 $w_i$ .然后每个国家有一个目标数.求每个国家达到目标数是第几次操作.否则输出 $NIE$ .
$n,m,q \le 300000 , w_i \le 10^9$

Solution:

经典的整体二分题.
每次的贡献在用BIT进行维护以及回溯.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(mx) sizeof(mx)
#define mcl(mx,b) memset(mx,b,Sz(mx))
#define mcp(mx,b) memcpy(mx,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 300002int n,m,q;
int ned[N];
int head[N],nxt[N],id[N];
struct ask{int l,r,w;
}Q[N];
int stk[N];
ll sum[N],ans[N];struct BIT{#define lowbit(x) (x&-x)ll bit[N];void add(int x,int v){while(x<=m){bit[x]+=v;x+=lowbit(x);}}ll query(int x){ll res=0;while(x){res+=bit[x];x-=lowbit(x);}return res;}
}T;void solve(int l,int r,int L,int R){if(L>R)return;if(l==r){REP(i,L,R)ans[id[i]]=l;return;}
//  printf("l=%d r=%d L=%d R=%d\n",l,r,L,R);int mid=(l+r)>>1;REP(i,l,mid){if(Q[i].l<=Q[i].r)T.add(Q[i].l,Q[i].w),T.add(Q[i].r+1,-Q[i].w);else T.add(Q[i].l,Q[i].w),T.add(1,Q[i].w),T.add(Q[i].r+1,-Q[i].w);}int nL=R+1,nR=L-1;REP(i,L,R){sum[i]=0;for(int j=head[id[i]];j;j=nxt[j]){sum[i]+=T.query(j);if(sum[i]>=ned[id[i]])break;}if(sum[i]>=ned[id[i]])stk[++nR]=id[i];else ned[id[i]]-=sum[i],stk[--nL]=id[i];}REP(i,L,R)id[i]=stk[i];REP(i,l,mid){if(Q[i].l<=Q[i].r)T.add(Q[i].l,-Q[i].w),T.add(Q[i].r+1,Q[i].w);else T.add(Q[i].l,-Q[i].w),T.add(1,-Q[i].w),T.add(Q[i].r+1,Q[i].w);}solve(l,mid,L,nR),solve(mid+1,r,nL,R);
}int main(){scanf("%d%d",&n,&m);REP(i,1,m){int x;scanf("%d",&x);nxt[i]=head[x];head[x]=i;id[i]=i;}REP(i,1,n)scanf("%d",&ned[i]);scanf("%d",&q);REP(i,1,q)scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].w);solve(1,q+1,1,n);REP(i,1,n){if(ans[i]<=q)printf("%d\n",ans[i]);else puts("NIE");}return 0;
}

POI 2011 Sticks

Description:
有k种颜色的木棍,对于每种颜色的木棍,告诉你它的长度.求是否存在一个用三个不同颜色的木棍组成的三角形.
$n \le 10^6 , len_i \le 10^9$

Solution:

与之前2018百度之星的一道题相似.
首先对边进行排序,然后逐一筛选 $3$ 个颜色的木棍.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(mx) sizeof(mx)
#define mcl(mx,b) memset(mx,b,Sz(mx))
#define mcp(mx,b) memcpy(mx,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;#define N 1000002
#define M 52template<class T>inline void Rd(T &x){x=0;char c;while((c=getchar())<48);do x=(x<<1)+(x<<3)+(c^48);while((c=getchar())>47);
}int n,m;
struct node{int len,col;bool operator<(const node &_)const{return len<_.len;} 
}A[N];
int len[M];void check(int col1,int col2,int id3){if(len[col1]+len[col2]>A[id3].len){printf("%d %d %d %d %d %d\n",col1,len[col1],col2,len[col2],A[id3].col,A[id3].len);exit(0);}
}int main(){scanf("%d",&m);REP(i,1,m){int cnt,x;Rd(cnt);while(cnt--){Rd(x);A[++n]=(node){x,i};} }sort(A+1,A+1+n);int col1,col2,col3;col1=col2=col3=0;REP(i,1,n){if(A[i].col==col1) check(col2,col3,i);else if(A[i].col==col2) check(col1,col3,i);else check(col1,col2,i);len[A[i].col]=A[i].len;if(A[i].col==col2)swap(col1,col2);else if(A[i].col!=col1){col3=col2;col2=col1;col1=A[i].col;}}puts("NIE");return 0;
}

POI 2011 Programming Contest

Description:
n个人m道题.每到题需要r分钟.比赛有t分钟.每个人都会做相应的题.求最大做题数及最小罚时.
$n,m \le 500 , r,t \le 10^6$

Solution:

首先,此题一眼就是一个裸的最小费用最大流.但复杂度有点大的…
那么我们分析…
注意到它其实是一个类似于二分图的增广方式,那么用二分图匹配的方法来跑即可.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(mx) sizeof(mx)
#define mcl(mx,b) memset(mx,b,Sz(mx))
#define mcp(mx,b) memcpy(mx,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;
typedef pair<ll,ll>PLL;#define N 1010
#define M 1000002int n,m,r,t,k;int S,T;
int head[N],qwq;
struct edge{int to,nxt,cap,flow,cost;
}E[M<<1];
void addedge(int x,int y,int cap,int cost){E[qwq]=((edge){y,head[x],cap,0,cost});head[x]=qwq++;E[qwq]=((edge){x,head[y],0,0,-cost});head[y]=qwq++;
}struct Min_Cost_Max_Flow{queue<int>Q;int Mn[N],d[N],pre[N];bool vis[N];ll cost,flow;bool SPFA(){mcl(d,INF);Q.push(S);vis[S]=1;d[S]=0;Mn[S]=INF;while(!Q.empty()){int x=Q.front();Q.pop();vis[x]=0;for(int i=head[x];~i;i=E[i].nxt){int y=E[i].to;if(E[i].cap>E[i].flow && chkmin(d[y],d[x]+E[i].cost)){pre[y]=i;Mn[y]=min(Mn[x],E[i].cap-E[i].flow);if(!vis[y])Q.push(y),vis[y]=1;}}}if(d[T]==INF)return 0;int U=T;while(U!=S){E[pre[U]].flow+=Mn[T];E[pre[U]^1].flow-=Mn[T];U=E[pre[U]^1].to;}flow+=Mn[T];cost+=1ll*Mn[T]*d[T];return 1;}PLL solve(){cost=flow=0;while(SPFA());return (PII){flow,cost};    }}MCMF;struct p1{void solve(){qwq=0;mcl(head,-1);S=0,T=n+m+1;REP(i,1,n){int cnt=0;for(ll j=r;j<=t;j+=r){addedge(S,i,1,j); cnt++;if(cnt==m)break;}}REP(i,1,m)addedge(i+n,T,1,0);while(k--){int a,b;scanf("%d%d",&a,&b);addedge(a,b+n,1,0);}PLL ans=MCMF.solve();printf("%lld %lld\n",ans.fi,ans.se);}
}p1;struct p2{int match[N];bool vis[N],mark[N];vector<int>E[N];bool find(int x){SREP(i,0,E[x].size()){int y=E[x][i];if(vis[y])continue;vis[y]=1;if(!match[y] || find(match[y])){match[y]=x;return 1;}}return 0;}void solve(){while(k--){int a,b;scanf("%d%d",&a,&b);E[a].pb(b);}ll cnt=0,sum=0;for(ll i=r;i<=t;i+=r) REP(j,1,n){if(mark[j])continue;mcl(vis,0);if(find(j))cnt++,sum+=i;else mark[j]=1;     }printf("%lld %lld\n",cnt,sum);}
}p2;int main(){scanf("%d%d%d%d%d",&n,&m,&r,&t,&k);if(n<=100 && m<=100) p1.solve();else p2.solve();return 0;
}