T1
有形如下分形
0 1 0 2 0 1 0 3
1 1 2 2 1 1 3 3
0 2 0 2 0 3 0 3
2 2 2 2 3 3 3 3
0 1 0 3 0 1 0 3
1 1 3 3 1 1 3 3
0 3 0 3 0 3 0 3
3 3 3 3 3 3 3 3
输出他.
Sol
略.
T2
多组询问，每次问如上分形坐标 \((x,y)\) 处的数.（第 \(x\) 行第 \(y\) 列）
Sol 1
dfs.
typedef unsigned int ui;
int dfs(ui x, ui y, int c) {
if (c == 1) return (x != 1) || (y != 1);
if (x > y) swap(x, y);
ui p = 1 << (c - 1);
int ans = 0;
if (x <= p && y <= p) ans = dfs(x, y, c - 1);
else if (x <= p && y > p) ans = dfs(x, y - p, c - 1), ans += ans == c - 1;
else if (x > p) ans = dfs(x - p, y - p, c - 1), ans += ans == c - 1;
else return assert(0), 0;
return ans;
}
void solve() {
ui x, y;
scanf("%u%u", &x, &y);
printf("%d\n", dfs(x, y, 31));
}
效率低、代码长.
Sol 2
观察发现很奇妙的结论.
void solve() {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", __builtin_ctz(~((x - 1) | (y - 1))));
}
总结
根据这个结论，我们可以轻松输出如上分形！
标签：输出,return,int,dfs,分形,ui,ans From： https://www.cnblogs.com/laijinyi/p/18544592