牛客练习赛 133 出题人题解

牛客练习赛 133 出题人题解

比赛链接

出题人:ZnPdCo , Liamwh , 一位不愿透露姓名的 B 题 Idea 提供人
审题人:superguymj

非常感谢审题人和内测同学们,以及一位不愿透露姓名的出题人。希望大家今晚玩的开心~

题目总览与预期

本场比赛共 1345 人参加,589 人有提交。

alt

alt

祝贺 lgvc 捧杯!

非常感谢大家前来参与比赛,小有、小川和小姬的问题都得到了解决,替她们表示感谢

关于本场难度的声明:本场比赛的题目难度被反应说较高,但是出题人确实是通过与 cf 同等难度的题目以及 div2 比赛的题目难度进行对照出题的,以下为对照列表:

而给出的练习赛要求表难度其实出题人是完全按要求行事的,而通过率与难度其实是非常矛盾的体现。在 CF 的 div2 比赛中(2027),A 题(*800)的通过率其实也只有 60 左右,按照要求其实是完全不达标的。

以及本场由于期末周的原因,应该有部分同学报了名但没有参与。

希望大家能够理解,同时祝大家新的一年快乐!

:由于牛客的公式渲染过于奇怪:等号在某些地方渲染不出来,公式内不能添加 & 来实现对齐等等。为了解决这些问题,这篇题解的等号均使用 )来替代,而 & 均通过打空格的方式来实现对齐。为观感问题感到十分抱歉。

以上!

Problem A:万年沉睡的宝藏

*900,70%,模拟

Idea:Lnw143(Liamwh),Statement、Solution、Code、Data:ZnPdCo

题解

考虑使用 map(对于 Pythondict)维护每一个小岛、set 维护每一个小岛上的宝藏。

操作 1 相当于将一个元素插入到 set 中;操作 2 相当于求出 set 中元素的数量;操作 3 相当于判断某个元素是否在 set 中;操作 4 相当于求出 map 中的元素数量。

使用 setmap 时记得时刻判断是否为空。

时间复杂度

参考代码

#include <bits/stdc++.h>
using namespace std;
int q;
map<string, set<string>> m;
int main() {
    cin >> q;
    while(q --) {
        int op;
        string x, y;
        cin >> op;
        if(op == 1) {
            cin >> x >> y;
            m[x].insert(y);
        } else if(op == 2) {
            cin >> x;
            if(!m.count(x)) cout << 0 << endl;
            else cout << m[x].size() << endl;
        } else if(op == 3) {
            cin >> x >> y;
            if(!m.count(x)) cout << 0 << endl;
            else if(!m[x].count(y)) cout << 0 << endl;
            else cout << 1 << endl;
        } else if(op == 4) {
            cout << m.size() << endl;
        }
    }
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q = scanner.nextInt();
        Map<String, Set<String>> m = new HashMap<>();

        while (q-- > 0) {
            int op = scanner.nextInt();
            if (op == 1) {
                String x = scanner.next();
                String y = scanner.next();
                m.computeIfAbsent(x, k -> new HashSet<>()).add(y);
            } else if (op == 2) {
                String x = scanner.next();
                System.out.println(m.getOrDefault(x, Collections.emptySet()).size());
            } else if (op == 3) {
                String x = scanner.next();
                String y = scanner.next();
                if (!m.containsKey(x)) {
                    System.out.println(0);
                } else {
                    System.out.println(m.get(x).contains(y) ? 1 : 0);
                }
            } else if (op == 4) {
                System.out.println(m.size());
            }
        }
    }
}
from collections import defaultdict
m = defaultdict(set)
q = int(input())
for _ in range(q):
    line = input().split()
    op = int(line[0])
    if op == 1:
        x, y = line[1], line[2]
        m[x].add(y)
    elif op == 2:
        x = line[1]
        print(len(m[x]) if x in m else 0)
    elif op == 3:
        x, y = line[1], line[2]
        print(1 if x in m and y in m[x] else 0)
    elif op == 4:
        print(len(m))

出题思路

C++ 中的 map 直接访问一个不存在的元素会创建一个新元素,此时访问 size() 函数会返回非预期的结果,如果你不了解这点可能会罚一发。

同时验题时还遇到了各种各样不同的细节错误,这题主要考察了大家的手熟程度。

Problem B: 完美主义追求者

*1000,60%,数学,模拟

