EOJ刷题记录&题解第一弹

2957. 统计不同的最简真分数的个数

思路

学习set迭代器的使用

代码

//
// Created by HUAWEI on 2025/3/6.
//
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

const int N = 1010;
set<int> a;

int gcd(int a, int b)
{
    if(b == 0)  return a;
    else return gcd(b, a % b);
}

int main()
{
    int T;
    cin >> T;

    for(int count = 0; count < T; count ++)
    {
        a.clear();
        int n;
        cin >> n;

        for(int i = 0; i < n; i ++) {
            int num;
            cin >> num;
            a.insert(num);
        }

        int res = 0;
        for(auto i = a.begin(); i != a.end(); i ++)
            for(auto j = next(i); j != a.end(); j ++)
            {
                int k = *i, m = *j;
                if(k < m && gcd(k, m) == 1)
                    res ++;
            }

        cout << "case #" << count << ":\n" << res << "\n";

    }
}

2958. 求上升子序列和的最大值

思路

最长上升子序列dp问题，卡在了初始化上。

什么情况下一定有上升子序列？数本身构成的长度为1的子序列

代码

//
// Created by HUAWEI on 2025/3/6.
//
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010;
int a[N];
int f[N];
int n, T;

int main()
{
    cin >> T;

    for(int count = 0; count < T; count ++)
    {
        memset(a, 0, sizeof a);
        memset(f, 0, sizeof f);

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

        for(int i = 1; i <= n; i ++)    f[i] = a[i];
        for(int i = 2; i <= n; i ++)
            for(int j = 1; j < i; j ++)
            {
                if(a[j] < a[i])
                    f[i] = max(f[i], f[j] + a[i]);
            }

        int ans = -1;
        for(int i = 1; i <= n; i ++)
            ans = max(ans, f[i]);
        printf("case #%d:\n%d\n", count, ans);
    }

    return 0;
}

3035. 次大黑区域

思路

经典的dfs问题，遍历到的点就记录下来不需要回溯。

最终的结果使用set存储，不用再考虑去重问题。输出次大值使用auto it = next(area.begin())，其中it是一个迭代器(iterator),使用 set 的 begin()、end()、next() 等方法获取迭代器时，这些迭代器是指向 set 中元素的指针。 这意味着 it 变量存储的是 指向 集合中某个元素的指针，而不是元素本身的值 。所以输出指针的值使用解引用*，表明取 it 指向的内存地址上的值

代码

//
// Created by HUAWEI on 2025/3/6.
//
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

const int N = 110;
int g[N][N];
bool st[N][N];
set<int, greater<int>> area;
int n, m;
int t;  // 每个黑区域的大小

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

void dfs(int a, int b)
{
    if(st[a][b] || g[a][b] == 0) return;

    t ++;
    st[a][b] = true;
    for(int i = 0; i < 4; i ++)
    {
        int x = a + dx[i], y = b + dy[i];
        if(x >= 1 && x << n && y >= 1 && y <= m && !st[x][y] && g[a][b] == 1)
            dfs(x, y);
    }

    return;
}

int main()
{
   int T;
   cin >> T;

   for(int cnt = 0; cnt < T; cnt ++)
   {
       memset(g, 0, sizeof g);
       memset(st, 0, sizeof st);
       area.clear();

       cin >> n >> m;
       for(int i = 1; i <= n; i ++)
           for(int j = 1; j <= m; j ++)
               cin >> g[i][j];

       for(int i = 1; i <= n; i ++)
           for(int j = 1; j <= m; j ++)
           {
               t = 0;
               dfs(i, j);
               area.insert(t);
           }

       auto it = next(area.begin());
       printf("case #%d:\n%d\n", cnt, *it);
   }

   return 0;
}

5124. 选择

思路

脑筋急转弯问题，思考了一会。没有认真读题看成了每次要选择下标连续的集合错误的认为至少需要n / 2次。查看未通过测试样例发现n为一个很大的数，Output为20。回看题干发现是求二进制位数。

代码

//
// Created by HUAWEI on 2025/3/6.
//
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int cnt = 0;
    while(n > 0)
    {
        n = n >> 1;
        cnt ++;
    }
    cout << cnt << endl;
    return 0;
}