Educational Codeforces Round 154 (Rated for Div. 2)

A. Prime Deletion

思路：
因为1到9每个数字都有，所以随便判断也质素即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t;
vector<int>del;
int a[200010],b[200010];
int prime[N];
bool st[N];
map<int,int>mp;
bool isPrime(int n)
{if (n <= 3)//当n不大于3时只有1不是素数return n > 1;if (n % 6 != 1 && n % 6 != 5)//只有6i+1和6i+5可能是素数return false;for (int i = 5; i <= sqrt(n); i += 6){if (n % i == 0 || n % (i + 2) == 0)return false;}return true;
}
void solve(){string s;cin>>s;int ans, res = 0;per(i,0,s.size()-1){if (s[i] == '1')ans = i;else if (s[i] == '7')res = i;}if (ans < res)cout << 17 << endl;else cout << 71 << endl;
}
signed main(){cin>>t;while(t--)solve();
}

B. Two Binary Strings

思路：
因为下标1是0，末尾下标是1，所以从左到右遍历，如果当前a[i]==b[i]并且是0的话，将前面跟新，如果走到a[i]==b[i]并且是1的话就一定能构成a=b

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t;
vector<int>del;
int l[200010],l1[N],r[200010],r1[N];
int prime[N];
bool st[N];
map<int,int>mp;
bool isPrime(int n)
{if (n <= 3)//当n不大于3时只有1不是素数return n > 1;if (n % 6 != 1 && n % 6 != 5)//只有6i+1和6i+5可能是素数return false;for (int i = 5; i <= sqrt(n); i += 6){if (n % i == 0 || n % (i + 2) == 0)return false;}return true;
}
void solve(){string a, b; cin >> a >> b;bool st = true;rep(i,1,a.size()-1) {if (a[i] != b[i]) {st = false;}else if (a[i] == '0' && b[i] == '0') {st = true;}else if (a[i] == '1' && b[i] == '1') {if (st)break;}}if (st)cout << "YES" << endl;else cout << "NO" << endl;// cin>>n;// string a,b;// cin>>a;// cin>>b;// int _0=0,_1=0;// int n=a.size();// rep(i,0,n-1){//     if(a[i]==b[i]){//         l[i]=_0;//         r[i]=_1;//         if(a[i]=='0')_0++;//         else _1++;//     }else{//         l[i]=_0;//         r[i]=_1;//     }// }// _0=0,_1=0;// per(i,0,n-1){//     if(a[i]==b[i]){//         l1[i]=_0;//         r1[i]=_1;//         if(a[i]=='0')_0++;//         else _1++;//     }else{//         l1[i]=_0;//         r1[i]=_1;//     }// }// int f=1;// rep(i,0,n-1){//     if(a[i]!=b[i]){//         if((l[i]==0||l1[i]==0)&&(r[i]==0||r1[i]==0)){//             f=0;//             break;//         }//     }// }// if(f){//     cout<<"YES\n";// }else{//     cout<<"NO\n";// }
}
signed main(){cin>>t;while(t--)solve();
}

C. Queries for the Array

思路：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t;
vector<int>del;
int l[200010],l1[N],r[200010],r1[N];
int prime[N];
bool st[N];
map<int,int>mp;
bool isPrime(int n)
{if (n <= 3)//当n不大于3时只有1不是素数return n > 1;if (n % 6 != 1 && n % 6 != 5)//只有6i+1和6i+5可能是素数return false;for (int i = 5; i <= sqrt(n); i += 6){if (n % i == 0 || n % (i + 2) == 0)return false;}return true;
}
void solve() {	int now = 0, s1 = 1, s2 = 3e5;string s; cin >> s;for(char c : s) {if(c == '+') {now++;continue;}if(c == '-') {now--;if(now > 0 && s1 > now) {s1 = now;}if(s2 > now) s2 = 3e5;continue;}if(c == '1') {if(s2 <= now) {cout << "NO\n";return;}s1 = max(s1, now);continue;}if(c == '0') {if(s1 >= now) {cout << "NO\n";return;}s2 = min(s2, now);continue;}}cout << "YES\n";
}
signed main(){cin>>t;while(t--)solve();
}

D. Sorting By Multiplication

思路：前后缀分解
copy一下思路
首先乘上负数能让一段连续递减的区间变成连续递增的区间

然后预处理出连续递增和递减的前缀和后缀

1 1 2 2 2

假设处理连续递增区间

通过样例可得1遇到第二个1有两个做法：

把下标2到4同时乘上一个数，不改变2到4的之间每个数的大小关系

单独把下标2乘上一个数使得比前面一个数大

那么下标3的数有两种情况：

如果a[3]>a[2]:但是a[2]乘上一个数使得a[2]>a[3]，肯定也要改变a[3]了

如果a[3]<=a[2]:a[2]乘上一个数依然不会改变关系

所以最优肯定是直接改变当前下标到后续区间最优

所以计算只需要关心当前数和下一个数的大小关系即可，统计有多少个数要改变即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
using node=tuple<int,int,int,int>;
typedef pair<int,int> PII;
int n,m;
int a[N];
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];vector<int> l(n+10),r(n+10);int now=0;a[n+1]=a[0]=INT_MAX;for(int i=2;i<=n;i++){l[i]=l[i-1]+(a[i]>=a[i-1]);//前缀多少个不是严格递减}now=0;for(int i=n-1;i>=1;i--){r[i]=r[i+1]+(a[i]>=a[i+1]);//后缀多少个不是严格递增}int res=min({n,r[1]});for(int i=1;i<=n;i++){res=min(res,l[i]+1+r[i+1]);}cout<<res<<"\n";}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;//init();cin>>t;while(t--) solve();
}