2024.10.20NISA百团题目题解

三道挺有意思的小题目，记录一下

第一题

题目描述：说反话

题解：

翻转字符串即可（大雾），时间复杂度是严格线性（大大雾）

第二题

题目描述：挑战者选择16/17/18张卡片和先/后手，每方每次可以掀开1/2/3张卡片；挑战者的目标是让敌手掀开最后一张卡牌

题解：

如果敌手掀开最后一张牌（即达成挑战目标），则必然最终只剩一张牌（如果剩余的牌数多于1张，则敌手可以掀开一张，这时挑战者并不会达到目标）

为了使敌手掀开最后一张牌，则只需保留一张牌，即保证挑战者掀开牌之后，剩余的牌数为4k+1即可，其中k为非负整数

在以上情况下，每一轮（指双方操作）后掀开四张卡牌即可保证挑战者一定获胜

看不懂？直接运行以下代码体验一下吧

直接使用devcpp运行以下代码即可，记得拓展名是cpp哦

#include<iostream>
using namespace std;
int n;

bool check( int x ){
    if( x == 1 || x == 2 || x == 3 ) return 1;
    cout << "请输入1/2/3哦，不要输入别的数字喵" << endl;
    return 0;
}
signed main()
{
    INIT:;
    cout << "请输入总牌数：(n=16/17/18)";
    RST:;
    cin >> n;
    if( n != 16 && n != 17 && n != 18 ){
        cout << "输入的数据不合法，请重新输入" << endl;
        cout << "-----------" << endl;
        goto INIT;
    }
    if( n == 17 ){
        cout << "你长得好看，让你先手" << endl;
        N17:;
        int sum = 17 , a;
        while( sum!=1 ){
            cout << "-----------" << endl;
            cout << "请输入你掀开的数量：";
            cin >> a;
            if( !check(a) ) continue;
            cout << "好的，这次我掀开的数量是：" << 4-a << endl;
            sum -= 4;
            cout << "现在剩下未掀开牌的数量是：" << sum << endl;
        }
    }
    else if( n == 16 ){
        cout << "我长得漂亮，让我先手" << endl;
        cout << "我掀开的数量是：" << 3 << endl;
        cout << "现在剩下未掀开牌的数量是：" << 13 << endl;
        int sum = 13 , a;
        while( sum!=1 ){
            cout << "-----------" << endl;
            cout << "请输入你掀开的数量：";
            cin >> a;
            if( !check(a) ) continue;
            cout << "好的，我掀开的数量是：" << 4-a << endl;
            sum -= 4;
            cout << "现在剩下未掀开牌的数量是：" << sum << endl;
        }
    }
    else{
        cout << "我长得漂亮，让我先手" << endl;
        cout << "我掀开的数量是：" << 1 << endl;
        cout << "现在剩下未掀开牌的数量是：" << 17 << endl;
        goto N17;
    }
    cout << "现在只剩下一张牌了，到你掀了，你失败了（嘻嘻）" << endl;
    cout << "再来一把？这次n是多少你说了算，但是先后手···嘿嘿······" << endl;
    goto RST;
    return 0;
}

结论：

17张时候，挑战者后手；16或18张时，挑战者先手

具体策略如上，此题解仅讨论必胜情况

第三题

问题描述：数桥问题

题解：

其实这个时间复杂度，（在保证有解的情况下）枚举一下大概率也能出来了，除非因为没有橡皮导致图越画越乱最终看不清楚（

使用贪心思想时间复杂度为O(N*M)，其中N是点的数量，M是每个点尝试的边的数量

ai给出的贪心代码，仅供参考

#include <iostream>
#include <vector>

using namespace std;

// 定义点结构
struct Point {
    int x, y; // 点的坐标
    int degree; // 点的边权（需要连接的边数）
};

// 定义一个方向数组，表示右、下
int dx[] = {1, 0}; // 横向和竖向（x+1, y）表示右边，(x, y+1)表示下方
int dy[] = {0, 1};

// 检查是否可以在(x1, y1)和(x2, y2)之间连接边
bool canConnect(int x1, int y1, int x2, int y2, vector<vector<int>>& grid) {
    // 确保(x2, y2)在图的范围内，且没有交叉边
    if (x2 < 0 || y2 < 0 || x2 >= grid.size() || y2 >= grid[0].size()) return false;
    if (grid[x1][y1] || grid[x2][y2]) return false;
    return true;
}

// 主函数：连接点的边，确保边不交叉
void connectPoints(vector<Point>& points, int n, int m) {
    // 创建一个网格表示是否有边（或点）
    vector<vector<int>> grid(n, vector<int>(m, 0));

    // 遍历所有点
    for (auto& p : points) {
        int x = p.x, y = p.y, degree = p.degree;
        grid[x][y] = 1; // 将该点标记为存在
        
        // 尝试为该点连接degree条边
        for (int i = 0; i < degree; ++i) {
            for (int d = 0; d < 2; ++d) { // 遍历两个方向（右和下）
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (canConnect(x, y, nx, ny, grid)) {
                    grid[nx][ny] = 1; // 连接边并标记
                    break; // 连接成功，退出当前方向的尝试
                }
            }
        }
    }
}

int main() {
    int n = 5, m = 5; // 网格大小
    vector<Point> points = {
        {0, 0, 2}, // (x, y, 边权)
        {2, 1, 1},
        {3, 4, 3},
    };

    connectPoints(points, n, m);

    return 0;
}