CF
Problem - 1955D - Codeforces
1400 双指针
#include
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 1e6+10;
int a[N], b[N];void solve()
{int n,m,k;cin >> n >> m >> k;map cnta, cntb;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= m;i++){cin >> b[i];cntb[b[i]]++;}int now = 0, ans = 0;for (int r = 1; r <= n;r++){if(r>m){int x = a[r - m];if(cnta[x]<=cntb[x]){now--;}cnta[x]--;}int add = a[r];if(cnta[add]=m&&now>=k){ans++;}}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 2049C - Codeforces
1500 构造 从 \(x\) 位置开始，交替0 1，如果最后不满足的话，改 \(x\) 为 2
#include
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 2e5+10;
int a[N];void solve()
{int n, x, y;cin >> n >> x >> y;x--, y--;for (int i = 0; i < n;i++){int pos = (x + i) % n;a[pos] = i % 2;}if(n%2==1||(y-x)%2==0){a[x] = 2;}for (int i = 0; i < n;i++){cout << a[i] << " ";}cout << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 2036E - Codeforces
1600 二分，找区间就可以
#include
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 2e5+10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, k, q;cin >> n >> k >> q;vector> a(k + 1, vector(n + 1));for (int i = 1; i <= n;i++){for (int j = 1; j <= k;j++){int x;cin >> x;a[j][i] = a[j][i - 1] | x;}}while(q--){int m;cin >> m;int L = 1, R = n;while(m--){int r, c;char op;cin >> r >> op >> c;if(op=='<'){int pos = lower_bound(a[r].begin() + 1, a[r].end(), c) - a[r].begin();R = min(R, pos - 1);}else{int pos = upper_bound(a[r].begin() + 1, a[r].end(), c) - a[r].begin();L = max(L, pos);}}if(L<=R){cout << L << endl;}else{cout << -1 << endl;}}
}
Problem - 557C - Codeforces
1900 计数排序
注意：这里是移除桌腿
枚举最长长度的可能，然后大于 ta 的直接剪掉
小于它的部分，一个有 num 个短边的话，最多保留 sz-1 个，所以要减去max(0,num-sz+1) 个，然后能量不大于200，所以直接从小到大枚举能量，减去满足的数量就可以了
注意把当前长度加入短边用于下一个长度计算
#include
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 1e5+10;
int a[N], s[N], suf[N], cnt[210];
vector v[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];}for (int i = 1; i <= n;i++){int x;cin >> x;v[a[i]].push_back(x);s[a[i]] += x;}for (int i = 100000; i >= 1;i--){suf[i] = suf[i + 1] + s[i];}int ans = 2e9, num = 0;for (int len = 1; len <= 100000;len++){if(v[len].empty()){continue;}int sz = v[len].size();int cut = max(0, num - sz + 1);int del = 0;for (int j = 1; j <= 200 && cut > 0; j++){int now = min(cut, cnt[j]);del += now * j;cut -= now;}ans = min(ans, suf[len + 1] + del);for(auto x:v[len]){cnt[x]++;num++;}}cout << ans << endl;
}
Problem - 914C - Codeforces
计数，要判断数字满足小于 k的情况
#include
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 1e9 + 7;
const int N = 1010;
LL C[N][N], dep[N];void init(){for(int i = 0; i <=1000; ++i){C[i][0] = 1; for(int j = 1; j <= i; ++j) { C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } C[i][i + 1] = 0; }
}LL calc(string s,int need){int n = s.size() - 1;int cnt = 0;LL ans = 0;for (int i = 1; i <= n;i++){if(s[i]=='1'){int rem = n - i;if(need-cnt>=0&&need-cnt<=rem){ans = (ans + C[rem][need - cnt]) % mod;}cnt++;}}if(cnt==need){//注意ans = (ans + 1) % mod;}return ans;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);init();string s;int k;cin >> s >> k;int n = s.size();s = " " + s;for (int i = 2; i <= n;i++){dep[i] = dep[__builtin_popcount(i)] + 1;}if(k==0){cout << 1 << endl;return 0;}LL ans = 0;for (int i = 1; i <= n;i++){if(dep[i]+1==k){ans = (ans + calc(s, i)) % mod;}}if(k==1){//特判 数字 1 的情况ans = (ans - 1 + mod) % mod;}cout << ans << endl;
}