[2022冬季训练]个人自测赛(一)题解与体会

自2019年CSP-J以来，浩熙再也没有参加过有关算法的正式比赛和考试。虽然其中经历过转专业考试和新生赛，但是个人觉得这些考试运用算法的很少，虽然新生赛也有算法题，但是还是以代码水平为主。因此，本次比赛算是浩熙三年后再一次参加的第一场算法比赛，是浩熙从一名OIER到一名ACMer转变的第一步。因此本次考试对于浩熙的意义是非同寻常的。

总体看下来，三道题一血，RANK6的成绩也还算不错。不过具体到题上，我们可以发现此次考试题其实多数是在提高组难度的，但浩熙现在却只会切模拟搜索和贪心题，对于图论和DP等已经很手生了。

所以下一步，要进行的大规模集训分为两部分，第一部分为回顾，第二部分为知新。这两者并不冲突，相反可以相辅相成。

最后，感谢浩熙的室友Hilton和fatak，让浩熙有了坚持和前进的动力。320ACM，冲！

1.CF1256A Payment Without Change

1.1 题目描述（传送门）

1.1.1 题目大意

你有 $a$ 枚 $n$ 元硬币和 $b$ 枚 $1$ 元硬币，问是否可以拿出 $x(0\leq x \leq a)$ 枚 $n$ 元硬币和 $b(0\leq y \leq b)$ 枚 $1$ 元硬币，使得总和为 $S$ （或者说是否可以在不找零的情况下买价值为 $S$ 的物品）。共有 $q$ 组提问。

1.1.2 输入格式

第一行一个整数 $q(1\leq q \leq 10^4)$ 。

接下来 $q$ 行，每行四个整数 $a,b,n,s$ 。 $1\leq a,b,n,S \leq 10^9$ 。

1.1.3 输出格式

共 $q$ 行。每行”YES”或”NO”，表示是否可以在不找零的情况下买价值为 $S$ 的物品。

1.1.4 样例

输入 #1

1 2 3 4

1 2 3 6

5 2 6 27

3 3 5 18

输出 #1

YES
NO
NO
YES

YES

1.2 解题思路

贪心。先尽可能的用 $n$ 元硬币，判断剩余钱数是否可以用 $1$ 元硬币支付。

$t=min(a,S/n)$ 为n元硬币的使用数，再判断 $S-n\timest$ 和 $b$ 的大小关系。后者大于等于前者即可以支付，否则不可以。

1.3 解题代码

#include <iostream>
using namespace std;
int q,a,b,n,S;
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d%d%d",&a,&b,&n,&S);
        int t=min(a,S/n);
        if(S-t*n<=b)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

int q,a,b,n,S;

int main()

{

scanf("%d",&q);

while(q--)

{

scanf("%d%d%d%d",&a,&b,&n,&S);

int t=min(a,S/n);

if(S-t*n<=b)printf("YES\n");

else printf("NO\n");

}

return 0;

}

1.4 解题心得

简单题就要稳准狠，考场上3min拿到一血，但是敲代码的时候可能是亢奋，手抖得很。对于比赛还是要注重心态问题，尤其后面的时候，对于难题来说也要有好的心态。

2.CF1256B Minimize the Permutation

2.1 题目描述（传送门）

2.1.1 题目大意

给你一个长度为 $n$ 的整数序列，你可以进行至多 $n-1$ 次操作，使该序列字典序最小。

操作 $i(1 \leq i \leq n-1)$ 是交换序列中 $i$ 和 $i+1$ 的元素，操作 $i$ 最多执行一次。

共有 $q$ 组提问。

2.1.2 输入格式

第一行一个整数 $q(1\leq q \leq 100)$ 。

接下来 $q$ 组输入，每组输入两行。

每组的第一行为一个整数 $n(1 \leq n \leq 100)$ 。

每组的第二行为 $n$ 个整数，表示给的长度为 $n$ 的整数序列。

2.1.3 输出格式

共 $q$ 行。输出每组的答案。

对于每组，输出 $n$ 个整数，为最多 $n-1$ 次交换后得到的字典序最小的序列。

2.1.4 样例

输入 #1

5 4 1 3 2

1 2 4 3

4 3 2 1

输出 #1

1 5 2 4 3

1 2 3 4

1 4 3 2

2.2 解题思路

交换相邻元素使字典序最小，这使我们想到了冒泡排序。但这道题每个位置只能交换一次，所以在冒泡排序的基础上记录每个位置是否进行过操作即可。

冒泡排序有向前（向小）和向后（向大）两种方法。对于本题，如果向后冒的话，无法达到字典序最小，因为我们要尽可能让最小的数字在最前面，而每个位置只能操作一次。所以我们应该从后向前遍历（注意是从 $n-1$ 开始），每次遍历都判断当前元素和后面紧邻它的元素的大小关系即是否可以进行操作。经过若干次遍历后，整个序列不会再改动，即得出最优解。

2.3 解题代码

#include <iostream>
using namespace std;
int q,n;
int a[110];
bool f[110];//当前位置是否进行过操作
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            f[i]=0;
        }
        bool flag=true;//本轮遍历是否有改动
        while(flag)
        {
            flag=false;
            for(int i=n-1;i>=1;i--)
            {
                if(!f[i]&&a[i]>a[i+1])
                {
                    f[i]=true;
                    swap(a[i],a[i+1]);
                    flag=true;
                }
            }
        }
        for(int i=1;i<=n;i++)printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

int q,n;

int a[110];

bool f[110];//当前位置是否进行过操作

int main()

{

scanf("%d",&q);

while(q--)

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i]);

f[i]=0;

}

bool flag=true;//本轮遍历是否有改动

while(flag)

{

flag=false;

for(int i=n-1;i>=1;i--)

{

if(!f[i]&&a[i]>a[i+1])

{

f[i]=true;

swap(a[i],a[i+1]);

flag=true;

}

for(int i=1;i<=n;i++)printf("%d ",a[i]);

printf("\n");

}

return 0;

}

2.4 解题心得

本题数据范围较小，因此采用最暴力的方法进行操作，时间复杂度为 $O(pn^2)$ 。如果数据范围增大，可能会有更优算法，不过本算法解本题足够。

