传送门

A - Count Takahashi

时间限制：2秒        内存限制：1024MB

分数：100分

问题描述

给定 N 个字符串。

第 i 个字符串  () 要么是 Takahashi 要么是 Aoki。

有多少个 i 使得  等于 Takahashi ？

限制

• 
• N 是整数。
• 每个字符串  是 Takahashi 或者 Aoki。()

输入格式

        

输出格式

        输出  等于 Takahashi 的数量。

样例输入输出

样例输入1

        

样例输出1

        

 和  等于 Takahashi，而  不等于 Takahashi。

因此，输出 2。

样例输入2

        

样例输出2

        

没有  等于 Takahashi。

样例输入3

        

样例输出3

        

代码

#include <bits/stdc++.h>
using namespace std;

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

int main () {
    int n = read(), cnt = 0;
    while (n--) {
        string s;
        cin >> s;
        if (s[0] == 'T') cnt++;
    }
    cout << cnt;
    return 0;
}

B - Couples

时间限制：2秒        内存限制：1024MB

分数：150分

问题描述

有 2N 个人站成一排，位于第i个位置的人穿着颜色为  的衣服。这里，衣服有 N 种颜色，每种颜色正好有两个人穿。

找出满足以下条件的整数  的数量：

• 颜色为 i 的两个人之间正好有一个人。

限制

• 
• 
• 每个从 1 到 N 的每个整数在 A 中恰好出现两次。
• 所有输入值都是整数。

输入格式

        

输出格式

        输出答案

样例输入输出

样例输入1

        

样例输出1

        

有两个 i 值满足条件：1 和 3。

实际上，穿着颜色为 1 的衣服的人分别在从左数第 1 和第 3 的位置，中间正好有一个人。

样例输入2

        

样例输出2

        

没有 i 值满足条件。

样例输入3

        

样例输出3

        

代码

#include <bits/stdc++.h>
using namespace std;

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

int main () {
    int n = read(), a[205], cnt = 0;
    for (int i = 1; i <= 2 * n; i++) a[i] = read();
    for (int i = 1; i < 2 * n; i++) {
        for (int j = i + 1; j <= 2 * n; j++) {
            if (a[i] == a[j] && j == i + 2) {
                cnt++;
                break;
            }
        }
    }
    cout << cnt;
    return 0;
}

C - Tile Distance 2

时间限制：2秒        内存限制：1024MB

分数：350分

问题描述

坐标平面被 2 × 1 的瓷砖覆盖。瓷砖的铺设遵循以下规则：

• 对于整数对 (i, j)，方块 包含在一块瓷砖中。
• 当 i + j 是偶数时， 和  包含在同一块瓷砖中。

瓷砖包括它们的边界，并且没有两块不同的瓷砖共享正面积。

在靠近原点的地方，瓷砖的铺设如下：

Takahashi 从坐标平面上的点 ( + 0.5,  + 0.5) 开始。

他可以重复以下移动操作任意次数：

选择一个方向（上，下，左，右）和一个正整数 n。向该方向移动 n 个单位。
每次他进入一个瓷砖，他需要支付 1 的费用。

求他到达点 ( + 0.5,  + 0.5) 所需支付的最少费用。

限制

• 
• 
• 
• 
• 所有输入都是整数。

输入格式

        

输出格式

        输出 Takahashi 需要支付的最少费用。

样例输入输出

样例输入1

        

样例输出1

        

例如，Takahashi 可以通过以下移动支付 5 的费用：

• 向左移动 1。支付 0 的费用。
• 向上移动 1。支付 1 的费用。
• 向左移动 1。支付 0 的费用。
• 向上移动 3。支付 3 的费用。
• 向左移动 1。支付 0 的费用。
• 向上移动 1。支付 1 的费用。

无法将费用减少到 4 或更少，因此输出 5。

样例输入2

        

样例输出2

        

有些情况下不需要支付任何费用。

样例输入3

        

样例输出3

        

注意，输出的值可能会超过 32 位整数的范围。

思路

将移动分为竖直方向跟水平方向来考虑。

任何情况下，在竖直方向上的移动需要支付  。与此同时也能在水平方向上移动  个单位，所以要给  加上  。如果在此之后水平方向依旧无法到达，则需要加上  。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main () {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a > c) swap(a, c), swap(b, d);
    if ((c + d) & 1) c--;
    if ((a + b) % 2 == 0) a++;
    int ans = abs(b - d);
    a += ans;
    if (a < c) ans += (c - a + 1) / 2;
    cout << ans;
    return 0;
}

E - Water Tank

时间限制：2秒        内存限制：1024MB

分数：500分

问题描述

给定一个长度为 N 的正整数序列 。

有一个长度为 N + 1 的非负整数序列 ，初始时 。

重复执行以下操作直到结束：

1. 将 的值增加 1。
2. 对于每个 ，按顺序执行以下操作：
  如果 并且 ，则将 的值减少 1，同时将 的值增加 1。

对于每个 ，找出在 首次成立之前执行了多少次操作。

限制

• 
• 
• 所有输入都是整数。

输入格式

        

输出格式

        将对于每个 的答案输出在一行上，以空格分隔。

样例输入输出

样例输入1

        

样例输出1

        

前五次操作如下。

这里，每一行对应一次操作，最左边的列代表步骤 1，其余的代表步骤 2。

从这个图表中可以看出， 首次在第4次操作后成立，而  首次在第5次操作后成立。

类似地， 的答案分别是 13，14，26。

因此，你应该输出 4 5 13 14 26。

样例输入2

样例输出2

请注意，输出的值可能超出 32 位整数的范围。

样例输入3

样例输出3

思路

先说歪解：看样例猜答案

我们很容易能发现每一个输出第第一项都是 。当  的时候，如果 ，那么 ；否则 。

（至于为什么各位先别急

•  是因为  才能将大于  的部分转移到 上

每次操作第二步的转移，题目意思是从  上连续转移到最右边可以转移的位置上，但这个也等价于在任意  上加 1，再向右转移

• 如果 ，那么在这个条件下，只需要在  上加 1，再将这个 1 转移到  上去即可（1步操作），所以 。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n, h[N], a[N], maxid = 1;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
stack<int> s;
signed main () {
	n = read();
	for (int i = 1; i <= n; i++) h[i] = read();
	for (int i = 1; i <= n; i++) {
		while (s.size() && h[s.top()] < h[i]) s.pop();
		if (s.size()) a[i] = a[s.top()] + (i - s.top()) * h[i];
		else a[i] = i * h[i] + 1;
		s.push(i);
	}
	for (int i = 1; i <= n; i++) printf("%lld ", a[i]);
    return 0;
}