Codeforces Round 1005 (Div. 2) A-D题解
A. Brogramming Contest
主要就是统计一下最后一个0移动了多少次就行了（和他前面的1联通块数量有关）
总体时间复杂度O（n）
// Problem: A. Brogramming Contest
// Contest: Codeforces - Codeforces Round 1005 (Div. 2)
// URL: https://codeforces.com/contest/2064/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(1e3) + 10, INF = static_cast<ll>(5e18) + 3;
ll N, M, T;
char A[MAXN];
inline void solve() {
cin >> N;
FOR(i, 1, N) { cin >> A[i]; }
ll ans = 0;
bool isConti0 = false, isConti1 = false,flag=false;
ROF(i, N, 1) {
if (A[i] == '0' && !isConti0) {
isConti0 = true, isConti1 = false;
if(!flag){
ll cnt = 0;
bool isConti = false;
ROF(j, i - 1, 1) {
if (A[j] == '1' && !isConti) {
++cnt, isConti = true;
} else if (A[j] == '0') {
isConti = false;
}
}
ans += cnt;
flag=true;
}
} else if (A[i] == '1' && !isConti1) {
isConti0 = false, isConti1 = true;
++ans;
} else if (A[i] == '0' && isConti0) {
isConti0 = true, isConti1 = false;
} else if (A[i] == '1' && isConti1) {
isConti0 = false, isConti1 = true;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
pretest pass 4
*/
B. Variety is Discouraged
其实这种只指定了substring的话，一般都有固定的操作模式，因为把所有l，r都遍历一遍就超时了，所以一般也不可能加速暴力计算
当然你说有没有可能是双指针，这个就需要具体分析了，主要还是这个计算用双指针没那么方便（这种计算没有可加性，不容易合并），所以也不太行
我们容易发现，这个只有删除只出现过一次的元素，才有可能让值保持不变，如果删除了一个重复出现过两次的元素，会直接让值下降，不符合题设
在样例中我们也发现，删除只是会让长度缩短，并不能增加得分
3
1
1
5
1 1 1 1 1
4
2 1 3 2
1 1
0
2 3
// Problem: B. Variety is Discouraged
// Contest: Codeforces - Codeforces Round 1005 (Div. 2)
// URL: https://codeforces.com/contest/2064/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;
ll N, M, T, A[MAXN]; // diff[MAXN], ndiff[MAXN],sum[MAXN],nsum[MAXN];
ll cnt[MAXN], pos[MAXN];
inline void solve() {
cin >> N;
bool flag = true;
FOR(i, 1, N) {
cnt[i] = 0;
pos[i] = 0;
}
FOR(i, 1, N) {
cin >> A[i];
if (A[i] != A[i - 1] && i != 1) flag = false;
// cnt[A[i]] = cnt.find(A[i]) == cnt.end() ? 1 : cnt[A[i]] + 1;
cnt[A[i]] += 1;
pos[A[i]] = i;
}
// if (flag && N != 1) {
// cout << 0 << '\n';
// return;
// }
// if (N == 1) {
// cout << 1 << ' ' << 1 << '\n';
// return;
// }
vector<ll> needDel;
FOR(i, 1, N) {
if (cnt[i] == 1) {
needDel.pb(pos[i]);
}
}
if(needDel.empty()){ // 注意空的判断，不要漏了
cout<<0<<'\n';
return;
}
if (SZ(needDel) == 1) {
cout << needDel[0] << ' ' << needDel[0] << '\n';
return;
}
sort(all(needDel));
ll l = needDel[0], r = needDel[0];
vector<arr> ans;
FOR(i, 1, SZ(needDel) - 1) {
ll p = needDel[i], bp = needDel[i - 1];
if (p - bp == 1) {
r = p;
} else {
ans.pb({r - l, l, r});
l = p;
r = p;
}
}
ans.pb({r - l, l, r});
sort(all(ans));
cout << ans.back()[1] << ' ' << ans.back()[2] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
AC
https://codeforces.com/contest/2064/submission/306477034
*/
C. Remove the Ends
我们容易观察到，其实只有正数+负数这种可能，比如负数1+正数+负数2，相当于只选了负数1，正数1+负数+正数2，也相当于只选了正数2
这个WA是因为我没考虑到这里所说的正数，负数是可以不连续的，即为子序列，而不是子串
其实子序列反而好弄一点，用正数前缀和+负数后缀和就搞定了
// Problem: C. Remove the Ends
// Contest: Codeforces - Codeforces Round 1005 (Div. 2)
// URL: https://codeforces.com/contest/2064/problem/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A[MAXN];
ll zsum[MAXN],fsum[MAXN];
inline void solve(){
// 这是一道有关前后缀最大化得分的题
// 只有正数+负数这种可能，比如负数1+正数+负数2，相当于只选了负数1
// 正数1+负数+正数2，也相当于只选了正数2
// 当然，这些正数是不一定相连的，负数也是同理
cin>>N;
zsum[0]=0;
FOR(i,1,N){
cin>>A[i];
if(A[i]>=0){
zsum[i]=zsum[i-1]+abs(A[i]);
}else{
zsum[i]=zsum[i-1];
}
}
fsum[N+1]=0;
ROF(i,N,1){
if(A[i]<0){
fsum[i]=fsum[i+1]+abs(A[i]);
}else{
fsum[i]=fsum[i+1];
}
}
ll ans=0;
FOR(i,0,N){
ans=max(zsum[i]+fsum[i+1],ans);
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
WA
https://codeforces.com/contest/2064/submission/306518627
这个WA是因为我没考虑到这里所说的正数，负数是可以不连续的，即为子序列，而不是子串
AC
https://codeforces.com/contest/2064/submission/306520956
*/
D. Eating
感觉是一道数据结构+位运算题（当然这两个我都比较一般）
这道题最烦人的其实就是异或计算没有单调性，不是说我这个值满足，比这个值大的都满足
所以说位运算位运算，总归是要按位分析
看了一下题解，总结来说就是（msb可以理解二进制数的位数）
// == msb 通过计算判断能不能吃，msb必定减少
// > msb 吃不了
// < msb 可以吃
因为==msb的这种比较复杂的情况必定会让x的msb下降，
WA的原因是由于lower_bound()方式实现的__lg()有点问题，我们还是老老实实写一个_lg2()吧
// Problem: D. Eating
// Contest: Codeforces - Codeforces Round 1005 (Div. 2)
// URL: https://codeforces.com/contest/2064/problem/D
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A[MAXN];
ll pow2[40];
ll last[MAXN][35]; // 从后往前，比这位msb大的（包括相等）最大的编号在哪里（）
ll sumA[MAXN];
inline int _lg2(ll n) {
int pos = 0;
while (n) {
n >>= 1;
pos++;
}
return pos;
}
inline void solve(){
cin>>N>>M;
FOR(i,1,N){
cin>>A[i];
ll msb=_lg2(A[i]);
FOR(j,0,33){
if(j<=msb){
last[i][j]=i;
}else{
last[i][j]=last[i-1][j];
}
}
}
sumA[N+1]=0;
ROF(i,N,1){ // 异或总和
sumA[i]=sumA[i+1]^A[i];
}
// == msb 通过计算判断能不能吃，msb必定减少
// > msb 吃不了
// < msb 可以吃
FOR(i,1,M){
ll x;
cin>>x;
ll msb=_lg2(x);
ll idx=last[N][msb],upPos=N+1;
while(idx>0){
if((x^(sumA[idx+1]^sumA[upPos]))>=A[idx]){
// #ifdef LOCAL
// cerr<<i<<' ' << idx<<' '<<x<<' '<< A[idx]<<' '<< (x^(sumA[idx+1]^sumA[upPos])) << '\n';
// #endif
x=( (x^(sumA[idx+1]^sumA[upPos]))^A[idx]);
msb=_lg2(x);
upPos=idx;
idx=last[idx-1][msb]; // 第idx个我已经吃了，那自然要看第idx-1个
}else{
// idx=upPos;
break;
}
}
cout<<N-idx<<' '; // 第idx个吃不了，但他的idx后面一个位置是可以吃的
}
cout<<'\n';
// #ifdef LOCAL
// FOR(i,1,7){
// FOR(j,1,N){
// cerr<<last[j][i]<<' ';
// }
// cerr<<'\n';
// }
// #endif
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
pow2[0]=1;
FOR(i,1,38){
pow2[i]=pow2[i-1]*2;
}
while(T--){
solve();
}
return 0;
}
/*
AC
https://codeforces.com/contest/2064/submission/306654531
*/
投递美团等公司9个岗位