CCF精英赛算法题目

A完美金字塔

古埃及的法老现在要为他自己修一座巨大的金字塔，为了使金字塔永存他从世界各地找来了各种各样的石头，每种石头都能够预防特定的灾害。现在我们给每种石头一个编号，使得所有石头的编号都等于下一层压着的石头编号之和，例如以下金字塔：

1
2
3
   4
 2   2
1 1 1 1

换句话来说，我们规定最底层的石头编号为 1，之后每层均由下层从左右两端同时向中间合并得到，合并后新石头的编号为合并前石头编号总和，可能会出现如下情况：

img

（在第四种情况中，编号3的石头视为压着3个编号1的石头）

现在想知道，指定编号的石头的总数各有多少个？

输入输出格式

输入格式：

  • 第一行输入两个整数 n 和 m，分别表示最底层的石头数量 和 询问次数
  • 接下来 m 个整数，每个整数表示询问的石头编号

输出格式：

  • 输出 m 个整数，表示每次询问对应石头的总数

输入输出样例

输入样例1：

1
2
10 5
1 2 3 4 10

输出样例1：

1
10 6 0 2 1

样例1解释：

如下图最底层的10块石头都为1，按照以上规则进行两两合并，得到5个2 。再往上一层由于合并是从最左和最右开始的，所以先合出边缘的2个4，然后中间还剩一个2 。 最后3个合成一个 10 。

1
2
3
4
        10
   4     2     4
 2   2   2   2   2   
1 1 1 1 1 1 1 1 1 1

测试点

共20个测试点。

时间限制2s，空间限制128MiB。

数据范围：$1≤n≤10{15},1≤m≤106 $

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
#include<bits/stdc++.h>
using namespace std;
map<long long,long long> mp;
signed main()
{
	long long n,m,a;
	cin >> n >> m;
	long long mid = 0;
	long long other = 1;
	long long cnt = n;
	mp[1] += n;
	while(cnt)
	{
		long long next_cnt = 0;
		if(cnt <= 3)
		{
			if(n != 1)
			{
				mp[n] ++;
			}
			break;
		}
		long long a = cnt/2;
		//printf("a = %lld other = %lld cnt = %lld\n",a,other,cnt);
		if(cnt % 2 != 0){
			if(a % 2 != 0)
			{
				a --;
				if(mid == 0)
				{
					mid = other * 3;
				}
				else
				{
					mid = mid + other * 2;
				}
			}
			else {
				if(mid == 0)
				{
					mid = other;
				}
			}
			mp[mid] ++;
			next_cnt ++;
			//printf("mid = %lld mp[mid] = %lld\n",mid,mp[mid]);
		}
		other = other * 2;
		mp[other] += a;
		next_cnt += a;
		cnt = next_cnt;
	}
	for(int i = 1;i<=m;i++)
	{
		if(i != 1) 
		{
			cout << " ";
		}
		cin >> a;
		cout << mp[a];
	}
	return 0;
}

B 两端对齐

小明最近在用软件写文档时发现，在英文内容的键入时，软件会自动添加一些额外的空格到内容中，使得整段英文在文本区域的两端对齐，并且不会出现单个单词被拆分到两行的情况，看上去整齐又美观。

现在给定一篇文章中的n个单词，请试着将其按顺序以“两端对齐”的方式输出，要求：

  • 单词间至少由一个空格隔开，行末单词后无空格
  • 各行字符数均为m个，必要时可以在单词间补充额外的空格
  • 一行内单词间的空格数要尽量相同，若始终不能均匀分配，那么左侧的空格数可以多一些
  • 输出行数要尽可能少一些，也即每行放置的单词要尽可能多一些
  • 最后一行要左对齐，单词间不再插入额外的空格，末尾补空格至m个字符

输入输出格式

输入格式：

  • 第一行输入两个数n、m
  • 接下来n行，每行1个单词，均由小写字母构成

输出格式：

  • 输出排版后的文章（数据保证有解）

输入输出样例

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10 14
to
be
or
not
to
be
that
is
a
question

输出样例：

1
2
3
to  be  or not
to  be that is
a question

样例说明：

第1行在前两个单词后分别额外添加了一个空格； 第2行在第一个单词后额外添加了一个空格； 最后一行在末尾额外添加了4个空格。 各行均为14个字符，输出的换行符不算入m。

