oToToT的code收藏區

題目連結: http://codeforces.com/problemset/problem/839/D 超級無敵久沒寫blog了，記錄一下這題好了，我過然數學還是不太好QQ 首先我們可能會想要對每個gcd都計算答案，那這時候我們可能會想知道有可能對這個gcd有貢獻的人會有誰，所以不妨先計算好有多少個數字含有因數$i$。那接著我們就直接計算總長度，對於每個因數$i$計算$\sum_{j=0}^{cnt[i]} j\cdot \binom{cnt[i]}{j}$但是這樣會重複計算到太多人，所以要扣掉他的2倍、3倍....的答案，而要算答案的時候則再乘上$i$即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; const int C = 1000000 + 5; const int MOD = 1000000007; int arr[N], cnt[C]; lld ans[C], two[N]; int main(int argc, char* argv[]){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; two[0] = 1; for(int i=1;i<n;i++) two[i] = two[i-1]*2 % MOD; for(int i=0;i<n;i++){ cin>>arr[i]; cnt[arr[i]]++; } for(int i=1;i<=C;i++) for(int j=2;j*i<=C;j++){ cnt[i] += cnt[i*j]; } lld ret = 0; for(int i=C;i>=2;i--){ if(cnt[i]==0) continue; ans[i] = cnt[i] * two[cnt[i]-1] % MOD; for(int j=2;j*i<=C;j++) ans[i] = (ans[i]-ans[j*i]+MOD)%MOD; ret = (ret + i*ans[i]%MOD) % M

題目連結: http://codeforces.com/problemset/problem/894/D 看了題解又問了人才會這題QAQ 本題作法我覺得好暴力(?，首先要觀察出這題第$i$條邊固定連接$ \lfloor \frac{i+1}{2} \rfloor $跟$i+1$的話，那給定的這棵樹就一定會是一棵完滿二元樹，深度必定為$\log_2(n)$，接著我們要預處理這棵樹，把每個點到其子樹們（包含自己）的距離算出來並排序好（這裡可以用merge sort的merge方法把兩棵子樹merge好），那我們要查詢的時候就只要往上走，並把我另外一邊的子樹可以走到的節點們通通加起來就好了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define SZ(x) ((int)(x).size()) #define ALL(x) begin(x), end(x) typedef pair<lld,int> PLI; #define FF first #define SS second const int N = 1000000 + 5; vector<lld> dis[N], sum[N]; lld len[N]; void build(int,int); lld go(int,lld,int); PLI get_val(int,lld); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, q; cin>>n>>q; for(int i=2;i<=n;i++) cin>>len[i]; build(1, n); while(q--){ int w, l; cin>>w>>l; cout<<go(w, l, n)<<'\n'; } return 0; } void build(int id, int mx){ if(id > mx) return; const int lc = id*

題目連結: http://codeforces.com/problemset/problem/675/C 想了很久才知道方向錯了QAQ 作法是枚舉每個人往右邊推過去(可以證明只要枚舉所有人往右走就一定是好的)，那仔細觀察就會發現我們要省幾個就是看我們走過來有幾個前綴為零，而枚舉每一個人做開頭的時候其實我們就是問一直把最後的放到前面，也就是把前面加值，最後一個減值接著再查一下有幾個0就好了XD #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 100000 + 5; map<lld,int> cnt; lld arr[N]; int main(int argc, char* argv[]){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; lld cur = 0; for(int i=0;i<n;i++){ cin>>arr[i]; cur += arr[i]; cnt[cur]++; } int ans = n-cnt[0]; cnt[0]--; for(int i=n-1;i>=0;i--){ cur -= arr[i]; ans = min(ans, n-cnt[cur]); } cout<<ans<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/798/D 很久以前比賽的時候沒寫出來，最近又再想還是想不到，只好去看題解QQ 大致的想法是，會發現對於$a$我們其實只要在$a$的任意排列的裡面選$a_{2i}$跟$a_{2i+1}$中比較大的人的index，那加起來就一定會夠。但是如果只是無腦的這樣挑很有可能$b$不會符合，所以不妨想想我們把$a$排序一下，並且一定選第一個，接著看相對映的$b$哪個index比較大，就挑他，這樣的話因為$b$一定是好的(跟前面講的一樣)，而$a$若是每次都挑到比較小的那個也不會爛，因為我們已經挑了最大的那個(可以想像成$a$是從$0$開始挑比較大的，$b$是從$1$開始挑比較大的之類的)。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; int a[N], b[N], p[N], ans[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; for(int i=0;i<n;i++) p[i]=i; sort(p, p+n, [](int x, int y){ return a[x] > a[y]; }); cout<<n/2+1<<'\n'; ans[0] = p[0]; for(int i=1;i<n;i+=2){ if(b[p[i]] > b[p[i+1]]) ans[(i+1)/2] = p[i]; else ans[(i+1)/2] = p[i+1]; } if(n%2==0) ans[n/2] = p[n-1]; for(int i=0;i<n/2+1;i++) cout<<ans[i]+1<<" \n"[i==n/2]; return 0; }

題目連結: http://codeforces.com/problemset/problem/877/E 把樹壓扁後題目就轉化成有一個01序列，並且有兩種操作：查詢區間和跟把區間的bit反轉。稍微想一下會發現線段樹可以好好做他，所以就用線段樹維護一下就好了。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,bool> PIB; #define FF first #define SS second const int N = 200000 + 5; class SegTree{ private: PIB nodes[N<<2]; int n; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} inline void push(int l, int r, int id){ if(!nodes[id].SS) return; nodes[id].FF = r-l - nodes[id].FF; if(r-l > 1){ nodes[lc(id)].SS ^= nodes[id].SS; nodes[rc(id)].SS ^= nodes[id].SS; } nodes[id].SS = 0; } inline void pull(int l, int r, int id){ int val = 0, mid = (l+r)>>1; if(nodes[lc(id)].SS) val += mid-l-nodes[lc(id)].FF; else val += nodes[lc(id)].FF; if(nodes[rc(id)].SS) val += r-mid-nodes[rc(id)].FF; else val += nodes[rc(id)].FF; nodes[id].FF = val; } void build(int l, int r, int id, int arr[]){

題目連結: http://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d 賽中唬爛了一個爛DP，很正常的TLE掉，賽後看著Editorial還是看不懂，只好去問別人QQ。 我用editorial的方式講一下好了：我們定義一種hash值$h(\text{str})=\sum_{i=0}^{26}2^i \cdot (sum(i) \mod 2)$其中$sum(i)$代表字元$i$出現幾次。這樣的話，我們會發現如果$\text{str}$是回文，若且唯若$h(\text{str})$是二的冪次或零(因為出現次數為奇的最多只能有一個)，接下來我們幫$\text{str}$的前綴算好hash值($h_i$代表$[0, i)$的hash值)，而另外一個小發現則是發現要算$\text{str}$中$[l, r)$的hash值，我們只要計算$h_l \oplus h_r$就好了。 那現在我們可以開始DP了，我們狀態是$dp[i]$代表$[0, i]$中我們至少要切幾段才能使得每塊都可以變回文，那我們會發現其實就是要找到最小的$dp[j]$使得$h_j \oplus h_i$是二的冪次或零，那這時我們再DP另外一個數字$val[S]$代表當$a_i=S$的最小$dp[i]$值，而因為xor的特性，我們只要枚舉$val[a_i], val[a_i \oplus 2^0], val[a_i \oplus 2^1] \cdots val[a_i \oplus 2^25]$就可以得到答案了(因為$(A \oplus B) \oplus A = B$)，而得到答案後記得再更新一下$val[a_i]$即可。 #include <bits/stdc++.h> using namespace std; const int N = 200000 + 5; const int INF = 1<<30; string ss; int dp[1<<26], ans[N]; int main(){ cin>>ss; int n = ss.size(), cur = 0; fill(dp, dp+(1<<26), INF);

