Codeforces Round #466 (Div. 2)

http://codeforces.com/contest/940

A水题

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

int a[N];
int main()
{
    int n,d;
    scanf("%d%d",&n,&d);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    int minn=100000;
    for(int i=0;i<n;i++)
    {
        bool ok=0;
        for(int j=i;j<n;j++)
        {
            if(a[j]-a[i]>d)
            {
                ok=1;
//                printf("%d %d
",i,j-1);
                minn=min(minn,n-(j-i));
                break;
            }
        }
        if(!ok)
        {
//            printf("%d+++
",i);
            minn=min(minn,i);
        }
    }
    printf("%d
",minn);
    return 0;
}
/********************

********************/
A

B直接暴力，忘了考虑1 的情况t了一发

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

int main()
{
    ll n,k,a,b,ans=0;
    scanf("%lld%lld%lld%lld",&n,&k,&a,&b);
    if(k==1)
    {
        printf("%lld
",(n-1)*a);
        return 0;
    }
    while(n)
    {
        if(n<k)
        {
            ans+=a*(n-1);
            break;
        }
        else
        {
            if(n%k==0)
            {
                ans+=min((n-n/k)*a,b);
                n=n/k;
            }
            else
            {
                ans+=(n%k)*a;
                n-=n%k;
            }
        }
    }
    printf("%lld
",ans);
    return 0;
}
/********************

********************/
B

C从后往前扫找第一个个能替换的换了，然后把后面的全部换成最小,O(n*26)

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

char s[N];
int num[30];
int main()
{
    int n,k;
    scanf("%d%d%s",&n,&k,s);
    for(int i=0;i<n;i++)num[s[i]-'a']=1;
    int f=0;
    for(int i=0;i<26;i++)
    {
        if(num[i])
        {
            f=i;
            break;
        }
    }
    if(n<k)
    {
        printf("%s",s);
        for(int i=0;i<k-n;i++)printf("%c",(char)(f+'a'));
        puts("");
    }
    else
    {
        for(int i=k-1;i>=0;i--)
        {
            int ok=-1;
            for(int j=0;j<26;j++)
            {
                if(num[j]&&s[i]-'a'<j)
                {
//                    printf("%d %d
",i,j);
                    ok=j;
                    break;
                }
            }
            if(ok!=-1)
            {
                s[i]=(char)(ok+'a');
//                printf("%d %c
",i,s[i]);
                for(int j=i+1;j<k;j++)s[j]=(char)(f+'a');
                for(int j=0;j<k;j++)printf("%c",s[j]);
                break;
            }
        }
    }
    return 0;
}
/********************

********************/
C

D枚举所有情况找l和r即可，见过最简单的d题= =

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

char s[N];
int a[N],b[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1')b[i]=1;
        else b[i]=0;
    }
    int l=-1e9,r=1e9;
    for(int i=5;i<=n;i++)
    {
        if(!b[i]&&b[i-1]&&b[i-2]&&b[i-2]&&b[i-3])
        {
            r=min(r,a[i]-1);
            r=min(r,a[i-1]-1);
            r=min(r,a[i-2]-1);
            r=min(r,a[i-3]-1);
            r=min(r,a[i-4]-1);
        }
        else if(b[i]&&!b[i-1]&&!b[i-2]&&!b[i-2]&&!b[i-3])
        {
            l=max(l,a[i]+1);
            l=max(l,a[i-1]+1);
            l=max(l,a[i-2]+1);
            l=max(l,a[i-3]+1);
            l=max(l,a[i-4]+1);
        }
    }
    printf("%d %d
",l,r);
    return 0;
}
/********************

********************/
D

E，题意：把一堆数分成若干块，每个块的价值是去掉前k/c（k是块大小）小的数的和，求所有块最小的和

很明显每个块分尽可能的c个，然后每次可以用dp来算dp【i】=min（dp【i-1】+a【i】，dp【i-c】+sum（i-c，i））求sum复杂度是o(n)，可以用线段树预处理然后优化到o（logn），总复杂度O（nlogn）

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

ll mi[N<<2],sum[N<<2],a[N],dp[N];
void pushup(int rt)
{
    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        mi[rt]=sum[rt]=a[l];
        return ;
    }
    int m=(l+r)>>1;
    build(ls);build(rs);
    pushup(rt);
}
ll querysum(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return sum[rt];
    int m=(l+r)>>1;
    ll ans=0;
    if(L<=m)ans+=querysum(L,R,ls);
    if(m<R)ans+=querysum(L,R,rs);
    return ans;
}
ll querymi(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return mi[rt];
    int m=(l+r)>>1;
    ll ans=1e9+10;
    if(L<=m)ans=min(ans,querymi(L,R,ls));
    if(m<R)ans=min(ans,querymi(L,R,rs));
    return ans;
}
int main()
{
    int n,c;
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,n,1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]+a[i];
        if(i-c>=0)
        {
            ll all=querysum(i-c+1,i,1,n,1);
            dp[i]=min(dp[i],dp[i-c]+all-querymi(i-c+1,i,1,n,1));
        }
    }
    printf("%lld
",dp[n]);
    return 0;
}
/********************

********************/
E

F，题意：一些数，两个操作1，把某个位置的数改成另一个，2，查询mex（数的总和个数）

带修莫队裸题，先把数离散化，然后暴力跑莫队即可，维护一个数的个数，一个数的个数有多少个，注意块一定要开n^(2/3)个,sqrt(n)会t，复杂度O（n^(5/3)+nlogn）

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=300000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

int a[N],belong[N],ans[N],now[N];
int l=1,r=0,num[N],t,co[N];
int Hash[N];
struct que{
    int l,r,tim,id;
}qu[N];
struct change{
    int pos,suf,pre;
}ch[N];
bool cmp(que a,que b)
{
    if(belong[a.l]==belong[b.l])
    {
        if(belong[a.r]==belong[b.r])return a.tim<b.tim;
        else return a.r<b.r;
    }
    else return a.l<b.l;
}
void gao(int x,int d)
{
    if(d==1)
    {
        num[co[x]]--;
        co[x]++;
        num[co[x]]++;
    }
    else
    {
        num[co[x]]--;
        co[x]--;
        num[co[x]]++;
    }
}
void go(int x,int d)
{
    if(l<=x&&x<=r)gao(d,1),gao(a[x],-1);
    a[x]=d;
}
int main()
{
    int n,q,cnt=0;
    scanf("%d%d",&n,&q);
    int block=3000;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        Hash[cnt++]=a[i];
        now[i]=a[i];
        belong[i]=(i-1)/block+1;
    }
    int cnt1=0,cnt2=0;
    for(int i=1;i<=q;i++)
    {
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if(op==1)qu[++cnt1]={a,b,cnt2,cnt1};
        else ch[++cnt2]={a,b,now[a]},now[a]=b,Hash[cnt++]=b;
    }
    sort(Hash,Hash+cnt);
    cnt=unique(Hash,Hash+cnt)-Hash;
    for(int i=1;i<=n;i++)a[i]=lower_bound(Hash,Hash+cnt,a[i])-Hash;

    for(int i=1;i<=cnt2;i++)
    {
        ch[i].pre=lower_bound(Hash,Hash+cnt,ch[i].pre)-Hash;
        ch[i].suf=lower_bound(Hash,Hash+cnt,ch[i].suf)-Hash;
    }
//    for(int i=1;i<=cnt1;i++)
//        printf("%d %d %d %d
",qu[i].l,qu[i].r,qu[i].id,qu[i].tim);
    sort(qu+1,qu+1+cnt1,cmp);
    for(int i=1;i<=cnt1;i++)
    {
        while(t<qu[i].tim)go(ch[t+1].pos,ch[t+1].suf),t++;
        while(t>qu[i].tim)go(ch[t].pos,ch[t].pre),t--;
        while(l<qu[i].l)gao(a[l],-1),l++;
        while(l>qu[i].l)gao(a[l-1],1),l--;
        while(r<qu[i].r)gao(a[r+1],1),r++;
        while(r>qu[i].r)gao(a[r],-1),r--;
        int res=1;
        while(num[res])res++;
        ans[qu[i].id]=res;
    }
    for(int i=1;i<=cnt1;i++)printf("%d
",ans[i]);
    return 0;
}
/********************

********************/
F
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/acjiumeng/p/8798567.html