测试点

20个测试点。

每个测试点时间限制2s，内存限制128MiB。

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
#include<bits/stdc++.h>
using namespace std;
string str[10100];
int size[10100];
int main() {
	int n,m;
	cin >> n >> m;
	for(int i = 1;i<=n;i++){
		cin >> str[i];
		size[i] = str[i].length();
	}
	int left = 1;
	int num = 0;
	int cnt = 0;
	while(left + cnt <= n)
	{
		//printf("left + cnt = %d\n",left + cnt);
		int next_num = num + size[left + cnt];
		if(cnt != 0){
			next_num ++;
		}
		//printf(" next_num = %d\n", next_num);
		if(next_num > m){
			int shengyu = m - num;
			int add = 0;
			int zuobian = 0;
			if(cnt == 1){
				add = shengyu;
				zuobian = -1;
			}else {
				add = shengyu / (cnt - 1);
				zuobian = shengyu - (cnt - 1) * add;
			}
			//printf(" shengyu = %d add = %d zuobian = %d cnt = %d m = %d\n", shengyu,add,zuobian,cnt,m);
			for(int i = 0;i<cnt;i++)
			{
				if(i != 0)
				{
					cout << " ";
				}
				cout << str[left + i];
				if(i != cnt - 1)
				{
					if(i + 1<= zuobian)
					{
						cout << " ";
					}
					for(int j = 1;j<=add;j++)
					{
						cout << " ";
					}
				}
			}
			cout << endl;
			left += cnt;
			cnt = 0;
			num = 0;
		} else{
			cnt++;
			num = next_num;
		}
	}
	//printf("YES\n");
	if(left <= n){
		//printf("YES\n");
		int s = 0;
		for(int i = left; i <= n;i++)
		{
			if(i != left){
				cout << " ";
				s ++;
			}
			cout << str[i];
			s += size[i];
		}
		for(int i = s+1;i<=m;i++){
			cout << " ";
		}
	}
	return 0;
}

C 光线折射

有一个小房间，光线从左下角沿45度角射入，问k次折射后的位置。

注：正好射向房间一角的话，光线会沿原路反射回去。

输入输出格式

输入格式：

  • 第一行输入 n、m、k，分别表示房间大小和折射次数

输出格式：

  • 输出光线在第k次折射后停留的坐标

输入输出样例

输入样例1：

1
4 5 2

输出样例1：

1
0 2

样例1解释：

img

如图，光线行进路线为OBCD。

测试点

共20个测试点

时间限制1s，空间限制128MiB。

数据范围: 

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
int x,y;
int fangxiang = 0;
signed main()
{
	cin >> n >> m >> k;
	x = 0;
	y = 0;
	for(int i = 1;i<=k+1;i++){
		switch(fangxiang)
		{
			case 0:{
				int dis = min(n-x,m-y);
				x += dis;
				y += dis;
				if(x == n && y == m){
					fangxiang = 2;
				} else if(x == n) {
					fangxiang = 1;
				} else {
					fangxiang = 3;
				}
				break;
			}
			case 1:{
				int dis = min(x, m-y);
				x -= dis;
				y += dis;
				if(x == 0 && y == m){
					fangxiang = 3;
				} else if(x == 0) {
					fangxiang = 0;
				} else {
					fangxiang = 2;
				}
				break;
			}
			case 2:{
				int dis = min(x, y);
				x -= dis;
				y -= dis;
				if(x == 0 && y == 0){
					fangxiang = 0;
				} else if(x == 0) {
					fangxiang = 3;
				} else {
					fangxiang = 1;
				}
				break;
			}
			case 3:{
				int dis = min(n-x,y);
				x += dis;
				y -= dis;
				if(x == n && y == 0){
					fangxiang = 1;
				} else if(x == n) {
					fangxiang = 2;
				} else {
					fangxiang = 0;
				}
				break;
			}
		}
	}
	cout<< x << " "<< y << endl;
}

D 根号拆分

在数学上，若a∗a=b的话，那么可以记为，读作a等于根号b。

在根号运算中，可以拆分为，比如

现在希望知道的是，给定一个数x，将其拆分为也即形式时最大的a是多少，（a,b,x均为正整数且b≥1）。

输入输出格式

