APIO了不好好写APIO的题来这儿装逼
BZOJ3969: [WF2013]Low Power
最大值最小肯定二分，然后我们将序列排序。然后相邻的一定比不相邻的优。
所以我们从小到大贪心，能选就选，不能选就随便扔到前面的电池上反正是合法的。
判断合法性的时候只要看剩下的电池数目够不够剩下的机器所需即可。从小到大也保证了这样更容易合法。
BZOJ3955: [WF2013]Surely You Congest
首先，最短路不同的一定不会发生堵塞。那么我们就按最短路分层考虑。
然后每条边只允许经过一次。。。这不就是个最大流么。。。
最坏情况下500次25000个点的网络流，这复杂度也能过我也是醉了
UPD：发现WF的题做不动。于是羞耻地修改了博文名称TATQAQ
BZOJ4029: [HEOI2015]定价
肯定尽量把数的后面都变成0。那么我们就可以脑补一个做法
当r-l<=lim的时候暴力
否则一定可以找到一个最小的数x（假设lim=10^5)>=l并且最后五位都是0，那么l-x的暴力检验一下，x-r的一定只有后面5位都为0的时候才可能比答案优。
所以就lim步长跳就可以了
BZOJ3979: [WF2012]infiltration
额。。。一般图的最小支配集只能爆搜。。。然后这题图比较特殊。
因为是竞赛图，即任意两点间都有一条有向边。
那么我们可以知道ans一定不会超过log（n）。因为我们可以每次取出出度最大的点，而这个出度一定>=当前点数/2.
然后将问题的规模缩小一半。这样就得到了一个log（n）的答案。但是这样不一定是最优的。感性理解一下。。。
然后那我们就按出度从大到小爆搜好了。然后注意就是有可能选择之前已经被覆盖了的点。。。之前没考虑这个被坑死
BZOJ4027: [HEOI2015]兔子与樱花
这题我们猜！结！论！
一棵子树中，儿子对父亲的负担越小越先选，然后能选就选！
证明什么的。。。
考场上想不出什么好方法不会证也要上！
BZOJ4026: dC Loves Number Theory
这题好神Orz
如果我们知道乘积，那我们只要知道区间内出现的质数的p/(p-1)就行了。
想到了什么？对，就是HH的项链。那题维护区间内不同颜色个数，这题维护区间内不同质数的p/（p-1）的个数。
如果离线的话树状数组/线段树搞一下就可以了。强制在线？我们可以可持久！
我是只口胡不写代码的傻逼
BZOJ4063: [Cerc2012]Darts
呵呵
BZOJ4052: [Cerc2013]Magical GCD
刚开始搞了个O（nlog^3n）的做法。。。枚举起点，将终点分段。。。然后T得酸爽。。。
看题解发现只要维护以每个终点为结尾的所有gcd相同的起点最小值即可，因为gcd是O（logai）的。所以暴力维护即可。
BZOJ4059: [Cerc2012]Non-boring sequences
我们考虑一个数对哪些区间有贡献，显然是左端点∈[pre[i]-1,i]，右端点∈[i,nxt[i]-1]的区间。
那我们就把这些区间都+1.最后判断是否存在某个合法区间取值为0即可。
矩形加和最小值查询。我们可以查分+线段树搞定。
BZOJ4034: [HAOI2015]T2
良心送分题，链剖或者dfs序+线段树正面刚毫无压力。dfs序入的时候+1，出的时候-1.所以区间修改的时候出点的权值是-=w。这也很简单。线段树记录一下正点+负点的数量作为真正的size即可。
BZOJ3443: 装备合成
这一类题目也比较有趣 @SCOI2011棘手的操作
(UPD:这类题目其实也可以直接用splay搞，合并的时候拼到一块儿就行了。这样可以实现在线
因为涉及合并操作，并且不会分离。而且对某个集合的操作比较复杂，不是很简单维护的。
我们就可以先预处理一遍，把任意时刻的集合的所有点映射到一段区间上，而这样就可用序列上的数据结构来维护了。
要注意到把集合映射到区间上是可做的。
我们每次合并的时候把标号大的合并到标号小的上面，然后把集合内的点用链表串起来。
这样最后沿着链表走一遍就可以重编号，并且保证任意时刻任意集合内的点都是连续的一段区间。
这题比较坑定义了集合的合并方向，但这也不是什么大问题，我们只要记录一下每个集合当前真的是谁做代表就可以了。
对每个点维护一个它作为老大的时候管辖的区间就ok了。
代码大概长这样:线段树的操作就不贴了，人人都会
int n,m,k,tot,a[maxn][maxm],fa[maxn],id[maxn],last[maxn],pos[maxn],next[maxn];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct rec{int a,b,c,k;}q[maxk],c[maxn];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();k=read();
for1(i,n)for1(j,m)a[i][j]=read();
k=0;
int t;
while(scanf("%d,%d,%d,%d",&t)!=EOF){q[++k].k=t,q[k].a=read(),q[k].b=read(),q[k].c=read();}
for1(i,n)fa[i]=i,last[i]=id[i]=i;
for1(i,k)if(q[i].k==1)
{
int x=find(q[i].a),y=find(q[i].b);
if(x==y)continue;
if(x>y)swap(x,y);
fa[y]=x;
next[last[x]]=y;
last[x]=last[y];
}
for1(i,n)if(fa[i]==i)for(int j=i;j;j=next[j])pos[j]=++tot;
for1(i,n)last[i]=pos[i],fa[i]=i,c[i]=(rec){pos[i],pos[i],0,0};
for1(j,m)
{
for1(i,n)b[pos[i]]=a[i][j];
T[j].build(1,1,n);
}
for1(i,k)
{
if(q[i].k==1)
{
int x=find(q[i].a),y=find(q[i].b);
id[min(x,y)]=q[i].b;
if(x==y)continue;
if(x>y)swap(x,y);
fa[y]=x;
last[x]=last[y];
c[id[x]]=(rec){pos[x],last[x],0,0};
}else if(q[i].k==2)printf("%d\n",T[q[i].b].query(1,1,n,c[q[i].a].a,c[q[i].a].b));
else T[q[i].b].change(1,1,n,pos[q[i].a],q[i].c);
}
return 0;
}
评论 (0)
