AtCoder Beginner Contest 295——A-D讲解

蒟蒻来讲题，还望大家喜。若哪有问题，大家尽可提！

Hello, 大家好哇！本初中生蒟蒻讲解一下AtCoder Beginner Contest 295这场比赛的A-D题！

===========================================================================================

A - Probably English

Problem Statement

You are given N N N strings W 1 , W 2 , … , W N W_1,W_2,\dots,W_N W1​,W2​,…,WN​ consisting of lowercase English letters.

If one or more of these strings equal and, not, that, the, or you, then print Yes; otherwise, print No.

Constraints

N N N is an integer between 1 1 1 and 100 100 100, inclusive.
1 ≤ ∣ W i ∣ ≤ 50 1 \le |W_i| \le 50 1≤∣Wi​∣≤50 ( ∣ W i ∣ |W_i| ∣Wi​∣ is the length of W i W_i Wi​.)
W i W_i Wi​ consists of lowercase English letters.

Input

The input is given from Standard Input in the following format:
N N N
W 1 W_1 W1​ W 2 W_2 W2​ … \dots … W N W_N WN​

Output

Print the answer.

Sample Input 1

10
in that case you should print yes and not no

Sample Output 1

Yes
We have, for instance, W 4 = W_4= W4​= you, so you should print Yes.

Sample Input 2

10
in diesem fall sollten sie no und nicht yes ausgeben

Sample Output 2

No
None of the strings W i W_i Wi​ equals any of and, not, that, the, and you.

思路

呜呜呜，太简单

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define endl '\n'
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)

using namespace std;

typedef pair<int, int> PII;

string cmp[6] = {"and", "not", "that", "the", "you"};

inline int read()
{
    int w = 1, s = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
    
    return w * s;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    int n;
    string c;
    
    cin >> n;
    
    while (n --)
    {
    	cin >> c;
    	for (int i = 0; i < 5; i ++)
    		if (c == cmp[i])
    		{
    			cout << "Yes" << endl;
    			return 0;
    		}
    }
    
    cout << "No" << endl;
    
    return 0;
}

B - Bombs

原题

Problem Statement

We have a board with R R R rows running horizontally and C C C columns running vertically. Let ( i , j ) (i,j) (i,j) denote the square at the i i i-th row from the top and j j j-th column from the left.
You are given characters B i , j B_{i,j} Bi,j​ representing the current states of ( i , j ) (i,j) (i,j).
. represents an empty square; # represents a square with a wall; 1, 2, … \dots …, 9 represent a square with a bomb of power 1 , 2 , … , 9 1,2,\dots,9 1,2,…,9, respectively.
At the next moment, all bombs will explode simultaneously.
When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square.
Here, the Manhattan distance from ( r 1 , c 1 ) (r_1,c_1) (r1​,c1​) to ( r 2 , c 2 ) (r_2,c_2) (r2​,c2​) is ∣ r 1 − r 2 ∣ + ∣ c 1 − c 2 ∣ |r_1-r_2|+|c_1-c_2| ∣r1​−r2​∣+∣c1​−c2​∣.
Print the board after the explosions.

Constraints

1 ≤ R , C ≤ 20 1\leq R,C \leq 20 1≤R,C≤20
R R R and C C C are integers.
Each B i , j B_{i,j} Bi,j​ is one of ., #, 1, 2, … \dots …, 9.

Input

The input is given from Standard Input in the following format:
R R R C C C
B 1 , 1 B 1 , 2 … B 1 , C B_{1,1}B_{1,2}\dots B_{1,C} B1,1​B1,2​…B1,C​
⋮ \vdots ⋮
B R , 1 B R , 2 … B R , C B_{R,1}B_{R,2}\dots B_{R,C} BR,1​BR,2​…BR,C​

Output

Print R R R lines representing the board after the explosions. Use the format used in the input (do not print R R R or C C C).

Sample Input 1

4 4
.1.#
###.
.#2.
#.##

Sample Output 1