題目連結: http://tioj.infor.org/problems/1152 裸的樹直徑題，那樹直徑要怎麼做呢?有個greedy的做法:先隨便從一個點DFS下去，走到最遠的地方後，再從那個點DFS下去走到離他最遠的點，則這兩個點中間的路徑就會是直徑。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int N = 10000 + 5; vector<int> G[N]; void dfs(int,int,int,PII&); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int x; while(cin>>x and x!=-1){ G[i].PB(x); G[x].PB(i); } } PII ans = {0, -1}; dfs(0, 0, 0, ans); ans.SS = -1; dfs(ans.FF, ans.FF, 0, ans); cout<<ans.SS<<'\n'; return 0; } void dfs(int w, int f, int sum, PII& ret){ if(sum > ret.SS) ret = {w, sum}; for(auto i: G[w]){ if(i==f) continue; dfs(i, w, sum+1, ret); } }

題目連結: http://tioj.infor.org/problems/1221 或 POI XII Toy Cars 我不知道怎麼證明QAQ... 總之做法就是要移掉東西的時候，就挑接下來最晚出現的移掉。而要維護誰最晚出現我這裡是開個陣列先預處理好對於每個$i$，紀錄下一個跟他一樣的數字是在哪裡。而接著掃過去的時候，每走到一個地方，就把這個地方的更新掉，這要樣pop東西的時候就可以拿到最新的資訊了。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define FF first #define SS second const int N = 500000 + 5; const int M = 100000 + 5; map<int,int> mp; int nxt[N], tmp[M], arr[N]; bool ins[M]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, k, p; cin>>n>>k>>p; for(int i=0;i<p;i++) nxt[i] = p+i; for(int i=0;i<=n;i++) tmp[i]=-1; for(int i=0;i<p;i++) cin>>arr[i]; for(int i=0;i<p;i++){ if(tmp[arr[i]]!=-1) nxt[tmp[arr[i]]] = i; tmp[arr[i]]=i; } int size = 0, ans = 0; for(int i=0;i<p;i++){ if(!ins[arr[i]]){ if(size == k){ ins[mp.rbegin()->SS]=0; size--; mp.erase(mp.rbegin()->FF); } ans++; mp.insert({nxt[i], arr[i]}); ins[arr[i]]=1; size++; } if(mp.find(i)==mp

題目連結: http://codeforces.com/problemset/problem/731/D 我覺得我的作法感覺不太對(?但還是講一下好了 我的做法是先把大小關係建成一張DAG，而這樣的話會發現題目變成說可不可以找到一種拓樸排序方法使得序列會是循環的字串，而又已經知道循環其實就只有可能中間斷開一個而已，所以我們不妨找到中間斷開的那個關係，並追本朔源到最前面的那個，從他開始拓樸排序，看會不會是好的。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define FF first #define SS second const int N = 500000 + 5; const int C = 1000000 + 5; class DJS{ private: vector<int> arr; public: inline void init(int n){ arr.resize(n); for(int i=0;i<n;i++) arr[i]=i; } int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(int a, int b){ int u = query(a), v = query(b); arr[max(u, v)]=min(u, v); } } djs; vector<int> G[C], cur; int in[C]; inline void kill(){cout<<"-1\n";exit(0);} int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, c; cin>>n>>c; djs.init(c+1); int sz; cin>>sz; for(int j=0;j<sz;j++){ int x; cin>>x; cur.PB(x); } int l

題目連結: http://codeforces.com/problemset/problem/761/E 一開始以為邊長只能是一www 會發現節點才30個，那我們可以簡單的安排每個深度的邊長$2^{55-d_i}$這樣的話，因為$\sum_{i=0}^{n-1}2^i < 2^n$，所以絕對不會疊在一起，而且最大也就$2^{56} \leq 10^{18}$長度。接著就DFS下去把邊安排一下就好了XD #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 30 + 5; lld dx[]={0, 0, 1, -1}, dy[]={1, -1, 0, 0}; int inv[]={1, 0, 3, 2, 5}; vector<int> G[N]; PLL ans[N]; int dep[N]; void dfs(int,int,int,PLL); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } bool flag = false; for(int i=1;i<=n;i++) if(G[i].size() > 4){ flag = true; } if(flag){ cout<<"NO\n"; return 0; } cout<<"YES\n"; dep[1] = 0; dfs(1, 1, 4, {0LL, 0LL}); for(int i=1;i<=n;i++) cout<<ans[i].FF<<" "

題目連結: http://codeforces.com/problemset/problem/735/C 我覺得這其實滿有趣的(?，我自己是半猜出跟費式數列有關，感覺好像是要找到最大的$i$使得$\sum_{j=0}^{i}F_j \leq n$，但一直不知道為什麼。看了題解才知道原來其實就是我們想想看如果要贏$n$場比賽，那勢必自己要贏$n-1$場，並且找一個贏過$n-2$場的人來打會最好，所以就得到$F_n = F_{n-1}+F_{n-2}$的費式數列公式了XDD。 #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); long long n; cin>>n; long long prepre = 0, pre=1, cnt = 0; int ans; for(ans=0;cnt<n;ans++){ long long cur = prepre+pre; prepre=pre; pre=cur; cnt+=prepre; cerr<<cnt<<'\n'; } cout<<ans-1<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/383/D 某種進階版的加減問題(?，原本的加減問題DP式大概長得像$dp[i][j] = dp[i-1][j+a_i]+dp[i-1][j-a_i]$之類的，而現在變成可以從任意時間點開始的話就除了原本的方法，還多了兩種:$dp[i][a_i]$跟$dp[i][-a_i]$ #include <bits/stdc++.h> using namespace std; const int C = 10000 + 5; const int N = 1000 + 5; const int MOD_BASE = 1000000007; #define dp(i, j) way[(i)][(j)+C] int way[N][2*C]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; for(int j=10000;j>=-10000;j--){ if(j+x <= 10000) dp(i, j) += dp(i-1, j+x); if(j-x >= -10000) dp(i, j) += dp(i-1, j-x); dp(i, j) %= MOD_BASE; } dp(i, x)++; dp(i, -x)++; } int sum = 0; for(int i=1;i<=n;i++) sum = (sum+dp(i, 0))%MOD_BASE; cout<<sum<<'\n'; return 0; }

題目連結: http://codeforces.com/contest/842/problem/C 一直以為因數個數會太多，所以只打算枚舉質因數.... 但其實直接枚舉因數，然後看看哪個因數個數有超過n-1個之類的就好，枚舉完後把他插進去，讓下面的人來看。(頭痛，有點不知所云OAO #include <bits/stdc++.h> using namespace std; #define PB push_back const int C = 200000 + 5; const int N = 200000 + 5; vector<int> frac[C], G[N]; int arr[N], ans[N], cnt[C]; void sieve(int); void dfs(int,int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); sieve(C); int n; cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=1;i<n;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } dfs(1, 1, 0, 0); for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n]; return 0; } void sieve(int n){ for(int i=2;i<n;i++) for(int j=i;j<n;j+=i){ frac[j].PB(i); } } void dfs(int w, int f, int g, int d){ auto& ret = ans[w]; for(auto i: frac[arr[w]]){ if(cnt[i] >= d-1) ret = i; cnt[i]++; } ret = max(ret, g); g = __gcd(g, arr[w]); for(auto i: G[w]

題目連結: http://codeforces.com/problemset/problem/735/D IOICamp的時候有提到這題，不過我其實已經忘了結論了www 去翻了一下才知道原來是跟哥德巴赫猜想有關，其猜想簡而言之就是說對於任意一個大於二的偶數，都可以拆成兩個質數相加。所以我們這題的做法就是先看看給定的數是不是質數，如果是當然就輸出1，接下來看他是不是偶數，是的話那根據歌德巴赫猜想，答案應該會是2，而對於一個奇數，我們要先看看他減二是不是質數，是的話輸出2，不是的話輸出3，因為對於一個奇數他一定是拆成一個質數加一個偶數，然後偶數拆成兩個質數，但要是拆出來的偶數是二，那答案就變成2了。 p.s. 附個維基上哥德巴赫猜想的條目 https://zh.wikipedia.org/wiki/哥德巴赫猜想 #include <bits/stdc++.h> using namespace std; bool isprime(int n){ for(int i=2;i*i<=n;i++){ if(n%i==0) return false; } return 1; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; if(isprime(n)) cout<<1<<'\n'; else if(n%2==0 or isprime(n-2)) cout<<2<<"\n"; else cout<<3<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1721 往右往左各分別維護一個遞減的stack，而若是塞入的東西比較大，則就把比他小的全部pop掉，同時也保證他們都只能看到這裡。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int N = 100000 + 5; int arr[N], ans[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ for(int i=0;i<n;i++) cin>>arr[i]; stack<PII> ss; for(int i=0;i<n;i++){ while(!ss.empty() and ss.top().FF <= arr[i]){ ans[ss.top().SS] = i-ss.top().SS+1; ss.pop(); } ss.push({arr[i], i}); } while(!ss.empty()){ ans[ss.top().SS] = n-ss.top().SS; ss.pop(); } for(int i=n-1;i>=0;i--){ while(!ss.empty() and ss.top().FF <= arr[i]){ ans[ss.top().SS] += ss.top().SS-i; ss.pop(); } ss.push({arr[i], i}); } while(!ss.empty()){ ans[ss.top().SS] += ss.top().SS; ss.pop(); } for(int i=0;i<n;i++) cout<<ans[i]<<" \n"

