P1
題目描述：
給出一個二分圖，選擇互不相交的邊，使得邊覆蓋的點權和最大。
solution：
簡單DP，用樹狀數組維護最大值。
時間復雜度：$O(n \log n) $
P2
題目描述：
給出N個或黑或白的元素，每個元素有與A集合和B集合相對應的A,B兩個值，將N個元素分成A,B兩個集合，使每個集合的前K大中的黑色元素的總和最大。
solution：
因為每個元素都有兩個關鍵字，而且每個關鍵字只對對應的集合有用，所以必須對其中一個關鍵字進行固定。枚舉A集合的第K大是哪個元素(i)，因為只需要黑色元素總和最大，所以A值比A[i]大的黑色元素都歸到A集合，A值比A[i]小的白色元素也歸到A集合（防止該元素是B集合的前K大）。然后對黑色元素和剩下的白色元素進行DP，狀態f[p][q]表示到前p個元素有q個元素分到了A集合的最大值。
時間復雜度：$ O(n^3) $
P3
題目描述：
給定一棵樹。在線求路徑點序列u -> ... -> v1，連續子序列a1,a2 ... ak滿足a1<a2< ... <aj>aj+1 >aj+2 >.....>ak或者a1>a2>... >aj< aj+1<aj+2<.... <ak，1<=j<=k，求最大的 \(k\)。
solution：
關于樹的算法不多，這題LCA就可以了，只是如何實現合并而已，我們對于LCA的每個區間記12個域：
區間左端：
- 遞增
- 遞減
- 先增后減
- 先減后增
區間右端:
- 遞增
- 遞減
- 先增后減
- 先減后增
- 區間左端編號
- 區間右端編號
- 區間長度
- 最大值
至于轉移方程嘛……，自己推。
時間復雜度：$ O(n \log n) $
P4
題目描述：
給出一個一開始為0的無窮棧，每次從棧頂拿出一個數\(top\)，并把棧里剩下的元素最低位變成$ (Y+1) \mod K \(（Y為之前的最低位），然后用top與L相比，如果\) top < L \(，那么X減一，否則把\)top+AK\(復制K份放入棧中。當\)X=0$時，結束操作，輸出top。
solution：
這題的數據很大，因此應該是找規律的題目。觀察可得，棧里面的數的變化只與出棧次數有關，如果要把棧里的某一個元素出棧，必須經歷s次出棧，而( s%K=1).
令$ L=cAK+d \(，而棧里的數i只可能是\) i=pAK+p,(0\leq p\leq c+1, 0\leq q\leq d) \(因此我們可以尋找循環節。例如\)K=5，L=21，A=2$
這表格包含了所有可能的數字，從縱向來看，它代表某一個數加AK的值，橫向來看，它代表每個數的變化。紅色為死亡瀕臨線。對于第二行（從下向上數）的數來說，必須死13次才能將其出棧，對于第一行來說，必須要死135次才能將其出棧。如果要將第一行的全部出棧，必須死$ 135^2 $次。
再舉一個例子：\(K=5,L=26,A=2\)
對于第三行要5次，第二行(5^2)，第三行(5^3)，……
再利用第一個例子研究答案：
30 31 32 33 34 * 31 32 33 34 30 * 22 23 24 *
31 32 33 34 30 * 22 23 24 * 30 31 32 33 34 *
22 23 24 * 30 31 32 33 34 * 31 32 33 34 30 *
23 24 * 30 31 32 33 34 * 31 32 33 34 30 * 22
24 * 30 31 32 33 34 * 31 32 33 34 30 * 22 2331 32 33 34 30 * 22 23 24 * 30 31 32 33 34 *
22 23 24 * 30 31 32 33 34 * 31 32 33 34 30 *
23 24 * 30 31 32 33 34 * 31 32 33 34 30 * 22
24 * 30 31 32 33 34 * 31 32 33 34 30 * 22 23
30 31 32 33 34 * 31 32 33 34 30 * 22 23 24 *22 23 24 * 30 31 32 33 34 * 31 32 33 34 30 *
23 24 * 30 31 32 33 34 * 31 32 33 34 30 * 22
24 * 30 31 32 33 34 * 31 32 33 34 30 * 22 23
30 31 32 33 34 * 31 32 33 34 30 * 22 23 24 *
31 32 33 34 30 * 22 23 24 * 30 31 32 33 34 *……
規律顯得，
當d<K時，每行有( (d+1)K+(K-d-1) )個元素，每一部分為一行出棧的死亡情況，所以答案的循環節（即整個表格死一次）為( ((d+1)K+(K-d-1))K^c )
算答案時令( t=(d+1)K+(K-d-1) )，把X拆成( X=a_{0}+\sum_{i=1}^{c}a_{i}tK^{i-1} ),通過( (\sum_{i=1}^{c}a_{i})%K )算出答案所在行，再利用( a_{0} )確定列。
當d>=K時，每行有K個元素，所以答案的循環節為( K^(c+2) )，計算答案就想一想好了。
廢話不說（我也解釋不清），上代碼（和鏈接）
wck
lyl
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <queue>
#include <deque>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const LL oo=1e18;int T;
LL X, K, L, A;int main()
{freopen("avenger.in", "r", stdin);freopen("avenger.out", "w", stdout);scanf("%d", &T);while (T--){scanf("%I64d%I64d%I64d%I64d", &X, &K, &L, &A);LL AK=A*K;LL c=L/AK, d=L-AK*c;LL ans=0;if (d>=K-1){--X;for (int i=1; X && i<=c+2; X/=K, ++i)ans=(ans+X%K)%K;printf("%I64d\n", (c+1)*AK+ans);}else{LL t=(d+1)*K+(K-d-1);--X;LL a0=X%t;X/=t;for (int i=1; X && i<=c; X/=K, ++i)ans=(ans+X%K)%K;if (ans<d+1)//the last is in the front最后一行在前{if (a0<(d-ans+1)*K)//the last{LL tmp=a0%K;a0/=K;printf("%I64d\n", (c+1)*AK+(ans+a0+tmp)%K);}else//the last but one倒數第二行{a0-=(d+1-ans)*K;if (a0<K-1-d) printf("%I64d\n", c*AK+d+1+a0);else//the last最后一行{a0-=(K-1-d);printf("%I64d\n", (c+1)*AK+(a0%K+a0/K)%K);}}}else//the last but one is in the front倒數第二行在前{if (a0<(K-d-1)-(ans-d)+1)printf("%I64d\n", c*AK+a0+ans);else//the last最后一行{a0-=(K-d-1)-(ans-d)+1;if (a0<K*(d+1))printf("%I64d\n", (c+1)*AK+(a0/K+a0%K)%K);else//the last but one倒數第二行{a0-=K*(d+1);printf("%I64d\n", c*AK+d+1+a0);}}}}}return 0;
}
