Codeforces Round 705&707 (div 2)

Codeforces Round #705&707 (div 2)

 

这两场实在是鸽了太久……#705那场成功渡劫上了绿名（不影响我菜）#707算是在绿名打的第一场

CF Round #705

A Anti-knapsack (1493A)

思维题+签到题

题意大致是找一组不同的数，这些数在 1 到 n 之间，这组数里面不能有两个或多个元素的和等于 k ；

显然如果 n 大于 k ，k 到 n 的数都是可以的；只需在 1 到 k 中找。考虑到一个数能分解为 ( 1 + ( k - 1 ) ) 、( 2 + ( k - 2 ) ) ……这样的形式，那么不难看出，选择 1 到 k 右半边的数字时，元素最多。

题解

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
#include<iostream>
using namespace std;

int a[1010];


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        cout<<n-k+k/2<<endl;
        if(n-k+k/2!=0)
        {
            for(int i=k+1;i<=n;i++)
            cout<<i<<" ";
            for(int i=(k+1)/2;i<k;i++)
            {
                cout<<i<<" ";             
            }
            cout<<endl;
        }                  
    }
    return 0;
}

 

B Planet Lapituletti (1493B)

模拟，某种意义上比第一题还简单 （没错我就这么幸运地到了绿名）

注意哪几个数字对称，对称过去是什么数字即可

题解

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
using namespace std;

int form(int a,int b)
{
    return (a*10+b);
}

int a[10]={0,1,5,-1,-1,2,-1,-1,8,-1};

bool test(int sh,int smin,int h1,int h2,int min1,int min2)
{
    bool test=1;
    if(a[h1]==-1||a[h2]==-1||a[min1]==-1||a[min2]==-1)
    return false;
    else
    {
        int h=form(a[min2],a[min1]);
        int min=form(a[h2],a[h1]);
        if(h>=sh||min>=smin)return false;
        else return true;
    }   
}


int main()
{
    int t;
    cin>>t;
    while(t--)
{
    int sh,smin;
    cin>>sh>>smin;
    char input[5];
    for(int i=0;i<5;i++)cin>>input[i];
    int h1=input[0]-48;
    int h2=input[1]-48;
    int min1=input[3]-48;
    int min2=input[4]-48;
    while(1)
    {
        if(test(sh,smin,h1,h2,min1,min2))break;
        else
        {
            min2++;
            if(min2==10)
            {
                min2=0;
                min1++;
            }
            if(form(min1,min2)==smin)
            {
                min1=0;min2=0;h2++;
            }
            if(h2==10)
            {
                h1++;
                h2=0;
            }
            if(form(h1,h2)==sh)
            {
                h1=0;h2=0;
            }

        }
    }
    cout<<h1<<h2<<":"<<min1<<min2<<endl;
}
    return 0;
}

 

 

CF Round #707

A Alexey and Train (1501A)

模拟题+签到题

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[105],b[105],c[105],t[105];t[0]=0;a[0]=0;b[0]=0;
        for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
        for(int i=1;i<=n;i++)
        {
            cin>>c[i];
            t[i]=max(t[i-1]+(b[i-1]-a[i-1]+1)/2,b[i-1])+c[i]+a[i]-b[i-1];            
        }
        cout<<t[n]<<endl;
    }
    return 0;
}

 

B Napoleon Cake (1501B)

模拟，但是一般的模拟会超时，考虑优化。

我的想法：因为下方的酱不会影响上方的饼， 所以考虑从后往前模拟，在把一些端点值设置为 1 的同时去除掉那些不能作为最终端点的 “ 1 ” 。最后数组中有偶数个 1 ，每两个 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstring>
using namespace std;

int main()
{

    int t;
    cin>>t;
    while(t--)
    {
        bool x[200010]={0};
        int a[200010];
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        int curr=200010;
        for(int i=n;i>0;i--)
        {
            if(a[i]==0)continue;
            else
            {
                if(i<curr)
                {
                    x[i]=1;
                    x[(curr=max(i-a[i],0))]=1;
                }
                else
                {
                    if(curr>max(i-a[i],0))
                    {
                        x[curr]=0;
                        x[(curr=max(i-a[i],0))]=1;
                    }
                    else continue;
                }                
            }
        }
        //for(int i=0;i<n;i++)cout<<x[i]<<' ';cout<<endl;
        bool test=x[0];
        for(int i=1;i<=n;i++)
        {            
            cout<<test<<' ';
            if(x[i])test=bool(1)^test;
        }
        cout<<endl;
    }
    return 0;
}

 

其他方法（某大佬给出） ：

碰到酱料时在两端点位置插入标识 （类似于对括号的判断），即“ 当左括号数量大于右括号的数量 ”的时候，碰到的饼是浸润的；不满足该条件时是不浸润的。