2024 SNCPC 单挑记录

2026-02-03 00:52:40 栏目：最新资讯 5 阅读

补题链接：https://codeforces.com/gym/105257

solved 7 out of 13.

题解按开题顺序排列。

A

题目大意

在 Linux 系统中，每个文件都有与之相关的权限，权限被分为读、写与执行三种权限（rwx）。

在本题中，chmod 模式串由若干 $0$ 到 $9$ 之间的十进制数组成，其二进制形式表示是否有对应权限。

例如数字 $7$ 的二进制形式为 $111$ ，那么表示权限字符串为 rwx；数字 $5$ 的二进制形式为 $101$ ，对应的权限为 r-x。

给出一个合法 chmod 模式串，输出对应的权限字符串。

输入包含 $t$ 组测试数据。

其中

$1 \leq t \leq 100$

思路

计算 chmod 串中每一位的二进制形式，然后按照题意输出就行。

Code

#include 
#define ll long long
void solve() {
    std::string s;
    std::cin >> s;
    for(int i = 0; i < 3; i ++) {
        ll tmp = (s[i] - '0');
        if((tmp >> 2) & 1) std::cout << "r";
        else std::cout << "-";
        if((tmp >> 1) & 1) std::cout << "w";
        else std::cout << "-";
        if(tmp & 1) std::cout << "x";
        else std::cout << "-";
    }
    std::cout << '
';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
    ll t;
    std::cin >> t;
    for(int i = 1; i <= t; i ++) {
        solve();
    }
    return 0;
}

F

题目大意

给定长度为 $n$ 的数组 ${a}$ ，找出两个可以重复的整数 $i$ 和 $j$ ，最大化 $a_i&a_j$ 的结果。

输入包含 $t$ 组测试数据。

其中

$10^5$
$10^5$
$10^5$

思路

数据范围不允许 $O(n^2)$ 的解，需要一些小巧思来优化复杂度。

首先找到数组中最大的元素 $m x$ ，与其自己做按位与运算，得到的答案不一定最优，但一定不劣于大多数解法。

很自然地能够想到，定下其中一个元素为 $m x$ ，然后扫描其余所有元素，计算其与 $m x$ 的按位与结果是否大于 $m x$ ，求出最大答案即可。

时间复杂度 $O (n)$ 。

Code

#include 
#define ll long long
ll a[200005];
void solve() {
    ll n;
    std::cin >> n;
    ll mx = 0, ans = 0;
    for(int i = 1; i <= n; i ++) std::cin >> a[i], mx = std::max(mx, a[i]);
    for(int i = 1; i <= n; i ++) ans = std::max(ans, mx & a[i]);
    std::cout << ans << '
';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
    ll t;
    std::cin >> t;
    for(int i = 1; i <= t; i ++) {
        solve();
    }
    return 0;
}

M

题目大意

有一扇大小为 $100 \times 100$ 的窗户和 $n$ 个对角线长为 $2$ 的正方形窗花。以 $(0, 0)$ 为窗户左下角的坐标，右上角的坐标为 $(100, 100)$ ，第 $i$ 个窗花的中心在整坐标点 $x_i,y_i)$ 上，窗花的对角线与坐标轴平行。

求出被窗花至少覆盖一次的面积大小。

其中

$10^4$
$x_i,y_ile 99$

思路

如下图所示，将一个单位正方形分为四个部分，每个部分的面积为 $0.25$ ，以其左下角为基准坐标。

令 $f [i] [j] [k]$ 为坐标为 $(i, j)$ 的第 $k$ 部分是否被覆盖至少一次，分类讨论：

若中心坐标在图中 $A$ 点，那么覆盖的部分是 $2$ 与 $3$ ，将 $f [i] [j] [2]$ 与 $f [i] [j] [3]$ 置为 $1$ 。
若中心坐标在图中 $D$ 点，那么覆盖的部分是 $1$ 与 $4$ ，将 $f [i] [j] [1]$ 与 $f [i] [j] [4]$ 置为 $1$ 。

