[TIOJ] 1117. Walsh code
題目連結: http://tioj.infor.org/problems/1117 學測念不完，可是又要北市賽了QQ只好把市賽題刷一刷，希望至少市賽不要出事 最近真的好笨，只會一些straightforward的題目，這題還是被雷的才出來的。 總之核心問題就是我們不能一次做太多事、要一步一步來，畢竟他每次要輸出的字串也沒多長。 那所以我們就每次要知道第n個矩陣的第i,j元素，而這可以直接根據定義直接看他在哪一塊，並且遞迴下去就會得知答案了。 #include <bits/stdc++.h>
using namespace std;
bool go(int,int,int);
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
for(int n, i, a, b;cin >> n >> i >> a >> b;){
for(int j=a;j<=b;j++)
cout << (go(n, i-1, j-1)?"+1":"-1") << " \n"[j==b];
}
return 0;
}
bool go(int n, int x, int y) {
if(n == 0) return 0;
int tl = (1<<(n-1));
if(x >= tl and y >= tl) return go(n-1, x-tl, y-tl)^1;
if(x >= tl) x -= tl;
if(y >= tl) y -= tl;
return go(n-1, x, y);
}