Idea:出题人不愿透露姓名,Statement、Solution、Code、Data:ZnPdCo

题解

每个长度为 的排列 都对应着唯一的完美的树,构造方法如下:

  • 找到 中最小值的下标 ,然后在 处分割序列 :左部构成 的左子树,右部则构成右子树。

而每一个完美的树都可以类似的对应到一个长度为 的排列。

那么排列与完美的树一一对应。

因为排列 共有 种,这意味着完美的树的数量也为

时,很明显 。因此,我们只需处理 的情况。

时间复杂度为

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string S;
ll N, P, ans = 1;
int main() {
	cin >> S >> P;
	while(S.at(0) == '0') S.erase(S.begin());
	if(S.length() > 7) {
		cout << 0;
		return 0;
	}
	istringstream ss(S);
	ss >> N;
	for(int i = 1; i <= P && i <= N; i ++) (ans *= i) %= P;
	cout << ans;
	return 0;
}
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String S = scanner.next();
        long P = scanner.nextLong();
        long ans = 1;
        if (S.length() > 7) {
            System.out.println(0);
            return;
        }
        long N = Long.parseLong(S);
        for (int i = 1; i <= P && i <= N; i++) {
            ans = (ans * i) % P;
        }
        System.out.println(ans);
    }
}
from functools import reduce
line = input().split()
n, p = int(line[0]), int(line[1])
if n < p:
    print(reduce(lambda x,y:x*y%p,range(1,n+1)))
else:
    print(0)

出题思路

诈骗题。考察了大家的想象能力。

Problem C:异或与位移

*1500,30%,位运算,数学

Idea、Statement、Solution、Code:Lnw143(Liamwh),Data:ZnPdCo

题解

做法 1

定义函数

假设我们有操作 ,现在我们知道 ,任务就是得到

我们考虑将 代入函数 ,得到 ,展开后可以看出 实际上等于

进一步地,将 代入 ,我们得到 ,通过展开可以得到 等于

同理,将 代入函数 次,可以使我们求出

足够大时, 增长到相当大。如果 ,则函数 中的 在向下取整后变为 ;而如果 ,该项在模 下也将变为 。最后得到 的值。

我们取 就可以确定 了。

我们可以使用 bitset 优化,时间复杂度为 ,其中 通常为

做法 2

本题存在一种 的做法,我们观察 函数中 的本质,记 表示 位上的值,那么上面哪个操作本质就是

那么考虑倒序操作上面的过程,也就是 ,直接转移就可以了。

#include <iostream>
#include <cstring>
#include <bitset>

using namespace std;

const int N = 20, M = 1e3, K = 1e4;

int n,m,k,a[N + 2];

bitset<K> y,all;

int main() {
	cin>>n>>m>>k;
	for(int i=1; i<=n; ++i) cin>>a[i];
	for(int i=0; i<k; ++i) all[i]=1;
	for(int i=1; i<=m; ++i) {
		string s;
		cin>>s;
		y.reset();
		for(int j=0; j<s.size(); ++j) y[s.size()-j-1]=s[j]-'0';
		for(int p=n; p>=1; --p)
			if(a[p]>0) for(int j=a[p]; j<k; j*=2) y=(y^(y<<j))&all;
			else for(int j=-a[p]; j<k; j*=2) y=(y^(y>>j))&all;
		bool f=false;
		for(int i=k-1; i>=0; --i)
			if(f|=y[i])
				cout<<int(y[i]);
		if(!f) cout<<'0';
		cout<<endl;
	}
	return 0;
}
#include <bits/stdc++.h>
#define N 10010
using namespace std;
int n, m, k;
int a[40];
int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        string str;
        cin >> str;
        bitset<N> s;
        for (int i = 0; i < str.size(); i++) {
            s[i] = str[str.size() - 1 - i] - '0';
        }
        for (int i = n; i > 0; i--) {
            bitset<N> t = s;
            if (a[i] > 0) {
                for (int j = a[i]; j < k; j++) {
                    t[j] = t[j] ^ t[j - a[i]];
                }
            } else {
                for (int j = k - 1 + a[i]; j >= 0; j--) {
                    t[j] = t[j] ^ t[j - a[i]];
                }
            }
            s = t;
        }
        int flag = 0;
        for (int i = k - 1; i >= 0; i--) {
            if (s[i]) flag = 1;
            if (flag) cout << s[i];
        }
        if (!flag) cout << 0;
        cout << endl;
    }
}

