ACM-ICPC 2023新疆省赛个人题解

B题 print yes

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Christina wants to write a program to automatically classify and recognize these letters, but unfortunately she doesn’t know how to code. Can you help her out?

Y, E, and S are all composed of images of 7*9 pixels under normal circumstances. However, the actual images may be rotated clockwise by 90°, 180°, or 270°. They may also be stretched horizontally (enlarged) or vertically (enlarged), or stretched horizontally and vertically at the same time, but the number of pixels in the final enlarged image will not exceed one million. The following images are the normal images of Y, E, and S, as well as three rotated images of Y and three stretched images of E.

输入描述

1
2
Enter a 2D 01 matrix, input one string per row, and continue to input until the end of the file. 1 represents the gray pixels in the above figure, and 0 represents the green pixels in the above figure. What you need to determine is what letter the 1s in the input matrix form. The input ensures that the number of character matrix pixels is less than 10^6
  (i.e., the total number of characters input), and the input ensures that the character matrix is valid and solvable.

输出描述

1
Output one of the letters Y, E, or S to represent the result.

示例1

输入

1
2
3
4
5
6
7
000000000000000000000000000
000111111000000000000000000
000000000111000000000000000
000000000000111111111111000
000000000111000000000000000
000111111000000000000000000
000000000000000000000000000

输出

1
Y

题解

题目解析

一道模拟?或者是思维题?解体的关键在于找到他们之间的不同点,然后根据他们之间的不同点来突破这一道题.

  • 首先说一下处理E这一个字母,E这个字母对我来说是最好处理的.我对他的处理方式为:

    对于E这个字母来说,我们仅需找到这个字符的左右边界并记录下来.然后判断这个字符是否有完整联通左右边界的连通块.利用这样判断,无论是什么方向的E都可以顺利判断,这里我用一张图表示.

  • 接下来判断Y这个字符.很巧,这个Y正好是关于中间轴线对称的.于是可以利用这个性质来处理这道题.

    由于我们使用的Y的判断方法会因为旋转而出现不同的结果,于是我们可以分类讨论,把Y讨论出来.这里的判断条件是:因为Y是轴对称图形,所以在左右两侧的方块必是相同的.我这里还是利用一张图来表示.

  • 那么Y和E确定之后,剩下的便是S了.

AC代码

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

string s[100010];//把这个01矩阵存下

int main(){
    int k,flag,left,right,up,down;//flag [1:E,2:Y,3:S]
    k = flag = 0,left = up = 0x3f3f3f3f,right = down = -0x3f3f3f3f;
    while(cin >> s[k]){k++;}k--;//记录一下一共有几行
    //提取出来left等数据
    for(int i=0;i<=k;i++){
        for(int j=0;j<s[i].size();j++){
            if(s[i][j] == '1'){
                left = min(left,j),up = min(up,i);
            }
            if(s[i][j] == '1'){
                down = max(down,i),right = max(right,j);
            }
        }
    }
    //判断是否有有完整联通左右边界的连通块,E.
    for(int i=0;i<=k;i++){
        int ans = 0;
        for(int f = left;f<=right;f++) ans += s[i][f] - '0';
        if(ans == right - left + 1 ) flag = 1; // 如果有满足有完整联通左右边界的连通块，则赋值其为E
    }
    //判断Y
    if(flag == 0){
        for(int i=0;i<=k;i++){
            int ans = 0;
            ans += s[i][left] + s[i][right] - 2 * '0';//左右边界两块加起来只能出现0/2的情况
            if (ans == 1) flag = -1;//如果存在不对称的地方，因为存在歪过来的Y,所以我们暂定.
        }
        if(flag == 0){//如果是对称的,则直接确定为Y
            flag = 2;
        }else{
            for(int i=0;i<s[1].size();i++){
                int ans = 0;
                ans += s[up][i] + s[down][i] - 2 * '0';
                if(ans == 1) flag = 3;//如果还存在不对称的地方,则肯定是S了.
            }
            if(flag != 3) flag = 2;//否则这里是Y
        }
    }
    if(flag == 1) cout << "E";
    if(flag == 2) cout << "Y";
    if(flag == 3) cout << "S";
    return 0;
}

E题 Couplet

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

It’s New Year’s Day, and it was a tradition for ancient Chinese to write couplets. Sometimes one person would give the first line, and another person would need to come up with the second line based on the sentence structure and meaning, which requires considerable literary skills.

Now given a first line of length $n$, with each character represented by a number for convenience, you need to write a second line that meets the following requirements:

  1. Each number in the second line must be a positive integer.
  2. Each number in the second line must not appear in the first line.
  3. The $i$-th number in the first line corresponds to the $i$-th number in the second line. You can specify the correspondence relationship arbitrarily, but the relationship must be consistent and unique.

For example, if you specify that the number 3 in the first line corresponds to the number 1 in the second line, then another non-3 number in the first line cannot correspond to the number 1, and all 3s in the first line must correspond to 1.

输入描述

The first line contains a positive integer $n$ ($1 \le n \le 10^5$), indicating the number of numbers. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$), representing each number.

输出描述

Output $n$ integers representing the second line.

Since you can specify the correspondence relationship arbitrarily, there may be multiple possible solutions for the second line. You need to output the smallest one in lexicographic order.

示例1

输入

1
2
6
3 3 4 2 4 7

输出

1
1 1 5 6 5 8

说明

