Lut本科回忆录

更新至G,D,C,H…

题G

题意：给定一个只包含 $1,2,3,4$ 的长度为 $n$ 的数组 $a$ 和整数 $k$， 求包含 $1,2,3,4$ 且有 $k$ 个 $4$ 的最短连续区间长度。

解：双指针。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int a[N], p[5];
int main(){
    int n, k, num = 0; cin >> n >> k;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    int ans = n;
    for(int l = 1, r = 1; r <= n; ++ r){
        p[a[r]] ++;
        while(p[1] >= 1 && p[2] >= 1 && p[3] >= 1 && p[4] >= k && l <= r){
            ans = min(ans, r - l + 1);
            p[a[l]] --;
            l ++;
        }
    }
    cout << ans;
}

用map wa了一发，奇奇怪怪。

题D

题意：给定 $k,c,n$ $(1<=k,c,n<=1e9)$, 求有多少对正整数 $a，b$ 满足 $ka+b=c$ 其中 $c=xb，x>=1,gcd(a,b)>=n$。

解：由题意可得方程 $a=(c-b)/k$, 我们由 $c=xb, x>=1$ 可以枚举 $b$，复杂度为 $O(sqrt(c))$, 然后欧几里得判断。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
vector<int> prime;
void cal(int x){
    for(int i = 1; i <= x / i; ++ i){
        if(x % i == 0){
            prime.push_back(i);
            if(x / i != i) prime.push_back(x / i);
        }
    }
}
void solve(){
    prime.clear();
    int k, c, n, ans = 0; cin >> k >> c >> n;
    cal(c);
    for(auto &b: prime){
        if((c - b) % k == 0){
            int a = (c - b) / k;
            if(a > 0 && __gcd(a, b) >= n) ans ++;
        }
    }
    cout << ans << '\n';
}
int main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    while(n--) solve();
    return 0;
}

题C

题意：给定一个二分图，图左右两边都有 $n$ 个点，且点的编号是 $1-n$ 和 $n + 1-2n$，若 $(i,j + n)$之间存在边，则 $(j,i +n)$之间不存在边。邻接矩阵给出该图的 $n(n-1)/2$条边。问该图的最大匹配 $(1<=n<=3000)$

解：根据题目性质，可以将 $(i,j+n)$ 转换为 $(i,j)$，此时该图变成了一个竞赛图，当且仅当一个强连通分量只有两个点的时候答案为 $n-1$,反之为 $n$。

#include<bits/stdc++.h>
using namespace std;
int d[3010];
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, x = 0, y = 0; cin >> n;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            int x; cin >> x;
            if(x) d[i] ++;
        }
    }
    sort(d + 1, d + 1 + n);
    for(int i = 1, j = 0, s = 0; i <= n; ++ i){
        s += d[i];
        if(s == i * (i - 1) / 2){
            if(i - j <= 2){cout << n - 1; return 0;}
            j = i;
        }
    }
    cout << n;
}

题H

题意：由 $n$ 个奶酪，体积分别为 $a_i$，价值为 $b_i$，只能按从前往后的顺序拿，当且仅当第 $i$ 个奶酪被损坏或者拿走才能对第 $i+1$ 奶酪操作。一共由 $m$ 个背包，每个背包体积为 $w_i$，每次拿一个背包从第一个奶酪出发，问最多拿走多少价值的奶酪$(1<=n<=200,1<=m<=1e5,1<=a_i<=200,1<=b_i<=1e5,1<=w_i<=200)$。

解：我们用 $dp[i][j]$ 表示用到第 $i$ 个背包花费 $j$ 空间的最大价值。因为背包是连续使用的，并且题目给的背包容积是从小到大，所以我们取最大的 $min(n, m)$ 个背包就好。然后我们第一维枚举每一块奶酪，对这么些个背包而言取不取这块奶酪，这里就是 $01$ 背包，判断完之后，更新一下下一位背包，下一个背包如果不取当前奶酪的话，那么 $dp[j + 1][0] = max(dp[j + 1][0], dp[j][k])$, 就可以更新下一个背包不取当前奶酪的情况。最后对第 $dp[m][i]$ 寻找最大价值方案。

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int a[N], b[N], w[100010];
int dp[N][N];
int main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    int n, m, mx = 0; cin >> n >> m;
    for(int i = 1; i <= n; ++ i) cin >> a[i] >> b[i];
    for(int i = 1; i <= m; ++ i) cin >> w[i];
    if(m > n) {for(int i = 1; i <= n; ++ i) w[i] = w[i + m - n]; m = n;}
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            for(int k = w[j]; k >= a[i]; -- k){
                dp[j][k] = max(dp[j][k], dp[j][k - a[i]] + b[i]);
            }
        }
        for(int j = 1; j < m; ++ j){
            for(int k = 0; k <= w[j]; ++ k){
                dp[j + 1][0] = max(dp[j + 1][0], dp[j][k]);
            }
        }
    }
    
    for(auto &x: dp[m]) mx = max(mx, x);
    cout << mx;
}