oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1711 說個笑話，oToToT會寫程式。 搞了好久都不會做，然後一直假解QAQ 去網路上查到momo學長的解居然也是錯的（詳見底下測資） 10 6 522 288 963 788 756 856 18 412 378 789 2 1 3 2 4 2 5 2 6 5 7 6 8 4 9 1 10 4 最後是去問了minson才知道一個怪怪的解QQ，我到現在還是不知道這為何是好的(他說複雜度是$O(N^2)$)，可能跟CF 729F有類的概念吧。 註(2019/04/24):似乎是因為某種兩個東西只會在他們的LCA被合起來 總之就是用一個顯然的事實就是我們一個(子)樹最多只能走他底下size步，所以我們就只要維護size，並且每次上界都用當前大小做dp即可。 dp狀態也很簡單 $ dp[i][j][0] := \text{第i個節點走j步後且要走回來的最大值}, dp[i][j][1] := \text{第i個節點走j步後，停在他底下某個人的最大值} $轉移就直接暴力混和背包即可。 #include <cstdio> #include <cstring> #include <vector> #include <algorithm> const int N = 1000 + 5; int w[N], dp[N][N<<1][2]; int tmp[N<<1][2], sz[N]; std::vector<int> G[N]; void dfs(int,int,int); int main(){ int n, k; scanf("%d%d", &n, &k); k = std::min(k, n+n); for(int i=1;i<=n;i++) scanf("%d", w+i); for(int i=1;i<n;i++) { int u, 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;...

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

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