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

2024牛客五一集训派对day1

按难度排序

H：Stammering Chemists

原题

题目描述

Like many other organic chemists, you are busy in synthesizing, separating, purifying and identifying new chemical compounds all year round. Getting bored with traditional substance isolation and identification methods, such as column chromatography, a bold idea comes to your mind: Computer Assisted Molecule Identification (CAMI). With this technology, millions of chemists can be freed from arduous manual labor. How promising!

Currently, you are developing a simplified version of CAMI that works for hydrocarbons (organic compounds consisting of hydrogen and carbon only). All hardware-side technologies are done, and you are just going to write the program. The sensor reports all carbon atoms as well as the chemical bonds between them. This naturally forms a graph, where carbon atoms are vertices, and the bonds are edges. Each connected component of this graph corresponds to a molecule, and the component itself is called hydrogen-depleted molecular graph (HDMG) of the molecule, since we generally do not care about hydrogen atoms.

The sensor has just detected some hexane molecules, which is a specific kind of hydrocarbons, consisting of 6 carbon atoms and 14 hydrogen atoms per molecule. There are five essentially different hexanes, also known as isomers:

img

Your task is to identify, for each hexane molecule detected, which specific type of hexane isomer it is. A molecule should be identified as any of the above isomers if its hydrogen-depleted molecular graph is isomorphic to the HDMG presented in the above table.

输入描述:

1
2
3
4
5
The first line of input consists of only a single integer T (1≤T≤200000), denoting the number of hexane molecules detected.

Every five lines of the remaining part of the input specify a molecule detected. Each of the five lines contains two integers a, b (1≤a,b≤6,a≠b), denoting a bond between carbon atoms a and b. In each molecule, the carbon atoms are numbered 1 through 6.

It is guaranteed that, for each molecule in the input, it is exactly one type of the hexane isomers listed above.

输出描述:

1
For each molecule in the input, display the name of the isomer in one line.

示例1

输入

复制

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

输出

复制

1
2
n-hexane
3-methylpentane

思路

​ 这道题目乍眼一看：so easy，但是实际写起来会发现还是蛮多小细节需要注意的。

​ 这道题目首先我们可以先记录每个结点的边的条数，通过存在哪些数量的边来判断是哪种类型的化学式。但是由于2-methylpentane 和3-methylpentane二者各节点的边的条数都是一样的，所以这个地方我们需要稍微特殊处理一下，我们可以发现二者的区别就只是两个连有2条边的结点是否连接在一起的区别，这样我们就可以将所有结点连接的边对应的另一个结点放到这个集合里面去，最后就通过判断是否存在相邻的且边数都为2的结点来判断这两种特殊情况。

代码

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
#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int p[10] = {0};
    int d[10] = {0};
    vector<int> ne[10];
    int c = 0;
    bool flag = false;
    for (int i = 1; i <= 5; i++) {
        int a, b;
        cin >> a >> b;
        ne[a].push_back(b);
        ne[b].push_back(a);
        p[a] ++;
        p[b] ++;
    }
    
    for (int i = 1; i <= 6; i++) {
        d[p[i]]++;
    }
    for (int i = 1; i <= 6; i++) {
         if (p[i] != 2) continue;
        for (int k = 0; k < ne[i].size(); k++) {
            if (p[i] == p[ne[i][k]] && p[i] == 2) {
                flag = true;
                break;
            }
        }      
    }
    
    if (d[4]) {
        cout << "2,2-dimethylbutane\n";
        return;
    } else if (d[3] == 2) {
        cout << "2,3-dimethylbutane\n";
        return;
    } else if (d[3] == 1 && d[1] == 3 && flag) {
        cout << "2-methylpentane\n";
        return;
    } else if (d[3] == 1 && d[1] == 3) {
        cout << "3-methylpentane\n";
        return;
    } else {
        cout << "n-hexane\n";
        return;
    }
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

B：Coffee Chicken

链接

题目描述

Dr. JYY has just created the Coffee Chicken strings, denoted as S(n). They are quite similar to the Fibonacci soup — today’s soup is made by mingling yesterday’s soup and the day before yesterday’s soup:
$ S(1)=”COFFEE”S(1) = \texttt{“COFFEE”}S(1)=”COFFEE”;$
$- S(2)=”CHICKEN”S(2) = \texttt{“CHICKEN”}S(2)=”CHICKEN”;$
$- S(n) = S(n-2) :: S(n-1), where :: denotes string concatenation.$
The length of S(n) quickly gets out of control as n increases, and there would be no enough memory in JYY’s game console to store the entire string. He wants you to find 10 contiguous characters in S(n), starting from the kth character.

