内容简介:顺序判断即比赛的时候忘记写 else 既然 PP 了,然后就 FST反正最后还是要前$ m \times k $ 个数字
A Got Any Grapes?
顺序判断即
比赛的时候忘记写 else 既然 PP 了,然后就 FST
#include <cstdio> int an,dm,mi; int gr,pu,bl; int main(){ scanf("%d%d%d", &an, &dm, &mi); scanf("%d%d%d", &gr, &pu, &bl); if(an > gr) { printf("NO\n"); return 0; } else gr -= an; if(pu + gr < dm){ printf("NO\n"); return 0; } else { if(pu <= dm) {dm -= pu; pu = 0;} else {pu -= dm; dm = 0;} if(gr < dm) { printf("NO\n"); return 0; } else gr -= dm; } if(gr + pu + bl < mi) printf("NO\n"); else printf("YES\n"); }
B Yet Another Array Partitioning Task
反正最后还是要前$ m \times k $ 个数字
直接离散化,然后见当前区间有$ m $ 个就收
#include <cstdio> #include <algorithm> const long long N = 2e5 + 1e4; struct node{ long long now, id; }b[N]; long long n, m, k, cnt, time; long long a[N]; bool vis[N]; bool cmp(node a, node b){ return a.now > b.now; } int main(){ scanf("%lld%lld%lld", &n, &m, &k); for(long long i = 1; i <= n; i++){ scanf("%lld", &a[i]); b[i].now = a[i], b[i].id = i; } std::sort(b + 1, b + n + 1, cmp); long long tmp = m * k; for(long long i = 1; i <= tmp; i++) vis[ b[i].id ] = true, cnt += b[i].now; printf("%lld\n",cnt); cnt = 0; for(long long i = 1; i <= n; i++){ cnt += vis[i]; if(cnt == m){ time++; time < k && printf("%lld ",i); cnt = 0; } } }
C. Trailing Loves (or L’oeufs?)
求 $ b $ 进制下 $ n! $ 的末尾的 0 的个数
显然我们要求中间乘出来有多少个$b$
接下来就是分解质因数,然后枚举求最小值即可
#include <cstdio> #include <cmath> const long long INF = 1e18 + 1e17; inline long long Min(long long a, long long b){return a < b? a: b;} struct node{ long long now, cnt; }pri[(int)(1e6)]; int pcnt; long long n, b, tmp, cnt, ans = INF; inline void get_pri(long long b){ tmp = std::sqrt(b); for(long long i = 2; i <= tmp; i++){ if(b % i == 0){ pri[ ++pcnt ] = (node){i, 0}; while(b % i == 0){ pri[pcnt].cnt++; b/=i; } } } if(b != 1) pri[ ++pcnt ] = (node){b, 1}; } int main(){ scanf("%lld%lld", &n, &b); get_pri(b); for(int i = 1; i <= pcnt; i++){ tmp = 1; cnt = 0; while(tmp * pri[i].now <= n){ tmp *= pri[i].now; if(tmp < 0 || tmp % pri[i].now != 0) break; cnt += n / tmp; } ans = Min(ans, cnt/pri[i].cnt); } printf("%lld\n", ans); }
D. Flood Fil
有一个非常显然的地方,就是我们每次有两个状态,当前联通部分向左对其或者想右对其
然后我们先把数列中的联通部分预处理出来,然后区间 dp 即可
#include <cstdio> #include <cstring> inline int Min(int a, int b){return a < b? a: b;} const int N = 5100; int n; int a[N], l[N], r[N], f[N][N]; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); l[1] = 1; for(int i = 2; i <= n; i++){ if(a[i] == a[i - 1]) l[i] = l[i - 1]; else l[i] = i; } r[n] = n; for(int i = n - 1; i >= 1; i--){ if(a[i] == a[i + 1]) r[i] = r[i + 1]; else r[i] = i; } memset(f, 0x3f, sizeof(f)); for(int i = 1; i<= n;i ++) f[ l[i] ][ r[i] ] = 0; for(int len = 0; len < n; len++){ for(int i = 1,j; i + len <= n; i++){ j = i + len; if(i > 1 && j < n && a[i - 1] == a[j + 1]) f[ l[i - 1] ][ r[j + 1] ] = Min(f[ l[i - 1] ][ r[j + 1] ],f[i][j] + 1); if(i > 1) f[ l[i - 1] ][j] = Min(f[ l[i - 1] ][j], f[i][j] + 1); if(j < n) f[i][ r[j + 1] ] = Min(f[i][ r[j + 1] ], f[i][j] + 1); } } printf("%d", f[1][n]); }
E. Arithmetic Progression
交互题目,60次询问内知道当前乱序等差数列的首项和公差
先二分找最大的,然后 random_shuffle
随机化询问,求与最大项差的 gcd 即为公差
#include <cstdio> #include <algorithm> int gcd(int a, int b){return b? gcd(b ,a%b): a;} inline int Min(int a, int b){return a < b? a: b;} inline int Aabs(int a){return a < 0? (0 - a): a;} const int N = 1e6 + 1e5; int n, global_tmp, d, max, chance_cnt = 60; int a[N]; inline bool has_num(int now){ printf("> %d\n",now); fflush(stdout); scanf("%d", &global_tmp); chance_cnt--; return global_tmp; } inline int binary_search_max(int max_limit){ int left = 0, rig = max_limit, mid, res; while(left <= rig){ mid = (left + rig) >> 1; if( has_num(mid) ) left = mid + 1; else rig = mid - 1, res = mid; } return res; } int main(){ scanf("%d", &n); max = binary_search_max(1e9); for(int i = 1; i <= n; i++) a[i] = i; for(int i = 1; i <= 5; i++) std::random_shuffle(a + 1, a + n + 1); for(int i = 1; i <= Min(n ,chance_cnt); i++){ printf("? %d\n", a[i]); fflush(stdout); scanf("%d", &global_tmp); if(global_tmp == max) continue; if(d == 0) d = Aabs(max-global_tmp); d = gcd(d , Aabs(max-global_tmp)); } fflush(stdout); printf("! %d %d\n", max - (n - 1) * d, d); }
F. Please, another Queries on Array?
这个题目首先得知道$\varphi(n)$的求法
然后就是乘积线段树和或线段树维护一下
就没有然后了
#include <cstdio> const int N = 4e5 + 1e4; const long long mod = 1e9 + 7; int n, q, x, y, z, pcnt; int a[N]; long long p[310], pri[N], inv[310]; char op[10]; inline long long ksm(long long a, long long p){ long long res = 1; while(p){ if(p & 1) res = (res * a) % mod; a = (a * a) % mod; p >>= 1; } return res; } inline void prime(){ for(int i = 2; i <= 300; i++){ for(int j = 1; j <= pcnt; j++) if(i % p[j] == 0) pri[i] |= pri[ p[j] ]; if(pri[i] == 0) {p[++pcnt] = i; pri[i] = (1LL << (pcnt - 1LL));} } } inline void get_inv(){ for(int i = 1; i <= pcnt; i++) inv[i] = ksm(p[i], mod - 2); } // Segment Tree Start struct node{ long long val,pri; void operator+= (const node &b){ this -> val = (this -> val * b.val) % mod; pri |= b.pri; } }tree[N << 2], lazy[N << 2]; inline void pushup(int now){ tree[now].val = (tree[now << 1].val * tree[now << 1 | 1].val) % mod; tree[now].pri = tree[now << 1].pri | tree[now << 1 | 1].pri; } inline void pushdown(int now, int lson, int rson){ if(lazy[now].pri != 0){ tree[now << 1].val = (1LL * tree[now << 1].val * ksm(lazy[now].val, lson)) % mod; tree[now << 1 | 1].val = (1LL * tree[now << 1 | 1].val * ksm(lazy[now].val, rson)) % mod; tree[now << 1].pri |= lazy[now].pri; tree[now << 1 | 1].pri |= lazy[now].pri; lazy[now << 1].val = (1LL * lazy[now << 1].val * lazy[now].val) % mod; lazy[now << 1 | 1].val = (1LL * lazy[now << 1 | 1].val * lazy[now].val) % mod; lazy[now << 1].pri |= lazy[now].pri; lazy[now << 1 | 1].pri |= lazy[now].pri; lazy[now].val = 1LL; lazy[now].pri = 0; } } inline void query_mut(int now, int left, int rig, int from, int to, int val){ if(from <= left && rig <= to){ tree[now].val = (1LL * tree[now].val * ksm(val, (rig - left + 1LL))) % mod; tree[now].pri |= pri[val]; lazy[now].val = (lazy[now].val * val) % mod; lazy[now].pri |= pri[val]; return ; } int mid = (left + rig) >> 1; pushdown(now, mid - left + 1LL, rig - mid); if(from <= mid) query_mut(now << 1, left, mid, from, to, val); if(to > mid) query_mut(now << 1 | 1, mid + 1, rig, from, to, val); pushup(now); } inline node query_sum(int now, int left, int rig, int from, int to){ if(from <= left && rig <= to) return tree[now]; int mid = (left + rig) >> 1; node res = (node){1, 0}; pushdown(now, mid - left + 1LL, rig - mid); if(from <= mid) res += query_sum(now << 1, left, mid, from, to); if(to > mid) res += query_sum(now << 1 | 1, mid + 1, rig, from, to); pushup(now); return res; } inline void build_tree(int now, int left, int rig){ lazy[now].val = 1; lazy[now].pri = 0; if(left == rig){ scanf("%lld", &tree[now].val); tree[now].pri = pri[ tree[now].val ]; return ; } int mid = (left + rig) >> 1; build_tree(now << 1, left, mid); build_tree(now << 1 | 1, mid + 1, rig); pushup(now); } // Segment Tree End int main(){ prime(); get_inv(); scanf("%d%d", &n, &q); build_tree(1, 1, n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); while(q--){ scanf("%s", op); if(op[0] == 'M'){ scanf("%d%d%d", &x, &y, &z); query_mut(1, 1, n, x, y, z); } else { scanf("%d%d", &x, &y); node tmp = query_sum(1, 1, n, x, y); for(int i = 1; i <= pcnt; i++){ if((tmp.pri >> (i - 1LL)) & 1LL) tmp.val = (((tmp.val * (p[i] - 1) ) % mod) * inv[i]) % mod; } printf("%lld\n", tmp.val); } } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode 第133场周赛解题报告
- Leetcode 第135场周赛解题报告
- Leetcode 第136场周赛解题报告
- Codeforces Round #530 (Div. 2) 解题报告
- The Cryptopals Crypto Challenges 解题报告(1)
- The Cryptopals Crypto Challenges 解题报告(2)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。