出题思路

本题原本的解法如做法 1,放在了 D 题的位置,但就在比赛前一天,出题人才发现验题人们写的都是做法 2,经过思考,发现做法 2 远比于做法 1 简单,虽然理论复杂度会更劣一点,但是出题人实在卡不掉也不想卡了,于是就将 C 题和 D 题调换了。

Problem D: 被拒绝在外的打卡

*2000,7%,动态规划,贪心

Idea、Statement、Solution、Code、Data:ZnPdCo

题解

做法 1

考虑树的情况,容易发现可以有且仅有一种移动方式:在第一时刻,点 移动到点 ,点 移动到点 ;在下一时刻,点 移回到点 ,点 移回到点 。反复如此就可以一直移动下去。

基于贪心策略可以想到一个很简单的树形 DP, 表示第 个点没有、有与它的儿子匹配交换,。然后累计子树答案即可。

考虑基环树的情况,我们可以分类讨论:

  1. 环上的点轮着移动

    这种情况可以分环上每一棵子树讨论,最后统计答案即可。

  2. 有一条边不会被匹配

    枚举断边,用树的情况累计答案。

直接枚举断边是 的,但是发现一个点肯定不可能既和它左边的点匹配又和它右边的点匹配,所以枚举环上的两个相邻的边分别断开统计答案即可。

时间复杂度:

做法 2

本题同样存在贪心的做法。更加好写但需要一定的想象能力。

每次直接找出度数为 的点,将其与任意一个相邻点匹配,以此类推,直到没有度数为 的点(那么此时图上要么没有点要么有一个简单环,对于简单环我们可以环上的点轮换匹配)。

为什么这样是对的呢?对于树的情况显然,因为每次就是从叶子往它的父亲进行匹配。而对于基环树,我们有两种情况:

  1. 环上的点轮着移动

    这种情况通过上述方式能够匹配出来。

  2. 有一条边不会被匹配

    我们按照上述方式匹配直到环上的一个点,此时将这个点匹配会让环同时减少两条边,那么此时这个图又变成了一棵树,我们可以继续按照上述方式匹配,直到没有度数为 的点。

注意需要特判只有一个点的情况。

时间复杂度:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000010
int t, n, m, ans;

struct PI {
	int first, second;
	PI(int a, int b) {first = a, second = b;}
};

namespace Graph {
	int head[N];
	int nxt[2*N];
	int to[2*N], cnt;
	
	void addEdge(int u, int v) {
		cnt++;
		to[cnt] = v;
		nxt[cnt] = head[u];
		head[u] = cnt;
	}
	
	void init() {
		__builtin_memset(head, 0, sizeof head);
		cnt = 0;
	}
}

namespace Loop {
	int dfn[N], fa[N], ti;
	int loop[N], num, flag[N];
	void dfs(int u) {
		using namespace Graph;
		dfn[u] = ++ti;
		for(int i = head[u]; i; i = nxt[i]) {
			int v = to[i];
			if(v == fa[u]) continue;
			if(!dfn[v]) {
				fa[v] = u;
				dfs(v);
			} else if(dfn[v] > dfn[u]) {
				for(; v != fa[u]; v = fa[v]) {
					loop[++num] = v;
					flag[v] = 1;
				}
			}
		}
	}
	
	void solve() {
		__builtin_memset(dfn, 0, sizeof dfn);
		__builtin_memset(fa, 0, sizeof fa);
		__builtin_memset(loop, 0, sizeof loop);
		__builtin_memset(flag, 0, sizeof flag);
		ti = num = 0;
		dfs(1);
	}
}

namespace Punch {
	int res;
	bool f[N];
	bool inTree;
	int nou, nov;
	
	void dfs(int u, int fa) {
		using namespace Graph;
		f[u] = 1;
		int sum = 0;
		for(int i = head[u]; i; i = nxt[i]) {
			int v = to[i];
			if(v == fa) continue;
			if(inTree && Loop::flag[v]) continue;
			if(u == nou && v == nov) continue;
			if(u == nov && v == nou) continue;
			
			dfs(v, u);
			sum += f[v];
		}
		
		if(sum) f[u] = 0, sum--;
		res += sum;
	}
	
	PI solve(int u, int _nou, int _nov, bool _inTree) {
		res = 0;
		inTree = _inTree, nou = _nou, nov = _nov;
		
		dfs(u, 0);
		return PI(res, f[u]);
	}
}

