Codeforces Round #617 (Div. 3)全题解(A-F)

题目地址：https://codeforces.com/contest/1296

A.Array with Odd Sum

题目：

题意：

判断数组中是否存在奇数即可，可以用奇数替换掉其中的偶数，这样能保证数组之和肯定为奇数。

但是要注意一点如果是偶数个奇数，也是无解的。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[2000+7];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
    {
        int n;
        int sum=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        if(sum%2==1) {printf("YES\n");continue;}
        else
        {
            int cnt1=0,cnt2=0;
            for(int i=1;i<=n;i++)
            {
                if(a[i]%2==1) cnt1++;
                else cnt2++;
            }
            if(cnt1==0||cnt2==0)  printf("NO\n");
            else  printf("YES\n");
        }
    }
    return 0;
}

B.Food Buying

题目：

题意：

模拟题，贪心就好，每次能买多少买多少，把返利的钱在加到剩余的钱里，以此循环。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//int a[2000+7];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
    {
        int n;
        scanf("%d",&n);
        int s=n;
        int ans=0;
        while(s>=10)
        {
            int tep=s-s%10;
            s=s-tep+tep/10;
            ans+=tep;
        }
        ans+=s;
        printf("%d\n",ans);

    }
    return 0;
}

C.Yet Another Walking Robot

题目：

题意：

需要找出最短的字串使得去掉后不影响机器人正常工作。其实就是找一段最短的字串，且按这个字串从头走到尾走还会走到字串开头的那一点。

我们对前i个左右移动的操作用一个前缀和来维护x

同理上下移动用也用一个前缀和y来维护。

我们通过排序来做，按照x为第一关键字，y为第二关键字，pos（次序）为第三关键词来排序。

然后相邻两两比较就好，如果相邻的两者x，y都相同，两者pos差记录下来。

只需要不断的比较pos差，找出最小的pos差即可。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
//int a[2000+7];
char s[200000+7];
struct node
{
    int x;
    int y;
    int p;
}pos[200000+7];
bool cmp(node a,node b)
{
    if(a.x==b.x)
       {
            if(a.y==b.y)
            {
                return a.p<b.p;
            }
            else return a.y<b.y;
       }
        else return a.x<b.x;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<=n;i++) pos[i].p=i;
        scanf("%s",s+1);
        pos[0].x=0;
        pos[0].y=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='L')	   {pos[i].x=pos[i-1].x-1; pos[i].y=pos[i-1].y;}
            else if(s[i]=='R') {pos[i].x=pos[i-1].x+1; pos[i].y=pos[i-1].y;}
            else if(s[i]=='U') {pos[i].y=pos[i-1].y+1;pos[i].x=pos[i-1].x;}
            else if(s[i]=='D') {pos[i].y=pos[i-1].y-1;pos[i].x=pos[i-1].x;}
        }
        sort(pos,pos+1+n,cmp);
        int minn=100000000,beg=-1;
        for(int i=1;i<=n;i++)
        {
            if(pos[i].x==pos[i-1].x&&pos[i].y==pos[i-1].y)
            {
                int t2=pos[i].p;
                int t1=pos[i-1].p;
                if(minn>abs(t2-t1))
                {
                    minn=abs(t2-t1);
                    beg=min(t2,t1);
                }
            }
        }
        if(beg==-1) printf("-1\n");
        else printf("%d %d\n",beg+1,beg+minn);
    }
    return 0;
}

D.Fight with Monsters

题目：

题意：

题目漏掉了一些信息，后来announcement通知到：每次从自己开始打，无论谁打怪兽们都从自己开始打。

很简单就是排序模拟，但是我们要先对这些怪兽的hp做一些处理，hp[i]=hp[i]%(a+b),这样就知道到最后我们打的时候怪兽还有多少血，值得注意的是处理完后的hp%（a+b）=0时要特殊处理，因为这代表当那个式子等于0时到我们最后打的时候怪兽还有0滴血，也就是已经死了，那么这不是我们最后一次打击，此时hp应该改为hp[i]=a+b

然后对hp排序后贪心。能用a伤害直接杀死就直接打，不能用控制多打一次，同时k—。以此循环模拟

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int hp[200000+7];
int main()
{
	int n,a,b,k;
	cin>>n>>a>>b>>k;
	for(int i=1;i<=n;i++)
    {
        cin>>hp[i];
        hp[i]=hp[i]%(a+b);
        if(hp[i]==0) hp[i]=a+b;
    }
    sort(hp+1,hp+1+n);
    //for(int i=1;i<=n;i++) printf("%d ",hp[i]);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(hp[i]<=a) ans++;
        else
        {
            int t=hp[i]%a==0?(hp[i]-a)/a:(hp[i]-a)/a+1;
            if(k>=t) {k-=t;ans++;}
        }
    }
    cout<<ans<<endl;
    return 0;
}

E1.String Coloring（easy version）

题目：

题意：

