るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

AOJ

AOJ 1001 Binary Tree Intersection And Union

AOJ

[問題文] AIZU ONLINE JUDGE [解法] 構文解析 慣れていないのでかなり時間がかかった。 こんなやつの解析 <exp>::= "(" , <exp> , <exp> , ")" | "" 結構楽しい。 struct E{ int l,r,id; int over; E(){ l = r = -1 ,id = 0; over = 0;} }; int now; int p = 0; E memo[400]</exp></exp></exp>…

AOJ 1016 Fibonacci Sets

AOJ

[問題文] AIZU ONLINE JUDGE [解法] dp + UF木 数列を作っておいて、UF木で集合を作る。 int par[2000]; int rank[2000]; void init(int n){ rep(i,n) par[i] = i; memset(rank,0,sizeof(rank)); } int find(int x){ if(par[x] == x) return x; return par[x…

AOJ 0233 Book Arrangement

AOJ

問題文→AIZU ONLINE JUDGE 10進数を-10進数に直す問題。 x mod (-10)^nをやっていく (負になった時は正にしてやる) string Trans(int n){ string ans=""; while(n != 0){ int mod=n%(-10); int nxt=n/(-10); if(mod < 0){ mod+=10; nxt++; } char c='0'+mod;…

AOJ 0531 Paint Color

AOJ

問題文→AIZU ONLINE JUDGEテープが貼ってあるので、囲まれる領域の数を答える問題。 座標圧縮+幅優先でいける。座標圧縮の解説が少なすぎて萎え...一応この問題、第7回JOIの本選5番なのでそこの解説を見れば座標圧縮の大まかな説明が載っている→ 書く量多す…

AOJ 0530 Pyon-Pyon River Crossing

AOJ

問題文→AIZU ONLINE JUDGE正解者数少なかったので、怖くて手をつけていなかった問題。やっと解けたのですごく嬉しいです。メモ化探索しました(ほとんどの方がdpしていたのでそっちの方が良かったかも...) #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #inc</string></vector></algorithm></cstdio></iostream>…

AOJ 0131 Doctor's Strange Particles

AOJ

問題文→ AIZU ONLINE JUDGE「あるマスを選んでそこの数字を反転(1 0)させる。 この時そのマスの上下左右も反転する。 すべてを0にするために必要な反転箇所を求めよ」 という問題。普通に考えたら O(2^100)とかで無理。 そこで一番上の行の反転の仕方を一意…

AOJ 0078 Magic Square

AOJ

問題文→AIZU ONLINE JUDGEマスの数を指定して魔法陣を出力する問題 #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<cmath> #include<map> using namespace std; int context[15][15]; void init(){ for(int i=0;i<15;i++){ for(int j=0;j<15;j++){ context[i][j</map></cmath></string></vector></algorithm></cstdio></iostream>…