…#
#…
…
#…
Figure representing the explosion ranges of bombs
The explosion of the bomb at ( 1 , 2 ) (1,2) (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
The explosion of the bomb at ( 3 , 3 ) (3,3) (3,3) will turn the red squares and purple squares in the above figure into empty squares.
As seen in this sample, the explosion ranges of bombs may overlap.

Sample Input 2

2 5
…#.#
###.#

Sample Output 2

…#.#
###.#
There may be no bombs.

Sample Input 3

2 3
11#

Sample Output 3

…
…#

Sample Input 4

4 6
#.#3#.
###.#.
##.###
#1…#.

Sample Output 4

…
#…
#…#
…#.

思路

我们直接四重循环，先循环每个炸弹，再循环能炸到的点。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define endl '\n'
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)

using namespace std;

typedef pair<int, int> PII;

const int N = 2e1 + 10;

int n, m;
char a[N][N];

inline int read()
{
    int w = 1, s = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
    
    return w * s;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++)
    	for (int j = 1; j <= m; j ++)
    		cin >> a[i][j];
    		
    for (int x1 = 1; x1 <= n; x1 ++)
    	for (int y1 = 1; y1 <= m; y1 ++)
    	{
    		if (!isdigit(a[x1][y1])) continue;
    		int t = a[x1][y1] - '0';
    		for (int x2 = 1; x2 <= n; x2 ++)
    			for (int y2 = 1; y2 <= m; y2 ++)
    				if ((!isdigit(a[x2][y2]) || (x1 == x2 && y1 == y2)) && abs(x1 - x2) + abs(y1 - y2) <= t)
    					a[x2][y2] = '.';//, printf("(%d, %d)->(%d, %d)\n", x1, y1, x2, y2);
    	}
    	
    for (int i = 1; i <= n; i ++)
    {
    	for (int j = 1; j <= m; j ++)
    		cout << a[i][j];
    	cout << endl;
    }
    return 0;
}

C - Socks

原题

Problem Statement

You have N N N socks. The color of the i i i-th sock is A i A_i Ai​.
You want to perform the following operation as many times as possible. How many times can it be performed at most?
Choose two same-colored socks that are not paired yet, and pair them.

Constraints

1 ≤ N ≤ 5 × 1 0 5 1\leq N \leq 5\times 10^5 1≤N≤5×105
1 ≤ A i ≤ 1 0 9 1\leq A_i \leq 10^9 1≤Ai​≤109
All values in the input are integers.

Input

The input is given from Standard Input in the following format:
N N N
A 1 A_1 A1​ A 2 A_2 A2​ … \dots … A N A_N AN​

Output

Print an integer representing the answer.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2
You can do the operation twice as follows.
Choose two socks with the color 1 1 1 and pair them.
Choose two socks with the color 4 4 4 and pair them.
Then, you will be left with one sock with the color 4 4 4 and another with the color 7 7 7, so you can no longer do the operation.
There is no way to do the operation three or more times, so you should print 2 2 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

思路

直接看看有多少个重复的颜色就行~~~

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)

using namespace std;

typedef pair<int, int> PII;

const int N = 5e5 + 10;

int n;
int a[N];
unordered_map<int, int> cnt;

inline int read()
{
    int w = 1, s = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
    
    return w * s;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> n;
    
    for (int i = 1; i <= n; i ++)
    	cin >> a[i], cnt[a[i]] ++;
    	
    int res = 0;
    for (auto c : cnt)
    	res += (c.second / 2);
    	
    cout << res << endl;
    
    return 0;
}

D - Three Days Ago

原题

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.

Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.

You are given a string S S S consisting of digits. Find the number of pairs of integers ( l , r ) (l,r) (l,r) satisfying all of the following conditions.
1 ≤ l ≤ r ≤ ∣ S ∣ 1 \le l \le r \le |S| 1≤l≤r≤∣S∣. ( ∣ S ∣ |S| ∣S∣ is the length of S S S.)
The (contiguous) substring formed of the l l l-th through r r r-th characters of S S S is happy.

Constraints

S S S is a string consisting of digits whose length is between 1 1 1 and 5 × 1 0 5 5 \times 10^5 5×105, inclusive.

Input

The input is given from Standard Input in the following format:
S S S

Output

Print an integer representing the answer.