題目連結: http://tioj.infor.org/problems/1610 乍看之下還以為是什麼奇怪的樹題，結果其實是個簡單的greedy題。 應該不難看出我們其實可以把船亂排、木板亂排，而答案會是$\sum_{i=0}^{n-1} L_i \sum_{j=0}^{i} W_j$，稍微觀察後會發現其實我們由小拿到到，然後木板由長的接到短的會是好的，因為你若拿了比較多再走長的一定會消耗較多體力。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 20000 + 5; lld arr[N], woo[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i]; for(int i=1;i<n;i++) cin>>woo[i]; sort(arr, arr+n); sort(woo+1, woo+n, [](lld a, lld b){return a>b;}); lld cur = arr[0], ans = 0; for(int i=1;i<n;i++){ ans += cur*woo[i]; cur += arr[i]; } cout<<ans<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1589 很明顯的可以知道到一個點的方法數，就是到所有連到他的人的方法數加起來，所以我們可以用類似DP的方法記錄從起點到每個點的方法數，而DP順序就按照拓樸排序就好了XD #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; const int N = 250 + 5; vector<int> G[N]; lld way[N]; int in[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int vv, ee, m; cin>>vv>>ee>>m; for(int i=0;i<ee;i++){ int u, v; cin>>u>>v; G[u].PB(v); in[v]++; } int st, ed; cin>>st>>ed; way[st]=1; queue<int> qq; for(int i=0;i<vv;i++) if(in[i]==0) qq.push(i); while(!qq.empty()){ int u = qq.front(); qq.pop(); for(auto v: G[u]){ way[v] = (way[v]+way[u])%m; in[v]--; if(in[v]==0) qq.push(v); } } cout<<way[ed]<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/864/E 只感覺應該是DP，而且東東的順序會有影響，但是完全不知道該用何種順序來DP，看了tutorial才知道原來要按照消失時間來DP。 tutorial中其實並未給出證明，不過下面有人表示「如果你不先挑那些會先消失的人，那很有可能他待會就消失了(當然挑他要是有助益的)」，想了想我自己是覺得說，如果你可以先挑比較晚消失的人，再挑比較早消失的人，那你也一定可以先挑早消失再挑晚消失的，但反過來的挑法就不一定了。 那所以就按照那個順序排好序後，這題就變得類似於背包問題了，所以我們就可以跟背包一樣，用加入東東的方是想，每次加入一個物品就是在那些可行的範圍中往後加值之類的。 #include <bits/stdc++.h> using namespace std; const int N = 100 + 5; const int M = 2000 + 5; struct Obj{ int t, d, p; int id; inline bool operator<(const Obj &x) const { return d < x.d; } } arr[N]; int sum[M]; vector<int> ori[M]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ cin>>arr[i].t>>arr[i].d>>arr[i].p; arr[i].id = i+1; } sort(arr, arr+n); for(int i=0;i<n;i++){ for(int j=arr[i].d-1;j>=arr[i].t;j--){ if(sum[j] < sum[j-arr[i].t]+arr[i].p){ sum[j] = sum[j-arr[i].t]+arr[i].p; ori[j] = ori[j-arr[i].t]; ori[j].push_bac

題目連結: http://codeforces.com/problemset/problem/802/M 沒敘述的題目www 但其實應該不難猜到就是輸出前k小數字的和。 #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); priority_queue<int,vector<int>,greater<int>> pq; int n, k; cin>>n>>k; for(int i=0;i<n;i++){ int x; cin>>x; pq.push(x); } int ans = 0; for(int i=0;i<k;i++){ ans += pq.top(); pq.pop(); } cout<<ans<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/721/C 莫名其妙吃了MLE，只好把int改short, long long改int = = 本題的做法滿DP的，我狀態直接訂成$dp[i][j]$代表起點到$i$號節點，經過$j$個中繼點所需的最短時間，而DP的順序就按照圖的拓樸排序順序DP就可以好好DP了，不過要注意的是起點有可能不會是拓樸排序的第一個點，所以要稍微判一下... #include <cstdio> #include <vector> #include <utility> #include <stack> #include <queue> using namespace std; typedef long long lld; #define PB push_back typedef pair<short,int> PSI; typedef pair<short,short> PSS; #define FF first #define SS second const int N = 5000 + 5; const int INF = 1<<30; short in[N]; int dp[N][N]; PSS ori[N][N]; vector<PSI> G[N]; int main(){ short n, m;int t; scanf("%hd%hd%d",&n,&m,&t); fill(dp[0], dp[n]+n+1, INF); for(int i=0;i<m;i++){ short u, v; int c; scanf("%hd%hd%d",&u,&v,&c); G[u].PB({v, c}); in[v]++; } queue<short> qq; for(int i=1;i<=n;i++) if(in[i]==0){ ori[i][1] = {-1, -1}; dp[i][1] = 0; qq.push(i); } // ori

題目連結: http://tioj.infor.org/problems/1995 噁爛的壓常數題，吳勝福居然原本官方解答是自己手寫3bytes整數，有夠可怕，好加在鄭天鈞夠聰明，讓我們免於這種可怕的地獄。 他的做法是建立一個Sparse Table，然而我們會發現我們正常sparse table會用掉$O(n log n)$記憶體的原因是因為我們要可以應付在線詢問，然而像這題離線的其實可以用$O(n)$的記憶體就好了，而少掉那$logn$也可簡單，就是你每次用完一條就丟掉，因為建立某一條的時候就可以把符合那條區間的詢問全部算好。此外我這裡因為沒把詢問排序好是因為若排序好就要多一條的記憶體來記錄原本誰是誰，所以只好讓詢問退化成$logN$，每建好一條就把所有詢問檢查過一遍。 #include <cstdio> #include <algorithm> using namespace std; const int N = 2500000 + 1; const int M = 1000000 + 1; int L[M], R[M], arr[N]; int main(){ int n, m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&L[i],&R[i]); L[i]--; R[i]--; } for(int i=0;i<n;i++) scanf("%d",&arr[i]); for(int j=0;(1<<j)<=n;j++){ for(int q=0;q<m;q++){ if(R[q]==-1) continue; int logN = 31-__builtin_clz(R[q]-L[q]+1); if(j!=logN) continue; L[q] = max(arr[L[q]], arr[R[q]-(1<<logN)+1]); R[q] = -1; } for(int i=0;i+(1<<(j+1)) <= n;i++){ arr

題目連結: http://tioj.infor.org/problems/1021 這裡每個狀態存的是在這個狀態下有幾個k出現，而若現在再加一個k就是再加入前面數字的數量，所以我還先算了一下每個情況數字的數量。(我不太會數位DP，講的可能不是很好OAO #include <bits/stdc++.h> using namespace std; typedef long long lld; const int LogN = 10 + 5; int dig[LogN], k, step; lld cnt[LogN][2][2], dp[LogN][2][2]; int cnted[LogN][2][2], dped[LogN][2][2]; lld calc(int,bool,bool); lld go(int,bool,bool); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n>>k){ step++; int logN; for(logN = 0;n>0;logN++){ dig[logN] = n%10; n/=10; } calc(logN, 0, 0); cout<<go(logN, 0, 0)<<'\n'; } return 0; } lld calc(int pos, bool any, bool start){ if(pos < 0){ cnt[pos+1][any][start]= start; return start; } if(cnted[pos+1][any][start] == step) return cnt[pos+1][any][start]; cnted[pos+1][any][start] = step; auto& ret = cnt[pos+1][any][start]; ret = 0; for(int i=0;i<10;i++){ if(!any and i > dig[pos]) break; ret += calc(pos-1,

