网站描述,鲜花网站建设策划方案书,成都网站建设scdzks,想自己做网站推广文章目录 A. Haitang and GameE.Haitang and MathJ. Haitang and TriangleK. Haitang and Ava A. Haitang and Game
通过审题可以知道#xff0c;最后的胜者和若干次操作后最多能增加的数的奇偶有关。
由于 a i a_i ai 较小#xff0c;所以我们枚举每一个没出现过的 x … 文章目录 A. Haitang and GameE.Haitang and MathJ. Haitang and TriangleK. Haitang and Ava A. Haitang and Game
通过审题可以知道最后的胜者和若干次操作后最多能增加的数的奇偶有关。
由于 a i a_i ai 较小所以我们枚举每一个没出现过的 x , x ∈ [ 1 , 1 e 5 ] x,x\in[1,1e5] x,x∈[1,1e5] 考虑如何让 x x x 出现很简单有两个数的 g c d gcd gcd 等于 x x x 呗好像说了废话。
那我们怎么快速寻找这么两个数呢在遍历 x x x 的时候查找它的所有倍数如果出现过并且这些所有的倍数 g c d gcd gcd 值为 x x x 的话则 x x x 可以出现。如果 x % 2 1 x\%21 x%21 先手获胜否则后手获胜时间复杂度 O ( T n l o g n ) O(Tnlogn) O(Tnlogn) 。
#include bits/stdc.h
#define int long long
using namespace std;
#define YES YES
#define NO NO
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pairint, int pii;
const double eps 1e-9;
const int N 1e6 10;
const int M 1e6 10;
const int INF 1e18 10;
const int mod 1e9 7;
const int base 23333;
const double pi acos(-1.0);
//mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int a[N];
void solve()
{vectorint jl(1e5 10, 0);int n;cin n;for(int i 1;i n;i){cin a[i];jl[a[i]] 1;}int cnt 0;for(int i 1;i 1e5;i){if(jl[i]) continue;int flag 0, now 0;for(int j i;j 1e5;j i){if(jl[j]){if(flag 0){now j;flag 1;}else now __gcd(now, j);}}if(now i) cnt;}if(cnt % 2 1) cout dXqwq \n;else cout Haitang \n;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t 1;cin t;while (t--) solve();return 0;
}E.Haitang and Math
赛时一直在调 O ( T n ) O(T\sqrt{n}) O(Tn ) 的做法但是没调出来都这么轻量级了还不让过真是可恶。
比赛结束之后才发现居然有 P o l l a r d R h o Pollard\ Rho Pollard Rho 这样的黑科技可以在 n 4 \sqrt[4]{n} 4n 的时间复杂度求得一个数的最大质因子真是学到了。
求出最大质因子之后就可以通过质因子分解分解出所有的质因子再通过 d f s dfs dfs 求出所有的因子对于 [ 1 , 108 ] [1,108] [1,108] 的所有 S ( m ) S(m) S(m) 求一下题目中的式子是否成立即可注意去重。时间复杂度有点玄学大概是 O ( T n l o g n ) O(\frac{T\sqrt{n}}{logn}) O(lognTn )交上去之后跑的飞起这个故事告诉我们学好算法还是很重要滴。
#include bits/stdc.h
#define int long long
using namespace std;
#define YES YES
#define NO NO
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pairint, int pii;
const double eps 1e-9;
const int N 1e6 100;
const int M 1e6 10;
const int INF 1e18 100;
const int mod 1e9 7;
const int base 23333;
// mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int max_factor, n, nn;
int quick_pow(int x, int p, int mod) // 快速幂
{int ans 1;while (p){if (p 1) ans (__int128)ans * x % mod;x (__int128)x * x % mod;p 1;}return ans;
}
bool Miller_Rabin(int p) // 判断素数
{if (p 2) return 0;if (p 2) return 1;if (p 3) return 1;int d p - 1, r 0;while (!(d 1)) r, d 1; // 将d处理为奇数for (int k 0; k 10; k){int a rand() % (p - 2) 2;int x quick_pow(a, d, p);if (x 1 || x p - 1) continue;for (int i 0; i r - 1; i){x (__int128)x * x % p;if (x p - 1) break;}if (x ! p - 1) return 0;}return 1;
}
int Pollard_Rho(int x)
{int s 0, t 0;int c (int)rand() % (x - 1) 1;int step 0, goal 1;int val 1;for (goal 1;; goal * 2, s t, val 1) // 倍增优化{for (step 1; step goal; step){t ((__int128)t * t c) % x;val (__int128)val * abs(t - s) % x;if ((step % 127) 0){int d __gcd(val, x);if (d 1) return d;}}int d __gcd(val, x);if (d 1) return d;}
}
void fac(int x)
{if (x max_factor || x 2) return;if (Miller_Rabin(x)) // 如果x为质数{max_factor max(max_factor, x); // 更新答案return;}int p x;while (p x) p Pollard_Rho(x); // 使用该算法while ((x % p) 0) x / p;fac(x), fac(p); // 继续向下分解x和p
}
vectorint pri;
mapint, int mp, cnt;
int ans;
int coun(int x)
{int res 0;while(x 0){res x % 10;x / 10;}return res;
}
void dfs(int now, int res, int tt)
{//cout now res tt \n;if(res tt) return;if(now pri.size()){if(tt % res 0 n % res ! 0 !cnt[res] coun(res) n - tt){//cout res \n;cnt[res] 1;ans;}return;}dfs(now 1, res, tt);if(mp[pri[now]]){mp[pri[now]]--;dfs(now, res * pri[now], tt);mp[pri[now]];}
}
void solve()
{srand((unsigned)time(NULL));cin n;ans 0;cnt.clear();for(int ii 1;ii min(n - 2, 108LL);ii){pri.clear();mp.clear();max_factor 0;nn n - ii;fac(nn);pri.push_back(max_factor);nn / max_factor;mp[max_factor];for(int i 2; i nn / i; i) {if(nn % i 0){pri.push_back(i);while (nn % i 0) {mp[i];nn / i;}}}if (nn 1){mp[nn];pri.push_back(nn);}//cout n - ii pri.size() \n;//for(auto u : pri) cout u mp[u] \n;dfs(0, 1, n - ii);}cout ans \n;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t 1;cin t;while (t--) solve();return 0;
}J. Haitang and Triangle n n n 个数相邻三三组合最多有 n − 2 n-2 n−2 种组合方式但是包含 1 1 1 的那一组一定组成不了三角形所以 k n − 2 kn-2 kn−2 时无解。 k 0 k0 k0 时形如 d , 2 d , 3 d , d − 1 , 2 d − 1 , 3 d − 1 , … , 1 , 1 d , 1 2 d d,2d,3d,d-1,2d-1,3d-1,\dots,1,1d,12d d,2d,3d,d−1,2d−1,3d−1,…,1,1d,12d 这样的排列是满足条件的 d ⌊ ( n − k ) 3 ⌋ d\lfloor \frac{(n-k)}3 \rfloor d⌊3(n−k)⌋。
那 k 0 k0 k0 怎么放呢不难发现把除了 1 1 1 的其他 m m m 个数按顺序发如 2 , 3 , 4 , … , m 2,3,4,\dots,m 2,3,4,…,m每个长度为三的字串都能构成一个三角形所以我们左边放 k 0 k0 k0 时的情况右边放其他数。再根据 d % 3 d\%3 d%3 的不同值往端点插入数增加构不成三角形的区间长度时间复杂度 O ( ∑ n ) O(\sum{n}) O(∑n)。
#include bits/stdc.h
#define int long long
using namespace std;
#define YES YES
#define NO NO
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pairint, int pii;
const double eps 1e-9;
const int N 1e6 100;
const int M 1e6 10;
const int INF 1e18 100;
const int mod 1e9 7;
const int base 23333;
// mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count())
void solve()
{int n, m;cin n m;vectorint flag(n 5);if(m n - 2){cout -1 \n;return;}int x n - m;int d x / 3;vectorint ans;if (x % 3 0) {for (int i 0;i d;i) {ans.push_back(d - i);ans.push_back(2 * d - i);ans.push_back(3 * d - i);}for (int i 1;i m;i) ans.push_back(3 * d i);}if (x % 3 1) { ans.push_back(n);for (int i 0;i d;i) {ans.push_back(d - i);ans.push_back(2 * d - i);ans.push_back(3 * d - i);}for (int i 1;i m;i) ans.push_back(3 * d i);}if (x % 3 2) {ans.push_back(3 * d 1);for (int i 0;i d;i) {ans.push_back(d - i);ans.push_back(2 * d - i);ans.push_back(3 * d - i);}ans.push_back(3 * d 2);for (int i 3;i m 2;i) ans.push_back(3 * d i);}for (auto x : ans) cout x ;cout \n;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t 1;cin t;while (t--) solve();return 0;
}K. Haitang and Ava
从前往后匹配 a v a ava ava 或者 a v a v a avava avava 串如果能匹配完输出 Y e s Yes Yes 否则输出 N o No No 时间复杂度 O ( ∑ S ) O(\sum{S}) O(∑S)。
#include bits/stdc.h
#define int long long
using namespace std;
#define YES YES
#define NO NO
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pairint, int pii;
const double eps 1e-9;
const int N 1e6 10;
const int M 1e6 10;
const int INF 1e18 10;
const int mod 1e9 7;
const int base 23333;
const double pi acos(-1.0);
//mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
void solve()
{string s;cin s;int pos 0;for(int i 0;i s.size();){if(i 5 s.size()){if(s[i] a s[i 1] v s[i 2] a s[i 3] v s[i 4] a){i 5;pos i;}else if(s[i] a s[i 1] v s[i 2] a){i 3;pos i;}else break;}else if(i 3 s.size()){if(s[i] a s[i 1] v s[i 2] a){i 3;pos i;}else break;}else break;}if(pos s.size()) cout Yes \n;else cout No \n;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t 1;cin t;while (t--) solve();return 0;
}
