CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）【6/9】

6/9

已过：A.B.C.G.H.I

还没过：D.E.F

题目列表

A.完全k叉树

算出层数，判断最后一层的树有没有超过k个

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

int main() {
	int t;
	for(cin>>t; t; t--) {
		ll n, k, cnt = 0, now = 1;
		cin>>k>>n;
		if(k == 1){
			cout<<(n-1)<<endl; 
		}else {
			while(n){
				n -= now;
				now *= k;
				cnt++;
				if(n < now){
					break;
				}
			}
			ll ans;
			if(n == 0) {
				ans = cnt*2-2;
			}else if(n <= now/k){
				ans = cnt*2-1;
			}else {
				ans = cnt*2;
			}
			cout<<ans<<endl;
		}
		
	}
}

B.距离产生美

贪心想，如果相邻两个数差值小于k，改掉后面这个数为特别大的数，那么后面的差值肯定符合，可以跳过

/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
const int maxn = 100005;
const int mod = 1e9+7;
#define line printf("--------------");
using namespace std;
ll a[maxn];
int n, k;
int main() {
	cin>>n>>k;
	for(int i = 0; i < n; i++){
		scanf("%lld", &a[i]);
	} 
	int ans = 0;
	for(int i = 1; i < n; i++) {
		if(abs(a[i]-a[i-1]) < k){
			i++;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

C.烤面包片

1!!! = 1!! = 1! = 1

2!!! = 2!! = 2! =2

4!!! = 24!! > 1e9

我***了这么简单都不知道

所以只有当n=3的情况需要去计算

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll c(ll n, ll p) {
	if(n == 0)return 0;
	ll ans = 1;
	for(int j = 2; j <= n; j++) {
		ans = ans * j % p;
	}
	return ans % p;
}

int main() {
	ll h,k;
	cin>>h>>k;
	if(h == 0) {
		cout<<1%k;
	} else if(h < 3) {
		cout<<h%k;
	} else if (h > 3){
		cout<<0;
	}else {
		ll q = c(h, k);
		q = c(q, k);
		q = c(q, k);
		cout<<q<<endl;
	}

	return 0;
}

G.篮球校赛

直接算出每项能力值前五的人为谁，用个数组存起来，进行dfs

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+5;
bool vis[maxn];
ll co[maxn][6], ans;
int maxx[6][6];
int n;
void dfs(int now, ll tmp){
	if(now == 6){
		ans = max(ans, tmp);
		return;
	}
	for(int i = 1; i <= 5; i++){//循环第now种能力第i大的能力值 
		if(vis[maxx[now][i]]) continue; 
		vis[maxx[now][i]] = 1;
		dfs(now+1, tmp + co[maxx[now][i]][now]);
		vis[maxx[now][i]] = 0;
	}
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= 5; j++){
			scanf("%lld", &co[i][j]);
			for(int k = 1; k <= 5; k++){
				if(co[i][j] > co[maxx[j][k]][j]){
					for(int h = 5; h >= k+1; h--){
						maxx[j][h] = maxx[j][h-1];
					}
					maxx[j][k] = i;
					break;
				}
			}
		}
	}
	dfs(1, 0);
	cout<<ans<<endl;
}

H.分配学号

排个序，对于每一个判断一下其需不需要进行加，需要加的方案数为其与应该增加到的数的差值+1，方案数相乘即可

/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
const int maxn = 100005;
const int mod = 1e9+7;
#define line printf("--------------");
using namespace std;
ll a[maxn];
int n;
int main() {
	cin>>n;
	for(int i = 0; i < n; i++){
		scanf("%lld", &a[i]);
	} 
	sort(a, a+n);
	ll ans = 1;
	
	for(int i = 0, j; i < n; i = j){
		for(j = i+1; j < n && a[j] < a[i] + j-i; j++){
			ans = ans * (a[i]+j-i -a[j]+1) % mod;//当前大小 与最大数的大小的差值就是可以变成的方案数 
//			cout<<ans<<endl;
		}
	}
	cout<<ans<<endl;
	return 0;
}

I.Gree的心房

判断一下方块的数量会不会多到挡到路即可，最优就是靠边的路

/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;

int main() {
	ll n, m, k;
	cin>>n>>m>>k;
	if(k > (n-1) * (m-1)){
		puts("-1");
	}else {
		cout<<n+m-2<<endl;
	}
	return 0;
}