潍坊网站建设服务,品牌策划方案模板,wordpress结合python,asp.net 网站开发实例#x1f33c;小宇#xff08;治愈版#xff09; - 刘大拿 - 单曲 - 网易云音乐
OI赛制且难度对标蓝桥杯省赛#xff08;#x1f625;真难#xff0c;第三题做了几百年#xff0c;第四题只敢骗骗分#xff09;
花了10块钱#x1f643; 买官网的思路#xff0c;结果… 小宇治愈版 - 刘大拿 - 单曲 - 网易云音乐
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 113 3也可以是等本身所以3和11也是只因数一开始钻牛角尖了 解法1 AC 100% 因数中只要存在偶数也就是不全为奇数累乘的n就是偶数 所以当n是偶数说明质因数中存在偶数当n是奇数质因数全为奇数 所以n是奇数时输出Yesn是偶数时输出No #includeiostream
#includecstdio //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)) coutYesendl;else coutNoendl;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 2m % i 0则 m 不是质数 #includeiostream
#includecstdio //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)) coutYesendl;else coutNoendl;t--;}return 0;
}第10个样例Time Limit ExceededTLE了 输入3由于 m * m 3连 m 2都不满足所以没经过判断直接return true;了 解法3 AC 60% 投机取巧骗分的方法关键是快只用了5分钟分也不少 #includeiostream
#includecstdio //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)) coutYesendl;else coutNoendl;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%
#includeiostream
#includecstdio //scanf()
#includealgorithm //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];}coutMin;return 0;
}思路很清晰啊怎么会错呢原来是第13行初始最小值设置成1e8了 而题目原文却是 所以设置最小值直接将题目中的范围粘贴过来好了。。 最大值一般设为负数 毕竟70%的样例都是大于1e8的 AC 100%
#includeiostream
#includecstdio //scanf()
#includealgorithm //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];}coutMin;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%
#includeiostream
#includecstdio //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);}coutans;return 0;
}做了2小时才AC 5%666 问题在哪呢 1dfs就不适合最短路指数级复杂度一般用Dijksta的堆优化求单源最短路 2漏了如果到达不了要输出-1的情况补上这个就AC 10% 3代码里默认(1, 1)能飞这是错误的 因为只是样例中的(1, 1)能飞存在(1, 1)不能飞走几步才能飞的情况 最后的
coutans;
改成
if(ans 3000) cout-1;
else coutans;
就AC 10% 好的下一步考虑用stl的优先队列priority_queue优化Dijkstra 这已经是最简单的做法了如果能成估计只需要60行 不行了堆优化的Dijkstra虽然可以用stl的最大最小值优先队列大小根堆但是还得学习什么“链式前向星”也就是静态的邻接表《啊哈算法》里有讲邻接表但是我想先放放先把简单的更易拿分的掌握了两个月以内再回来克服它 2023/02/12
1027留坑
四P9066 [yLOI2023] 腐草为萤
P9066 [yLOI2023] 腐草为萤 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
难度提高/省选-
题目就不放了感兴趣的自己去模拟 样例骗分吧
AC 5%
#include iostream
using namespace std;
int a[110], b[110];
int main()
{int n;cinn;for(int i 0; i n; i)cina[i]; //初始位置for(int i 0; i n; i)cinb[i]; //亮度for(int i 1; i n; i) {if(b[i] b[i - 1])couta[i] 0;else if(b[i] b[i - 1])cout0 0;elsecout0 a[i - 1];}return 0;
}
