Codeforces Round 1013(Div. 3). A~F    原题链接    中等

作者： 作者的头像   NextAutumn ,  2025-03-26 21:39:32 ·江苏 ,  所有人可见 ,  阅读 7

0


A:

统计 0， 1， 2， 3， 5的个数
时间复杂度O(Tn)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = 2e5 + 10, M = 2 * N;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int P = 1e9 + 7;

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a; 
} 

void solve(){
    int n;
    cin >> n;
   // cout << n << '\n';
    vector<int> cnt(10);
    int ans = 0;
    int flag = 0;
    for(int i = 1; i <= n; i ++){
        int x;
        cin >> x;
        cnt[x] ++;
        if(cnt[0] >= 3 && cnt[1] >= 1 && cnt[2] >= 2 && cnt[3] >= 1 && cnt[5] >= 1){
            if(!flag) ans = i;
            flag = 1;
        }
    }
    cout << (flag ? ans : 0) << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

B

贪心：小的只会拖累大的，从大的开始枚举，如果大于x则直接添加，否则往前遍历再看是否可能大于x
时间复杂度O(n)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = 2e5 + 10, M = 2 * N;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int P = 1e9 + 7;

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a; 
} 

void solve(){
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n + 10);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + n, [&](ll x, ll y){return x > y;});
    ll ans = 0;
    for(int i = 1; i <= n; i ++){
        if(a[i] >= k) ans ++;
        else{
            ll j = i, minx = a[i];
            int flag = 0;
            while(j <= n){
                minx = min(minx, a[j]);
                if(minx * (j - i + 1) >= k){
                    i = j;
                    ans ++;
                    flag = 1;
                    break;
                }
                j ++;
            }
        }
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

C
首先可以发现，偶数的情况必然无解，奇数的情况只要有一个a[i] = i必然可以凑出，这里提供一种好写的排序：先输出偶数（或者奇数），再输出奇数（或者偶数）
时间复杂度O(n)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = 2e5 + 10, M = 2 * N;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int P = 1e9 + 7;

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a; 
} 

