本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15730268.html

丽泽普及2022交流赛day1总结

提交情况

  • 8:52 T1
  • 9:19 T3
  • 9:26 T4
  • 9:28 T4
  • 10:32 T2
  • 10:49 T1

A. Efim与奇怪的成绩

题目

众所周知，每当我们看见自己糟糕的成绩时，我们总希望以奇怪的方式将其四舍五入。

Efim同样如此。在晴朗的一天，Efim拿到了他的成绩X，他希望通过最多m次四舍五入使他的成绩最大化（每一次四舍五入舍掉的的位置任意，但只能在小数部分，不能在整数部分）。注意：m次可以不用完。

例如1.14四舍五入掉最后一位后为1.1。1.5四舍五入后为2。1.299四舍五入后为1.3。

思路

由于进位次数有限，所以每次进位贡献越大越好。

另一方面，如果某个位进位没有用，那么就不要进位。

所以我们可以从小数点开始往后找，如果遇到可以进位就从这里开始往前进位即可。

总结

这题是一道偏细节的题，思维含量有一点。

有一些细节要注意，例如不能小数点后啥也没。

考场上没有写对，是因为没有考虑进位到整数。以后对于这类进位的题，好要考虑进位的问题。

Code

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
// Problem: A. Efim与奇怪的成绩
// Contest: UOJ - 丽泽普及2022交流赛day1
// URL: http://zhengruioi.com/contest/1062/problem/407
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 200010
//#define M
//#define mo
int n, m, i, j, k; 
char s[N]; 

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); m=read(); 
	scanf("%s", s+1); 
	while(s[++k]!='.'&&k<=n); 
	for(i=k+1; i<=n; ++i)
		if(s[i]>='5')
		{
			while(s[i]>='5'&&m&&i>k)
			{
				s[i]=0; 
				if(i-1==k)
				{
					s[--i]=0; 
					s[--i]++; 
					while(i&&s[i]>'9')
					{
						s[i]='0'; 
						s[--i]++; 
					}
					if(i==0) printf("1"); 
					printf("%s", s+1);
					return 0;
				}
				else s[--i]++; 
				--m; 
			}
			break; 
		}
	printf("%s", s+1); 
	return 0;
}

B. 美丽的IP地址

题目

该问题使用简化的TCP/IP地址模型，请仔细阅读描述。

IP地址是32位整数，表示为一组四位十进制8位整数（没有前导零），用逗号分隔。例如，记录0.255.1.123显示了正确的IP地址，记录为0.256.1.123和0.255.1.01则是不正确的。

我们的英雄Polycarpus仍然在一些大公司担任系统管理员。他喜欢漂亮的IP地址。为了检查某个IP地址是否美观，他应该做如下操作：

  1. 写出一行四位8位的IP地址，没有逗号；
  2. 检查结果字符串是否为回文。

让我们提醒你回文是一个字符串，从右到左，从左到右。

例如，IP地址12.102.20.121和0.3.14.130是漂亮的（如字符串“1210220121”和“0314130”是回文），IP地址1.20.20.1和100.4.4.1不是。 Pulycarpus希望找到所有具有给定数字集合的漂亮IP地址。集合中的每个数字必须至少在IP地址中出现一次。IP地址不能包含任何其他数字。帮助他应付这项艰巨的任务。

思路

爆搜，搜前半部分（因为字符串长度最长也就12），而一半最长是6，然后暴力填。如果前半部分确定，为保证回文，后半部分也会确定。然后在这个字符中插入三个’.'的方案数即可。

总结

考场上拿了50分，考后发现ip地址第一个范围是 [0,255][0,255]，我以为是 [0,127][0,127]，我希望以后的出题人能够认真解释清ip地址的含义，不要搞文字狱。

同时，看来我也要复习一下ip地址了。

Code

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
// Problem: B. 美丽的IP地址
// Contest: UOJ - 丽泽普及2022交流赛day1
// URL: http://zhengruioi.com/contest/1062/problem/408
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 110
//#define M
//#define mo
int n, m, i, j, k; 
int a[N], b[N], c[N], dp[N][7], ans, l; 

int check(int l, int r, int s)
{
	int j, k; 
	if(a[l]==0&&r-l+1!=1) return 0; 
	for(j=l, k=0; j<=r; ++j) k=k*10+a[j]; 
	if(k>s) return 0; 
	return 1; 
}

int suan(int n)
{
	int i, j, k; 
	++m; 
	// for(i=0; i<10; ++i) printf("%lld", c[i]); 
	// printf("\n"); 
	for(i=0; i<10; ++i) if(b[i]&&(!c[i])) return 0; 
	
	for(i=1; i<=n; ++i)
	{
		dp[i][1]=dp[i][2]=dp[i][3]=dp[i][4]=0; 
		if(i<4) dp[i][1]=check(1, i, 255); 
		for(k=max((long long)1, i-2); k<=i; ++k)
			if(check(k, i, 255))
			{
				dp[i][2]+=dp[k-1][1]; 
				dp[i][3]+=dp[k-1][2]; 
				dp[i][4]+=dp[k-1][3]; 
			}
	}
	// if(dp[n][4])
	// {
		// printf("> %lld\n", dp[n][4]); 
		// for(i=1; i<=n; ++i) printf("%lld", a[i]); 
		// printf("\n"); 
	// }
	
	return dp[n][4]; 
}

