[ABC337A] Scoreboard

题面翻译

题目描述

高桥队和青木队进行了 $N$ 次比赛。在第 $i$ 局$（1\leq i\leq N）$的比赛中，高桥队获得了 $Xi$ 分，青木队获得了 $Yi$ 分。

在 $N$ 次比赛中获得的分数合计更多的队伍获胜。

请输出哪个队赢了。但是，两支队伍获得的分数合计相等的情况下为平局。

输入格式

输入按以下格式：

第一行一个数 $N$；

接下来 $N$ 行，每行两个数 $Xi$ 和 $Yi$ ，分别表示高桥队和青木队第 $i$ 轮获得的分数。

输出格式

如果高桥队获胜就输出Takahashi；

如果青木队获胜就输出Aoki；

如果平局就输出Draw。

翻译来自 @zhouxianzhuo

题目描述

チーム高橋とチーム青木が $ N $ 回の試合を行いました。 $ i $ 回め $ (1 i N) $ の試合ではチーム高橋が $ X i $ 点、チーム青木が $ Y i $ 点を獲得しました。

$ N $ 回の試合で獲得した得点の合計がより多いチームの勝ちです。

どちらのチームが勝ったか出力してください。ただし、獲得した得点の合計が等しい場合は引き分けとなります。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ X 1 $ $ Y 1 $ $ X 2 $ $ Y 2 $ $ $ $ X N $ $ Y N $

输出格式

チーム高橋が勝った場合 Takahashi を、チーム青木が勝った場合 Aoki を、引き分けの場合 Draw を出力せよ。

样例 #1

样例输入 #1

样例输出 #1

Takahashi

样例 #2

样例输入 #2

样例输出 #2

Draw

样例 #3

样例输入 #3

样例输出 #3

Aoki

提示

制約

$ 1 N 100 $
$ 0 X _ i 100 (1 i N) $
$ 0 Y _ i 100 (1 i N) $
入力はすべて整数

Sample Explanation 1

$ 4 $ 回の試合で、チーム高橋は $ 33 $ 点、チーム青木は $ 7 $ 点を獲得しました。チーム高橋が勝ったため、Takahashi を出力してください。

Sample Explanation 2

いずれのチームも $ 22 $ 点を獲得しました。引き分けなので、Draw を出力してください。

Sample Explanation 3

一方もしくは両方のチームが、一試合のうちに $ 1 $ 点も取れない場合もあります。

//水题
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    LL a = 0, b = 0;
    while (n--)
    {
        int x, y;
        cin >> x >> y;
        a += x;
        b += y;
    }
    if (a > b)
        cout << "Takahashi" << '\n';
    else if (a < b)
        cout << "Aoki" << '\n';
    else
        cout << "Draw" << '\n';

    return 0;
}

[ABC337B] Extended ABC

题面翻译

扩展 A 串是有 $i \ge 0$ 个 A 组成，扩展 B 串是有 $i \ge 0$ 个 B 组成，扩展 C 串是有 $i \ge 0$ 个 C 组成，

问你给定字符串 $S$ 是不是扩展 A 串 $+$ 扩展 B 串 $+$ 扩展 C 串的结构。

题目描述

拡張 A 文字列、拡張 B 文字列、拡張 C 文字列および拡張 ABC 文字列を以下のように定義します。

文字列 $ S $ が拡張 A 文字列であるとは、$ S $ のすべての文字が A であることをいいます。
文字列 $ S $ が拡張 B 文字列であるとは、$ S $ のすべての文字が B であることをいいます。
文字列 $ S $ が拡張 C 文字列であるとは、$ S $ のすべての文字が C であることをいいます。
文字列 $ S $ が拡張 ABC 文字列であるとは、ある拡張 A 文字列 $ S A $ 、拡張 B 文字列 $ S B $ 、拡張 C 文字列 $ S C $ が存在して、$ S A,S B,S C $ をこの順に連結した文字列が $ S $ と等しいことをいいます。

