Educational Codeforces Round 30

时间：2022-02-06 04:18:03

Educational Codeforces Round 30 

A. Chores

把最大的换掉

view code 
#pragma GCC optimize("O3")

#pragma GCC optimize("Ofast,no-stack-protector")

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define endl "\n"

#define LL long long int

#define vi vector<int>

#define vl vector<LL>

#define all(V) V.begin(),V.end()

#define sci(x) scanf("%d",&x)

#define scl(x) scanf("%I64d",&x)

#define pii pair<int,int>

#define pll pair<LL,LL>

#ifndef ONLINE_JUDGE

#define cout cerr

#endif

#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))

#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))

#define debug(x)  cerr << #x << " = " << x << endl

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }

template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }

const int MAXN = 2e5+7;

void solve(){

    int n, m, k;

    sci(n); sci(m); sci(k);

    vi A(n); for(int &x : A) sci(x);

    cmin(m,n);

    for(int i = n - 1, j = 0; j < m; j++, i--) cmin(A[i],k);

    cout << accumulate(all(A),0) << endl;

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

B.  Balanced Substring

令\(s\)为前缀和

就是要找\(s_r-s_{l-1}=\frac {r-l+1}{2}\)

那就是\(2s_r-r = 2s_{l-1}-(l-1)\)

维护每个值最早出现的位置

view code 
#pragma GCC optimize("O3")

#pragma GCC optimize("Ofast,no-stack-protector")

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define endl "\n"

#define LL long long int

#define vi vector<int>

#define vl vector<LL>

#define all(V) V.begin(),V.end()

#define sci(x) scanf("%d",&x)

#define scl(x) scanf("%I64d",&x)

#define pii pair<int,int>

#define pll pair<LL,LL>

#ifndef ONLINE_JUDGE

#define cout cerr

#endif

#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))

#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))

#define debug(x)  cerr << #x << " = " << x << endl

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }

template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }

const int MAXN = 2e5+7;

char s[MAXN];

void solve(){

    int n; cin >> n;

    cin >> s + 1;

    map<int,int> msk;

    int pre = 0;

    msk[0] = 0;

    int ret = 0;

    for(int i = 1; i <= n; i++){

        pre += s[i] - '0';

        if(msk.count(2*pre-i)) cmax(ret,i-msk[2*pre-i]);

        else msk[2*pre-i] = i;

    }

    cout << ret << endl;

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

C. Strange Game On Matrix

每一列单独考虑，枚举\(q\)的起点

view code 
#pragma GCC optimize("O3")

#pragma GCC optimize("Ofast,no-stack-protector")

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define endl "\n"

#define LL long long int

#define vi vector<int>

#define vl vector<LL>

#define all(V) V.begin(),V.end()

#define sci(x) scanf("%d",&x)

#define scl(x) scanf("%I64d",&x)

#define pii pair<int,int>

#define pll pair<LL,LL>

#ifndef ONLINE_JUDGE

#define cout cerr

#endif

#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))

#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))

#define debug(x)  cerr << #x << " = " << x << endl

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }

template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }

const int MAXN = 2e5+7;

int A[111][111];

void solve(){

    int n, m, k;

    sci(n); sci(m); sci(k);

    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sci(A[i][j]);

    int ret = 0, exc = 0;

    for(int i = 1; i <= m; i++){

        vi pos;

        for(int j = 1; j <= n; j++) if(A[j][i]==1) pos << j;

        if(pos.empty()) continue;

        int tmpret = 0, tmpexc = 0;

        for(int j = 0; j < (int)pos.size(); j++){

            int sum = 0;

            for(int kk = j; kk < pos.size(); kk++){

                if(pos[kk] - pos[j] >= k) break;

                sum++;

            }

            if(sum > tmpret) tmpret = sum, tmpexc = j;

        }

        ret += tmpret; exc += tmpexc;

    }

    cout << ret << ' ' << exc << endl;

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

D. Merge Sort

递归下去，如果还需要调用的话，就把当前数字区间左右互换然后分别调用，否则直接不换分别调用

view code 
#pragma GCC optimize("O3")

#pragma GCC optimize("Ofast,no-stack-protector")

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define endl "\n"

#define LL long long int

#define vi vector<int>

#define vl vector<LL>

#define all(V) V.begin(),V.end()

#define sci(x) scanf("%d",&x)

#define scl(x) scanf("%I64d",&x)

#define pii pair<int,int>

#define pll pair<LL,LL>

#ifndef ONLINE_JUDGE

#define cout cerr

#endif

#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))

#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))

#define debug(x)  cerr << #x << " = " << x << endl

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }

template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }

const int MAXN = 2e5+7;

int n, k, A[MAXN];

void merge(int L, int R, int numl, int numr, int &T){

    if(L+1==R){

        A[L] = numl;

        return;

    }

    int mid = (L + R) >> 1;

    if(T>0) T-=2, merge(L,mid,numr-mid+L,numr,T), merge(mid,R,numl,numr-mid+L,T);

    else merge(L,mid,numl,numl+mid-L,T), merge(mid,R,numl+mid-L,numr,T);

}

