A - Slots

题目大意

给定三个大写英文字母$C_1,C_2,C_3$，判断它们是否相同。

输入格式

$C_1C_2C_3$

输出格式

如果$C_1,C_2,C_3$相等，输出Won；否则，输出Lost。

样例

分析

这题如果不会做，就等于没学过C++吧……

代码

注意：请不要将Won和Lost写成Yes和No！

1
2
3
4
5
6
7
8
9

#include <cstdio>
using namespace std;

int main(int argc, char** argv)
{
    char a = getchar(), b = getchar(), c = getchar();
    puts((a == b && b == c)? "Won": "Lost");
    return 0;
}

B - Alcoholic

题目大意

一个人要按顺序喝$N$杯酒。第$i$杯酒有$V_i$毫升，酒精含量为$P_i\%$（$1\le i\le N$）。
他喝的酒精总含量超过$X$毫升时将会醉酒。（如果正好喝了$X$毫升也不会喝醉）
他喝完第几杯酒后会第一次喝醉？

$1\le N\le 10^3$
$0\le X\le 10^6$
$1\le V_i\le 10^3$
$0\le P_i\le 100$

输入格式

$N~X$
$V_1~P_1$
$\vdots$
$V_N~P_N$

输出格式

如果这个人在喝完第$i$杯酒后第一次喝醉，输出$i$。如果他直到最后都没有喝醉，输出-1。

样例

样例输入1

1
2
3

2 15
200 5
350 3

样例输出1

1

2

第$1$杯酒含有$200\times5\%=10$毫升的酒精。
第$2$杯酒含有$350\times3\%=10.5$毫升的酒精。
他喝完第二杯酒后一共喝了$20.5$毫升的酒精，高于最大可承受量（$15$），所以我们输出$2$。

样例输入2

1
2
3

2 10
200 5
350 3

样例输出2

1

2

当他正好喝了$X$毫升的酒精时，他还没有喝醉。

样例输入3

1
2
3
4

3 1000000
1000 100
1000 100
1000 100

样例输出3

1

-1

他似乎免疫酒精了……

分析

第$i$杯酒中酒精的量是$V_i\times P_i\%$，即$V_i\times P_i/100$。
这时，我们将题目转化一下，就是求符合$V_1\times P_1/100+V_2\times P_2/100+...+V_i\times P_i/100 > X$的最小$i$。所以，我们很容易想到在输入的同时计算$V_1\times P_1/100+V_2\times P_2/100+...+V_i\times P_i/100$，当它大于$X$时输出$i$。
但是，这里有一个问题。
由于C++存在浮点数精度误差，所以这样算可能会得到错误的结果。
例如，下面一组数据：（数据来自AtCoder官方题解）

1
2
3
4

3 13
30 13
35 13
35 13

这时，我们就可以用前面的思路写代码了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <cstdio>
using namespace std;

int main(int argc, char** argv)
{
    int n, x;
    scanf("%d%d", &n, &x);
    x *= 100;
    for(int i=1; i<=n; i++)
    {
        int v, p;
        scanf("%d%d", &v, &p);
        x -= v * p;
        if(x < 0)
        {
            printf("%d\n", i);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

C - Mandarin Orange

题目大意

Takahashi面前有$N$个碗排成一行，从左数第$i$个碗中装有$A_i$个橙子。
他会选出以个符合下列所有条件的三元组$(l,r,x)$：

• $1\le l\le r\le N$
• $1\le x\le A_i$（$l\le i\le r$）

然后，他在第$l$个到第$r$个盘子（包含$l$和$r$）中每个吃掉$x$个橙子。
通过选择三元组$(l,r,x)$以最大化此数目，Takahashi最多可以吃多少个橙子？

$1\le N\le 10^4$
$1\le A_i\le 10^5$

输入格式

$N$
$A_1~\dots~A_N$

输出格式

输出一行，即Takahashi最多可以吃的橙子的个数。

样例

样例输入1

1
2

6
2 4 4 9 4 9

样例输出1

1

20

他可以选择$(l,r,x)=(2,6,4)$，能吃$20$个橙子。

样例输入2

1
2

6
200 4 4 9 4 9

样例输出2

1

200

他可以选择$(l,r,x)=(1,1,200)$，能吃$200$个橙子。

分析

很明显，如果我们选择$(l,r,x)$，则Takahashi能吃$(l-r+1)x$个橙子。
我们要让吃的橙子个数最大化，那么选择$(l,r)$后，$x$必定为$\min\{A_l,A_{l+1},...,A_r\}$。这样一来，我们就可以枚举$(l,r)$，并记录$\min\{A_l,A_{l+1},...,A_r\}$作为$x$，最终输出最小的$(l-r+1)x$。
这个算法的时间复杂度为$\mathcal O(n^2)$。

代码

 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

#include <cstdio>
#define maxn 10005
#define INF 2147483647
using namespace std;

int a[maxn];

inline void setmin(int& a, int b) {if(b < a) a = b;}
inline void setmax(int& a, int b) {if(b > a) a = b;}

int main(int argc, char** argv)
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", a + i);
    int ans = 0;
    for(int l=0; l<n; l++)
    {
        int m = INF;
        for(int r=l; r<n; r++)
        {
            setmin(m, a[r]);
            setmax(ans, (r - l + 1) * m);
        }
    }
    printf("%d\n", ans);
    return 0;
}

D - Logical Expression

题目大意

给你$N$个字符串$S_1,S_2,...,S_N$，每个是AND或者OR。
找到符合下列条件的长度为$(N+1)$的元组$(x_0,x_1,...,x_N)$的数量：

• $x_i$是$\text{True}$或者$\text{False}$；
• $y_0=x_0$；
• 当$i\ge 1$时：如果$S_i$为AND，$y_i=y_{i-1}\land x_i$；如果$S_i$为OR，则$y_i=y_{i-1}\lor x_i$。

在这里，$a\land b$表示$a$与$b$，$a\lor b$表示$a$或$b$。

$1\le N\le 60$

输入格式

$N$
$S_1$
$\vdots$
$S_N$

输出格式

输出答案。

样例

略，请自行前往AtCoder查看

分析

其实，题目解释得有些复杂了 :(
理解时例如样例$1$：

我们将$f(N)$定义为本题$S=\{S_1,S_2,\dots,S_N\}$的答案，则
$f(N)=\begin{cases} f(N-1) & (S_N=\text{AND})\\ f(N-1)\times2^N & (S_N=\text{OR}) \end{cases}$
这时，我们就可以在输入时处理答案了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <cstdio>
using namespace std;

int main(int argc, char** argv)
{
    int n;
    scanf("%d", &n);
    char c[4];
    long long ans = 1LL, x = 1LL;
    while(n--)
    {
        x <<= 1LL;
        scanf("%s", c);
        if(c[0] == 'O')
            ans ^= x; // 等同于ans += x;这样写速度更快
    }
    printf("%lld\n", ans);
    return 0;
}