伟大的IOI的博客

原题传送门 思路一眼线段树板子题。 用线段树来维护每一个区间和更改区间的值。 tag 函数主要是维护儿子的 sum 值。 懒标记在此题中主要指这个区间是否需要更改。 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include<bits/stdc++.h>using namespace std;const int maxn=1145141;int ans,n,m,a,b,c;struct tree { int l,r,sum,add;} t[maxn];void build(int u,int x,int y) { t[u].l=x; t[u].r=y; if(x==y) { t[u].sum=0; return ; } int mid=(x+y)>>1; build( ...

思路。这是一道挺简单的贪心，由于题目中说交换操作免费，所以我们尽量使用交换，不能交换了再用删除。 求要用的钱也很简单，我们用两个变量分别储存字符串中 $0$ 和 $1$ 的个数，然后开始交换，从字符串开头枚举到字符串结尾，如果遇到 $0$，就将 $1$ 的数量减 $1$，反之亦然。 要在每次减之前判断一下数量是否为空，为空就跳出，防止变成负数。 最后要删除的数量就是 $0$ 剩下的数量加 $1$ 剩下的数量。 AC代码。1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>using namespace std;int t,z,o,c;string s;int main(){ cin>>t; while(t--){ c=z=o=0; cin>>s; for(int i=0;i<s.size();i++){ if(s[i]=='0'){ z++; } else o++; } for(int i=0;i<s.siz ...

所以以后登洛谷也要用梯子了是吧（

题目大意给你 $m$ 组数列，每组数列中有 $t$ 个数，数列中的每个数的绝对值不超过 $n$，两个互为相反数的数中一个是叛徒，一个是好人，现让你判断其中是否有一个数列有全是叛徒的可能，只要有一个数列有就输出 YES，否则输出 NO。 思路因为只要某个数列中的某个数在这个序列中找不到相反数就有可能是叛徒，所以我们可以用两个数组 $a$ 和 $b$ 分别储存正数和负数。 $a{i}$ 表示数列中是否有 $i$，$b{i}$ 表示数列中是否有 $-i$。 所以我们只需要判断数列中是否有 $a{i} = 1 \operatorname{and} b{i}=1$，只要有一组，就说明不可能全是叛徒，输出 NO，如果都没有，说明有可能全是叛徒，输出 YES。 注意事项两个数组和标记每次循环前要清零，如果已经判定要输出 YES 时但数据还没有输入完要等输入完再输出（只是为了好看点）。 AC代码123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namesp ...

洛谷博客界面（留存） 洛谷博客阅读界面（留存） 洛谷博客编辑界面（留存） 洛谷博客后台（留存） 洛谷博客设置界面（留存） 洛谷博客主题设置界面（留存） 洛谷博客文章回收站界面（留存） 如果不出意外，本文将是我的最后一篇博客。 再见！洛谷博客！

CF868B Race Against Time 题解。 题目传送门 感觉此题还是挺坑的。 注意1.秒钟、分钟、时钟是会动的，但只能在开始的一瞬间动，并且移动的距离 $< 1$。 2.米莎可以瞬间移动因为她开挂了。 3.米莎想咋走就咋走（也就是说她既可以顺时针走也可以逆时针走）。 思路暴力模拟米莎的运动（真的很暴力，毕竟其他大佬的思路我也不懂）。 这里将表针视为不动，米莎每次走半个格，便可以变相地实现米莎的瞬间移动。 先顺时针走，移动的过程中判断是否碰到指针，碰到后再逆时针走，如果再次碰到，输出 NO 结束，如果有一次没碰到，输出 YES 结束。 在模拟时要统一单位，我这里统一成了秒。 AC 代码12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;long double t1,t2,shi,miao,fen,mm,mm2,mm3;//mm为起点所指的秒数，mm2为终点所指的秒数，mm3为时针所指 ...

此题暴力肯定过不了，会在第九个点 TLE。 暴力代码（#9 TLE）代码就不写注释了，反正 AC 不了。12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;struct node{ int a,b;}qj[114514],qjj[114514];bool f[114514],ff,fff[114514],ffff[114514],g[114514];int n,m,c,cc,jj;int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>qj[i].a>>qj[i].b; } for(int i=1;i<=m;i++){ cin>>qjj[i].a>>qjj[i].b; } for(int i=1;i<=n;i++){ ff=0;jj=0; for(int j= ...

思路。我们知道最初添加的液体越多，那么每个蚂蚁得到的液体也就越多，又因为标签里有深搜，所以可以用 DFS+二分解决（感觉说了一通废话），算是比较常规的一种解法了。 在此题中我们需要魔改一下建树，需在其中添加判断此边是否为超级管道和处理通过液体的百分比这两段代码。 DFS 和二分的代码是最重要的，但也是最简单的。 温馨提示：此题的码量有点逆天，根本不像正常的 DFS + 二分的题的码量，所以就不放完整代码了，也请各位注意。 其他就没什么了。 核心 DFS + 二分代码。12345678910111213141516171819202122232425262728void dfs(int x,int f) { for(int i=tou[x]; i; i=ed[i].nxt) { int y=ed[i].to; double res=0; if(y==f){ continue; } res=ll[x]*ed[i].w; if(ed[i].opt){ res*=res; } ll[y]+=res; dfs(y,x); }}bool zhao(double mid) ...

思路：此题其实很简单，不要被邪恶的出题人迷惑了双眼。 此题判断有解一共有两种情况。 通过题意可以知道将原数组排序后如果 $b{1} \ne b{2}$，那么最后的结果一定 $\ne 0$，这是第一种情况。 第二种情况其实就是第一种情况的变形，在排序后 $b{1} = b{2}$ 的情况下，如果 $b$ 中有一个数 $\bmod b_{1} \ne 0$，就可以把这个数放在第一位来满足第一种情况，所以输出 YES。 除这两种情况外其它都无解。 AC 代码：12345678910111213141516171819202122232425262728293031323334#include <iostream>#include <algorithm>using namespace std;int n,a[114514],m;bool f;int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>m; for(int j=1; j<=m; j++){ cin>>a[j]; ...

思路根据我们小学学的最小公倍数可知：1 与 3 的最小公倍数为 3，1 的乘数为 3；3 与 6 的最小公倍数为 6，3 的乘数为 2；6 与 10 的最小公倍数为 30，6 的乘数为 5；10 与 15 的最小公倍数为 30，10 的乘数为 3。 根据以上的推论，我们可以知道 3 个 1 元可以换成 1 个 3 元；2 个 3 元可以换成 1 个 6 元；5 个 6 元可以换成 3 个 10 元；3 个 10 元可以换成 2 个 15 元。 所以可以枚举每种钱币，能换的时候就换了它，最终便是最优解。 AC 代码想什么呢，自己写去！

思路：因为要判断是否单调不降，所以将这个数组从后往前扫一遍，便会遇到两种情况： 前一个数大于后一个数，便考虑将前一个数拆分，如果十位还大于个位，说明拆分后还不能单调不降，输出 NO，否则继续扫下去。 前一个数小于等于后一个数，便继续扫。 考虑完这两种情况，便可以愉快地 AC 了。 AC 代码： 12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;int a[114],n,t;bool f;int main() { cin>>t; while(t--){ cin>>n; f=0; for(int i=1; i<=n; i++){ cin>>a[i]; } for(int i=n; i>0; i--) { if(a[i-1]>a[i]) { int x=a[i-1]; int s=x/10,g=x%10; if(s<=g&& ...

思路：一道非常板的深搜题（但我还是求机房大佬把我的屎山代码修改后才完成的。呜呜我太蒻了）。 提供一个不同的思路。 由于本蒟蒻觉得用字符类型的地图进行深搜太麻烦了，所以在输入时将每个南瓜的位置用它们的价值替换，干草块用 0 表示，就将此题转化成普通的深搜了。 再将深搜板子上加一段统计价值的代码就可以愉快地 AC 了。 AC 代码：12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;int r,c,xx[4]={0,0,-1,1},yy[4]={1,-1,0,0},cont,s,e;char ma[10005][10005];int mapp[10005][10005];void dfs(int x,int y){ cont+=mapp[x][y]; mapp[x][y]=0; int nx,ny; for(int i=0;i<=3;i++){ nx=x+xx[i],ny=y+yy[i]; if(mapp[ ...