3.CF1256C Platforms Jumping

3.1 题目描述（传送门）

3.1.1 题目大意

有一条长度为 $n$ 的河，你站在坐标 $0$ 处，要到达坐标 $n+1$ 处。

你会跳，但每次最多只能跳 $d$ 坐标距离。即你可以从 $0$ 到达 $1\sim d$ 的任意坐标处，但是不能到 $d+1$ 及更大的坐标处。

你有 $m$ 块木板，可以在木板上随意走动。在开始前你可以随意放木板，但要遵守以下规则：

（1）木板的相对位置不能变。即木板只能按照输入顺序排列。

（2）木板只能放在河里，即不能有木板跑到岸上。

（3）木板间不能重叠，即河里的每个坐标上至多只能放一块木板。

（4）一旦你开始跳跃，木板就不能再更改位置。

本题可能有多种解，因此采用 $spj$ 。

3.1.2 输入格式

第一行三个整数 $n,m,d(1 \leq n,m,d \leq 1000,m \leq n)$ 。分别表示河的长度，木板的数量和能跳的最远距离。

第二行 $m$ 个整数 $c_1,c_2,…,c_m(1 \leq c_i \leq n,\sum\limits_{i=1}^m{c_i \leq n})$ 。其中 $c_i$ 表示第 $i$ 块木板的长度。

3.1.3 输出格式

如果不能到达 $n+1$ 处，则输出一行”NO”。

否则，则共两行输出。第一行输出“YES”。

第二行输出满足要求的木板的放法。共 $n$ 个数字，表示坐标为 $i$ 的位置放了哪块木板。如果没有木板即为0，否则输出木板对应的下标值。注意，输出要满足题干要求的规则。

3.1.4 样例

输入 #1

7 3 2
1 2 1

7 3 2

1 2 1

输出 #1

YES
0 1 0 2 2 0 3

YES

0 1 0 2 2 0 3

输入 #2

10 1 11
1

10 1 11

输出 #2

YES
0 0 0 0 0 0 0 0 0 1

YES

0 0 0 0 0 0 0 0 0 1

输入 #3

10 1 5
2

10 1 5

输出 #3

YES
0 0 0 0 1 1 0 0 0 0

YES

0 0 0 0 1 1 0 0 0 0

3.2 解题思路

贪心。我们在能跳到的最远距离处放下一块木板，并走到木板最末尾处跳下一次。我们要时刻记录答案，但注意我们可能用不到所有木板，因此针对这种情况要特别处理（因为题目要求我们用到所有木板）。个人处理是把所有木板放在最后面。

官方的题解是直接把所有木板放在最后面，然后需要木板的时候就直接拿过来，觉得很巧妙。

3.3 解题代码

#include <iostream>
using namespace std;
int n,m,d;
int a[1010];
int ans[1010];
int main()
{
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    int now=0,i=1;//now表示当前位置，i表示当前木板号
    while(now+d<=n&&i<=m)
    {
        now+=d;
        for(int j=now;j<=min(n,now+a[i]-1);j++)
            ans[j]=i;
        now+=(a[i++]-1);
    }
    if(now+d<=n)printf("NO\n");//如果所有木板放完后，now+d还是没有达到n+1，则说明无解
    else
    {
        printf("YES\n");
        if(now>=n+1)i--;//如果now大于等于n+1，说明最后放的木板有一部分放在了岸上
        now=n;
        for(int j=m;j>=i;j--)//倒序放没有放的木板
        {
            for(int k=now;k>=now-a[j]+1;k--)
            {
                if(ans[k])i=ans[k];//如果这个位置之前有木板，则这块木板也需要重新放
                ans[k]=j;
            }
            now=now-a[j];//注意，此时的now是下一块木板的结束位置，因此不是now-a[j]+1。后者是当前木板的开始位置
        }
        for(int i=1;i<=n;i++)printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

int n,m,d;

int a[1010];

int ans[1010];

int main()

{

scanf("%d%d%d",&n,&m,&d);

for(int i=1;i<=m;i++)scanf("%d",&a[i]);

int now=0,i=1;//now表示当前位置，i表示当前木板号

while(now+d<=n&&i<=m)

{

now+=d;

for(int j=now;j<=min(n,now+a[i]-1);j++)

ans[j]=i;

now+=(a[i++]-1);

}

if(now+d<=n)printf("NO\n");//如果所有木板放完后，now+d还是没有达到n+1，则说明无解

else

{

printf("YES\n");

if(now>=n+1)i--;//如果now大于等于n+1，说明最后放的木板有一部分放在了岸上

now=n;

for(int j=m;j>=i;j--)//倒序放没有放的木板

{

for(int k=now;k>=now-a[j]+1;k--)

{

if(ans[k])i=ans[k];//如果这个位置之前有木板，则这块木板也需要重新放

ans[k]=j;

}

now=now-a[j];//注意，此时的now是下一块木板的结束位置，因此不是now-a[j]+1。后者是当前木板的开始位置

}

for(int i=1;i<=n;i++)printf("%d ",ans[i]);

printf("\n");

}

return 0;

}

3.4 解题心得

本题难度不高，但是最后处理未放置木板时需要特别注意，稍有差错便会导致WA。细节还是很重要。比如最开始把 $i=ans[k]$ 写成 $i=k$ 这种问题。这道题考场上用时28min，属实有点拖进度。

4.CF1256D Binary String Minimizing

4.1 题目描述（传送门）

4.1.1 题目大意

给你一个长度为 $n$ 的二进制串，要求你最多进行 $k$ 次交换相邻两个字符的操作，使得操作后的字符串字典序最小。共有 $q$ 组提问。

4.1.2 输入格式

第一行一个整数 $q(1\leq q \leq 10^4)$ 。

对于每组提问，第一行两个整数 $n,k(1 \leq n \leq 10^6,1 \leq k \leq n^2)$ 。分别表示二进制数的长度和允许的最大操作数。

第二行是一个由 $n$ 个’ $0$ ‘或’ $1$ ‘组成的字符串。为给定的二进制串。

4.1.3 输出格式

共q行。

每行一个长度为n的二进制串，为最多k次操作后字典序最小的二进制串。

4.1.4 样例

输入 #1

8 5

11011010

7 9

1111100

7 11

1111100

输出 #1

01011110
0101111
0011111

01011110

0101111

0011111

4.2 解题思路

贪心。字典序最小，我们需要让前面的数尽可能是 $0$ 。因此，我们的目标是将当前状态下的第一位 $1$ 变成 $0$ 。但是是用哪个 $0$ 去变这个 $1$ 呢？我们来考虑一个例子： $1010$ 。

如果我们用第一个 $0$ ，则可变成 $0110$ 。

如果我们用第二个 $0$ ，则需变成 $0011$ 。但我们发现，在这个过程中，其实是包含 $0110$ 这个过程的，即我们想变成 $0011$ ，就必须经历 $0110$ 。原因很简单，我们考虑第一个1，要想变成 $0011$ ，它一定要向后动。它向后动的时候首先变成 $0110$ ，然后才会一点点变成 $0011$ 。

所以，虽然我们用第二个 $0$ 变成的 $0011$ 比用第一个 $0$ 变成的 $0110$ 字典序要小，但是变 $0011$ 的过程可以视作先变成 $0110$ ，再用第一个 $0$ 去替换第一个 $1$ ，将其分解成两部分。因此，我们每一步做的都是将当前状态下第一个 $1$ 和第一个 $0$ 进行交换。

最后考虑 $k$ 这个量。我们每次大交换其实都进行了第一个 $0$ 的下标减第一个 $1$ 的下标的小交换。因此我们只需要判断当前 $k$ 值支不支持我们进行这样的大交换。如果支持，我们直接进行交换，然后修改 $k$ 的值。如果不支持，则将当前状态的第一个 $0$ 尽可能的往前移，用光所有操作次数为止。

4.3 解题代码

#include <iostream>
using namespace std;
int q,n;
long long k;
char s[1000010];
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%lld%s",&n,&k,s);
        int one=0,zero=0;
        while(one<n&&zero<n&&k)
        {
            while(s[one]=='0'&&one<n)one++;
            zero=max(zero,one);
            while(s[zero]=='1'&&zero<n)zero++;
            if(one>=n||zero>=n)break;
            if(zero-one<k)
            {
                s[one]='0';
                s[zero]='1';
                k-=(zero-one);
            }
            else
            {
                s[zero-k]='0';
                s[zero]='1';
                k=0;
                break;
            }
        }
        printf("%s\n",s);
    }
    return 0;
}

