タイトルの案が思い浮かばない。
よし、じゃあこれからJOI模擬練習でも・・・orz
0121
メモ化もしてるのになんだこのTLEはって思ったら、最初はループ判定、次にマップ判定間違えてて、
最終的に最初に全部計算しなきゃTLEになったので計三回程度TLEした←
#include <cstdio> #include <cmath> #include <iostream> #include <string> #include <map> #include <queue> #include <algorithm> using namespace std; const string target="01234567"; struct puzzle { string stat; int zero; puzzle(string _s,int _x) { stat=_s; zero=_x; } }; int d[4]={-1,1,-4,4}; int n; int main() { queue<puzzle> que; map<string, int> done; que.push(puzzle(target,0)); done[target]=0; while (!que.empty()) { puzzle now = que.front(); que.pop(); int pos=now.zero; for (int i=0; i<4; i++) { int nx=pos+d[i]; if ((nx>=0&&nx<4&&pos>=0&&pos<4)|| (nx>=4&&nx<8&&pos>=4&&pos<8)|| (nx>=0&&nx<4&&pos>=4&&pos<8&&abs(nx-pos)==4)|| (nx>=4&&nx<8&&pos>=0&&pos<4&&abs(nx-pos)==4)) { string temp=now.stat; swap(temp[pos],temp[nx]); if (done.count(temp)==0) { que.push(puzzle(temp,nx)); done[temp]=done[now.stat]+1; } } } } while (scanf("%d",&n)!=EOF) { string stats=""; stats+=(n+'0'); for (int i=1; i<8; i++) { scanf("%d",&n); stats+=(n+'0'); } printf("%d\n",done[stats]); } }
0087
やるだけ
#include <iostream> #include <sstream> #include <string> #include <stack> #include <vector> #include <cstdio> using namespace std; int main() { string str; while (getline(cin, str)) { vector<string> vec; stack<double> stc; string temp=""; for (int i=0; i<str.length(); i++) { if (str[i]==' ') { vec.push_back(temp); temp=""; } else { temp+=str[i]; } } if (temp.length()!=0) vec.push_back(temp); for (int i=0; i<vec.size(); i++) { if (vec[i]!="+"&&vec[i]!="-"&&vec[i]!="*"&&vec[i]!="/") { stringstream ss; ss<<vec[i]; int n; ss>>n; stc.push((double)n); } else if (stc.size()>1) { double top=stc.top(); stc.pop(); double top2=stc.top(); stc.pop(); if (vec[i]=="+") stc.push(top+top2); else if (vec[i]=="-") stc.push(top2-top); else if (vec[i]=="*") stc.push(top*top2); else if (vec[i]=="/") stc.push(top2/top); } } printf("%.6f\n",stc.top()); } }
0189
ワーシャルフロイドやるだけ
#include <cstdio> #include <cstring> #include <climits> #include <set> #include <algorithm> using namespace std; typedef long long ll; ll dist[10][10]; int main() { int n; while (scanf("%d",&n)!=EOF) { if (!n) break; for (int i=0; i<10; i++) for (int j=0; j<10; j++) { if (i==j) dist[i][j]=0; else dist[i][j]=INT_MAX; } set<int> town; int a, b, c; for (int i=0; i<n; i++) { scanf("%d%d%d",&a,&b,&c); dist[a][b]=c; dist[b][a]=c; town.insert(a); town.insert(b); } int sz=town.size(); for (int k=0; k<sz; k++) { for (int i=0; i<sz; i++) { for (int j=0; j<sz; j++) { dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } } } int rpos, res=INT_MAX; for (int i=0; i<sz; i++) { int sum=0; for (int j=0; j<sz; j++) if (dist[i][j]!=INT_MAX) sum+=dist[i][j]; if (sum<res) { rpos=i; res=sum; } } printf("%d %d\n",rpos,res); } }
0525
Rが少ないことに着目して横一列を裏返すか裏返さないかのパターンを全列挙。
これはbit使います。
それであとは縦に1の数を数えたとき1と0の数の多いほうを合計したのが答えになる。
#include <cstdio> #include <algorithm> using namespace std; int osen[10][10000]; int main() { int r, c; while (scanf("%d%d",&r,&c)) { if (!r&&!c) break; for (int i=0; i<r; i++) for (int j=0; j<c; j++) { scanf("%d", &osen[i][j]); } int res=0; for (int S=0; S < 1<<r; S++) { for (int i=0; i<r; i++) { if (S>>i&1) { for (int j=0; j<c; j++) osen[i][j]^=1; } } int cnt=0; for (int i=0; i<c; i++) { int one=0; for (int j=0; j<r; j++) one+=osen[j][i]; cnt+=max(one,r-one); } for (int i=0; i<r; i++) { if (S>>i&1) { for (int j=0; j<c; j++) osen[i][j]^=1; } } res=max(res,cnt); } printf("%d\n",res); } }