算法练习系列——2024牛客五一集训派对day3

2024牛客五一集训派对day3

A：Permutation

原题

题目描述

You are given a prime number p, you want to find a permutation of numbers $1,2,…,p−1$, such that for all $i(1≤i≤p−2), x_i+1≡2x_i(mod\ p)\ or\ x_i+1≡3x_i(modp)$.

输入描述:

1
2
3
The first line contains an integer T(1≤T≤100) indicating the number of test cases.
For each test case, there is one prime number p(2≤p≤106) in the first line.
It's guaranteed that ∑p≤106\sum p\leq 10^6∑p≤106.

输出描述:

1
If there is no solution for this prime, print '-1'. Otherwise print p-1 integers x1,x2,…,xp−1

示例1

输入

复制

1
2
3
2
3
5

输出

复制

1
2
1 2
1 2 4 3

思路

​ 这道题目的大致题意就是：让你构造1~p-1的一种排列(p是素数)，使得a[i+1] == a[i]*2%p 或者 a[i+1] == a[i]*3%p。这样的话其实直接暴力DFS的写法就OK了，但是我们要注意一点，就是每次肯定都是可以从 1 开始的。当然选择其他的应该也是可以的，但是可能有一些数字会需要进行一点特殊处理，所以我们就从最简单的 1 开始枚举就OK了。枚举的流程就是，从 2 ~p - 1，枚举到某个位置的时候我们就看看我们需要使用的 a[i - 1] * 2 % p 或者 a[i - 1] * 3 % p是否之前使用过，如果用过的话我们就可以判断序列无解了。

代码

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 <cstring>
#include <algorithm>

using namespace std;
const int N = 1e6 + 10;
int arr[N];
bool st[N];

void solve() {
    memset(st, false, sizeof st);
    memset(arr, 0, sizeof st);
    int p;
    bool flag = false;
    cin >> p;
    arr[1] = 1;
    st[1] = true;
    for (int i = 2; i < p; i++) {
        int x = arr[i - 1] * 2 % p, y = arr[i - 1] * 3 % p;
        if (!st[x] && x) {
            arr[i] = x;
            st[x] = true;
        } else if (!st[y] && y) {
            arr[i] = y;
            st[y] = true;
        } else {
            flag = true;
            break;
        }
    }
    
    if (flag) cout << "-1\n";
    else {
        for (int i = 1; i <= p - 1; i ++) cout << arr[i] << " \n"[i == p - 1]; 
    }
        
    return;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    cin >> T;
    
    while (T--) {
        solve();
    }
}

E：Game

链接

题目描述

There are n columns of blocks standing in a row. The i-th column has aia_iai blocks in the beginning. Each block has size 1×1×1. Define (x,y) represent the block at column x and is the y-th block from bottom to top. You can perform one operation:
- Push one block to the left, that means you choose one block which has no block at its right and make it move to the left. Because of the friction, the block above it will also move to the left, and because the blocks cannot intersect, the block at its left will move to the left either. This will cause a chain reaction. After every block moved, if some blocks hang in the air, then it will fall because of gravitation. Note that the blocks at column 1 can’t move to the left, so if a movement will cause a block at column 1 move, you can’t perform this operation.

Formally, let bib_ibi be the number of blocks in the i-th column now, then you can choose block (x,y) that satisfy$b_x\geq b_y$ and $b_{x+1}<y$(or $x=n$ ). let l be the greatest position that satisfies $1\leq l<x$ and $b_l<y$, then you can perform this operation as long as l exists. Then for all blocks $(i,j)$ that satisfy $i\leq x$ and $j\geq y$, it moves to (i-1,j). After that, for blocks (x,y) (y>1) that there are no blocks in $(x,y-1)$, it moves to (x,y-1). Repeat doing it until no blocks satisfy the condition.

img

img

img

This shows an operation that pushes the block at (6,4), and the value of l is 3.
The goal of the game is to minimize the height of blocks. You need to operate any times of the operation and minimize $\max\limits_{i=1}^n b_i$​, where $b_i$ represents the number of blocks in the end. Output the minimize value.

输入描述:

image-20240503154725958

输出描述:

image-20240503154716392

示例1

输入

复制

1
2
3
4
5
2
4
2 3 5 6
8
2 1 1 4 4 6 2 3

输出

复制

1
2
4
3

思路

题意：

