题目描述：给定由1-n组成的长度为n的a[]和k，问长度为k+1的子序列中有多少个单调递增的？n<=1e5,k<=10 终于想到了！开k+1个线段树/树状数组记f[i][j][o]为前i个数，以j结尾，长度为o的子序列有多少个。i维可以省略，f[j][o]=f[Σ1-(j-1)][o-1],所以用树状数组维护f数组（写成了c） 所求答案即为f[1~n][k+1].复杂度O(knlogn) ```#include<bits stdc++.h>#define ll long longusing namespace std;ll a[100010];ll c[100010][...

题目描述：一家餐厅收到了n份订单，每份订单有开始和结束时间，餐厅可以选择接或不接，接受的订单时间必须互不重合，即任意一刻都不能被两个订单占用。问餐厅最多能接受几份订单。 啊这，乍看是经典DP，但是不能直接写，需要多思考。以订单结束顺序排序。f[i]表示处理订单数为i时，所用的最小时间，发现f[i]有单调性。每次对一个订单，用开始时间二分查找f[k]<lef<=f[k+1],更新f[k+1]=min(f[k+1],rig)最后f[]数组最后不为INF的对应下标就是答案。 #include<bits/stdc++.h> //#define ll long long usin...

题意描述：给定区间[a,b]，问有多少个整数可以被k整除。 一个小思路是分别计算a到0、b到0有多少个整数被k整除，然后再分类讨论求解。尤其注意0和端点的判断。 #include<bits/stdc++.h> using namespace std; int main() { long long k,a,b,ans=0; cin>>k>>a>>b; if(a<0&&b<0) { a=-a,b=-b; swap(a,b); ans=b/k-(...

题意：给定长度n的数组a[]，问所有的连续子数组中有多少对相同的数。这不就是整个a[]有多少对相同的数的变种题吗是不是叫一维数点来着？~~ 一对相同的数ai,aj，它们一共在i*(n-j+1)个子数组内出现过。根据这个直接算贡献。用mp[a[i]]维护a[i]在1-(i-1)的出现过的坐标和。这样每次找到a[i]，就方便O(log)查询，O(1)计算a[i]与之前所有与a[i]相同的数组成的对的贡献:(本质是提取公因数) ans+=mp[a[i]]*n-i+1,mp[a[i]]+=i. 复杂度O(Σ nlogn) #include<bits/stdc++.h> #define ...

题意：ALICE先手，每次能对一个字符串做两种操作:选择任意i(1≤i≤n)，其中s[i]= '0'，将s[i]改为'1'。支付1美元。把整个字符串反过来，付0元。此操作只允许在字符串当前不是回文且上次操作没有反转的情况下进行。也就是说，如果Alice翻转了串，那么Bob在下一个动作中就不能翻转，反之亦然。二人足够聪明，问给定一个 回文串 ，谁花的钱数最少。平局输出DRAW. 考虑1.长度奇数且中间为'0'的串和2.其他类型的串。 对于2.统计左半边0的个数.(1)个数为1，BOB翻转即可让自己必胜，且BOB比ALICE少花2美元。(2)个数大于1，每次ALICE怎么填，BOB就对着填，能转化...

题目描述：给定n,求最大的k使得 n & (n−1) & (n−2) & (n−3) & ... (k) = 0 大胆猜测当且仅当n的最高位被0与掉了的时候这个式子会等于0，所以k满足2^m-1<n<=2^(m+1)-1，找到这个k=2^m-1输出即可。 #include<bits/stdc++.h> #define ll long long using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ...

题目描述：有一块长度为n的一维地，每格地可能为空('.')也可能有一只羊('*')每次可以令一只羊左移或右移一格，当且仅当目的地是空。问最少几步能让这些羊相邻。 我的做法：记所有羊的坐标为ai,维护两个值f(x)=Σ|x-ai|，sum1[x]为x及之前的羊数，sum2[x]为x及之后的羊数，定义g(t)=t*(t-1)/2;维护f(x)当x从0增至n-1时能做到O(1)计算；g(t)的目的是修正由于“羊不能重叠”而多算进去的步数。发现记x∈[0,n-1]为目标点，那么步数ans=f(x)-g(sum1[x])-g(sum2[x]),取最小值即为答案。这都什么垃圾想法复杂度O(Σ n) #in...

题意描述：给定长度n的数组a[],问有多少对(i,j)满足1<=i<j<=n使得aj-ai=j-i. 对式子整理得到aj-j=ai-i. 这……根本不带掩饰的？这太经典了 给b[]=a[i]-i，问有多少对相同的数？这都见过吧？ 用map维护1到i-1中，b[i]出现了mp[b[i]]次，ans+=mp[b[i]],++mp[b[i]]即可。别忘了以各种乱搞的方式清空mp。 上述想法复杂度o(Σ nlogn) 但是代码构造的是b[i]=a[i]-i+n，利用了a[i]的范围，省下了离散化(map)操作，复杂度O(Σ n) #include<bits/stdc++....

题意描述：给定n，用1-n^2构造一个n×n矩阵，要求上下左右相邻的数的差值大于1，无解输出-1，有解就给出任意一组解。 图省事特判n=1,n=2() n>=3时，按照对角线方向依次填数，先填对角线再轮流在上下侧填数，得到的矩阵符合要求，输出即可。 大胆猜测小心使用不用证明 编辑：网上有一种想法是隔一个对角线填数，填满了再回来填隔掉的对角线。链接：https://blog.csdn.net/JophieQu/article/details/116448296 #include<bits stdc++.h> #define ll long long using namespac...

题目描述：给定n，求1-n中有几个数字满足各位数上的数相同。 统计位数len和最高位h，构造位数和n相同的数hh，hh各位数上都是h，比较n和hh，n小了就--h;ans=h+9*(len-1). #include<bits/stdc++.h> #define ll long long using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int t,len,n,h,cnt,k,flag,hh; cin>>t; ...

题目描述：有26种任务，用大写英文字母表示，Polycarp每天完成一个任务，一旦切换任务，他不能再返回这个任务，否则会被老师怀疑，现在给定任务序列，问是否会被老师怀疑。 这太水了每次遇到切换点就判断一下是否出现即可，是否出现用vis[]数组搞一下标记就行。 #include<bits/stdc++.h> #define ll long long using namespace std; int vis[31]; string s; int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ...

题目描述：有n个人，给出所属学校和实力值，k个人才能组成一队，每个学校都按照实力值和尽可能大的方法派出队伍，问k从1~n，分别求所有学校所有队伍的实力值和。 把人按照学校分开，实力值从小到大排序做前缀和，对某个学校有m个人，派出的实力值和sum[m]-sum[m%k]。累加进ans[k]即可。复杂度O(Σ nlogn) #include<bits/stdc++.h> #define ll long long using namespace std; struct orz { ll u; ll v; }a[200010]; ll n; ll sum[200010],a...

题意描述：给你由1-n组成的数组a[],每次操作可以任意交换任意次长度小于n的一段区间内的数，问几次操作能把a[]好排序。 贪心地发现操作次数主要和1与n的位置有关。总结如下0：如果已经排好序1：如果仅1或n不在原位置3：如果1在[n]且n在a[1]2：其他所有情况 ```#include<bits stdc++.h>#define ll long longusing namespace std;int a[10100];int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int t; ...

题意描述：每次能向锅里添加1份魔法精华或者1份水，问最少几次操作能让锅里精华比例为k% 朴素的想，往里放入k份精华和100-k份水。然后发现可以约分，约分完了加起来，最终答案为100/gcd(k,100-k). ```#include<bits stdc++.h>#define ll long longusing namespace std;int gcd(int a,int b) {return b?gcd(b,a%b):a;}int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int...