题解 | #校赛题解#

*******************

难度

$eazyeazy$：$A\mathrm{、}C\mathrm{、}F\mathrm{、}G\mathrm{、}JA、C、F、G、J$

$middlemiddle$：$B\mathrm{、}D\mathrm{、}E\mathrm{、}IB、D、E、I$

$hardhard$：$HH$

A前n项和

给你$nn$个数求$1+2+\mathrm{.}\mathrm{.}\mathrm{.}+n1+2+...+n$的和，答案是$n\ast (n+1)\mathrm{/}2n*(n+1)/2$，直接这样求时间复杂度为$O(1)O(1)$，你也可以for循环遍历求，时间复杂度为$O(n)O(n)$

代码如下

#include<bits/stdc++.h>

using namespace std;

int main() {
    
    int n;
    cin >> n;
    cout << n * (n + 1) / 2 << endl;
    
    return 0;
}

B前n项和（升级版）

第一行1枚硬币，第二行两枚硬币，第三行三枚硬币...，所以现在我们要求出$1+2+3+\mathrm{.}\mathrm{.}\mathrm{.}+k\le n1\; +\; 2\; +\; 3\; +...\; +\; k\; \backslash leq\; n$，即$k\ast (k+1)\mathrm{/}2\le nk\; *\; (k\; +\; 1)\; /\; 2\; \backslash leq\; n$，我们就想到二分$kk$来确定最大的满足条件的$kk$，如果最后那而在加上一行就好了，答案为$k+1k+1$，如果等于$nn$答案就是$kk$。这里$nn$的范围比较大，最大是$10^{16}10^\{16\}$所以要用long long来存储

时间复杂度$O(Tlogn)O(Tlogn)$

代码如下

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main()
{
    
    int T;
    cin >> T;
    
    while(T --) {
        i64 n;
        cin >> n;
        
        i64 l = 0, r = 1e9;
        while(l < r) {
            i64 mid = (l + r + 1) / 2;
            if(mid * (mid + 1) / 2 <= n) l = mid;
            else r = mid - 1;
        }
        
        if(l * (l + 1) / 2 < n) l ++;
        cout << l << endl;
    }
    
    return 0;
}

C博弈大师

很有意思的一道题，也是本场比较简单的题。$AliceAlice$先拿石子，每次能取不超过$\lceil \frac{n}{2}\rceil \backslash left\; \backslash lceil\; \backslash frac\{n\}\{2\}\; \backslash right\; \backslash rceil$的石子，我们考虑$n=1n=1$时，$BobBob$可以直接拿完。当$n!=1n!=1$时，因为每个人每次能取不超过$\lceil \frac{n}{2}\rceil \backslash left\; \backslash lceil\; \backslash frac\{n\}\{2\}\; \backslash right\; \backslash rceil$的石子，至少取1个石子，如果A能把石子拿的剩$\lceil \frac{n}{2}\rceil +1\backslash left\; \backslash lceil\; \backslash frac\{n\}\{2\}\; \backslash right\; \backslash rceil\; +\; 1$个那么B无论拿多少都拿不完，而且无论B拿多少A都能取得胜利，这个称之为A的必胜态。即当n - \left \lceil \frac{n}{2} \right \rceil - 1 \ge 1$$Bob就必胜，否则$AliceAlice$必胜，化简一下就是$n\ge n\backslash ge$4，所以$n=2,3n\; =\; 2,\; 3$时$AliceAlice$胜利，其余情况$BobBob$胜利。（数据量太大，cin会超时，scanf可以快速通过）

时间复杂度$O(T)O(T)$

代码如下

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

int main() {


    int T;
    cin >> T;
    while(T --) {

        i64 n;
        scanf("%lld", &n);

        if(n == 2 || n == 3) puts("Alice");
        else puts("Bob");

    }
    

    return 0;
}

D清洁工

动态规划经典入门题，数字三角形。也是我当初写的第一道动态规划题目

