Educational Codeforces Round 159 (Rated for Div. 2)

好困，差点没打

A - Binary Imbalance

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
	string s;
	int n;
	cin>>n;
	cin>>s;
	if(n==1&&s[0]=='0'){
        cout<<"YES"<<endl;
        return;
	}
	for(int i=1;i<s.size();i++){
        if(!(s[i]==s[i-1]&&s[i]=='1')){
            cout<<"YES"<<endl;
            return;
        }
	}
	cout<<"NO"<<endl;
}

signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
	return 0;
}

B - Getting Points

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int n,P,l,t;

void solve() {
    cin>>n>>P>>l>>t;
    int all=(n+6)/7;
    int day=(all+1)/2;
    if(all*t+day*l>=P){
        int ans=(P+(2*t+l-1))/(2*t+l);
        cout<<n-ans<<endl;
        return;
    }
    int ans=day;
    P-=all*t+day*l;
    cout<<n-ans-(P+l-1)/l<<endl;
}

signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
	return 0;
}

C - Insert and Equalize

(好像写复杂了)

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
int a[N];
int n;

void solve() {
    cin>>n;
    map<int,int> b;
    for(int i=1;i<=n;i++) cin>>a[i],b[a[i]]++;
    sort(a+1,a+1+n);
    if(n==1){
        cout<<1<<endl;
        return;
    }
    int x;
    if(n==2){
        x=a[2]-a[1];
    }else{
        x=__gcd(a[2]-a[1],a[3]-a[2]);
        for(int i=4;i<=n;i++) x=__gcd(x,a[i]-a[i-1]);
    }
    int ans1=0,ans2=0;
    int idx1=-1,idx2=a[n]+x;
    for(int i=a[n];;i-=x)
        if(b.find(i)==b.end()){
            idx1=i;
            break;
        }
    for(int i=1;i<=n;i++){
        ans1+=(a[n]-a[i])/x;
        ans2+=(idx2-a[i])/x;
    }
    ans1+=(a[n]-idx1)/x;
    cout<<min(ans1,ans2)<<endl;
}

signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
	return 0;
}

E - Collapsing Strings

打的时候有想着用字符串哈希正着求一遍，反着求一边。想了很久怎么快速求出答案，没想懂。

打完别人写的才懂怎么实现的。

搓了用map的hash wa21了，看了题解说是字符串哈希很容易被卡，用字典树维护数量好写一点。

调半天，刚开始全开ll,runtime error6，后面把宏定义注释掉了，又爆int了。

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;

const int N = 2e6 + 10;
int tr[N][26],cnt1[N],cnt2[N];
string s;
int n;
int tot;

int ct(int u,int v){
    if(!tr[u][v]) tr[u][v]=++tot;
    return tr[u][v];
}

void solve() {
    cin>>n;
    unsigned long long ans=0;
    for(int i=1;i<=n;i++){
        cin>>s;
        ans += s.size()*2*n;
        int u=0;
        for(int j=0;j<s.size();j++) u=ct(u,s[j]-'a'),cnt1[u]++;
        u=0;
        for(int j=s.size()-1;j>=0;j--) u=ct(u,s[j]-'a'),cnt2[u]++;
    }

    for(int i=1;i<=tot;i++) ans-= 2ll*cnt1[i]*cnt2[i]; //这里一定一定一定要是2ll*,不然会爆Int。
    cout<<ans<<endl;
}

signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
	return 0;
}

D - Robot Queries

这题主要要搞清楚原路径上的点和 翻转后路径上的点 的映射关系