Codeforces Round #605 (Div. 3) A~E

比赛链接

日常训练，E题完善了一下我的最短路，挺好的。

A - Three Friends

题意：给定a,b,c三人在x轴上的坐标，现在每个人都可以向左移动一格或向右移动一格或不动，问|ab|+|ac|+|bc|的最小值。
思路：在移动完以后求这个值很容易看出是最左边和最右边的点的距离乘2，所以让这两个点距离最近即可，所以我们可以先排序，左右两个点尽量靠近即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=100+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=100003;
const double pi=4*atan(1.0);
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        int a[3];
        cin>>a[0]>>a[1]>>a[2];
        sort(a,a+3);
        if(a[2]==a[0])
            cout<<0<<endl;
        else if(a[2]==a[0]+1)
            cout<<0<<endl;
        else
            cout<<2*(a[2]-a[0]-2)<<endl;
    }
}

B - Snow Walking Robot

题意：给定一个由R,D,U,L构成的字符串，分别代表向右，向下，向上，向左移动一格的指令，要求从这串字符串中删去最小的字符，并重新排序，使该点能回到原点，且除原点外没有点被经过两次。
思路：首先可以确定的是U和D，R和L必然是一样的,所以u=d=min(u,d)，r=l=min(r,l)，然后我们通过观察可以得知，在u和r都不等于0时，只需要走一个矩形就可以不经过一个点第二次回到原点，比如URDL。而其中有一个为0，假如R为0，那么只剩U和D，容易看出，只有UD和DU满足条件。另外特判全为0的情况。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=100003;
const double pi=4*atan(1.0);
char s[MAX_N];
int l,r,u,d;
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        scanf("%s",s);
        int i;
        l=r=u=d=0;
        for(i=0;s[i];i++)
        {
   
            if(s[i]=='L')
                l++;
            else if(s[i]=='R')
                r++;
            else if(s[i]=='U')
                u++;
            else
                d++;
        }
        l=min(l,r);
        u=min(u,d);
        if(u==0&&l==0)
        {
   
            cout<<0<<endl;
            cout<<endl;
        }
        else if(u==0)
        {
   
            cout<<2<<endl;
            cout<<"LR"<<endl;
        }
        else if(l==0)
        {
   
            cout<<2<<endl;
            cout<<"UD"<<endl;
        }
        else
        {
   
            cout<<(l+u)*2<<endl;
            for(i=1;i<=l;i++)
                cout<<"L";
            for(i=1;i<=u;i++)
                cout<<"U";
            for(i=1;i<=l;i++)
                cout<<"R";
            for(i=1;i<=u;i++)
                cout<<"D";
            cout<<endl;
        }
    }
}

C - Yet Another Broken Keyboard

题意:给定一个字符串，再给定几个字符，要求得出该字符串中所有不含这些字符以外的子串的数目。
思路:相当于说不在规定字符中的字符不能出现在截取的子串中，那么只需把用这些不合规定的字符将字符串切割成若干个字符串，那么这些字符串的所有子串必然符合规定，一个字符串的所有子串数目是(1+len)*len/2，注意，将开头和结尾都看作不合规定的字符。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=100003;
const double pi=4*atan(1.0);
char s[MAX_N];
int vis[30];
int main()
{
   
    int n,k;
    cin>>n>>k;
    scanf("%s",s+1);
    int i;
    for(i=0;i<k;i++)
    {
   
        char c;
        cin>>c;
        vis[c-'a']=1;
    }
    int flag=0;
    ll ans=0;
    for(i=1;s[i];i++)
    {
   
        if(vis[s[i]-'a']==0)
        {
   
            int len=i-flag-1;
            ans+=(ll)(1+len)*len/2;
            flag=i;
        }
    }
    int len=i-flag-1;
    ans+=(ll)(1+len)*len/2;
    cout<<ans<<endl;
}

D - Remove One Element

