oToToT的code收藏區

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_c 題目大意: 給你一棵樹，詢問在樹上加入一條邊後最長的環可以是多長。 樹直徑就會是這題答案了。 #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<int>> g(n); for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[--u].emplace_back(--v); g[v].emplace_back(u); } int ans = 0; auto dfs = [&g, &ans] (auto rec, int u, int f) -> int { int mx1 = 0, mx2 = 0; for (int v: g[u]) { if (v == f) continue; int s = rec(rec, v, u); if (s >= mx1) { mx2 = mx1; mx1 = s; } else if (s >= mx2) { mx2 = s; } } ans = max(ans, mx1 + mx2); ...

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

題目連結: http://tioj.infor.org/problems/1369 裸裸的DFS題，遞迴遍歷過每個節點即可 #include <bits/stdc++.h> using namespace std; #define N 50000 int arr[N+5], tt=0; vector<int> graph[N+5]; void dfs(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=1;i<=n;i++){ int k;cin>>k; while(k--){ int x;cin>>x; graph[i].push_back(x); } } dfs(1); for(int i=1;i<=n;i++)cout<<arr[i]<<'\n'; return 0; } void dfs(int x){ arr[x]=++tt; for(auto i:graph[x]) dfs(i); }

題目連結: http://tioj.infor.org/problems/1230 本題就照著DFS就好了XD 更新:突然發現我這寫法是假解，還在思索真解怎麼寫。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define N 3000 int graph[N][N]; struct List{ int x; int y; List* next; List(){ next=NULL; } ~List(){ if(next!=NULL)delete next; } }; bitset<N> walked[N]; lld DFS(int,int,List*); void cList(List*); int n,m; int main(){ scanf("%d%d\n",&n,&m); for(int i=0;i<n;i++){ char inp[N+5]; gets(inp); int inpSZ = strlen(inp); int ctt=0; for(int j=0;j<inpSZ;j++){ if(inp[j]==' ')continue; if(inp[j]=='x'){ walked[i][ctt]=1; graph[i][ctt++]=-100; }else{ graph[i][ctt++]=inp[j]-'0'; }...

題目連結: http://tioj.infor.org/problems/1717 本題要求對於每個專案的最大值，所以想想就直接DFS就好，而且顯然不能同一個點走太多次，所以要DP，而因為我覺得存原本的圖不好判斷誰是起點，所以不妨存個反過來的圖，甚至開一個假點當作起點，反正答案都會對。大概就這樣吧 #include <bits/stdc++.h> using namespace std; #define N 1000 int Time[N+5]; int val[N+5]; bitset<N+5>walked; vector<int> graph[N+5]; inline void init(int); int DFS(int); int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); init(n); for(int i=1;i<=n;i++){ int v,sz; scanf("%d%d",&v,&sz); Time[i]=v; if(sz==0) graph[0].push_back(i); for(int j=0;j<sz;j++){ int w; scanf("%d",&w); graph[w].push_back(i); } } int ans=DFS(0); printf("%d\n"...

題目連結: http://tioj.infor.org/problems/1092 本題是個對稱遊戲，所以應該只需要管該點是先手贏或後手贏，那顯然最後一點是先手贏，而連到最後一點的都輸，所以可以導出該點一定跟他下一點相反，而如果前面的點有必勝的點，那對方也一定走過去，所以只要看他連到的點有沒有必勝的，若有自己就必輸，若無則自己必贏，所以DFS一遍就可以解決了XD #include <bits/stdc++.h> using namespace std; #define N 10000 vector<int> graph[N+10]; int n,e; bitset<N+10> isset; bitset<N+10> val; inline void init(); bool dfs(int); int main(){ scanf("%d%d",&n,&e); while(n+e!=0){ init(); while(e--){ int a,b; scanf("%d%d",&a,&b); graph[a].push_back(b); } isset[n]=1; val[n]=1; dfs(1); char name[7]; scanf("%s",name); if((!val[1] && name[1]=='i') || (val[1] && name[1]=='o')) puts("Moumou"); else puts("Mimi"); ...

題目連結: http://tioj.infor.org/problems/1336 建中校內補選題，我開賽19分鐘才AC，覺得太廢了QAQ，本題就照著DFS，記得記一下誰已經走過了，走到他就別再走，大概這樣吧 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef unsigned long long llu; typedef double lf; typedef long double llf; #define F1(i,a,n) for(int i=a;i<n;i++) #define F(i,a,n,m) for(int i=a;i<n;i+=m) #define WC(x) while(x--) #define N 100 int graph[N+10][N+10]; bitset<N + 10> checked[N + 10]; void check(int,int,int); int n,m; char str[N+10]; int main(){ scanf("%d%d",&m,&n); F1(i,0,n){ scanf("%s",str); F1(j,0,m){ char c=str[j]; switch(c){ case '-': graph[i][j]=1; break; case 'G': graph[i][j]=2; break; case 'W': ...

題目連結: http://tioj.infor.org/problems/1557 邊DFS邊DP，只要知道起點到起點的走法是一種，然後每次都詢問他的來源走法有幾種，大概這樣吧 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define N 10000 #define modBASE 1073741824 vector<int> graph[N + 10]; lld val[N + 10]={0}; bitset<N + 10>dped; lld dp(int); int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); graph[b].PB(a); } int Start,End; scanf("%d%d",&Start,&End); val[Start]=1; dped[Start]=1; lld ans = dp(End); printf("%lld",ans); return 0; } lld dp(int w){ if(!dped[w]){ lld sum=0; for(int i=0;i<graph[w].size();i++){ sum += dp(graph[w][i]); sum %= modBASE; }...

題目連結: http://tioj.infor.org/problems/1196 雖然本題理應是要DP，但其實n小小的(才10而已)，直接BFS甚至DFS就好了XD #include <stdio.h> int size, maze[11][11]; int DFS(int x, int y, int val){ if(maze[x][y] == 22) return val; else if(maze[x][y] == -1) return -1; else{ if(x<size-1 && y<size-1){ int a = DFS(x+1, y, val + maze[x][y]); int b = DFS(x, y+1, val + maze[x][y]); return (a>b)?a:b; }else if(x < size-1) return DFS(x+1, y, val+maze[x][y]); else return DFS(x, y+1, val+maze[x][y]); } } int main(){ scanf("%d\n",&size); for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ char c=getchar(); maze[i][j] = (c=='A') ? 71 : (c=='B') ? 22 : (c=='X') ? -1 : c-'0'; } getchar(); } int ans=D...