Good Bye 2022: 2023 is NEAR

news/2024/11/17 6:27:45/

A.B略

C.鸽巢原理+中国剩余定理

首先,显然所有数必须两两相同,不然加上任何整数必定会产生gcd >= 2的组合

然后我们手玩可以发现奇偶性,我们至少不能使得有两个数同时是偶数,如果出现两个偶数,两个奇数,例如2 4 5 7,那么无论x选择什么,都至少会出现两个偶数,进一步地,我们发现只要存在min(奇数个数,偶数个数) >= 2,那么就一定会出现两个偶数,也就是出现两个mod 2 == 0的数.进一步拓展,我们如果想要让整个数组至多出现一次mod p == 0的数, 我们贪心的做法是选择mod p得到的值出现次数最少的数,假设mod p == t,我们只要选择x mod p = (p - t)就可以让这个数被p整除,同理,如果出现次数最少的数 >= 2,也是无解的.我们知道一个数mod p 得到的值为0 ~ p - 1,由鸽巢原理,当p > n / 2时,出现次数最少的那个数一定<= 1,所以我们枚举p (2~n / 2)且p为质数(当然不是质数也可以),然后判断mod p的值最小次数是否大于等于2即可.

如果对于p ∈ [2, n / 2]都满足以上条件,我们最后选择的x只要满足x mod 2 == x1, x mod 3 == x2...,x1,x2..这些模数由上面的假设可知,是两两互质的,所以由CRT可知这个方程组一定有整数解.

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e5 + 10;
int n, k, a[N];
void solve() {set<int> s;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];s.emplace(a[i]);}if (s.size() < n) return cout << "NO\n", void(0);for (int p = 2; p <= n / 2; ++p) {vector<int> cnt(110, 0);for (int i = 1; i <= n; ++i) {++cnt[a[i] % p];}int mn = INF;for (int i = 0; i <= p - 1; ++i) {mn = min(mn, cnt[i]);}if (mn >= 2) return cout << "NO\n", void(0);}cout << "YES\n";
}
signed main() {IOS;int T;cin >> T;while (T--) solve();
}

D.并查集

手玩可知对于每个i,都要满足每个数在ai, bi, ci中至少出现两次.

如果ai == bi,那么第三个数ci 1 ~ n随便选.

否则,ci只能选择ai 或者 bi,如果我们选择了ai,那么必须在另外一个点选择bi,如果在另外一个点选择了bi,必须在另外一个点选择被占用的那个数,层层的牵制关系可以表示为一张图,观察图发现,只有基环树才可以满足分配条件,在这种情况下,共有两种方案.

我们用并查集维护图的边数和点数,ai -> bi,如果是自环,那么方案数 * n,如果是基环树, 那么方案数 * 2,否则方案数为0.

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e5 + 10, MOD = 998244353;
int n, k, a[N], b[N], fa[N], cv[N], ce[N], sl[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {int fx = find(x), fy = find(y);++ce[fy];if (fx == fy) return;fa[fx] = fy;cv[fy] += cv[fx], ce[fy] += ce[fx];sl[fy] |= sl[fx];
}
void solve() {cin >> n;for (int i = 1; i <= n; ++i) cv[i] = 1, ce[i] = 0, fa[i] = i, sl[i] = 0;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) cin >> b[i];for (int i = 1; i <= n; ++i) {merge(a[i], b[i]);if (a[i] == b[i]) sl[find(b[i])] = 1;}int ans = 1;map<int, int> vis;// for (int i = 1; i <= n; ++i) {// int fi = find(i);// cout << fi << " " << ce[fi] << " " << cv[fi] << "\n";// }for (int i = 1; i <= n; ++i) {if (vis[find(i)]) continue;if (ce[find(i)] != cv[find(i)]) ans = 0;if (sl[find(i)]) (ans *= n) %= MOD;else (ans *= 2) %= MOD;vis[find(i)] = 1;}cout << ans << "\n";
}
signed main() {IOS;int T;cin >> T;while (T--) solve();
}

E.计数 + 概率

 我们很容易想到按边处理,可以知道某条边的两端的蝴蝶数只有在处理过这条边之后才会变化,而某条边的贡献就是选择两只的蝴蝶的概率.我们只要求出处理完之后两端的蝴蝶数的期望是多少就行,在这道题,每个点只有一个蝴蝶,也就是说我们只要求出每条边的两点的蝴蝶是否移动就行.

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e5 + 10, MOD = 998244353;
int n, k, a[N], b[N], fa[N], cv[N], ce[N], sl[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {int fx = find(x), fy = find(y);++ce[fy];if (fx == fy) return;fa[fx] = fy;cv[fy] += cv[fx], ce[fy] += ce[fx];sl[fy] |= sl[fx];
}
void solve() {cin >> n;for (int i = 1; i <= n; ++i) cv[i] = 1, ce[i] = 0, fa[i] = i, sl[i] = 0;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) cin >> b[i];for (int i = 1; i <= n; ++i) {merge(a[i], b[i]);if (a[i] == b[i]) sl[find(b[i])] = 1;}int ans = 1;map<int, int> vis;// for (int i = 1; i <= n; ++i) {// int fi = find(i);// cout << fi << " " << ce[fi] << " " << cv[fi] << "\n";// }for (int i = 1; i <= n; ++i) {if (vis[find(i)]) continue;if (ce[find(i)] != cv[find(i)]) ans = 0;if (sl[find(i)]) (ans *= n) %= MOD;else (ans *= 2) %= MOD;vis[find(i)] = 1;}cout << ans << "\n";
}
signed main() {IOS;int T;cin >> T;while (T--) solve();
}

