题意  给定长为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 ...

题意  m块石头，n只青蛙，第i青蛙步长  求解所有被踩过的石头的编号(0-base)和  思路  观察发现，对于一只青蛙，他能踩到的石头是  暴力会炸 考虑从m入手， 的结果一定是m的因子  枚举m的因子，标记是gcd倍数的因子，这些因子会产生贡献 用一个cnt记录每个因子还需要计算贡献的次数 从小到大计算每一个cnt不为0的因子 计算完一个因子的贡献后，改因子所有的倍数因子也被计算了，所以要减去次数 对于计算贡献，每个因子的贡献是 （等差数列求和，由于0-base开始，共有m/v[i]-1项，首项v[i]，公差v[i]，通项公式），再乘上自己的cnt，正值代表还没算，负值代表算多了（eg:...

题意  长为n的排列，第i为不能放i，求解方案数  思路  典型的错排问题  c++得写高精度  代码 n=int(input()) f=[0,0,1] for i in range(3,n+1): f.append((i-1)*(f[i-1]+f[i-2])) print(f[n])

题意  把n个1，m个0组成字符串，要求任意前k个字符中，1的个数不少于0的个数 求解满足要求的字符串有多少个  思路  总保证前缀和大于0 卡特兰数板子题 求解f(n) 组合数求解要开逆元，x%p的逆元和x的逆元相等  代码 #include<bits/stdc++.h> using namespace std; #define int long long const int p=20100403; int f[2010101]; void cal(int x){ f[1]=1; for(int i=2;i<=x;i++){ f[i]=i*f[i-1]%p; } } int...

题意  长度为m的序列，每个位置可选1~n，有k条限制，限制位置a不能选择b 求解所有序列内部求积的和  思路  加法原理和乘法原理 如果没有限制，每个位置可以选择1~n，m个位置 每个位置的贡献为(n*(n+1)/2)总价值为(n*(n+1)/2)^m 然后对于没限制的部分就按照公式算 有限制的部分，就是在贡献中减去限制的值  代码 #include<bits/stdc++.h> using namespace std; const int p=1e9+7; long long qpow(long long a,long long b){ a%=p; long long res=...

题意  给出n，求1~n之中，有多少数不是2，5，11，13的倍数  思路  容斥原理，用n减去即可  代码 #include<bits/stdc++.h> using namespace std; long long n; void solve(){ cout << n-(n/2+n/5+n/11+n/13 -n/(2*5)-n/(2*11)-n/(2*13)-n/(5*11)-n/(5*13)-n/(11*13) +n/(2*5*11)+n/(2*5*13)+n/(2*11*13)+n/(5*11*13) -n/(2*5*11*13)) <<endl; ...

赛时FB，补GI  F 题意  有n个宝藏，每个宝藏有自己的val，你能获得前k个 同时，你还可以进行一些交换，每次交换消耗价值c 求解你可以获得的最大价值  思路  考虑将所有宝藏都换到最前面，取最高的k个，然后再加上把k个宝藏从第一个放到前k个的价值  代码 #include <bits/stdc++.h> using namespace std; #define int long long signed main() { cin.tie(0)->sync_with_stdio(0); priority_queue<int> pq; int n, k, c; ...

赛时ADFJ，补BE  F 题意  给定n，每次先给n减去a，再减去b，你可以提前减少一次n，但不能全减，请问最少减去多少使得n是在减去b时被减光 如果无解输出"Sayonara"  思路  n<=a无解 考虑最后一轮所剩  ,如果  ，减去r，否则减去0就行  代码 #include<bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--){ int n,a,b; cin >> n >> a >> b; if(n<=a) cou...

A题和C题犯蠢，A看半天没看出来，在那里写模拟，C以为暴力会爆炸，结果不会，G是个神奇乱搞  A 题意  当一个01串任意的相邻两个字符不一样时称为好串 给定n输出长度为n的好串个数  思路  一共只有两种，别想复杂了，输出2就行  代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; cout << 2 << endl; return 0; }  B 题意  一个01串中有三个1，判断中间的1和两边的1是否相等  思路  扫一遍模拟即可  代码 ...

赛时ABFIL，补D  B 题意  长度为n的数组，操作一次会删掉其中的两个，并添加他们的异或和，请问一次操作后会不会减小  思路  就是判断任意两个的异或的最高位会不会小于等于这两个数中大的的最高位 如果两个数异或变得更小就一定不行，最多有63位，所以如果超过63个数一定会有两个数最高位相同，异或变小，不行 小于63个数的时候暴力枚举就行 另一种思路是，先排序，从小到大判断，每次将两个数异或后的最高位加入p，如果某一次加入的数和p异或消除了p的某一位，就说明会变小  代码 #include<bits/stdc++.h> using ll=long long; using name...

#欧拉函数 题意  给定n，输出n*n方阵中站在(1,1)可以看到得点  思路  观察发现，能被看到得点一定x，y坐标互质 由于对称性，只求下半个三角就行，也就是对于固定x，求和x互质的数的个数，也就是欧拉函数的板子 边求边加，最后加上左下角三个点就行  代码 #include<bits/stdc++.h> using namespace std; using ll=long long; int v[40404],prime[40404],pi[40404]; int cnt=0; ll ans=0; void sieve(int x){ for(int i=2;i<x;i+...

#积性函数 #线性筛 #快速幂 题意  给定n，求解 n<=1.3e7  思路   满足积性函数 需要找到n以下每个数的n次方，可以用筛法，质数的用快速幂计算，合数的用质数递推 因为空间限制，无法记录每个数的最小质因子，但其实可以直接暴力的乘上每一个质因子，同时开一个bool的vis数组保证每一个数只计算一遍  代码 #include<iostream> using namespace std; using ll=long long ; const int N=13e6+10; const int p=1e9+7; ll qpow(ll a,ll b){ a%=p; ll r...