Problem - 131D - Codeforces n個點 n條邊保證聯通，俗稱的水母圖。題目求的是每個點與環的距離，所以用一次 dfs求環，利用 next數組就能夠紀錄並判環。最後再把所有環裡的點拿去做bfs求距離。 #include <bits/stdc++.h> using namespace std; const int MAXN = 3e3 + 3; in</bits/stdc++.h>…

Problem - E - Codeforces 点が全て連結する場合を考えて、辺の数だけ degree = 1の点の数ができるとわかる。つまり、連結成分それぞれについてそれを求めればいい。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; t</bits/stdc++.h>…

Problem - D - Codeforces よく考えると前の方向と今の方向としか関わらない。本番中は難しく考えすぎて偶数奇数まで思考が飛んでタイムオーバー。 レーティングが元から低いから落ちてないし逆に上がった。 次は書き出す前に自信を持って、合ってると確信し…

Problem - 404C - Codeforces The vertex i with dis[ i ] = 0 will be the origin, and if it doesn't exist, or multiple 0 distance vertices exist, there will be no solution. Otherwise iterate through all distances from smaller to larger and ex…

Problem - E - Codeforces The deterministic solution for this problem is quite difficult. However, it is easy to come up with a randomised algorithm. There are primarily 2 types of randomised algorithms, Monte Carlo that runs in a certain t…

Problem - 330B - Codeforces There are n vertices and at most n / 2 - 1 edges. Easy to see that there will be at least one vertex with 0 degree. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 3; const int MAXM = MAXN / 2; int n, m; i</bits/stdc++.h>…

Problem - 329B - Codeforces Let's think about all other trainers try to meet or wait us at the exit. Certainly if one is able to move to the exit before ( or on the same time ) we do, they will battle us. What if not? We will be able to av…

Problem - 377A - Codeforces 逆に連結成分を確保するという角度でやると簡単。 #include <bits/stdc++.h> using namespace std; const int MAXN = 500 + 5; const int MAXM = 500 + 5; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; int n, m, k, </bits/stdc++.h>…

