[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);
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology