比赛链接：https://ac.nowcoder.com/acm/contest/96419

密码：acmwantac

A.二分大佬历险记

题是很简单，大家应该都觉得能做，但是直接遍历进行查找一定会超时，题目给了序列严格递增，使用二分查找即可

说实话出题人真没想到大家都还没学二分查找，他说感觉自己有罪

C代码

#include <stdio.h>
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    int arr[n];
    for (int i = 0; i < n; ++i)//输入数据
        scanf("%d", &arr[i]);
    int a;
    while (q--)
    {
        scanf("%d", &a);
        int left = 0, right = n - 1;
        int mid;
        while (left <= right)//进行二分查找
        {
            mid = (left + right) / 2;
            if (arr[mid] > a)
                right = mid - 1;
            else if (arr[mid] < a)
                left = mid + 1;
            else
                break;
        }
        printf("%d\n", mid + 1);
    }
    return 0;
}

B.人机！

一道很简单的位运算

方法一

最朴素的方法，求出 x，y 两个数字的二进制，比对每一位是否相同，输出结果。十进制转二进制的方法大家的C语言老师都讲过了，我就不赘述了

#include <stdio.h>

int main()
{
    int x, y;
    scanf("%d%d", &x, &y);
    int arrx[32], arry[32];
    for (int i = 0; i < 32; ++i)
    {
        arrx[i] = (x % 2);
        x /= 2;
    }
    for (int i = 0; i < 32; ++i)
    {
        arry[i] = (y % 2);
        y /= 2;
    }
    int res = 0;
    for (int i = 0; i < 32; ++i)
    {
        if (arrx[i] != arry[i])
            res++;
    }
    printf("%d", res);
    return 0;
}

方法二：

异或运算符'^' 可以很轻易的求出两个数中不同的位数其原理是将两个数的二进制所有位数挨个比对，相同等于0，不同等于1；例如5 ^ 8 = 13。

$5 : (0 1 0 1)_2$

$8 : (1 0 0 0)_2$

得到 $13 : (1 1 0 1)_2$

因此本题仅需统计（x ^ y）中1的个数即可。

那么，怎么统计呢？

可以使用移位'>>'，每次移动一位后判断最后一位的数，若为1，结果+1。

C代码

#include <stdio.h>
int main()
{
    int x, y;
    scanf("%d%d", &x, &y);
    int tmp = x ^ y;
    int res = 0;
    while (tmp)
    {
        if (tmp & 1)
            res++;
        tmp >>= 1;
    }
    printf("%d", res);
    return 0;
}

方法三

使用内建函数，直接获取一个数的二进制中‘1’的数量，所以直接对(x ^ y)使用即可

#include <stdio.h>
int main()
{
    int x, y;
    scanf("%d%d", &x, &y);
    int tmp = x ^ y;
    printf("%d", __builtin_popcount(tmp));
    return 0;
}

C. Anon and Soyo

博弈论，巴什博奕

$n$ 在8以内的话，先手都可以一次拿完，获得胜利，当n等于9时，如样例说明，先手必输；那么，现在的问题就是当n>9时。

我们已经知道，剩余9张牌时，当前回合的人必定失败，这样的话先手可以考虑拿走牌之后将剩余的数量控制在9张卡牌，即控制为后手必败，当 $n \in [10,17]$ 时都可以实现。

而当 $n$ 等于18时，又回到了和 $n$ 等于9时类似的问题，即无论先手拿多少张，后手都可以将先手控制到9张，使之必败。

这样看来，实际问题就是每9张一个周期：

当 $n\in[1,9]$ 时，双方要考虑怎么让自己拿完之后剩余0张；

当 $n\in[10,18]$ 时，双方要考虑怎么让自己拿完之后剩余9张；

当 $n\in[19,27]$ 时，双方要考虑怎么让自己拿完之后剩余18张；

......

因此，后手胜利的条件仅有当n为9的倍数时，其余情况均为先手获胜

C代码

#include <stdio.h>
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        if (n % 9 == 0)
            printf("Anon Tokyo\n");
        else
            printf("CRYCHIC\n");
    }
    return 0;
}

D.大合照

如果一个人的眨眼间隔是 $i$ ，那么他眨眼会在第 $i$ 秒，第 $2i$ 秒，第 $3i$ 秒……

现在给出了 $n 2$ 个数代表每个人的眨眼间隔，那么所有人都没眨眼的第 $t$ 秒将不为给出的任何一个数的倍数。从2开始，求出符合条件的最小的数即可

C代码

#include <stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    n += 2;
    int peo[n];
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &peo[i]);
    }
    for (int i = 2; i < 1e9; ++i)
    {
        int flag = 1;
        for (int j = 0; j < n; ++j)
        {
            if (i % peo[j] == 0)
            {
                flag = 0;//若i是某个人眨眼间隔的倍数，将flag更新为0
                break;
            }
        }
        if (flag)//若某一次flag未被更新过，则当前的i为答案
        {
            printf("%d", i);
            return 0;//输出后结束程序
        }
    }
    return 0;
}

E.环

使用并查集，原理就不讲了，不会的可以去学一学

我的思路是求出点的数量、联通块的数量、边的数量；若点-边=联通块，则无环，否则有环。

原理：对于一个联通块，若无环，则边 = 点 - 1，而对于多个联通块，每多一个联通块边就会少一个

哥们不会用C写这道题，对不住

C++代码

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

unordered_map<int, int> mp;
int Find(int x)
{
    return mp[x] == x ? x : mp[x] = Find(mp[x]);
}

void Akira()
{
    int n;
    cin >> n;
    int a, b;
    unordered_set<int> ss;
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        ss.insert(a);
        ss.insert(b);
        if (mp.find(a) == mp.end())
            mp[a] = a;
        if (mp.find(b) == mp.end())
            mp[b] = b;
        mp[Find(b)] = Find(a);
    }
    unordered_set<int> s;
    for (auto i : mp)
    {
        s.insert(Find(i.second));
    }
    if (s.size() + n == ss.size())
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll Kita = 1;
    // cin >> Kita;
    while (Kita--)
    {
        Akira();
    }
    return 0;
}

F.右三角？

问 $n$ 能否用两个非零整数 $i、j$ 的平方和表示，若能，又问 $i、j、\sqrt n$ 能否构成“神奇的直角三角形”，但实际上这时 $i、j、\sqrt n$ 已经符合勾股定理，所以一定会是一个直角三角形，因此只需判断 $\sqrt n$ 是否为整数即可。

方法一

朴素的两层循环遍历，寻找符合条件的 $i$ 和 $j$ ，要注意，循环的终止条件必须写 $\sqrt n$ ，否则会超时。

若未找到符合条件的 $i$ 和 $j$ ，直接输出那一串拼音；

若找到了，进一步判断 $\sqrt n$ 是否为整数

C代码

#include <stdio.h>
#include <math.h>
int main()
{
    int n;
    scanf("%d", &n);
    int i = 1, j;
    int flag = 0;
    for (; i * i <= n; ++i)
    {
        flag = 0;
        for (j = i; j * j <= n; ++j)
        {
            if (i * i + j * j == n)
            {
                flag = 1;
                break;
            }
        }
        if (flag)
            break;
    }
    if (!flag)
    {
        printf("e e e,xiong di men,hai you gao shu zuo ye");
        return 0;
    }
    if ((int)sqrt(n) * (int)sqrt(n) == n)
    {
        printf("e e e,xiong di men,zhong yu chi shang huo guo ji la");
        return 0;
    }
    else
        printf("e e e,xiong di men,ye shi he shang po fang shui la");
    return 0;
}

方法二

双指针

本题的标准解法。

如果数据给的再大一些，朴素的方法一便会超时。

令 $i$ = $1$ , $j$ = $\lfloor \sqrt n \rfloor$ (向下取整)，判断 $i^2$ + $j^2$ 与 $n$ 的大小关系：

若 $i^2$ + $j^2 < n$ ，移动左指针 $i$ ，

若 $i^2$ + $j^2 > n$ ，移动右指针 $j$ ，

若 $i^2$ + $j^2$ = $n$ ，跳出循环，当前的 $i、j$ 便是所求

当 $i > j$ 时，说明不存在符合条件的 $i、j$ 使得 $i^2$ + $j^2$ = $n$ 。

C代码

#include <stdio.h>
#include <math.h>
int main()
{
    int n;
    scanf("%d", &n);
    int i = 0, j = (int)sqrt(n);
    while(i <= j)
    {
        int tmp = i * i + j * j;
        if(tmp > n)
            j--;//移动右指针
        else if(tmp < n)
            i++;//移动左指针
        else
            break;
    }

    if(i > j)//不存在
    {
        printf("e e e,xiong di men,hai you gao shu zuo ye");
    
    }
    else{
        if((int)sqrt(n) == sqrt(n))//可构成神气的...
            printf("e e e,xiong di men,zhong yu chi shang huo guo ji la");
        else//不可构成
            printf("e e e,xiong di men,ye shi he shang po fang shui la");
    }
    return 0;
}

G.赶车

将时间全部都转换为分钟会简单很多，例如将样例一的开始时间10:58转换为 10 * 60 + 58 = 658，其它也都这样转换，那么这道题就很容易了。

特别注意时间跨越了24点的情况

C代码

#include <stdio.h>
#include <math.h>
int main()
{
    int a, b;
    scanf("%d:%d", &a, &b);
    int start = a * 60 + b;//将开始时间转为分钟
    scanf("%d:%d", &a, &b);
    int end = a * 60 + b;//结束时间转换

    int n;//要做的事数量
    scanf("%d", &n);
    int sum = 0;//要做的所有事耗费的总时间
    while(n--)
    {
        scanf("%d:%d", &a, &b);
        sum += (a * 60 + b);
    }

    int now = start + sum;
    now %= (24 * 60);//处理时间跨越了24点的情况
    if(now > end)
        printf("NO");
    else{
        printf("YES\n");
        int hh = now / 60;//当前小时
        int mm = now % 60;//当前分钟
        printf("%02d:%02d", hh, mm);
    }
    return 0;
}

H.美丽的零元购

一个简单的模拟，小学时我们就学过，总价 = 单价 * 数量。

现在总价已固定，想让数量最多，肯定要单价最小。

因此，将数据均输入数组后，按从小到大排序，拿单价小的一直拿到总价超过界限即可。

注意边界条件的处理

C代码

#include <stdio.h>
#include <math.h>
int main()
{
    int n, maxx;
    scanf("%d%d", &n, &maxx);
    int goods[n];
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &goods[i]);
    }

    for (int i = 0; i < n; ++i) // 冒泡排序
    {
        for (int j = i; j < n; ++j)
        {
            if (goods[j] < goods[i])
            {
                int t = goods[i];
                goods[i] = goods[j];
                goods[j] = t;
            }
        }
    }
