思维训练1 Myth丶恋晨 2024-02-25 03:26 17阅读 0赞 ### 题目描述2 ### [Problem - A - Codeforces][] ![4b942838e22247cda9f6f0b75dbc3c65.png][] ### 题目分析 ### 思路一: 由于是连续的数,我们可以使用f1, f2, f3来记录连续数的开头数字,只可能有三种情况 ①开头数为第一个数-1 ②开头数为第一个数 ③开头数为第一个数+1 分别观察这三个情况,如果都不符合要求说明此只能记为NO 如果这三种情况有一种符号就记为YES #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 10; void solve() { int flag1 = 0, flag2 = 0, flag3 = 0; ll n, a[N]; cin >> n; cin >> a[1]; ll f1 = a[1]; ll f2 = a[1] - 1; ll f3 = a[1] + 1; for(int i = 2; i <= n; i ++) { cin >> a[i]; } for(int i = 1; i <= n; i ++) { if(f1 <= a[i] + 1 && f1 >= a[i] - 1) { f1 ++; } else { flag1 = 1; } } for(int i = 1; i <= n; i ++) { if(f2 <= a[i] + 1 && f2 >= a[i] - 1) { f2 ++; } else { flag2 = 1; } } for(int i = 1; i <= n; i ++) { if(f3 <= a[i] + 1 && f3 >= a[i] - 1) { f3 ++; } else { flag3 = 1; } } if(flag1 == 1 && flag2 == 1 && flag3 == 1)cout << "NO" << '\n'; else cout << "YES" << '\n'; return; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while(t --) { solve(); } return 0; } 思路二: 由于是连续的一段,所以只能连续往左移或者连续往右移,最左边的只能向右移,最右边的只能向左移(这两个数的移动可以改变中间的空隙的大小,故最多空隙大小不能大于2)对于中间的数无论是向左移还是向右移都不能改变其真正中间空隙的大小 #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; void solve() { int n, a[N]; int cnt = 0; cin >> n; for(int i = 1; i <= n; i ++) { cin >> a[i]; } for(int i = 2; i <= n; i ++) { cnt += a[i] - a[i - 1] - 1; } if(cnt > 2)cout << "NO" << '\n'; else cout << "YES" << '\n'; } int main() { int t; cin >> t; while(t --) { solve(); } return 0; } ### 题目描述2 ### [Problem - B - Codeforces][] ![55d17d412f794bceaa97765f2203a675.png][] ### 题目分析 ### 我们可以假象使用一个数组c来描述了操作的情况, ci < 0 表示 ci = -k \* ai,也就是经行了k次的减ai的操作, ci > 0 表示 ci = k \* ai,也就是经行了k次的加ai的操作 ci = 0 表示没有经行任何的操作 我们发现操作一定是先减后加的为了使用最少的操作,也就是k最小,其中先减后加的操作中必有一个操作为0步,我们可以从每一步开始一一枚举为0的操作,最后从这个位置分别向左和向右计算出整个c数组,最后找出最小的操作即可 ![65bc4df527da44019801aa3b9e2539ac.jpeg][] #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e5 + 10; ll a[N], b[N], n; int main() { ll ans = 8e18; cin >> n; for(ll i = 1; i <= n; i ++)cin >> a[i]; for(ll i = 1; i <= n; i ++) { ll cnt = 0; memset(b, 0, sizeof b); for(ll j = i - 1; j >= 1; j --)//向左 { ll k = 1 - b[j + 1] / a[j]; b[j] = - k * a[j]; cnt += k; } for(ll j = i + 1; j <= n; j ++)//向右 { ll k = 1 + b[j - 1] / a[j]; b[j] = k * a[j]; cnt += k; } ans = min(ans, cnt); } cout << ans; return 0; } ### 题目描述3 ### [Problem - C - Codeforces][] ![09772d0520d143ef921ff62c82b0a447.png][] ### 题目分析 ### 对于带有绝对值的,我们首先需要想到去掉绝对值或者说确定这个绝对值所代数的具体的正负号,对于构造问题,我们可以考虑顺序,逆序跳序 我们先思考顺序:12 34 56 78 这样由于第一部分全部为负,故我们逆序思考 87 65 43 21 ![5c5c213169404d57893fcf720ff442cd.jpeg][] 通过上图我们发现在逆序过后每颠倒两个数就会多一个2,故序列得以构造 #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int n, k, a[N]; int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> k; n = n * 2; for(int i = 1; i <= n; i ++)a[i] = n - i + 1; for(int i = 1; i <= k; i ++)swap(a[2 * i], a[2 * i - 1]); for(int i = 1; i <= n; i ++)cout << a[i] << ' '; return 0; } ### 题目描述4 ### [Problem - D - Codeforces][] ![e87b00c60a984318afbf116499a2c9d6.png][] ### 题目分析 ### ![dc5024ab4229498f8f4d41ab9fb7403d.jpeg][] #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e7 + 10, inf = 2e9; int minp[N]; void euler(ll n) { bitset<N>vis; vector<ll> primes; vis[0] = vis[1] = true; minp[1] = 1; for(ll i = 2; i <= n; i ++) { if(!vis[i])primes.push_back(i),minp[i] = i; for(int j = 0; j < primes.size() && i * primes[j] <= n; j ++) { vis[i * primes[j]] = true; minp[i * primes[j]] = primes[j]; if(i % primes[j] == 0)break; } } } void solve() { ll x, y; cin >> x >> y; if(y - x == 1)cout << -1 << '\n'; else { ll ans = inf; y-= x; while(y > 1) { ll p = minp[y]; ans = min(ans, ((-x) % p + p) % p); while(y % p == 0)y /= p; } cout << ans << '\n'; } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; euler(1e7); cin >> t; while(t --) { solve(); } return 0; } ### 题目描述5 ### [Problem - A - Codeforces][Problem - A - Codeforces 1] ![d48cd562828949559d0d5fb8883677f8.png][] ### 题目分析 ### 对于此题意是删除左右两端连续的串,使留下的0以及删除的1最大值最小最终只剩下一部分,我们可以使用双指针来枚举这一部分,**c0 : 保留下来0的个数, c1 : 删除掉的1的个数**,枚举左端点,当c0 == c1时右端点确定 ![cfe1e60e32ea42fca3e1ad0986ca52e7.jpeg][] 在这两个数发生变化的时候一方变化,另一方必定不变,故一定会出现相交的点此点即为答案,找出最小的即可 #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; char s[N]; void solve() { int c1 = 0, c0 = 0, ans = 3e5 + 10; cin >> s + 1; int n = strlen(s + 1); for(int i = 1; i <= n; i ++)if(s[i] == '1')c1 ++; for(int i = 1, j = 0; i <= n; i ++) { while(j + 1 <= n && c0 < c1) { j ++; if(s[j] == '0')c0 ++; else c1 --; } ans = min(ans, max(c1, c0)); if(s[i] == '1')c1 ++; else c0 --; } cout << ans << '\n'; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while(t --) { solve(); } return 0; } [Problem - A - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/477747/problem/A [4b942838e22247cda9f6f0b75dbc3c65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/60a090868ade494a8001b28e3e19f05c.png [Problem - B - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/477747/problem/B [55d17d412f794bceaa97765f2203a675.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/700e0bf2d97b46b1b4dcabbae75c6937.png [65bc4df527da44019801aa3b9e2539ac.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/a4b0013706344944b874fb3cf070aed3.png [Problem - C - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/477747/problem/C [09772d0520d143ef921ff62c82b0a447.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/a798bc9ad219461a826c133467992f7a.png [5c5c213169404d57893fcf720ff442cd.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/e98bd811b3e446058788b834444e5b8f.png [Problem - D - Codeforces]: https://codeforces.com/group/vfMYBJyMgZ/contest/477747/problem/D [e87b00c60a984318afbf116499a2c9d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/6033099a0d234509985a7fa17ca8654b.png [dc5024ab4229498f8f4d41ab9fb7403d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/34bb75f3777b49b795101767abbe0a75.png [Problem - A - Codeforces 1]: https://codeforces.com/group/vfMYBJyMgZ/contest/478562/problem/A [d48cd562828949559d0d5fb8883677f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/5615e8ec8e684087a8953afbed635a79.png [cfe1e60e32ea42fca3e1ad0986ca52e7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/c25212a4dd5b4071b74f334ce41e42c5.png
相关 【Java从入门到大牛】编程思维训练 本文讲解了几个小案例,巩固了之前学习Java的一些基础知识,同时积累了一定的代码量 本是古典 何须时尚/ 2024年04月26日 02:40/ 0 赞/ 39 阅读
相关 培养python思维(1) 于Python新手来说,写代码很少考虑代码的效率和简洁性,因此容易造成代码冗长、执行慢,这些都是需要改进的地方。本文是想通过几个案列给新手一点启发,怎样写python代码... 短命女/ 2024年04月20日 08:41/ 0 赞/ 24 阅读
相关 思维训练1 题目描述2 [Problem - A - Codeforces][] ![4b942838e22247cda9f6f0b75dbc3c65.png][] 题 Myth丶恋晨/ 2024年02月25日 03:26/ 0 赞/ 18 阅读
相关 思维训练2 题目描述1 [Problem - A - Codeforces][] ![e71625cd70d04988bc3ca5f1b6952b95.png][] 题目分析 偏执的太偏执、/ 2024年02月21日 09:59/ 0 赞/ 8 阅读
相关 思维训练3 题目描述1 [Problem - A - Codeforces][] ![af3e7b33dd1442779c7b42dd43903341.png][] 题目分析 ゝ一世哀愁。/ 2024年02月20日 10:49/ 0 赞/ 5 阅读
相关 思维训练4 题目描述1 [Problem - A - Codeforces][] ![a3b5e80a6dc8425f98ef43fb5a884aaa.png][] 题目分析 末蓝、/ 2024年02月19日 08:32/ 0 赞/ 10 阅读
相关 Yolov1训练笔记 24类心理卡牌检测 `1、使用标注工具对图像(W,H)进行标注:标注的数据是目标的左上和右下角坐 今天药忘吃喽~/ 2022年11月19日 12:46/ 0 赞/ 138 阅读
相关 基础数论训练1 \可以通过旁边的目录查看(´・ω・\`),或者Ctrl + F Least Common Multiple (HDU - 1019) 难度:0/5,1A 解法: 爱被打了一巴掌/ 2021年09月16日 01:42/ 0 赞/ 405 阅读
还没有评论,来说两句吧...