树状数组、询问离线排序我的想法是对询问离线，然后我们容易知道[l,r]的答案等于[1,r]的值减去[1,l-1]的值所以把每次询问的两个端点都拉出来，标记好是左端点还是右端点，将每个询问的[1,l-1]和[1,r]答案记录下来最后一次性输出差值即可。复杂度O( (n+m) * logn)貌似和大佬的离线有点不同 大佬的做法是顺便把a数组排序了，不过复杂度倒是一样的 #include<bits/stdc++.h> using namespace std; int c[1<<17]; int a[1<<17]; struct node { int id,l,x,...

无语。。原来这是个水题。。当时看榜过的人并不多题目就没去看 题意：给你一个n * m的矩阵，矩阵中a[i][j]=i * jq次询问，每次询问矩阵中第k小的元素是多大。 很容易想到二分答案，因为答案具有单调性。那么对于每一行计算出有多少个≤二分的答案mid的个数，计算一下总个数和k比较即可。对于每一行，求小于等于mid的数的个数为N达到了1e8，显然不允许直接算可以发现上述式子其实就是整除分块(之前的每日一题的数码的知识点)所以check答案可行性用整除分块来判断，复杂度sqrt(min(n,mid))总体复杂度 q * log * sqrt(n)顺便安利一下每日一题的数码，如果没有做过的话h...

01背包、排序很容易看出来这是一个01背包，但是因为价值跟所完成的时间有关(即跟选取顺序有关)，所以不能按照顺序直接背包，要先排序。考虑第i个和第j个两个菜，假设先完成第i个菜的价值更大，则有化简后得到按照上式排序后，01背包即可。注意答案可能为负，dp数组除dp[0]外应赋为无穷小 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[1<<20]; ll b[1<<20]; struct node{ ll b,a,c; }a[1<<20]; int m...

只过了ADFGJ其他待补 A 贪心考虑一下，如果数字一样，这人还是会排在前面的所有人里的最后一名，那么m肯定先给自己加一个，然后因为≥他的人不管加不加都在他前面，所以给数字≥他的都加上，如果m还有剩余，考虑从最小的加，尽量减少他后面的人谁提高到和他一样(因为他字典序最大)所以排序一下，对他前面的人进行加，还有剩余，就从最小的开始加。再次排序找他的名次即可。 #include <bits/stdc++.h> using namespace std; typedef long long ll; struct node { ll x; ll id; } a[200005]; int ma...

这是一个计数类的dpdp[i][j]表示前i个数字中，删除j个元素的方案数很容易得到转移方程意思就是前i个删除j个，要么从前i-1个中删除了j-1个，等于第i个也要删，要么从前i-1个删除了j个，等于第i个不删这样还没做完，下面考虑去除重复的个数。(其实这就是个容斥的思想，先尽管算，再把重复的去除就是了)考虑一下怎么会出现重复的情况。……1，4，7，8，5，1很容易发现，对于1，4，7，8，5，1这一段，删除1，4，7，8，5 和删除4，7，8，5，1 会造成重复计算。重复的方案数是多少？其实就是第一个1前面的序列随便选加上后面的1 4 7 8 5 1后再删除1 4 7 8 5 或者4 7 8...

dp[i]表示以i结尾的子序列的方案数 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; ll dp[105],a[105]; int main(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1; ll ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<i;j++){ if(j*log(a[i])>i*log(a...

A正常的bfs搜一下即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; char mp[105][105][105]; bool vis[105][105][105]; struct node{ int x,y,z; int num; }; int n; bool check(int x,int y,int z){ if(x>n || x<1 || y>n || y<1 || z>n || z<1 || vis[x][y][z]==1 ||mp[x][y][...

做法：二分答案+双指针判定二分答案比较明显，那么怎么去调整边界呢。考虑二分出一个答案mid对数组A进行双指针枚举，左指针固定不动，右指针向右移动如果当前左右指针之间的区间≥mid的个数≥k个,那么意味着左指针取l，右指针取[r,n]中任意一点所构成的区间的第k大都≥mid因为在[l,r]这一段≥mid的个数已经≥k个了，在往后的话只有数字对第k大的才有影响，小的都被扔到后面了 而第k大就一定≥mid每次满足条件后，左指针也右移，这样就计算出所有的子区间第k大≥mid的个数ans说白了就是利用双指针计算出所有满足区间第k大≥mid的区间个数。然后ans去跟m作比较，如果ans≥m，说明二分的答案...

A 最短路   待补   B组队   排序后，二分大于当前这个数的第一个位置，更新最大值即可   #include<bits/stdc++.h> using namespace std; typedef long long ll; #define me(a,x) memset(a,x,sizeof a) #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int&...

对于这一位置的糖糖能存活，当且仅当他编号后面的另一个组的糖糖的最大值≤它对于发功，发功的作用会对1~i产生影响，也就是提高前面的能力值，我们大可以直接处理出来发功次数用完后的能力值。为什么可以这样？因为如果前面的糖糖会被提前干掉，发功产生的影响其实是对前面的都进行增加的，是不影响前面会被打掉的人，只会影响前面没被打掉的是否会被该位置后面的干掉。那么，对发功处理一个后缀和，倒序遍历所有糖糖更新能力值，同时更新两个组的最大值，比较当前位置的能力与另一个组的最大值即可。 #include<bits/stdc++.h> using namespace std; typedef long l...

考虑二分答案。二分出来mid，那么对于绝对值≤mid的，我们不需要管他，因为他可以直接走到原点，在mid时间内一定可以到。那么对于剩下的呢？我们对于剩下的去找最大值max和最小值min，如果max - min <= 2 * mid,说明mid这个是满足答案的，那么就需要下降二分上界，至于一个门放在了原点处，另一个门在哪我们并不关注，只要满足max - min <= 2 * mid,那么第二个门一定在min到max之间，并且会尽可能地居中。其实不难发现，要满足这个式子，一定要满足除去绝对值≤mid后的剩下的a[i]要同(符)号，不然必有max - min > 2 * mid #...

考虑只有一种颜色，对于选取i个节点每边有f[n]= 种那么两边的话就有ans=f[n]*f[n].这样是有重复的，考虑容斥结果就是 但是这样复杂度需要n^2 这样就是on递推了 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e7 + 10; const int mod = 1e9 + 7; LL mul[maxn]; LL inv[maxn]; LL F[maxn]; void init() { mul[0] = 1; for (int i = 1; i &...

经典题。二分答案。二分木棍的值mid，遍历一次数组看得到的个数是不是≥所要求的k个，是的话，考虑提高二分下界，即l=mid否则说明mid过大，考虑下调二分上界，即r=mid #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[1<<21]; int main(){ int n,k;cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; int l=0,r=2e9; while(l+1<r){ int ...

考虑从n个位置任取两个，前面位置放1，后面位置放0.所以这是一个组合数n个位置固定了两个位置了，还剩下n-2个位置，每个位置可以放0或者1，是个幂级数所以答案就是进行的除法运算时候，因为模数是个质数，直接用费马小定理即可。当然了，注意特判n=1的情况，因为对于快速幂只能进行非负数，而幂级数的指数部分当n=1时候为-1 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; ll qpow(ll a, ll b){ ll ans=1; while(b){ if(b&a...