比赛链接：The 2023 ICPC Xi’an Invitational Programming Contest - Dashboard - Contest - QOJ.ac

A

题意：给出一个 $n$ 的排列 $p$ ，$A$ 和 $B$ 轮流进行，每次可以将 $p_{1…p_1}$ 按照任意顺序排列，当某人对于同一个 $p_1$ 执行两次操作时（这个人执行了两次），这个人输掉比赛。$A$ 先手，求出 $n$ 的排列中 $B$ 赢得比赛的排列数。

首先，当某个人执行操作时，必须将序列打乱，否则另一个人保持原序，这个人再次操作时就会输掉比赛。

考虑 $B$ 必赢的情况：

对于初始排列 $p$ ，当在 $p_1,p_2,…,p_{p_1}$ 中 $p_1$ 是最小的时候 $B$ 必赢。因为此时不管 $A$ 怎么操作，$B$ 都能将 $p_1$ 重新排回第一个数。

而对于 $p_1$ 不是最小的数的时候，$A$ 先手操作时可以排列出另一个 $p_1$ 最小的情形使 $B$ 输掉比赛。

因此答案即为：
$$
\sum A_{n-i}^{i-1}A_{n-i}^{n-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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# include <bits/stdc++.h>

using namespace std;
const int N = 1e7 + 10, mod = 998244353;
typedef long long LL;
int n;
LL fact[N], infact[N], inv[N];

int qp(int a, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % mod;
        a = (LL) a * a % mod;
        k >>= 1;
    }
    return res;
}

void init()
{
    fact[0] = infact[0] = 1;
    inv[1] = 1;
    for(int i = 2; i < N; i ++) inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
    for(int i = 1; i < N; i ++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod; 
        infact[i] = (LL)infact[i - 1] * inv[i] % mod;
    }

}

int A(int y, int x)
{
    return (LL)fact[x] * infact[x - y] % mod;
}

int main()
{
    init();
    cin >> n;
    LL res = 0;
    for(int i = 1; i <= (n + 1) / 2; i ++)
    {
        LL ans = (LL)A(i - 1, n - i) * fact[n - i] % mod;
        res = (res + ans) % mod;
    }
    cout << res << endl;
    //system("pause");
    return 0;
}

math

E

给出一个网格，被分成很多个长方形，问能否通过将长方形按照长-长/宽-宽合并成一个整体。

没H难，，榜又歪了

考虑逆过程，能否将大长方形分割成多个长方形，因为肯定是两个长方形合并成一个大长方形，因此考虑分治做法。

首先预处理，以列为例，预处理出网格的每一列有没有完全贯穿，若完全贯穿则说明可能从这里分开；行同理。

在dfs时枚举以网格的某一列分割是否可行，若这一列可以分成两部分那么分治依次讨论两部分；首先讨论按列分割，然后讨论按行分割。

注意剪枝：若以某一列分割时左边能够完全分割，但是右边不能分割，那么直接retuen 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
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
#include<bits/stdc++.h>
using namespace std;
const int N=1510;
int n,m;
char col[N][N],row[N][N];
int righ[N][N],down[N][N];
bool dfs(int x1,int y1,int x2,int y2){
    // printf("%d %d %d %d\n",x1,y1,x2,y2);
    bool tm1=0,tm2=0;
    bool ret=1;
    for(int i=x1+1;i<x2;++i){
        // printf("xi=%d righ=%d\n",i,righ[i][y1]);
        if(righ[i][y1]!=y1) ret=0;
        if(righ[i][y1]<y2)  continue;
        tm1=dfs(x1,y1,i,y2);
        tm2=dfs(i,y1,x2,y2);
        return (tm1&&tm2);
    }
    for(int i=y1+1;i<y2;++i){
        // printf("yi=%d down=%d\n",i,down[x1][i]);
        if(down[x1][i]!=x1) ret=0;
        if(down[x1][i]<x2)  continue;
        tm1=dfs(x1,y1,x2,i);
        tm2=dfs(x1,i,x2,y2);
        return (tm1&&tm2);
    }
    return ret;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)   scanf("%s",row[i]+1);
    for(int i=1;i<=n;++i)   scanf("%s",col[i]+1);
    for(int i=1;i<n;++i){
        righ[i][m]=m;
        for(int j=m;j>=1;--j){
            // cout<<i<<" "<<j<<" "<<row[i][j]<<endl;
            if(row[i][j]=='1')      righ[i][j-1]=righ[i][j];
            else    righ[i][j-1]=j-1;
        }
    }
    for(int j=1;j<m;++j){
        down[n][j]=n;
        for(int i=n;i>=1;--i){
            if(col[i][j]=='1')   down[i-1][j]=down[i][j];
            else down[i-1][j]=i-1;
        }
    }
    // for(int i=1;i<n;++i){
    //     for(int j=0;j<=m;++j)   cout<<righ[i][j];
    //     cout<<endl;
    // }
    if(dfs(0,0,n,m))    puts("YES");
    else puts("NO");
    // system("pause");
}

分治

G

水题

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cout<<i<<" ";
    return 0;
}

H

题意：有一个分成 $n$ 块的大轮子，同时内圈有对应 $n$ 个小轮子，初始内圈每一块都是0，外圈按顺时针每块依次标有 $0,1,…,n-1$ 。有两种操作，一种是将外圈的数加到对应的内圈上，另一种是将内圈旋转到任一角度。先给出内圈最终序列，求能否达到最终状态并求最小次数。

每一次加的都是一组等差数列，因此考虑差分。

  1. 若最终序列能够达到，那么最终序列的循环差分的模必须相同。要么有正有负，要么全零。
  2. 考虑若差分的值全零，且数组 $a$ 不是全零，那么可以模拟得到最小操作数为 $n+1$ 。具体操作为：先加 $n-1$ 次，然后把0移动到目标处再加一次。
  3. 若其他情况，答案为模值+1。可以证明一定可以直接加模值次数然后通过交换得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,rst;
int a[100010],b[100010];
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)   scanf("%lld",a+i);
    for(int i=1;i<=n;++i)   b[i]=a[i%n+1]-a[i];
    rst=ans=(b[1]+n)%n;
    for(int i=1;i<=n;++i){
        if(((b[i]+n)%n!=rst)){
            puts("-1");
            return 0;
        }
    }
    if(a[1]!=0) ans++;
    if(rst==0&&a[1]!=0) ans=n+1;
    printf("%lld",ans);  
}

math

J

题意：给出两个0-1的实数 $x,y$ 。对 $x$ 进行操作得到 $y$ 。第一中操作是 $x=x\times 0.5$，第二种是 $x=(x-1)\times 0.5+1$ 。求一种操作方案。

观察到操作2相当于将 $x$ 除以2然后加上0.5。

直接先对 $x$ 操作1直至变为 $0$ ，然后从 $0$ 变为 $y$ 。

把 $y$ 先乘2的50次方变成整数。

从后往前遍历 $y$ 的每一位，若为1，进行操作2，否则进行操作1。

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 i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    double a, b;
    std::cin >> a >> b;
    
    i64 B = (1LL << 50) * b;
    
    for (int i = 0; i < 50; i++) {
        std::cout << (B >> i & 1) + 1;
    }
    std::cout << "\n";
    
    return 0;
}

math