「CSP-S 2019」题解

~~今年的题真是毒瘤~~,一个蒟蒻要来写题解了

校门外有两棵树,一棵叫括号树一棵叫树上的数,这两棵树要被一匹叫格雷的马划分开为Emiya做饭,这两棵树问:那你猜猜我们的重心在哪啊

$D1T1$ 格雷码

沙雕暴力dfs(我的做法)

考场上真是脑残了,拿dfs模拟,忘了二分的事了,还传了四个参数
注意:一定要用unsigned long long

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <ctype.h>
using namespace std;
typedef unsigned long long ull;

inline ull read() {
	ull x = 0, f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}

const int maxn = 64;

ull n, k;

void dfs(ull n, ull k, ull rev, ull from) {
	if (n == 1) {
		if (rev == 0) {
			if (k == 0) printf("0");
			else printf("1");
		} else {
			if (k == 0) printf("1");
			else printf("0");
		}
		return;
	}
	if (k <= (1LL << (n - 1LL)) - 1LL) {
		if (rev == 0 && from == 0) {
			printf("0");
			dfs(n - 1LL, k, 0LL, 0LL);
		} else if (rev == 0 && from == 1) {
			printf("0");
			dfs(n - 1LL, k, 1LL, 0LL);
		} else if (rev == 1 && from == 0) {
			printf("1");
			dfs(n - 1LL, k, 0LL, 0LL);
		} else {
			printf("1");
			dfs(n - 1LL, k, 0LL, 0LL);
		}
	} else {
		if (rev == 0 && from == 0) {
			printf("1");
			dfs(n - 1LL, k - (1LL << (n - 1LL)), 1LL, 1LL);
		} else if (rev == 1 && from == 0) {
			printf("0");
			dfs(n - 1LL, k - (1LL << (n - 1LL)), 0LL, 1LL);
		} else if (rev == 0 && from == 1) {
			printf("1");
			dfs(n - 1LL, k - (1LL << (n - 1LL)), 0LL, 1LL);
		} else {
			printf("0");
			dfs(n - 1LL, k - (1LL << (n - 1LL)), 1LL, 1LL);
		}
	}
}

int main() {
	n = read(); k = read();
	dfs(n, k, 0, 0);
	printf("\n");
	return 0;
}
/* 55ms 812kB */

二分模拟($lyd$巨佬的做法)

考前做过一道类似的题,但可惜我忘了
$lyd$巨佬说他这题只做了15分钟

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
unsigned long long n,k;
unsigned long long two[65];
int change=0;
int main()
{
	two[0]=1;
	for(int i=1;i<=63;i++)
	{
		two[i]=two[i-1]*2;
	}
	cin>>n>>k;
	while(n>0)
	{
		if(k>=two[n-1])
		{
			if(!change)
			{
				printf("1");
				change^=1;
			}
			else
			{
				printf("0");
			}
			k-=two[n-1];
		}
		else
		{
			if(change)
			{
				printf("1");
				change^=1;
			}
			else
			{
				printf("0");
			}
		}
		n--;
	}
	return 0;
}
/* 57ms 928kB */

位运算正解

格雷码的规律就是
第$i$位为$k\ xor\ \lfloor\frac{k}{2}\rfloor$的第$i$位

#include <bits/stdc++.h>
using namespace std;

int n;
unsigned long long k;

int main() {
    scanf("%d %llu", &n, &k);
    k ^= (k >> 1);
    while (n--) {
        printf("%d", (k >> n & 1));
    }
    puts("");
    return 0;
}
/* 54ms 932kB */

$D1T2$ 括号树

后面的先咕着,等着补

$D1T3$ 树上的数

$D2T1$ $Emiya$家今天的饭

$D2T2$ 划分

$D2T3$ 树的重心