其余情况类似。扫描每个单位正方形的每个部分，若该部分状态为 $1$ ，则将答案累加 $0.25$ 。

时间复杂度 $O (100 \times 100 \times 4)$ 。

Code

#include 
#include 
#define ll long long
ll map[155][155][5];
void solve() {
    ll n;
    std::cin >> n;
    for(int i = 1; i <= n; i ++) {
        ll x, y;
        std::cin >> x >> y;
        map[x][y][2] = 1, map[x][y][4] = 1;
        map[x][y - 1][1] = 1, map[x][y - 1][2] = 1;
        map[x - 1][y][3] = 1, map[x - 1][y][4] = 1;
        map[x - 1][y - 1][1] = 1, map[x - 1][y - 1][3] = 1;
    }
    double ans = 0.0;
    for(int i = 0; i <= 99; i ++) {
        for(int j = 0; j <= 99; j ++) {
            for(int k = 1; k <= 4; k ++) {
                if(map[i][j][k]) ans += 0.25;
            }
        }
    }
    std::cout << std::fixed << std::setprecision(18) << ans << '
';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
    ll t;
    // std::cin >> t;
    t = 1;
    for(int i = 1; i <= t; i ++) {
        solve();
    }
    return 0;
}

D

题目大意

给定一个整数 $n$ 。

现在所有包含 $x$ 的数字都消失了，找出 $n$ 在所有还未消失的自然数中从小到大排在第几位。

输入有 $T$ 组测试数据。

其中

$10^5$
$10^{18}$
$1 \leq x \leq 9$

输入保证 $n$ 中不含数字 $x$ 。

思路

有一个比较玄学的做法。

将 $n$ 中所有大于 $x$ 的数位减去 $1$ ，得到一个新的十进制数 $m$ ，然后将其转为 $9$ 进制再加上 $1$ （因为 $0$ 也属于自然数，但进制转换中把它忽略掉了，所以还需要加 $1$ ）即为答案。

时间复杂度 $O (T lo g n)$ 。

Code

#include 
#include 
#define ll long long
ll map[155][155][5];
ll func(std::string s) {
    ll res = 0;
    for(auto it : s) res *= 9, res += (it - '0');
    return res + 1;
}
void solve() {
    std::string s;
    std::cin >> s;
    ll x;
    std::cin >> x;
    for(auto & it : s) it -= (it - '0' > x);
    ll ans = func(s);
    std::cout << ans << '
';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
    ll t;
    std::cin >> t;
    // t = 1;
    for(int i = 1; i <= t; i ++) {
        solve();
    }
    return 0;
}

L

题目大意

LNC 喜欢所有 $k$ 进制下所有数位的乘积为自身因子的数。他称之为 LNC 数。例如：

当 $k = 10$ 时， $y = (36)_{10}$ 是 LNC 数，因为 $(3 \times 6) ∣ 36$ 。

当 $k = 4$ 时， $y = (12)_4$ 是 LNC 数，因为转换成十进制后 $12)_4 = (6)_{10}$ ，而 $(1 \times 2) ∣ 6$ 。

当 $k = 2$ 时， $y = (1101)_2$ 不是 LNC 数，因为转换成十进制后 $1101)_2 = (13)_{10}$ ，而 $0$ 不是 $13$ 的因子。

LNC 在和 LJJ 玩一个游戏，LJJ 给出 $x$ 枚棋子，然后 LNC 选定一个整数 $k$ ( $k \geq 2$ )。随后他们交替取走若干枚棋子，要求取走的棋子数量是 $k$ 进制意义下的 LNC 数。LNC 先手，先取完的获胜。两个人都绝顶聪明，故都会选择最优的策略。

LJJ 觉得这个游戏很不公平，他们一共玩了 $T$ 局游戏，对于每局游戏他给出的 $x$ ，他希望知道最小的 $k$ 使得 LNC 先手必胜。

其中：

思路

先考虑简单情况。二进制内的LNC数有 $1$ ，三进制内的LNC数有 $1$ 和 $2$ 。