F.计数+lucas定理+范德蒙恒等式

 

 

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
int n, x, y;
bool issub(int a, int b) {if (a < 0 || b < 0) return 0;return (a | b) == b;
}
signed main() {IOS;cin >> n >> x >> y;int ans = 0;for (int t = y; t; t = (t - 1) & y) {for (int i = 0; i < 21; ++i) {if (t >> i & 1 && issub(x - (1ll << i), n * t - (1ll << i))) {ans ^= (1ll << i);}}}cout << (ans * (n & 1)) << "\n";
}


http://www.ppmy.cn/news/8435.html

相关文章

Linux多进程编程之exec函数族使用

Linux多进程编程之exec函数族使用

Linux多进程编程之exec函数族使用1.exec函数族是什么2.execl函数具体使用3.execlp4.exec后面不同字母所代表的含义1.exec函数族是什么 顾名思义&#xff0c;它并不只是一个函数&#xff0c;而是以exec开头的六个函数&#xff0c;并且是没有exec这个函数的&#xff08;就像TCP/…
阅读更多...
C++中STL的vector扩容机制

C++中STL的vector扩容机制

目录前言发生扩容扩容机制size()和capacity()reserve()和resize()前言 前阵子面试的时候&#xff0c;被问到往vector中插入一个数据可能会发生什么&#xff1f; 我答:可能会扩容; 为啥vector支持变长&#xff1f; 我答:它实在堆上动态申请内存&#xff0c;因此有自己的一套扩容…
阅读更多...
保护性暂停设计模式

保护性暂停设计模式

目录 保护性暂停设计模式 获取结果 产生结果 总代码实现 测试 增加超时效果的Guarded suspension get(long timeout) 测试 保护性暂停设计模式 Guarded Suspension 即 保护性暂停; 是一种等待唤醒机制的一种规范 ,也可以理解为使用中设计模式,Java的API很多都按照保护性…
阅读更多...
android中service实现原理分析

android中service实现原理分析

前言&#xff1a; 一开始的目标是解决各种各样的ANR问题的&#xff0c;我们知道&#xff0c;ANR总体上分有四种类型&#xff0c;这四种类型有三种是和四大组件相对应的&#xff0c;所以&#xff0c;如果想了解ANR发生的根因&#xff0c;对安卓四大组件的实现流程是必须要了解的…
阅读更多...
第一个完整的CMake工程

第一个完整的CMake工程

第一个完整的CMake工程一、概述二、准备工作2.1 创建工程2.2 创建源码目录三、换个地方保存目标二进制文件3.1 add_subdirectory 指令说明3.2 重设目标二进制生成目录四、如何安装4.1 目标文件的安装4.2 普通文件的安装4.3 非目标文件的可执行程序安装(比如脚本之类)&#xff1…
阅读更多...
【自学Java】Java选择结构if

【自学Java】Java选择结构if

Java选择结构if Java语言if条件判断 在 Java 中&#xff0c;关键字 if 是用于测试某个条件&#xff08;布尔型或逻辑型&#xff09;的语句是否满足一定的条件&#xff0c;如果满足特定的条件&#xff0c;则会执行 if 后面的大括号 {} 括起来的代码块&#xff0c;如果没有代码…
阅读更多...
领导的本质就是：管理自己，影响别人

领导的本质就是：管理自己，影响别人

欲戴皇冠&#xff0c;必承其重。作为领导者&#xff0c;就应当承担相应的职责。管理好自己&#xff0c;下面还有很多双眼睛看着你&#xff0c;正人先正己&#xff0c;身正令才行&#xff0c;自己做好了&#xff0c;才可能影响到别人&#xff0c;成为一位受人尊重的领导者。 有…
阅读更多...
一名普通Java程序员的2022的总结和2023的展望

一名普通Java程序员的2022的总结和2023的展望

前言今天是元旦节&#xff0c;也是2023年的第一天&#xff0c;首先祝各位亲朋好友们元旦快乐&#xff0c;在新的一年全家身体康健&#xff0c;诸事顺遂&#xff0c;阖家幸福&#xff0c;最重要的是身体健康&#xff0c;工作顺利&#xff0c;永无BUG永不加班&#xff01;&#x…
阅读更多...
最新文章

Copyright @ 2022~2023