Sample Input 1

20230322

Sample Output 1

4
We have S = S= S= 20230322.
Here are the four pairs of integers ( l , r ) (l,r) (l,r) that satisfy the condition: ( 1 , 6 ) (1,6) (1,6), ( 1 , 8 ) (1,8) (1,8), ( 2 , 7 ) (2,7) (2,7), and ( 7 , 8 ) (7,8) (7,8).

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

185
S S S may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

9

思路

本题主要意思是有多少个区间满足区间内的值随便排列能够组成两个相同的序列。例如：202303，就可以排列成230230，这就是一个满足条件的序列！通过观察，要想凑出两个相同的小序列，必须序列中的每一个数出现的次数都是偶数，这样才能平均的分配到两个小序列中。
知道这一点之后，明确一下本题的目标：找到有多少个区间其中的数出现的次数都是偶数，这里我们可以用到异或（这一篇写的很好，值得一看）。因为，每一个数只能取1-9，所以我们用一个01序列来表示他们的奇偶（0表示偶数，1表示奇数）。

例如：S=20230322

R[i]表示前i个数中每个数出现的次数的奇偶
i = 0  0000000000
i = 1  0010000000
i = 2  1010000000
i = 3  1000000000
i = 4  1001000000
i = 5  0001000000
i = 6  0000000000
i = 7  0010000000
i = 8  0000000000

若 R i = R j ( i < j ) R_i = R_j(i < j) Ri​=Rj​(i<j)，则从 i + 1 i+1 i+1到 j j j一定是一个满足条件的序列。

证明：从 i + 1 i + 1 i+1到 j j j的奇偶性序列通过前缀和的思想，其实就是 R j − R i ( R j ≥ R i ) R_j - R_i(R_j \geq R_i) Rj​−Ri​(Rj​≥Ri​)（注意不是i+1, 因为要取i+1），若 R j − R i R_j - R_i Rj​−Ri​中所有的数全部是偶数，那么序列中的体现就是0000000000，也就是 R j − R i = 0 R_j - R_i = 0 Rj​−Ri​=0，即： R i = R j R_i = R_j Ri​=Rj​，则从 i + 1 i+1 i+1到 j j j一定是一个满足条件的序列。

所以找到所有的 R i = R j R_i = R_j Ri​=Rj​的个数，即为答案！

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define psb(i) push_back(i)
#define ppb() pop_back()
#define psf(i) push_front(i)
#define ppf() pop_front()
#define ps(i) push(i)

using namespace std;

typedef pair<int, int> PII;

string s;
unordered_map<int, int> times;
int state;
int res = 0;

inline int read()
{
    int w = 1, s = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
    
    return w * s;
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> s;
    
    times[0] = 1; //全是0就是一种可行的方案！
    for (int i = 0; i < (int)s.size(); i ++)
    {
    	state ^= (1 << (s[i] - '0')); //我们可以通过二进制来存储奇偶性序列
    	res += times[state]; //每一次加上之前的所有可以的，因为对于每一个小于j的i，都要记录
    	times[state] ++; //出现了一次，不断累加
    }
    
    cout << res << endl;
    
    return 0;
}

今天就到这里了！

大家有什么问题尽管提，我都会尽力回答的！

吾欲您伸手，点的小赞赞。吾欲您喜欢，点得小关注！

（这两天比赛有点多，直到现在才发出来，非常抱歉~~~）

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/3488.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

开关电源Y电容放置的位置

开关电源Y电容放置的位置

Y电容&#xff0c;是我们工程师做开关电源设计时都要接触到的一个非常关键的元器件&#xff0c;它对EMI的贡献是相当的大的&#xff0c;但是它是一个较难把控的元器件&#xff0c;原理上并没有那么直观易懂&#xff0c;在EMI传播路径中需要联系到很多的寄生参数才能够去分析。 …
阅读更多...
Python和Excel的完美结合:常用操作汇总(案例详析)

Python和Excel的完美结合:常用操作汇总(案例详析)

