Educational Codeforces Round 174 （A-D题解）
这场总体我打的挺爽的，直接做出3题，对于我这个灰名来说也是首次了
A. Was there an Array?
没什么好说的，就是模拟，然后检验
// Problem: A. Was there an Array?
// Contest: Codeforces - Educational Codeforces Round 174 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2069/problem/0
// Memory Limit: 512 MB
// Time Limit: 2000 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>(1e2)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,B[MAXN],A[MAXN];
inline void solve(){
cin>>N;
FOR(i,1,N){
A[i]=0;
B[i]=0;
}
FOR(i,2,N-1){
cin>>B[i];
}
ll idx=0;
FOR(i,2,N-1){
if(B[i]==1){
if(A[i-1]!=0 || A[i]!=0 || A[i+1]!=0){
A[i-1]=idx;
A[i]=idx;
A[i+1]=idx;
}else{
A[i]=++idx;
A[i-1]=idx;
A[i+1]=idx;
}
}
}
FOR(i,1,N){
if(A[i]==0){
A[i]=++idx;
}
}
// #ifdef LOCAL
// FOR(i,1,N){
// cerr<<A[i]<<' ';
// }
// cerr<<"\n";
// FOR(i,1,N){
// cerr<<B[i]<<' ';
// }
// cerr<<"\n\n";
// #endif
FOR(i,2,N-1){
if(B[i]==0){
if(A[i]==A[i-1] && A[i]==A[i+1]){
cout<<"NO\n";
return;
}
}
}
cout<<"YES\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
AC
*/
B. Set of Strangers
脑筋急转弯，其实你会发现，只要这个颜色出现过而且这个颜色有块相邻，那么最佳stranger分组个数就是2，否则为1。
然后就好做了，具体看代码吧
// Problem: B. Set of Strangers
// Contest: Codeforces - Educational Codeforces Round 174 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2069/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 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>(7e2)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,maze[MAXN][MAXN];
bool col[490100]; // stranger count（该颜色有没有检测到相邻？）
bool vis[490100]; // is this color occur?
ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};
inline void solve(){
cin>>N>>M;
FOR(i,1,N){
FOR(j,1,M){
cin>>maze[i][j];
}
}
// if(N==1 && M==1)
FOR(i,1,N*M){
col[i]=false;
vis[i]=false;
}
FOR(i,1,N){
FOR(j,1,M){
vis[maze[i][j]]=true;
if(col[maze[i][j]]) continue;
FOR(k,0,3){
ll u=i+dx[k],v=j+dy[k];
if(u<1 || u>N) continue;
if(v<1 || v>M) continue;
if(maze[u][v]==maze[i][j]){
col[maze[u][v]]=true;
break;
}
}
}
}
ll ans=0,mx=0;
FOR(i,1,N*M){
if(!vis[i]) continue;
if(col[i]){
ans+=2;
mx=max(mx,2ll);
}else{
ans+=1;
mx=max(mx,1ll);
}
}
cout<<ans-mx<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
AC
*/
C. Beautiful Sequence
这个题目官方打了dp，可能是其他解法吧，反正我的做法用不到dp，最重要的反而是你的高中组合知识要比较扎实。
当然，首先你要发现关键是首数和尾数，首数一定是序列最里最小的，尾数一定是序列里最大的，而且这个最大，最小是严格的。
因此，我们得出结论开头一定是1，结尾一定是3，中间是2
众所周知，nC1+nC2+nC3+...+nCn=(2^n)-1，那么每多加一个2，那么对于一个1来讲，可能性就多了2^(n-1)
当然对于多个1，情况会略微复杂一点，具体请看下面的代码。
FOR(i,1,N){
if(A[i]==2){
cnt2.add(last1Pos,idx);
idx=(idx*2)%mod;
}else if(A[i]==1){
last1Pos=i;
++idx;
}else{
ans=(ans+cnt2.query(1,i))%mod;
}
}
然后我的代码有点小复杂，不小心用了树状数组，其实根本不需要，用一个数就够了，我写的时候太兴奋了。
// Problem: C. Beautiful Sequence
// Contest: Codeforces - Educational Codeforces Round 174 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2069/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 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;
constexpr ll mod=998244353;
ll N,M,T,A[MAXN];
struct BIT { // 普通的单点修改区间查询树状数组（依赖MAXN）含有查找第K个空位的功能
vector<ll> tr;
int n;
inline int lowbit(int x) { return x & (-x); }
BIT(int ln) { // 构造+初始化函数
n = ln;
tr.resize(n+5,0);
}
inline void add(int p, int x) {
if(p==0) return;
while (p <= n) {
tr[p] += x;
p += lowbit(p);
}
}
inline ll query(int l, int r) {
ll lres = 0, rres = 0;
l -= 1;
while (l > 0) {
lres += tr[l];
l -= lowbit(l);
}
while (r > 0) {
rres += tr[r];
r -= lowbit(r);
}
return rres - lres;
}
inline int findKth(int k) { // 找到第k个空位
int cx = 0;
for (int i = 1 << 20; i > 0; i >>= 1) { // 这个你可以理解为不断缩小步长的搜索
if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
// lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
k -= lowbit(cx + i) - tr[cx + i];
cx += i;
}
}
return cx + 1; // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
}
};
// 关键是首数和尾数，首数一定是序列最里最小的，尾数一定是序列里最大的
inline void solve(){
cin>>N;
FOR(i,1,N){
cin>>A[i];
}
BIT cnt2(N);
// FOR(i,1,N){
// if(A[i]==2){
// cnt2.add(i,1);
// }
// }
ll last1Pos=0,idx=0;
ll ans=0;
FOR(i,1,N){
if(A[i]==2){
cnt2.add(last1Pos,idx);
idx=(idx*2)%mod;
}else if(A[i]==1){
last1Pos=i;
++idx;
}else{
ans=(ans+cnt2.query(1,i))%mod;
}
}
if(ans<0) ans+=mod;
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
AC
*/
D. Palindrome Shuffle
题解提示了我用二分答案，这就有点意思了，我来看看有没有办法自己写出来
搞了半天，结果是题解的讲法有点问题，即便是已经匹配好的块，也是要动的，不动不行。
ktffetfekktttteeekffkekkttfttfeftefftk
比如说这个例子，正确答案是12，但是如果你不考虑移动已经匹配好的字符，这个答案是算不出来的。所有未匹配块的下标已经在下面给出。正确的是选择9～20这个区间，因为19，20虽然已经匹配了，但都是f，正好和后面匹配，空出来的两个位置放无法匹配的e。
k t t e e k t t f e
9 10 12 15 16 23 24 27 29 30
那我们怎么搞那？其实是这样，如果没有跨越中线，那么还是就匹配未匹配块（当然你要匹配已经匹配的也没人管你）。然后跨越中线的，就需要无论是否是已经匹配，直接减，然后看剩余的是不是比空的位置多（跨越中线一格，就会多两个自匹配位置），具体看代码就行。
// Problem: D. Palindrome Shuffle
// Contest: Codeforces - Educational Codeforces Round 174 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2069/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 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;
// ll cnt[MAXN][30];
ll oripos[MAXN];
ll idx=0;
ll ans=INF;
string s;
inline bool check(ll x){
// 可以用预处理优化，但我摆烂了
if(oripos[1]+x-1<=N/2){
vector<ll> cnt(26,0),cnt1(26,0);
FOR(i,1,N/2){
if(s[i]!=s[N-i+1]) ++cnt[s[i]-'a'];
}
FOR(i,N/2+1,N){
if(s[i]!=s[N-i+1]) ++cnt1[s[i]-'a'];
}
FOR(i,0,25){
if(cnt1[i]!=cnt[i]) return false;
}
return true;
}else{
ll rem=(oripos[1]+x-1-N/2)*2;
vector<ll> cnt(26,0),cnt1(26,0);
FOR(i,oripos[1],oripos[1]+x-1){
++cnt[s[i]-'a'];
}
FOR(i,oripos[1]+x,oripos[idx]){
++cnt1[s[i]-'a'];
}
ll sum=0;
FOR(i,0,25){
ll t=cnt[i]-cnt1[i];
if(t<0) return false;
if(t%2!=0) return false;
sum+=t;
}
if(sum>rem) return false;
else return true;
}
return false;
}
inline void solve(){
s.clear();
cin>>s;
ans=INF;
N=SZ(s);
FOR(i,1,2){
s="0"+s;
idx=0;
FOR(i,1,N){
if(s[i]!=s[N-i+1]){
oripos[++idx]=i;
}
}
if(idx==0){
cout<<0<<'\n';
return;
}
ll l=oripos[idx/2]-oripos[1]+1,r=oripos[idx]-oripos[1]+1;
while(l<r){
ll mid=l+r>>1;
if(check(mid)){
r=mid;
}else{
l=mid+1;
}
}
ans=min(ans,l);
reverse(all(s));
s.resize(N);
}
cout<<ans<<"\n";
#ifdef LOCAL
FOR(i,1,idx){
cerr<<s[oripos[i]]<<" ";
}
cerr<<"\n";
FOR(i,1,idx){
cerr<<oripos[i]<<" ";
}
cerr<<"\n";
#endif
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
// #ifdef LOCAL
// cerr << '\n';
// #endif
}
return 0;
}
/*
AC
https://codeforces.com/contest/2069/submission/307218443
*/
美的集团公司福利 163人发布
投递腾讯音乐娱乐集团等公司9个岗位