JOI難しい
二問しかといてないけどそれはあり本で勉強してたからです(言い訳)
AOJ 0534
Run-Length圧縮したらはやくなるかなとかやってたらしいけど、それだと例外できまくってだめだった。
実際はただの探索。
nが小さいからO(n^2)で普通にできる。
#include <cstdio> #include <climits> #include <algorithm> using namespace std; int n, col[10000]; int calc(int x, int c) { if (col[x]==c) return n; int p=x-1, q=x+1; int cnt=1; for (;p>=0;p--) { if (col[p]==c) cnt++; else break; } for (;q<n; q++) { if (col[q]==c) cnt++; else break; } if (cnt<4) return n; else if (p<0||q>=n) return n-cnt; else if (col[p]!=col[q]) return n-cnt; int res=n-cnt; while (true) { cnt=0; c=col[p]; for (;p>=0;p--) { if (col[p]==c) cnt++; else break; } for (;q<n; q++) { if (col[q]==c) cnt++; else break; } if (cnt<4) return res; else if (p<0||q>=n) return res-cnt; else if (col[p]!=col[q]) return res-cnt; res-=cnt; } return res; } int main() { while (scanf("%d",&n)) { if (!n) break; for (int i=0; i<n; i++) { scanf("%d",&col[i]); } int res=INT_MAX/2; for (int i=0; i<n; i++) { for (int j=1; j<=3; j++) { res=min(res,calc(i,j)); } } printf("%d\n",res); } }
PKU 3660
グラフに落とし込めるのがわかるようになったのは嬉しい。ちょっとした成長
勝ちチームから負けチームへ有向の辺をはっていって有向グラフにしたとき、それはDAGなので各頂点についてその頂点にたどりつける頂点の数と、その頂点からたどりつける頂点の数の合計がn-1になるとき(上下のチームが確定するので)その頂点のチームの順位が確定する。
よってこれを単純に探索すればよい。単純に幅優先n回やったけど自明な枝刈りをしてAC
#include <cstdio> #include <cstring> #include <vector> #include <set> #include <queue> using namespace std; int n, m; vector<int> G[100]; set<int> in[100], out[100]; bool used[100]; void calc(int x) { memset(used, 0, sizeof(used)); queue<int> que; que.push(x); while (!que.empty()) { int nx=que.front(); que.pop(); if (used[nx]) continue; used[nx]=true; for (int i=0; i<G[nx].size(); i++) { int y=G[nx][i]; in[y].insert(x); out[x].insert(y); que.push(y); } } } int main() { scanf("%d%d",&n,&m); for (int i=0; i<m; i++) { int a, b; scanf("%d%d",&a,&b); a--; b--; G[a].push_back(b); } int res=0; for (int i=0; i<n; i++) { calc(i); } for (int i=0; i<n; i++) { if (in[i].size()+out[i].size()+1==n) res++; } printf("%d\n",res); }