answerend42的Blog 主页归档标签分类关于
第一次CF比赛
|比赛
字数总计: 1.9k|阅读时长: 8 分钟

CF上的题目确实值得一做，打比赛是提升代码水平的好方法。

参赛感想

​ 我参加的第一场 CF 比赛是 Educational Codeforces Round 84 (Rated for Div. 2)。我很早就注册了CF账号，但是打比赛还是第一次。原先总觉得CF的题都好难，实际上真正去做的时候发现自己只要有时间还是可以做出来几题的。CF的题目是典型的思维题，没有思维很难想到。最终的码量都不会很大（这让我在最后时刻抢着把 B 题做完了）。（非常感谢 too_late 对我的鼓励）

题解（只有 A,B,C）

A Sum of Odd Integers

题目描述

给定 $n,k$,求是否能用 $k$ 个不同奇数的和来表示 $n$。

输入输出格式

输入格式

第一行一个正整数 $t(1\leq t\leq 10^5)$

之后 $t$ 每行两个正整数 $n,k(1\leq n,k \leq 10^7)$

输出格式

如果有解，输出 YES，否则输出 NO。

输入输出样例

输入1：

1
2
3
4
5
6
7
6
3 1
4 2
10 3
10 2
16 4
16 5

输出1：

1
2
3
4
5
6
YES
YES
NO
YES
YES
NO

解法

​ 这一题一开始先手玩了一下

数字 $n$ 可以满足的 $k$ 解释
$1$ $1$ $1=1$
$2$ 无 $1+3=4>2$
$3$ $1$ $3=3$
$4$ $2$ $1+3=4$
$5$ $1$ $5=5$
$6$ $2$ $1+5=6$
$7$ $1$ $7=7$
$8$ $2$ $3+5=8$
$9$ $1,3$ $9=9$,$1+3+5=9$

可以发现一个规律，$n,k$ 的奇偶性都是相同的，也许并不那么显然。还有一个规律，所有满足条件的 $k$ 都是小于 $\sqrt n$ 的，这个题目的证明可以参照 jijidawang 的博客。

得出

$n-k^2\ge 0$ 且 $(n-k^2)\bmod 2=0$ 是有解的充要条件。

代码就呼之欲出了（但是很坑的是计算 $k^2$ 要开 long long）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
inline long long read()
{
    char ch=getchar();long long ret=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getchar();}
    return ret*f;
}
long long t,n,k;
int main()
{
    t=read();
    while(t--)
    {
        n=read(),k=read();
        printf("%s",n%2==k%2&&n>=k*k?"YES\n":"NO\n");
    }
    return 0;
}

B Princesses and Princes

题目描述

有 $n$ 个公主和王子，每个公主依次选择她喜欢并且没有结婚的王子结婚，问能不能让一个公主再多喜欢一个王子，使得最终配对的对数更多。

输入输出格式

输入格式

第一行一个正整数 $t(1\leq t\leq 10^5)$

之后 $t$ 组数据

每组数据第一行 $1$ 个正整数 $n(1\leq n \leq 10^5)$

接下来 $n$ 行每行第一个正整数 $k(0\leq k\leq n)$ 随后 $k$ 个正整数表示第 $i$ 个公主可以配对的王子编号

输出格式

如果可以通过加入一个不在公主喜欢名单中的王子到这个公主的喜欢名单中使得配对数更多，输出两行，第一行 IMPROVE，第二行两个对应的公主王子编号，否则输出一行，OPTIMAL。

输入输出样例

输入1 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
5
4
2 2 3
2 1 2
2 3 4
1 3
2
0
0
3
3 1 2 3
3 1 2 3
3 1 2 3
1
1 1
4
1 1
1 2
1 3
1 4

输出1 :

1
2
3
4
5
6
7
IMPROVE
4 4
IMPROVE
1 1
OPTIMAL
OPTIMAL
OPTIMAL

解法

非常简单的模拟。（但是要注意不要使用 memset 会超时，直接 for 赋值就好了）

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
#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],n,t,m,p;
inline int read()
{
    char ch=getchar();int ret=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getchar();}
    return ret*f;
}
int main()
{
    t=read();
    while(t--)
    {

        int flag1=0,flag2=0;
        n=read();
        for(int i=1;i<=n;i++) a[i]=b[i]=0;
        for(int i=1;i<=n;i++)
        {
            m=read();
            for(int j=1;j<=m;j++)
            {
                p=read();
                if(b[p]==0&&a[i]==0) a[i]=1,b[p]=1;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i]==0) flag1=i;
            if(b[i]==0) flag2=i;
            if(flag1&&flag2) break;
        }
        if(flag1&&flag2)
        {
            printf("IMPROVE\n%d %d\n",flag1,flag2);
        }
        else
        {
            printf("OPTIMAL\n");
        }
    }
    return 0;
}