输入描述:

The first line of input is a single integer$(1 \leq T \leq 1000)$, denoting the number of test cases. Each of the following T lines is a test case, which contains two integers n, k $(1 \leq n \leq 500, 1 \leq k \leq \min{|S(n)|, 10^{12}}$). |S| denotes the length of string S.

输出描述:

1
For each test case, print the answer in one line. If there are no enough characters from the kth character, output all characters until the end of the string.

示例1

输入

复制

1
2
3
2
3 4
2 7

输出

复制

1
2
FEECHICKEN
N

思路

​ 思路一：这道题目的主要思路就是使用递归的思路一直往前寻找一直到 $n = 1$ 或者 $n = 2$ 的位置即可.

image-20240501201728457

代码

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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll t, n, k;
ll f[58] = {0,6,7};
char s1[10] = "COFFEE", s2[10] = "CHICKEN";

void dfs(int n, ll k){
    // 可能存在字符不输出的情况，因此需要进行该特判，比如说COFFEECHICKEN，k = 7,那么就存在输出少于10个字符的情况了。
    if(k > f[n]) return;
    if(n == 1) printf("%c", s1[k-1]);
    else if(n == 2) printf("%c", s2[k-1]);
    else {
        if(k > f[n - 2]) dfs(n - 1,k - f[n - 2]);
        else dfs(n - 2,k);
    }
}


int main()
{
    for(int i = 3;i <= 57;i++) f[i]=f[i - 1] + f[i - 2];
    // 打表查看,慢慢缩小范围一直到57左右位置为止
    //for (int i = 1; i <= 57; i++) printf("%lld ", f[i]);
    scanf("%d", &t);
    while(t--){
        scanf("%d%lld", &n, &k);
        if(n > 57){
            if(n & 1) for(int i = 0; i < 10; i++) dfs(57,k + i);
            else for(int i = 0;i < 10; i++) dfs(56,k + i);
        }
        else
            for(int i=0; i < 10; i++) dfs(n,k + i);
        printf("\n");
    }
    return 0;
}

F：Popping Balloons

链接

题目描述

Recently, an interesting balloon-popping game can be commonly found near the streets. The rule of this game is quite simple: some balloons are tied to cells of a lattice, and you are allowed to throw some darts to prick the balloons. The more balloons you pierce, the more incredible prize you will get.

Probably because too many people have got bored with this childish game, a new variation of the game has appeared. In this variation, you should prick the balloons by shooting an air rifle instead of throwing darts. You can make six shots in total, three horizontally and three vertically. If you shoot horizontally (vertically, resp.), all balloons in the row (column, resp.) are popped. In order to increase the difficulty, there is one restriction imposed on your shots: the distances between any two adjacent horizontal shots and any two adjacent vertical shots must all equal to a given number r. The problem is, what is the maximum number of balloons you can pop by making three horizontal and three vertical shots, under the aforementioned restriction.

输入描述:

1
2
3
The first line of input is two integers n, r (1≤n,r≤105), the number of balloons and the distance between any two adjacent horizontal or vertical shots.

The remaining part of the input is n lines, specifying the positions of the balloons. Each of these lines contains two integers x, y (0≤x,y≤105), denoting a balloon positioned at (x, y). Note that multiple balloons may lie in the same position.

输出描述:

1
Output the answer as a single integer in one line.

示例1

输入

复制

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

输出

复制

1
6

示例2

输入

复制

1
2
3
4
5
6
5 2
0 10
2 3
5 7
9 6
2 3

输出

复制

1
4

思路一