我们将整个楼倾斜成样例的样子，发现第$ii$层的数只有两个传递路径$[i-1,j-1][i\; -\; 1,\; j\; -\; 1]$和$[i-1,j][i\; -\; 1,\; j]$，另$f[i,j]f[i,\; j]$代表从第一层走到第$ii$行第$jj$列的最大值，可以表示为$f[i,j]=max(f[i-1,j],f[i-1,j-1])+a[i,j]f[i,\; j]\; =\; max(f[i\; -\; 1,\; j],\; f[i\; -\; 1,\; j\; -\; 1])\; +\; a[i,\; j]$，最好的答案是$max(f[n,j])max(f[n,\; j])$其中$j\in [1,n]j\; \backslash in\; [1,\; n]$

为了方便处理我们下标从1开始存储，这样不用处理边界情况

时间复杂度为$O(n^2)O(n^2)$

代码如下

#include<iostream>
using namespace std;

const int N=1010, INF=1e9;

int n;
int a[N][N];
int f[N][N];

int main(){
    
    cin>>n;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=i; ++j)
            cin>>a[i][j];
            
    f[1][1] = a[1][1];
    
    for(int i=2; i<=n; ++i)
        for(int j=1; j<=i; ++j)
            f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j]);
            
    int res=0;
    for(int i=1; i<=n; ++i) res=max(res, f[n][i]);
    
    cout<<res<<endl;
    
    return 0;
}

E龟兔赛跑

同样也是一道动态规划，感觉和上一题难度差不多。设$f[i]f[i]$为我们跑到第$ii$个黑洞所需要的最短时间，显然$f[i]=min(f[i-1],f[last\mathrm{\_}i])+1f[i]\; =\; min(f[i\; -\; 1],\; f[last\backslash \_i])\; +\; 1$，其中$last\mathrm{\_}ilast\backslash \_i$为到达跟第$ii$个黑洞数字相同，且小于$ii$的黑洞所需要的时间

举个例子1 2 3 1 4 5 1 9 2 11，对于第4个黑洞来说它的last_i就是第1个黑洞；对于第9个数字来说它的last_i就是第2个黑洞。

过程中使用一个$stst$数组来代表到达已经走过的数字为$xx$的时间

最后兔子到达重点的时间就是$s+f[n]s\; +\; f[n]$我们判断一下它和$mm$的大小即可

时间复杂度$O(n)O(n)$

代码如下

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int s, n, m;
int a[N], f[N], st[N];

int main() {

    cin >> s >> n >> m;

    for(int i = 1; i <= n; ++ i) cin >> a[i];

    for(int i = 1; i <= n; ++ i) {
        f[i] = f[i - 1] + 1;
        if(st[a[i]]) f[i] = min(f[i], st[a[i]] + 1);
        st[a[i]] = f[i];
    }


    if(s + f[n] >= m) puts("kai bai");
    else {
        cout << "zhe dou pao bu ying wo?" << ' ' << m - (s + f[n]) << '\n';
    }

    return 0;
}

F统计单词

这个题也肯简单，根据题意模拟即可为什么不往后看看呢emmm

时间复杂度$O(n\ast s\mathrm{.}length)O(n*s.length)$其中$nn$为单词数量，$s\mathrm{.}lengths.length$为单词长度的最大值

代码如下

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

vector<string> v[21];

void solve() {

    string s;
    int cnt = 0;
    while(cin >> s) {
        if(!v[s.size()].size()) cnt ++;
        v[s.size()].push_back(s);
    }
    
    cout << cnt << '\n';
    for(int i = 1; i <= 20; ++ i)
        if(v[i].size()) cout << i << ' ' << v[i].size() << '\n';
    
    for(int i = 20; i > 0; -- i)
        if(v[i].size()) {
            for(auto &x : v[i]) cout << x << ' ';
            break;
        }
    
}


int main() {

    int T = 1;

    while(T --) {
        solve();
    }

    return 0;
}

G排序

题如其名，排序即可。题目保证所有区间互不相交

时间复杂度$O(nlogn)O(nlogn)$

代码如下

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int a[N];

int main() {
    
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    
    while(m --) {
        int l, r;
        cin >> l >> r;
        sort(a + l, a + r + 1);
    }
    
    for(int i = 1; i <= n; ++ i) cout << a[i] << ' ';
    
    return 0;
}

H想买支笔的Bob

这个题是防AK题（确实也做到了），难度远高于其它9题。首先无论$xx$表现在哪个位置，我们都把它当作根节点即可，因为无序树的性质就是每一个结点都可以称为根节点，比如

