link
You can view the official tutorial here
This is a simple but interesting data structure problem.
2016年3月12日 星期六
2016年3月11日 星期五
[Wunder Fund Round 2016 pD][DP] Hamiltonian Spanning Tree
link
You can view official tutorial here.
Here I will explain some points I consider important when trying to solve the problem.
There may be some mistakes in grammar due to my poor English QAQ.
Any correction of algorithm or grammar is welcomed.
It's not hard to find that x>y and x<y are two different problem: One is to use more tree edges as possible while the other is to use less tree edges.
You can view official tutorial here.
Here I will explain some points I consider important when trying to solve the problem.
There may be some mistakes in grammar due to my poor English QAQ.
Any correction of algorithm or grammar is welcomed.
It's not hard to find that x>y and x<y are two different problem: One is to use more tree edges as possible while the other is to use less tree edges.
2016年3月6日 星期日
2016年3月5日 星期六
2016年3月4日 星期五
2016年3月3日 星期四
[Codeforces Round #218 (Div. 2) pD][Disjoint Set] Vessels
原題連結
一道並查集的頗直覺的題目
難點大概就只有在有沒有想到要用Disjoint Set去做吧......
對於已經滿的vessel i ，執行 fa[i] <- findset(i+1) ，直觀上就是將每個相鄰的滿vessel連接起來，已達到快速查詢可用vessel的效果。
細節上要注意水流到地上的case要做好，不然很容易WA或是TLE。
一道並查集的頗直覺的題目
難點大概就只有在有沒有想到要用Disjoint Set去做吧......
對於已經滿的vessel i ，執行 fa[i] <- findset(i+1) ，直觀上就是將每個相鄰的滿vessel連接起來，已達到快速查詢可用vessel的效果。
細節上要注意水流到地上的case要做好，不然很容易WA或是TLE。
#include<cstdio> #define LL long long using namespace std; const int maxn=200000+5; int fa[maxn],cap[maxn],cur[maxn]; int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);} int main() { int n,m; scanf("%d",&n); for(int i=0;i<n;i++) {fa[i]=i;scanf("%d",cap+i);} fa[n]=n; scanf("%d",&m); for(int i=0,type,a,b;i<m;i++) { scanf("%d",&type); if(type==1) { scanf("%d%d",&a,&b);a--; a=findset(a); for(;b && a!=n;) { if(cap[a]-cur[a]>b) cur[a]+=b,b=0; else // cap[a]-cur[a]<=b { b-=cap[a]-cur[a]; cur[a]=cap[a]; fa[a]=findset(a+1); a=findset(a); } } } else { scanf("%d",&a);a--; printf("%d\n",cur[a]); } } }
2016年3月2日 星期三
2016年2月22日 星期一
2016年2月21日 星期日
[Codeforces Round #313 (Div. 1) pC][DP] Gerald and Giant Chess
原題連結
本來一直往dp[i][j]=dp[i-1][j]+dp[i][j-1]去想......結果不管怎麼弄都逃離不了O(n^2)XD
最後看了codeforces上的tag寫著combinatorics!
才突然想起高中數學也有教，從(0,0)走到(n,m)的捷徑方法數是C(n+m,m)，這是解這題的其中一個關鍵
本來一直往dp[i][j]=dp[i-1][j]+dp[i][j-1]去想......結果不管怎麼弄都逃離不了O(n^2)XD
最後看了codeforces上的tag寫著combinatorics!
才突然想起高中數學也有教，從(0,0)走到(n,m)的捷徑方法數是C(n+m,m)，這是解這題的其中一個關鍵
2016年2月20日 星期六
2016年2月13日 星期六
2016年1月28日 星期四
2016年1月26日 星期二
[Codeforces 100495A][2014 KTU ACM ICPC Qualification Round][Dijkstra] Crystals
原題連結
注意到因為n很小...所以對於任何一個水晶集合都可以將狀態用一個int表示出來(點)，然後將集合的變換看成狀態的轉移(邊)
那麼本題就可以套用經典的最短路算法解決O(NlogN)，此時N=(2^n)
注意到因為n很小...所以對於任何一個水晶集合都可以將狀態用一個int表示出來(點)，然後將集合的變換看成狀態的轉移(邊)
那麼本題就可以套用經典的最短路算法解決O(NlogN)，此時N=(2^n)
訂閱：
文章 (Atom)