例えば、ABC や A 、AAABBBCCCCCCC などは拡張 ABC 文字列ですが、ABBAAAC 、BBBCCCCCCCAAA などは拡張 ABC 文字列ではありません。空文字列は拡張 A 文字列でも拡張 B 文字列でも拡張 C 文字列でもあることに注意してください。

A, B, C からなる文字列 $ S $ が与えられます。 $ S $ が拡張 ABC 文字列ならば Yes を、そうでなければ No を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ S $

输出格式

$ S $ が拡張 ABC 文字列ならば Yes を、そうでなければ No を出力せよ。

样例 #1

样例输入 #1

1	AAABBBCCCCCCC

样例输出 #1

Yes

样例 #2

样例输入 #2

ACABABCBC

样例输出 #2

No

样例 #3

样例输入 #3

样例输出 #3

Yes

样例 #4

样例输入 #4

1	ABBBBBBBBBBBBBCCCCCC

样例输出 #4

Yes

提示

制約

$ S $ は A, B, C からなる文字列
$ 1|S| 100 (|S| $ は文字列 $ S $ の長さ$ ) $

Sample Explanation 1

AAABBBCCCCCCC は長さ $ 3 $ の拡張 A 文字列 AAA 、長さ $ 3 $ の拡張 B 文字列 BBB 、長さ $ 7 $ の拡張 C 文字列 CCCCCCC をこの順に連結した文字列なので、拡張 ABC 文字列です。よって、Yes を出力してください。

Sample Explanation 2

どのような拡張 A 文字列 $ S A, $ 拡張 B 文字列 $ S B, $ 拡張 C 文字列 $ S C $ についても、$ S A,S B,S C $ をこの順に連結した文字列が ACABABCBC と等しくなることはありません。よって、No を出力してください。

//去重排序和原来的去重一样的话
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    s.erase(unique(s.begin(), s.end()), s.end());
    auto t = s;
    ranges::sort(t);
    if (s == t)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

//做法二：去重+打表
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL mod = 998244353;
const LL N = 5e5;

int main()
{
    string S;
    cin >> S;
    S.erase(unique(S.begin(), S.end()), S.end());
    if (S == "ABC" || S == "A" || S == "B" || S == "C" || S == "AB" || S == "AC" || S == "BC")
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

[ABC337C] Lining Up 2

题面翻译

有 $n$ 个人在排队。给一个数组 $s$，表示：

如果 $s_i=-1$，那么第 $i$ 个人在队首。
如果 $s_i \ne -1$，那么第 $i$ 个人排在第 $s_i$ 个人的后面。

请输出队伍的情况。

题目描述

人 $ 1, $ 人 $ 2,, $ 人 $ N $ の $ N $ 人が一列に並んでいます。

並び方の情報が長さ $ N $ の数列 $ A=(A 1,A 2,,A _ N) $ として与えられます。

$ A _ i (1 i N) $ は次のような情報を表しています。

$ A _ i=-1 $ のとき、人 $ i $ は先頭に並んでいる。
$ A i -1 $ のとき、人 $ i $ は人 $ A i $ のすぐ後ろに並んでいる。

列に並んでいる人の番号を先頭から順番に出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A 1 $ $ A 2 $ $ $ $ A _ N $

输出格式

人 $ s 1, $ 人 $ s 2,, $ 人 $ s N $ がこの順に列に並んでいるとき、$ s 1,s 2,,s N $ をこの順に空白を区切りとして出力せよ。

样例 #1

样例输入 #1

1 2	6 4 1 -1 5 3 2

样例输出 #1

1	3 5 4 1 2 6

样例 #2

样例输入 #2

1 2	10 -1 1 2 3 4 5 6 7 8 9

样例输出 #2

1	1 2 3 4 5 6 7 8 9 10

样例 #3

样例输入 #3

1 2	30 3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

样例输出 #3

1	10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

提示

制約

$ 1 N ^ 5 $
$ A i=-1 $ もしくは $ 1 A i N (1 i N) $
情報と矛盾しないような $ N $ 人の並び方がただ $ 1 $ 通り存在する
入力はすべて整数

Sample Explanation 1

先頭から、人 $ 3, $ 人 $ 5, $ 人 $ 4, $ 人 $ 1, $ 人 $ 2, $ 人 $ 6 $ がこの順に列に並んでいるとき、与えられた情報と一致しています。実際、 - 人 $ 1 $ は人 $ 4 $ のすぐ後ろに並んでいます。 - 人 $ 2 $ は人 $ 1 $ のすぐ後ろに並んでいます。 - 人 $ 3 $ は先頭に並んでいます。 - 人 $ 4 $ は人 $ 5 $ のすぐ後ろに並んでいます。 - 人 $ 5 $ は人 $ 3 $ のすぐ後ろに並んでいます。 - 人 $ 6 $ は人 $ 2 $ のすぐ後ろに並んでいます。となり、与えられた情報と一致していることが確認できます。よって、$ 3,5,4,1,2,6 $ をこの順に空白区切りで出力してください。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
//记录一下后继
//类似单链表
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    map<int, int> pos;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        pos[x] = i + 1;
    }
    int st = pos[-1];
    //找到-1
    cout << st;
    //-1对应的下标在对应的下一个
    for (int i = 0; i < n - 1; i++)
    {
        st = pos[st];
        cout << ' ' << st;
    }
    cout << '\n';
    return 0;
}