#include <iostream>

using namespace std;

int q,n;

long long k;

char s[1000010];

int main()

{

scanf("%d",&q);

while(q--)

{

scanf("%d%lld%s",&n,&k,s);

int one=0,zero=0;

while(one<n&&zero<n&&k)

{

while(s[one]=='0'&&one<n)one++;

zero=max(zero,one);

while(s[zero]=='1'&&zero<n)zero++;

if(one>=n||zero>=n)break;

if(zero-one<k)

{

s[one]='0';

s[zero]='1';

k-=(zero-one);

}

else

{

s[zero-k]='0';

s[zero]='1';

k=0;

break;

}

printf("%s\n",s);

}

return 0;

}

4.4 解题心得

代码部分没有写注释，按照思路模拟即可。

$zero$ 要取 $zero$ 和 $one$ 中大的那个，否则如果只取 $one$ 的话会 $TLE$ 。

开 $long\ long$ ，开 $long\ long$ ，开 $long\ long$ 。 $k$ 到 $n^2$ ，没开 $long\ long$ 调了半个小时。

5.CF1256E Yet Another Division Into Teams

5.1 题目描述（传送门）

5.1.1 题目大意

你是一名ICPC教练，现在有n名学生要参赛，每人有一个能力值。

ICPC是要分队的，每队不少于3人，每人属于一队且仅属于一队。每队的极差为队伍中能力值最高的人的能力值与能力值最低的人的能力值的差。现在要你找出一种分队方法，使得所有队伍的极差和最小。

5.1.2 输入格式

第一行一个整数 $n(3\leq n \leq 2·10^5)$ ，表示学生的数量。

第二行为 $n$ 个整数 $a_1,a_2,…,a_n(1 \leq a_i \leq 10^9)$ ，其中 $a_i$ 表示第 $i$ 名学生的能力值。

5.1.3 输出格式

共两行。

第一行两个整数 $res$ 和 $k$ ，分别表示所得的极差最小和和队伍数量。

第二行为 $n$ 个整数 $t_1,t_2,…,t_n(1\leq t_i \leq k)$ ，其中 $t_i$ 表示第 $i$ 名学生属于的队伍编号。

如果有多组答案，输出一组即可。不一定要最小化队伍的数量。

共q行。

每行一个长度为n的二进制串，为最多k次操作后字典序最小的二进制串。

5.1.4 样例

输入 #1

5
1 1 3 4 2

1 1 3 4 2

输出 #1

3 1
1 1 1 1 1

3 1

1 1 1 1 1

输入 #2

6
1 5 12 13 2 15

1 5 12 13 2 15

输出 #2

7 2
2 2 1 1 2 1

7 2

2 2 1 1 2 1

输入 #3

10
1 2 5 129 185 581 1041 1909 1580 8150

1 2 5 129 185 581 1041 1909 1580 8150

输出 #3

7486 3
3 3 3 2 2 2 2 1 1 1

7486 3

3 3 3 2 2 2 2 1 1 1

5.2 解题思路

本题是一道 $DP$ 题。首先将整个序列从小到大排序。

我们设 $dp[i]$ 表示前 $i$ 个位置所能达到的极差的最小值。

状态转移方程为 $dp[i]=min(dp[i],dp[j]+a[j]-a[i])(4 \leq j \leq i-3)$ 。

这样复杂度为 $O(n^2)$ ，毫无疑问会 $TLE$ 。

因此我们考虑一条特性：每个队伍的人数只能为 $3,4,5$ 。

假设我们队伍的人数为 $6$ ，那么一定可以拆分为两个人数为 $3$ 的队伍，使得总极差值不变或变小。

因为 $a[6]-a[1] \geq a[6]-a[4]+a[3]-a[1]$ 。

所以我们在状态转移时， $j$ 的枚举范围就可以大幅减小： $i-5 \leq j \leq i-3$ 。

这样复杂度仅为 $O(n)$ ，复杂度大大降低了。（当然还有排序的复杂度，所以其实是 $O(nlogn)$ ）

5.3 解题代码

#include <iostream>
#include <algorithm>
using namespace std;
int n;
struct node
{
    int i,x,start,ans;
}a[200010];
long long dp[200010];
bool cmp(node x,node y){return x.x<y.x;}
bool cmp2(node x,node y){return x.i<y.i;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].x);
        a[i].i=i;
        dp[i]=INT_MAX;//dp初始化一个很大的值，因为我们要找最小值
    }
    sort(a+1,a+1+n,cmp);
    for(int i=3;i<=5;i++)//预处理前5个dp值，其中dp[1],dp[2]无答案
    {
        dp[i]=a[i].x-a[1].x;
        a[i].start=1;
    }
    for(int i=6;i<=n;i++)
    {
        for(int j=i-5;j<=i-3;j++)
        {
            if(dp[i]>dp[j]+a[i].x-a[j+1].x)
            {
                dp[i]=dp[j]+a[i].x-a[j+1].x;
                a[i].start=j+1;//a[i].start记录当前元素所属组的起始元素位置
            }
        }
    }
    int cnt=0;
    for(int i=n;i>=1;i--)//按记录的start值进行答案赋值
    {
        cnt++;
        for(int j=a[i].start;j<=i;j++)
            a[j].ans=cnt;
        i=a[i].start;
    }
    sort(a+1,a+1+n,cmp2);
    printf("%d %d\n",dp[n],cnt);
    for(int i=1;i<=n;i++)printf("%d ",a[i].ans);
    printf("\n");
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int n;