每次操作可以把右边的一行格子向左移动，由于重力格子下落，可以操作任意次，求最小的最高高度。

思路：

二分寻找最为合适的高度。看代码还是很好懂的。

代码一（前綴和 + 二分）

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll a[100100];
ll b[100100];

bool check(int mid,int n)
{
    for(int i = 0;i < n;i ++) b[i] = a[i];
    ll res = 0;
    for(int i = 0;i < n;i++){
        if(b[i] > mid) res -= b[i] - mid;
        else res += mid 	- b[i];
        if(res < 0) return false;
    }
    return true;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i = 0;i < n;i++) scanf("%lld",&a[i]);
        int l = 0,r = 1e9,ans = 0;
        while(l < r){
            int mid = l + r >> 1;
            if(check(mid,n)){
                ans = mid;
                r = mid;
            }
            else l = mid + 1;
        }
        printf("%d\n",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
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>

using namespace std;
typedef long long ll;
#define P pair<ll, ll>
const ll maxn = 1e5 + 10;
ll a[maxn];
int main() {
    ll T;
    scanf("%lld", &T);
    while (T--) {
        ll n;
        scanf("%lld", &n);
        ll pre = 0;
        ll ans = 0;
        for (ll i = 1; i <= n; ++i) {
            scanf("%lld", a + i);
            pre += a[i];
            if (a[i] < ans) continue;
            // 这样写是为了地方前缀和为奇数的情况，比如说1 4 1 1这个案例
            ll hei = ceil(1.0 * pre / i);
            ans = max(hei, ans);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

I:Tournament

链接

题目描述

You are scheduling a tournament. There are n teams. There are $\frac{n(n-1)}{2}$competitions against every pair of teams. You can schedule a competition each day. For each team, it will arrive in the day when its first competition holds, and leave after its last competition finishes.
For example, there are 3 teams and the schedule is $(1,2), (1,3), (2,3)$. The first team will arrive in day 1, and leave in day $2$. It will stay for two days. The second team will stay for three days. The third team will stay for two days.
You want to find a schedule minimizing the sum of days they stay.

输入描述:

1
2
The first line contains one integer T(1≤T≤30) — the number of test cases.
For each test cases, the first line contains one integer n(2≤n≤300).

输出描述:

1
For each test cases, output n(n-1)/2  lines. Each line contains two integers (u,v)(1≤u,v≤n)(u,v) - the competition you schedule in this day.

示例1

输入

复制

1
2
3
2
3
4

输出

复制

1
2
3
4
5
6
7
8
9
1 2
1 3
2 3
1 2
1 3
1 4
2 3
2 4
3 4

思路

如果每次我们让第一队先走，那么我们会发现标号越大的队伍住的天数越多，这明显是不合理的…

首先我们想到：1队越早走，后面的队伍住的总时间就越长，所以我们要尽量折中每个队伍的住的时间。

这里我们可以大概这么想一下，如果我们先让1走，就是直接先让2,3,4,…,n先和比赛，然后再是剩下的所有队伍互相pk了，按照这样的规则来比赛我们可以得到最大的时间之和。下面我们就要思考如何才可以最小了：我们可以通过枚举得知1队越早走，后面的队伍住的总时间就越长，所以我们要尽量折中每个队伍的住的时间。总之我们的最终目的就是让大家停留时间尽可能平均化。

于是我们就想到如下的构造方法：

  • 首先把n个人分成两半
  • 然后让前一半的人开始打比赛
  • 然后让前一半的人和后一半的人打比赛
  • 然后后一半的人开始打比赛

例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
暴力：         构造：
1 2            1 2
1 3            1 3
1 4            2 3
1 5            1 4
1 6            2 4
2 3            3 4
2 4            1 5
2 5            2 5
2 6            3 5
3 4            4 5
3 5            1 6
3 6            2 6
4 5            3 6
4 6            4 6
5 6            5 6

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        
        // 1、先让前 n / 2个人互相打，然后前 n / 2 和后面 n / 2互相打
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j < i; ++j)
				if (i + j - 1 < n)
					cout << j << " " << i << endl;
		// 2、最后让后 n / 2个人互相打
		for (int i = 1; i <= n; ++i)
			for (int j = i + 1; j <= n; ++j)
				if (i + j - 1 >= n)
					cout << i << " " << j << endl;
    }
}