//可以了解一下C中的qsort或c++中的sort函数，更优
    int now = 0, count = 0;
    for (int i = 0; i < n; ++i)
    {
        if (now >= maxx)
        {
            count--;
            break;
        }
        else
        {
            now += goods[i];
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

I.校门外的数

校赛时出过一道一样的，样例数据都没改，仅仅是修改了题面，目的是看看大家校赛后有没有补题

方法一

直接按题意模拟，创一个 $L 1$ 长度的数组(包含0~m)，代表马路，将数组中所有地方先赋值为1，接下来输入多组 $l、r$ ，仅需把数组中的 $[l,r]$ 区间改为0即可，最后统计数组中剩余1的数量，作为答案输出。

C代码

#include <stdio.h>
#include <math.h>
int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    int road[m + 1];
    for (int i = 0; i <= m; ++i)
        road[i] = 1;//初始化全为1

    int l, r;
    while (n--)
    {
        scanf("%d%d", &l, &r);
        for (int i = l; i <= r; ++i)
        {
            road[i] = 0;//将要建地铁的地方标位0
        }
    }
    int res = 0;

    for (int i = 0; i <= m; ++i)//统计1的数量
        if (road[i] == 1)
            res++;

    printf("%d", res);
    return 0;
}

方法二

差分本题的正解

使用一个数组road，初始化为全1，表示每个位置都有树。遍历输入的 $M$ 个区间，使用差分标记表示从起始点到终止点的树需要移除。根据差分数组，计算移除后剩余的树。

C代码

#include <stdio.h>
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    int road[10001];  // 差分数组
    // 初始化差分数组
    for (int i = 0; i <= m; i++) {
        road[i] = 0;
    }
    // 读入区域并应用差分操作
    for (int i = 0; i < n; i++) {
        int start, end;
        scanf("%d %d", &start, &end);
        road[start]--;  //起始点减一
        if (end + 1 <= m) {
            road[end + 1]++;//终止点加一
        }
    }
    // 利用差分数组计算剩余树
    int count = 0, current = 1;
    for (int i = 0; i <= m; i++) {
        current += road[i];
        if (current > 0) { 
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

J.国民的请求

让奇数*偶数最大，实际上就是在输入的数中找出最大的奇数、最大的偶数，输出乘积便可。这道题其实连数组都不需要，只需要维护两个最大值

注意：如果使用数组储存数据并进行冒泡排序是会超时的！！！

C代码

#include <stdio.h>

int max(int x, int y)
{
    if(x >= y)
        return x;
    else
        return y;
}

int main() {
    int n;
    int odd = -1, even = -1;
    scanf("%d", &n);
    int tmp;
    while(n--)
    {
        scanf("%d", &tmp);
        if(tmp % 2 == 0)//若输入的为偶数
            even = max(even, tmp);//若比当前最大偶数还大，则更新
        else//奇数与偶数同理
            odd = max(odd, tmp);
    }
    int res = odd * even;
    if(res < 0)//如果奇数或偶数未出现过
        printf("-1");
    else
        printf("%d", res);
    return 0;
}

K.艾登提提

二维字符串问题，按照题意进行处理即可

从最后一行往前遍历，如果某一行出现了两个及以上的‘#’，输出对应信息并结束程序。遍历的同时将每一行的‘#’所在位置储存在数组中，若符合条件依次输出。

C代码

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    char arr[n][4];
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", arr[i]);
    }

    int res[n], index = 0;
    for (int i = n - 1; i >= 0; --i)
    {
        int count = 0;//记录本行出现的'#'
        for (int j = 0; j < 4; ++j)
        {
            if (arr[i][j] == '#')
            {
                if (count != 0)//若本行已经出现过了'#'
                {
                    printf("IDENTITY");
                    return 0;
                }
                count++;
                res[index++] = j + 1;
                //存到结果数组中
                //每存一个index就会自增一次
                //可以学习一下这种巧妙的写法
            }
        }
    }

    printf("FULL COMBO\n");
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", res[i]);
    }
    return 0;
}

L.日本到底有没有罗森

本题涉及到算法了，我是真的不会用C写了，见谅

不细讲了，想学的可以先去学习一下bfs或dfs

出题人太邪恶了，竟然出这种题

方法一

DFS c++代码

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

