Codeforces Round 703&704 （div 2)

Codeforces Round #703&704 (div 2)

  

#703

A Shifting Stacks (1486A)

签到题，只需从 i=n 开始对前 i 项求和，判断该和的值是否不小于 (i-1) * i/2 ，i 逐步递减，直到 i=1 。如果均满足和值不小于 (i-1) * i/2，输出 “ YES ” 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
using namespace std;

long long computesum(int a[],int len)
{
    long long sum=0;
    for(int i=0;i<len;i++)
    sum+=a[i];
    return sum;
}


int main()
{
    int x;
    cin>>x;
    for(int j=0;j<x;j++)
    {
            int n;
    cin>>n;
    int a[n]={0};
    long long sum=0;
    for(int i=0;i<n;i++)
    cin>>a[i];
    bool test=1;
    for(int i=1;i<=n;i++)
    {
        long long s=computesum(a,i);
        if(s<((i*(i-1))/2))
        {
            test=0;
            break;
        }
    }
    if(test)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    }
}

 

B Eastern Exhibition (1486B)

找中位数的个数，因为是曼哈顿距离，所以横纵坐标互不影响，可以分别求横距离和纵距离后再求和。对于一个维度，如果房子个数为奇数，就只有中位数代表的位置是 “最优解” ，个数为 1；房子个数为偶数，则最中间的两个房子之间的所有位置（包括其本身所在位置）均为“ 最优解 ”。最后将两个维度的 “ 最优解 ”个数相乘即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<algorithm>
using namespace std;
 
int main()
{
    long long num;
    cin>>num;
    for(long long i=0;i<num;i++)
    {
        long long x[1001]={0},y[1001]={0};
    long long n;
    cin>>n;
    for(long long i=0;i<n;i++)
    cin>>x[i]>>y[i];
    if((n%2)==1)cout<<1<<endl;
    else
    {
        sort(x,x+n);
        sort(y,y+n);
        long long a=x[n/2]-x[n/2-1]+1;
        long long b=y[n/2]-y[n/2-1]+1;
        long long c=a*b;
        cout<<c<<endl;
    }
    }
}

 

 

#704

A Three Swimmers (1492A)

签到题，用 p 模游泳一来回的时间，再用该时间减去上一步模的结果。注意模的结果如果为 0 ，那就直接得到 0 这一结果而不用减。这一步实际上是算 “ 这个人还有多久游回来” 。最后找三个结果的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#define LL long long 
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        LL x,a,b,c;
        cin>>x>>a>>b>>c;
        if(x%a)a=a-x%a;
        else a=0;
        if(x%b)b=b-x%b;
        else b=0;
        if(x%c)c=c-x%c;
        else c=0;
        LL r;
        r=a;
        if(r>b)r=b;
        if(r>c)r=c;
        cout<<r<<endl;
    }
}

 

B Card Deck (1492B)

题意是不断从后面开始截取原数组的一段，原封不动地放到新数组的后面。直接从原数组中找最大的数，然后将其之后的所有数截取下来放到新数组后。在原数组剩下的数中不断重复该操作，直至全部移动完。但是本题对时间的要求比较高，所以在实际操作中，可以先记录下所有 “ 剩下的数里面最大数的位置 ”，方法是从左端开始，只要出现比左侧值更大的数，就把这个数的位置记录一次，那么扫描结束之后从右往左的这些位置就依次是每次操作的 “ 截取点 ”，从而避免了对剩下的数的重复搜索。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<algorithm>
#define LL long long
#define inf 100010
using namespace std;

int a[inf],b[inf],c[inf],an,cn=0,curr=0;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cn=0;curr=0;
        cin>>an;
        for(int i=0;i<an;i++)
        {
            cin>>a[i];
            if(curr<a[i])
            {
                curr=a[i];
                c[cn]=i;
                cn++;
            }
        }
        int l=0,r=an,t=0;
        cn--;
        while(cn!=-1)
        {
            for(int i=0;i<r-c[cn];i++)
            *(b+t+i)=*(a+c[cn]+i);
            t+=r-c[cn];
            r-=(r-c[cn]);
            cn--;
        }
        for(int i=0;i<an;i++)
        cout<<b[i]<<" ";
    }
}

 

C Maximum Width (1492C)

啥也别说了，看了题解才做出来……

简单说一下思路。对于 t 串中的第 i 个元素，可以在 s 串中找到最靠左侧的能满足要求的一个元素，也有最靠右的这样的元素。找出这些元素的位置（用一个 int 表示排在第几位）。找最靠左侧的满足要求的元素，就是从 t 串的第一个元素开始，在 s 串中从左端开始一直向右找对应元素，不能向左返回。注意找到对应元素之后指针一定要再向右移动一位。最靠右侧的同理。最后从 0 开始到 m-2为止找 max( 右(i + 1) - 左i )。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
int main()
{
    char a[200005],b[200005];
    int n,m;
    int min[200005],max[200005];
    cin>>n>>m;
    int pa=0;
    for(int i=0;i<n;i++)
    cin>>a[i];
    cin>>b[0];
    while(a[pa]!=b[0])pa++;
    min[0]=pa;
    pa++;
    for(int i=1;i<m;i++)
    {
        cin>>b[i];
        while(a[pa]!=b[i])pa++;
        min[i]=pa;
        pa++;
    }
    pa=n-1;
    for(int i=m-1;i>=0;i--)
    {
        while(a[pa]!=b[i])pa--;
        max[i]=pa;
        pa--;
    }
    int ans=0,curr=0;
    for(int i=0;i<m-1;i++)
    if(ans<(curr=max[i+1]-min[i]))ans=curr;
    cout<<ans;
}

 

 

 

剩下的题看能不能哪天去补吧……