POI2011 Conspiracy (2-SAT)
Description
\(n\leq 5000\)
Solution
发现可拆点然后使用2-SAT做,由于特殊的关系,可以证明每次只能交换两个集合中的一个元素,或者改变一个元素的位置,然后分类讨论即可.
注意特判集合为空的情况.
POI2011 Lollipop (YY)
Description
\(n,m\leq 1000000,q\leq 2000000\)
Solution
挖掘题目性质,由于只存在1,2.所以对于一个端点为1的线段,如果它能表示x+1,则一定可以表示出x.
所以预处理从起始点开始的情况,以及从最两边的1开始的情况,就可以解决该问题了.
POI2011 Lightning Conductor
Description
\(n\leq 500000,ai\leq 1000000000\)
Solution1
定义
- \(dp[i]=Max^{i}_{j=1}(A[j]+\sqrt{i-j})-A[i]\)
- \(DP[i]=Max^{n}_{j=i}(A[j]+\sqrt{j-i})-A[i]\)
- \(p[i]=Max(dp[i],DP[i])\)
然后根据\(f(x)=\sqrt{x}\)的图像性质可知,\(\sqrt{x}\)为缓增图像.
然后根据该性质可以用类似四边形不等式+分治的方法确定转移区间.
复杂度\(O(nlogn)\)
Solution2
发现可以影响答案的只有\(Mx-\sqrt{n}\)到\(Mx\),同时对于同一数值的点,分散到最两端的才能影响答案.
所以共计最多\(2*\sqrt{n}\)个,然后每个点产生的不同p只有\(sqrt{n}\)个,所以总修改操作只有\(n\)个.
然后使用线段树动态维护区间最大值就好了.
复杂度\(O(nlogn)\)
POI2011 Shift (YY)
Description
\(n\leq 2000\)
Solution
由于只关心操作块,所以操作一可以直接抽象成移动一个队头指针,就是把序列头尾相连.
操作二可以看做把某个数在环上向前跳两个.
然后模拟+注意细节即可.
POI2011 Plot (计算几何)
Description
\(n\leq 100000\)
Solution
最大值最小->显然需要二分答案,二分最后的半径.
然后就要枚举每个圆心的覆盖的点.
可以贪心地发现:一个圆要尽覆盖尽量多的点.
已知最小覆盖圆算法为O(n)的.
那么直接二分的话复杂度为\(log{n}*n^2log{n}\)
考虑优化,如果让每次二分的量级和最后的答案不会差太大.
那就用类似倍增的方法,每次将枚举的答案区间乘2.
直到不合法时,确定答案在\((2^{k-1},2^{k})\)之内.
然后再倍增一遍.
总复杂度为\(logn * \sum l*logl\)其中\(\sum l =n\) ,所以可以近似为\(nlog^2n\)
POI2011 Strongbox (Math)
Description
\(k\leq 250000,n\leq 10^14\)
Solution
对于一个密码a可推广出的密码,可以抽象为\(ax+ny\)在模n意义下的所有非负数解.
有裴蜀定理得,这些非负数解一定是gcd(a,n)的倍数.
同时可推广:如果密码集合有两个数互质,那么所有数将会成为答案.
所以总能确定密码集合中所有数是某个数(key)的倍数.
所以确定一个密码a后,key一定是gcd(a,n)的因子.
所以就枚举gcd(a,n)的因子,然后暴力检验是否为之前给的k-1个数与n的gcd的因数(加一点剪枝就过去了)
POI2011 Difference (DP)
Description
\(n\leq 1000000\)
Solution
通过枚举出现最少和出现最多的字母,然后跑一遍最大连续和即可.
然后对于某点权值为a,只用更新52种状态.
复杂度\(O(52*n)\).
POI2011 Garbage (Euler Path)
Description
\(n\leq 100000,m\leq 1000000\)
Solution
发现对于一个无需改变的边,那么一定会被经过偶数次,那么等于可以把两条简单路径合并成一条.
所以就只关心需要改变的边,跑欧拉回路就可以了.
由于只能跑简单环,所以在dfs下去的时候把x加入栈,然后再遍历到该点的时候弹出.
void Angry_Tiger(int x){
if(vis[x]){
++now;
while(1){
Ans.add(now,Sk[top]);
vis[Sk[top]]=false;
Sz[now]++;
if(Sk[top--]==x)break;
}
}
LFOR(i,x,E){
int y=E[i];
if(mark[i]||mark[i^1])continue;
mark[i]=1;
vis[Sk[++top]=x]=true;
Angry_Tiger(y);
}
}
POI2011 Dynamite(Binary)
Description
\(n\leq 300000\)
Solution
首先可以看出答案满足单调性,所以二分答案把题目化作一个判定性问题.
然后要做一个类似于树形dp的东西.
从叶子结点向上转移,当且仅当必须要加点的时候才加点.
要记录两个东西:还未被覆盖且距离自己最远的点(Mx),以及距离自己最近的爆炸点(Mi).
然后若\(Mx+Mi<=mid\),\(Mx=0\)
否则\(Mx==mid\),\(cnt++,Mi=-1,Mx=-1\)
POI2011 Programming Contest(二分图)
Description
\(n,m\leq 500,1\leq r,t\leq 10^6\)
Solution
首先有一个结论:集体完成的时间越短越好.
当然这个是在保证做题数不变的情况下.
然后根据这个性质,可以不断推移时间线,然后让每个时间段的做题数尽量多.
这显然是一个二分图匹配,每次匹配的复杂度为\(O(nm)\).
设最后每个人的做题数量为\(A_i\),那么对于一个人,对他做二分图匹配的次数也是\(A_i\)次,已知\(\sum A_i=m\),所以总复杂度为\(O(nm^2)\).
POI2014 Salad Bar(单调栈)
Description
\(n\leq 10^6\)
Solution
记p=1,j=-1,Dim \(A_i\)为前缀和.
然后对于一段合法区间[l,r],一定要满足\(A[l]\leq A[x]\leq A[r]\),其中\(x \in [l,r]\) .
那么发现可以使用单调栈维护这个上界和下界.
对于一个二元组\((x,y)\),x表示下界,y表示上界.
那么对于两个二元组a,b 如果\(a.x\leq b.x\)且\(a.y\leq b.y\)那么两者就可以合并成\((a.x,b.y)\).
如果当前\(b.x<a.x\),那应该弹掉栈中的a,因为将没有序列可以和它相接.
然后如果弹完之后栈顶元素a,\(a.y>b.y\),将b加入栈中,不然就执行合并操作.
总复杂度\(O(n)\)
FOR(i,1,c){
now+=abs(B[i]);
if(i==1){
if(B[i]>0){
Sk[++top]=(node){1,now};
ans=max(ans,now);
}
else low=now+1;
}else {
if(B[i]<0){
while(A[Sk[top].a-1]>A[now]&&top)--top;
low=now+1;
}
else{
while(A[Sk[top].b]<=A[now]&&top){
low=Sk[top].a;
--top;
}
Sk[++top]=(node){low,now};
ans=max(ans,now-low+1);
}
}
}
POI2014 Couriers(Segment Tree)
Description
\(n,m\leq 5*10^5\)
Solution
这个(r-l+1)/2是一个特别好的性质.
可以先离散权值,然后看左半部分的个数和是否大于sz/2,如果右半部分也不合法,那就无解.
然后这个信息可以用可持久化权值线段树维护.
POI2014 Around the world(尺取)
Description
\(n\leq 1000000,s\leq 100\)
Solution
发现这题的复杂度应该为\(O(ns)\).
贪心地考虑,每个点对于当前的x最多能到哪个点.
这个信息可以用单调队列或者尺取解决.
然后利用Dis维护一下深度最后减一下就可以了.
FOR(i,0,n<<1)pre[i]=i;
int l=0,ans=n;
FOR(i,n+1,n<<1){
while(B[i]-B[l]>x)++l;
pre[i]=pre[l];
Dis[i]=Dis[l]+1;
if(i-pre[i]>=n)ans=min(ans,Dis[i]-Dis[pre[i]]);
}