struct node

{

int i,x,start,ans;

}a[200010];

long long dp[200010];

bool cmp(node x,node y){return x.x<y.x;}

bool cmp2(node x,node y){return x.i<y.i;}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i].x);

a[i].i=i;

dp[i]=INT_MAX;//dp初始化一个很大的值，因为我们要找最小值

}

sort(a+1,a+1+n,cmp);

for(int i=3;i<=5;i++)//预处理前5个dp值，其中dp[1],dp[2]无答案

{

dp[i]=a[i].x-a[1].x;

a[i].start=1;

}

for(int i=6;i<=n;i++)

{

for(int j=i-5;j<=i-3;j++)

{

if(dp[i]>dp[j]+a[i].x-a[j+1].x)

{

dp[i]=dp[j]+a[i].x-a[j+1].x;

a[i].start=j+1;//a[i].start记录当前元素所属组的起始元素位置

}

int cnt=0;

for(int i=n;i>=1;i--)//按记录的start值进行答案赋值

{

cnt++;

for(int j=a[i].start;j<=i;j++)

a[j].ans=cnt;

i=a[i].start;

}

sort(a+1,a+1+n,cmp2);

printf("%d %d\n",dp[n],cnt);

for(int i=1;i<=n;i++)printf("%d ",a[i].ans);

printf("\n");

return 0;

}

5.4 解题心得

考场上没有解出来的 $DP$ 题，或者说看到题就没有意识到是 $DP$ 题，或者是意识到是 $DP$ 题但是没有构造转移方程的思维。总而言之， $DP$ 这个大专题是该练了。校队寒假集训今天讲了 $DP$ ，等给题之后做一做。 $DP$ 的大块复习诸如数位 $DP$ ，状压 $DP$ ，树形 $DP$ 等也该着手进行了。

6.CF1256F Equalizing Two Strings

6.1 题目描述（传送门）

6.1.1 题目大意

给你两个长度为 $n$ 的由小写字母组成的字符串 $s$ 和 $t$ 。

对于一次操作，你可以选择任意长度为 $len(1\leq len \leq n)$ 的一段并进行下述操作：

（1）在 $s$ 中选择任意一个长度为 $len$ 的子串并将其翻转。

（2）同时在 $t$ 中选择任意一个长度为 $len$ 的子串并将其翻转。

要注意对于一次操作，你只需要关注 $len$ 相同，并不需要关注具体区间。例如 $len=3$ 且 $n=5$ ，你可以翻转 $s[1\dots3]$ 和 $t[3\dots5]$ ， $s[2\dots4]$ 和 $t[2\dots4]$ ，但是不可以是 $s[1\dots3]$ 和 $t[1\dots2]$ 。

你的任务是判断在若干次（可能为 $0$ 次）操作后， $s$ 和 $t$ 是否可能相等。

共有 $q$ 组问题。

6.1.2 输入格式

第一行一个整数 $q(1\leq q \leq 10^4)$ 。

对于每组问题，共三行。

每组第一行为一个整数 $n(1 \leq n \leq 2·10^5)$ ，表示 $s$ 和 $t$ 的长度。

每组第二行为一个由小写字母组成的长度为 $n$ 的字符串 $s$ 。

每组第三行为一个由小写字母组成的长度为 $n$ 的字符串 $t$ 。

$q$ 组问题的 $n$ 的和不超过 $2·10^5(\sum{n}\leq{2·10^5})$ 。

6.1.3 输出格式

共 $q$ 行。

每行为对应问题的答案。”YES”表示 $s$ 和 $t$ 可能在若干次操作后相等，”NO”表示不能。

6.1.4 样例

输入 #1

4
4
abcd
abdc
5
ababa
baaba
4
asdf
asdg
4
abcd
badc

abcd

abdc

ababa

baaba

asdf

asdg

abcd

badc

输出 #1

NO
YES
NO
YES

YES

6.2 解题思路

本题是一道找规律题。（这么说可能不太讲理）

对于每组数据，我们首先判断两个字符串里各个字符的个数是否相等，如果不相等，直接 $NO$ 。

接下来，我们判断是否有字符个数大于等于 $2$ ，如果有，直接 $YES$ 。因为我们可以在一个串中选两个相等的字符放在一起然后只选中它们进行翻转，相当于这个串是一直不变的。而另一个串在若干次变换后一定会和该串相等（因为所有字符数都相等，类似于冒泡排序）。

以上两条都是找规律的问题，接下来才进入正式解题的部分。

如果满足了第一条但不满足第二条，那么我们可以通过判断字符串的逆序对奇偶性是否相同来判断是否可行。我们来考察冒泡排序移动次数和逆序对的关系。例如： $4,1,3,2$ 。序列的逆序对为 $4$ ，而我们考虑向大冒，即 $4$ 先移动 $3$ 次到最末尾，然后 $3$ 再移动 $1$ 次到倒数第二个。我们发现每个序列冒泡排序的移动次数就是逆序对数。

至于为什么奇偶性，我们考虑将每个字符串都变成元素按字典序递增的形式，称为标准形式，每次 $len$ 只取 $2$ ，即冒泡排序。那么如上所说，如果逆序对数相同，说明二者可以同时变成标准形式。如果不同，则必有一个串先变成标准形式。那么如果奇偶性相同，则另一个串的剩余变换次数为偶数次，那么对于已经变好的串，我们将前两位进行偶数次变换，串仍然是标准形式，此时另一个串也达到标准形式。然而如果奇偶性不同，二者总会有两个元素相反，所以不可行。

综上，排除前两种情况后，我们只需要考虑两个字符串的逆序对数奇偶性是否相同即可。

6.3 解题代码

#include <iostream>
#include <cstring>
using namespace std;
int q;
int n;
char s1[200010],s2[200010];
int cnt1[30],cnt2[30];//记录每个字符个数
int ans1,ans2;//记录逆序对数
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&n);
        memset(cnt1,0,sizeof(cnt1));
        memset(cnt2,0,sizeof(cnt2));
        ans1=0;ans2=0;
        scanf("%s%s",s1,s2);
        for(int i=0;i<n;i++)
        {
            cnt1[s1[i]-'a']++;
            cnt2[s2[i]-'a']++;
            for(int j=s1[i]-'a'+1;j<26;j++)//这里因为字符数量有限，因此我们可以通用比当前元素大的所有字符的个数来表示前面元素与当前元素构成的逆序对数
                ans1+=cnt1[j];
            for(int j=s2[i]-'a'+1;j<26;j++)
                ans2+=cnt2[j];
            ans1%=2;//我们只要逆序对的奇偶性，因此为了放置爆int，我们随时取模
            ans2%=2;    
        }
        bool flag1=true,flag2=false;//flag1=false说明有字符在两个串中的个数不等，flag2=true说明有字符个数大于等于2
        for(int i=0;i<26;i++)
        {
            if(cnt1[i]!=cnt2[i])
            {
                flag1=false;
                break;
            }
            if(cnt1[i]>=2||cnt2[i]>=2)
                flag2=true;
        }
        if(!flag1){printf("NO\n");continue;}//存在某字符在两个串中个数不等
        if(flag2||ans1==ans2){printf("YES\n");continue;}//存在某字符数量大于等于2或两串逆序对奇偶性相同
        printf("NO\n");//；两串逆序对奇偶性不同
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int q;