題目連結: http://tioj.infor.org/problems/1561 原來本題是嚴格次短路徑= = 寫個奇怪的SPFA，除了算最短路徑以外也同時算個次短路徑，而要算最短路徑就枚舉一下當前拿來鬆弛他人的點的第一或第二短路徑，看看他可不可以讓原本的次短更短，但同時也不能比原本的短 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int INF = 1<<29; const int N = 100 + 5; vector<PII> G[N]; PII dis[N]; bitset<N> inq; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; while(cin>>n>>m){ for(int i=0;i<n;i++) G[i].clear(); fill(dis, dis+n, (PII){INF, INF}); inq.reset(); for(int i=0;i<m;i++){ int u, v, c; cin>>u>>v>>c; G[u].PB({v, c}); G[v].PB({u, c}); } int st, ed; cin>>st>>ed; dis[st].FF=0; queue<int> SPFA; inq[st]=1; SPFA.push(st); while(!SPFA.empty()){ int u = SPFA.front(); SPFA.pop(); inq[u]=0; for(auto i: G[u]){ int v = i.FF, c = i.SS; if(dis[v].FF > dis[u].FF+c){ dis[v].SS = dis[v].

題目連結: http://codeforces.com/contest/855/problem/C 賽中看到一堆大大們都寫出來的題目，但是自己怎麼寫都寫不出來就是了QQ，一定是因為我DP太爛的緣故 總之這題很明顯就是個樹DP題，狀態這裡是定成$$ dp[i][x][0] := 第i個節點放[1,k-1]種類且有x個k的方法數 \\ dp[i][x][1] := 第i個節點放k且有x個k的方法數 \\ dp[i][x][2] := 第i個節點放[k+1,M]且有x個k的方法數 $$轉移的話就算滿好想的了，大致就是0號可以從0,1,2轉來；2只能從0轉來；ㄉ可以從0, 2轉來，而怎麼轉就直接枚舉其中一邊有幾個就好了。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; const int N = 100000 + 5; const int K = 10 + 2; const int MOD_BASE = 1e9+7; int n, m, k, x; lld dp[N][K][3]; vector<int> G[N]; void dfs(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } cin>>k>>x; dfs(1, 1); lld ans = 0; for(int i=0;i<=x;i++){ ans=(ans+dp[1][i][0])%MOD_BASE; ans=(ans+dp[1][i][1])%MOD_BASE; ans=(ans+dp[1][i][2])%MOD_BASE; } cout<<ans<<'\n'; return 0; } void dfs(int w, int f){ dp[w

題目連結: http://tioj.infor.org/problems/1997 校內複賽的時候只喇到$k \leq 3$的測資，不過感覺這題是DP，只是賽中一直想不太出來，後來被雷了才知道這題的做法... 狀態設成$dp[i][j]$代表用前$i$個湊出$j$組的最大值可能為多少，而很明顯知道若是現在再加一個數，可以選擇的就是變成$dp[i+1][j+1]$或$dp[i+1][j]$，所以就照著這DP下去就好了，然後記得判一下奇偶之類的。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<int,int> PII; #define FF first #define SS second const int N = 1000000 + 5; const lld INF = 1LL<<40; int arr[N]; lld dp[N][7]; PII ori[N][7]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>arr[i]; fill(dp[1], dp[n]+7, -INF); dp[1][1]=arr[1]; for(int j=1;j<=k;j++){ for(int i=j;i<n;i++){ if(j&1){ if(dp[i][j]+arr[i+1] > dp[i+1][j]){ dp[i+1][j] = dp[i][j]+arr[i+1]; ori[i+1][j] = {i, j}; } if(i >= j and dp[i][j]-arr[i+1] > dp[i+1][j+1]){ dp[i+1][j+1] = dp[i][j]-arr[i+1]; ori[i+1][j+1] = {i, j}; } }else{ if(dp[i][j]-arr[i+1

題目連結: http://codeforces.com/problemset/problem/731/F 惹...原來可以暴力做。直接枚舉每個人$i$當作leader時的情況，而計算時就是要算$[ik, i(k+1))$的數字數有幾個，因為在這區間的數字$a$再扣完之後一定都變成$ik$。此外枚舉倍數是$nlogn$的(某種調和級數的想法)，所以就照著做囉(? #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; lld sum[N]; bool isok[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int x; cin>>x; sum[x]++; isok[x]=1; } for(int i=1;i<N;i++) sum[i]+=sum[i-1]; lld ans = 0; for(int i=1;i<N;i++){ if(!isok[i]) continue; lld cur = 0; for(int j=i;j<N;j+=i) cur += j*(sum[min(j+i,N)-1]-sum[j-1]); ans = max(ans, cur); } cout<<ans<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/463/E 某種DP感的東東，我的作法大概就是先篩好質因數表，接著DFS下去的時候就把每個數的質因數塞到某個set之類的裡面，而在塞之前可以看一下是不是有前面的人有這個質因數了，然後紀錄一下就好了XD #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int C = 2000000 + 5; const int N = 100000 + 5; bool notprime[C]; vector<int> frac[C], G[N]; int arr[N], ans[N], dep[N], mp[C]; inline void sieve(int); void dfs(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); sieve(C); memset(mp, -1, sizeof(mp)); int n, q; cin>>n>>q; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } dep[1]=1; dfs(1, 1); while(q--){ int tp; cin>>tp; if(tp==1){ int v; cin>>v; cout<<ans[v]<<'\n'; }else{ int v, w; cin>>v>>w; arr[v]=w; dfs(1, 1); } } return 0; } inline void sieve(int n)

題目連結: http://tioj.infor.org/problems/1998 可以發現其實每個IP都是一個32-bit的東東，所以可以直接用個unsigned int或long long存下來。而遮罩的那個區間其實就是那些x全填0到全填1，而我們要詢問一堆IP是不是在一堆區間內，其實就直接把那些區間當作區間加值，那查詢就只要查詢那個點是不是大於一就好了。不過因為範圍有點大，要先離散化掉就是了。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) begin(x), end(x) typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int M = 200000 + 5; const int N = 300000 + 5; class LiSan{ private: vector<lld> vv; public: inline void init(){vv.clear();} inline void insert(lld x){vv.PB(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(lld x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } } lisan; PLL msk[M]; lld que[N]; int arr[2*M+N]; int main(){ lisan.init(); int m, n; scanf("%d%d",&m,&n); for(int i=0;i<m;i++){ int a, b, c, d, x; scanf("%d.%d.%d.

題目連結: http://tioj.infor.org/problems/1999 裸著做(?，每次都從當前最早服務完的人中叫他來服務客人，那他服務完的時間就再加上服務這個人的時間。而要早當前最早服務完的就拿個priority_queue就好了XD #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; priority_queue<int,vector<int>,greater<int>> pq; for(int i=0;i<m;i++) pq.push(0); for(int i=0;i<n;i++){ int x;cin>>x; int tp = pq.top();pq.pop(); pq.push(tp+x); } int ans = 0; while(!pq.empty()){ ans=pq.top();pq.pop(); } cout<<ans<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1409 我被雷了才知道原來多邊形也有任$n-1$邊之和大於第$n$邊的事，所以就掃過去紀錄最大值是誰，然後看$sum-max > max$有沒有成立就好了XD #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; int main(int argc, char* argv[]){ int n; while(~scanf("%d",&n)){ int mx = -1; long long cnt = 0; for(int i=0;i<n;i++){ int x; scanf("%d",&x); mx = max(mx, x); cnt+=x; } puts((cnt>(mx<<1))?"YES":"NO"); } return 0; }