[ABC337D] Cheating Gomoku Narabe

题面翻译

题目描述

给定一个 $H$ 行 $W$ 列的矩阵，矩阵由 o、x、. 三种字符组成。你可以进行若干次操作（可以不做），每次操作可以把矩阵中的一个 . 改成 o。请问最少经过多少次操作后，能在矩阵中找到位于同一行或同一列的连续 $K$ 个 o。

输入描述

第一行三个整数 $H$，$W$ 和 $K$。接下来 $H$ 行，每行一个长度为 $W$ 的字符串，由字符 o、x、. 组成，表示这个矩阵。

输出描述

输出最小的操作次数。如果永远不能满足要求，输出 -1。

题目描述

$ H $ 行 $ W $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i, j) $ と呼びます。

各マスには o 、x 、. のうちいずれかの文字が書かれています。各マスに書かれた文字は $ H $ 個の長さ $ W $ の文字列 $ S_1, S_2, , S_H $ で表され、マス $ (i, j) $ に書かれた文字は、文字列 $ S_i $ の $ j $ 文字目と一致します。

このグリッドに対して、下記の操作を $ 0 $ 回以上好きな回数だけ繰り返します。

. が書かれているマスを $ 1 $ 個選び、そのマスに書かれた文字を o に変更する。

その結果、縦方向または横方向に連続した $ K $ 個のマスであってそれらに書かれた文字がすべて o であるようなものが存在する（すなわち、下記の $ 2 $ つの条件のうち少なくとも一方を満たす）ようにすることが可能かを判定し、可能な場合はそのために行う操作回数の最小値を出力してください。

$ 1 i H $ かつ $ 1 j W-K+1 $ を満たす整数の組 $ (i, j) $ であって、マス $ (i, j), (i, j+1), , (i, j+K-1) $ に書かれた文字が o であるものが存在する。
$ 1 i H-K+1 $ かつ $ 1 j W $ を満たす整数の組 $ (i, j) $ であって、マス $ (i, j), (i+1, j), , (i+K-1, j) $ に書かれた文字が o であるものが存在する。

输入格式

入力は以下の形式で標準入力から与えられる。

$ H $ $ W $ $ K $ $ S_1 $ $ S_2 $ $ $ $ S_H $

输出格式

問題文中の条件を満たすことが不可能な場合は -1 を、可能な場合はそのために行う操作回数の最小値を出力せよ。

样例 #1

样例输入 #1

3 4 3
xo.x
..o.
xx.o

样例输出 #1

样例 #2

样例输入 #2

4 2 3
.o
.o
.o
.o

样例输出 #2

样例 #3

样例输入 #3

3 3 3
x..
..x
.x.

样例输出 #3

-1

样例 #4

样例输入 #4