int n;

char s1[200010],s2[200010];

int cnt1[30],cnt2[30];//记录每个字符个数

int ans1,ans2;//记录逆序对数

int main()

{

scanf("%d",&q);

while(q--)

{

scanf("%d",&n);

memset(cnt1,0,sizeof(cnt1));

memset(cnt2,0,sizeof(cnt2));

ans1=0;ans2=0;

scanf("%s%s",s1,s2);

for(int i=0;i<n;i++)

{

cnt1[s1[i]-'a']++;

cnt2[s2[i]-'a']++;

for(int j=s1[i]-'a'+1;j<26;j++)//这里因为字符数量有限，因此我们可以通用比当前元素大的所有字符的个数来表示前面元素与当前元素构成的逆序对数

ans1+=cnt1[j];

for(int j=s2[i]-'a'+1;j<26;j++)

ans2+=cnt2[j];

ans1%=2;//我们只要逆序对的奇偶性，因此为了放置爆int，我们随时取模

ans2%=2;

}

bool flag1=true,flag2=false;//flag1=false说明有字符在两个串中的个数不等，flag2=true说明有字符个数大于等于2

for(int i=0;i<26;i++)

{

if(cnt1[i]!=cnt2[i])

{

flag1=false;

break;

}

if(cnt1[i]>=2||cnt2[i]>=2)

flag2=true;

}

if(!flag1){printf("NO\n");continue;}//存在某字符在两个串中个数不等

if(flag2||ans1==ans2){printf("YES\n");continue;}//存在某字符数量大于等于2或两串逆序对奇偶性相同

printf("NO\n");//；两串逆序对奇偶性不同

}

return 0;

}

6.4 解题心得

这道题拿了一血是没想到的，考场上只想到了逆序对数但是第二个样例死活过不去，手动模拟了一下才找到第二条规律。题目不算很难，但是逆序对确实是巧妙的东西。

7.CF1243A Maximum Square

7.1 题目描述（传送门）

7.1.1 题目大意

给你 $n$ 个矩形木板编号为 $1$ 到 $n$ ，第 $i$ 块木板的大小为 $a_i\timesi$ （宽为 $1$ ，高为 $a_i$ ）。

你想做一个正方形的木板，方法是选择一些木板并按一定顺序并排放置，然后将它们粘在一起，最后从生成的形状中切割出一个正方形。正方形的边要和原木板的边平行。

例如下图，我们有高度为 $4,3,1,4,5$ 的木板。然后选择高度为 $4,3,5$ 的木板，可以切割出一个 $3\times3$ 的矩形，且是最大的矩形。

你要做的是找到能切割出的最大矩形边长是多少。

7.1.2 输入格式

第一行一个整数 $k(1\leq k \leq 10)$ ，表示问题组数。

对于每组问题，共两行。

每组第一行为一个整数 $n(1 \leq n \leq 1000)$ ，表示木板的数量。

每组第二行为 $n$ 个整数 $a_1,a_2,…,a_n(1 \leq a_i \leq n)$ ，表示木板的高度。

7.1.3 输出格式

共 $k$ 行。