題目連結: http://codeforces.com/problemset/problem/711/D 小品(?的圖論題。首先有個小觀察，這種給法的圖，在每一個連通塊(?中，只會有一個環，不過還是可能會有很多連通塊就是了。所以先考慮一個連通塊的情況，發現若他的環有$k$個邊，且整個連通塊有$n$個邊的話，他的方法數就會是$(2^k-2)\cdot(2^{n-k})$，想法大致就是，環上每個邊都可以選擇要換或不換扣掉全換跟全部換，再乘以其他大家的可能性就好了。至於多個連通塊的情況就直接把他們乘在一起就好了，畢竟他們是獨立的。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define FF first #define SS second const int N = 200000 + 5; const lld MOD_BASE = 1e9 + 7; class DJS{ private: vector<int> arr, sz; public: void init(int n){ arr.resize(n); sz.resize(n); for(int i=0;i<n;i++){ arr[i]=i; sz[i]=1; } } int size(int x){return sz[query(x)];} int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(int a, int b){ if(size(a) < size(b)) swap(a, b); int aa = query(a), bb = query(b); if(aa==bb) return; arr[aa]=bb; sz[bb]+=sz[aa]; } } djs; vector<int> G[N]; int dfn[N]; bool done[N]; int dfs(int); lld qP

題目連結: http://codeforces.com/problemset/problem/698/B 一開始完全沒想法，被提示(?說就算非法也還是一張圖後才比較有想法。這題我的作法很greedy，就先判斷一下有沒有原本就有可以當根的點，有的話就把他當根，接下來再掃一遍，看看有沒有人會構成環，有的話就直接把他接到根上面，此外，若沒有現成的根的話就直接把他變成根。而要找誰跟誰一樣就用個並查集就好了XD #include <bits/stdc++.h> using namespace std; #define PB push_back #define FF first #define SS second const int N = 200000 + 5; class DJS{ private: vector<int> arr; public: void init(int n){ arr.resize(n); for(int i=0;i<n;i++) arr[i]=i; } int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(int a, int b){ arr[query(a)]=arr[query(b)]; } } djs; int arr[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, ans = 0, root = -1; cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; if(arr[i]==i and root==-1) root=i; } djs.init(n+1); for(int i=1;i<=n;i++){ int x = arr[i]; if(x == root) continue; if(djs.query(x) == djs.query(i)){ if(root == -1){ root = i; if(x!=i){

題目連結: http://tioj.infor.org/problems/1410 裸的區間加值，查詢全部最大值問題。因為沒有奇怪的修改之類的，所以我們可以直接用個簡單的技巧，先插入兩個小標記之後再往後推過去一遍的作法做，而這題應為值域太大要先離散話，或是向我一樣懶懶的直接開個map解決他。 #include <bits/stdc++.h> using namespace std; map<long long,int> mp; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ long long l, r; cin>>l>>r; mp[l]++; mp[r+1]--; } int cur = 0, ans = 0; for(auto i: mp){ cur += i.second; ans = max(ans, cur); } cout<<ans<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1401 我好廢QQ被雷了才會。 很簡單的可以觀察到垂直跟水平可以分開，那這樣的話問題被轉化成給你一堆線段，你要為每條線段選一個點，使得這些點不能重複。做法很greedy直接從左掃到右邊，然後如果有可以放的就放，然後如果遇到一條線段就把他右界放進去之類的。 #include <bits/stdc++.h> using namespace std; #define PB push_back const int N = 100000 + 5; vector<int> hen[N], zhi[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ for(int i=1;i<=n;i++){ hen[i].clear(); zhi[i].clear(); } bool flag = true; for(int i=0;i<n;i++){ int l, r, u, d; cin>>l>>r>>u>>d; hen[l].PB(r); zhi[u].PB(d); } priority_queue<int,vector<int>,greater<int>> pq; for(int i=1;i<=n;i++){ for(auto j: hen[i]) pq.push(j); if(!pq.empty()){ if(pq.top() < i) flag = 0; else pq.pop(); } } if(!pq.empty()) flag = 0; for(int i=1;i<=n;i++){ for(auto j: zhi[i]) pq.push(j); if(!pq.empty()){ if(pq.top() < i) flag = 0; else pq.pop(); } } if(!pq.e

題目連結: http://tioj.infor.org/problems/1280 應該很明顯就是要求個凸包的面積，那就先求個凸包，求法就是先求出上凸包，再求下凸包，看上下凸包的方法也不難，就看看兩個相鄰的邊的夾角是不是超過180度就好。接著要求面積就直接算個有向面積加起來，而因為剛剛求凸包的順序關西，我們求有向面積的時候甚至不需要極角排序，直接求就好了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 10000 + 5; inline PLL operator-(const PLL &a, const PLL &b){ return {a.FF-b.FF, a.SS-b.SS}; } inline lld cross(const PLL &a, const PLL &b){ return a.FF*b.SS - b.FF*a.SS; } inline lld cross(const PLL &o, const PLL &a, const PLL &b){ return cross(a-o, b-o); } PLL arr[N]; vector<PLL> hull1, hull2; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i].FF>>arr[i].SS; sort(arr, arr+n); for(int i=0;i<n;i++){ while(hull1.size() > 1 and \ cross(hull1.back(), hull1[hull1.size()-2], arr[i]) < 0) hull1.pop_back(); hull1.push_back(arr[i

題目連結: http://tioj.infor.org/problems/1637 枚舉每個點，看有哪些區間會以他為最大值，若是裸著做可能會有個$O(n^2)$的作法，但是其實會發現維護那些區間會以他為最大值，其實可以先找出最長且以他為最大值的區間，而要做這件事就只要用個stack維護一下左邊右邊第一個比自己大的數在哪就好(維護stack的遞減性就可做到)。維護好後算答案其實也不難，區間的可能個數就是右邊元素的數量乘以左邊元素的數量。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<lld, int> PLI; #define FF first #define SS second const int N = 1000000 + 5; lld arr[N], LL[N], RR[N]; vector<PLI> ss; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n-1;i++) cin>>arr[i]; for(int i=0;i<n-1;i++){ while(!ss.empty() and ss.back() < (PLI){arr[i], i}) ss.pop_back(); LL[i] = ss.empty()?-1:ss.back().SS; ss.push_back({arr[i], i}); } ss.clear(); for(int i=n-2;i>=0;i--){ while(!ss.empty() and ss.back() < (PLI){arr[i], i}) ss.pop_back(); RR[i] = ss.empty()?n-1:ss.back().SS; ss.push_back({arr[i], i}); } lld ans = 0; for(int i=0;i<n-1;i++) ans += arr[i]*(RR[i]-i)*(i-LL[i]); cou

題目連結: http://codeforces.com/contest/855/problem/E 早上才學完數位統計DP晚上就寫不出來，我還真垃圾... 這題我的狀態是定成$dp[i][j][k]$代表在$i$進位下，算到第$j$位，而且有$k$個奇數次時的方法數，這狀態的轉移很簡單，就是枚舉多一位奇數或少一位奇數($dp[i][j][k]=dp[i][j-1][k-1] \cdot k + dp[i][j-1][k+1] \cdot (i-k)$)。那這樣的話，對於每一個範圍，我們就只要枚舉他在哪一位開始可以任意選之類的就可以回答了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 65; int dig[N]; lld dp[11][N][11]; bool dped[11][N][11]; void init(); lld go(int,int,bool,int,bool); lld calc(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); init(); int q; cin>>q; while(q--){ int b; cin>>b; long long l, r;cin>>l>>r; l--; int cnt; for(cnt=0;l>0;cnt++){ dig[cnt]=l%b; l/=b; } dig[cnt]=0; lld L = go(b, cnt, 0, 0, 1); for(cnt=0;r>0;cnt++){ dig[cnt]=r%b; r/=b; } dig[cnt]=0; lld R = go(b, cnt, 0, 0, 1); cout<<R-L<<'\n'; } return 0; } void init(){ for(int base=2;base<=10;base++){ for(int pos=0;pos