我们不难发现这样一个规律，第一次我们找出一个上升子序列并给这些点赋值为0，再扫一遍没有赋值的，如果是单调增的那么把他们赋值为1，如果不是单调增的就无法构成，这个画几个例子会很好找到规律并理解为什么的。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
char s[200+9];
int main()
{
 
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    vector<int>rem;
    int beg=s[1];
    for(int i=1;i<=n;i++)
    {
        if(s[i]>=beg)
        {
            rem.push_back(i);
            beg=s[i];
        }
    }
    //int siz=rem.size();
    int cnt=0;
    int b=-1;
    //int cnt2=0;
    for(int i=1;i<=n;i++)
    {
        if(rem[cnt]==i)
        {
            cnt++;
            continue;
        }
        else
        {
            b=i;
            break;
        }
    }
    cnt=0;
    if(b==-1) {printf("YES\n");for(int i=1;i<=n;i++) printf("0"); return 0;}

    int st=s[b];
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        if(rem[cnt]==i)
        {
            cnt++;
            continue;
        }
        if(s[i]>=st)  st=s[i];
        else flag=1;
    }
    if(flag) printf("NO\n");
    else
    {
        cnt=0;
        printf("YES\n");
        for(int i=1;i<=n;i++)
        {
            if(rem[cnt]==i)
            {
                cnt++;
                printf("0");
                continue;
            }
            else printf("1");
        }
    }
    return 0;
}

E2.String Coloring（hard version）

题目：

题意：

同样的道理，我们这个可以用dp来做。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+1;
char s[maxn];
int n,mx=0,ans[maxn],Max[maxn];
int main()
{
    scanf("%d",&n);
    scanf("%s",s);
    for(int i=0; i<n; ++i)
    {
        int cnt=0;
        for(int j=s[i]+1; j<='z'; j++)
            cnt=max(cnt,Max[j]);
        cnt++;
        Max[s[i]]=cnt;
        ans[i]=cnt;
        mx=max(mx,cnt);
    }
    printf("%d\n",mx);
    for(int i=0; i<n; ++i)
        printf("%d ",ans[i]);
    return 0;
}

F.Berland Beauty

题目：

题意：

给一颗无根树，你要给每条边赋边权，满足每对到的路径上最小边权为$w_i$。

树上任意两点之间的路径可以知道的，我们把所有w按从大到小排序，然后把a到b的路径上的边没有赋边权的全设为w，已经有边权的不变，同时计算这条路径上最小边权minn，如果最后minn=w，证明赋权成功，否则失败。

w一定要从大到小，这样才能保证后来的 $w_j$不会覆盖先前的$w_i$ 。如果把$w_i$覆盖成了$w_j$ ，那么之前$a_i$到$b_i$的路径上最小边权就不是$w_i$，而是 $w_j$了。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5000+7;
const int inf=100000000;
vector<int>mp[maxn];
int ans[maxn][maxn];
int x[maxn],y[maxn];
int a[maxn],b[maxn],g[maxn];
int vis[maxn];
int flag=0,minn=0;
struct node
{
    int a,b,g,pos;
}ask[maxn];
bool cmp(node a,node b)
{
    return a.g>b.g;
}
void dfs(int u,int v,int w)
{
    if(u==v) {flag=1;return;}
    if(vis[u]) return;
    vis[u]=1;
    int sz=mp[u].size();
    for(int i=0;i<sz;i++)
    {
        int nxt=mp[u][i];
        int last=ans[u][nxt];
        int last_min=minn;
        if(ans[u][nxt]==inf) {ans[u][nxt]=w;ans[nxt][u]=w;minn=min(minn,w);}
        else minn=min(minn,ans[u][nxt]);
        dfs(nxt,v,w);
        if(flag) return;
        ans[u][nxt]=last;
        ans[nxt][u]=last;
        minn=last_min;
    }
    return;
}
void init_ans()
{
    for(int i=0;i<=5000;i++)
        for(int j=0;j<=5000;j++)
            ans[i][j]=inf;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        mp[x[i]].push_back(y[i]);
        mp[y[i]].push_back(x[i]);
    }
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        ask[i].pos=i;
        scanf("%d%d%d",&ask[i].a,&ask[i].b,&ask[i].g);
    }
    sort(ask+1,ask+1+m,cmp);
    int exit=0;
    init_ans();
    for(int i=1;i<=m;i++)
    {
        memset(vis,0,sizeof vis);//init
        flag=0;//init
        minn=inf;//init
        dfs(ask[i].a,ask[i].b,ask[i].g);
        if(minn!=ask[i].g) exit=1;
    }
    if(exit)
    {
        printf("-1");
        return 0;
    }
    for(int i=1;i<=n-1;i++)
    {
        if(ans[x[i]][y[i]]==inf) printf("1000000 ");
        else printf("%d ",ans[x[i]][y[i]]);
    }
    return 0;
}

ACM-Codeforces

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Codeforces Round #618 (Div. 2)全题解（A-E）上一篇

数位DP总结+模板下一篇