“传智杯”第六届河南省高校新生程序设计大赛决赛--题解

前言

本文章偏向于那些想要打ACM的新生的，设计到的算法知识比以往的多很多。如果单纯只想在蓝桥杯等一系列拿奖的话，可以尽力而为，如果是偏向打ACM的同学尽量全部掌握

传送门

点击传送

A:Hello World!

1.题目表述

2.思路讲解

其实对于这道题吧，我个人感觉它更加偏向于脑筋急转弯，真转不过来就可以直接放弃了，这里分享个链接华容道解法问题
然后至于算法方面就是线段树或者树状数组或者归并排序这些求逆序对问题的算法，如果是新手推荐先去学树状数组再搞这道题(个人认为树状数组简单点)

3.代码

#include <iostream>
#include <vector>
#include <cstring>

const int MAXN = 1e6 + 5;  

class Tree 
{
private:
    std::vector<int> tree;
    int n;
    
public:
    Tree(int size) 
    {
        n = size;
        tree.resize(n + 1, 0);
    }
    
    void update(int idx, int delta) 
    {
        while (idx <= n) 
        {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }
    
    int query(int idx) 
    {
        int sum = 0;
        while (idx > 0) 
        {
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
    
    int rangeQuery(int l, int r) 
    {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
    
    void clear() 
    {
        fill(tree.begin(), tree.end(), 0);
    }
};

int main() 
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int t;
    std::cin >> t;
    
    while (t--) 
    {
        int n;
        std::cin >> n;
        
        std::vector<int> nums;
        nums.reserve(n * n - 1);
        int blank_row = 0;  
        // 空白行号
        
        // 读取棋盘，记录非零数字和空白位置
        for (int i = 1; i <= n; i++) 
        {
            for (int j = 1; j <= n; j++) 
            {
                int x;
                std::cin >> x;
                if (x != 0) 
                {
                    nums.push_back(x);
                } 
                else 
                {
                    blank_row = i;  // 记录空白所在行（从1开始）
                }
            }
        }
        
        // 使用树状数组计算逆序数
        int max_val = n * n - 1;  // 数字最大为 n^2-1
        Tree bit(max_val);
        long long inv_count = 0;
        
        // 从后往前遍历，统计每个数字前面有多少比它小的数字（已出现的）
        for (int i = (int)nums.size() - 1; i >= 0; i--) 
        {
            int x = nums[i];
            inv_count += bit.query(x - 1);  // 比x小的数字个数
            bit.update(x, 1);
        }
        
        // 判断可解性
        if (n % 2 == 1) 
        {
            // 奇数阶：逆序数为偶数则有解
            std::cout << (inv_count % 2 == 0 ? "YES" : "NO") << '\n';
        } 
        else 
        {
            // 偶数阶：逆序数与空白行之和为偶数则有解
            if ((inv_count + blank_row) % 2 == 0) 
            {
                std::cout << "YES\n";
            } 
            else 
            {
                std::cout << "NO\n";
            }
        }
    }
    
    return 0;
}

如果不懂面向对象编程的话可以直接把class里面的东西移到外面就OK了

B:组合数

1.题目表述

2.思路讲解

这个和大家在高中期间学到的组合数学是一样的，直接用编程语言来模拟计算组合数的过程就行了
温馨提醒一下:C++的cin和cout的速度是比C语言的scanf和printf慢点的，所有我们开头加了两行神奇代码来提升速度，如果要进一步来提升速度的话推荐用快读和快写(请同学们自行了解)

3.代码

#include <iostream>
#include <vector>
using namespace std;

int C[20][20];

int main() 
{
	//神奇代码在这里(
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    // 预处理组合数
    for (int n = 0; n <= 18; n++) 
    {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; k++) 
        {
            C[n][k] = C[n-1][k-1] + C[n-1][k];
        }
    }
    
    int T;
    scanf("%d", &T);
    
    while (T--) 
    {
        int n, k;
        scanf("%d%d", &n, &k);
        
        if (k > n) 
        {
            printf("0\n");
        } 
        else 
        {
            printf("%d\n", C[n][k]);
        }
    }
    
    return 0;
}

C:好玩的数组

1.题目表述

2.思路讲解

这里简单介绍一下题目中出现的位运算相关:计算机中每个数据都是以二进制的形式表现出来的
按位于(&):当两个数相应的二进制位都为1，那么才为1
异或(^):和上面相反，只有当两个数相对应的一个二进制位为1，那么结果才为1
示例:001(1) & 101(5) = 001(1)       001(1) ^ 101（5） = 100（4）

题目中让我们求这个数组按位与的最大值，那么根据按位与的运算法则我们可以知道我们二进制层面答案的的每一位都一定会出现在这个这个数组的每一个元素中

而且此时我们还可以将一个数异或上x，那么我们此时可以开两个数组来记录异或上x的数组，一个来记录原数组。最后我们从最高位开始往最低位遍历，看看是不是数组内所有的数都有我们当前遍历到的那个1，最后再加上去就是答案了

3.代码

#include <iostream>
#include <algorithm>

int num[100005] , num1[100005];

void solve()
{
    int n , x;
    std::cin >> n >> x;
    for(int i = 1; i <= n; i++)
    {
        std::cin >> num[i];
        num1[i] = num[i] ^ x;
    }
    //我们这里使用贪心的方法来确保较高位
    int res = 0;
    bool judge = true;
    for(int i = 30; i >= 0; i--)
    {
        int temp = res | (1 << i);
        
        judge = true;

        for(int j = 1; j <= n; j++)
        {
            if(!judge) break;
            if(((num[j] & temp) != temp) && ((num1[j] & temp) != temp)) judge = false;
        }

        if(judge) res = temp;
    }

    std::cout << res << std::endl;
}

int main(int argc , const char *argv[])
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    
    while(T--) solve();
    return 0;
}

D:阵地扩张

1.题目表述

2.思路讲解

这个其实是一个非常模版的BFS算法，这里推荐上B站大学先学习这个算法，学完这道题就可以解决大部分了现场开学！！！

这里说下为什么用BFS，因为我们至少有一个"!"可以来感染其他区块，而我们占领的区块也可以去感染其他区块，所以这导致了我们有多个可以感染其他区块的母体，所以用BFS

3.代码

//一眼BFS
#include <iostream>
#include <cstring>
#include <queue>

const int N = 2e3 + 5;

char map[N][N];
bool st[N][N];
int Time[N * N] , n , m , T , ti = 0 , map_time[N][N];
int dir_x[4] = {1 , 0 , -1 , 0} , dir_y[4] = {0 , 1 , 0 , -1};

struct Node
{
    int x , y;
};
std::queue<Node>q;

void BFS()
{
    while(!q.empty())
    {
        ti++;
        int si = q.size();
        //这里里面再加个while循环的主要原因是为了记录这个时间的
        while(si--)
        {
            Node cur = q.front();
            q.pop();
            int x = cur.x , y = cur.y;

            for(int i = 0; i < 4; i++)
            {
                int xx = x + dir_x[i] , yy = y + dir_y[i];
                if(xx < 1 || xx > n || yy < 1 || yy > m || map[xx][yy] == '#' || st[xx][yy] == true) continue;

                if(map[xx][yy] == '.')
                {
                    q.push({xx , yy});
                    map_time[xx][yy] = ti;
                    st[xx][yy] = true;
                }
                else if(map[xx][yy] == '@')
                {
                    Time[ti]++;
                    q.push({xx , yy});
                    map_time[xx][yy] = ti;
                    st[xx][yy] = true;
                }
            }
        }
    }
}

void solve()
{
    for(int i = 0; i <= ti; i++) Time[i] += Time[i - 1];

    int op , x , y;
    std::cin >> op;

    if(op == 1)
    {
        std::cin >> x >> y;
        std::cout << map_time[x][y] << std::endl;
    }
    else if(op == 2)
    {
        std::cin >> x;
        std::cout << Time[x] << std::endl;
    }
}

int main(int argc , const char *argv[])
{
    memset(map_time , -1 , sizeof(map_time));
    std::cin >> n >> m >> T;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            std::cin >> map[i][j];
            
            if(map[i][j] == '!')
            {
                q.push({i , j});
                st[i][j] = true;
                map_time[i][j] = 0;
            }
        }
    }

    BFS();

    while(T--) solve();

    return 0;
}