输入格式：

  • 第一行输入一个数n，表示询问次数
  • 之后n行，每行一个数x*，表示要拆分的数

输出格式：

  • 输出n行，每行一个数，表示每个询问拆分后得到的最大的a*

输入输出样例

输入样例：

1
2
3
2
75
81

输出样例：

1
2
5
9

样例说明：

75=5∗5∗3、81=9∗9∗175=5∗5∗3、81=9∗9∗1

测试点

一共20个测试点

每个测试点时间限制为1s，空间限制为128MiB

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
#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;

// 预处理函数：生成所有小于等于 sqrt(10^12) 的质数
vector<long long> sieve(long long max_val) {
    vector<bool> is_prime(max_val + 1, true);
    vector<long long> primes;
    is_prime[0] = is_prime[1] = false;
    for (long long i = 2; i <= max_val; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (long long j = i * i; j <= max_val; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

long long max_a = 1;

// 函数：质因数分解，返回数 x 的所有质因子及其幂次
long long prime_factorize(long long x, const vector<long long>& primes) {
    max_a = 1;
    unordered_map<long long, int> factors;
    
    for (long long p : primes) {
        
        if (p * p > x) break;  // 质数的平方超过 x 就可以停止
        while (x % p == 0) {
            factors[p]++;
            if(factors[p]%2==0) // 是二的倍数 需要乘了
            {
                max_a *= p;
            }
            x /= p;
        }
    }
    if (x > 1) {
        factors[x]++;
    }
    return max_a;
}


int main() {
      std::ios::sync_with_stdio(false);
    const long long MAX_X = 1e12;
    const long long MAX_PRIME = sqrt(MAX_X);  // 平方根上限
    vector<long long> primes = sieve(MAX_PRIME);  // 预处理质数
    
    

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        long long result =  prime_factorize(x, primes);
        cout << result<<"\n";
    }
    
    return 0;
}

G二分图

题目描述

小明在学校的编程课上了解到了关于二分图的相关知识，所谓的二分图是一种特殊的图，图中的所有顶点可以分为两个不相交的集合，而图中的所有边的两个顶点都分属于这两个集合。

换句话来说，二分图是可以进行黑白染色的图，即给图中所有顶点都涂上黑色或者白色，使得每条边的两个端点都异色。

现在小明想知道，对于任意的一个n个顶点m*条边的无向图，通过删去一条边使其变为二分图的方案数是多少？

输入输出格式

输入格式：

  • 第一行输入两个数n、m，表示图的顶点数和边数
  • 接下来m行，每行两个数x、y，表示一条边（编号1～1～m）

输出格式：

  • 第一行输出一个数k，表示答案方案数
  • 第二行输出k个数，表示k条边的编号，升序排列

输入输出样例

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
9 12
1 2
1 3
2 4
2 5
3 5
4 6
4 7
5 7
6 8
7 8
7 9
8 9

输出样例：

1
2
2
11 12

样例说明：

如图，删去两条黑色边的任意一条（边编号为11、12），均可使图成为二分图。

img

测试点

一共20个测试点。

每个测试点时间限制为1s，空间限制为128MiB。

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 1000010
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 100000007
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
int head[N], u, v, n, m, ans[N], cans, p[N], fl[N];
struct edge{
    int nxt, v, id;
}e[N << 1];
int tot = 1, d[N];
int c1[N], c2[N], cnt;
inline void addedge (int u, int v, int id)
{
    e[++tot] = (edge) {head[u], v, id};
    head[u] = tot;
}
inline void dfs (int u, int fa, int pre)
{
    d[u] = d[fa] + 1; p[u] = e[pre].id;
    edge (i, u)
    {
        if ((i ^ pre) == 1) continue;
        if (!d[v])
        {
            dfs(v, u, i);
            fl[e[i].id] = 1;
            c1[e[pre].id] += c1[e[i].id]; c2[e[pre].id] += c2[e[i].id];
        }
        else
        {
            if (u == v && i & 1)
            {
                ++c1[e[i].id]; ++cnt;
            }
            else
            {
                if (d[u] > d[v])
                if ((d[u] - d[v]) & 1)
                {
                    ++c2[e[i].id];
                    ++c2[e[pre].id];
                    --c2[p[v]];
                }
                else
                {
                    ++c1[e[i].id];
                    ++c1[e[pre].id];
                    --c1[p[v]];
                    ++cnt;
                }
            }
        }
    }
}
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, m)
    {
        scanf("%d %d", &u, &v);
        addedge(u, v, i);
        addedge(v, u, i);
    }
    fo (i, 1, n)
        if (!d[i]) dfs(i, 0, 0);
    if (!cnt)
        fo (i, 1, m)
            ans[++cans] = i;
    else
    fo (i, 1, m)
        if (fl[i])
        {
            if (c1[i] == cnt && !c2[i])
            {
                ans[++cans] = i;
            }
        }
        else
        {
            if (cnt == 1 && c1[i] == 1)
                ans[++cans] = i;
        }
    printf("%d\n", cans);
    fo (i, 1, cans)
        printf("%d ", ans[i]);
    return 0;
}

