牛客小白月赛55 A-E 回顾

A 至至子的等差中项

$2\ast b=a+c$
$c=2\ast b-a$

#include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;
ll a,b;
int main(){
	cin>>a>>b;
	cout<<2*b-a;	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

B 至至子的按位与

a&c=b&c
我们转化为二进制来计算，最多有 c 63位 ，我们考虑 每一位具体取值
a b c
1 1 1
1 0 0
0 1 0
0 0 1

按照这个规律我们计算出 c 二进制的每一位后转换为十进制即可

#include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

ll a[100],c,d;
ll a1[100],a2[100],c1,c2,ans;

int main(){
	
	cin>>c>>d;
	
	while(c){
		a1[++c1]=c%2;
		c/=2;
	}
	
	while(d){
		a2[++c2]=d%2;
		d/=2;
	}
	
	for(int i=1;i<=63;i++){
		if(a1[i]==a2[i]){
			ans+=(ll)pow(2,i-1);
		}
	}
	
	cout<<ans;		
	return 0;
}
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

C 至至子的斐波那契

已知斐波那契数列成指数级增长，我们可以发现求到92项左右就会超过 ll 的范围，所以我们打表出斐波那契前 92 项的值，用 map 建立起 值和下标的映射 ， 然后用map 的 lowerbound 去求即可

注意 map set 二分函数返回的是迭代器

#include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

map<ll,int>mp;
ll a[1001];
ll t,k,ans;

int main(){
	
	a[1]=1;
	a[2]=1;
	mp[1]=1;
	
	for(int i=3;i<=92;i++){
		a[i]=a[i-1]+a[i-2];
		mp[a[i]]=i;
	}
	
	cin>>t;
	
	while(t--){
			cin>>k;
			auto it = mp.lower_bound(k);
			auto it1 = it;
			it--; 
        // it it1
			if(abs(it1->first - k) >= abs(k - it->first)){
				ans = it->second;
			}else{
				ans = it1 -> second;
			}
		
		cout<<ans<<"\n";
	}
	
	
	return 0;
}
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
49

D 至至子的鸿门宴

无论开始序列如何，序列都会变成 1 2 3 - - - n 这个形式 ， 计算出变到这个形式的步数，奇数ZZZ赢偶数SSZ赢

#include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int n;
ll ans,a[N];

int main(){
	
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ans+=(a[i]-i);
	}
	
//	cout<
	
	if(ans%2!=0){
		cout<<"ZZZ";
	}else{
		cout<<"SSZ";
	}
		
	return 0;
}
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

E 至至子的长链剖分

构造，需要满足三个条件

1. 任意 cnt[$h_i$] != 0
   书高如果出现 0 1 2 4 显然是不合理的
2. cnt[root] == 1
   只能有一个根，不然就成森林了，不是树；
3. cnt[$h_i$] >= cnt[$h_{i+1}$]
   0 1 1 2 这样显然不是树

那怎么构造呢 0 0 0 0 0 1 1 1 2 2 2 3 3 4 5

构造方法是
5
4
3 3
2 2 2
1 1 1
0 0 0 0 0

从叶节点开始 ，对应的一一连结，多出来的连结任意一个即可

#include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int t,n;
int a[N],b[N];//b 数组用来记录树高的数量
vector<int>ve[N];
int mx;

int main(){
	
	scanf("%d",&t);
	
	while(t--){
		
		for(int i=0;i<=mx;i++){
			ve[i].clear();
			b[i]=0;
		}
		//初始化，很巧妙的初始化，用上次的最大链长初始化，优化了时间复杂度
		
		mx=0;
		
		cin>>n;
				
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			mx=max(mx,a[i]);
			ve[a[i]].push_back(i);
			b[a[i]]++;
		}
		
		
		
		//根节点只能有一个
		if(b[mx]>1){
			cout<<"-1\n";
			continue;	
		}
		
		
		
		//b[i]!=0 && b[i]>=b[i+1]
		bool f=1;
		for(int i=0;i<mx;i++){
			if(b[i+1]>b[i]||b[i]==0){
				f=0;
				cout<<"-1\n";
				break;
			}
		}
		if(!f) continue;
		
		cout<<ve[mx][0]<<"\n";
		
		
		for(int i=0;i<mx;i++){
			int l1=ve[i].size();
			int l2=ve[i+1].size();
			
			for(int j=0;j<l2;j++){
				printf("%d %d\n",ve[i][j],ve[i+1][j]);
			}
			
			for(int j=l2;j<l1;j++){
				printf("%d %d\n",ve[i][j],ve[i+1][l2-1]);
			}
		}	
	}
	return 0;
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81