更新至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;
}