这里给新来的同学们科普一下:queue指的是队列，一种先进先出且十分经典的数据结构，不会的话

点击即学

E:涂色游戏

1.题目表述

2.思路讲解

这是个偏向思维的题目这里给一个例子供大家思考
123456
114514
对于这个例子它输出的是NO，而为什么会输出NO呢？
我们这样来想对于a数组我们可以先转化成114456，然后我们发现，它可以继续转化成114556，但是它的4不可能在5之后，因为4要是出现了5之后的话，那么5肯定会被4感染
所以呢我们就可以得到一个关键信息:相对位置，只有两个数组的相对位置情况相同a数组才能转化为b数组，否则就不能
最后我们使用双指针的方式来模拟这个过程就可以了

3.代码

//CodeForce上有原题(bushi)
//好像取决于二者相对位置？
#include <iostream>
#include <cstring>

const int N = 1e6 + 5;
int a[N] , b[N];

void solve()
{
    //第一次写的太冗长了，这次简化一下
    int n;
    std::cin >> n;

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

    int i , j;
    for(int i = 1; i <= n; i++)
    {
        while(j <= n && b[i] != a[j]) j++;
    }

    if(j > n)
        std::cout << "NO" << std::endl;
    else
        std::cout << "YES" << std::endl;
}

int main(int argc , const char *argv[])
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T;
    std::cin >> T;

    while(T--) solve();

    return 0;
}