int main() {
	scanf("%d", &t);
	while(t--) {
		ans = 0;
		Graph::init();
		scanf("%d %d", &n, &m);
		for(int i = 1; i <= m; i++) {
			int u, v;
			scanf("%d %d", &u, &v);
			Graph::addEdge(u, v);
			Graph::addEdge(v, u);
		}
		
		Loop::solve();
		
		if(Loop::num == 0) {
			auto res = Punch::solve(1, 0, 0, 0);
			ans = res.first + res.second;
		} else {
			auto res = Punch::solve(1, Loop::loop[2], Loop::loop[3], 0);
			ans = res.first + res.second;
			
			res = Punch::solve(1, Loop::loop[1], Loop::loop[2], 0);
			ans = min(ans, res.first + res.second);
			
			int sum = 0;
			for(int i = 1; i <= Loop::num; i++) {
				res = Punch::solve(Loop::loop[i], 0, 0, 1);
				sum += res.first + (res.second ^ 1);
			}
			ans = min(ans, sum);
		}
		
		if(ans == 0) printf("Yes\n");
		else printf("%d\n", ans);
	}
	
	return 0;
}
// writer: 牛客lulu
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int __FAST_IO__ = []() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    return 0;
}();

void solve() {
    int n, m;
    cin >> n >> m;
    if (n == 1) {
        cout << "1\n";
        return;
    }
    vector<vector<int>> g(n);
    vector<int> deg(n, 0), vis(n, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
        deg[u - 1]++;
        deg[v - 1]++;
    }

    int ans = 0;
    queue<int> qs;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 1) {
            qs.push(i);
        }
    }
    while (!qs.empty()) {
        auto u = qs.front();
        qs.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        int v = -1;
        for (auto x : g[u]) {
            if (!vis[x]) {
                v = x;
                break;
            }
        }
        if (v == -1) {
            ans++;
            continue;
        }
        vis[v] = 1;
        for (auto x : g[v]) {
            if (!vis[x]) {
                deg[x]--;
                if (deg[x] == 1) {
                    qs.push(x);
                }
            }
        }
    }
    if (ans) cout << ans << "\n";
    else cout << "Yes\n";
}