1
Let 3 correspond to 1, 4 correspond to 5, 2 correspond to 6, and 7 correspond to 8, then the second line is [1, 1, 5, 6, 5, 8]. This is the smallest in lexicographic order. If we let 3 correspond to 9, the second line would be [9, 9, 5, 6, 5, 8], which is also a valid second line, but not the smallest one required by the problem.

题解

题目解析

一个简单的构造题,它有三个条件:

  • 必须是正数
  • 第一行用过的第二行不能出现
  • 一旦绑定第一行其中的数,这个数就永远绑定了.

这道题应该是一道简单的贪心,第一个出现的永远是最小的.于是可以从$1$遍历到$2\times10^5$就好.遇到第一次绑定的就扔到map里,这就最后解决了这个问题.

AC代码

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
#include <iostream>
#include <map>
using namespace std;
const int MAXN = 2e5+10;

map<int,int> mp;

int a[MAXN],b[MAXN];//a存储用没用过这个数字(存小于2e5的),b存第一列的数字

int main(){
	int n,temp=1;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> b[i];
		if(b[i]<MAXN) a[b[i]] = 1;//如果出现过这个数字,则对应位置更新数值
	}
	for(int i=1;i<=n;i++){
		while(a[temp]){temp++;}//如果这个数字用过就再往后++
		if(mp.find(b[i]) != mp.end()){
			cout << mp.find(b[i])->second << " ";
		}else{
			mp[b[i]] = temp;//将此数字与temp绑定
			a[temp] = 1;
            cout << mp[b[i]] << " ";
		}
	}
	return 0;
}

H题 Triangle

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Now there is a right triangle composed of * with a side length of $n$. The length of the first row of the triangle is $n$, the length of the second row is $n-1$, the length of the third row is $n-2$, and the length of the $n$th row is 1. For example, a right triangle with a side length of 4 is as follows:

1
2
3
4
****
***
**
*

However, Haitao replaced these * with ordered uppercase letters, A, B, C … X, Y, Z. That is, the triangle above becomes: 

1
2
3
4
ABCD
EFG
HI
J

When the number of * is greater than 26, the letters used to form the right triangle are not enough, and we start from A again. For example, a right triangle of length 7 is: 

1
2
3
4
5
6
7
ABCDEFG
HIJKLM
NOPQR
STUV
WXY
ZA
B

Now, given the side length $n$ of the right triangle, what is the letter of the $b$-th character in the $a$-th row?

输入描述

Given three positive integers $n$, $a$, and $b$ $(1 \leq n \leq 10^9)$. It is guaranteed that the right triangle has at least $a$ rows, and the $a$-th row has at least $b$ letters.

输出描述

Output one letter as the answer.

示例1

输入

1
4 2 3

输出

1
G

示例2

输入

1
7 7 1

输出

1
B

题解

题目解析

这绝对是签到题,但是有大坑大坑!!!就这个题,我WA了两次.double计算的时候会有误差,结果最后答案错误了= =.n如果赋值成int的话参与计算的时候会炸int.

这道题仅需用等差数列算出其中的前 $x$ 层的个数加上 $y$ 就是从第一个到 $(x,y)$ 的字母个数.因为是字母个数,如果是 $1$ ,那么就是 $A$ ,所以最后需要 $y-1$ .最后 $\text{mod}26+\text{‘A’}$ 就可以了.

个数通项公式为:

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
typedef long long ll;

int main(){
	ll n,x,y;
	ll ans = 0;
	cin >> n >> x >> y;
	if(x == 1){//第一层不需要通项公式
		ans = y-1;
	}else{
		ans = (-x*x+(3+2*n)*x-(2*n+2))/2 + y-1;
	}
	cout << char(ans%26+'A') << endl; 
	return 0;
}

J题 Components in Tree

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Given a tree with $n$ nodes numbered from $1$ to $n$.

Alice wants to know the number of connected components with a size of three in the tree.

输入描述

The first line contain a single integer $n (1\leq n\leq 10^5)$, denoting the number of nodes in the tree.

In the next $n-1$ lines, each line contain two integers uuu and $v (1\leq u,v\leq n)$, indicating that there is an edge between node $u$ and node $v$.

输出描述

Output an integer in a single line, indicating the number of connected components with a size of three in the tree.

示例1

输入

1
2
3
3
1 2
2 3

输出

1
1

示例2

输入

1
2
3
4
5
5
1 2
1 3
1 4
2 5

输出

1
4

题解

题目解析

一道伪装成图论的签到题,给出的数据组成了一个非连通图,问能组成的三个联通块的个数.和同学在考场上随便画了几笔,找到了规律:记录所有数字出现的次数算其边数,如果一个节点上的边超过1个,就可以跟任意两个相连的边形成三连通块.其公式可以写作:

AC代码

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
#include <iostream>
using namespace std;
typedef long long ll;

const int MAXN = 1e5+10;
int p[MAXN];

ll Cn(ll n){//这里的n也要用long long,考试的时候数据没这么可怕= =,后来加hack数据了我没加long long被hack了.
	if(n == 0) return 0;
	ll up,down=2;
	up = n*(n-1);
	return up/down;
}

int main(){
	ll ans = 0;
	int n,x,y;
	cin >> n;
	for(int i=1;i<=n-1;i++){
		cin >> x >> y;
		p[x]++,p[y]++;
	}
	for(int i=1;i<=n;i++) ans += Cn(p[i]);
	cout << ans;
	return 0;
}