F:取石子

1.题目表述

2.思路讲解

这道题是经典的博弈论而且还是个纯思维
首先二者取石子的方程都符合(ax)^2 + ax + 1的格式，我们化简可得ax(ax + 1) + 1,那么对于前面的ax(ax + 1)它的结果肯定是偶数那么再此基础上加一所以它的结果肯定是奇数
那么对于第二者也一样取出石子的数量肯定也是奇数，那么相加的话就是偶数
所有结论就是:如果总数是奇数那么就是A赢了，不然就是B赢了

3.代码

//非常好的博弈论使我的大脑不断旋转
//oiiaiiio

#include <iostream>

void solve()
{
    int a , b , n , sum = 0 , st = 0;
    std::cin >> a >> b >> n;

    if(n % 2) std::cout << "Alice" << std::endl;
    else std::cout << "Bob" << std::endl;
}

int main(int argc , const char *argv[])
{
    int T;
    std::cin >> T;

    while(T--) solve();

    return 0;
}

G:洞天

1.题目表述

2.思路讲解

这个其实没什么好讲的，设计的算法是二维前缀和，题目也只是让我们求个正方形的面积现学链接

3.代码

//二维前缀和预处理正方形
#include <iostream>

typedef long long ll;
ll map[305][305];
ll pre[305][305];
//pre[i][j]表示为从(1,1)到(i,j)的距离

int main(int argc , const char *argv[])
{
    int n , m , ans = 0;
    std::cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            std::cin >> map[i][j];
            ans++;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            pre[i][j] = map[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        }
    }

    //众所周知，我们求一个正方形的长要它的四条边，但是此时我们这里有它的边长，所有我们只需要枚举它的左上角的坐标就OK了
    int max_k = (n > m) ? n : m;
    for(int k = 2; k <= max_k; k++)
    {
        for(int x1 = 1; x1 <= n - k + 1; x1++)
        {
            for(int y1 = 1; y1 <= m - k + 1; y1++)
            {
                int x2 = x1 + k - 1 , y2 = y1 + k - 1;
                long long sum = pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];

                if(sum % k == 0) ans++;
            }
        }
    }

    std::cout << ans << std::endl;
    return 0;
}

H: 奶龙VS水豚噜噜

1.题目表述

首先，我才是奶龙()

2.思路讲解

这里补充个知识点:只有两个数互质它们的gcd才为1

首先，对于答案我们分为三种情况
1:数组里面本来就有1，这样我们就不会配1了并且这样的结果肯定是最优的
2:我们能通过两个或以上的数配出来1，题目中2 3的gcd就可以配出来1，同时对于数组 5 10 2也可以配出来1，它们的区别是2 3只取了一次gcd，而5 10 2取了两次gcd，同理我们可以把这个方法延伸到数组的长度n
3:就是把所有的数组都配也配不出来1 例如 2 4 8

3.代码

//题目的大至要求是让我们通过互质(因为只有互质两个的最大公约数才为1)将所有数替换为1
//那么我们要做的就是看它们其中有几个互质的
//第一遍交错了，我们这里再思考一下
/*
    对于一开始原数组里面没有1但是我们又配出了一个1呢？
    例子:6 10 15
    这个配两次就可以配出一个1，题目中的只需要一次(造数据的重要性)
    所有我们这里就要根据这个例子来想
    如果我们追求的是最小的次数，那么我们应该要枚举整个区间找到那个最小的小区间最后加上n - 1就是答案了
*/


#include <iostream>

int a[2005];

int gcd(int a, int b) 
{
    return b == 0 ? a : gcd(b, a % b);
}