在以前&#xff0c;商业分析对应的英文单词是Business Analysis&#xff0c;大家用的分析工具是Excel&#xff0c;后来数据量大了&#xff0c;Excel应付不过来了&#xff08;Excel最大支持行数为1048576行&#xff09;&#xff0c;人们开始转向python和R这样的分析工具了&#…
阅读更多...
JNI原理及常用方法概述

JNI原理及常用方法概述

1.1 JNI(Java Native Interface) 提供一种Java字节码调用C/C的解决方案&#xff0c;JNI描述的是一种技术。 1.2 NDK(Native Development Kit) Android NDK 是一组允许您将 C 或 C&#xff08;“原生代码”&#xff09;嵌入到 Android 应用中的工具&#xff0c;NDK描述的是工具集…
阅读更多...
python迭代器详解

python迭代器详解

不懂的问题&#xff1a;什么是协变、逆变&#xff1f;渐进式&#xff1f; _T_co TypeVar("_T_co", covariantTrue) # Any type covariant containers.作者&#xff1a;20岁爱吃必胜客&#xff08;坤制作人&#xff09;&#xff0c;近十年开发经验, 跨域学习者&…
阅读更多...
【Docker】Network网络

【Docker】Network网络

文章目录网络情况查看宿主机网络情况 ifconfig查看docker网络模式命令 docker network ls常用基本命令查看网络 docker network ls查看网络源数据 docker network inspect XXX网络名字创建网络 docker network create test_network删除网络 docker network rm XXX网络名字netwo…
阅读更多...
Kotlin~Adapter适配器模式

Kotlin~Adapter适配器模式

概念 Adapter&#xff08;Wrapper&#xff09; Pattern&#xff0c;连接两个不兼容的接口&#xff0c;让接口不兼容的对象能够相互合作。 适配器中的角色 请求者Client&#xff1a;调用者目标Target&#xff1a;定义了Client要使用的功能转化对象Adaptee&#xff1a; 需要适…
阅读更多...
ROC-RK3588S-PC (Android 12) 看门狗的使用

ROC-RK3588S-PC (Android 12) 看门狗的使用

&#x1f347; 博主主页&#xff1a; 【Systemcall小酒屋】&#x1f347; 博主追寻&#xff1a;热衷于用简单的案例讲述复杂的技术&#xff0c;“假传万卷书&#xff0c;真传一案例”&#xff0c;这是林群院士说过的一句话&#xff0c;另外“成就是最好的老师”&#xff0c;技术…
阅读更多...
走进二叉树的世界 ———性质讲解

走进二叉树的世界 ———性质讲解

二叉树的性质和证明前言1.二叉树的概念和结构特殊的二叉树&#xff1a;二叉树的性质前言 本篇博客主要讲述的是有关二叉树的一些概念&#xff0c;性质以及部分性质的相关证明&#xff0c;如果大伙发现了啥错误&#xff0c;可以在评论区指出&#x1f618;&#x1f618; 1.二叉树…
阅读更多...
Verilog之小规模经典电路设计

Verilog之小规模经典电路设计

verilog语句执行顺序 每个语句块&#xff0c;是事件(event)触发执行的主要分为 连续赋值语句assign过程赋值语句always, initial(只执行一次) 连续和过程之间是并行执行的&#xff0c;只要满足出发条件即可assign是在后面的输入发生变化时进行执行always是在敏感列表发生变化时…
阅读更多...
C语言数据结构初阶(8)----栈与队列OJ题

C语言数据结构初阶(8)----栈与队列OJ题

CSDN的uu们&#xff0c;大家好。这里是C语言数据结构的第八讲。 目标&#xff1a;前路坎坷&#xff0c;披荆斩棘&#xff0c;扶摇直上。 博客主页&#xff1a; 姬如祎 收录专栏&#xff1a;数据结构与算法栈与队列的知识点我➡➡队列相关点我➡➡栈相关2. 用栈实现队列原题链接…
阅读更多...
C语言基础 — ( C语言的链表实例)

C语言基础 — ( C语言的链表实例)