每行一个整数，表示对应问题下能切割出的最大矩形边长。

7.1.4 样例

输入 #1

4 3 1 4 5

4 4 4 4

1 1 1

5 5 1 1 5

输出 #1

7.2 解题思路

本题二分答案即可。

我们可以很轻松发现答案单调的性质，即如果 $x$ 满足题意，那么小于 $x$ 的数也都满足题意；如果 $y$ 不满足题意，那么大于 $y$ 的数也都不满足题意。所以我们可以二分答案。

其次，对于check函数，为了满足 $mid$ ，我们需要选择大于等于 $mid$ 的木板，看其数量是否大于等于 $mid$ 即可。具体手动模拟一下就能看出这条性质来。

7.3 解题代码

#include <iostream>
#include <algorithm>
using namespace std;
int k,n;
int a[1010];
bool check(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=x)//找到第一个大于等于x的木板，后面的就都大于等于x了
            return (n-i+1)>=x;
    }
    return false;
}
int work(int l,int r)
{
    if(l==r)return l;
    int mid=(l+r)/2+1;//+1是为了更好的处理端点，可以有别的处理端点的办法
    if(check(mid))return work(mid,r);
    return work(l,mid-1);
}
int main()
{
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+1+n);//排序是为了更快的check
        printf("%d\n",work(1,n));
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int k,n;

int a[1010];

bool check(int x)

{

for(int i=1;i<=n;i++)

{

if(a[i]>=x)//找到第一个大于等于x的木板，后面的就都大于等于x了

return (n-i+1)>=x;

}

return false;

}

int work(int l,int r)

{

if(l==r)return l;

int mid=(l+r)/2+1;//+1是为了更好的处理端点，可以有别的处理端点的办法

if(check(mid))return work(mid,r);

return work(l,mid-1);

}

int main()

{

scanf("%d",&k);

while(k--)

{

scanf("%d",&n);

for(int i=1;i<=n;i++)scanf("%d",&a[i]);

sort(a+1,a+1+n);//排序是为了更快的check

printf("%d\n",work(1,n));

}

return 0;

}

7.4 解题心得

这道题是个div.2的A题，考场上以为题目难度递增，看到这道题的时候才发现貌似不是，二分答案还是很好想的，注意处理端点即可。

8.CF1243B2 Character Swap (Hard Version)

8.1 题目描述（传送门）

8.1.1 题目大意

你有两个只由小写字母组成的字符串 $s$ 和 $t$ ，要求你每次交换两者的一个字符，在最多 $2n$ 次交换后使得两者相同。

注意我们只需让两者相同，但不需最小化交换次数，即任何的小于等于 $2n$ 次操作使得两者相同都是满足题意的。

8.1.2 输入格式

第一行一个整数 $k(1\leq k \leq 1000)$ ，表示问题组数。

对于每组问题，共三行。

每组第一行为一个整数 $n(2 \leq n \leq 50)$ ，表示 $s$ 和 $t$ 的长度。

每组第二行为一个由小写字母组成的长度为 $n$ 的字符串 $s$ 。

每组第三行为一个由小写字母组成的长度为 $n$ 的字符串 $t$ 。

8.1.3 输出格式

共 $k$ 行。

对于每组问题，如果不能在最多2n次交换后使其相等，输出一行”NO”即可。

反之，输出三行，第一行为”YES”。第二行为你的操作数 $x(x \leq 2n)$ 。

接下来 $x$ 行为你的 $x$ 次操作，每行两个整数，分别为要交换的 $s$ 和 $t$ 中的字符的位置。

8.1.4 样例

输入 #1

4
5
souse
houhe
3
cat
dog
2
aa
az
3
abc
bca

souse

houhe

cat

dog

abc

bca

输出 #1

Yes
1
1 4
No
No
Yes
3
1 2
3 1
2 3

Yes

1 4

Yes

1 2

3 1

2 3

8.2 解题思路

贪心。我们枚举两个串，如果某一位不同，则向后寻找第一个可以替换的字符（第一个与 $s$ 串该位置字符相同的字符）。因为只能在两个串之间互相交换而不能串内交换，所以又分为两种情况：

case1：souse和houhe，我们执行操作 $4,1$ 即可。

case2：souhe和house，我们执行 $4,4$ ，再执行 $4,1$ 。

由此我们可以看出，如果可以替换的字符在 $s$ 串内，直接替换即可，否则，要先把该字符换到 $s$ 串中，然后再替换。

最后可以看出，我们最多替换的次数为 $2n$ 次，因此只需判断替换后是否可以相等即可。

8.3 解题代码

