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;

}

最新文章

  1. linux內核輸出soft lockup
  2. visual studio 2012更换皮肤、功能添加
  3. AngularJS自定义表单控件
  4. SQL Server 的内存分类
  5. 搭建环境Visual Studio 2013 社区版
  6. cpp - 输入输出
  7. git clone下载代码
  8. IIS配置HTTPS
  9. 第四节：tensorflow图的基本操作
  10. PF部分代码解读
  11. ceph学习
  12. 添加script标签、添加事件
  13. 【LeetCode】 617. 合并二叉树
  14. spark-shell启动spark报错
  15. JS object(对象)的学习汇总
  16. 解析XML：DOM,SAX,PULL
  17. Android开发——你真的了解Dialog、Toast和Snackbar吗
  18. UGUI 学习
  19. 【BZOJ4894】天赋（矩阵树定理）
  20. oracle将一个表中字段的值赋值到另一个表中字段（批量）

热门文章

  1. 【剑指 Offer】06.从尾到头打印链表
  2. CICD基础概念
  3. k8s之ServiceAccount
  4. 原生工程接入Flutter实现混编
  5. kill 指令的执行原理
  6. C语言字符串结束符“\0”
  7. Doge.jpg 的背后是什么，你知道么？
  8. 视图V_160M和表T_160M的维护
  9. ElasticSearch Python 基本操作
  10. jmeter-并发及常数吞吐量定时器设定