首页 📔算法学习

解题情况:solved: (4 / 6)
知识点分布:
A题:模拟
B题:找规律
C题:找规律
D题:前缀和、规律
E题:费用流
F题:DP


Problem A:Floor Number

题目传送门Floor Number

解题思路:

水题,初始值为2,每次加x,直到大于等于n为止。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int T;
    cin >> T;
    while(T--) {
        int n, x;
        cin >> n >> x;
        if(n <= 2) {
            puts("1");
            continue;
        }
        int tot = 2;
        for(int i = 2; ; ++i) {
            tot += x;
            if(n <= tot) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

Problem B: Symmetric Matrix

题目传送门: Symmetric Matrix

解题思路

如果m为奇数,则必不可能拼接成对称矩阵,剩下的检查一下瓷砖副对角线上的元素是否相同,如果相同即可组成,否则不行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
 
int main(void)
{
    int T, n, m;
    int a, b, c, d;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        bool flag1 = 0;
        bool flag2 = 0;
        flag1 = m % 2 ? true : false;

        for (int i = 0; i < n; i++) {
            cin >> a >> b >> c >> d;
            if (b == c) flag2 = 1; 
        }
        
        cout << (flag1 && flag2 ? "YES" : "NO") << endl;

    }
    
    return 0;
}

Problem C: Increase and Copy

题目传送门: Increase and Copy

解题思路

贪心题,我们只要让第一个数自增到某个阈值,然后拷贝这个数即可。

经过打表发现自增到$⌈\sqrt(n)⌉$,然后再自增是最佳方案。(可以使用对勾函数来证明)

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

int main()
{
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        int x = sqrt(n);
        int  ans = x - 1;
        int sum = x;
        while(sum < n) 
            sum += x, ans++;

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

Problem D: Non-zero Segments

题目传送门: Non-zero Segments

解题思路

因为可以在两个数之间插入任意大小的数,我们可以对整个数组做一个前缀和,如果$sum[i] == sum[j]$,说明区间$[i, j]$内肯定有一段和为0,我们在这最小的一段(和为0的一段)之间插入一个无穷大或者无穷小的数,就可以使整个大区间内不会存在和为0的情况。

插入数后,我们将前面的前缀和舍去,因为前面的前缀和已经插入一个数解决了和为0的问题,不会影响后面的情况了。

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

int main() 
{
    int T, n;
    cin >> T;
    set<ll> pref;

    ll cur_pref = 0;
    pref.insert(cur_pref);
    int ans = 0;
    while(T--) {
        cin >> n;
        cur_pref += n;
        if(pref.count(cur_pref)) {
            ans++;
            pref = set<ll>({cur_pref - n});
        }
        pref.insert(cur_pref);
    }
    cout << ans << endl;

    return 0;
}



文章评论

    Cat 访客ChromeWindows
    2020-10-10 15:43   回复

    你还记得你有个博客啊

目录