int main(int argc , const char *argv[])
{
    int n , one = 0;
    std::cin >> n;

    for(int i = 1; i <= n; i++) 
    {
        std::cin >> a[i];
        if(a[i] == 1) one++;
    }

    bool judge = false;
    int temp = gcd(a[1] , a[2]);
    for(int i = 3; i <= n; i++)
    {
        //这里求的是它们一起的最大公约数，如果它们其中一个小区间的gcd是1，那么这个大区间肯定也是1
        temp = gcd(temp , a[i]);
        if(temp == 1)
        {
            judge = true;
            break;
        }
    }

    //一般用作最大值这个0x3f
    int ans = 0x3f;
    
    //这里来枚举区间
    for(int i = 1; i < n; i++)
    {
        int cnt = a[i];
        for(int j = i + 1; j <= n; j++)
        {
            cnt = gcd(cnt , a[j]);
            if(cnt == 1)
            {
                int len = j - i + 1;
                ans = (len < ans) ? len : ans;
            }
        }
    }

    //这里再插一嘴，如果one存在的话，那么它一定是最优的
    //我们如果是多个区间的话执行的操作是j - i次，由于我们之前多加了个1，所有这里要多减去一个1，加上之前那个n - 1,所以是-2
    if(one)
        std::cout << n - one << std::endl;
    else if(judge)
        std::cout << ans + n - 2 << std::endl;
    else
        std::cout << "-1" << std::endl;

    return 0;
}

I:上京赶烤

1.题目表述

2.思路讲解

对于这道题如果我们一个一个减的话肯定会超时，用优先队列也会超(大冤种)，所以对于这道题的正解就是二分了
二分的话我们计算它所有鸭子的总和再除以3就是上界，然后再进行二分。我们二分的是我们可以考多少次烤鸭，每一次考需要k只烤鸭，我们把所有群落的烤鸭能提供贡献的数量加起来看看是不是比我们需要的结果大就可以了

3.代码

//一眼二分
#include <iostream>
#include <algorithm>

const int N = 2e5 + 5;
typedef long long ll;
ll num[N] , sum = 0;
int n , k;

bool check(ll mid)
{
	//这里说一下为什么要和mid取最小，因为如果一个烤鸭场是10000，那么它最多只能提供mid个
	//因为我们只举办了mid，就算每次烧烤的时候都有来自哪个部落的鸭子，最多也才mid个
    ll total = 0;
    for(int i = 1; i <= n; i++)
        total += std::min(num[i] , mid);

    return total >= k * mid;
}

int main(int argc , const char *argv[])
{
    std::cin >> n >> k;


    for(int i = 1; i <= n; i++)
    {
        std::cin >> num[i];
        sum += num[i];
    }

    ll l = 0 , r = sum / k , ans;
    //二分看看可以吃几次鸭子
    while(r >= l)
    {
        ll mid = (l + r) >> 1;
        if(check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }

    std::cout << ans << std::endl;
    return 0;
}

J:残酷的战场

1.题目表述

2.思路讲解

题目让我们求方案数，而方案数与最后一次炸的情况有关
示例：
2 2 2 3
2 1
1 1
2 2
输出
2
从这个示例我们可以得到上述结论，所以我们从后往前遍历，看看有多少次有效轰炸，如果轰炸的地区之前没有被标记过，那么它就是一个有效轰炸，最终方案数要乘以k，相反则是无效轰炸

3.代码

/*
    本题让我们求轰炸后的方案次数，那么我们就要考虑什么是有效轰炸
    假如我们轰炸的某一行或者某一列之前就已经被轰炸过了，那么我们再次轰炸就会造成无效轰炸，这样对我们的答案是没有贡献的
    所有我们可以通过开两个bool数组来表示该行或者该列是否被轰炸，如果有贡献的话，那么它的方案数就是之前的方案数*k
    这里计算有效答案需要从后面往前计算，我们这么做可以参考题目给出的第二个示例并在纸上进行模拟一下
    这里简单说说为什么是从后往前，因为我们每次计算的结果取决的都是最后的那次轰炸，所有从后往前可以避免无效轰炸
*/

#include <iostream>
#include <cstring>

const long long MOD = 998244353;
const int N = 1e3 + 5;
const int M = 2e5 + 5; 

bool row[M] , line[M];
int n , m , k , q , x[M] , y[M] , row_cnt = 0 , line_cnt = 0;
long long ans = 1;



int main(int argc , const char *argv[])
{
    memset(row , false , sizeof(row));
    memset(line , false , sizeof(line));

    std::cin >> n >> m >> k >> q;

    for(int i = 1; i <= q; i++)
    {
        std::cin >> x[i] >> y[i];
    }

    bool st = false;
    for(int i = q; i >= 1; i--)
    {
        st = false;
        int xx = x[i] , yy = y[i];

		//当它们其中一个达到条件了证明此时已经全部被轰炸过一次，没有黑色的地区，再怎么炸也不是有效贡献
        if(row_cnt == n || line_cnt == m) break;

        if(!row[xx])
        {
            row[xx] = true;
            st = true;
            row_cnt++;
        }
        if(!line[yy])
        {
            line[yy] = true;
            st = true;
            line_cnt++;
        }

        if(st)
        {
            ans *= k;
            ans %= MOD;
        }
    }

    std::cout << ans << std::endl;
    return 0;
}

总结

力竭了，后面写的有点不好请见谅