void dfs(int x)
{
	if(x>l)
	{
		ans+=suan(2*l); 
		for(int i=2*l+1; i>l+1; --i)
			a[i]=a[i-1]; 
		for(int i=0; i<10; ++i)
			if(b[i])
			{
				c[i]++; 
				a[l+1]=i; 
				ans+=suan(2*l+1); 
				c[i]--; 
			}
		for(int i=l+1; i<=2*l; ++i)
			a[i]=a[i+1]; 
	}
	else
	{
		for(int i=0; i<=9; ++i)
			if(b[i])
			{
				c[i]++; 
				a[x]=a[2*l-x+1]=i; 
				dfs(x+1); 
				c[i]--; 
			}
	}
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); 
	for(i=1; i<=n; ++i) b[read()]++; 
	for(l=2; l<=6; ++l)
		dfs(1); 
	// printf("%lld\n", m); 
	printf("%lld", ans); 
	return 0;
}

C. Tic-tac-toe

题目

显然，我们每个人都熟悉Tic-tac-toe游戏。

这个游戏的规则是：两个人依次在3X3的棋盘上下棋。

当一个人有3个棋子连成一行或一列或一纵列时，则这个人已经获得胜利。这时则停止下棋。第一个人先下，第二个人后下。

现在，请你判断一游戏的状态。

first，现在轮到第一个人下。

second，现在轮到第二个人下。

the first player won，如果第一个人刚刚赢得比赛。

the second player won，如果第二个人刚刚赢得比赛。

illegal，如果这种棋局不可能出现。

draw，如果棋盘已经下满且无法分出胜负。

思路

  1. 首先先统计没人的次数，看第一个人与第二个人的棋子差是否有解
  2. 枚举统计每个人是否赢了
  3. 如果两个人都赢了，则无解
  4. 如果第一个人赢了，但第二个人还在下，无解
  5. 如果第二个人赢了，但第一个人还在下，无解
  6. 如果某个人赢了，输出此人赢了
  7. 如果棋盘满了，平局
  8. 如果两人棋子个数相同，第一个人出棋
  9. 如果第一个人比第二个人棋子多，第二个人出棋。

总结

很巧，这题我昨天刚做了一模一样的一道题。（好像是CF3C）

当时有点难调，现在刚好有机会重构代码，确实好看很多。

Code

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
// Problem: C. Tic-tac-toe
// Contest: UOJ - 丽泽普及2022交流赛day1
// URL: http://zhengruioi.com/contest/1062/problem/409
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define N
//#define M
//#define mo
int n, m, i, j, k; 
char s[9][9]; 

void check(char s1, char s2, char s3)
{
	if(s1!=s2) return ; 
	if(s2!=s3) return ; 
	if(s1=='.') return ; 
	(s1=='X' ? i=1 : j=1); 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	scanf("%s%s%s", s[1]+1, s[2]+1, s[3]+1); 
	for(i=1; i<=3; ++i)
		for(j=1; j<=3; ++j)
			if(s[i][j]=='X') ++n; 
			else if(s[i][j]=='0') ++m; 
	if(n-m!=1&&n-m!=0) return printf("illegal"), 0; 
	i=j=0; 
	check(s[1][1], s[1][2], s[1][3]); 
	check(s[2][1], s[2][2], s[2][3]); 
	check(s[3][1], s[3][2], s[3][3]); 
	check(s[1][1], s[2][1], s[3][1]); 
	check(s[1][2], s[2][2], s[3][2]); 
	check(s[1][3], s[2][3], s[3][3]); 
	check(s[1][1], s[2][2], s[3][3]); 
	check(s[1][3], s[2][2], s[3][1]); 
	if(i&j) return printf("illegal"), 0; 
	if(i&&n-m==0) return printf("illegal"), 0; 
	if(j&&n-m==1) return printf("illegal"), 0; 
	if(i) return printf("the first player won"), 0; 
	if(j) return printf("the second player won"), 0;
	if(n+m==9) return printf("draw"), 0;
	if(n==m) return printf("first"), 0; 
	if(n-m==1) return printf("second"), 0; 

	return 0;
}

D. 小 X 与煎饼达人

题目

玩着玩着小 X 觉得有点饿了，他想出门买些吃的。刚刚走出大门，小 X 就看到有位大叔在做煎饼，而且做法十分有趣。只见此人将 n块煎饼排成一排，手持一把大铲，将煎饼铲得上下翻飞，煞是好看。小 X 顿时食指大动，赶紧走上前去细细打量，发现此人做煎饼还十分的讲究。

在做的过程中，大叔每次会将从第 x 块煎饼开始到第 y 块煎饼结束的这 y-x+1 块煎饼全部翻个个儿（正面翻到反面，反面翻到正面）。而他每次会选择不同的区间（区间是指连续的一段煎饼，如 3,4,5,6 四块煎饼用区间[3,6]表示）来翻这些煎饼。

每块煎饼都有正反两面，开始时这些煎饼有的是正面朝上，有的是在反面朝上。此人一共翻了 m 次煎饼，看得小 X 眼花缭乱。但是小 X 很想知道这 n 块煎饼到最后一共有多少块是正面朝上的，于是他只好求助于你了。

思路

差分，统计每块煎饼被翻过多少次，如果奇数次就说明是正面。

总结

这道题几乎没有什么难度，只要分析出利用差分即可。

Code

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
// Problem: D. 小 X 与煎饼达人
// Contest: UOJ - 丽泽普及2022交流赛day1
// URL: http://zhengruioi.com/contest/1062/problem/410
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 1000010
//#define M
//#define mo
int n, m, i, j, k; 
int a[N], ans, x, y; 

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); m=read(); 
	for(i=1; i<=m; ++i)
	{
		x=read(); y=read(); 
		a[x]++; a[y+1]--; 
	}
	for(i=1; i<=n; ++i)
		ans+=((k+=a[i])&1); 
	printf("%d", ans); 
	return 0;
}