題目連結: http://tioj.infor.org/problems/1795 想了很久想不出來QQ，被雷了才知道其實就是求最小生成樹跟最大生成樹，然後判斷k是不是介在這兩棵樹的權值之間。證明也不難，就簡單的想一下你要從一棵生成樹變成另一棵生成樹，必定是加加減兩條邊，而且保證邊權都是0或1，所以其實每棵生成樹都最多差一(排序後)，所以只要判是不是介在最大最小就好。 #include <bits/stdc++.h> using namespace std; typedef tuple<int,int,int> III; #define FF(x) get<0>(x) #define SS(x) get<1>(x) #define TT(x) get<2>(x) class DJS{ private: vector<int> arr; public: void init(int n){ arr.clear(); arr.resize(n); for(int i=0;i<n;i++) arr[i]=i; } int query(int x){ if(arr[x]!=x) arr[x]=query(arr[x]); return arr[x]; } void merge(int a, int b){ arr[query(a)]=query(b); } } mx, mi; vector<III> edges; int main(){ int n, m, k; cin>>n>>m>>k; mx.init(n+1); mi.init(n+1); for(int i=0;i<m;i++){ int u, v, p; cin>>u>>v>>p; edges.emplace_back(p, u, v); } sort(edges.begin(), edges.end()); int miK=0, mxK=0; for(int i=0;i<m;i++){ int u = SS(edges[i]), v=TT(e

題目連結: http://tioj.infor.org/problems/1446 稍微想一下就會發現這題就等價於塞到trie後的DFS的順序，但是因為建棵trie有點麻煩，所以在想個兩下就會發現建棵trie再DFS其實跟你直接排序再扣掉相鄰的人的LCP等價，所以就這樣做吧XD #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; string ss[N]; int main(){ int n, ans=0; cin>>n; for(int i=0;i<n;i++){ cin>>ss[i]; ans+=ss[i].size(); } sort(ss, ss+n); for(int i=1;i<n;i++){ int sz = min(ss[i].size(), ss[i-1].size()); int lcp; for(lcp=0;lcp<sz and ss[i][lcp]==ss[i-1][lcp];lcp++); ans-=lcp; } cout<<ans*2+n<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1062 這題題目好像有點怪，但還在可理解的範圍內，總之就是問你說給你網格內的一堆數，每個人移動都有1單位的cost，問你選哪個點讓大家都移動到他後的cost最小。 可以發現其實左右跟上下是可以分開的，因為他不能斜的走。所以就從左到右枚舉哪個點可以並從上到下枚舉哪個點可以，兩個混和在一起就好了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<lld, int> PLI; #define FF first #define SS second const int N = 100 + 5; const lld INF = 1LL<<60; lld X[N], Y[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int x; cin>>x; X[j]+=x; Y[i]+=x; } } PLI ansX={INF, 0}, ansY={INF, 0}; lld curX=0, curY=0; for(int i=1;i<=m;i++) curX+=X[i]*i; for(int i=1;i<=n;i++) curY+=Y[i]*i; for(int i=1;i<=m;i++) X[i]+=X[i-1]; for(int i=1;i<=n;i++) Y[i]+=Y[i-1]; for(int i=1;i<=m;i++){ curX += X[i-1]; curX -= X[m]-X[i-1]; if(curX < ansX.FF) ansX = {curX, i}; } for(int i=1;i<=n;i++){ curY += Y[i-1]; curY -= Y[n]-Y[i-1];

題目連結: http://codeforces.com/problemset/problem/766/E 貌似是某種樹DP的東東，看到xor就要先想到把bit拆開，這樣的話問題就被轉化成說給你一堆0, 1的節點，問你所有路徑的和。這樣的話有個好處就是，因為只有0跟1，所以我們其實只要計算他的奇偶，然後偶爾交換一下之類的。接下來發現要枚舉所有路徑，其實枚舉lca就好了，所以就先走下去，把子樹算一算，之後提上來的時候稍微看一下自己是0還是1再把大家乘一乘之類的就好了。(想睡覺，可能有點不知所云 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back const int N = 100000 + 5; int arr[N]; vector<int> G[N]; lld ans = 0; PII dfs(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } for(int i=0;i<20;i++) dfs(1, 1, i); cout<<ans<<'\n'; return 0; } PII dfs(int w, int f, int d){ queue<PII> qq; PII ret = {0, 0}; for(auto i: G[w]){ if(i==f) continue; PII sub = dfs(i, w, d); qq.push(sub); ret.FF += sub.FF; ret

題目連結: http://tioj.infor.org/problems/1481 一個小觀察，$\forall x \in \mathbb{N},gcd(x, x+1)=1$，所以這題每個邊的編號其實就是DFS時每個邊被遍歷到了順序。 #include <bits/stdc++.h> #include "lib1481.h" using namespace std; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back const int V = 2000+5, E = 20000+5; bitset<E> visited; vector<PII> G[V]; int ans[E], cnt=0; void dfs(int); int main(){ Init(); int n, m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ int u, v; scanf("%d%d",&u,&v); G[u].PB({v, i}); G[v].PB({u, i}); } dfs(1); Possible(); for(int i=0;i<m;i++) Number(ans[i]); Finish(); return 0; } void dfs(int w){ for(auto i: G[w]){ int v = i.FF, id = i.SS; if(visited[id]) continue; visited[id]=1; ans[id]=++cnt; dfs(v); } }

題目連結: http://codeforces.com/problemset/problem/208/E 稍微轉化一下問題就可以得到問節點$i$的子節點們深度為$d$的有那些，轉法也很簡單，對於一組詢問$(v, p)$就直接變成，對於$v$的$p$倍祖先問在$dep[v]$的數字有哪些(問一個人的$p$倍祖先可以直接用個倍增法做到)。轉化成這樣後就可以直接開個map維護每個深度為$k$時有幾個，然後要合併兩子樹就啟發式合併就好了。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; typedef pair<int,int> PII; #define PB push_back #define FF first #define SS second class K_anc{ private: vector<int> G[N]; int anc[N][20]; void dfs(int w, int f){ anc[w][0]=f; for(auto i: G[w]) if(i!=f) dfs(i, w); } public: inline void AddEdge(int u, int v){ G[u].PB(v); G[v].PB(u); } void solve(int r, int maxn){ dfs(r, r); for(int j=1;j<20;j++) for(int i=0;i<maxn;i++){ anc[i][j] = anc[anc[i][j-1]][j-1]; } } int query(int a, int k){ for(int i=0;i<20;i++) if(k & (1<<i)) a=anc[a][i]; return a; } } anc; vector<int> G[N]; vector<PII> que[N]; int dep[N], ans[N]; void dfs(int,map<int,int>

題目連結: http://codeforces.com/contest/570/problem/D 把詢問依照節點存好，接下來我們就可以對樹DFS，同時記錄一下他的深度與每個字母出現的次數，然後要把兩棵子樹的資訊合併起來時就用啟發式合併，而完成一棵子樹後就可以把每個詢問的答案填上去，而且我們只在意奇偶性，所以甚至還可以用位元運算壓掉一些常數，大概就這樣吧。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int N = 500000 + 5; vector<int> G[N]; char wh[N]; vector<PII> que[N]; int ans[N], dep[N]; void dfs(int, map<int,int>&); int main(){ int n, q; scanf("%d%d",&n,&q); dep[1]=1; for(int i=2;i<=n;i++){ int x; scanf("%d", &x); G[x].PB(i); dep[i]=dep[x]+1; } scanf("%s", wh); for(int i=0;i<q;i++){ int v, d; scanf("%d%d", &v, &d); if(d < dep[v]) continue; que[v].PB({d, i}); } map<int,int> mp; dfs(1, mp); for(int i=0;i<q;i++){ if(__builtin_popcount((unsigned)ans[i])<=1) puts("Yes"); else puts("No"); } return 0; } void dfs

題目連結: http://codeforces.com/contest/198/problem/E 被雷了才會QQ 會發現其實他是個圓並不重要，重要的其實是距離，所以不妨把每個人的座標轉換成跟原點的距離，這樣的話每次詢問就變成詢問一個距離內質量小於k的數有誰，而我們其實也不用一次把一坨東西拉出來，只要一次拉一個就好，反正最多拉n個，複雜度不會太慘。而這樣其實就是詢問一個前綴極值就可達到這件事，所以就開個BIT套個單調的queue之類的就可以做到這件事了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define ALL(x) begin(x), end(x) #define FF first #define SS second const int N = 250000 + 5; const lld INF = 1LL<<31; class LiSan{ private: vector<lld> vv; public: inline void init(){vv.clear();} inline void insert(lld x){vv.PB(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(lld x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } inline lld inv_get(int x){return vv[x];} } lisan; struct Obj{ lld d, m, p, r; bool operator<(const Obj &x) const { return tie(m, d) < tie(x.m, x.d); } } arr[N]; class BIT{ typ