void solve(){
    int n;
    cin >> n;
    if(n % 2 == 0) cout << -1 << '\n';
    else{
        for(int i = 2; i <= n - 1; i += 2) cout << i << ' ';
        for(int i = 1; i <= n - 2; i += 2) cout << i << ' ';
        cout << n << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

D
满足单调性，比赛的时候直接拿二分写的，赛后看大佬说是鸽巢原理，可以直接O(T);
说一下二分的写法：
二分枚举答案，由于每次排座位要留空，所以剩余 m % (mid + 1)个空，这必然小于mid，所以一行的答案就是 m / (mid + 1) * mid + m % (mid + 1);
有n行，所以总答案： tol = n * (m / (mid + 1) * mid + m % (mid + 1))
时间复杂度O(T * logm)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = 2e5 + 10, M = 2 * N;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int P = 1e9 + 7;

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a; 
} 

void solve(){
    ll n, m, k;
    cin >> n >> m >> k;

    function<int(ll)> check = [&](ll mid) -> int{
        ll t = mid + 1;
        ll x = m / t * mid, r = m % t;
        ll tol = (x + r) * n;
        //cout << tol << '\n';
        return tol >= k;
    };
    //check(2);
    ll l = 1, r = INF;
    while(l < r){
        ll mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

E:
公式转换：a * b / gcd(a, b) = lcm(a, b);

假设a，b互质，那么最后的答案就是1 = 质数，显然1不是质数
所以假设 b = k * a，则最后的答案就是k = 质数

所以：我们现在有2种做法：

做法1：枚举b，题目转化成了，1~n中所有数的质因子个数
做法2：枚举a，题目转化成了，找出最大的质数x，使得a * x <= n，
每次统计1~x范围内的质数的数量

首先，既然都要找质数，我们先要取做个质数筛
对于做法1：时间复杂度是O(n^(3 / 2))显然超时
对于做法2：我们统计出质数后，用前缀和统计[1, i]中的质数个数，
最后枚举1~n，加上对应的s[n / i]即可
时间复杂度O(n)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = 2e5 + 10, M = 2 * N;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int P = 1e9 + 7;

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a; 
} 

void solve(){
    int n;
    cin >> n;
    vector<int> primes(1000000), vis(n + 10);
    int cnt = 0;
    for(int i = 2; i <= n; i ++){
        if(!vis[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] * i <= n; j ++){
            vis[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
    ll ans = 0;
    vector<ll> s(n + 10);
    for(int i = 2; i <= n; i ++){
        s[i] = s[i - 1];
        if(!vis[i]) s[i] ++;
    }
    for(int i = 1; i <= n; i ++){
        ans += s[n / i];
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

F:
考虑dp：
设：dp[i][j][k]表示：爬到(i，j)这个点，且用了k - 1个石头的方案数（同一层最多用两个石头，0表示1个，1表示2个，每一层最多用2个石头）
如果直接打暴力，那么时间复杂度是O(n * m^2) 显然TLE

对于同一层：dp[i][j][1] += ∑dp[i][k][0]（k != j）
对于上一层（必然是1个石头）：dp[i][j][0] += ∑dp[i + 1][k][0] + ∑dp[i + 1][k][1];

显然，对于同一层，我们要求出所有符合条件的dp[i][k][0]，这里因为是同一层，所以只要满足|k - j| <= d 即可 -> j - d <= k <= d + j， 考虑用前缀和维护
所以同一层的范围是：j - d <= k <= d + j

对于上一层，求出所有满足条件的dp[i + 1][k][0] 和 dp[i + 1][k][1]，这一层也要用前缀和维护
对于距离，考虑以d为斜边，1为短直角边的直角三角形做勾股定理：
斜边为d，直角边为1，那么长边就是sqrt(d * d - 1) = L
范围就是：[j - (上取整)L, j + (下取整)L]
别忘了范围还要和1取max，和m取min，涉及到减法取模别忘加模数
通过前缀和和勾股定理，成功优化掉了第三层循环
时间复杂度O(nm)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef double db;
typedef pair<db, db> pdd;
const int N = 2e5 + 10, M = 2 * N;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int P = 998244353;

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a; 
} 

void solve(){
    int n, m, d;
    cin >> n >> m >> d;
    vector<vector<char>> g(n + 10, vector<char>(m + 10));
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> g[i][j];

    vector<vector<vector<ll>>> dp(n + 10, vector<vector<ll>>(m + 10, vector<ll>(2)));
    vector<vector<ll>> s0(n + 10, vector<ll>(m + 10)), s1(n + 10, vector<ll>(m + 10));
    for(int i = 1; i <= m; i ++){
        if(g[n][i] == 'X') dp[n][i][0] = 1;
    }
    for(int i = n; i; i --){
        for(int j = 1; j <= m; j ++){
            if(g[i][j] == 'X'){
                double L = sqrt(d * d - 1);
                int l0 = max(1, (int)ceil(j - L)), r0 = min(m, j + (int)L);
                dp[i][j][0] = (dp[i][j][0] + s0[i + 1][r0] - s0[i + 1][l0 - 1] + P) % P;
            }
        }
        for(int j = 1; j <= m; j ++){
            s1[i][j] = (s1[i][j - 1] + dp[i][j][0]) % P;
        }
        for(int j = 1; j <= m; j ++){
            if(g[i][j] == 'X') {
                int l1 = max(1, j - d), r1 = min(m, j + d);
                dp[i][j][1] = (dp[i][j][1] + s1[i][r1] - s1[i][l1 - 1]) % P;
                dp[i][j][1] = (dp[i][j][1] - dp[i][j][0] + P) % P;
            }
        }
        for(int j = 1; j <= m; j ++){
            s0[i][j] = (s0[i][j - 1] + dp[i][j][0] + dp[i][j][1]) % P;
        }
    }
    ll ans = 0;
    for(int i = 1; i <= m; i ++) ans = (ans + dp[1][i][0] + dp[1][i][1]) % P;
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

0 评论

1024
x