int main() {
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

出题思路

本题分为一种相对于比较好想但是相对于难写一点的 dp 做法和一种贪心做法,可以区分不同写法的选手。

主要考察了大家的调试能力。

Problem E: 斐波那契的压迫

*2300,2%, 线段树

Idea、Statement、Solution、Code、Data:ZnPdCo

题解

考虑不真正地去维护这个数列,发现数列是由若干个斐波那契数列的前缀组成。

我们用线段树维护每个前缀的长度,查询可以在线段树上二分实现。而修改可以通过在线段树前后预留一些空位置,通过两个指针维护当前的前缀的起始位置,然后将新的数值插入到两个指针指向的位置,并更新指针的位置。

时间复杂度

#include <bits/stdc++.h>
#define int long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define N 1000000
#define P 998244353
using namespace std;
int n;
struct node {
	int mx, cnt, sum;
	friend node operator+(const node &x, const node &y) {
		node z;
		z.mx = max(x.mx, y.mx);
		z.cnt = x.cnt + y.cnt;
		z.sum = (x.sum + y.sum) % P;
		return z;
	} 
} t[N * 4 + 10]; 
bool lazy[N * 4 + 10];
int head = N / 2, tail = N / 2 - 1;
int fib[N + 10], sum[N + 10], len;
void pushdown(int pos) {
	t[ls(pos)].mx = t[ls(pos)].sum = t[ls(pos)].cnt = 0;
	t[rs(pos)].mx = t[rs(pos)].sum = t[rs(pos)].cnt = 0;
	lazy[ls(pos)] = lazy[rs(pos)] = 1;
	lazy[pos] = 0;
}
void update(int x, int l, int r, int pos, int k) {
	if(x == 0) return ;
	if(l == r) {
		t[pos].mx = k;
		t[pos].sum = sum[k];
		t[pos].cnt = k;
		return;
	}
	if(lazy[pos]) pushdown(pos);
	int mid = (l + r) >> 1;
	if(x <= mid) update(x, l, mid, ls(pos), k);
	else update(x, mid + 1, r, rs(pos), k);
	t[pos] = t[ls(pos)] + t[rs(pos)];
}
void clear(int nl, int nr, int l, int r, int pos) {
	if(nl > nr) return ;
	if(nl <= l && r <= nr) {
		t[pos].mx = t[pos].sum = t[pos].cnt = 0;
		lazy[pos] = 1;
		return;
	}
	if(lazy[pos]) pushdown(pos);
	int mid = (l + r) >> 1;
	if(nl <= mid) clear(nl, nr, l, mid, ls(pos));
	if(mid < nr) clear(nl, nr, mid + 1, r, rs(pos));
	t[pos] = t[ls(pos)] + t[rs(pos)];
}
node query(int nl, int nr, int l, int r, int pos) {
	if(nl > nr) return {0, 0, 0};
	if(nl <= l && r <= nr) {
		return t[pos];
	}
	if(lazy[pos]) pushdown(pos);
	int mid = (l + r) >> 1;
	node res = {0, 0, 0};
	if(nl <= mid) res = res + query(nl, nr, l, mid, ls(pos));
	if(mid < nr) res = res + query(nl, nr, mid + 1, r, rs(pos));
	return res;
}
int bound(int l, int r, int pos, int k) {
	if(l == r) {
		return l;
	}
	if(lazy[pos]) pushdown(pos);
	int mid = (l + r) >> 1;
	if(t[ls(pos)].cnt < k) return bound(mid + 1, r, rs(pos), k - t[ls(pos)].cnt);
	else return bound(l, mid, ls(pos), k);
}
int calc(int x) {
	if(x == 0) return 0;
	int res = bound(1, N, 1, x);
	node y = query(1, res - 1, 1, N, 1);
	return (y.sum + sum[x - y.cnt]) % P;
}
signed main() {
	fib[1] = fib[2] = 1;
	for(int i = 3; i <= N; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % P;
	for(int i = 1; i <= N; i++) sum[i] = (sum[i - 1] + fib[i]) % P;
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		int op, x, y;
		scanf("%lld", &op);
		if(op == 1) {
			scanf("%lld", &x);
			update(++tail, 1, N, 1, x);
			len += x;
		} else if(op == 2) {
			scanf("%lld", &x);
			update(--head, 1, N, 1, x);
			len += x;
		} else if(op == 3) {
			scanf("%lld", &x);
			int res = bound(1, N, 1, len - x);
			len -= x;
			x -= query(res + 1, N, 1, N, 1).cnt;
			clear(res + 1, N, 1, N, 1);
			update(res, 1, N, 1, query(res, res, 1, N, 1).cnt - x);
			tail = res;
		} else if(op == 4) {
			scanf("%lld %lld", &x, &y);
			int L = bound(1, N, 1, x);
			int R = bound(1, N, 1, y);
			int ans = 0;
			if(R > 1) ans = y - query(1, R - 1, 1, N, 1).cnt;
			if(L > 0 && R > 0 && L <= R - 1) ans = max(ans, query(L, R - 1, 1, N, 1).mx);
			ans = fib[ans];
			printf("%lld\n", ans);
		} else if(op == 5) {
			scanf("%lld %lld", &x, &y);
			int ans = ((calc(y) - calc(x - 1)) % P + P) % P; 
			printf("%lld\n", ans);
		}
	}
}

出题思路

感觉相较于前两题较为一眼,但是码量相对较大,所以放在了 E 题的位置,同样考察了选手的调试能力。

Problem F:千变万化的排列

*2600,0%,贪心,数学

Idea、Statement、Solution、Code、Data:ZnPdCo

题解

时,答案是好求的。下面我们假定

首先发现如果我们连续做两次第一种操作或者连续做两次第二种操作,相当于没有操作。所以如果我们要产生尽可能多的情况,一定是先做操作一再做操作二不断反复。我们要求的就是做多少次后序列会恢复。

我们把先做一次操作一再做一次操作二看为“一***作”。那么答案就是序列恢复所需要做的“一***作”次数乘以

我们可以模拟第一次的“一***作”,得出一个新的排列 ,对于所有 ,将 连一条有向边,形成若干环,答案就是所有环环长 乘以 。这样我们可以做到

分析排列 长成什么样子:

那么对于 ,它会向这个点连边:

我们可以得出一个简单的结论:我们只计算包含点 的环的环长的 ,就可以得到答案。

取值不在这些点时,包含它的环的环长一定与某一个包含上面这些点的环的环长相等。这一点可以通过反证法证明。

考虑怎么快速计算包含一个点的环的环长。我们定义上面的连边情况中当 时为情况 ,当 时为情况 时为情况

我们发现情况 实际上类似于将 移动到 ,假如移动 步后一直都在情况 中,它将会移动到 ,直到超过情况 的边界——。相当于我们从 出发,每次走 个单位长度,问走多少步才能超过 。所以我们通过一个简单的除法计算就可以得出到达下一个不在情况 中的点所需的步数以及到达的位置。

发现:对于一个环,在情况 中的连续点数不会超过 ,在情况 中的连续点数不会超过

证明:假如当前点是满足情况 的点 ,向后移动了两个点后依旧在情况 中,那么就会移动回 ,形成一个大小为 的环。所以连续点数不会超过 。情况 同理。

发现:发现连续的情况 ,连续的情况 或者连续的情况 形成的连续段最多不会超过 个。

证明:假如当前点是满足情况 的点 ,向后移动了若干步后移动到满足情况 的点 ,此时通过情况 移动到满足情况 的点 ,再通过若干次移动移动到满足情况 ,移动到满足情况 ,最后通过若干次移动回 ,连续段数恰好为 。其它情况可以类似证明。

综上,我们可以从点 开始计算包含这些点的环的环长,当点在情况 时,可以通过快速计算得到下一个不在情况 的点;当点在情况 时,因为最多不会超过 个点,可以直接暴力移动。最后因为连续段不会超过 ,所以模拟只会进行 次。

时间复杂度 ,瓶颈在于对高精度运算与求 ,精细实现可以做到更优。

from math import gcd, lcm
P = 998244353

def run(x, n, a, b):
    x = ((x - 1) % n + n) % n + 1
    sz = 0
    tmp = x
    if 1 <= tmp <= a + b - n:
        sz += 1
        tmp += n * 2 - a - b
    elif a + b - n + 1 <= tmp <= a:
        sz += 1
        tmp = a + 1 - tmp
    elif a + 1 <= tmp <= n:
        sz += 1
        tmp = n * 2 - b + 1 - tmp
    while tmp != x:
        if 1 <= tmp <= a + b - n:
            if 1 <= x <= a + b - n and x >= tmp and (x - tmp) % (n * 2 - a - b) == 0:
                step = (x - tmp) // (n * 2 - a - b)
            else:
                step = (a + b - n - tmp + (n * 2 - a - b)) // (n * 2 - a - b)
            sz += step
            tmp += step * (n * 2 - a - b)
        elif a + b - n + 1 <= tmp <= a:
            sz += 1
            tmp = a + 1 - tmp
        elif a + 1 <= tmp <= n:
            sz += 1
            tmp = n * 2 - b + 1 - tmp
    return sz

T = int(input())
for _ in range(T):
    ans = 1
    n, a, b = map(int, input().split())
    if a == 1 and b == 1:
        print(1)
        continue
    if a == 1:
        print(2)
        continue
    if b == 1:
        print(2)
        continue
    if a + b <= n:
        print(4)
        continue
    ans = lcm(ans, run(a, n, a, b))
    ans = lcm(ans, run(a + b - n + 1, n, a, b))
    ans = lcm(ans, run(n, n, a, b))
    ans = lcm(ans, run(a + 1, n, a, b))
    ans = lcm(ans, run(1, n, a, b))
    ans = lcm(ans, run(a + b - n, n, a, b))
    print((ans * 2) % P)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define P 998244353


const int maxn = 1000;  
  
struct bign{  
    int d[maxn], len;  
  
    void clean() { while(len > 1 && !d[len-1]) len--; }  
  
    bign()          { memset(d, 0, sizeof(d)); len = 1; }  
    bign(int num)   { *this = num; }   
    bign(char* num) { *this = num; }  
    bign operator = (const char* num){  
        memset(d, 0, sizeof(d)); len = strlen(num);  
        for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';  
        clean();  
        return *this;  
    }  
    bign operator = (int num){  
        char s[20]; sprintf(s, "%d", num);  
        *this = s;  
        return *this;  
    }  
  
    bign operator + (const bign& b){  
        bign c = *this; int i;  
        for (i = 0; i < b.len; i++){  
            c.d[i] += b.d[i];  
            if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;  
        }  
        while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;  
        c.len = max(len, b.len);  
        if (c.d[i] && c.len <= i) c.len = i+1;  
        return c;  
    }  
    bign operator - (const bign& b){  
        bign c = *this; int i;  
        for (i = 0; i < b.len; i++){  
            c.d[i] -= b.d[i];  
            if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;  
        }  
        while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;  
        c.clean();  
        return c;  
    }  
    bign operator * (const bign& b)const{  
        int i, j; bign c; c.len = len + b.len;   
        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)   
            c.d[i+j] += d[i] * b.d[j];  
        for(i = 0; i < c.len-1; i++)  
            c.d[i+1] += c.d[i]/10, c.d[i] %= 10;  
        c.clean();  
        return c;  
    }  
    bign operator / (const bign& b){  
        int i, j;  
        bign c = *this, a = 0;  
        for (i = len - 1; i >= 0; i--)  
        {  
            a = a*10 + d[i];  
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;  
            c.d[i] = j;  
            a = a - b*j;  
        }  
        c.clean();  
        return c;  
    }  
    bign operator % (const bign& b){  
        int i, j;  
        bign a = 0;  
        for (i = len - 1; i >= 0; i--)  
        {  
            a = a*10 + d[i];  
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;  
            a = a - b*j;  
        }  
        return a;  
    }  
    bign operator += (const bign& b){  
        *this = *this + b;  
        return *this;  
    }  
  
    bool operator <(const bign& b) const{  
        if(len != b.len) return len < b.len;  
        for(int i = len-1; i >= 0; i--)  
            if(d[i] != b.d[i]) return d[i] < b.d[i];  
        return false;  
    }  
    bool operator >(const bign& b) const{return b < *this;}  
    bool operator<=(const bign& b) const{return !(b < *this);}  
    bool operator>=(const bign& b) const{return !(*this < b);}  
    bool operator!=(const bign& b) const{return b < *this || *this < b;}  
    bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}  
  
    string str() const{  
        char s[maxn]={};  
        for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';  
        return s;  
    }  
};  
  
