陌研 - 个人主页动态 - 牛客网

发布(30) 评论刷题

2021-10-29 00:54

福建师范大学技术美术

题解 | #【模板】同余方程#

【同余方程】 模板题，直接用exgcd就行了，上一场的青蛙的约会搞懂了，自然就会了。 #include <bits/stdc++.h> #define int long long using namespace std; int exgcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1, y = 0; return a; } int nx, ny; int res = exgcd(b, a % b, nx, ny); x = ny; ...

0 点赞评论收藏

分享

2021-10-28 09:37

福建师范大学技术美术

题解 | #X-factor Chains#

【X-factor Chains】 题目需要让序列aaa尽可能的长，且ai∣ai+1a_i|a_{i+1}ai∣ai+1，即ai×t=ai+1a_i\times t = a_{i+1}ai×t=ai+1只要让ttt尽可能小就行了，也就是ttt是一个质数。 对xxx分解质因数得x=p1α1p2α2...pkαkx=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}x=p1α1p2α2...pkαk，即ai+1=ai×pja_{i+1}=a_i\times p_jai+1=ai×pj，只需要将质因数pjp_jpj排列...

0 点赞评论收藏

分享

2021-10-28 09:36

福建师范大学技术美术

题解 | #Prime Land#

【Prime Land】 先求出x=∏pieix=\prod p_i^{e_i}x=∏piei，然后对x−1x-1x−1分解质因数并输出。 #include <bits/stdc++.h> #define int long long using namespace std; const int N = 3e4 + 10; int power(int a, int b) { int res = 1; while (b) { if (b & 1) res *= a; a *= a; b >>= ...

0 点赞评论收藏

分享

2022-03-13 08:53

已编辑

福建师范大学技术美术

题解 | #Prime Distance#

【Prime Distance】 要找到LLL到R(L<R≤2147483647)R(L< R\le2147483647)R(L<R≤2147483647)之间的所有素数，仅需用maxR=46340\sqrt {max_R}=46340maxR=46340以内的素数进行筛选就足够了。 又因为∑(R−L)≤106\sum (R-L)\le 10^6∑(R−L)≤106，因此可以用埃氏筛在O(nlog⁡log⁡n)O(n\log\log n)O(nloglogn)的时间复杂度内筛出[L,R][L,R][L,R]内的质数。 注意：直接用me...

长途：错误样例： 1 1 10 其中1不是质数，但你最短距离中会输出1。另外你int T,但输入用的scanf("%lld",&T)

0 点赞评论收藏

分享

2021-10-28 09:34

福建师范大学技术美术

题解 | #Sum of Consecutive Prime Numbers#

【Sum of Consecutive Prime Numbers】 4×1074\times 10^74×107内有243365424336542433654个素数（可以用欧拉筛在O(4×107)O(4\times 10^7)O(4×107)的时间内求出）。 题目保证T≤1000,∑n≤4×107T\le 1000,\sum n\le 4\times 10^7T≤1000,∑n≤4×107， 对于每次查询nnn，可以用双指针维护连续的素数和，暴力的话是2.4×106×1032.4\times 10^6\times 10^32.4×106×103会超时，可以考虑减枝操...

0 点赞评论收藏

分享

2021-10-28 09:33

福建师范大学技术美术

题解 | #青蛙的约会#

【青蛙的约会】 设跳了ttt次后两个青蛙相遇，即x+(m×t)≡y+(n×t)(mod  L)x+(m\times t)\equiv y + (n\times t)(\mod L)x+(m×t)≡y+(n×t)(modL)。 方程可以转换成(m−n)×t+L×u=(y−x)(m-n)\times t + L\times u=(y-x)(m−n)×t+L×u=(y−x)。 根据裴蜀定理，可知方程ax+by=max+by=max+by=m有整数解时当且仅当mmm是aaa及bbb的最大公约数d=gcd⁡(a,b)d=\gcd(a,b)d=gcd(a,b)的倍数。 可以把无解的情况特判掉。 ...

0 点赞评论收藏

分享

2021-10-05 20:44

已编辑

福建师范大学技术美术

