oToToT的code收藏區

題目連結: 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)