Codeforces Round #620 (Div. 2)

A Two Rabbits

两只兔子，一只在x,每秒向右跳a，一只在y（x<y）每秒向左跳b
问它们在第几秒能相遇，不能相遇输出-1
取模判断一下就行了

代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define Pll make_pair
using namespace std;
typedef long long ll;
const int MAXN=1e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int phi=1e9+6;
ll quick(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        ll x,y,a,b;
        cin>>x>>y>>a>>b;
        if(x>y){
            cout<<-1<<endl;
            continue;
        }
        if((y-x)%(a+b)==0){
            cout<<(y-x)/(a+b)<<endl;
        }
        else
            cout<<-1<<endl;
    }
    return 0;
}
/*

 */

B Longest Palindrome

给n个长度为m的字符串，问删掉一些字符串，能组成的最长的回文串

先判断对于每个字符串能否找到跟它配对的，如果不能，再判断它本身是不是回文串，如果是，它就可以放在最中间增加长度，但只能放一个这样的，不然不能组成回文串

代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define Pll make_pair
using namespace std;
typedef long long ll;
const int MAXN=1e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int phi=1e9+6;
ll quick(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}
string f[150];
int a[150];
int b[150];
int vis[150];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>f[i];
    int c1=0,c2=0;
    for(int i=1;i<=n;i++){
        string s;
        s=f[i];
        reverse(s.begin(),s.end());
        //cout<<s<<endl;
        int flag=0;
        if(s==f[i]){
            flag=1;
        }
        for(int j=1;j<=n;j++){
            //cout<<s<<endl;
            //cout<<f[j]<<endl;
            if(j!=i&&vis[j]==0&&f[j]==s){
                b[++c2]=i;//能配对
                vis[i]=vis[j]=1;//它们两个配对之后，就不能用了
                flag=8;
                break;
            }
        }
        if(flag==1)a[++c1]=i;
    }
    string ans="",p;
    //cout<<c1<<" "<<c2<<endl;
    for(int i=1;i<=c2;i++)ans+=f[b[i]];
    p=ans;
    reverse(p.begin(),p.end());
    if(c1>=1)ans+=f[a[1]];//如果有本身是回文串且没有配对的，可以在正中间放一个（长度都是m，随便放一个就行）
    ans+=p;
    cout<<ans.size()<<endl;
    cout<<ans<<endl;
    return 0;
}
/*

 */

C Air Conditioner

维护一个区间，最后看区间还有没有元素
最初的区间为[m,m]
每次来新的顾客，与它取交集，如果为空了，说明不能满足所有人

代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define Pll make_pair
using namespace std;
typedef long long ll;
const int MAXN=1e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int phi=1e9+6;
struct sa{
    ll x;
    ll y;
    ll t;
}p[150];
int flag;
ll l,r;
void quj(ll a,ll b,ll c,ll d){//[a,b]  [c,d]的交集
    flag=1;
    if(b<c||d<a){
        flag=0;
        return ;
    }
    if(a<=c&&c<=b&&b<=d){
        l=c;r=b;
        return ;
    }
    if(c<=a&&b<=d){
        l=a,r=b;
        return ;
    }
    if(a<=c&&d<=b){
        l=c,r=d;
        return ;
    }
    if(c<=a&&a<=d&&d<=b){
        l=a,r=d;
        return ;
    }
}
int main()
{
    int q;
    cin>>q;
    while(q--){
        int n,m;
        cin>>n>>m;
        l=r=m;
        for(int i=1;i<=n;i++)cin>>p[i].t>>p[i].x>>p[i].y;
        for(int i=1;i<=n;i++){
            if(i==1) {
                l -= p[i].t;
                r += p[i].t;
            }
            else{
                l -= (p[i].t-p[i-1].t);
                r += (p[i].t-p[i-1].t);
            }
            quj(l,r,p[i].x,p[i].y);
            //cout<<l<<" "<<r<<endl;
            if(flag==0)break;
        }
        if(flag==1)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
/*

 */

D Shortest and Longest LIS

给一个长度为n-1字符串全是 > 和 <
然后把1-n，这n个数，填进去，使其满足所有字符
然后输出所有满足的里面，最长递增子序列，最短和最长的
开始先为这个序列附值
最短时：n ,n-1,n-2,n-3…3,2,1(这样才能使最长递增子序列最短)
遇到$>$>时，因为本来就满足，所以不变，遇到$<$<,看后面还有几个$<$<，然后把这之间的数翻转
最长时：1,2,3,4,…n-1,n
遇到$<$<时，因为本来就满足，所以不变，遇到$>$>,看后面还有几个$>$>，然后把这之间的数翻转
ls:tmd,比赛时没交上，赛后一交就A，…

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define Pll make_pair
using namespace std;
typedef long long ll;
const int MAXN=2e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int phi=1e9+6;
char ch[MAXN];
int a[MAXN];
int main()
{
    int n,q;
    scanf("%d",&q);
    while(q--){
        scanf("%d ",&n);
        scanf("%s",ch+1);
        //cout<<ch+1<<endl;
        for(int i=1;i<=n;i++)a[i]=n-i+1;
        int l,r;
        for(int i=1;i<=n-1;i++){
            if(ch[i]=='>')continue;
            //cout<<ch[i]<<endl;
            l=i;
            while(ch[i]=='<')
                i++;
            r=i;
            reverse(a+l,a+r+1);//翻转
        }
        for(int i=1;i<=n;i++)printf("%d%c",a[i],i==n?'\n':' ');
        for(int i=1;i<=n;i++)a[i]=i;
        for(int i=1;i<=n-1;i++){
            if(ch[i]=='<')continue;
            l=i;
            while(ch[i]=='>')
                i++;
            r=i;
            reverse(a+l,a+r+1);
        }
        for(int i=1;i<=n;i++)printf("%d%c",a[i],i==n?'\n':' ');
    }
    return 0;
}
/*
3
7 >><>><
 */

后面的还没看题，太菜了