此篇属于CodeForces比赛题解集合
链接
CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) vp 补题
题目清单 传送门
B
满足性质,前一个不行,后面都不行。
做前缀或和运算。
#include<iostream>
#include<algorithm>
#include<queue>
//#include<bits/stdc++.h>
#include<cstring>
#define endl '\n'
#define int long long
#define debug cout << "debug" << endl
using namespace std;
void fileoi()
{
freopen("in.txt","r",stdin);
//freopen("mid.out","w",stdout);
}
const int N = 1e6 + 10;
int n;
int x;
int a[N]; int b[N]; int c[N];
void solve()
{
cin >> n >> x;
int res = 0;
for(int i = 1;i <= n;i ++) { cin >> a[i]; a[i] |= a[i-1]; if((a[i] & x) == a[i]) res |= a[i];}
for(int i = 1;i <= n;i ++) { cin >> b[i]; b[i] |= b[i-1]; if((b[i] & x) == b[i]) res |= b[i];}
for(int i = 1;i <= n;i ++) { cin >> c[i]; c[i] |= c[i-1]; if((c[i] & x) == c[i]) res |= c[i];}
cout << ((res == x) ? "Yes" : "No" )<< endl;
}
signed main()
{
//fileoi();
std::ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _; cin >> _; while(_--)
solve();
}
C
考虑dp[i] 为 前i个最多删除多少个。然后推一下转移式。
#include<iostream>
#include<algorithm>
#include<queue>
//#include<bits/stdc++.h>
#include<cstring>
#define endl '\n'
#define int long long
#define debug cout << "debug" << endl
using namespace std;
void fileoi()
{
freopen("in.txt","r",stdin);
//freopen("mid.out","w",stdout);
}
int n;
const int N = 2e5 + 10;
const int INF = 1e9;
int a[N];
int dp[N];
void solve()
{
cin >> n; for(int i = 1;i <= n;i ++) cin >> a[i];
vector<int> mp(n + 5, -INF);
for(int i = 1;i <= n;i ++)
{
dp[i] = dp[i-1];
dp[i] = max(dp[i],i + mp[a[i]]);
mp[a[i]] = max(mp[a[i]],dp[i-1]-(i-1));
}
cout << dp[n] << '\n';
}
signed main()
{
//fileoi();
std::ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _; cin >> _; while(_--)
solve();
}
D
对于每个选择的集合当中,1必须选,n一定不能选,每个限制条件的意思是如果u和v不在一个集合里则最能玩y时间,则u或v独自玩最多玩y时间
好难
https://grainmad.github.io/2023/06/26/1842/