istream& operator >> (istream& in, bign& x)  
{  
    string s;  
    in >> s;  
    x = s.c_str();  
    return in;  
}  
  
ostream& operator << (ostream& out, const bign& x)  
{  
    out << x.str();  
    return out;  
}

ll T;
bign ans = 1, n, a, b;
bign gcd(bign a, bign b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}
bign lcm(bign a, bign b) {
	return a * b / gcd(a, b);
}
void run(bign x) {
	x = ((x - bign(1)) % n + n) % n + bign(1);
	bign sz = 0, tmp = x;
	if(bign(1) <= tmp && tmp <= a + b - n) {
		sz += 1;
		tmp += n * bign(2) - a - b;
	} else if(a + b - n + bign(1) <= tmp && tmp <= a) {
		sz += 1;
		tmp = a + bign(1) - tmp;
	} else if(a + bign(1) <= tmp && tmp <= n) {
		sz += 1;
		tmp = n * 2 - b + bign(1) - tmp;
	}
	while(tmp != x) {
		if(bign(1) <= tmp && tmp <= a + b - n) {
			bign step = 0;
			if(bign(1) <= x && x <= a + b - n && x >= tmp && (x - tmp) % (n * 2 - a - b) == 0) {
				step = (x - tmp) / (n * bign(2) - a - b);
			} else {
				step = (a + b - n - tmp + (n * 2 - a - b)) / (n * bign(2) - a - b);
			}
			sz += step;
			tmp += step * (n * bign(2) - a - b);
		} else if(a + b - n + bign(1) <= tmp && tmp <= a) {
			sz += 1;
			tmp = a + bign(1) - tmp;
		} else if(a + bign(1) <= tmp && tmp <= n) {
			sz += 1;
			tmp = n * 2 - b + bign(1) - tmp;
		}
	}
	ans = lcm(ans, sz);
	// cerr << sz << endl;
}
int main() {
	cin >> T;
	while(T --) {
		ans = 1;
		cin >> n >> a >> b;
		if(a == 1 && b == 1) {
			cout << 1 << endl;
			continue;
		}
		if(a == 1) {
			cout << 2 << endl;
			continue;
		}
		if(b == 1) {
			cout << 2 << endl;
			continue;
		}
		if(a + b <= n) {
			cout << 4 << endl;
			continue;
		}
		run(a);
		run(a + b - n + 1);
		run(n);
		run(a + 1);
		run(1);
		run(a + b - n);
		cout << ans * 2 % P << endl;
	}
	return 0;
}

出题思路

本场的压轴题,考察的算法并不高级,但是需要部分的数学推理。

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务