CodeForces#19 E

这是道好题啊。。。想想麻烦。。做做更麻烦。。
题目很简洁,给你一个图,求哪些边删掉之后能变成二分图。。
额。。我WA了N次。。比赛的时候肯定来不及。。。
慢慢分析吧。。
首先求生成树,然后对每个点2-染色,
那么如果删非树边的话,显然任何点的颜色都不会变,那么如果两端颜色一样的非树边有0条,所有非树边都可以删,有1条,只有这条可以删,2条或以上,都不能删。。
如果删树边的话,显然必须要搞翻所有的奇环,分析一下什么情况下一个树中会出现奇环。。
某个两端颜色一样的非树边造成的奇环。。
一个两端颜色一样的非树边和一个两端不一样的非树边造成的奇环。。
那么把这个树树链剖分一下。。对每个两端颜色一样的非树边的两点之间的路径+1,显然要删的树边上的权值一定要等于非树边的数量。。
然后对每个两端颜色不一样的非树边的两点之间的路径+1,显然要删掉树边不能在被两端颜色一样的非树边的两点间的路径跨越的情况下再被这个不一样的非树边的两点之间的路径跨越。。
然后维护两个树链剖分。。分别搞树边和非树边。。就没什么问题了。。
写的累死晕。。。
我发现还是我在codeforces上英文的说明更清楚一点啊囧。。。
It’s a interesting problem.If you for every edge, 
try to remove it and check if it is a 
bipartite 
graph..I think it will get TLE..so let’s analysis 
the property of bipartite graph..
It should never contain a cycle of odd length…
and it can be 2-colored..
so first build a spanning forest for the graph..
and do the 2-color on it(Tree can be 2-colored).
for convenience.
Let TreeEdge={all edge in forest}
NotTreeEdge={All edge}/TreeEdge
ErrorEdge={all edge that two endpoint have the same color..}
NotErorEdge=NotTreeEdge/ErroEdge..
First,consider a edge form NotTreeEdge,remove it 
can’t change any node’s color..so..if |ErrorEdge|=0 of course we can remove all NotTreeEdgeif =1 we just can remove the ErrorEdgeif >1 we can’t remove any from NotTreeEdge
Now,Let consider a Edge e from TreeEdge..
Let Path(Edge e)=the path in forest between e’s two endpoints..
if there is a Edge e’ from ErrorEdge that Path(e’) 
didn’t  go through e..it will destroy the bipartite 
graph..
if there is a Edge e’ from ErrorEdge that Path(e’) go through e and there is a Edge e” from NotErrorEdge that Path(e”) go through e..it will also destroy the bipartite graph..
so now we need to know for every edge,how many such path go through it..it require a data structure…
one way is to use heavy-light decomposition then we can update every path in O(LogN^2)…
another way is to use Link-Cut Tree..It can do the same in O(LogN)….
Code:
http://www.ideone.com/dPS5N

CodeForces#19…

自己做了场CodeForces。。发现偏偏是没有题解的那个囧。。。
A:跟24的B有点像的繁琐题。。忽略吧。。我由于过于SBWA了2次囧。。
B:将所有t=t+1,注意到选择的物品t的和要大于n。。同时价格和最小。。就是背包问题了。。
C:额。。显然每个repeat的开头那个跟中间那个是一样的,那么枚举每对一样的数,同时用Suffix Array帮忙算Lcp就可以搞出所有repeat,然后排个序依次处理就可以了。。为了方便我写了CQF的New Lcp。。
D:这个题目蛮有意思的。。首先要在尽量在右边,同时又要大于某个值,显然让人想到线段树。。所以我离散化了一下写了个线段树,同时对每个X值维护一个Set就可以了。。
E:有点难哎。。先睡觉吧明天再想啦

SRM 477

我震惊了。。

显然这次人品爆发的有点厉害。。话说每次我SRM的时候人品总会很好。。。这次好到了令人发指的程度。。。。
Problem 250 显然是水题,表示忽略。。
Problem 500 就是给你一堆数,每两个平方和是平方数的数能凑成一对,最对凑出几对?
我毫无思路。其实这个图是二分图那么就很显然了。。但很悲剧的是当时我想不出这个。。。。由于我信春哥。。我正好做过Ural 1099。。。于是写了个随机化交了。。居然过了。。
恩。。写个是二分图的证明吧。。
由于对两个数x,y来说,gcd(x,y)=1,所以不能都是偶数,同时一个数平方mod4只能是0或1.。显然如果两个都是1就不对了。。。所以只能一个是0一个是1,那么按平方mod4的余数分成两部分就可以了。。
Problem 1000 这题显然是APIO-2010巡逻那题的一个变种。。。所以同样算法可以无压力AC。。好像不能用O(n)的那个找直径的算法。。所以我写了个n^2的。。一开始写了个n^3的。。发现会TLE只好resubmit。。。
额。。差5分就可以变红了。。看来注定是个悲剧啊。。下次肯定没这么好RP就要掉Rating了。。。

块状树