#include <iostream>
#include <algorithm>
using namespace std;
int k,n;
char s[60];
char t[60];
int ans[110][2],cnt;
int main()
{
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d%s%s",&n,s,t);
        cnt=0;
        bool f=true;
        for(int i=0;i<n;i++)
        {
            if(s[i]!=t[i])
            {
                bool flag=false;
                for(int j=i+1;j<n;j++)
                {
                    if(s[i]==s[j])//case 1
                    {
                        ans[++cnt][0]=j;
                        ans[cnt][1]=i;
                        swap(s[j],t[i]);
                        flag=true;
                        break;
                    }
                    if(s[i]==t[j])//case 2
                    {
                        ans[++cnt][0]=j;
                        ans[cnt][1]=j;
                        swap(s[j],t[j]);
                        ans[++cnt][0]=j;
                        ans[cnt][1]=i;
                        swap(s[j],t[i]);
                        flag=true;
                        break;
                    }
                }
                if(!flag)//如果找不到，则为NO
                {
                    f=false;
                    break;
                }
            }
        }
        if(!f)printf("NO\n");
        else{
            printf("YES\n%d\n",cnt);
            for(int i=1;i<=cnt;i++)
                printf("%d %d\n",ans[i][0]+1,ans[i][1]+1);
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int k,n;

char s[60];

char t[60];

int ans[110][2],cnt;

int main()

{

scanf("%d",&k);

while(k--)

{

scanf("%d%s%s",&n,s,t);

cnt=0;

bool f=true;

for(int i=0;i<n;i++)

{

if(s[i]!=t[i])

{

bool flag=false;

for(int j=i+1;j<n;j++)

{

if(s[i]==s[j])//case 1

{

ans[++cnt][0]=j;

ans[cnt][1]=i;

swap(s[j],t[i]);

flag=true;

break;

}

if(s[i]==t[j])//case 2

{

ans[++cnt][0]=j;

ans[cnt][1]=j;

swap(s[j],t[j]);

ans[++cnt][0]=j;

ans[cnt][1]=i;

swap(s[j],t[i]);

flag=true;

break;

}

if(!flag)//如果找不到，则为NO

{

f=false;

break;

}

if(!f)printf("NO\n");

else{

printf("YES\n%d\n",cnt);

for(int i=1;i<=cnt;i++)

printf("%d %d\n",ans[i][0]+1,ans[i][1]+1);

}

return 0;

}

8.4 解题心得

贪心策略还比较好想，但是考场上因为没有意识到题目难度非递增这点所以，这题看了眼样例就直接过了也没回来看，后来看榜才发现榜前的就我没写这道题……最后就是，要注意答案数组开 $2n$ ，脑残没开又WA一次。

9.CF1242A Tile Painting

9.1 题目描述（传送门）

9.1.1 题目大意

你要粉刷从你的房子到你的大门的小路。

小路共有 $n$ 个瓷砖，标号为 $1$ 到 $n$ ，你将用一些颜色粉刷它们。

要满足：如果两个瓷砖的序号是 $i$ 和 $j$ ，有 $|i-j|>1$ 且 $n\ mod\ |i-j|=0$ ，则这两个瓷砖要粉刷一样的颜色。

9.1.2 输入格式

一行一个整数 $n(1\leq n \leq 10^{12})$ ，表示路的长度。

9.1.3 输出格式

一行一个整数，表示能用到的满足题意的最多的颜色数量。

9.1.4 样例

输入 #1

4

输出 #1

2

输入 #2

5

输出 #2

5

9.2 解题思路

最开始想到了二分答案，但check过程时间复杂度是很高的（甚至可以到 $O(n)$ ），这对于本题这种n很大的情况是不可取的。

其实这是一道数学题。我们考虑 $n\ mod\ |i-j|=0$ ，其实如果找出的 $n$ 的因子，那么问题就迎刃而解了。再进一步考虑，如果 $n=8$ ，那么因子有 $1,2,4,8$ ，但其实如果想满足 $n\ mod\ |i-j|=0$ 的话， $|i-j|$ 只能是2，因为其包含 $|i-j|=4$ 的情况。换句话说，如果 $|i-j|=4$ 的话，我们是不能用 $4$ 种颜色的，因为模 $4$ 等于 $0$ 的数模 $2$ 也一定等于 $0$ 。

因此，我们只需要找质因数。再考虑如果一个数有多个质因数的情况。假设 $n$ 有质因数 $p_1,p_2$ ，那么其实要考虑的是 $ap_1+bp_2$ 能组合出来的数字。可以证明两个质数的线性组合是可以组合出任意数的（证明参考）。

两条重要定理：两个互质数的线性组合等于 $1$ 必定有解。两个质数一定互质。（可以组合成裴蜀定理的一部分）

回归问题，如果 $n$ 有两个质因子，那么它们可以组合使得任意两个瓷砖都要颜色相同。

总结一下：

（1）如果 $n$ 本身是质数，那么最大颜色数就是 $n$ 。

（2）如果 $n$ 是合数且 $n$ 有且仅有一个质因子，那么最大颜色数就是这个质因子。

（3）如果 $n$ 是合数但 $n$ 有两个及以上质因子，那么最大颜色数为 $1$ 。

最后我们考虑如何找质因子，一种办法是先找出所有的质数然后挨个枚举是否是 $n$ 的质因子。但是 $n$ 本身很大，而且如果 $n$ 等于 $2$ 和一个超大质数相乘的话，那筛出的别的质数就都没有用了。所以我们直接对 $n$ 进行拆分。

9.3 解题代码

#include <iostream>
#include <cmath>
using namespace std;
long long n;
long long p[5000010],cnt;
int main()
{
    cin>>n;
    long long ans=n;
    for(long long i=2;i<=sqrt(n);i++)//很朴素的拆质因数，i从2枚举到根号n
    {
        if(n%i==0)
        {
            p[++cnt]=i;
            while(n%i==0)n/=i;//用尽可能多的质因子拆n，比如2拆8可以拆3次
        }
        if(n<i)break;
    }
    if(n>1)p[++cnt]=n;
    if(cnt==1)printf("%lld\n",p[1]);//这里cnt==1包含n本身就是质数的情况
    else printf("1\n");
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

long long n;

long long p[5000010],cnt;

int main()

{

cin>>n;

long long ans=n;

for(long long i=2;i<=sqrt(n);i++)//很朴素的拆质因数，i从2枚举到根号n

{

if(n%i==0)

{

p[++cnt]=i;

while(n%i==0)n/=i;//用尽可能多的质因子拆n，比如2拆8可以拆3次

}

if(n<i)break;

}

if(n>1)p[++cnt]=n;

if(cnt==1)printf("%lld\n",p[1]);//这里cnt==1包含n本身就是质数的情况

else printf("1\n");

return 0;

}

9.4 解题心得

数论数论数论，冲NOIP的时候就一直搞不明白的东西。或许现在还只能搞懂gcd相关。什么中国剩余定理费马小定理等等等等，数论还是要学的。这次的裴蜀定理也只是考场上觉得是这么回事儿，要是真证明自己也还是啥都不会。数论还是要搞的。

10.CF1242B 0-1 MST

10.1 题目描述（传送门）

10.1.1 题目大意

你有一个有 $n$ 个节点的无向完全图，其中 $m$ 条边边权为 $1$ ，其余边边权为 $0$ 。

你的目标是求出这个图的最小生成树的树权。

10.1.2 输入格式

一行两个整数 $n,m$ ，分别表示完全图顶点的个数和边权为 $1$ 的边的个数。

接下来 $m$ 行每行两个整数 $u,v$ ，表示连接 $u,v$ 两个顶点的边的边权为 $1$ 。

10.1.3 输出格式

一行一个整数，该完全图的最小生成树的树权。

10.1.4 样例

输入 #1

6 11

1 3

1 4

1 5

1 6

2 3

2 4

2 5

2 6

3 4

3 5

3 6

输出 #1

2

输入 #2

3 0

3 0

输出 #2

0

10.2 解题思路

首先想到尽可能用边权为 $0$ 的边。我们求边权为 $1$ 的边构成的图的补图（即边权为 $0$ 的边构成的图）。

接下来在这个图中尽可能的连接最小生成树，最终会形成 $x$ 个连通块，连通块间在原图中只有边权为 $1$ 的边，因此我们只需要添加 $x-1$ 条边权为 $1$ 的边就可以构成最小生成树了。答案即为 $x-1$ 。

所以这样一道看似求最小生成树的题转化为了求补图的连通块个数的题。

这道题数据范围不小，如果暴力的去判断点是否在最小生成树内等会很耗时间。所以我们采用优秀的数据结构 $set$ 。

10.3 解题代码

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int n,m,u,v;
set<int>q;//用set判断点是否在最小生成树中
set<int>t[100010];//用set存边
bool vis[100010]={0};//辅助判断点是否在最小生成树中，因为set在使用时删除可能会出现问题
void work(int x)
{
    vis[x]=true;
    q.erase(x);
    vector<int>p;//用vector存不在最小生成树中的出点，也是因为set在使用时删除可能会出现问题
    for(auto it=q.begin();it!=q.end();it++)//不用枚举所有出点，只需枚举还不在最小生成树里的点是否是出点
    {
        int y=*it;
        if(!t[x].count(y))
            p.push_back(y);
    }
    for(int i=0;i<p.size();i++)//全部判断后再进行删除
        q.erase(p[i]);
    for(int i=0;i<p.size();i++)
        work(p[i]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)q.insert(i);//初始所有点都不在最小生成树中
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        t[u].insert(v);
        t[v].insert(u);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            ans++;
            work(i);
        }
    }
    printf("%d\n",ans-1);
    return 0;
}

#include <iostream>

#include <set>

#include <vector>

using namespace std;

int n,m,u,v;

set<int>q;//用set判断点是否在最小生成树中

set<int>t[100010];//用set存边

bool vis[100010]={0};//辅助判断点是否在最小生成树中，因为set在使用时删除可能会出现问题

void work(int x)

{

vis[x]=true;

q.erase(x);

vector<int>p;//用vector存不在最小生成树中的出点，也是因为set在使用时删除可能会出现问题

for(auto it=q.begin();it!=q.end();it++)//不用枚举所有出点，只需枚举还不在最小生成树里的点是否是出点

{

int y=*it;

if(!t[x].count(y))

p.push_back(y);

}

for(int i=0;i<p.size();i++)//全部判断后再进行删除

q.erase(p[i]);

for(int i=0;i<p.size();i++)

work(p[i]);

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)q.insert(i);//初始所有点都不在最小生成树中

for(int i=1;i<=m;i++)

{

scanf("%d%d",&u,&v);

t[u].insert(v);

t[v].insert(u);

}

int ans=0;

for(int i=1;i<=n;i++)

{

if(!vis[i])

{

ans++;

work(i);

}

printf("%d\n",ans-1);

return 0;

}

10.4 解题心得

$set$ 是个好东西，可惜不会用。对于 $stl$ 还是要熟练运用，总是说用到再学用到再学可是真的用到的时候也只是暂时会用，等到再想用的时候还是一团空。有机会要写一篇 $stl$ 大汇总，随时遇到随时学随时更新那种。

图的题还是好理解，不过最近遇到的图的题不多， $dij$ 也不会了只会 $spfa$ ， $spfa$ 也不熟只熟 $Floyd$ 。图的知识还不只这些，而且貌似图论的实际应用还挺丰富的，所以图论还是要好好搞，集训后期搞图论的时候还是要再努把力。

11.CF1242C Sum Balance

11.1 题目描述（传送门）

11.1.1 题目大意

你有 $k$ 个盒子，编号为 $1$ 到 $k$ 。第 $i$ 个盒子有 $n_i$ 个整数（可以是负数）。所有盒子里的所有数字都是不同的。

现在你可以执行一次操作：

从每个盒子中拿出一个数字，共拿出 $k$ 个数字。然后将这些数字分别放入 $k$ 个盒子中，每个盒子只能放一个数字。最后保证盒子内的数字数目不变。注意从同一个盒子拿出的数字可以放回本盒子中。

你的问题是，是否可以在这样的一次操作后，所有盒子内的数字和都相等。

11.1.2 输入格式

第一行一个整数 $k(1 \leq k \leq 15)$ ，表示盒子的数量。

接下来 $k$ 行，表示每个盒子的信息。

接下来第 $i$ 行的第一个元素为 $n_i(1 \leq n_i \leq 5000)$ ，表示第 $i$ 个盒子中整数的个数。后面跟着 $n_i$ 个整数 $a_{i,1},…,a_{i,n_i}(|a_{i,j}\leq 10^9|)$ ，表示第 $i$ 个盒子中的 $n_i$ 个整数。

数据保证所有的 $a_{i,j}$ 都不相同。

11.1.3 输出格式

如果不可以在这样的一次操作后，所有盒子内的数字和都相等，则输出一行”NO”。

否则，输出 $k+1$ 行。第一行”YES”。

接下来k行，表示每个盒子移动的信息。

接下来的第 $i$ 行有两个整数 $c_i$ 和 $p_i$ 。意味着我们将第 $i$ 个盒子中的整数 $c_i$ 移动到第 $p_i$ 个盒子中去。

如果有多组解，输出任意一组即可。

11.1.4 样例

输入 #1

3 1 7 4

2 3 2

2 8 5

1 10

输出 #1

Yes

7 2

2 3

5 1

10 4

输入 #2

2
2 3 -2
2 -1 5

2 3 -2

2 -1 5

输出 #2

No

输入 #3

2
2 -10 10
2 0 -20

2 -10 10

2 0 -20

输出 #3

Yes
-10 2
-20 1

Yes

-10 2

-20 1