Codeforces Round #376 (Div. 2)

A:水题,模拟即可

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-12;
const int N=2000+10,maxn=90000+10,inf=0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int ans=0,last=0;
    for(int i=0;i<s.size();i++)
    {
        int p=s[i]-'a';
       // cout<<p<<" "<<last<<endl;
        ans+=min(abs(p-last),26-abs(p-last));
      //  cout<<ans<<endl;
        last=p;
    }
    cout<<ans<<endl;
    return 0;
}
/********************

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

B:题意:给你两种折扣卷,一种连续两天消费,一种一天内消费两次,你有无限的消费卷,问能不能刚好满足每天的消费

不为偶数的用第一中,否则第二种,直接遍历找矛盾

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-12;
const int N=200000+10,maxn=90000+10,inf=0x3f3f3f3f;

int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n-1;i++)
    {
        if(a[i]&1)
        {
            if(a[i+1]==0)
            {
                cout<<"NO"<<endl;
                return 0;
            }
            else a[i+1]--;
        }
    }
    if(a[n-1]&1)
    {
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;
    return 0;
}
/********************

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

C:题意:找每个连通图里最小修改次数使得每个点权值相同

简单dfs一下记录最多的权值和总点数就好了

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-12;
const int N=200000+10,maxn=90000+10,inf=0x3f3f3f3f;

vector<int>v[N];
bool vis[N];
map<int,int>ma[N];
int sz,c[N];
void dfs(int u)
{
    sz++;
    ma[0][c[u]]++;
    vis[u]=1;
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        if(!vis[x])dfs(x);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        if(!ma[l][r])
        {
            v[l].pb(r);
            v[r].pb(l);
            ma[l][r]=ma[r][l]=1;
        }
    }
   /* for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
            cout<<v[i][j]<<" ";
        cout<<endl;
    }*/
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            ma[0].clear();
            sz=0;
            dfs(i);
            int maxx=0;
            for(auto x:ma[0])
                maxx=max(maxx,x.se);
            ans+=sz-maxx;
        }
    }
    cout<<ans<<endl;
    return 0;
}
/********************

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

D:给你n行数,每次操作对所有数+1,大于c就变成1,要求找到一种操作次数来使得,每两行之间满足字典序(类似与字符串的比较),不可能输出-1

题解:每两行之间遍历一遍找到第一个不相同的数对,最后只要操作使得找到的数对,第一个小于第二个就好了,我们可以通过把满足条件的区间用查分标记+前缀和来维护,最后找满足条件的结果时,用扫描线,从左往右扫一遍即可

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-12;
const int N=500000+10,maxn=1000000+10,inf=0x3f3f3f3f;

vector<int>v[N];
ll num[maxn];
int n,c;
void add(int x,int y,int op)
{
    int be,en;
    if(op==1)
    {
        be=c-x+1;
        y+=be;
        while(y>c)y-=c;
        en=c-y+be;
        num[be]++;num[en+1]--;
    }
    else
    {
        if(y==c&&x!=1)
        {
            be=c-x+1;en=c-1;
            num[be]++,num[en+1]--;
        }
        else if(x==1&&y!=c)
        {
            be=c-y;
            num[0]++,num[be+1]--;
        }
        else if(x!=1&&y!=c)
        {
            be=c-y;
            num[0]++;
            num[be+1]--;
            be=c-x+1;
            en=c-1;
            if(be<=en)
            {
                num[be]++;
                num[en+1]--;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
    {
        int a;
        for(scanf("%d",&a);a;a--)
        {
            int x;
            scanf("%d",&x);
            v[i].pb(x);
        }
    }
    ll ans=0;
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            if(j>=v[i+1].size())
            {
                puts("-1");
                return 0;
            }
            if(v[i][j]>v[i+1][j])
            {
                add(v[i][j],v[i+1][j],1);
                ans++;
                break;
            }
            else if(v[i][j]<v[i+1][j])
            {
                add(v[i][j],v[i+1][j],2);
                ans++;
                break;
            }
        }
    }
    for(int i=1;i<=1000000;i++)
        num[i]+=num[i-1];
    for(int i=0;i<=1000000;i++)
    {
        if(num[i]>=ans)
        {
            printf("%d
",i);
            return 0;
        }
    }
    puts("-1");
    return 0;
}
/********************

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

E:题意:n个数,两个人依次操作,一次操作把前k(2<=k<=m,m是剩余的数)个变成他们的和,该人的分数+这个和,每个人的目标都是使两个人的分数差距最大

题解:dp[i]表示从1到i为1堆的下一次先手取的最优情况,转移方程dp[i]=max(sum[j]-dp[j])(i+1<=j<=n)每次转移相当于,换了一个人在j这个地方取了一次,因为是-dp【j】,那么每次操作符号都会改变,这样苏算的是先手取的和减后手取的和,用maxx来维护把复杂度降到O(n)

#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 pii pair<int,int>

using namespace std;

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

int sum[N],dp[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&sum[i]),sum[i]+=sum[i-1];
    int maxx=sum[n];
    for(int i=n-1;i>=1;i--)
    {
        dp[i]=maxx;
        maxx=max(maxx,sum[i]-dp[i]);
    }
    printf("%d
",dp[1]);
    return 0;
}
/********************

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

F:题意:n个数,从中取任意个,先找到最小的,然后把其他的数减到是最小的数的倍数,求取得数的和的最大值

题解:可以注意到数的范围只有200000,我们可以巧妙的用前缀和维护每个数出现的次数,然后我们sort,遍历通过每次找a【i】的倍数之间的个数(因为下一个倍数区间要加的值会不同)来计算最大值,复杂度O(nlogn)

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-12;
const int N=200000+10,maxn=90000+10,inf=0x3f3f3f3f;

ll a[N],num[N];
bool vis[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        num[a[i]]++;
    }
    for(int i=1;i<=200000;i++)num[i]+=num[i-1];
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[a[i]])
        {
            ll te=0;
            vis[a[i]]=1;
            for(ll j=1;j*a[i]<=a[n];j++)
            {
                int p=(j+1)*a[i]-1;
                if(p>200000)p=200000;
                te+=(num[p]-num[j*a[i]-1])*j*a[i];
            }
            ans=max(ans,te);
        }
    }
    printf("%lld
",ans);
    return 0;
}
/********************

********************/
F
原文地址:https://www.cnblogs.com/acjiumeng/p/7989366.html