題目連結: http://codeforces.com/contest/861/problem/D 裸裸的對於每個字串枚舉他可能會有的子字串，然後判斷一下是否沒出現在其他人過就好了，一開始寫了hash但不知道為何一直WA，最後開個unordered_map就過了... #include <bits/stdc++.h> using namespace std; #define PB push_back unordered_map<string,int> ex; vector<string> inp; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ string ss; cin>>ss; for(int j=0;j<9;j++){ string tp; for(int k=j;k<9;k++){ tp.push_back(ss[k]); ex[tp]++; } } inp.PB(ss); } for(int i=0;i<n;i++){ string ans = "IOI2018Participant"; for(int j=0;j<9;j++){ string tp; for(int k=j;k<9;k++){ tp.push_back(inp[i][k]); ex[tp]--; } } for(int j=0;j<9;j++){ string tp; for(int k=j;k<9;k++){ tp.push_back(inp[i][k]); if(tp.size() < ans.size() and ex[tp] == 0) ans=tp; } } for(int j=0;j<9;j++){ string tp; for(int k=j;k<9;k++){ tp.push_back(inp[i][k]); e

題目連結: http://codeforces.com/problemset/problem/835/D 先觀察到一件事，是k回文的他一定也是k-1回文，這樣的話就只要知道一個子字串他最大是幾回文就好了，而這可以DP，狀態是$dp[i][j]$代表$i~j$最大可以是幾回文，而轉移也很顯然的就是$dp[i][j] = dp[i][mid]+1$，如果$i~mid == mid~r$的話，否則的話就是0，而要判斷兩個子字串是否相等其實用個hash就好了，只不過我真的不太會寫hash，搞了好久QQ #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 5000 + 5; class Hash{ private: const lld p = 127, q = 1208220623; int sz; lld prefix[N], power[N]; public: void init(const string &x){ sz = x.size(); prefix[0]=0; for(int i=1;i<=sz;i++) prefix[i]=((prefix[i-1]*p)%q+x[i-1])%q; power[0]=1; for(int i=1;i<=sz;i++) power[i]=(power[i-1]*p)%q; } lld query(int l, int r){ // 1-base (l, r] return (prefix[r] - (prefix[l]*power[r-l])%q + q)%q; } }; // dp[4][9] : xxxx|jkljk|xxxxx // [l, r) int dp[N][N], ans[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); string ss; cin>>ss; int n = ss.size(); Hash ori, rev; ori.init(ss); reverse(ss.begin(), ss.

題目連結: http://codeforces.com/problemset/problem/600/E 詢問子樹區間眾數和，一開始我只想到可以樹壓扁莫隊。後來被雷了之後才知道可以啟發式合併，讓子樹回傳一個map之類的東西記錄每個數字有幾個，而要把子樹們合起來的方式則採用啟發是合併，這樣可以保證每個數字最多被合併$logN$次，要算答案也很簡單，就簡單的看一下現在最大的數字個數有幾個跟維護一下和就好。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; typedef pair<lld,int> PLI; #define FF first #define SS second const int N = 100000 + 5; int col[N]; lld ans[N]; vector<int> G[N]; PLI dfs(int,int,unordered_map<int,int>&); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) cin>>col[i]; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } unordered_map<int,int> mp; dfs(1, 1, mp); for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n]; return 0; } PLI dfs(int w, int f, unordered_map<int,int>& res){ // (res) number -> count // (ret) sum, count PLI ret = {col[w], 1}; res[col[w]]

題目連結: http://codeforces.com/problemset/problem/832/C 煩躁的一題...還因為沒注意到一定要放在整數點卡了一段時間QQ。 作法大概就是對答案二分搜，而驗證的時候，則會發現若是考慮要讓某個人往右的人達到終點，如果直接放在他身上可以，那往他左邊一點可能也可以，所以可以求出一個區間 ；同理往左的也是。這樣就轉化成為先將一堆區間填在數線上，接著詢問一堆區間是否與先前的區間們有碰在一起的地方。而找出對於往右區間的方法這裡是列了$$\frac{x-x^\prime}{s-v}+\frac{10^6-\frac{x-x^\prime}{s-v}\cdot v-x}{s+v} \leq t\\x^\prime \geq 10^6-\frac{v(10^6-x-vt)}{s}-st$$往左的則是$$\frac{x^\prime-x}{s-v}+\frac{x-\frac{x^\prime-x}{s-v}\cdot v}{s+v} \leq t\\x^\prime \leq \frac{v(x-vt)}{s}+st$$ #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second typedef long double llf; typedef long long lld; const int N = 1e6 + 5; int n, s; vector<PII> L, R; lld arr[N]; inline bool isOK(llf); int main(){ cin>>n>>s; for(int i=0;i<n;i++){ PII tp; cin>>tp.FF>>tp.SS; int x; cin>>x; if(x-1) R.PB(tp); else L.PB(tp); } llf l = 0, r = 1e6; for(int _=0;_<80;_++){ llf mid = (l+r)

題目連結: http://tioj.infor.org/problems/1990 每次都照著換就太慢了，所以不妨做個映射$col[i]=k$代表換完後的第$i$個欄其實是原本的第$k$欄，列也是用同樣的方法，這樣的話交換$i, j$就只要$swap(col[i], col[j])$了。 #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; string mtx[N]; int col[N], row[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cin>>mtx[i*m+j]; } for(int i=0;i<n;i++) col[i]=i; for(int i=0;i<m;i++) row[i]=i; int q; cin>>q; while(q--){ char type; cin>>type; if(type=='S'){ int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2; x1--, y1--, x2--, y2--; swap(mtx[col[x1]*m+row[y1]], mtx[col[x2]*m+row[y2]]); }else if(type=='C'){ int a, b; cin>>a>>b; a--, b--; swap(row[a], row[b]); }else if(type=='R'){ int a, b; cin>>a>>b; a--, b--; swap(col[a], col[b]); } } for(int i=0;i<n;i++) for(int j=0;j<

題目連結: http://tioj.infor.org/problems/1993 DP題可以滾動，狀態大概就是$dp[i][j]$代表可否用前j個數湊出i，滾起來後就剩一維了，而且還會發現其實我每次在做的事情其實就是把他在往後移某個格數，所以可以用bitset的位移來達到優化的效果(自己$O(N)$位移會是爛的QQ) p.s. 其實bitset位移好像也是$O(N)$，但常數超小(我這裡真的找不太到資料，但他跑起來超快) #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; bitset<N> isok; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ isok.reset(); isok[0]=1; int n, m; cin>>n>>m; for(int i=0;i<n;i++){ int a, b, c; cin>>a>>b>>c; isok = (isok<<a)|(isok<<b)|(isok<<c); } int ans = 0; for(int i=0;i<=m;i++) if(isok[i]) ans = i; if(ans==0) cout<<"no solution\n"; else cout<<ans<<'\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1994 就照著做，分成左上左下右上右下四塊遞迴下去，但是很噁心，要判一些case QQ，賽中寫了2hr，然後就沒時間寫其他題了 #include <bits/stdc++.h> using namespace std; const int N = 1<<11; const int A=0, B=1, C=2, D=3, E=4; int n; int ans[N][N]; void dfs(int,int,int,int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n; int sz = 1<<n; dfs(0, 0, sz, sz, 0, B); for(int i=0;i<sz;i++) for(int j=0;j<sz;j++){ cout<<ans[i][j]<<" \n"[j==sz-1]; } return 0; } void dfs(int l, int u, int r, int d, int x, int f){ if(r-l==1){ ans[l][u]=x; return; } int hal = (r-l)>>1; if(f==A){ dfs(l, u, r-hal, d-hal, x, B); dfs(l+hal, u, r, d-hal, x+hal*hal*3, E); dfs(l+hal, u+hal, r, d, x+hal*hal*2, A); dfs(l, u+hal, r-hal, d, x+hal*hal*1, A); }else if(f==D){ dfs(l, u, r-hal, d-hal, x+hal*hal*2, D); dfs(l+hal, u, r, d-hal, x+hal*hal, D); dfs(l+hal, u+hal, r, d, x, E); dfs(l, u+hal, r-hal, d, x+hal*hal*3, B); }else if(