首先需要对输入的结点进行去重，因为无论送多少外卖到一个地方都只需走一次。我们从$xx$开始dfs（深度优先搜索），记录以下几个信息$fafa$为结点$aa$的父结点，保存在$fafa$数组里。$dd$为结点$aa$到其父结点的距离，保存在$distdist$数组里，记录以下$diydiy$为$xx$即根结点到$yy$的距离，最后保存在$dydy$里。之后我们遍历外卖目的地，每次遍历一个点一层层往上爬，直到爬到根结点或者已经走过的结点，已经走过的结点在$stst$数组里标记为$truetrue$(这保证了我们对于每个结点最毒遍历一次)，每次加上对应的$distdist$即可。之后以相同的方式求以下$yy$到$min(x,\mathrm{最}\mathrm{近}\mathrm{已}\mathrm{经}\mathrm{遍}\mathrm{历}\mathrm{过}\mathrm{的}\mathrm{结}\mathrm{点}\mathrm{的}\mathrm{距}\mathrm{离})min(x,\; 最近已经遍历过的结点的距离)$，这些距离都加在$cntcnt$里，因为我们一来一回要走两次，所以$cntcnt$要乘2，但是最后走到$yy$又不需要回到$xx$，所以要减去一个$dydy$

时间复杂度$O(m)O(m)$

代码如下

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m, x, y, dy;
int h[N], e[N], ne[N], w[N], idx;
int f[N], dist[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int fa, int d, int diy) {
    f[u] = fa;
    dist[u] = d;

    if(u == y) dy = diy;
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u, w[i], diy + w[i]);
    }
}

void solve() {
    cin >> n >> m;
    vector<int> a(m, 0);
    for(int i = 0; i < m; ++ i) cin >> a[i];
    memset(h, -1, sizeof h);

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    for(int i = 1, a, b, c; i <= n - 1; ++ i) {
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    cin >> x >> y;
    dfs(x, -1, 0, 0);

    int cnt = 0;
    for(int i = 0; i < a.size(); ++ i) {
        int now = a[i];
        while(now != x && !st[now]) {
            st[now] = 1;
            cnt += dist[now];
            now = f[now];
        }
    }

    int now = y;
    while(now != x && !st[now]) {
        st[now] = 1;
        cnt += dist[now];
        now = f[now];
    }

    cout << 2 * cnt - dy << '\n';

}

int main() {

    solve();

    return 0;
}

I I am bigger

这个题可能是本场比赛最有趣的一道题啦，我们对$506240161506240161$分解质因数发现$506240161=7\ast 17\ast 19\ast 41\ast 43\ast 127506240161\; =\; 7*17*19*41*43*127$模数并不是一个质数，意味着对于所有大于等于127的输入，答案都是0。对于小于127的数我们直接计算阶乘即可，大于等于127的数直接看作0

时间复杂度$min(max(a,b),127)\ast Tmin(max(a,\; b),\; 127)\; *\; T$

代码如下

//127 * 43 * 41 * 19 * 17 * 7

#include<bits/stdc++.h>

using namespace std;

const int mod = 506240161;

using i64 = long long;

i64 f(int x){
    i64 sum = 1;
    for(int i = 1; i <= x; ++ i) sum = sum * i % mod;

    return sum;
}

int main() {

    int T;
    cin >> T;
    while(T --) {
        int a, b;
        cin >> a >> b;
        i64 sum1 = 0, sum2 = 0;

        if(a < 127) sum1 = f(a);
        if(b < 127) sum2 = f(b);

       // cout << sum1 << ' ' << sum2 << '\n';

        if(sum1 > sum2) puts("a is bigger");
        else if(sum1 < sum2) puts("b is bigger");
        else puts("no bigger");
    }


    return 0;
}

J国王的财富

这道题可能太靠后了，不过确实是签到中的签到。国王的财富就是所有财富的总和啊喂，直接把输入的财富值相加即可，连树边都可以不读

时间复杂度$O(n)O(n)$

代码如下

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {

    int n;
    cin >> n;
    
    i64 sum = 0, t;
    for(int i = 1; i <= n; ++ i) {
        cin >> t;
        sum += t;
    }

    cout << sum << endl;

    return 0;
}