J 抢红包

题目描述

巨信软件开发了一个抢红包的功能，群里的每个人点开红包就会获得红包额度的一部分金额。

产品经理提出了抢红包的需求：

  1. 群里人数为n，则红包的额度设置为2 * n-1。
  2. 在红包生成的一瞬间，群里每个人就已经被分配了金额，点开红包时获得该金额。
  3. 处于公平考虑，不能有人获得0金额，也不能让某个人获得n的一半以上的金额。

在投入研发之前，产品经理决定先计算一下，对n个人的群，一共有多少种可行的红包分配方案。

答案可能很大，要对1e9+7求余。

输入输出格式

输入格式：

  • 第一行t，表示有t组数据
  • 接下来每组数据是一个数字n，表示群的人数

输出格式：

  • t行，每行一个数字，表示对n个人的群计算出的可行红包方案

输入输出样例

输入样例1：

1
2
1
4

输出样例1：

1
4

样例1说明：

7分配给4个人，每个人可分配金额x的范围为0<x≤2，共4种排列可能："1 2 2 2"、"2 1 2 2"、"2 2 1 2"、"2 2 2 1"。

输入样例2:

1
2
3
4
3
1
2
3

输出样例1:

1
2
3
0
0
0

样例2说明：

  • n=1：1<=x<=0，无法分配
  • n=2：1<=x<=1，3额度无法分配给2个人
  • n=3：1<=x<=1，5额度无法分配给3个人

输入样例3:

1
2
3
4
3
6
9
50

输出样例3:

1
2
3
126
8451
129289161

测试点

共20个测试点。

时间限制1s，内存限制128MiB。

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
#include<stdio.h>
#define N 1000010
#define MOD 1000000007
#define INF 1000000000000000000LL

long long fact[N], infact[N];

long long qmi(long long a, long long k, long long p) {
    long long res = 1;
    while (k) {
        if (k & 1) res = (res * a) % p;
        a = (a * a) % p;
        k >>= 1;
    }
    return res;
}

void init() {
    fact[0] = infact[0] = 1;
    for (long long i = 1; i < N; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
        infact[i] = (infact[i - 1] * qmi(i, MOD - 2, MOD)) % MOD;
    }
}

long long C(long long a, long long b) {
    if (b < 0 || b > a) return 0;
    return ((fact[a] * infact[b] % MOD) * infact[a - b] % MOD);
}

long long CC(long long m, long long n) {
    return C(m + n - 1, n - 1);
}

void solve() {
    long long n;
    scanf("%lld", &n);
    if (n <= 3) {
        printf("0\n");
        return;
    }
    long long res = C(n - 1 + n - 1, n - 1);
    long long h = n / 2;
    for (long long i = 1; i <= 3; i++) {
        if (i % 2 == 1) {
            res -= (C(n, i) * CC(n - 1 - i * h, n)) % MOD;
        } else {
            res += (C(n, i) * CC(n - 1 - i * h, n)) % MOD;
            res %= MOD;
        }
        res = (res + MOD) % MOD;
    }
    printf("%lld\n", res);
}

int main() {
    int t;
    scanf("%d", &t);
    init();
    while (t--) solve();
    return 0;
}
算法 > 精英赛题目
CCF精英赛算法题目
https://rain_dew.gitee.io/2024/06/03/算法/比赛或笔试/精英赛题目/
Author
Wang yulu
Posted on
June 3, 2024
Licensed under