10 12 6
......xo.o..
x...x.....o.
x...........
..o...x.....
.....oo.....
o.........x.
ox.oox.xx..x
....o...oox.
..o.....x.x.
...o........

样例输出 #4

提示

制約

$ H, W, K $ は整数
$ 1 H $
$ 1 W $
$ H W 2 10^5 $
$ 1 K H, W $
$ S_i $ は o 、x 、. のみからなる長さ $ W $ の文字列

Sample Explanation 1

操作を $ 2 $ 回行って、例えばマス $ (2, 1) $ とマス $ (2, 2) $ に書かれた文字をそれぞれ o に変更することで問題文中の条件を満たすことができ、これが最小の操作回数です。

Sample Explanation 2

操作を一度も行わなくても問題文中の条件を満たします。

Sample Explanation 3

問題文中の条件を満たすことは不可能なので、-1 を出力します。

#include <bits/stdc++.h>
using namespace std;
int i, j, n, m, k, s1, s2, ans = INT_MAX;
using LL = long long;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    char a[n + 5][m + 5];
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            cin >> a[i][j];
    }
    for (i = 1; i <= n; i++)
    {
        s1 = s2 = 0;
        for (j = 1; j <= m; j++)
        {
            if (j > k && a[i][j - k] == '.')
                s2--;
            if (a[i][j] == '.')
                s2++;
            if (a[i][j] == '.' || a[i][j] == 'o')
                s1++;
            else
                s1 = 0;
            if (s1 >= k)
                ans = min(ans, s2);
        }
    }
    for (j = 1; j <= m; j++)
    {
        s1 = s2 = 0;
        for (i = 1; i <= n; i++)
        {
            if (i > k && a[i - k][j] == '.')
                s2--;
            if (a[i][j] == '.')
                s2++;
            if (a[i][j] == '.' || a[i][j] == 'o')
                s1++;
            else
                s1 = 0;
            if (s1 >= k)
                ans = min(ans, s2);
        }
    }
    if (ans == INT_MAX)
        cout << -1;
    else
        cout << ans;
    return 0;
}

[ABC337E] Bad Juice

题面翻译

有 $n$ 杯果汁，其中一杯是发霉的，喝了发霉的果汁会窜稀。

现在你不知道哪杯是发霉的，但明天你要把这些果汁因此你想去坑你的好基友，让他们喝下这些果汁。每个基友可以喝很多杯果汁，每杯果汁可以被很多基友喝。

为了得罪尽量少的人，请求出最少需要给多少基友喝果汁，并构造出一种方案。

接下来用一个字符串 $s$ 给出你的方案中每个人的窜稀情况，1 代表窜稀，0 代表没有窜稀。你需要据此输出发霉的果汁编号。

交互题。先读入 $n$，然后输出方案，然后读入 $s$，然后输出发霉的果汁编号。每次输出完需要刷新标准输出。编号全部从 $1$ 开始。

交互方式示例：

请在输出完毕后使用 fflush(stdout) 或 endl 清空缓冲区，然后再获得下一个输入。

输入	输出	解释
`3`		给出 $n$。
	`2`	输出叫的朋友人数。
	`2 1 2`	给第一个朋友喝果汁 $1$ 和果汁 $2$。
	`1 2`	给第二个朋友喝果汁 $2$。
`10`		给出每个朋友是否肚子疼。
	`1`	输出发霉的果汁编号。

题目描述

この問題は インタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

$ 1 $ から $ N $ の番号がついた $ N $ 本のジュースがあります。このうちちょうど $ 1 $ 本が腐っていることが判明しました。そのジュースを微量でも飲むと、翌日お腹を壊してしまいます。

高橋君は翌日までに腐ったジュースを特定しなければなりません。高橋君はそのために必要な最小の数の友人を呼び、それぞれに $ N $ 本のジュースのうちの一部を振る舞うことにしました。各友人には何本でもジュースを与えることができ、各ジュースは何人の友人にでも与えることができます。

呼ぶ友人の数とジュースの与え方を出力して、翌日に各友人がお腹を壊したかどうかの情報を受け取り、腐ったジュースの番号を出力してください。

