赛前把D和F的顺序调了一下，D题时限加了1秒（原先是1秒），看来这个决定非常正确。A题这种题在算法竞赛是非常常见的，是我们需要学会的技能。C题题意可能略复杂一点，但是出题人都有在后台实时回复。F 题其实特判并不多，可以参考题解和代码最短的正确提交，总的来说结果还是符合预期的，希望大家玩的开心！

A 矩阵快速幂签到

归纳法：设 ，则

因此数列是公差为 的等差数列，答案就是。在本题中，答案就是 ，因此取不取模都行。

时间复杂度为 ，如果使用矩阵快速幂，时间复杂度为 。

经过测试，使用循环也可以通过本题。善于观察样例，或者手动造出前几项，或者对数据范围比较敏感的选手应该很快就能猜出正确结论。

#include<bits/stdc++.h>
int n;
int main(){
    scanf("%d",&n);
    printf("%d\n", 1 + n);
    return 0;
}

B 第一次放学

采用贪心策略。由于想知道最多有多少人属于同一个班级，因此我们假设人数最多的那个班级尽可能的少走人，而让其他班级先走。因此，统计每个班的人数，只保留人数最多的班级，优先假设跑出去的都是其他班级的人，如果还不够 个人，再从这个班里减。

总时间复杂度为输入的时间复杂度，为 。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m,k;
int a[maxn];
int main(){
    scanf("%d %d %d",&n,&m,&k);
    int mx = 0;
    for(int i = 1; i <= n; i++){
        int x;
        scanf("%d",&x);
        a[x]++;
        if(a[x] > mx) mx = a[x];
    }
    if(n - k < mx) mx = n - k;
    printf("%d\n",mx);
    return 0;
}

C 又放学辣（简单）

见D题。

D 又放学辣（进阶）

首先容易想到一个暴力的做法，枚举拖堂的班级，然后再枚举答案，然后扫描剩下的班级人数，贪心的去掉大于答案的人数，再看离开的人是不是可能为 个。这样做的时间复杂度为 ，足以通过简单版本。然后发现答案满足单调性，这样就得到了一个时间复杂度为 的做法。继续优化，发现”去掉每个班级大于答案的人数”这一步可以用排序、前缀和和二分来优化，这样时间复杂度就降为了 ，常数小一些可以通过进阶版本。

如果我们按照每个班级的人数排序，按班级人数枚举拖堂的班级，那么答案依然是单调的，可以通过维护当前答案、最少离开的人数以及相关信息来 求出答案。总时间复杂度为排序的时间复杂度，为 ，已经足够通过本题。如果使用桶排序，总时间复杂度可降为 ，只是实现起来会有亿点点细节，可能比较浪费时间。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n,m,k;
int a[maxn];
pair<int,int>p[maxn];
vector<int>vc[maxn];
int main(){
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 1; i <= n; i++){
        int x;
        scanf("%d",&x);
        a[x]++;
    }
    for(int i = 1; i <= m; i++) {
        vc[a[i]].push_back(i);
    }
    int cnt = 0;
    for(int i = 0; i <= n; i++){
        for(int j:vc[i]) p[++cnt] = {i,j};
    }
    int pos = m;
    for(int i = m; i >= 1; i--){
        if(n - p[i].first < k) {a[p[i].second] = -1;pos = i - 1;}
        else {pos = i;break;}
    }
    int v = p[m].first,run = 0;
    int i = m + 1;
    int pv,prun,pi;
    int ext = 0;
    while(run - ext <= k){
        pv = v;
        pi = i;
        prun = run - ext;
        v--;
        if(v < 0) break;
        while(i > 1 && p[i - 1].first > v) i--;
        run += m - i + 1;
        if(p[pos].first > v) ext = p[pos].first - v;
    }
    a[p[pos].second] = pv;
    for(int i = pos - 1; i >= 1; i--){
        if(p[i].first > pv) prun -= p[i].first - pv;
        if(p[i + 1].first > pv) prun += p[i + 1].first - pv;
        while(prun > k){
            pv++;
            prun -= (m - pi + 1);
            if(i >= pi) prun++;
            while(pi <= m && p[pi].first == pv) pi++;
        }
        a[p[i].second] = pv;
    }
    for(int i = 1; i <= m; i++) printf("%d%c",a[i],i == m ? '\n' : ' ');
    return 0;
}