C Game with Chips

题目描述

Petya 有一个大小为 $n×m$ 的矩形版。一开始，在板子上有 $k$ 个芯片，第 $i$ 个芯片位置位于第 $sx$ 行与第 $sy$ 列的相交点上。

在一次操作中， Petya 可以把所有的芯片向左、向右、向下或者向上移动一格。

如果芯片在 $(x, y)$ 格中，则在操作之后：

  • 往左：坐标为 $(x, y - 1)$;
  • 往右：坐标为 $(x, y + 1)$;
  • 往下：坐标为 $(x + 1, y)$;
  • 往上：坐标为 $(x - 1, y)$;

如果现在芯片在版的边缘上，然而 Petya 将其移向边缘，那么芯片的位置保持不变。

对于每一个芯片， Petya 选择了它应该到达的位置。注意 芯片不需要在这个地方停下来。

由于 Petya 时间不多， 总操作数不能超过 $2nm$。

你需要求出 Petya 应该做的操作：在不超过 $2nm$ 次的操作里让每个芯片走过 Petya 选定的位置一遍。或者说明是不可能达到目的的。

输入输出格式

输入格式

第一行三个正整数 $n,m,k ( 1 \le n, m, k \le 200)$

接下来 $k$ 行每行两个正整数 $sx,sy$ 表示每个芯片的初始位置

接下来 $k$ 行每行两个正整数 $fx,fy$ 表示每个芯片应该经过的位置

输出格式

在第一行中输出操作的次数，以便每个芯片至少访问一次 Petya 为其选择的位置。
在第二行中输出操作序列。为了表示左、右、下和上的操作，分别使用字符 L,R,D,U。
如果所需的序列不存在，请在单行中打印 -1。

输入输出样例

输入1：

1
2
3
4
5
3 3 2
1 2
2 1
3 3
3 2

输出1：

1
2
3
DRD

输入2：

1
2
3
4
5
6
7
5 4 3
3 4
3 1
3 3
5 3
1 3
1 4

输出2：

1
2
9
DDLUUUURR

解法

​ 奇妙思路，将所有芯片通过至多 $m-1$ 次向右的操作和至多 $n-1$ 次向下的操作放到右下角，然后暴力扫一遍，总共的次数 $mn+m+n-3<2nm$ 。但是要特判 $n+m>nm$ 的情况，也很简单。所以说，这一题和 $k,sx,sy,fx,fy$ 无关直接输出方案就行了。

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
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    char ch=getchar();int ret=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getchar();}
    return ret*f;
}
int n,m,k,idx;
int main()
{
    n=read(),m=read(),k=read();
    if(n==1) 
    {
        printf("%d\n",m*2-2);
        for(int i=1;i<=m-1;i++)printf("R");
        for(int i=1;i<=m-1;i++)printf("L");
        return 0;
    }
    if(m==1) 
    {
        printf("%d\n",n*2-2);
        for(int i=1;i<=n-1;i++)printf("D");
        for(int i=1;i<=n-1;i++)printf("U");
        return 0;
    }
    printf("%d\n",m*n+m+n-3);
    for(int i=1;i<=m-1;i++)printf("R");
    for(int i=1;i<=n-1;i++)printf("D");
    while(idx!=m)
    {
        for(int i=1;i<=n-1;i++)printf("%c",idx%2==0?'U':'D');
        idx++;
        if(idx==m) break;
        printf("L");
    }
    return 0;
}

D E F G我都不会，也没时间去做了，如果以后做了会放代码的

总结

第一次 CF 的体验还是很不错的，就是没有那种竞赛的状态，速度也提不上来（再次证明我的题做的太少了），感谢观看。

文章作者: answerend42
文章链接: http://answerend42.github.io/2020/03/24/%E7%AC%AC%E4%B8%80%E6%AC%A1CF%E6%AF%94%E8%B5%9B/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog！
模拟数论数学贪心奇偶性