敗戦記

PKU 1610 Quad Trees

PKU

http://poj.org/problem?id=1610

白黒の画像データを、同じ部分をまとめて符号化して出力するというような問題。

再帰。

結構時間ギリギリでした

bool in[512][512];
map<int,vector<int> > ans;

void dfs(int x,int y,int n){
  set<bool> app;
  rep(i,n)rep(j,n)app.insert(in[x+i][y+j]);
  if(app.size()==1)ans[-n].pb(0),ans[-n].pb(*app.begin());
  else{
    ans[-n].pb(1);
    dfs(x,y,n/2);
    dfs(x,y+n/2,n/2);
    dfs(x+n/2,y,n/2);
    dfs(x+n/2,y+n/2,n/2);
  }
}

main(){
  int t;
  cin>>t;
  while(t--){
    ans.clear();
    int n;
    cin>>n;
    rep(i,n)rep(j,n)cin>>in[i][j];
    dfs(0,0,n);
    vector<int> vec;
    FOR(miter,ans)vec.insert(vec.end(),ALL(miter->S));
    reverse(ALL(vec));
    string out;
    rep(i,SZ(vec)){
      int p=0;
      rep(j,4){
        if(i+j<SZ(vec))p+=vec[i+j]<<j;
      }
      i+=3;
      if(p<9)out+=(p+'0');
      else out+=(p-10+'A');
    }
    reverse(ALL(out));
    cout<<out<<endl;
  }
}

Permalink | コメント(0) | トラックバック(0) | 20:00

PKU 1684 Dynamic Declaration Language (DDL)

PKU

http://poj.org/problem?id=1684

与えられたように簡易的な言語のようなものを実装する。

エラーコードの出力ミスで1WA

全く読みやすくないゴミソースになってます。

int toi(const string&in){
  int ret=0;
  rep(i,SZ(in))ret=ret*10+in[i]-'0';
  return ret;
}

main(){
  int test;
  cin>>test;
  rep(sc,test){
    cout<<sc+1<<endl;
    int n;
    cin>>n;
    cin.ignore();
    string in[n];
    rep(i,n){
      string temp;
      getline(cin,temp);
      rep(j,SZ(temp))if(temp[j]!=' ')in[i]+=temp[j];
    }
    map<int,PI> dec;
    rep(i,n){
      const string& str=in[i];
      if(str[1]=='='){
        int id=str[0];
        int num=toi(str.substr(2));
        if(dec.count(id))dec[id]=mp(num,1);
        else cout<<i+1<<' '<<2<<endl;
      }else if(str[0]=='G'){
        if(isalpha(str[4])){
          int id=str[4];
          int num=toi(str.substr(5));
          if(dec.count(id)){
            dec[id].S=1;
            if(dec[id].F>0)i=num-2;
          }else cout<<i+1<<' '<<2<<endl;
        }else{
          int num=toi(str.substr(4));
          i=num-2;
        }
      }else if(str[1]=='C'){
        int id=str[3];
        if(dec.count(id) && dec[id].S){
          dec[id]=mp(0,0);
        }else if(dec.count(id)){
          cout<<i+1<<' '<<1<<endl;
        }else dec[id]=mp(0,0);
      }else if(str[0]=='I'){
        if(dec.count(str[3]))dec[str[3]].F++,dec[str[3]].S=1;
        else cout<<i+1<<' '<<2<<endl;
      }else if(str[0]=='E'){
        break;
      }else if(str[0]=='D'){
        if(dec.count(str[3]))dec[str[3]].F--,dec[str[3]].S=1;
        else cout<<i+1<<' '<<2<<endl;
      }
    }
  }
}

Permalink | コメント(0) | トラックバック(0) | 16:45

PKU 2993 Emag eht htiw Em Pleh

PKU

http://poj.org/problem?id=2993

先程の問題の入出力を逆にするバージョン。

こちらのほうが微妙に楽な気がします。

これも書くだけ。