void solve(){

    sci(n); sci(k); k--;

    merge(0,n,1,n+1,k);

    if(k!=0) cout << -1 << endl;

    else for(int i = 0; i < n; i++) cout << A[i] << ' ';

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

E. Awards For Contestants

先所有数从大到小排序

枚举前两个的位置然后可以确定下一个位置的可行范围，然后\(ST\)表找最大的位置即可

view code 
#pragma GCC optimize("O3")

#pragma GCC optimize("Ofast,no-stack-protector")

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define endl "\n"

#define LL long long int

#define vi vector<int>

#define vl vector<LL>

#define all(V) V.begin(),V.end()

#define sci(x) scanf("%d",&x)

#define scl(x) scanf("%I64d",&x)

#define pii pair<int,int>

#define pll pair<LL,LL>

#ifndef ONLINE_JUDGE

#define cout cerr

#endif

#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))

#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))

#define debug(x)  cerr << #x << " = " << x << endl

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }

template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }

const int MAXN = 3333;

int n, d1, d2, d3, x, y, z, ret[MAXN];

pii A[MAXN];

pii st[MAXN][20];

void solve(){

    sci(n); for(int i = 1; i <= n; i++) sci(A[i].first), A[i].second = i;

    sort(A+1,A+1+n,greater<pii>());

    for(int i = 1; i <= n; i++) st[i][0] = make_pair(A[i].first-A[i+1].first,i);

    for(int j = 1; (1 << j) <= n; j++) for(int i = 1; i + (1 << j) - 1 <= n; i++){

        if(st[i][j-1].first > st[i+(1<<(j-1))][j-1].first) st[i][j] = st[i][j-1];

        else st[i][j] = st[i+(1<<(j-1))][j-1];

    }

    auto query = [&](int l, int r){

        int d = (int)log2(r - l + 1);

        if(st[l][d].first>st[r-(1<<d)+1][d].first) return st[l][d];

        else return st[r-(1<<d)+1][d];

    };

    d1 = d2 = d3 = -1;

    for(int i = 1; i <= n - 2; i++) for(int j = i + 1; j <= n - 1; j++){

        int a = i, b = j - i;

        if(min(a,b) * 2 < max(a,b)) continue;

        int l = 1, r = n - j;

        cmax(l,(max(a,b)+1)/2);

        cmin(r,min(a,b)*2);

        if(l>r) continue;

        l += j; r += j;

        auto p = query(l,r);

        int t1 = A[i].first - A[i+1].first, t2 = A[j].first - A[j+1].first, t3 = p.first;

        if(t1>d1 or (t1==d1 and t2>d2) or (t1==d1 and t2==d2 and t3>d3)){

            d1 = t1; d2 = t2; d3 = t3;

            x = i; y = j; z = p.second;

        }

    }

    for(int i = 1; i <= x; i++) ret[A[i].second] = 1;

    for(int i = x + 1; i <= y; i++) ret[A[i].second] = 2;

    for(int i = y + 1; i <= z; i++) ret[A[i].second] = 3;

    for(int i = z + 1; i <= n; i++) ret[A[i].second] = -1;

    for(int i = 1; i <= n; i++) cout << ret[i] << ' ';

    cout << endl;

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

F. Forbidden Indices

后缀自动机，插入一个字符的时候如果这个位置末尾被禁止的话，当前点的\(right\)集合大小设为\(0\)，否则设为\(1\)，然后就是计算每个状态节点的\(len[i]\cdot right[i]\)最大值了

view code 
#pragma GCC optimize("O3")

#pragma GCC optimize("Ofast,no-stack-protector")

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define endl "\n"

#define LL long long int

#define vi vector<int>

#define vl vector<LL>

#define all(V) V.begin(),V.end()

#define sci(x) scanf("%d",&x)

#define scl(x) scanf("%I64d",&x)

#define pii pair<int,int>

#define pll pair<LL,LL>

#ifndef ONLINE_JUDGE

#define cout cerr

#endif

#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))

#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))

#define debug(x)  cerr << #x << " = " << x << endl

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }

template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }

const int MAXN = 1e6+7;

char s[MAXN], t[MAXN];

struct SAM{

    int len[MAXN],link[MAXN],ch[MAXN][26],cnt[MAXN],tot,last;

    int buc[MAXN], sa[MAXN];

    SAM(){ link[0] = -1; }

    void extend(int c, int ct){

        int np = ++tot, p = last;

        len[np] = len[last] + 1; cnt[np] = ct;

        while(p!=-1 and !ch[p][c]){

            ch[p][c] = np;

            p = link[p];

        }

        if(p==-1) link[np] = 0;

        else{

            int q = ch[p][c];

            if(len[p]+1==len[q]) link[np] = q;

            else{

                int clone = ++tot;

                len[clone] = len[p] + 1;

                link[clone] = link[q];

                memcpy(ch[clone],ch[q],sizeof(ch[q]));

                link[np] = link[q] = clone;

                while(p!=-1 and ch[p][c]==q){

                    ch[p][c] = clone;

                    p = link[p];

                }

            }

        }

        last = np;

    }

    void rua(){

        for(int i = 1; i <= tot; i++) buc[i] = 0;

        for(int i = 1; i <= tot; i++) buc[len[i]]++;

        for(int i = 1; i <= tot; i++) buc[i] += buc[i-1];

        for(int i = tot; i >= 1; i--) sa[buc[len[i]]--] = i;

        LL ret = 0;

        for(int i = tot; i >= 1; i--){

            int u = sa[i];

            cnt[link[u]] += cnt[u];

        }

        for(int i = 1; i <= tot; i++) cmax(ret, 1ll * cnt[i] * len[i]);

        cout << ret << endl;

    }

}sam;

void solve(){

    int len;

    cin >> len >> s >> t;

    for(int i = 0; i < len; i++) sam.extend(s[i]-'a',(t[i]-'0')^1);

    sam.rua();

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    solve();

    return 0;

}

相关文章