E 一种因子游戏

由于两个人都知道对方手里的牌，且都足够聪明，因此Bob想赢就必须考虑好如何安排出牌顺序使得每次出的牌上的数字都可以与Alice出的牌互质。

因此，如果将Alice手中的牌与Bob手中的牌中牌上数字数字互质的牌连边，那么问题就等价于是否存在一个完美匹配。按照上述方式进行建边，使用匈牙利算法求出最大匹配，根据最大匹配是否等于 即可判断Bob是否能获胜。

总时间复杂度为。

#include<bits/stdc++.h>
const int maxn = 500 + 5;
using namespace std;
int n,m,x;
int lk[maxn][maxn];
int g[maxn],us[maxn];
int a[maxn],b[maxn];
void init() {
    memset(lk,0,sizeof(lk));
    memset(g,0,sizeof(g));
}
bool find(int x) {
    for (int i = 1; i <= n; i++) {
        if(lk[x][i] && !us[i]) {
            us[i] = 1;
            if(g[i] == 0 || find(g[i])) {
                g[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    init();
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&x);
        for(int j = 1; j <= n; j++) if(__gcd(a[j],x) == 1) lk[j][i] = 1;
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        memset(us,0,sizeof(us));
        if(find(i)) sum++;
    }
    printf("%s\n",sum == n?"Bob":"Alice");
    return 0;
}

F 一种异或游戏

首先，一个比较明显的结论是将 Alice 或 Bob 手中所有的牌异或 ，则 Bob 获胜的判定条件等价于两人打出的牌上的数字相同。以下假设已经将 Alice 的所有手牌都已经异或 。

假设 Bob 最终获胜，且获胜回合 Bob 打出的牌上的数字为 。定义 Alice 手中剩下的某张牌若与Bob手中剩下的某张牌数字相同，则称这张牌被 Bob 的手牌覆盖。则 Bob 在该回合获胜等价于：

Bob 获胜的回合开始时，Bob 的剩余手牌能够覆盖 Alice 的全部剩余手牌，且两人手牌都至少还剩两张。

证明：覆盖全部手牌显然，Alice 手牌如果剩一张就直接获胜了，Bob 如果剩一张按照判定规则还是 Alice 获胜。

因此，Bob 想获胜，就要尽可能覆盖 Alice 的手牌。若 Bob 手牌中的一张牌能覆盖 Alice 手牌中的至少一张牌，那么这张牌就是有效的（有效是指可能为 Bob 带来胜利，相同数字只有一张牌有效）。假设 Bob 有 张有效牌，这些牌覆盖了 Alice 的 张手牌，首先不考虑最后一轮不判定的情况，则可以得出 Bob 获胜等价于：

1、

2、 （条件一隐含）

3、

接下来再考虑最后一轮不判定的情况，则由上述结论，Bob 获胜等价于以下条件必须全部满足：

1、

2、 （条件一隐含）

3、 时，

4、 时，

统计 ， 然后直接判断即可。另外注意异或 以后数字可能超过 。

总时间复杂度为。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n,m,k,x;
int c[maxn];
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= n; i++){
        scanf("%d",&x);
        x ^= k;
        if(x < maxn) c[x]++;
    }
    int sum = 0,tot = 0;
    for(int i = 1; i <= m; i++){
        scanf("%d",&x);
        if(c[x] > 0){
            tot++;
            sum += c[x];
            c[x] = 0;
        }
    }
    int fg = 0;
    if(sum > 1 && m - max(tot,2) >= n - sum) fg = 1;
    if(fg) puts("Bob");
    else puts("Alice");
}
int main(){
    solve();
    return 0;
}