(寒假开黑gym)2018 USP Try-outs

layout: post

title: (寒假开黑gym)2018 USP Try-outs

author: "luowentaoaa"

catalog: true

tags:

mathjax: true

- codeforces

B.Aesthetics in poetry (暴力模拟)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e6+50;

const ll inf=1e10;

const ll INF = 1000000000;

const double eps=1e-5;

map<int,int>mp;

int a[maxn];

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int n;

    cin>>n;

    for(int i=0;i<n;i++)cin>>a[i];

    bool flag=false;

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

        if(n%i==0){

            mp.clear();

            for(int j=0;j<n;j++)mp[a[j]%i]++;

            if(mp.size()==i){

                bool ok=false;

                for(int j=0;j<i;j++){

                    if(mp[j]!=n/i){ok=true;break;}

                }

                if(!ok){

                    cout<<i<<endl;return 0;

                }

            }

        }

    }

    cout<<-1<<endl;

    return 0;

}

D.Maximizing Advertising (离散化)

题意

在平面内有两种点，让你用两个不相交的矩形把平面覆盖，让一个平面的黑点+另一个平面内的百白点数目最多

思路

直接枚举两平面的相隔点就行，数据太大无法计数用离散化解决

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e6+50;

const ll inf=1e10;

const ll INF = 1000000000;

const double eps=1e-5;

#define bug cout<<"mx="<<mx<<endl;

vector<int>x1,x2,y1,y2;

vector<int>X;

int sum1,sum2;

int vis1x[maxn],vis1y[maxn],sum1x[maxn],sum1y[maxn];

int vis2y[maxn],vis2x[maxn],sum2x[maxn],sum2y[maxn];

void get(int id){

    sum1x[id]=vis1x[id];

    sum1y[id]=vis1y[id];

    sum2x[id]=vis2x[id];

    sum2y[id]=vis2y[id];

    if(id){

        sum1x[id]+=sum1x[id-1];sum1y[id]+=sum1y[id-1];

        sum2x[id]+=sum2x[id-1];sum2y[id]+=sum2y[id-1];

    }

}

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int n;

    cin>>n;

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

        int x,y;char ch;

        cin>>x>>y>>ch;

        if(ch=='b')x1.push_back(x),y1.push_back(y),sum1++;

        else x2.push_back(x),y2.push_back(y),sum2++;

        X.push_back(x);X.push_back(y);

    }

    sort(X.begin(),X.end());

    X.erase(unique(X.begin(),X.end()),X.end());

    int sz=X.size();

    for(int i=0;i<x1.size();i++){

        x1[i]=lower_bound(X.begin(),X.end(),x1[i])-X.begin();

        y1[i]=lower_bound(X.begin(),X.end(),y1[i])-X.begin();

    }

    for(int i=0;i<x2.size();i++){

        x2[i]=lower_bound(X.begin(),X.end(),x2[i])-X.begin();

        y2[i]=lower_bound(X.begin(),X.end(),y2[i])-X.begin();

    }

    int mx=0;

    for(int i=0;i<sum1;i++){

        vis1x[x1[i]]++;

        vis1y[y1[i]]++;

    }

    for(int i=0;i<sum2;i++){

        vis2x[x2[i]]++;

        vis2y[y2[i]]++;

    }

    for(int i=0;i<sz;i++){

       get(i);

        mx=max(mx,sum1x[i]+sum2-sum2x[i]);

        mx=max(mx,sum2x[i]+sum1-sum1x[i]);

        mx=max(mx,sum1y[i]+sum2-sum2y[i]);

        mx=max(mx,sum2y[i]+sum1-sum1y[i]);

    }

    cout<<mx<<endl;

    return 0;

}

E.Group work (组合数学)

题意

N个学生分组，可以大于等于三个人一组问分组数量有多少中

思路

Cn0+Cn1+Cn2+Cn3+...+Cnn等于2^n 减去取0个和取1个就是答案

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e6+50;

const ll inf=1e10;

const ll INF = 1000000000;

const double eps=1e-5;

#define bug cout<<"mx="<<mx<<endl;

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int n;

    cin>>n;

    cout<<((1LL<<n)-n-1)<<endl;

    return 0;

}

G.Running a penitentiary (区间交集)

题意

有n个警察，第i个警察看管监狱的区间是【Li，Ri】。

有两种操作：C i l r ：把第i个警察的区间变为【l，r】。

？l r ：询问从第l个警察到第r个警察共同看管的区间长度是多少

H. Wine Production (莫队算法+离散化)

题意

给出N个数，每次查询一个区间返回一个K,表示区间有K个数出现了至少K个次

题解

首先用num[x]表示X出现了多少次，cnt[x]表示出现次数为X的个数，

因为N个数有负数所以需要离散化一下，然后就是莫队算法瞎搞(模板是从1开始的，我一开始是从0开始的。。)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e5+50;

const ll inf=1e10;

const ll INF = 1000000000;

const double eps=1e-5;

#define bug cout<<"mx="<<mx<<endl;

// ---

// 莫队算法,可以解决一类静态,离线区间查询问题。分成 $\sqrt{x}$ 块,分块排序。

// ---

int unit;

int a[maxn];

vector<int> b;

struct query { int L, R, id; };

int ans[maxn];

int num[maxn];///出现次数

int cnt[maxn]; ///出现个数

int tmp;

void add(int x){

    num[x]++;cnt[num[x]]++;

    if(min(num[x],cnt[num[x]])>tmp)tmp=min(num[x],cnt[num[x]]);

}

void del(int x){

    cnt[num[x]]--;

    if(num[x]==tmp&&cnt[num[x]]<tmp){

        tmp=cnt[num[x]];

    }

    num[x]--;

}

void solve(query node[], int m)

{

    memset(ans, 0, sizeof(ans));

    sort(node, node + m, [](query a, query b) {

        return a.L / unit < b.L / unit

               || a.L / unit == b.L / unit && a.R < b.R;

    });

    int L = 0, R = -1;

    for (int i = 0; i < m; i++)

    {

        while (node[i].L < L) add(a[--L]);

        while (node[i].L > L) del(a[L++]);

        while (node[i].R < R) del(a[R--]);

        while (node[i].R > R) add(a[++R]);

        ans[node[i].id] = tmp;

    }

}

query my[maxn];

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int n,m;

    cin>>n>>m;

    unit=sqrt(n);

    for(int i=0;i<n;i++)cin>>a[i],b.push_back(a[i]);

    sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());

    for(int i=0;i<n;i++)a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin();

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

        cin>>my[i].L>>my[i].R;my[i].id=i;

        my[i].L--;my[i].R--;

    }

    solve(my,m);

    for(int i=0;i<m;i++)cout<<ans[i]<<endl;

    return 0;

}

I.A story about tea ()

J.Meme Wars （模拟）

思路

就按照题意构造字符串，第一次交超内存了，于是就判断长度是否大于N在构造

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e5+50;

const ll inf=1e10;

const ll INF = 1000000000;

const double eps=1e-5;

#define bug cout<<"mx="<<mx<<endl;

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    string s="a";

    int n;cin>>n;

    for(char c='b';c<'z'&&s.size()<n;c++)s=s+c+s;cout<<s[n-1];

    return 0;

}

巴特西