​ 一般并且绝对正确的思路还是很好想的，就是横向三线和竖向三线的气球数量之和最大的行和列的气球数量即为答案，但是时间复杂度是O(n^2^)显然是会TLE的。下面我们就思考一下贪心的思路，首先我们线预处理一下竖向三线所有气球各自的数量，首先直接用sum[i].x枚举三条竖线(i, i+r, i+2*r)能够经过的点数，sum[i].y记录当前枚举是从横坐标为i这条竖线开始的，然后对sum[i]按x从大到小排序，贪心的选取sum[i]后，肯定不能直接枚举三条横线能够经过的点数，因为这样会有重复。
​ 那怎么办呢？我们就先对cntY[a[j].y]进行处理，假如我选取的sum[i]中已经包含a[j]这个点了，那么我的cntY[[a[j].y]就不能加1，因为这个点已经被计算过。现在当然就可以枚举三条横线能够经过的点数，取最大值和sum[i].x相加就是当前总共能经过的最多点数

代码一

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, r, cntX[maxn*3], cntY[maxn*3], res;
struct Point {
    int x, y;
    bool operator<(const Point &rhs)const {
        return x > rhs.x;
    }
} a[maxn], sum[maxn];

int main() 
{
    scanf("%d%d", &n, &r);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        cntX[a[i].x]++;
    }
    for (int i = 0; i < maxn; i++) {
        sum[i].x = cntX[i] + cntX[i + r] + cntX[i + r * 2];
        sum[i].y = i;
    }
    sort(sum, sum + maxn);
    
    // 这个贪心思路感觉很难证明，但是仔细思考一下好像又合乎情理。		
    for (int i = 0; i < 100; i++) {
        memset(cntY, 0, sizeof(cntY));
        for (int j = 0; j < n; j++)
            if (a[j].x != sum[i].y && a[j].x != sum[i].y + r && a[j].x != sum[i].y + r * 2)
                cntY[a[j].y]++;
        int my = 0;
        for (int j = 0; j < maxn; j++)
            my = max(my, cntY[j] + cntY[j + r] + cntY[j + r * 2]);
        res = max(res, my + sum[i].x);
    }
    printf("%d\n", res);
    return 0;
}

思路二

image-20240501211957722

代码二(官方题解，目前看不懂，待理解？？？？？)

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<cstring>
#include<string>
#include<set>
#include<vector>
using namespace std;
const int maxn = 1e5 + 10;
const int M = 1e5;

int cnt[maxn]; // cnt[i] 表示第 i 列的气球数量
vector <int> h[maxn]; // h[i] 存的是以 i 行为中心位置的所有气球的行数
multiset<int> s; // 存放各行的气球数量
void add(int x) {
    // 这个地方存在着一个非常妙的贪心，比如说有2行的气球总数是相同的，但是由于我们是从低行到高行的顺序枚举的，所以这里对应的 p 一定是对应的低行的数据，而且找到了之后我们就会更新，也不会影响之后高行的查找，非常妙的一个思想
    auto p = s.find(cnt[x]); // 非常需要注意这里返回的是迭代器而不是下标
    s.erase(p);
    cnt[x]++;
    s.insert(cnt[x]);
}

// 更新对于第 x 列里的气球与 s 中出现冲突的列的数量，什这样讲可能会比较绕，什么意思呢？比如下面的例子（这里必须很清楚）：
// 0 0 0 0 1
// 1 1 1 0 0
// 1 0 0 0 0
// 1 1 1 0 0
// 0 0 0 0 1
// 我们在枚举行的时候：
// 第1行：和第5列冲突，在排除冲突之后我们直接行的所有气球数量 + 最大竖着的三列的气球数量就可以求出最终的以第1行为中心的
// 第2行：和第1,2,3列冲突,....
// ......
void del(int x) {
    // 这可以实现：如果之前不存在，我们就按照普通情况加上这个数就OK了，反之更新一下再插回去就可以了
    auto p = s.find(cnt[x]);
    s.erase(p);
    cnt[x]--;
    s.insert(cnt[x]);
}
//multiset + 思维
int main()
{
    int n, r, x, y, ans = 0;
    scanf("%d%d", &n, &r);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        h[x].push_back(y);
        if (x - r >= 0) h[x - r].push_back(y);
        if (x + r <= M) h[x + r].push_back(y);
        cnt[y]++;
        if (y - r >= 0) cnt[y - r]++;
        if (y + r <= M) cnt[y + r]++;
    }
    
    for (int i = 0; i <= M; i++) s.insert(cnt[i]);// 往multiset里添加列的气球数
    
    for (int i = 0; i <= M; i++) {
        int res = (int) h[i].size(); // 三行的气球总数
        for (int j = 0; j < res ; j++) { //如果影响了列，就更新
            del(h[i][j]);
            if (h[i][j] - r >= 0) del(h[i][j] - r);
            if (h[i][j] + r <= M) del(h[i][j] + r);
        }
        ans = max(ans, res + (int)(*s.rbegin()));//取最大值
        for (int j = 0; j < res ; j++) {//再更新回去
            add(h[i][j]);
            if (h[i][j] - r >= 0) add(h[i][j] - r);
            if (h[i][j] + r <= M) add(h[i][j] + r);
        }
    }
    printf("%d\n", ans);
    return 0;
}