void solve()
{
    ll m, n;
    cin >> n >> m;
    ll sta[2] = {0, 0};
    vector<string> arr(n);
    for (ll i = 0; i < n; ++i)
    {
        cin >> arr[i];
        for (ll j = 0; j < m; ++j)
        {
            if (arr[i][j] == 'S')
                sta[0] = i, sta[1] = j;
        }
    }
    vector<vector<int>> v(n, vector<int>(m, 0));
    auto dfs = [&](auto &&dfs, ll x, ll y)
    {
        if (arr[x][y] == 'E')
        {
            cout << "Yes";
            exit(0);
            return;
        }
        else
        {
            // 向右
            if (x >= 0 && x < n && y + 1 >= 0 && y + 1 < m && (arr[x][y + 1] == '.' || arr[x][y + 1] == 'E') && !v[x][y + 1])
            {
                v[x][y + 1] = 1;
                dfs(dfs, x, y + 1);
                v[x][y + 1] = 0;
            }

            // 向下
            if (x + 1 >= 0 && x + 1 < n && y >= 0 && y < m && (arr[x + 1][y] == '.' || arr[x + 1][y] == 'E') && !v[x + 1][y])
            {
                v[x + 1][y] = 1;
                dfs(dfs, x + 1, y);
                v[x + 1][y] = 0;
            }

            // 向左
            if (x >= 0 && x < n && y - 1 >= 0 && y - 1 < m && (arr[x][y - 1] == '.' || arr[x][y - 1] == 'E') && !v[x][y - 1])
            {
                v[x][y - 1] = 1;
                dfs(dfs, x, y - 1);
                v[x][y - 1] = 0;
            }

            // 向上
            if (x - 1 >= 0 && x - 1 < n && y >= 0 && y < m && (arr[x - 1][y] == '.' || arr[x - 1][y] == 'E') && !v[x - 1][y])
            {
                v[x - 1][y] = 1;
                dfs(dfs, x - 1, y);
                v[x - 1][y] = 0;
            }
        }
        return;
    };

    dfs(dfs, sta[0], sta[1]);
    cout << "No";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

方法二

BFS c++代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef struct loc
{
    ll x, y;
} loc;

void solve()
{
    ll m, n;
    cin >> n >> m;
    ll sta[2] = {0, 0};
    vector<vector<char>> arr(n, vector<char>(m));
    for (ll i = 0; i < n; ++i)
    {
        for (ll j = 0; j < m; ++j)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 'S')
                sta[0] = i, sta[1] = j;
        }
    }
    queue<loc> q;
    ll dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
    q.push({sta[0], sta[1]});
    while (!q.empty())
    {
        loc t = q.front();
        q.pop();
        for (ll i = 0; i < 4; ++i)
        {
            ll xx = t.x + dx[i], yy = t.y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && (arr[xx][yy] == '.' || arr[xx][yy] == 'E'))
            {
                if (arr[xx][yy] == 'E')
                {
                    cout << "Yes";
                    return;
                }
                q.push({xx, yy});
                arr[xx][yy] = 'W';
            }
        }
    }
    cout << "No";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

M.完美字符串

原谅我，这个我也不会用C写

方法一

按照题意模拟

每次会删掉2个字符，所以最多就会循环n/2遍，遇到数字前有字母的情况，就把这两个字符删除，最后清理掉字符串开头的数字

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
void Akira()
{
    string s;
    int qqqq;
    cin >> qqqq;
    cin >> s;
    int n = s.size() / 2 + 1;
    while (n--)
    {
        for (int i = 1; i < s.size(); ++i)
        {
            if (s[i] >= '0' && s[i] <= '9' && s[i - 1] >= 'a' && s[i - 1] <= 'z')
            {
                s[i] = '.';
                s[i - 1] = '.';
            }
            string t;
            for (auto j : s)
                if (j != '.')
                    t += j;
            s = t;
        }
    }
    int i = 0;
    for (; i < s.size(); ++i)
    {
        if (s[i] >= 'a' && s[i] <= 'z')
            break;
    }

    s = s.substr(i);
    if (s.empty())
        s = "-1";
    cout << s;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll Kita = 1;
    // cin >> Kita;
    while (Kita--)
    {
        Akira();
    }
    return 0;
}

方法二

栈将整个字符串按顺序入栈，如果栈顶为字母且下一个入栈的为数字，则pop。遍历字符串完成后，将栈中元素依次pop，合成字符串，最后清除字符串开头的数字。

c++代码

#include <bits/stdc++.h>
using namespace std;
void Akira()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    stack<char> ss;
    for (auto i : s)
    {
        if (ss.empty())
            ss.push(i);
        else if (i >= '0' && i <= '9' && ss.top() >= 'a' && ss.top() <= 'z')
            ss.pop();
        else
            ss.push(i);
    }
    string t;
    while (!ss.empty())
    {
        char tmp = ss.top();
        t = tmp + t;
        ss.pop();
    }

    int i = 0;
    for (; i < t.size(); ++i)
    {
        if (t[i] >= 'a' && t[i] <= 'z')
            break;
    }

    t = t.substr(i);
    if (t.empty())
        t = "-1";
    cout << t;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll Kita = 1;
    // cin >> Kita;
    while (Kita--)
    {
        Akira();
    }
    return 0;
}

大连民族大学ACM工作室2024级纳新考核赛题解