Input & Output Format

この問題はインタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

対話を行う前にジャッジは、腐ったジュースの番号 $ X $ として $ 1 $ 以上 $ N $ 以下の整数を秘密裏に選択します。 $ X $ の値はあなたには与えられません。また、対話の途中で $ X $ の値が制約および以前の出力に矛盾しない範囲で変わる場合があります。

まず、ジャッジから $ N $ が入力から与えられます。

$ N $

あなたは呼ぶ友人の数 $ M $ を出力し改行してください。

$ M $

さらに、あなたは次に述べる $ M $ 回の出力からなる手続きを行ってください。 $ i = 1, 2, , M $ について $ i $ 回目の出力では、 $ i $ 番目の友人に飲ませるジュースの本数 $ K_i $ および、それら $ K_i $ 本のジュースの番号を昇順に並べた列 $ A_{i, 1}, A_{i, 2}, , A_{i, K_i} $ を下記の形式で空白区切りで出力し、改行してください。

$ K_i $ $ A_{i, 1} $ $ A_{i, 2} $ $ $ $ A_{i, K_i} $

その後ジャッジから、各友人が翌日にお腹を壊したかどうかの情報が、0 と 1 のみからなる長さ $ M $ の文字列 $ S $ として与えられます。

$ S $

$ i = 1, 2, , M $ について、$ S $ の $ i $ 文字目が 1 のとき、かつそのときに限り、$ i $ 番目の友人がお腹を壊したことを表します。

それに対し、あなたは腐ったジュースの番号 $ X' $ を出力し、改行してください。

$ X' $

その後、直ちにプログラムを終了してください。

あなたが出力した $ M $ が $ N $ 本のジュースから腐ったジュースを特定するために必要な最小の友人の数であり、かつ、あなたが出力した $ X' $ が腐ったジュースの番号 $ X $ と一致していれば、正解となります。

输入格式

输出格式

提示

制約

$ N $ は整数
$ 2 N 100 $

注意点

出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。 特に、プログラムの実行中に実行時エラーが起こった場合に、ジャッジ結果が RE ではなく WA や TLE になる可能性があることに注意してください。
$ X' $ を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
この問題のジャッジはアダプティブです。つまり、制約および以前の出力に矛盾しない範囲で $ X $ の値が変わる場合があります。

入出力例

以下は、$ N = 3 $ の場合の入出力例です。

入力 出力 説明     `3`  ジュースの本数 $ N $ が与えられます。    `2` 呼ぶ友人の数 $ M $ を出力します。    `2 1 2` $ 1 $ 人目の友人にジュース $ 1 $ とジュース $ 2 $ を与えます。     `1 2` $ 2 $ 人目の友人に、ジュース $ 2 $ を与えます。     `10`  翌日に各友人がお腹を壊したかどうかを表す文字列 $ S $ が与えられます。    `1` 腐ったジュースの番号を出力します。

//注意交互题格式
//注意点是一种二进制套路
//枚举每一位的一个思路，建议记住
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n, ans;
string s;
int main()
{
    cin >> n;
    cout << __lg(n - 1) + 1 << endl;
    //输出方案
    for (int i = 0; i <= __lg(n - 1); i++)
    {
        ll sum = 0;
        for (int j = 1; j <= n; j++)
        {
            if (j & (1 << i))
                sum++;
        }
        cout << sum;
        //第一个人喝几瓶
        for (int j = 1; j <= n; j++)
        {
            if (j & (1 << i))
                cout << ' ' << j;
        }
        //输出
        cout << endl;
    }
    cin >> s;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '1')
            ans += (1 << i);
    }
    if (ans == 0)
        ans = n;
    cout << ans << endl;
    return 0;
}

输入	输出	解释
`3`		给出 \(n\)。
	`2`	输出叫的朋友人数。
	`2 1 2`	给第一个朋友喝果汁 \(1\) 和果汁 \(2\)。
	`1 2`	给第二个朋友喝果汁 \(2\)。
`10`		给出每个朋友是否肚子疼。
	`1`	输出发霉的果汁编号。