D：Han Xin and His Troops

链接

题目描述

His majesty chatted with Han Xin about the capabilities of the generals. Each had their shortcomings. His majesty asked, How many troops could I lead?" Han Xin replied, Your highness should not lead more than 100000.” His majesty said, And what about you?" For your humble servant, the more the merrier!” said Han Xin.

—Records of the Grand Historian

Han Xin was a military general who served Liu Bang during the Chu-Han contention and contributed greatly to the founding of the Han dynasty. Your friend, in a strange coincidence, also named Han Xin, is a military general as well.

One day you asked him how many troops he led. He was reluctant to tell you the exact number, but he told you some clues in certain form, for example:

- if we count the troops by threes, we have two left over;
- if we count by fives, we have three left over;
- if we count by sevens, two are left over;
- …
You wonder the number of his troops, or he was simply lying. More specifically, you would like to know the minimum possible number of troops he leads, and if the minimum number is too large, then you suspect he was lying.

输入描述:

1
2
3
The first line of input contains two integers n, m (1≤n≤100,1≤m≤1018), the number of clues he told you and the threshold that you think he was probably lying.

The remaining part of the input are n lines, specifying the clues, Each line consists of two integers a, b (0≤b<a<105), representing a clue that b troops are left over if we count them by a's.

输出描述:

1
If there does not exist a non-negative number of troops satisfying all clues, print he was definitely lying; otherwise, if the minimum non-negative possible number of troops is greater than m, print he was probably lying; otherwise, print the minimum non-negative number.

示例1

输入

复制

1
2
3
4
3 100
3 2
5 3
7 2

输出

复制

1
23

示例2

输入

复制

1
2
3
4
5
4 10000
12 7
15 2
30 5
8 6

输出

复制

1
he was definitely lying

示例3

输入

复制

1
2
3
2 10
11 3
19 7

输出

复制

1
he was probably lying

思路

​ 中国剩余定理板子，但是需要快读 + __int128

代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<map>
#include<set>
#include<stack>
#define debug cout<<"*"<<endl;
#define input(x) scanf("%d",&x)
#define output(x) printf("%d\n",x);
#define llinput(x) scanf("%lld",&x)
#define lloutput(x) printf("%lld\n",x);
using namespace std;
typedef __int128 ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<string,int> psi;
typedef pair<char,char> pcc;
const int mod=998244353;
const int INF=1e9+7;
const int maxn=1e5+7;
const double PI=acos(-1);
const int N=3007;
void Init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void print(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll gcd = exgcd(b, a%b, x, y);
    ll t = x;
    x = y;
    y = t - a/b*y;
    return gcd;
}
ll China(ll B[], ll W[], ll k, ll m) //W为除数，B是余数
{
    ll i, a, b, c, d, x, y, t;
    for(i=1; i<k; ++i)
    {
        a = W[i-1], b = W[i];
        c = B[i] - B[i-1];
        d = exgcd(a, b, x, y);
        if(c%d)
            return -1;
        t = b/d;
        x = (x*(c/d)%t+t)%t;
        B[i] = B[i-1] + W[i-1]*x;
        W[i] = W[i]/d*W[i-1];
    }
    return B[k-1];
}
 
ll m[100101], a[100101];
int main() {
    ll k;
    ll limit;
    k=read();limit=read();
        for (int i = 0; i < k; i++) {
            scanf("%lld%lld",&m[i],&a[i]);
        }
        ll tmp=China(a,m,k,limit);
        if(tmp==-1)
        {
            printf("he was definitely lying\n");
        }
        else if(tmp>limit)
            printf("he was probably lying\n");
        else
            print(tmp);
 
    return 0;
}