oToToT的code收藏區

題目連結: http://poj.org/problem?id=1067 我通靈不出來，盯了他一個晚上只發現對於每個$i$都有一個$j$使他慘掉(?，而且似乎有個1.6左右的比例，但我就不會了QAQ 正解是這個： 威佐夫遊戲 結論就是只要看符不符合$i 我缺少知識QQ #include <iostream> #include <cmath> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); long double TongLing = (sqrt((long double)5)+1)/2; int n, m; while(cin>>n>>m){ if(n > m) swap(n, m); cout << ((int)((m-n)*TongLing) != n) << '\n'; } return 0; }

題目連結: http://poj.org/problem?id=3233 其實看到的時候以為是要用等比級數的公式，可是馬上就發現兩個會慘的點1.不保證有反矩陣, 2.不保證有些東西模m有反元素。後來被提示了才知道原來其實是用DP的想法找的轉移矩陣，然後對他快速冪。稍微列一下式就會得到$ \begin{bmatrix} S_i \\ A_i \end{bmatrix} = \begin{bmatrix} I \cdot S_{i-1}+A \cdot A_{i-1} \\ 0 \cdot S_{i-1}+A \cdot A_{i-1} \end{bmatrix} = \begin{bmatrix} I & A \\ 0 & A \end{bmatrix} \cdot \begin{bmatrix} S_{i-1} \\ A_{i-1} \end{bmatrix} $，所以就照著這個跑就好了。 #include <iostream> using namespace std; const int N = 60 + 2; int (*A)[N] = new int[N][N]; int (*Mtx)[N] = new int[N][N]; int (*Temp)[N] = new int[N][N]; int (*Ans)[N] = new int[N][N]; int (*Res)[N] = new int[N][N]; int n, m, n2; inline void mTimes(int[N][N],int[N][N],int[N][N],int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int k; cin>>n>>k>>m; n2 = n<<1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>A[i][j]; for...

題目連結: http://poj.org/problem?id=2104 裸的區間第K大值，曾經會過可是又忘記了，只記得關鍵字持久化，被雷了才知道。原來就是原本的序列第K大是直接用樹上的節點作二分搜，但是區間的話就變成要用$[L,R]$的和做節點二分搜，而要算$[L,R]$的和，其實就用持久化線段樹把$roots[R]-roots[L]$即可。 #include <iostream> #include <vector> #include <algorithm> #include <cassert> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100000 + 5; const int MEM = 2000000; class LiSan{ private: vector<int> v; public: inline void init(){v.clear();} inline void insert(int x){v.PB(x);} inline int size(){return v.size();} inline void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } inline int get(int x){ return distance(v.begin(), lower_bound(ALL(v), x)); } inline int inv_get(int x){return v[x];} } lisan; ...

題目連結: http://poj.org/problem?id=1769 一開始用cin有把連結斷開還是吃了個TLE QQ。 回到正題，本題我個人的一開始的想法其實是看看某個線段插到線段樹後可以幹嘛，後來想一想後發現有點DP的fu，狀態大概就是$dp[i]$為最遠轉移到i時的最小值，那新增一條線段的時候其實就是查$[l,r]$之間的最小值，然後把$r$那個點設成先前查到的最小值+1，因為$\displaystyle dp[i] = \min_{l \leq j \leq r}dp[j]+1 $，不過實際在寫的時候要再跟原值取個min，因為有可能r被覆蓋很多次之類的。 #include <cstdio> #include <algorithm> using std::min; const int N = 50000 + 10; const int INF = 1<<30; class SegTree{ private: int nodes[N<<2], size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} void build(int l, int r, int id){ nodes[id] = INF; if(r-l>1){ int mid=(l+r)>>1; build(l, mid, lc(id)); build(mid, r, rc(id)); } } void modify(int ql, int qr, int v, int l, int r, int id){ if(qr <= l o...

題目連結: http://poj.org/problem?id=3468 裸的線段樹，區間加值、區間查和，不過也可以用BIT做掉，不過我不太會QQ #include <iostream> #include <utility> using namespace std; typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 100000 + 5; class SegTree{ private: PLL nodes[N<<2]; int size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} inline void push(int l, int r, int id){ if(r-l>1){ nodes[lc(id)].FF += nodes[id].FF; nodes[rc(id)].FF += nodes[id].FF; } nodes[id].SS += nodes[id].FF * (r-l); nodes[id].FF=0; } inline void pull(int l, int r,int id){ int mid=(l+r)>>1; lld ll = nodes[lc(id)].SS+nodes[lc(id)].FF*(mid-l); lld rr =...

題目連結: http://tioj.infor.org/problems/1448 / http://poj.org/problem?id=1182 經典的並查集應用，想法大概就跟並查集的大多數用途一樣，考慮把每個動物X分三種類型$X_A, X_B, X_C$，代表若X為A的情況或X為B的情況...，那要兩種動物$X, Y$為同一種的話合併的話，顯然就是合併$X_A \equiv Y_A, X_B \equiv Y_B, X_C \equiv Y_C$，吃的話則是$X_A \equiv Y_B, X_B \equiv Y_C, X_C \equiv Y_A$，這樣的話要判斷是否為假話的話就變容易了，仔細想想會發現不可能有一種動物$X$，他在某次操作後$X_A \equiv X_B \lor X_B \equiv X_C \lor X_C \equiv X_A$，所以只要操作前看看沒有要合併的人他的集合是不是原本就一樣就好。 p.s POJ上範圍不太一樣，這裡是TIOJ的範圍(而且動態配置貌似POJ會TLE) #include <bits/stdc++.h> using namespace std; #define FAKE ans++;continue; const int N = 500000; class DJS{ private: int *arr; public: void init(int T){ arr=new int[T]; for(int i=0;i<T;i++) arr[i]=i; } void merge(int a, int b){ arr[query(a)]=query(b); } int query(int x){ if(arr[x]!=x) arr[x]=query(arr[x]); retur...