题意  长为x的跑道上有A，B两个打卡点，必须先在A打卡再在B打卡 请问完成两次打卡后跑步距离超过k的概率  思路  用图形算概率，横轴为A纵轴为B，占比就是概率 如果k<x，那么只要B<=A||(B>A&&B>k)就可以 如果k>x，那么B>=k-x&&B<=A 如果k>2x，寄 如果k=x，当且仅当B<=A  代码 #include<bits/stdc++.h> using namespace std; void solve(){ int k,x; scanf("%d%d",&k,&a...

题意  n堆石子，可以做两种操作  对一个奇数堆石子拆分成两堆 合并两个偶数堆石子   无法操作的人判负，给定n和每堆石子个数，判断胜负  思路  如果没有偶数且奇数不全是1，A分解，B分解，A合并，B分解——A必胜 如果有偶数，所有奇数没有贡献，能合并cnt_even-1次  代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; int cnt=0; int flg=0; for(int i=0;i<n;i++){ int tmp; cin >> tm...

题意  对于一个数n，两个人每次可以把它拆分成两个因数，没得拆的人输，给定n，判断胜负情况  思路  对任何一个数，最终一定会被拆成它的质因数分解形式，然后无法继续拆解 而中途的拆法并不影响结果 每次拆会使得总数+1，总共能拆因子个数-1次 如果质因数分解有奇数个因子，先手必败 反之后手必败  代码 #include<bits/stdc++.h> using namespace std; int prime[100000]; int vis[100000]; int cnt=0; void sieve(int lim){ for(int i=2;i<=lim;i++){ if...

题意  n*m棋盘，交替染色，不能染的输  思路  奇数先手赢，偶数后手赢  #include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin >> n >> m; if(n*m%2){ cout << "akai" << endl; }else{ cout << "yukari" << endl; } return 0; }

题意  n*n棋盘，白皇后在(1,1)黑皇后在(1,n)，其余位置是中立棋 皇后可以水平，垂直，斜向吃子，无法吃子的一方输 白先黑后 如果白方能赢，给出第一步往哪走  思路  如果奇数，无论白棋怎么走，黑棋都对称的走，最后一定会两方之间只剩下1列中立棋，此时该白方走，然后黑方可以直接吃 如果偶数，白方向右走一步就变成黑方先手的奇数情况，白方必胜  #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n ; if(n%2){ cout << "black" <&lt...

300多AK，输TT 背景：不动点  一个序列中的元素，当且仅当  认为是一个不动点 一个矩阵中的元素，当且仅当  认为是一个不动点    A 题意  长为4的序列，输出其中的不动点个数  思路  签到，直接模拟  代码 int main(){ int cnt=0; for(int i=1;i<=4;i++){ int tmp; cin >> tmp; if(tmp==i)cnt++; } cout << cnt ; return 0; }  B 题意  构造一个长为n有k个不动点的排列  思路  观察发现k=n-1就寄了 正解：先把前k个按顺序放，后面的错一位放...

题意  对于一个序列，如果某个数字出现两次及以上就可以全部拿取 否则就不能拿取，给出长为n的序列，有m次查询 每次查询会给出一个区间，回答最多拿取多少种数字  思路  附一个别的大佬的blog，推导很详细 对于一个数字，可不可以拿取，取决于到当前位置该数字有没有出现超过两次，也就是一个数出现意味着左端点落在上一次和上上次之间可得的数量增加1 离线查询，按照查询右端点排序 维护一个树，记录处理到当前位置，每个点可得的最大值 这个树设计两个操作，对于某个点值的查询，对于某个区间的整体加一 可以维护这个树的差分数组，单点的查询变为前缀和，区间的增加变为两个单点的修改，这样就不用开线段树可以用树状数组...

题意  对于长为n的全0序列，完成m次如下两种操作  输入x y，将所有1-base下标为x的倍数的元素加上y 输入x y，输出x到y区间和    思路  对于操作1，如果暴力做，每次的复杂度会是  分析x  如果x很大，那么x的倍数就不会很多，暴力的复杂度是可以接受的 如果x很小，通过数学可以快速得到需要增加的元素的个数，开一个桶，记录每个x被加的y的总和，最后统一计算贡献(这个方法在x大的时候设计开不下数组的问题)   x的分界定多大  采用上面的方法后，修改的复杂度变为  ，查询的复杂度变为  ，由均值不等式得分界定在  即可    代码 #include<bits/stdc++....

用途  求矩形面积并，面积交，周长并  思路  用一条假想的线从图形的上方扫到下方，分析扫描线被图形截获的线段就能得到所求结果，过程可以用线段树进行加速  面积并  从上往下扫，每次扫到和扫描线平行的线就更新线段树 线段树一共记录n-1个区间，记录的内容是每个区间被覆盖的次数 此时被覆盖的区间数就是当前小矩形的一条边长，而另一条边长则为当前边和下一条边之间的距离 有时候坐标很大线段很少，使用离散化  #include<bits/stdc++.h> using namespace std; const int N=2e5+10; struct L{ long long x,y1,y2...

题意  给定一个长为n的01序列，有五种操作，总共操作m次(n,m<=1e5) 0. 把[a,b]区间内的所有数全变成0  把[a,b]区间内的所有数全变成1 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 询问[a,b]区间内总共有多少个1 询问[a,b]区间内最多有多少个连续的1    思路  线段树，线段树本身维护区间中01个数和最长连续01个数 前三种操作用lazy标记维护 除此之外，还由于需要区间合并，将子区间合并的时候需要左区间的后继长度和右区间的前驱长度 所以还得维护每个区间的前驱和后继  代码 #include<bits/stdc++...

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct L{ double x,y1,y2; bool flg; }line[N]; int cnt; double seg[N]; double tree[N*4]; int lazy[N*4]; unordered_map<double,int> mp; void build(int p,int l,int r){ if(l==r){ tree[p]=0; lazy[p]=0; return ; } int mid=(l+r)&gt...

题意  给定长为n的序列，每个位置有权值 两种操作  删除第k个，右边的都往左挪一位 查询第i个到第j个的最大和最小值    思路  结构体维护最大最小和区间内的个数 删除的时候区间个数-1 查询的时候按照区间个数查询 注意查询的时候，直接弹出当且仅当，查询的区间左界比1小右界比个数大 不开读写优化会TLE  代码 #pragma GCC optimize(3) #include<bits/stdc++.h> #define endl '\n' using namespace std; struct ty{ int mx,mn,num; }tree[4010101]; int a[...

A 题意  给出一个n，判断翻转后有没有前导0  思路  直接 mod 10就可以了  代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n ; cout << (n%10?"YES":"NO") << endl; return 0; }  B 题意  判断一个01环有没有有没有可能单调不减  思路  模拟就行  代码 #include<bits/stdc++.h> using namespace std; int a[202020]; ...

题意  对于一个长为n的序列a，你需要完成q次询问，每次询问有四种情况  输出(l,r)区间和 输出(l,r)区间平方和 (l,r)所有元素+=x (l,r)所有元素*=x   其中n为1e4量级，m为2e5量级  思路  线段树变种 对于区间和，维护第一个线段树 对于区间平方和，维护第二个线段树 对于所有元素加上定值，使用第1个lazy标记 对于所有元素乘上定值，使用第2个lazy标记 对于加法运算和乘法运算混合出出现，永远将lazy记录的式子转化为kx+b，即每次乘上一个因子s时，转化为ksx+sb 对于lazy标记的pushdown  乘法lazy初值是1，加法初值是0 先更新lazy ...