赛时状况

切了 T1 和 T2，感觉这套题还是很偏向于思维的，至少我做出来的 T1 和 T2 都不是很需要学习过算法知识。T3 和 T4 显然不是我能力范围之内了就没读题，直接润了。如果后面发现简单的话应该会补一下。

T1 - 二五一十

题意简述

多组测试数据，将正整数写成十进制形式，删除末尾所有连续的 $0$ 后，剩余十进制串的长度称为该数的有效长度。例如 $1203000$ 的有效长度为 $4$

给定一个正整数 $n$，你可以对其进行若干次 $\times 2$ 或 $\times 5$ 操作，使得结果的有效长度最短。

对于所有测试数据，保证：

  • $T \le 10^6$;
  • $n \le 10^{18}$。

题解

题目说我们可以对 $n$ 进行若干次 $\times 2$ 或 $\times 5$ 操作，根据题目名称，我们想到 $5 \times 2 = 10$ 和 $2 \times 5 = 10$ ，这样的话因为末尾的 $0$ ，我们就实现了降低有效长度的目的，那么我们可以把 $n$ 分解为如下形式：$n=2^a5^bm$

我们进行实际操作，就能得到：$n\cdot 2^x5^y=2^{a+x}5^{b+y}m$

末尾的 $0$ 来自一个 $2$ 和一个 $5$，最多可以删去 $min(a+x,b+y)$ 个末尾零。删除后剩下的数本质上是 $m$，再乘上没有配对的 $2$ 或 $5$。

这样的话答案就变成了 $m$ 的十进制位数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
    ll n;
    cin>>n;
    while(n%2==0) n/=2;
    while(n%5==0) n/=5;
    ll ans=0;
    while(n) {
        ans++;
        n/=10;
    }
    if(ans) cout<<ans<<endl;
    else cout<<1<<endl;
}

T2 - 构造大师

题意简述

给定正整数 $n,k$。

$1\leq k\leq n-1$，$n$ 为奇数。

你需要构造两个数组 $a_1,a_2\dots a_n$ 和 $b_1,b_2\dots b_n$，使得：

令 $S_1={(a_i+a_{i+1})\bmod 3n\mid 1\leq i\leq n}$（其中 $a_{n+1}=a_1$）。

$S_2={(a_i+b_i)\bmod 3n\mid 1\leq i\leq n}$。

$S_3={(b_i+b_{i+k})\bmod 3n\mid 1\leq i\leq n}$（其中 $b_{i+n}=b_{i}$）。

满足 $|S_1\cup S_2\cup S_3|=3n$ 。

对于所有测试数据，保证：

  • $3 \le n \le 10^6$ 且 $n$ 为奇数;
  • $1 \leq k \leq n - 1$。

题解

我们一共只有 $3n$ 次加法，得到 $3n$ 个结果，又要求我们的并集必须有 $3n$ 个元素，那也就是说我们这 $3n$ 个结果必须完全不同。

直接让这 $3n$ 个结果完全不同是困难的，那我们可以考虑把这个问题拆成两个子问题：

  • 不同类别之间，产生的结果不重复
  • 相同类别之间，产生的结果不重复

其中的类别就是指这三类加法。

容易注意到让相同类别之间产生的结果不重复是容易的，我们只要让它单调，且稍微错位几个，就一定不会重复，那么难点主要就在不同类别之间了。

注意到我们的模数是 $3n$ ，它显然是 $3$ 的倍数，那么我们就可以考虑：让 $3$ 类操作对 $3$ 取模得到的结果分别是 $0、1、2$

这样的话因为取模的结果都不同了，那结果显然就是不重复的了，但是 $S_2$ 要求了 $a_i + b_i$ ，同时涉及到了两个数组，就要考虑怎么让它跟别的不一样了。我们观察一下加数的一些性质可以得到下面的表格：

类别 加数模 $3$ 的余数 结果模 $3$ 的余数
$S_1$ $0+0$ $0$
$S_2$ $0+1$ $1$
$S_3$ $1+1$ $2$

那就好办了，我们对数组都乘 $3$ 不会影响取余结果，于是我们直接构造：

$a_i=3(i-1),\qquad b_i=3(i-1)+1$

这道题就做完了。

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
    int n,k;
    cin>>n>>k;
    cout<<"Yes"<<endl;
    for(int i=0;i<n;i++) {
        cout<<3*i<<" ";
    }
    cout<<endl;
    for(int i=0;i<n;i++) {
        cout<<3*i+1<<" ";
    }
}