Codeforces Round #704 (Div. 2)

A. Three swimmers

原题链接

给你三个数a,b,c和一个p。你在p分钟将达到泳池左侧,而a到达泳池左侧时间分别是[0,a,2a,3a…]。[0,b,2b,3b…]。[0,c,2c,3c…]。求你到达后最少还需要等多久会碰上他们其中一人。


实际上不管a,b,c你到达后需要等待x=(p+a-1)/a,res=a*x-p。分别求三个的最小值即可

#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e5+5;
void solve()
{
    int t;
    cin>>t;
    while(t--){
        ll p,a,b,c;
        cin>>p>>a>>b>>c;
        ll t1=(p+a-1)/a;
        ll t2=(p+b-1)/b;
        ll t3=(p+c-1)/c;
        ll res=min(t1*a-p,min(t2*b-p,t3*c-p));
        cout<<res<<'\n';    
    }
}
int main() {
    solve();
    return 0;
}

B. Card Deck

原题链接

给你一副牌,下标从小到大对应牌从下到上,你每次可以选择一个k,然后从k到最后放到另一个地方,牌的顺序是按照下标对应从下到上,也就是说下一次选择的k,从k到最后继续放另一个地方的时候是压在之前方的地方上面的。直至第一副牌空为止,求这样操作之后的使得[ n n − 1 ∗ a [ 0 ] + n n − 2 ∗ a [ 1 ] + . . . n 0 ∗ a [ n − 1 ] n^{n-1}*a[0]+n^{n-2}*a[1]+...n^0*a[n-1] nn−1∗a[0]+nn−2∗a[1]+...n0∗a[n−1]]最大。


实际上就是最后的数组要尽可能大数在前边。那么每次肯定选择最大值和之后的往另一个地方放,继续选择次大值,范围1e5。那么就必须来维护这个最大值。用一个vis数组即可。

#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N],vis[N];
void solve()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        int last=n;
        stack<int>s;
        memset(vis,0,sizeof vis);
        for(int i=n;i>=1;i--){
            vis[a[i]]=1;
            s.push(a[i]);
            if(a[i]==last){
                while(s.size()){
                    cout<<s.top()<<' ';
                    s.pop();    
                }
                while(vis[last])last--;
            }
        }
        cout<<'\n';
    }
}
int main() {
    solve();
    return 0;
}

C. Maximum width

原题链接

给你两个串a和b,然后b去匹配a,(保证一定能匹配成功)。把a数组匹配的下标存起来求相邻的最大值。


一开始只是反正匹配一次,发现样例2就过不了,后来接着群友口胡,正匹配一次。求相邻最大值即可

#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=3e5+5;
int res1[N],res2[N];
void solve()
{
    // int t;
    // cin>>t;
    // while(t--){
        int n,m,ans=0;
        cin>>n>>m;
        string s1,s2;
        cin>>s1>>s2;
        for(int i=0,j=0;i<n&&j<m;i++){
            if(s1[i]==s2[j]){
                res1[j]=i;j++;
            }
        }
        for(int i=n-1,j=m-1;i>=0&&j>=0;i--){
            if(s1[i]==s2[j]){
                res2[j]=i;
                j--;
            }
        }
        for(int i=1;i<m;i++){
            ans=max(res2[i]-res1[i-1],ans);
        }
        cout<<ans<<'\n';
}
int main() {
    solve();
    return 0;
}
//5 4 1
上一篇:Codeforces Round #704 DIv.2 A B C D


下一篇:Codeforces Round #704 (Div. 2)A,B,C,D