蟻本セット
今日も蟻本セットやってた。
しばらくして少しこの練習方法が本当に本番に役立つのか不安になったけどとにかくやることにした←
3187
next_permutation(←スペルもあやふやなほど慣れてない)を使って全列挙。
どうやらこれは辞書順に作ってくれるようでほんとにやるだけになった。
#include <cstdio> #include <algorithm> using namespace std; int n, fsum; int perm[10]; int nex[10][10]={ {1,0,0,0,0,0,0,0,0,0}, {1,1,0,0,0,0,0,0,0,0}, {1,2,1,0,0,0,0,0,0,0}, {1,3,3,1,0,0,0,0,0,0}, {1,4,6,4,1,0,0,0,0,0}, {1,5,10,10,5,1,0,0,0,0}, {1,6,15,20,15,6,1,0,0,0}, {1,7,21,35,35,21,7,1,0,0}, {1,8,28,56,70,56,28,8,1,0}, {1,9,36,84,126,126,84,36,9,1}}; int main() { scanf("%d%d",&n,&fsum); for (int i=0; i<n; i++) { perm[i]=i+1; } do { int sum=0; for (int i=0; i<n; i++) { sum+=perm[i]*nex[n-1][i]; } if (sum==fsum) { for (int i=0; i<n; i++) { printf("%d%c",perm[i],i==n-1?'\n':' '); } break; } } while (next_permutation(perm, perm+n)); }
1862
細胞が一杯ぶつかっていき、二個体がぶつかるたびと質量がその二個体の相乗平均×2の個体としてかわりに出てくるとしたとき、一個体になるまで減らしていったらの最小でどのくらいの重さの個体を作れるか、求めよって問題。
貪欲というのはわかっていて見ていたことはさておき、まぁ√がいっぱいつくように大きいものからとっていくで簡単。
ただしdoubleの出力をlfでやってたらなんかWAくらいまくった。
#include <cstdio> #include <cmath> #include <algorithm> #include <functional> using namespace std; int n; double res; int str[101]; int main() { scanf("%d",&n); for (int i=0; i<n; i++) { scanf("%d",&str[i]); } sort(str, str+n, greater<int>()); res=(double)str[0]; for (int i=1; i<n; i++) { res=2*sqrt(res*str[i]); } printf("%.3f\n",res); }
2377
最小全域木ならぬ最大全域木。
プリムはよく理解できてなくて改造できないので逆順ソート+クラスカルでやった。
Union-Find木重要だね。うん。
#include <cstdio> #include <algorithm> using namespace std; int par[1000]; int rank[1000]; void init(int n) { for (int i=0; i<n; i++) { par[i]=i; rank[i]=0; } } int find(int x) { if (par[x]==x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if (x==y) return; if (rank[x]<rank[y]) { par[x]=y; } else { par[y]=x; if (rank[x]==rank[y]) rank[x]++; } } bool same(int x, int y) { return find(x)==find(y); } struct edge { int u, v, cost; }; bool comp(const edge& e1, const edge& e2) { return e1.cost > e2.cost; } edge es[20000]; int n, m; int main() { scanf("%d%d",&n,&m); for (int i=0; i<m; i++) scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost); sort(es, es+m, comp); init(n); int res = 0; for (int i=0; i<m; i++) { edge e = es[i]; if (!same(e.u, e.v)) { unite(e.u, e.v); res += e.cost; } } bool flag=true; for (int i=2; i<=n; i++) { if (!same(1,i)) { flag=false; break; } } if (flag) printf("%d\n",res); else puts("-1"); }
2236
さっきのからの流れでUnion-Find木の問題。
実装するだけだけど最初初期化忘れてて苦戦。
で、一応Union-Find木を改めて確認しておくと・・・
par[i]はiの親、rank[i]はiの含まれる木のランクを示している。
find,same,initあたりは簡単としてuniteを再確認すると
- まず二要素の親を持っておく。
- ランクを比べる、ランクが大きいほうにランクが小さいほうをつなげる。ただし同じ場合は片方の親にもう片方の親が子になる形になるのでランクは+1される。
で、ランクというのは木の高さ・・・で理解はおk。
もうちょい実装練がんばる
#include <cstdio> #include <cmath> #include <cstring> int par[1001]; int rank[1001]; void init(int n) { for (int i=0; i<n; i++) { par[i]=i; rank[i]=0; } } int find(int x) { if (par[x]==x) { return x; } else { return par[x]=find(par[x]); } } void unite(int x, int y) { x=find(x); y=find(y); if (x==y) return; if (rank[x]<rank[y]) { par[x]=y; } else { par[y]=x; if (rank[x]==rank[y]) rank[x]++; } } bool same(int x, int y) { return find(x)==find(y); } struct pos { int x, y; }; pos cpu[1001]; double dist(int i, int j) { return sqrt((cpu[i].x-cpu[j].x)*(cpu[i].x-cpu[j].x)+(cpu[i].y-cpu[j].y)*(cpu[i].y-cpu[j].y)); } int n, d, p, q; char mode; int con[1001][1001]; bool red[1001]; int main() { scanf("%d%d",&n,&d); memset(con, 0, sizeof(con)); for (int i=0; i<n; i++) { red[i]=false; scanf("%d%d",&cpu[i].x,&cpu[i].y); } init(n); for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { if (dist(i,j)<=d) { con[i][j]=1; con[j][i]=1; } } } while (scanf("%c",&mode)!=EOF) { if (mode=='O') { scanf("%d", &p); red[p-1]=true; for (int i=0; i<n; i++) { if (con[p-1][i]&&red[i]) { unite(p-1,i); // printf("connect: %d %d\n",p-1,i); } // printf("%d root: %d\n",i,find(i)); } } else if (mode=='S') { scanf("%d%d",&p,&q); if (same(p-1,q-1)&&red[p-1]) { // printf("%d root: %d %d root :%d\n",p-1,find(p-1),q-1,find(q-1)); puts("SUCCESS"); } else { puts("FAIL"); } } } }