acwing第67场周赛

1.火柴棍数字

原题链接：https://www.acwing.com/problem/content/4612/

思路

利用n根火柴拼成最大的数字
数字位数越大，数字的值就越大
1只用两根火柴就可以拼成，所以就看n根火柴可以拼成多少根1
n为偶数：拼成的数字为\(n/2\)位
n为奇数：拼成的数字也为\(n/2\)位，但多余出来一根火柴，这时就把这根多余出来的火柴和第一位的两根火柴拼成7即可

即：
n为偶数：\(n/2\)位1
n为奇数：第1位为7加上\(n/2-1\)位1

string构造函数

string( size_type length, char ch )

代码：
	cout << string(5,'c');
显示：
	ccccc

代码

#include<iostream>
#include<cstring>

using namespace std;

int main()
{
    int m,n;
    cin >> m;
    while(m --)
    {
        cin >> n;
        
        if(n % 2)
        {
            cout << '7' + string(n/2 - 1,'1') << endl;
        }
        else cout << string(n/2,'1') << endl;
    }
    
    return 0;
}

2.列表排序

原题链接：https://www.acwing.com/problem/content/4613/

思路

第一种操作：只交换每一行的两个数，每一行只能交换一次
第二种操作：交换两列数，只能进行一次操作

如果只看第一种操作
可以发现，只要一行中不在相应位置上的数的个数超过两个，那就无解，否则肯定有解

我们可以先进行第二种操作，然后去判断第一种操作之后是否有解

进行第二种操作一共有 \(C_{m}^{2} + 1\) 种操作(选两列，或者不交换),数据范围比较小，直接暴力枚举即可

代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 25;
int g[N][N];
int n,m;

bool check()
{
    int cnt;
    for(int i = 1; i <= n; i ++)
    {
        cnt = 0;
        for(int j = 1; j <= m; j ++)
        {
            if(g[i][j] != j) cnt ++;
            if(cnt > 2) return false;
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> g[i][j];
        }
    }
    
    // 枚举第二种操作
    for(int i = 1; i <= m; i ++)
    {
        for(int j = i; j <= m; j ++)
        {
            for(int k = 1; k <= n; k ++) swap(g[k][i],g[k][j]);
            if(check()) 
            {
                puts("YES");
                return 0;
            }
            for(int k = 1; k <= n; k ++) swap(g[k][i],g[k][j]); // 一定要记得恢复现场
        }
    }
    puts("NO");
    return 0;
}