当前位置：首页 > news >正文

2026-03-15

news 2026/3/27 5:58:23

CF

Problem - 467C - Codeforces

选和不选简单dp

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=5010;
LL a[N];
LL dp[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m,k;cin >> n >> m >> k;for (int i = 1; i <= n;i++){cin >> a[i];}for (int i = 1; i <= n;i++){a[i] += a[i - 1];}for (int i = 1; i <= n; i++){for (int j = 1; j <= k; j++){if (i - m >= 0)dp[i][j] = max(dp[i - m][j - 1] + a[i] - a[i - m], dp[i - 1][j]);}}cout << dp[n][k] << endl;
}

Problem - 283A - Codeforces

模拟

[!warning] 一个注意点：
first ai elements = 前 ai 个元素

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
LL a[N], d[N];//注意，开 LL！！！int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;int op, x, y;LL ans = 0;int top = 1;while(n--){cin >> op;if(op==1){cin >> x >> y;d[x] += y;//后往前求和ans += x * y;}else if(op==2){cin >> x;a[++top] = x;ans += x;}else{ans -= a[top] + d[top];d[top - 1] += d[top];a[top] = 0, d[top] = 0, top--;}cout << fixed << setprecision(10) << ans * 1.0 / top << endl;}
}

Problem - 1991C - Codeforces

一道1300的构造，花了好久想
首先判断奇偶性，因为不管怎么减，奇偶性相反的数字始终是相反的
然后减去一个数，相当于把数组变成偶数（这里想了好久，一直想不懂，理解下来只是为了化简操作）
理解：把整个数组放到数轴上，固定0为最左的端点，每次虽然减去 \(2^i\) ，能保证整个数组处理之后，不会超过 \(2^i\) ，因为数组的变化实际上是变成距离 \(2^i\) 的大小

你的纸条长达 2^30。

你捏住正中间的 2^29，往下拽成 V 字型，碰到桌面（高度变 0）。

两端的 0 和 2^30 翘到天上贴在一起，它们的高度都是 2^29。

纸条上所有的数字，现在全被折进了 0 到 2^29 的高度里！
下一轮，你再拿一把剪刀，把这个 V 字型的纸条从高度 2^28 的地方剪开，再捏住中间折一次……
每折一次，最高的高度就矮一半！

所以一定保证数组会一直缩小，直到1或0
如果是奇数的话，只要进行31次，因为最后一次减去1之后，变成偶数0，不用再操作

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
int a[N];void solve()
{int n;cin >> n;for (int i = 0; i < n;i++){cin >> a[i];}bool flag = 0;for (int i = 1; i < n;i++){if(a[i]%2!=a[0]%2){flag = 1;break;}}if(flag){cout << -1 << endl;return;}cout << 32 << endl;cout << a[0] << " ";//想了好久for (int i = 29; i >= 0;i--){cout << (1 << i)<<" ";}cout << 1 << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}

另一种写法（好理解的）：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
int a[N];void solve()
{int n;cin >> n;for (int i = 0; i < n;i++){cin >> a[i];}bool flag = 0;for (int i = 1; i < n;i++){if(a[i]%2!=a[0]%2){flag = 1;break;}}if(flag){cout << -1 << endl;return;}bool isodd = a[0] % 2;//补充if(isodd){cout << 30 << endl;}else{cout << 31 << endl;}for (int i = 29; i >= 0;i--){cout << (1 << i)<<" ";}if(isodd==0)cout << 1 << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}

复习

输入输出

freopen("data.in","r",stdin);
freopen("data.out","w",stdout);

单调栈

P3467 [POI 2008] PLA-Postering - 洛谷

单调栈简单好题
单调递增

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;stack<int> s;int d, w;int cnt = 0;//可以合并的个数for (int i = 1; i <= n;i++){cin >> d >> w;while(!s.empty()&&w<=s.top()){if(w==s.top())cnt++;s.pop();}s.push(w);}cout << n - cnt << endl;
}

Problem - 1779D - Codeforces

只不过这个是凹，就是保持单调递减，然后找相等

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
int a[N], b[N];void solve()
{int n;map<int, int> mp;stack<int> s;cin >> n;for (int i = 0; i < n;i++){cin >> a[i];}for (int i = 0; i < n;i++){cin >> b[i];}int m;cin >> m;for (int i = 0; i < m;i++){int x;cin >> x;mp[x]++;}for (int i = 0; i < n;i++){while(!s.empty()&&s.top()<b[i])s.pop();if(a[i]<b[i]){cout << "NO\n";return;}if (a[i] == b[i] || (!s.empty() && s.top() == b[i]))continue;if(mp[b[i]]==0){cout << "NO\n";return;}s.push(b[i]);mp[b[i]]--;}cout << "YES\n";
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}

查看全文

http://www.jsqmd.com/news/480888/