Problem - C - Codeforces 細かいケースが多く、割と面倒くさい。 でもちゃんと考えてたら、実は簡単。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int n, d, h; void solve(){ if( n < h + 1 ) return (void)puts("-1"); // 一直線でやって</bits/stdc++.h>…

Problem - 300B - Codeforces 暴力でやるだけ。実装が下手。 つまらないミスで時間を溶かした。 #include <bits/stdc++.h> using namespace std; const int MAXN = 48 + 2; const int MAXM = MAXN * MAXN / 2; int n, m; vector< int > G[ MAXN ]; struct UnionFind{ int fa</bits/stdc++.h>…

Problem - D - Codeforces Problem in short: Given k arrays of 1 ~ n permutation, find max LCS length Since the final LCS will be in the first array anyways, we can describe the state as dp[ i ] : maximum length of LCS when a[ 0 ][ i ] is th…

Problem - 414B - Codeforces 2D/0D. #include <bits/stdc++.h> using namespace std; const int MAXN = 2000 + 2; const int MAXK = 2000 + 2; const int MOD = 1e9 + 7; int n, k; int dp[ MAXN ][ MAXK ]; // last digit i, length j, possible ways void solve(){ dp[ 1</bits/stdc++.h>…

Problem - 455A - Codeforces First sort and compress the items. Now we will find that if a number x is to be taken, it will only affect that it might be illegal to take x - 1 or x + 1. So it is only possible to transfer to the next state th…

Problem - B - Codeforces Have an extra vector on the dp array for recording the growth of the virus. There will be some kmp failure function like moves being made at the end of the current string, and it is sufficient to describe it with t…

今天中午吃麥當勞就放人了 整個氣氛不太一樣 我想這就是大家口中的二模後崩潰潮吧 不過我覺得我從這次的失敗得到的已經很多了 所以很滿足 已經使出渾身解數 就沒有什麼好愧對的 一路來放棄了很多機會 吃了很多苦 但我還是很慶幸有這些經歷 畢業後的學長還會…

Problem - D - Codeforces Just make clear how one state can transfer to another, it will be easy. #include <bits/stdc++.h> using namespace std; const int MAXM = 2000 + 3; const int MAXP = 2000 + 3; const int MOD = 1e9 + 7; #define rep( i, a ) for( int i =</bits/stdc++.h>…

http://codeforces.com/contest/652/problem/E Shrink each bridge BCC to as a single vertex. If a treasure exists in some BCC, that BCC will be sure able to take that treasure. Otherwise a treasure might be on a bridge linking BCCs, and we wi…

Problem - D - Codeforces Sort by left bound, that scan from left to right, we will query the number of right bounds that are before the right bound of the current segment. After answering the query, the segment should be removed, which wil…

Problem - C - Codeforces 每次即時刪除無用的編號( 因為所有編號相異 )，似乎就能夠均攤解決。 #include <bits/stdc++.h> using namespace std; const int MAXN = 3e5 + 5; const int MAXM = 3e5 + 5; typedef long long ll; int n, m; int p[ MAXN ]; set< int > foe[ MAX</bits/stdc++.h>…

考完二模，我覺得以我來說真的考得挺不錯的，算是有拿該有的分數吧 在考試當下想起來高一校內筆試的那題 學長後來隨便捏的尤拉定理 然後就多40分了 第一次有這種感覺 蠻開心的 嘛 二模考一題數值方法 兩題模逆元也是醉了 不過聽說每年都是這樣 看來我是不能…

今天過得算是挺痛快的，寫了幾個恰到好處的題目，學了幾個蠻有趣的技巧。 下午花了一個小時重開一個User重建編輯環境，真的超棒的! 我的 coding風格這幾天有一些劇變，在實作方面增強很多 接下來就是多做思考為主的題目，學習不怕寫 200行的 code 覺得 IOI題…

Problem - D - Codeforces It is well known fact that only the adjacent elements would have the maximum slope. Making use of this fact, we can always find the maximum slope, find all subsequences it will contribute to, then apply divide and …

Problem - C - Codeforces It's easy to see it is a complete graph, which means there exists exactly one path that could carry one from the start to the end. So the actual answer is quite simple, the maximum among the two shortest paths. Def…

Problem 1036. -- [ZJOI2008]树的统计Count このテクすごいね、猛練習しよう。 #include <bits/stdc++.h> using namespace std; const int MAXN = 3e4 + 4; const int MAXQ = 2e5 + 5; const int INF = 0x3f3f3f3f; int n; vector< int > es[ MAXN ], bes[ MAXN ]; int par[</bits/stdc++.h>…

Problem 1833. -- [ZJOI2010]count 数字计数 Given a ≤ 1e12, b ≤ 1e12, find frequency for each digit in range [ a , b ]. dp[ i ][ j ][ k ]: chose i digits, less flag, not zero Note that when transferring, we are to add the number of ways of i…

PEG Judge - NOI '12 - Random Number Generator www.2cto.com See the formulae here. What's particularly interesting in this problem is that it might cause overflow when calculating the product for some long long integers. However, here again…

UVa Online Judge Range Sum Query の基礎問題を平方分割で処理した。 ncastar.hatenablog.com この記事が大変参考になりました。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; int kase; int n; int a[ MAXN ]; int BS; vector< int > bucket</bits/stdc++.h>…

Problem - E - Codeforces 第一次寫平方分割，不太習慣。這題的關鍵在於維護一些值，使得可以O( 1 ) 完成一個塊的查詢。操作也要逆著做回來( 由右到左 ) 才會正確。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; in</bits/stdc++.h>…

http://sprout.tw/oj/pro/101/ 顯然就是二分圖。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 2 * MAXN; int n; vector< int > G[ MAXN ]; void init(){ for(int i = 0; i < n; ++i) G[ i ].clear(); } int col[ MAXN ]; bo</bits/stdc++.h>…

今天早上忠毅學長來看我，超感動QQ 聊了蠻久，被鼓勵了很多，還被說什麼覺得高一就應該要進的XDDD 我不太相信 不過還是很開心 學長聽說也過得不差，只是有點頹廢什麼的，一學期12學分，外語被當 現在學長是資芽的python講師，我之後閒著有空也想去A掉一些水…