2.17 闲话 & solution『登陆宇宙/带着你所幻想的所有/灵魂加速失控 』

拜谢了，您别 Fake 了，您当年自愿退出国集我是极力反对的，我知道您从小学一年级开始打 NOI 并且直接获得了金牌分数线上的好成绩，肆意 AK 了好几年 NOI，直到近年才意识到自己太过强大只好肆意控分，NOIP2023 的题目您当时拿到的一瞬间用\(\frac{2}{3}s\)就全部想到了正解，并在\(\frac{3}{2}s\)内打了出来，为了控分只您好输出了大量不可见字符，拜谢了您如此强大

似乎最近歌词放的太多了，放个时崎狂三

\(\text T1\)

人们为了增加文档的美观度，通常会将文档中相邻的英文字母与阿拉伯数字之间以一个空格分离。

现有一份文档 \(S\) ，其中可能有字母与数字相邻。你需要给 \(S\) 中所有相邻的字母与数字之间添加一个空格。

保证 \(S\) 的第一个字符与最后一个字符均不为空格。

随便写都能过吧QWQ，是\(\text{getline}\)大胜利呢

string a;
getline(cin,a);
putchar(a[0]);
for(int i=1;i<a.size();i++){
    if(!isdigit(a[i-1])){
        if(a[i-1]!=' '&&isdigit(a[i])){
            putchar(' ');
        }
    }
    else if(isdigit(a[i-1])){
        if(a[i]!=' '&&!isdigit(a[i])){
            putchar(' ');
        }
    }
    putchar(a[i]);
}
return 0;

\(\text T2\)

Alice 与 Bob 希望玩一个游戏：他们首先在黑板上写下了 \(n\) 个整数 \(a_1, a_2, \cdots, a_n\) 。

然后 Alice 与 Bob 轮流行动，Alice 先手。

当轮到 Alice 行动时，Alice 需要选择黑板上的若干整数 (至少一个) ，并从黑板上擦除这些整数。

当轮到 Bob 行动时，Bob 需要选择黑板上的一个整数，并从黑板上擦除这个数。

当一名玩家行动后，若黑板上所有数均被擦除，游戏终止。

游戏的得分被定义为 Alice 每一轮行动中所有选择的数的和。Alice 希望最大化游戏的得分，Bob 希望最小化游戏的得分。

Alice 与 Bob 均绝顶聪明，他们会以最优的策略行动。你的任务是预测这个游戏的得分。

题解似乎很唐，题解复杂度是\(O(n^2+n \log n+n)\)无法通过此题但是它说复杂度是\(O(n)\)

直接对其排序，然后直接狂加不止即可，下面是我写的题解

\(\text T3\)

你是 \(\text B\) 学校的一名教师。你有 \(n\) 名学生，编号为 \(1, 2, \cdots, n\) 。在近期的一次测试中，编号为 \(i\) 的学生的得分为 \(a_i\) 。

你需要对学生们的得分抽样调查。一次抽样调查需要选出编号连续的若干名学生，我们称这一次抽样调查是准确的当且仅当选出的这些学生得分的平均数为整数。

你想知道在所有 \(\dfrac {n(n + 1)} 2\) 种选出编号连续的学生的抽样调查方案中，有多少种方案能使这一次抽样调查是准确的。

直接枚举平均数，然后用前缀和维护\(∑^r_{i=l}a_i−t\)，判断是否为\(0\)，接下来用pb_ds自带的 hash 维护方案数即可

signed a[N],n,s[N],ans;
int Luo=INF,TianYi=-INF;
gp_hash_table<int,int> Hash;
signed main(){
    fire();
    int n;FastI>>n;
    for(int i=1;i<=n;i++){
        FastI>>a[i];
        Luo=min(Luo,a[i]);
        TianYi=max(TianYi,a[i]);
    }
    for(int i=Luo;i<=TianYi;i++){
        Hash.clear();
        for(int j=1;j<=n;j++)
            s[j]=s[j-1]+a[i]-i;
        Hash[0]++;
        for(int j=1;j<=n;j++)
            Hash[s[j]]++;
        for(auto x:Hash){
            int YueZheng=x.second;
            ans+=(YueZheng*(YueZheng-1))/2;
        }
    }
    FastO<<ans;
}

\(\text{T}4\)

B 国是一个拥有 \(n\) 个城市的国家，\(n\) 个城市依次编号为 \(1, 2, \cdots, n\) 。B 国的首脑计划在国内修建 \(m\) 条城市间的单向道路。

如果从一个城市 \(x\) 出发，经过若干条道路能够到达城市 \(y\) ，我们就称 \(x\) 可达 \(y\) 。特殊的，我们认为每个城市都可达它本身。注意：\(x\) 可达 \(y\) 并不一定意味着 \(y\) 可达 \(x\) 。

对于一个城市的集合 \(S\) ，如果 \(S\) 中任意两个城市 \(u, v\) 都满足 \(u\) 可达 \(v\) 且 \(v\) 可达 \(u\) ，那么我们称 \(S\) 是互通的。特殊的，大小为 \(1\) 的集合总是互通的。

如果一个互通的城市集合 \(A\) 满足不存在另一个互通的城市集合 \(B\) 使得 \(A\) 是 \(B\) 的真子集，那么我们称 \(A\) 是一个城市群。

可以证明，对于任意的修建 \(m\) 条城市间的道路的方案，总能够将 \(n\) 个城市划分为若干个城市群，满足每个城市恰好属于一个城市群且每个城市群包含至少一个城市。

B 国的首脑要求这 \(n\) 个城市恰好被划分成 \(X\) 个城市群，他还有额外的 \(q\) 个限制 \((a_i, b_i)\) ，要求城市 \(a_i\) 与城市 \(b_i\) 属于同一个城市群。

你需要构造一种修建 \(m\) 条道路的方案满足首脑的要求，或者报告满足要求的方案不存在。

如果存在多种可能的方案，你可以输出任意一种。

注意：对于任意的两个城市 \(u, v\) ，从 \(u\) 到 \(v\) 的道路只能修建至多一条；你不能修建从一个城市到它本身的道路。

题面太长惹，不太想改，下面直接搬了题解呢