main(){
  vector<string> ans(17,string(33,' '));
  for(int i=0;i<17;i+=2){
    for(int j=0;j<33;j+=4){
      if(i)ans[i-1][j]='|';
      ans[i][j]='+';
      if(j){
        int x=i/2,y=j/4;
        rep(k,3){
          ans[i][j-k-1]='-';
          if(i && (x+y)%2)ans[i-1][j-k-1]='.';
          else if(i)ans[i-1][j-k-1]=':';
        }
      }
    }
  }
  rep(rp,2){
    string in;
    getline(cin,in);
    int pos;
    while(true){
      pos=in.find(',');
      if(pos==string::npos)break;
      in[pos]=' ';
    }
    stringstream ss(in.substr(7));
    while(ss>>in){
      char cc;
      if(SZ(in)==2)cc='P'+rp*('p'-'P');
      else cc=in[0]-rp*('P'-'p');
      int y=(in[SZ(in)-2]-'a')*4+2,x=(in[SZ(in)-1]-'1')*2+1;
      ans[x][y]=cc;
    }
  }
  reverse(ALL(ans));
  rep(i,17){
    cout<<ans[i]<<endl;
  }
}

Permalink | コメント(0) | トラックバック(0) | 15:57

PKU 2996 Help Me with the Game

PKU

http://poj.org/problem?id=2996

チェスボードを読み取ってそれぞれの駒の場所を出力するというような問題。

書くだけ。

いろいろと楽をしようと思ったけれど、あまり簡潔に書けてないです。

main(){
  map<char,set<PI> >ans;
  rep(i,17){
    string in;
    cin>>in;
    rep(j,SZ(in))
      if(isalpha(in[j])){
        if(isupper(in[j]))ans[in[j]].insert(mp(7-(i-1)/2+1,(j-2)/4+1));
        else ans[in[j]].insert(mp((i-1)/2-8,(j-2)/4+1));
      }
  }
  string out="KQRBNP";
  rep(re,2){
    if(!re)cout<<"White: ";
    else cout<<"Black: ";
    rep(i,SZ(out)){
      switch(toupper(out[i])){
      case 'R':
      case 'B':
        FOR(siter,ans[out[i]])cout<<','<<(char)toupper(out[i])<<char(siter->S+'a'-1)<<abs(siter->F);
        break;
      case 'P':
        FOR(siter,ans[out[i]])cout<<','<<char(siter->S+'a'-1)<<abs(siter->F);
        break;
      case 'K':
        FOR(siter,ans[out[i]])cout<<(char)toupper(out[i])<<char(siter->S+'a'-1)<<abs(siter->F);
        break;
      default:
        FOR(siter,ans[out[i]])cout<<','<<(char)toupper(out[i])<<char(siter->S+'a'-1)<<abs(siter->F);
        break;
      }
      out[i]=tolower(out[i]);
    }
    cout<<endl;
  }
}

Permalink | コメント(0) | トラックバック(0) | 15:34

PKU 2992 Divisors

PKU

http://poj.org/problem?id=2992

nCkの約数の個数を求める。(0<=k<=n<=431)

cinの遅さを改めて実感しました。

あと、高速化するのが大変でした。

素因数分解して事前計算して、頑張りました。

map<int,int> fac[432];
ll ans[432][432];

map<int,int> ret;
map<int,int> fact(int in){
  ret.clear();
  for(int i=2;i*i<=in;i++){
    if(in%i)continue;
    do{
      ret[i]++;
      in/=i;
    }while(in%i==0);
  }
  if(in>1)ret[in]++;
  return ret;
}

map<int,int> tt;
main(){
  rep(i,432){
    fac[i]=fact(i);
  }

  rep(n,432){
    tt.clear();
    rep(k,n+1){
      if(ans[n][min(k,n-k)])break;
      if(0<k)FOR(miter,fac[n-k+1])tt[miter->F]+=miter->S;
      FOR(miter,fac[k])tt[miter->F]-=miter->S;
      ll tans=1;
      FOR(miter,tt){
        tans*=miter->S+1;
      }
      ans[n][k]=tans;
    }
  }

  int n,k;
  while(~scanf("%d%d",&n,&k))cout<<ans[n][min(k,n-k)]<<endl;
}

Permalink | コメント(0) | トラックバック(0) | 11:41