題目連結: http://tioj.infor.org/problems/1991 大概看個一兩眼就會發現其實橫的跟直的可以分開，每個區塊都是獨立的(表示我選了這塊，我再選另一塊並不會影響前面那塊的值(某些奇怪的題目會有))，所以不難發現實作個二維的前綴和就好了，跟普通前綴和差不多，就輸出的時候再扣掉不要的部分就好了。 #include <bits/stdc++.h> using namespace std; const int N = 2000000 + 5; #define Hash(i, j) ((i)*(m+1)+(j)) bool mtx[N]; int preH[N], preZ[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mtx[Hash(i, j)]; if(mtx[Hash(i, j)] and mtx[Hash(i, j-1)]) preH[Hash(i, j)]++; if(mtx[Hash(i, j)] and mtx[Hash(i-1, j)]) preZ[Hash(i, j)]++; preH[Hash(i, j)]+=preH[Hash(i, j-1)]; preZ[Hash(i, j)]+=preZ[Hash(i-1, j)]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ preH[Hash(i, j)]+=preH[Hash(i-1, j)]; preZ[Hash(i, j)]+=preZ[Hash(i, j-1)]; } } int q; cin>>q; while(q--){ int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2; cout<<(preZ[Hash(x2, y2)]+preZ[Hash(x1,

題目連結: http://codeforces.com/problemset/problem/842/D 寫過類似的題目，一看到就認出來了XD。考慮把所有數字塞到bitwise的trie上，這樣xor一個數字時就變成交換左右子樹了，而且其實也不用真的把每個子樹都換過一遍，只要再走下去的時候看一下要誰當左右子樹即可。那這樣就只要在一棵樹上找mex值就好了，這也不難，只要維護一下每個子節點的大小，先看左子樹是不是空的，若是就直接回傳0，因為表示往左走都沒東東了，再看一下左子樹是不是滿的，若是就只能走右邊，不然就繼續走左子樹即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 300000 + 5; const int MEM = 20*N; class Trie{ private: struct node{ node *l, *r; int size; node(){l=r=nullptr;size=0;} }; node *root, pool[MEM]; int _mem; node* newnode(){ assert(_mem<MEM); pool[_mem]=node(); return &pool[_mem++]; } int size(node *x){return x?x->size:0;} void insert(int x, node *&cur, int d){ if(!cur) cur=newnode(); cur->size++; if(d>=32) return; if(x&1LL<<(31-d)) insert(x, cur->r, d+1); else insert(x, cur->l, d+1); } int find_min(node *cur, int d){ if(cur->l) return find_min(cur->l, d

題目連結: http://tioj.infor.org/problems/1846 想了一段時間才想出來，我的數學一定是太爛了QQ。做法就是先用圓心距跟兩個半徑套餘弦定理求出兩個扇形的夾角，那答案就是兩個扇形的面積扣掉兩組半徑所構成的箏形面積，此外記得多判一下兩園沒交點的情況。 #include <bits/stdc++.h> using namespace std; const double PI = acos(-1); inline double dis(double,double,double,double); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ int x1, y1, r1; cin>>x1>>y1>>r1; int x2, y2, r2; cin>>x2>>y2>>r2; double dd = dis(x1, y1, x2, y2); if(dd >= r1+r2) cout<<"0.00\n"; else if(dd+min(r1, r2) <= max(r1, r2)) cout<<fixed<<setprecision(2)<<min(r1, r2)*min(r1, r2)*PI<<'\n'; else{ double deg1 = acos((dd*dd+r1*r1-r2*r2)/(2*dd*r1)); double deg2 = acos((dd*dd+r2*r2-r1*r1)/(2*dd*r2)); double ans = r1*r1*deg1+r2*r2*deg2 - r1*r1*sin(deg1*2)/2 - r2*r2*sin(deg2*2)/2; cout<<fixed<<setprecision(2)<<ans<<'\n'; } } return 0; } inline

題目連結: http://codeforces.com/problemset/problem/551/E 把序列分成$\sqrt{N}$塊後，每次操作就變得很簡單了，修改時如果那塊完整被覆蓋就直接在懶標記上修改，而如果沒有就把那塊重新建置一次；詢問時就先看一下懶標記，再查詢即可。複雜度$O(Q \sqrt{N})$ #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second typedef long long lld; const int K = 710; const int N = 500000 + 5; lld arr[N], flag[K]; unordered_map<lld, PII> blk[K]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, q; cin>>n>>q; for(int i=0;i<n;i++) cin>>arr[i]; const int k = ceil(sqrt(n)); for(int i=0;i<n;i+=k){ for(int j=i;j<min(n, i+k);j++){ if(blk[i/k].find(arr[j])==blk[i/k].end()) blk[i/k][arr[j]].FF = j; blk[i/k][arr[j]].SS = j; } } while(q--){ int tp; cin>>tp; if(tp==1){ int l, r; lld v; cin>>l>>r>>v; l--; const PII ID = {l/k, (r-1)/k}; blk[ID.FF].clear(); for(int i=ID.FF*k;i<min((ID.FF+1)*k, n);i++){ if(l <= i and i < r) arr[i]+=

題目連結: http://tioj.infor.org/problems/1847 題目看了一下下才看懂，原來就是給你一張圖問你最短距離小於D的點權和。那要求最短路徑就寫個dijkstra就好，然後再掃一下看某個點距離是不是小於D，是就加點權，不是就不加。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back const int N = 100000 + 5; const int INF = (1<<30) + 5; vector<int> G[N]; int dis[N], val[N]; bitset<N> visited; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m, d; cin>>n>>m; for(int i=0;i<n;i++) cin>>val[i]; for(int i=0;i<m;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } cin>>d; fill(dis, dis+n, INF); priority_queue<PII,vector<PII>,greater<PII>> pq; dis[0]=0; pq.push({dis[0], 0}); while(!pq.empty()){ int u = pq.top().SS; pq.pop(); if(visited[u]) continue; visited[u]=1; for(auto v:G[u]){ if(dis[v] > dis[u]+1){ dis[v]=dis[u]+1; pq.push({dis[v], v}); } } } int ans=0; for(int i=

題目連結: http://codeforces.com/contest/854/problem/E 賽中還有一個多小時時一看到這題就知道該怎麼做了，然而想太快有許多細節忽略掉就爛掉了(後來還因為沒開long long又de了約莫5個小時QQ)。 因為保證每一行每一列都只會有一個格子被塗黑，所以其實可以把整張網格壓成一個序列(如同他給的資料一樣)，那這樣詢問一個矩形內有幾個黑格子時其實就是詢問一個區間大於A小於B的數字有幾個，可能很多人直覺就直接持久話做掉，不過我是想到先前寫過的一個做法(歸併樹)：開一顆線段樹，樹上節點是一個排序好的序列，查詢那個比K大的數字時就直接二分搜一下就好了，而若要再查小於B的數字，其實可以用扣掉比B+1大的做法做就好了。 這樣我們就會做查詢一個矩形內黑色的數量了，剩下該怎麼算的問題了。仔細想想(其實好像根本就是高一組合題)後，發現可以用扣的，那問題轉化為給你一個中間挖掉一塊的矩形，問你可以湊出幾個矩形，那顯然就是挖掉那塊矩形的上下左右一大塊都是不能用的，但是扣掉這些後左上、左下、右上、右下會被多扣，再加回來就好了。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() typedef long long lld; const int N = 200000 + 5; class SegTree{ private: vector<int> nodes[4*N]; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} int size; void build(int l, int r, int arr[], int id){ if(r-l > 1){ int mid=(l+r)>>1; build(l, mid, arr, lc(id)); build(mid, r, arr, rc(id)); } for(int i=l;i<r;i++) nodes[id].PB(arr[i]);