题意：给定一个序列，要求从中去掉一个数字或者不去任何数字后，求新序列的最大严格增长序列长度。
思路：用动态规划，dp1[i]代表以i结尾，没有别去掉任何数字的增长序列的最大长度，dp2[i]代表以i结尾，去掉过一个数字的增长序列的最大长度。
所以dp1[i]必然是dp1[i-1]推过来，而dp2[i]就有可能从dp1[i-1]推过来，也有能从dp2[i-1]推过来，前者的话代表之前还没去掉过数字，那我们要把num[i-1]去掉，然后通过num[i-2]确定，后者直接通过num[i-1]确定。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=100003;
const double pi=4*atan(1.0);
int a[MAX_N];
int dp1[MAX_N];
int dp2[MAX_N];
int main()
{
   
    int n;
    cin>>n;
    int i;
    for(i=1; i<=n; i++)
        scanf("%d",&a[i]);
    dp1[1]=1;
    dp2[1]=1;
    int mx=0;
    for(i=2; i<=n; i++)
    {
   
        if(a[i]>a[i-1])
        {
   
            dp1[i]=dp1[i-1]+1;
            dp2[i]=dp2[i-1]+1;
            if(a[i]>a[i-2])
                dp2[i]=max(dp2[i],dp1[i-2]+1);
            else
                dp2[i]=max(dp2[i],1);
        }
        else
        {
   
            dp1[i]=1;
            dp2[i]=1;
            if(a[i]>a[i-2])
                dp2[i]=max(dp2[i],dp1[i-2]+1);
            else
                dp2[i]=max(dp2[i],1);
        }
        mx=max(mx,max(dp1[i],dp2[i]));
    }
    cout<<mx<<endl;
}

E - Nearest Opposite Parity

题意：给定序列a[]，每个a[i]代表到达这点是可以跳转至i+a[i]和i-a[i]，要求求出每个点出发，至少要跳转几次才能使跳转后的点a[j]和这个点a[i]奇偶性不同。
思路：一开始是想用dfs写，但是会成环，也处理不好回溯，后来查了题解，学到了最短路超级汇点和超级源点的技巧。这里就是设两个超级源点，一个连接所有偶数，一个连接所有奇数，然后这些数之间，反向建边，比如从奇数点出发，那么从超级奇数点到然后一个偶数点的最短距离都代表他所能到底某一个奇数点最短距离(反向思维).

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=100003;
const double pi=4*atan(1.0);
int n;
int a[MAX_N];
vector<P>v[MAX_N];
int vis[MAX_N];
int d[MAX_N];
int ans[MAX_N];
void SPFA(int x)
{
   
    int i;
    for(i=1; i<=n+2; i++)
    {
   
        vis[i]=0;
        d[i]=inf;
    }
    //for(i=1;i<=n+2;i++)
    //cout<<d[i]<<endl;
    queue<int>q;
    q.push(x);
    vis[x]=1;
    d[x]=0;
    while(!q.empty())
    {
   
        int u=q.front();
        //cout<<u<<endl;
        q.pop();
        for(auto j:v[u])
        {
   
            int vv=j.first;
            //cout<<d[u]+j.second<<' '<<d[vv]<<endl;
            if(d[u]+j.second<d[vv])
            {
   
                d[vv]=d[u]+j.second;
                if(vis[vv]==0)
                {
   
                    q.push(vv);
                    vis[vv]=1;
                }
            }
        }
    }
 
}
int main()
{
   
    cin>>n;
    int i;
    for(i=1; i<=n; i++)
    {
   
        scanf("%d",&a[i]);
        if(a[i]%2==0)//0是偶数点 n+1是奇数点
        {
   
            v[0].pb(P(i,0));
            //cout<<a[i]<<endl;
        }
        else
            v[n+1].pb(P(i,0));
        if(i-a[i]>=1)
            v[i-a[i]].pb(P(i,1));
        if(i+a[i]<=n)
        {
   
            v[i+a[i]].pb(P(i,1));
        }
    }
    SPFA(0);
    me(ans,-1);
    for(i=1; i<=n; i++)
    {
   
        if((a[i]%2)&&d[i]!=inf)
            ans[i]=d[i];
    }
    SPFA(n+1);
    for(i=1; i<=n; i++)
    {
   
        if(a[i]%2==0&&d[i]!=inf)
            ans[i]=d[i];
    }
    for(i=1; i<=n; i++)
    {
   
        cout<<ans[i];
        if(i==n)
            cout<<endl;
        else
            cout<<' ';
 
    }
}