在 $k$ 为 $2$ 时，剩余棋数为奇数时显然必胜，偶数时必败。

$k$ 为 $3$ 时，如果剩余棋数是 $3$ 的倍数，那么这个局面先手必败（先手取 $1$ 或者取 $2$ ，后手将剩余棋数模 $3$ 后剩余的部分拿掉就行）。

推广到任意情况，对于任意 $k$ ，如果剩余棋数是它的倍数，那么先手必败。

如果均选择最优策略，那么一回合下来，会拿走 $k$ 个棋子。若经过若干回合后剩下的棋子数必会小于 $k$ ，先手拿走剩下的所有棋子赢下比赛。

也就是说， $x % k \neq = 0$ 时，先手必胜。

暴力枚举 $k$ ，找到第一个满足 $x % k \neq = 0$ 的 $k$ 即可。

Code

#include 
#include 
#define ll long long
void solve() {
    ll x;
    std::cin >> x;
    if(x & 1) std::cout << "2
";
    else {
        if(x % 3 != 0) std::cout << "3
";
        else {
            ll ans = 4;
            while(ans <= x) {
                // std::cout << ans << ' ' << x << std::endl;
                if(x % ans != 0) {
                    std::cout << ans << '
';
                    return;
                }
                ans ++;
            }
            std::cout << ans << '
';
        }
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
    ll t;
    std::cin >> t;
    // t = 1;
    for(int i = 1; i <= t; i ++) {
        solve();
    }
    return 0;
}

C

题目大意

Shirost 作为树王国的庆典设计师，准备邀请 $n$ 个嘉宾来参加本次庆典。庆典上一共准备了 $2 n$ 个座位，一个座位最多只能坐一个人且一个人恰好坐一个座位。Shirost 初步计划将第 $i$ 个嘉宾安排在第 $i$ 个座位上。但是总统调查了这 $n$ 个嘉宾的意愿，第 $i$ 个嘉宾的心仪座位为第 $a_i$ 个座位。但除非能坐到心仪座位上，否则他们只愿意坐在原来的座位上。总统希望 Shirost 能够修改计划，使得尽可能多的嘉宾坐在他们的心仪座位上。

给定一个长为 $n$ 的数组 ${a}$ ，找到长为 $n$ 的数组 $(1≤i≤n,1≤bi≤2×105)b_i (1le ile n,1le b_ile 2 imes 10^5)$ ，满足 $j,b_i eq b_j$ 且 $i,b_i=i$ 或 $b_i=a_i$ ，最大化 $b_i=a_i$ 的个数。

其中

$10^5$
$a_ile 2n$

思路

对于每个 $a [i]$ ，表示坐在第 $i$ 号座位的嘉宾希望坐在座位 $a [i]$ 上。建立有向边 $(i, a [i])$ ，表示第 $i$ 位嘉宾希望移动至 $a [i]$ 。

因为每个点的出度一定不大于 $1$ ，所以不可能存在两个环共用一条路径的情况，那么形成的图集一定是由若干 $D A G$ 和若干只含有一个环的有向图组成。

$D A G$ 很好理解，如果其中出度为 $0$ 的点大于 $n$ ，就找以其为终点的最长路径，这张图对答案的贡献就是最长的路径长度。如果小于等于 $n$ ，那么这张图就移不动了，对答案的贡献为 $0$ 。

如果这张图存在环，那么对答案的贡献就是环大小。

可以使用拓扑排序加工出所有环大小之和，然后再在所有终点编号大于 $n$ 的所有 $D A G$ 上跑一遍 $D P$ 以求出最大路径长，然后将所有求出来的东西取加和，则为最后的答案。

至于如何找出所有 $D A G$ 上节点对应的终点，建反图后以终点为起点跑一遍 $df s$ 就行了。

时间复杂度 $O (n)$ 。

Code

#include 
#include 
#include 
#include 
#include 
#define ll long long
ll a[200005];
ll deg1[200005], deg2[200005];
ll f[200005];
ll tag[200005];
std::vector<ll> map[200005];
std::vector<ll> rev[200005];
bool isdag[200005];
void find_dag(ll u, ll anc) {
    isdag[u] = true;
    tag[u] = anc;
    for(auto v : rev[u]) {
        find_dag(v, anc);
    }
}
void func(ll u) {
    for(auto v : map[u]) {
        if(f[v]) f[u] = std::max(f[u], f[v] + 1);
        else {
            func(v);
            f[u] = f[v] + 1;
        }
    }
}
void solve() {
    ll n;
    std::cin >> n;
    for(int i = 1; i <= n; i ++) std::cin >> a[i];
    for(int i = 1; i <= n; i ++) {
        map[i].push_back(a[i]);
        rev[a[i]].push_back(i);
        deg1[a[i]] ++, deg2[a[i]] ++;
    }
    std::queue<ll> que;
    for(int i = 1; i <= (n << 1); i ++) {
        if(!deg1[i]) que.push(i);
    }
    ll index = 0;
    while(!que.empty()) {
        ll u = que.front();
        que.pop();
        index ++;
        for(auto v : map[u]) {
            deg1[v] --;
            if(!deg1[v]) que.push(v); 
        }
    }
    ll ans = (n << 1) - index;
    for(int i = n + 1; i <= (n << 1); i ++) {
        if(!map[i].size()) find_dag(i, i);
    }
    for(int i = 1; i <= (n << 1); i ++) {
        if(!deg2[i] && tag[i]) func(i);
    }
    std::map<ll, ll> mp;
    for(int i = 1; i <= (n << 1); i ++) {
        if(!tag[i] || tag[i] < n) continue;
        mp[tag[i]] = std::max(mp[tag[i]], f[i]);
    }
    for(auto it : mp) ans += it.second;
    std::cout << ans << '
';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
    ll t;
    // std::cin >> t;
    t = 1;
    for(int i = 1; i <= t; i ++) {
        solve();
    }
    return 0;
}

B

题目大意

一个 $n \times m$ 的字符矩阵 $a_{ij}$ ，被称为合法的表达式矩阵，当且仅当其满足如下条件：

矩阵只包含 ‘1’，‘+’，‘*’ 字符。
对于矩阵的每行从左向右组成的字符串，均为合法的表达式。
对于矩阵的每列从上向下组成的字符串，均为合法的表达式。

一个合法的表达式矩阵的权值定义为，每行从左向右组成的字符串和每列从上向下组成的字符串共 $n + m$ 个表达式求值后的值求和的结果。
求所有 $n \times m$ 的合法表达式矩阵中，权值最小的那一个。如果有多个最小的答案，你可以给出任意一个。
我们定义字符串 $s$ 是合法表达式如下：

如果 $overbrace{111dots111}^{ ext{至少一个 }1}$ ，则 $s$ 是合法表达式。
如果 $s$ 和 $t$ 均为合法表达式，则 $s$ * $t$ 也是合法表达式。
如果 $s$ 和 $t$ 均为合法表达式，则 $s$ + $t$ 也是合法表达式。

其中

$3 \leq n, m \leq 9$

思路

有一个很直观的想法就是，将外围全部填上 $1$ （为了保证所有行列表达式合法），然后在内部交替填上 $*$ 和 $1$ ，这样保证能够存在最多的，对权值无贡献的 $1 * 1$ 结构。

但这样构造显然存在问题。

例如 $n = m = 5$ 的情况构造出的矩阵如下

$11111 1 * 1 * 1 11 * 11 1 * 1 * 111111$

得出的权值为 $44690$ 。

有另一种构造方法如下

$11111 1 * 1 * 1 11 + 11 1 * 1 * 111111$

得出的权值为 $44492$ ，小于上面的 $44690$ ，所以交替填乘号不一定是最优解。

对比两个构造方法，可以发现区别在于 $11 \times 11$ 和 $11 + 11$ 上，前者结果为 $121$ ，后者结果为 $22$ ，明显后者对总权值的大小贡献较小。

同时因为 $1 \times 1$ 优于 $1 + 1$ ，所以还需要尽量保留 $1 \times 1$ 的结构。

因为数据范围较小，可以考虑乱搞。

先按照之前的错误方法（外围全填 $1$ 内部交替填乘号）构造出矩阵，然后对上面的所有乘号进行替换，检查替换后的权值是否最小。用 $df s$ 暴力搜索出所有正确答案后，打表输出即可。

Code

用于打表的程序

#include 
#include 
#include 
#include 
#define ll long long
char ans[15][15];
char tmp[15][15];
ll n, m, cur = LLONG_MAX;
int get_res(std::string s);	// 表达式求值
void dfs(ll x, ll y) {
    if(x == n) {
        ll res = 0;
        for(int i = 1; i <= n; i ++) {
            std::string s;
            for(int j = 1; j <= m; j ++) s += tmp[i][j];
            res += get_res(s);
        }
        for(int i = 1; i <= m; i ++) {
            std::string s;
            for(int j = 1; j <= n; j ++) s += tmp[j][i];
            res += get_res(s);
        }
        if(cur > res) {
            cur = res;
            for(int i = 1; i <= n; i ++) {
                for(int j = 1; j <= m; j ++) ans[i][j] = tmp[i][j];
            }
        }
        return;
    }
    if(tmp[x][y] == '1') {
        if(y == m - 1) dfs(x + 1, 2);
        else dfs(x, y + 1);
    } else {
        tmp[x][y] = '+';
        if(y == m - 1) dfs(x + 1, 2);
        else dfs(x, y + 1);
        tmp[x][y] = '*';
        if(y == m - 1) dfs(x + 1, 2);
        else dfs(x, y + 1);
    }
}
void solve(ll x, ll y) {
    cur = LLONG_MAX;
    n = x, m = y;
    for(int i = 1; i <= m; i ++) ans[1][i] = '1', ans[n][i] = '1';
    for(int i = 2; i < n; i ++) ans[i][1] = '1', ans[i][m] = '1';
    
    if(m & 1) {
        for(int i = 2; i < m; i ++) {
            if(i & 1) ans[2][i] = '1';
            else ans[2][i] = '*';
        }
        for(int i = 3; i < n; i ++) {
            for(int j = 2; j < m; j ++) {
                ans[i][j] = (ans[i - 1][j] == '*') ? '1' : '*';
            }
        }
    } else {
        for(int i = 2; i < m; i ++) {
            if(i & 1) ans[2][i] = '1';
            else ans[2][i] = '*';
        }
        for(int i = 3; i < n; i ++) {
            for(int j = 2; j < m; j ++) {
                ans[i][j] = (ans[i - 1][j] == '*') ? '1' : '*';
            }
        }
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) tmp[i][j] = ans[i][j];
    }
    dfs(2, 2);
    std::cout << "ans[" << n << "][" << m << "] = "";
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) std::cout << ans[i][j];
    }
    std::cout << "";