最近过于颓废一直拖着这篇小论文囧。。今天总算不颓废了。。写下吧。。
称树的一个联通的顶点子集为树块,一个树块的根就是这个树块中深度最小的顶点,那么如果将树划分成一些树块
有如下定理:
对于两个顶点,(1)若他们属于相同的树块,那么Lca肯定在该数块中,(2)如果属于不相同的树块,Lca肯定不在树块的根较浅的那个树块中。。。
证明:(1)废话
(2):否则Lca就会在另一个顶点与其树块的根的路径上,与Lca属于较浅的那个树块矛盾。。
现在以QTREE为考虑的问题。。
考虑QTREE,如果对每个点都维护其到其树块的根的路径上最大边权,那么我们的询问就可以用以下方法完成。。
设当前顶点是u、v
若在同一树块中,直接暴力..
否则可以使用维护的信息跳过一个树块。。
同时修改直接暴力可以解决。。
那么显然要让修改快,当然块越小越好,要让查询快,当然块越大越好。取个综合,就是Sqrt(N)了。。
那么就要搞出一种划分的方法使得,
每个块大小不超过SqrtN。。。
每个点到根最多经过SqrtN个块。。。
划分的方法有很多.。我想出来3个。。就说说最实用的那个吧。。
Dfs一下,对每个结点只要其属于的块大小不超过SqrtN,就把其孩子加入其属于的块。。否则其孩子自立一个块。。
这种数据结构的优点:
代码短,好写,没了。。
缺点:
只能维护单点(边)的修改,不能应付GSS7那样的神题,
速度:
速度还不错。。可以看下我交的那个八中OJ1036的代码。。。最快的那个第16。。。
写的时候的一些技巧:
修改的时候只需要修改该点在块里的后代,可以加快不少。
对每个点另开一个边表维护在块里的后代。
或者用Bfs来修改(快不了多少。。。)
代码:
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define pb push_back
const int maxn=30000,inf=~0U>>1;
using namespace std;
vector<int> E[maxn],Et[maxn];
typedef vector<int>::iterator it;
int n,q,w[maxn],L,D[maxn],F[maxn];
int own[maxn],M[maxn],S[maxn]={};
void Build(int t,int f,int d)
{
D[t]=d;F[t]=f;
int tmp=own[t];
tr(e,E[t])if(*e!=f)
{
if(S[tmp]++<L)Et[t].pb(*e),own[*e]=tmp;
Build(*e,t,d+1);
}
}
void Dfs(int t,int s,int m)
{
S[t]=s+=w[t];M[t]=m>?=w[t];
tr(e,Et[t])Dfs(*e,s,m);
}
void Change(int t,int u)
{
w[t]=u;
if(t==own[t])Dfs(t,0,-inf);
else Dfs(t,S[F[t]],M[F[t]]);
}
void Query(int a,int b,int&s,int&m)
{
s=0;m=-inf;
while(a!=b)
{
if(D[a]<D[b])swap(a,b);
if(own[a]==own[b])
s+=w[a],m>?=w[a],a=F[a];
else
{
if(D[own[a]]<D[own[b]])swap(a,b);
s+=S[a],m>?=M[a],a=F[own[a]];
}
}
m>?=w[a];s+=w[a];
}
int main()
{
scanf("%d",&n);int s,t;L=sqrt(n)+1;
rep(i,n-1)scanf("%d%d",&s,&t),–s,–t,E[s].pb(t),E[t].pb(s);
rep(i,n)scanf("%d",w+i),own[i]=i;
Build(0,-1,0);
rep(i,n)if(own[i]==i)Dfs(i,0,-inf);
scanf("%d",&q);
char cmd[100];int S,M;
rep(i,q)
{
scanf(" ");
scanf("%s%d%d",cmd,&s,&t);
if(cmd[0]==’C’)Change(s-1,t);
else
{
Query(s-1,t-1,S,M);
if(cmd[1]==’S’)printf("%dn",S);
else printf("%dn",M);
}
}
}

CodeForces#24

额。。我发现CodeForces比TopCoder更接近OI。。感到很有意思。。以后要多关注这个地方了。。

Problem A:
水题。。我写了个Dfs爆搜非常的繁琐。。幸好1A了。。
Problem B:
模拟题这题折磨了我很久。。我大量使用了map和vector,不知道哪个地方出错了。。改了半天最后做完C之后才A掉这个。。
Problem C:
这题比B好做多了。。直接循环到一定程度就可以直接计算了。。
Problem E:
一开始我在那边写E因为我感觉这个就是一个最大斜率啊。。可惜对这方面不熟悉哎囧。。不是很会搞。。以后要补一下了囧。。。求(x-x’)/(v-v’)的最小值,就是倒数的最大值。。。。然后应该可以做。。但是我水平太烂写不出来囧。。
Problem D:
这题最神奇了!!!我完全不能相信我居然过了!!

Ural 1752 Tree 2

题目很简洁。。做法也容易。。就是有点烦。。
很显然你要知道是否要输出0,必须知道从某点开始的最长路径,显然可以Dp之。。
然后干脆对每个询问都在最长路径上找点。。
对每个点记录2^k的祖先就可以准确的找到点。。就没问题了。。。
Code:
超过最大长度。。
www.ideone.com/I5fn5