欢迎小伙伴的点评✨✨ 本篇章系列是对C语言的深度思考和总结、关于C语言内容会持续更新 文章目录前言一、什么是链表二、建立简单静态链表二、建立简单动态链表三、链表的增加、删除、更改、查询四、总结前言 本章会给大家带来基于C语言链表的实例。 一、什么是链表 链表是一…
阅读更多...
Python解题 - CSDN周赛第40期

Python解题 - CSDN周赛第40期

上期问哥没参加&#xff0c;但从赛后大家的反馈来看&#xff0c;又出现了数据上的bug&#xff0c;使用 python 的朋友会遇到第二个用例的柱子高度数组长度不够&#xff0c;200根柱子&#xff0c;只有179个数据&#xff0c;这让人怎么玩&#xff1f;但是用C的选手就没有这个问题…
阅读更多...
面试官：vue2和vue3的区别有哪些

面试官：vue2和vue3的区别有哪些

目录 多根节点&#xff0c;fragment&#xff08;碎片&#xff09; Composition API reactive 函数是用来创建响应式对象 Ref toRef toRefs 去除了管道 v-model的prop 和 event 默认名称会更改 vue2写法 Vue 3写法 vue3组件需要使用v-model时的写法 其他语法 1. 创…
阅读更多...
提升网站性能：Nginx五种高效负载均衡策略

提升网站性能：Nginx五种高效负载均衡策略

前言 本文收录于我是沐风晓月的csdn专栏《linux基本功-系统服务实战》&#xff0c; 关于nginx的系列后面会汇总起来&#xff0c;关注我&#xff0c;一起学习与成长。 本专栏写作的过程中&#xff0c;联合了csdn几位大佬&#xff0c;目前正在整理更新目录&#xff0c;力争让大…
阅读更多...
多线程代码案例-阻塞队列

多线程代码案例-阻塞队列

hi,大家好,今天为大家带来多线程案例--阻塞队列 这块知识点也很重要,要好好掌握呀~~~ &#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x1f338;&#x…
阅读更多...
【蓝桥杯_练习】

【蓝桥杯_练习】

蓝桥杯1.创建工程2.LED灯点亮led.c3.LCD液晶屏显示lcd.c4.定时器按键单机interrupt.hinterrupt.cman.c5.定时器&#xff08;长按键&#xff09;interrupt.hinterrupt.cmain.c6.PWMmain.c7.定时器-输入捕获&#xff08;频率&#xff0c;占空比测量&#xff09;interrupt.cmain.c…
阅读更多...
中科亿海微FPGA应用(一、点灯)

中科亿海微FPGA应用(一、点灯)

1.软件&#xff1a; https://download.csdn.net/download/weixin_41784968/87564071 需要申请license才能使用&#xff1a;软件试用申请_软件试用申请_中科亿海微电子科技&#xff08;苏州&#xff09;有限公司 2.开发板&#xff1a; 芯片EQ6HL45&#xff0c;42.5k LUT。 3…
阅读更多...
移植RK3568的串口

移植RK3568的串口

文章目录 前言一、代码位置二、硬件原理图三、修改设备树四、关闭串口调试功能总结前言 本文主要讲解如何移植RK3568的串口 提示：以下是本篇文章正文内容，下面案例可供参考 一、代码位置 drivers/tty/serial/8250/8250_core.c drivers/tty/serial/8250/8250_dma.c dma实现…
阅读更多...
TCP协议详解

TCP协议详解

1.TCP的准备条件在古代的时候&#xff0c;古人们经常写书信进行交流&#xff0c;写书信的前提是你要知道这份信是要寄给谁在网络中&#xff0c;我们通过ip端口号找对目标对象&#xff0c;但是现在网站一般会对ip端口注册一个域名&#xff0c;所以我们一般就是对域名进行查找&am…
阅读更多...
mysql的limit查询竟然有坑？

mysql的limit查询竟然有坑？

背景 最近项目联调的时候发现了分页查询的一个bug&#xff0c;分页查询总有数据查不出来或者重复查出。 数据库一共14条记录。 如果按照一页10条。那么第一页和第二页的查询SQL和和结果如下。 .png) 那么问题来了&#xff0c;查询第一页和第二页的时候都出现了11,12,13的记录…
阅读更多...
最新文章

Copyright @ 2022~2023