目录
A - Wanna go back home
注意到横纵坐标是独立的，因此可以分开考虑。
考虑横坐标或纵坐标最终为零的充要条件为：
- 没有出现任何关于它的任何操作（没有
N和S，或没有W和E）； - 出现所有关于它的任何操作（有向正方向走与往负方向走，如有
N和S，或有W和E）。
统计每种字母是否出现即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
int main() {
string s;
cin >> s;
bool a, b, c, d;
a = b = c = d = false;
int i;
for(i = 0; i < s.size(); i++) {
if(s[i] == 'N') {
a = true;
}
if(s[i] == 'S') {
b = true;
}
if(s[i] == 'W') {
c = true;
}
if(s[i] == 'E') {
d = true;
}
}
if(!(a ^ b) && !(c ^ d)) {
printf("Yes\n");
}
else {
printf("No\n");
}
return 0;
}
B - Simplified majhong
考虑一个极大的区间 \([l, r]\)，满足 \(\forall i \in [l, r]\)，\(A_i > 0\)。
假设我们用相同点数的牌凑对子，则剩下的牌数量为满足 \(A_i\) 为奇数的 \(i\) 的数目。
考虑一个有序数列 \([p, q]\)（\(p < q\)），满足 \(\forall i \in (p, q)\)，\(A_i \bmod 2 = 0\)，且 \(A_p \bmod 2 = A_q \bmod 2 = 1\)，因为 \(\forall i \in (p, q)\)，\(A_i \bmod 2 = 0\) 且 \(A_i > 0\)，所以 \(A_i \ge 2\)，可以将 \((p, q)\) 间点数的对子各拆一个，然后让 \((p, p + 1), (p + 1, p + 2), \dots, (q - 1, q)\) 各凑一个对子，这样答案每次可以增加 \(2\)，最多只剩下一张牌，这样就达到了这一极大区间对答案贡献的上界。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 100005;
int n, a[N];
int main() {
int i;
n = Read();
for(i = 1; i <= n; i++) {
a[i] = Read();
}
ll sum = 0, ans = 0;
for(i = 1; i <= n + 1; i++) {
if(a[i]) {
sum += a[i];
}
else {
ans += sum / 2, sum = 0;
}
}
Write(ans), putchar('\n');
return 0;
}