无聊弄出来的Lca算法。。。

   天天在弯销油西。。。颓废万分。。晚上总算去水了道题。。我无聊中想出一个很SB的Lca。。。
就是把这颗树树链剖分(不用线段树的,只需要记录每个点对应当路径的最高点)。。。
然后考虑u和v的Lca(假设u的深度大于v)。。如果在同一条链中就是v。。
否则的话设u的路径最高点要深于v的路径最高点,那么显然Lca不可能在u的路径中,将u换成u的路径最高点的父节点。。。然后就这递归下去。。。
额。。时间复杂度LogN。。预处理复杂度是O(N)的。。常数又比线段树那个要小。。速度比记录2^k祖先那个和线段树都要快一些。。树链剖分还可以写Bfs..拒绝爆stack。。还是挺不错滴(*^__^*) 嘻嘻。。。
Code:(题目是Ural上的Tree)
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=50000;
using namespace std;
int n,q;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void AddEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));
E[t].pb(Edge(s,c));
}
void Init()
{
scanf("%d",&n);int s,t,c;
rep(i,n-1)
{
scanf("%d%d%d",&s,&t,&c);
AddEdge(s,t,c);
}
}
int D[maxn],C[maxn],F[maxn],Size[maxn];
int Q[maxn],h,t,Own[maxn];
void BFS(int vs)
{
h=t=0;
for(Q[t++]=vs,F[vs]=-1,D[vs]=0,C[vs]=0;h<t;h++)
{
int x=Q[h];
tr(e,E[x])if(e->t!=F[x])
{
F[e->t]=x;C[e->t]=C[x]+e->c;
D[e->t]=D[x]+1;Q[t++]=e->t;
}
}
for(int i=h-1;i>=0;i–)
{
int x=Q[i];Size[x]=1;
tr(e,E[x])if(e->t!=F[x])Size[x]+=Size[e->t];
}
memset(Own,-1,sizeof Own);
for(int i=0;i<h;i++)
{
int a=Q[i];
int x=a,next;if(Own[x]>=0)continue;
for(;;x=next)
{
next=-1;Own[x]=a;
tr(e,E[x])if(e->t!=F[x])
if(next==-1||Size[e->t]>Size[next])
next=e->t;
if(next==-1)break;
}
}
}
int Lca(int u,int v)
{
for(;;)
{
if(D[u]<D[v])swap(u,v);
if(Own[u]==Own[v])return v;
if(D[Own[u]]<D[Own[v]])swap(u,v);
u=F[Own[u]];
}
}
int Query(int u,int v)
{
int lca=Lca(u,v);
return C[u]+C[v]-2*C[lca];
}
void Solve()
{
scanf("%d",&q);int u,v;
rep(i,q)
{
scanf("%d%d",&u,&v);
printf("%dn",Query(u,v));
}
}
int main()
{
//freopen("in","r",stdin);
Init();
BFS(0);
Solve();
}

SPOJ QTREE3

这个变态题目。。有N种做法。。能AC的MS不多囧。。
做法系列1:
思路:从下往上对每个节点维护一个平衡树,然后用平衡树来回答第K大大问题
A:平衡树+启发式合并,两颗平衡树合并直接暴力把小的插进大的。。每个最多被插LogN次。。总共就是O(NLogN^2+QLogN)。。极难AC。。我Treap TLE,SBT也TLE。因为我SBT写得太烂了。。
B:Splay合并,Splay可以做到在O(NLogN)完成合并。。然后Splay常数较大,还是TLE。。。
C:注意题目的特性。。首先就是Q比N小很多,就是说许多结点都不需要维护平衡树,先先序遍历这个树,然后一些节点要插入的话直接用先序遍历中的区间插入。。再设个常数如果一个节点中最大的子树实在太小的话插入也麻烦干脆直接重新建个平衡树好。。估计可以勉强AC。。不过可能很困难吧。。我一直觉得可能可以弄个阀值仿照IOI2009的Region搞出来。。不过很麻烦。。
做法系列2:
思路:从小到大加入每个数,对每个节点维护还需要+几个数就可以输出了。。然后每次都可以取路径中的最小值,如果是0的话就输出,然后变成下一个。。一个节点显然只能影响的它的所有祖先。。所以需要维护路径。。
A:维护路径,还要最小值,直接上动态树,我的动态树写得太烂了。。无法AC。。。
B:维护路径也可以树链剖分啊,还是TLE。。。
做法系列3:
思路:TMD,干脆忽略这个树直接上区间K大值的算法好了,当然要先先序遍历一下了。。
A:一般的先二分在用线段树的做法肯定TLE O(NLogN+QLogN^3)..
B : 有一种二分树就是对所有权值建树,然后每个节点储存当前权值区间中的所有数在序列中的位置。。那么可以LogN得到节点区间中L到R之间的树的个数,就可以在LogN^2完成2分了。。写的好一点可以AC。。。
C:还有一种很NB的划分树,可以在NLogN+QLogN的时间解决问题。。非常NB啊。。具体看www.notonlysuccess.com/ 还不会写哎。。不过应该可以AC。。。

Page 1 of 41234