洛谷2月普及组(月赛)
🌼小宇（治愈版） - 刘大拿 - 单曲 - 网易云音乐
OI赛制且难度对标蓝桥杯省赛（😥真难，第三题做了几百年，第四题只敢骗骗分）
花了10块钱🙃 买官网的思路，结果还是习惯自己硬磕，别人的思路根本不想看，还不如自己百度
切记切记，OI赛制是部分分 + 无反馈
所以骗分很重要
骗分 = 样例 + 模拟 + 暴力
养成先测试再提交的好习惯，否则，你以为你天王盖地虎，原来是个二百五
👊总结
总结写在前头
1，骗分 = 样例 + 模拟 + 暴力
2，不论是codeforces还是洛谷，只做对样例，不给分，盲猜改革后的蓝桥杯也没分
3，不论是codeforces还是洛谷，凡是和数字有关的，都和奇偶数规律有着千丝万缕的关系
4，第三题，AC 100%需要（邻接表 + STL的priority_queue + Dijkstra），我还有邻接表没学，先留个坑，日后有时间回来做
目录
👊总结
👊一，P9063 [yLOI2023] 分解只因数
🌼解法1 AC 100%
🌼解法2 AC 90%
🌼解法3 AC 60%
👊二，P9064 [yLOI2023] 苦竹林
🌼AC 30%
🌼AC 100%
👊三，P9065 [yLOI2023] 云梦谣
🌼AC 5%
👊四，P9066 [yLOI2023] 腐草为萤
🌼AC 5%
👊一，P9063 [yLOI2023] 分解只因数
P9063 [yLOI2023] 分解只因数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
通过率 10%
难度：入门
首先要理解n不一定需要相乘得到的，比如 11 == 11，3 == 3，也可以是等本身，所以3和11也是只因数，一开始钻牛角尖了
🌼解法1 AC 100%
因数中只要存在偶数，也就是不全为奇数，累乘的n就是偶数
所以，当n是偶数，说明质因数中存在偶数；当n是奇数，质因数全为奇数
所以n是奇数时输出"Yes"，n是偶数时输出"No"
#include<iostream>
#include<cstdio> //scanf()
using namespace std;
typedef long long LL;
bool check(LL n)
{if(n % 2 == 1) return true;return false;
}
int main()
{int t;scanf("%d", &t);while(t) {LL n;scanf("%lld", &n);if(check(n)) cout<<"Yes"<<endl;else cout<<"No"<<endl;t--;}return 0;
}
5
2
No
3
Yes
4
No
6
No
9
Yes4
12
No
123
Yes
1234
No
12345
Yes
🌼解法2 AC 90%
常规解法，对质数，因数不熟练的新手，耗时比较久，比如我
质数：能被1和本身整除的数
1，遍历到m的平方差，即 i * i <= m
2，m % i == 0，则 m 不是质数
#include<iostream>
#include<cstdio> //scanf()
using namespace std;
typedef long long LL;
bool check(LL n)
{int flag = 1;if(n == 1 || n == 2) return false; //1不是质数, 2是偶数int m;for(m = 2; m * m <= n; ++m) {for(int i = 2; i * i <= m; ++i)if(m % i == 0) {flag = 0; //m不是质数break;}if(flag && n % m == 0) //m是质数且是n的因子if(m % 2 == 0) return false; //因子是偶数}return true;
}
int main()
{int t;scanf("%d", &t);while(t) {LL n;scanf("%lld", &n);if(check(n)) cout<<"Yes"<<endl;else cout<<"No"<<endl;t--;}return 0;
}
第10个样例，Time Limit Exceeded，TLE了
输入3，由于 m * m <= 3连 m = 2都不满足，所以没经过判断，直接return true;了
🌼解法3 AC 60%
投机取巧，骗分的方法，关键是快！只用了5分钟，分也不少
#include<iostream>
#include<cstdio> //scanf()
using namespace std;
typedef long long LL;
bool check(LL n)
{if(n == 2 || n == 4 || n == 6|| n == 8 || n == 10 || n == 12 || n == 14|| n == 16 || n == 18 || n == 20)return false;if(n == 3 || n == 5 || n == 9 || n == 15 || n == 21|| n == 7 || n == 11 || n == 13 || n == 17 || n == 19)return true;
}
int main()
{int t;scanf("%d", &t);while(t) {LL n;scanf("%lld", &n);if(check(n)) cout<<"Yes"<<endl;else cout<<"No"<<endl;t--;}return 0;
}
👊二，P9064 [yLOI2023] 苦竹林
P9064 [yLOI2023] 苦竹林 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
通过率 14%
难度：普及-
1，先对数组a从小到大排序
2，尺取法，对连续的m个数遍历，每次更新Min
将Min与 （尺取的最后一个元素 - 尺取的第一个元素） 作比较
复杂度O(logn + n - m) ；logn表示log2n，是快排的复杂度
不会尺取法的看这里
尺取法（图文解析、初学推荐）_小白小郑的博客-CSDN博客_尺取法
算法基础----尺取法（双指针）_jkaliang的博客-CSDN博客
1，尺取法是算法竞赛中,常用的优化技巧
2，它比暴力枚举区间的效率高很多（特别是数据量大时，比如10^6），是一种高效枚举区间的方法，用于求取有一定限制的区间个数或最短区间
3，本题中通过左边界右移,右边界右移的方法,找到满足区间,并用Min保留相减最小值（也就是题目中的ε）
注意！！！OI赛制没有反馈，所以首先要自己想多点全面，偏门的案例
来验证代码，不然很可能就是信心满满 = AC 30%
先别急着提交，下面我展示5组测试样例
10 6
1 8 26 33 41 17 102 27 11 5
226 2
1 4 9 12 13 15
15 3
1 2 3 4 5
26 4
1 7 8 3 4 6
410 4
120 240 550 1101 1199 2012 3312 5520 5523 5524
959然后，，，第一次30%
🌼AC 30%
#include<iostream>
#include<cstdio> //scanf()
#include<algorithm> //sort()
using namespace std;
int a[100010];
int main()
{int n, m;scanf("%d%d", &n, &m);for(int i = 0; i < n; ++i)scanf("%d", &a[i]); //读入数据sort(a, a + n);int Min = 1e8; //大坑for(int i = m - 1; i < n; ++i) {int j = i - (m - 1); //此时[j, i]刚好m个数if(a[i] - a[j] < Min)Min = a[i] - a[j];}cout<<Min;return 0;
}
思路很清晰啊，怎么会错呢？原来是第13行，初始最小值设置成1e8了
而题目原文却是：
所以，设置最小值，直接将题目中的范围粘贴过来好了。。
最大值一般设为负数
毕竟70%的样例都是大于1e8的
🌼AC 100%
#include<iostream>
#include<cstdio> //scanf()
#include<algorithm> //sort()
using namespace std;
int a[100010];
int main()
{int n, m;scanf("%d%d", &n, &m);for(int i = 0; i < n; ++i)scanf("%d", &a[i]); //读入数据sort(a, a + n);int Min = 1e9; //大坑for(int i = m - 1; i < n; ++i) {int j = i - (m - 1); //此时[j, i]刚好m个数if(a[i] - a[j] < Min)Min = a[i] - a[j];}cout<<Min;return 0;
}
复杂度O(n * logn)，也就是快排的复杂度，后面的O(n - m)相比O(nlogn)可忽略
👊三，P9065 [yLOI2023] 云梦谣
P9065 [yLOI2023] 云梦谣 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目有点长😅，通过率 6%
难度：普及+/提高
1，读入数据较多，我们用scanf不用cin
2，点与点之间路径一样，都为1，我觉得用dfs比Dijkstra好做
所以就是纯dfs（后面证明dfs❌）
然鹅。。第一次就AC 5% ，而且我四个测试样例都对了，，，，
🌼AC 5%
#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int a[3010][3010], book[3010][3010], b[3010][3010];
int fly[3010][3010], ans = 3000;
int n, m, k;void dfs(int x, int y, int step)
{int next[4][2] = { //方向数组, 循环得到下一步坐标{-1, 0}, //上{1, 0}, //下{0, -1}, //左{0, 1}}; //右//dfs第一步: 遍历int tx, ty; //临时变量for(int i = 0; i < 4; ++i) {tx = x + next[i][0]; //0表示每行第1个元素ty = y + next[i][1]; //1表示每行第2个元素//越界if(tx < 1 || ty < 1 || tx > n || ty > m)continue; //跳出本次循环//非障碍物且未走过if(a[tx][ty] != 0 && book[tx][ty] != 1) {book[tx][ty] = 1; //标记dfs(tx, ty, step + 1); //递归book[tx][ty] = 0; //取消标记}}//找到目标if(x == n && y == m) {ans = min(ans, step); //更新return; //返回上一步}
}int main()
{scanf("%d%d%d", &n, &m, &k);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)scanf("%d", &a[i][j]); //读入数据int r, t;for(int i = 0; i < k; ++i) {scanf("%d%d", &r, &t);fly[r][t] = 1; //可飞行}book[1][1] = 1; //初始已走过//得到全程走的最小值dfs(1, 1, 0);//得到飞的最小值for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)if(fly[i][j] == 1) { //可飞if(a[i][j] != a[1][1]) //高度不同dfs(i, j, 2);else //高度一样dfs(i, j, 1);}cout<<ans;return 0;
}
做了2小时才AC 5%，，，666
问题在哪呢？
1，dfs就不适合最短路（指数级复杂度），一般用Dijksta的堆优化求单源最短路
2，漏了，如果到达不了，要输出"-1"的情况（补上这个就AC 10%）
3，代码里默认(1, 1)能飞，这是错误的
因为只是样例中的(1, 1)能飞，存在(1, 1)不能飞，走几步才能飞的情况
最后的
cout<<ans;改成
if(ans == 3000) cout<<-1;
else cout<<ans;就AC 10%
好的，下一步考虑用stl的优先队列priority_queue优化Dijkstra
这已经是最简单的做法了，如果能成，估计只需要60行
不行了，堆优化的Dijkstra虽然可以用stl的最大最小值优先队列（大小根堆），但是还得学习什么“链式前向星”（也就是静态的邻接表），《啊哈算法》里有讲邻接表，但是我想先放放，先把简单的，更易拿分的掌握了，两个月以内再回来克服它
2023/02/12 👆👆👆
10：27留坑
👊四，P9066 [yLOI2023] 腐草为萤
P9066 [yLOI2023] 腐草为萤 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
难度：提高+/省选-
题目就不放了，感兴趣的，自己去模拟 + 样例骗分吧
🌼AC 5%
#include <iostream>
using namespace std;
int a[110], b[110];
int main()
{int n;cin>>n;for(int i = 0; i < n; ++i)cin>>a[i]; //初始位置for(int i = 0; i < n; ++i)cin>>b[i]; //亮度for(int i = 1; i < n; ++i) {if(b[i] > b[i - 1])cout<<a[i]<<" "<<0;else if(b[i] == b[i - 1])cout<<0<<" "<<0;elsecout<<0<<" "<<a[i - 1];}return 0;
}