0w1

Entries from 2016-03-17 to 1 day

UVA 11270 Tiling Dominoes ( 輪廓線DP )

UVa Online Judge 訓練指南上的輪廓線DP基本題。一開始看的時候怎樣都看不懂,沈下來想就懂了。要考慮的是放一個 tile不管橫置還是直擺,以當前那個格子為那個 tile的右下角,這種“結束考慮這個格子"的情況當作狀態。那麼如果上面的格子沒有放東西,我們就被…

TOJ 47 1d-kd-tree ( STL map )

TOJ

http://sprout.tw/oj/pro/47/ 題目的要點在於求離一個數距離最小的數,並且支持插入和修改。先考慮如果題目只求正方向距離最小,那其實只是求 lower_bound罷了。加了一個負方向其實也只是要找以該點在數線上對稱的lower_bound。因此我們只需要維護正數和負數…

TOJ 72 Happiness Function ( 三分搜 )

http://sprout.tw/oj/pro/72/ 一個三分搜模板。每次總是縮小至少三分之一的搜索範圍,慢慢走往凹點。 #include <cstdio> int n; double a[10], b[10], c[10]; double S(double t){ double mx = 0; for(int i = 0; i < n; ++i) if(a[i]*(t-b[i])*(t-b[i])+c[i] > mx) </cstdio>…

TOJ 275 同學會 ( Adhoc )

http://sprout.tw/oj/pro/275/ 這題雖然看起來很簡單,卻要想清楚很多細節才能寫好。最重要的關鍵是要發現如何做才能快速地發現那個團體中最後一個人。如果我們對每個團體紀錄 id的總和,剩下的人數,每次減少一個人就從 id總和減去它的 id,就能夠在刪除某…

TOJ 277 騎腳踏車 ( Greedy )

http://sprout.tw/oj/pro/277/ 很明顯如果希望疲累度最大,就不能讓休息站幫我們太多。讓休息站最沒有幫助的方法無疑是連續的,還有一個起點一個終點的情況。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 6; const int MAXA = 1e3 + 3; typedef </bits/stdc++.h>…

CFR 500 B. New Year Permutation ( Greedy + Union Find )

Problem - 500B - Codeforces 如果某兩個數可以交換,那麼可以和那兩個數的任意一個交換的數同樣能和另一個交換,所以我們可以維護一個集合代表當前的位子可以用的數字有哪些。欲處理完就能貪心的由左到右依次選取集合中最小的。 #include <bits/stdc++.h> using namespace </bits/stdc++.h>…

POJ 1456 Supermarket ( Greedy + Union Find )

1456 -- Supermarket 很顯然要從最貴的開始放,而且是放到離他期限最近的時間點。我們需要快速查詢 lastDay[ i ],代表第 i天( 含 )之前最晚的還沒有賣東西的時間,又因為這件事可以指來指去 i.e. lastDay[ 5 ] = 3 AND lastDay[ 3 ] = 1 -> lastDay[ 5 ] = …

CFR 371 D. Vessels ( Union Find )

Problem - 371D - Codeforces 細節需要想一下下,怎麼快速存取下一個非滿的盤子的下標。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; const int MAXA = 1e9 + 9; const int MAXM = 2e5 + 5; int n; int a[ MAXN ], f[ MAXN ]; int m; struct </bits/stdc++.h>…

POJ 1182 Food Chain ( Union Find )

1182 -- 食物链 這題解法我覺得很特別,是要維護哪些情報有相互證明的關係,哪些情報有相互排斥的關係,哪些情報沒有關係。這些都可以透過並查集的一些小技巧解決。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 4; const int MAXK = 1e5 + 5; in</bits/stdc++.h>…

TOI 日記 Day3

今日もまた何もしなかった気がする。朝はJOI春合宿系の問題を色々解こうとしてみたが、手に負えなかった。予選 / 本選のとは全く違うレベルだとしか思えません。 午後は教授が vjudgeで宿題だと出された IOI practice - Virtual Judge グラフ色々簡単な問題…

TimOJ 1671 Anansi's Cobweb ( Union Find + Time Reverse )

1671. Anansi's Cobweb @ Timus Online Judge If we simulate it from the back instead, thinking the original edge destroying operation as adding, it will be possible to solve using elementary union find. #include <bits/stdc++.h> using namespace std; const i</bits/stdc++.h>…