题解：AtCoder AT_awc0003_b Line of Handshakes

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：B - Line of Handshakes

【题目描述】

Takahashi is observing an interesting phenomenon at a party venue.
高桥正在派对会场观察一个有趣的现象。

N NNparticipants are standing in a line, all facing the same direction (to the right), and are numbered1 , 2 , … , N 1, 2, \ldots, N1,2,…,Nfrom left to right. Each participant is wearing a glove on their left hand and right hand (from their own perspective). The color of each glove is either navy or white. In the input, navy is represented byN(Navy) and white is represented byS(Snow).
N NN名参与者站成一排，全部面向同一方向（右侧），从左到右编号为1 , 2 , … , N 1, 2, …, N1,2,…,N。每名参与者在其左手和右手上各戴有一只手套（从参与者自身视角）。每只手套的颜色为深蓝色或白色。在输入中，深蓝色用N（Navy）表示，白色用S（Snow）表示。

>Note:The characterNrepresenting the navy color and the integerN NNrepresenting the number of participants are different things. Please be careful not to confuse them.

注意：表示深蓝色的字符N与表示参与者数量的整数N NN是不同的概念。请注意不要混淆。

The color of participanti ii’s left-hand glove is given asL i L_iLi​, and the color of their right-hand glove is given asR i R_iRi​.
参与者i ii的左手手套颜色由L i L_iLi​给出，其右手手套颜色由R i R_iRi​给出。

Since all participants are standing in a line facing the same direction, when two adjacent participants shake hands, the right hand of the left participant (the one with the smaller number) and the left hand of the right participant (the one with the larger number) touch each other. If the colors of the two gloves that touch are the same (both navy or both white), this is called anawkward handshake.
由于所有参与者站成一排且面向同一方向，当两名相邻参与者握手时，左侧参与者（编号较小者）的右手与右侧参与者（编号较大者）的左手会相互接触。如果接触的两只手套颜色相同（均为深蓝色或均为白色），则称为尴尬握手。

Takahashi wants to know the number of adjacent participant pairs that result in an awkward handshake.
高桥想知道会导致尴尬握手的相邻参与者对数。

Specifically, for eachi = 1 , 2 , … , N − 1 i = 1, 2, \ldots, N-1i=1,2,…,N−1, check whether the color of participanti ii’s right-hand gloveR i R_iRi​and the color of participanti + 1 i+1i+1’s left-hand gloveL i + 1 L_{i+1}Li+1​are the same, and find the number of suchi ii.
具体而言，对于每个i = 1 , 2 , … , N − 1 i = 1, 2, …, N-1i=1,2,…,N−1，检查参与者i ii的右手手套颜色R i R_iRi​与参与者i + 1 i+1i+1的左手手套颜色L i + 1 L_{i+1}Li+1​是否相同，并统计满足条件的i ii的数量。

【输入】

N NN
L 1 L_1L1​R 1 R_1R1​
L 2 L_2L2​R 2 R_2R2​
⋮ \vdots⋮
L N L_NLN​R N R_NRN​

• The first line contains an integerN NNrepresenting the number of participants.
• In the followingN NNlines, thei ii-th line( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)contains the characterL i L_iLi​representing the color of participanti ii’s left-hand glove and the characterR i R_iRi​representing the color of participanti ii’s right-hand glove, separated by a space. Each ofL i L_iLi​andR i R_iRi​is eitherN(navy) orS(white).

【输出】

Print the number of adjacent participant pairs that result in an awkward handshake, in a single line.

【输入样例】

4 N S S N N N S S

【输出样例】

2

【解题思路】

【算法标签】

#模拟#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intn,ans;// n: 物品数量，ans: 计数器charl[N],r[N];// l: 左颜色数组，r: 右颜色数组intmain(){cin>>n;// 读入物品数量for(inti=1;i<=n;i++){cin>>l[i]>>r[i];// 读入第i个物品的左颜色和右颜色}// 检查相邻两个物品的连接处颜色是否相同for(inti=1;i<n;i++){if(r[i]==l[i+1])// 如果前一个物品的右颜色等于后一个物品的左颜色{ans++;// 计数器加1}}cout<<ans<<endl;// 输出颜色相同的连接处数量return0;}

【运行结果】

4 N S S N N N S S 2