2019CCF-CSP-S2(NOIP2019) Solution

D1T1 格雷码

按照题目要求,使用递归求解。

注意使用unsigned long long,并且不要出现1ll<<64

有dalao找到了规律k^(k>>1),tql!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>

using LL = long long;
using ULL = unsigned long long;

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

const int inf = 0x7fffffff;
const LL linf = 0x7fffffffffffffff;

ULL solve(ULL n,ULL k)
{
if(n==1ull)
{
return k;
}
else if(k < (1ull<<(n-1))) // k < 2^(n-1)
{
return solve(n-1,k);
}
else // k >= 2^(n-1)
{
return solve(n-1, (1ull<<(n-1)) - k + (1ull<<(n-1)) -1ull) + (1ull<<(n-1));
}
}

int main(int argc, char *argv[])
{
ULL n,k;
scanf("%llu%llu",&n,&k);
ULL ans=solve(n,k);
for(int i=n-1;i>=0;i--)
{
printf("%llu",(ans>>i)&1);
}
puts("");
return 0;
}

D1T2

咕咕咕

D1T3

咕咕咕

D2T1

咕咕咕

D2T2

咕咕咕

D2T3

咕咕咕