Codeforces Round #617(Div. 3) 解题报告

A - Array with Odd Sum
首先看原数组的和是不是奇数，再看是不是全为奇数或者全为偶数即可。

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=2050;
int a[N];
int main()
{
    int Test;
    cin>>Test;
    while(Test--)
    {
        int n;
        cin>>n;
        ll sum=0;
        bool eji=0,eou=0;
        for(int i=1;i<=n;++i)cin>>a[i],sum+=a[i];
        for(int i=1;i<=n;++i)
        {
            if(a[i]&1)eji=true;
            else eou=true;
        }
        if(sum%2==1||(eji&&eou)){puts("Yes");continue;}
        puts("NO");
    }
    return 0;
}

B - Food Buying
实际上就按照那个例子来模拟即可......

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int s;
int ans;
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        cin>>s;
        ans=s;
        while(s>=10)
        {
            ans+=s/10;
            s=s/10+s%10;
        }
        cout<<ans<<endl;
    }
    return 0;
}

C - Yet Another Walking Robot
用map来存最后一次到达该坐标的时间，之后贪心即可。
另外，pair没法hash，所以只能用map而不能用unordered_map。

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
const int N=200050;
int n;
char s[N];
int ans;
map <pair<int,int>,int> vis;
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        cin>>n;
        ans=N;
        vis.clear();
        scanf("%s",s+2);
        int x=0,y=0;
        vis[mp(x,y)]=1;
        int L=-1,R=-1;
        for(int i=2;i<=n+1;++i)
        {
            if(s[i]=='L')x--;
            if(s[i]=='R')x++;
            if(s[i]=='U')y++;
            if(s[i]=='D')y--;
            if(vis[mp(x,y)])
            {
                int tmp=i-vis[mp(x,y)];
                if(ans>tmp)
                {
                    ans=tmp;
                    L=vis[mp(x,y)];
                    R=i-1;
                }
            }
            vis[mp(x,y)]=i;
        }
        if(L==-1)puts("-1");
        else printf("%d %d\n",L,R);
    }
    return 0;
}

D - Fight with Monsters
首先看这个怪是不是给予其最后一击的就是自己，是的话ans++；
再看这个怪轮流打完后剩的血量（此时所剩血量对手能够直接秒），就求得$yu=h_i\bmod (a+b)$的值，再看$yu$的值除以$a$，即自己还需要打多少下。
之后将所有的$yu/a$存起来，从小到大排序，贪心即可。
代码有一些细节要注意，比如说$yu=0$之类的。

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,a,b,k;
const int N=200050;
int h[N];
int ans;
vector <int> v;
int main()
{
    cin>>n>>a>>b>>k;
    for(int i=1;i<=n;++i)scanf("%d",&h[i]);
    for(int i=1;i<=n;++i)
    {
        int yu=h[i]%(a+b);
        if(yu<=a&&yu>0)ans++;
        else
        {
            if(yu==0)v.push_back((a+b)/a+(((a+b)%a)>0));
            else v.push_back(yu/a+(yu%a>0));
        }
    }
    sort(v.begin(),v.end());
    for(auto yu:v)
    {
        int cnt=yu-1;
        if(k>=cnt)ans++,k-=cnt;
    }
    cout<<ans<<endl;
    return 0;
}

E1 - String Coloring (easy version)
E2 - String Coloring (hard version)
这题有一点dp的味道，我们可以发现若$i<j,s_i>s_j$，那么$i$和$j$肯定会被交换，也就是说这俩颜色肯定不相等。
于是可以得出一个dp方程：$dp[i]=\max\limits_{j=1}^{i-1}dp[j]+1, s_i<s_j$，然后对于同一种字母，其dp值是单调不减的，所以我们只需要维护26个max值就行。
E1代码：

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200050;
int n;
int mx[30],mx2;
char s[N];
int ans[N];
int main()
{
    cin>>n;
    scanf("%s",s+1);
    for(int i=1;i<=n;++i)
    {
        int nowmx=0;
        for(int j=s[i]-'a'+1;j<26;++j)
            nowmx=max(nowmx,mx[j]);
        mx[s[i]-'a']=nowmx+1;
        ans[i]=nowmx;
        mx2=max(mx2,nowmx+1);
    }
    if(mx2<=2)
    {
        puts("Yes");
        for(int i=1;i<=n;++i)printf("%d",ans[i]);
    }
    else puts("No");
    return 0;
}

E2代码：

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200050;
int n;
int mx[30],mx2;
char s[N];
int ans[N];
int main()
{
    cin>>n;
    scanf("%s",s+1);
    for(int i=1;i<=n;++i)
    {
        int nowmx=0;
        for(int j=s[i]-'a'+1;j<26;++j)
            nowmx=max(nowmx,mx[j]);
        mx[s[i]-'a']=nowmx+1;
        ans[i]=nowmx+1;
        mx2=max(mx2,nowmx+1);
    }
    cout<<mx2<<endl;
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    return 0;
}

F - Berland Beauty
这题真就暴力：把所有$m$个路径按照其最小权值从大到小排序，然后一个一个往树上放就行......注意判断-1的情况即可。
当然假设这个题$n,m$到1e5这些规模的时候就可以上树剖了。

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=5050;
int n,m;
int id[N][N];
struct edge
{
    int v,nxt;
}e[N<<1];
int head[N],ecnt;
void ad(int u,int v)
{
    e[++ecnt].v=v;e[ecnt].nxt=head[u];head[u]=ecnt;
}
struct querys
{
    int a,b,mn;
}q[N];
bool cmp(const querys &x,const querys &y)
{
    return x.mn>y.mn;
}
int pre[N];
int S,T;
void dfs(int u,int fa)
{
    if(u==T)return;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        pre[v]=u;
        dfs(v,u);
    }
}
int ans[N];
int main()
{
    cin>>n;
    for(int i=1;i<n;++i)
    {
        int x,y;
        cin>>x>>y;
        ad(x,y),ad(y,x);
        id[x][y]=id[y][x]=i;
    }
    cin>>m;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].mn);
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=m;++i)
    {
        mem(pre,-1);
        S=q[i].a,T=q[i].b;
        dfs(S,0);
        bool flag=false;
        int now=9999999;
        for(int j=T;pre[j]!=-1;j=pre[j])
        {
            int u=j,v=pre[j];
            if(ans[id[u][v]]){now=min(ans[id[u][v]],now);continue;}
            ans[id[u][v]]=q[i].mn;
            now=q[i].mn;
            flag=1;
        }
        if(!flag&&q[i].mn!=now)return puts("-1"),0;
    }
    for(int i=1;i<n;++i)if(!ans[i])ans[i]=1e6;
    for(int i=1;i<n;++i)cout<<ans[i]<<" ";
    return 0;
}