【题解】跨年ak场题解

跨年ak场出题组：兰子、沙烬、智乃给大家拜年了！！！

A

如果输出5，说明所有题都把你防住了，这样你就通过了0题，那么这题就通过不了。

输出0~4中任意一个数字都可以通过本题。

参考代码：（php语言）

0

B

画图题。注意输入右斜杠是"\"。

参考代码：

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

int n ;

int main() {
    scanf("%d",&n);

        for (int j = 1 ; j <= n ; j ++) {
            string s;
            for (int k = 1 ; k < j ; k ++) {
                s += ' ';
            }
            s += "\\";
            for (int k = 1 ; k <= n-j ; k ++) {
                s += ' ';
            }
            s += "|";
            for (int k = 1 ; k <= n-j ; k ++) {
                s += ' ';
            }
            s += '/';
            for (int k = 1 ; k < j ; k ++) {
                s += ' ';
            }
            cout << s << endl;
        }
        string s;
        for (int j = 1 ; j <= n ; j ++) {
            s += '-';
        }
        s += 'O';
        for (int j = 1 ; j <= n ; j ++) {
            s += '-';
        }
        cout << s << endl;
        for (int j = 1 ; j <= n ; j ++) {
            string s;
            for (int k = 1 ; k <= n-j ; k ++) {
                s += ' ';
            }
            s += "/";
            for (int k = 1 ; k < j ; k ++) {
                s += ' ';
            }
            s += '|';
            for (int k = 1 ; k < j ; k ++) {
                s += ' ';
            }
            s += '\\';
            for (int k = 1 ; k <= n-j ; k ++) {
                s += ' ';
            }
            cout << s << endl;
        }
}

C

留给小红的攒雪球的时间是小紫的时间减去1。所以最终的答案是

参考代码：

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

int main() {
    long long x, y, a;
    scanf("%lld%lld%lld",&x,&y,&a);
    printf("%lld",(y*a-1)/x);
}

D

显然 X 都可以当成 9 来看，因为求的是最大的可能。

所以把所有 X 替换成 9 ，排序一下即可。

彩蛋：

智乃：我就是要卡掉那些觉得X是无敌的人！

结果：最终数据还是弱了，放过了部分错解~

感谢智乃大魔王的仁慈吧，哈哈哈哈嗝（

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
struct node
{
    string data;
    int id;
}a[MAXN];
int n;
int main()
{
    cin>>n;
    assert(n<=1000);
    for(int i=1;i<=n;++i)
    {
        cin>>a[i].data;
        assert(a[i].data.size()<=100);
        a[i].id=i;
        for(auto &it:a[i].data)
        {
            if(it=='X')it='9';
        }
    }
    sort(a+1,a+1+n,[](const node &A,const node &B){
        if(A.data.size()!=B.data.size())
            return A.data.size()>B.data.size();
        return A.data>B.data;
    });
    cout<<a[1].id;
    return 0;
}

E

本场唯一一个需要一定思维的题目。

我们先以下面的字符串举例："afnabasfoab"

不难想到，最后一个'b'，谁的 t 串添加到这里谁就赢了。那么字符串标记为。其中中括号为必胜区间。

那么，这个 b 到上一个 b 之间所有的字母都是必败的。因为如果某人“不小心”取到了这些字母中的任意一个，对方只要在后面加一个 'b' ，就直接到了最后一个 b 了。

因此，第五个字母 'b' 后面这些字母都是必败的。字符串标记为 。其中小括号为必败区间。

那么第四个字母'a'就是必胜的，因为只要某人取到了这个 a ，对方就不得不取后面的小括号区间的某个字母，导致失败。

以此类推，字符串可以标记为 。标记的逻辑是：最后一个字母 为必胜，那么找到它前面离它最近的那个 ，这段区间为必败。必败区间前面的那个字母为必胜，以此类推，标记出所有区间。

那么怎么评定胜负的标准呢？很简单，若第一个字母在必败区间，那么小红必败。否则小红必胜，因为小红可以直接取到第一个必败区间前面的那一个字母，迫使紫m去取必败区间。

彩蛋：如果要求每次添加的时候t都是s的子串，解法是后缀自动机next指针dag图上求sg函数，恕出题人不会qwq

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int i,j=s.length()-1;
    for(i=j-1;i>=0;i--){
        if(s[i]==s[j])j=i-1,i=j;
    }
    if(j==-1)cout<<"yukari";
    else cout<<"kou";
}