";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
    ll t;
    for(int i = 3; i <= 9; i ++) {
        for(int j = 3; j <= 9; j ++) solve(i, j);
    }
    return 0;
}

用于提交的程序

#include 
#include 
#include 
#include 
#define ll long long
std::string ans[15][15];
void init() {
    ans[3][3] = "1111*1111";
    ans[3][4] = "11111*111111";
    ans[3][5] = "111111*1*111111";
    ans[3][6] = "1111111*1*11111111";
    ans[3][7] = "11111111*1*1*11111111";
    ans[3][8] = "111111111*1*1*1111111111";
    ans[3][9] = "1111111111*1*1*1*1111111111";
    ans[4][3] = "1111*1111111";
    ans[4][4] = "11111*1111*11111";
    ans[4][5] = "111111*1*111+1111111";
    ans[4][6] = "1111111*1*1111*1*1111111";
    ans[4][7] = "11111111*1*1*111+1*111111111";
    ans[4][8] = "111111111*1*1*1111*1*1*111111111";
    ans[4][9] = "1111111111*1*1*1*111+1*1*11111111111";
    ans[5][3] = "1111*11111*1111";
    ans[5][4] = "11111*1111+11*111111";
    ans[5][5] = "111111*1*111+111*1*111111";
    ans[5][6] = "1111111*1*1111+1+11*1*11111111";
    ans[5][7] = "11111111*1*1*111+1+111*1*1*11111111";
    ans[5][8] = "111111111*1*1*1111+1+1+11*1*1*1111111111";
    ans[5][9] = "1111111111*1*1*1*111+1+1+111*1*1*1*1111111111";
    ans[6][3] = "1111*11111*1111111";
    ans[6][4] = "11111*1111*11*1111*11111";
    ans[6][5] = "111111*1*111+111*1*111+1111111";
    ans[6][6] = "1111111*1*1111*1*11*1*1111*1*1111111";
    ans[6][7] = "11111111*1*1*111+1*111*1*1*111+1*111111111";
    ans[6][8] = "111111111*1*1*1111*1*1*11*1*1*1111*1*1*111111111";
    ans[6][9] = "1111111111*1*1*1*111+1*1*111*1*1*1*111+1*1*11111111111";
    ans[7][3] = "1111*11111*11111*1111";
    ans[7][4] = "11111*1111+11*1111*11*111111";
    ans[7][5] = "111111*1*111+111*1*111+111*1*111111";
    ans[7][6] = "1111111*1*1111+1+11*1*1111*1*11*1*11111111";
    ans[7][7] = "11111111*1*1*111+1*111*1*1*111*1+111*1*1*11111111";
    ans[7][8] = "111111111*1*1*1111+1+1+11*1*1*1111*1*1*11*1*1*1111111111";
    ans[7][9] = "1111111111*1*1*1*111+1+1*111*1*1*1*111*1*1+111*1*1*1*1111111111";
    ans[8][3] = "1111*11111*11111*1111111";
    ans[8][4] = "11111*1111*11*1111*11*1111*11111";
    ans[8][5] = "111111*1*111+111*1*111+111*1*111+1111111";
    ans[8][6] = "1111111*1*1111*1*11*1*1111*1*11*1*1111*1*1111111";
    ans[8][7] = "11111111*1*1*111+1*111*1*1*111+1*111*1*1*111+1*111111111";
    ans[8][8] = "111111111*1*1*1111*1*1*11*1*1*1111*1*1*11*1*1*1111*1*1*111111111";
    ans[8][9] = "1111111111*1*1*1*111+1*1*111*1*1*1*111+1*1*111*1*1*1*111+1*1*11111111111";
    ans[9][3] = "1111*11111*11111*11111*1111";
    ans[9][4] = "11111*1111+11*1111*11*1111*11*111111";
    ans[9][5] = "111111*1*111+111*1*111+111*1*111+111*1*111111";
    ans[9][6] = "1111111*1*1111+1+11*1*1111*1*11*1*1111*1*11*1*11111111";
    ans[9][7] = "11111111*1*1*111+1*111*1*1*111+1*111*1*1*111*1+111*1*1*11111111";
    ans[9][8] = "111111111*1*1*1111+1+1+11*1*1*1111*1*1*11*1*1*1111*1*1*11*1*1*1111111111";
    ans[9][9] = "1111111111*1*1*1*111+1*1*111*1*1*1*111*1+1*111*1*1*1*111*1*1+111*1*1*1*1111111111";

}
void solve() {
    init();
    ll n, m;
    std::cin >> n >> m;
    std::string str = ans[n][m];
    ll len = str.length();
    for(int i = 0; i < len; i ++) {
        if(i % m == m - 1) std::cout << str[i] << '
';
        else std::cout << str[i];
    }
    std::cout << '
';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
    ll t;
    // std::cin >> t;
    t = 1;
    for(int i = 1; i <= t; i ++) {
        solve();
    }
    return 0;
}