【A.gpa题解】 直接二分答案（答案为小数，注意精度）。 对于当前答案D，如果有更大的结果，则∑(s[i]c[i])/∑s[i]>D\sum (s[i]c[i])/\sum s[i] > D∑(s[i]c[i])/∑s[i]>D，即∑(s[i]c[i])>∑(s[i]D)⇒∑(s[i](c[i]−D)>0\sum (s[i]c[i])> \sum (s[i]D) \Rightarrow \sum (s[i](c[i]- D) > 0∑(s[i]c[i])>∑(s[i]D)⇒∑(s[i](c[i]−D)>0，删掉最小的k个，判断正负。 #i...

0 点赞评论收藏

分享

2021-10-04 21:36

福建师范大学技术美术

题解 | Different Integers 莫队

【Different Integers题解】 模板题，扔一个比较简洁的代码。 将指针起始位置定义在L=0,R=n+1，然后随着查询操作(l,r)进行移动，使得L=l,R=r。 需要注意的是查询的边界问题，l和r也包含在被查询的区间中。 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, len; int w[N], ans[N]; int get(int x) { return x / len; } struct Query { int id, l, r; ...

0 点赞评论收藏

分享

2021-09-13 10:41

福建师范大学技术美术

题解 | #都市的柏油路太硬#

【D.都市的柏油路太硬】克鲁斯卡尔重构树的板子题，直接套板子就行了。 #include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 5; // 点 const int M = 5e5 + 5; // 边 int n, m; // 点,边 // ========================================================================== // 题目定义的随机数 typedef uns...

0 点赞评论收藏

分享

2021-09-11 08:31

福建师范大学技术美术

题解 | #寻寻觅觅寻不到#

【B.寻寻觅觅寻不到】暴力，对于两个字符串a、b，如果a[pos]!=b[pos]，那么截取的k一定在pos处或者左边，枚举k就行了。特判有点麻烦。 #include <bits/stdc++.h> #define sz(x) (int)(x).size() using namespace std; const int N = 3e5 + 10; string s, t; int n1, n2, k; int main() { int T; cin >> T; while (T--) { cin >> s >...

0 点赞评论收藏

分享

2021-09-11 08:24

已编辑

福建师范大学技术美术

题解 | #踩不出足迹

【C.踩不出足迹】打表能发现规律，无论数组是什么，只会出现两种结果，cur=a_1 ^ a_2 ^...^ a_n和对cur逐位取反。取一个max就行了。 from math import * n,k = input().split(' ') n = int(n) k = int(k) a = input().split(' ') def f(cur): res = 0 for i in range(k): if (cur & (1<<i)) == 0: res = res | (1<<i) ...

0 点赞评论收藏

分享

2021-06-01 21:02

福建师范大学技术美术

题解 | #二刺猿浓度鉴定#

Ecout<<"GFD\nACH\nIBE"; Fcout<<"RPJI\nENMK\nTSGC\nFADB\nLQHO"; Hcout<<"DACBEEDCCBA";

0 点赞评论收藏

分享

2021-05-24 11:29

已编辑

福建师范大学技术美术

题解 | #集合操作#

集合操作 参考了大佬的代码：boringhaker 提交的代码 先將序列a排序。 如果 a[pos] 后边的数减去 k * p的平均值大于等于 a[pos - 1]，就不需要管pos前边的数。用后缀和找到 pos 的位置。 pos后边的数减去 (a[i] - key)/p*p。如果 k 依旧不为0，继续从大到小减去p。 #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e6+10; int a[N]; signed main(){ std::ios_base:...

0 点赞评论收藏

分享

2021-05-22 20:28

福建师范大学技术美术

题解 | #计算几何#

找规律。0： 00000(偶数个)1： 00001(奇数个)2： 00010(奇数个)3： 00011(偶数个) 4： 00100(奇数个)5： 00101(偶数个)6： 00110(偶数个)7： 00111(奇数个) 8： 01000(奇数个)9： 01001(偶数个)10：01010(偶数个)11：01011(奇数个)每四个数里面都包含两个满足条件的。 #include<bits/stdc++.h> #define int long long using namespace std; int solve(int x){ int res = 0; while(x)...

0 点赞评论收藏

分享

2021-05-02 22:14

福建师范大学技术美术

题解 | #D 迷阵#

二分搜索答案。代码里面有注释。 #include<bits/stdc++.h> using namespace std; int dir[4][2]= {{1, 0}, {0, 1}, {0, -1},{-1, 0}}; int n; int vis[110][110], a[110][110]; // 防止越界、或者重复访问 bool check(int x, int y){ if(x < 1 || x > n){ return false; } if(y < 1 || y > n){ retur...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务