前言  位运算往往涉及到拆位思考，有时候每一位达到最优解汇合到一起就是全区最优解，同时位运算可以缩小量级，把一个很大的数处理成一个不超过64位的01串  题意  选择一个不超过m的数，做k次给定的操作  （opt包含OR，XOR，AND），结果最大可能是多少  思路  对每一位来说无非0，1两种情况，所以读入opt和t后可以直接拿00……0和11……1去进行上述操作，然后枚举每一位的最优解，如果填零是最优就填零，否则看填一是否是最优并检查填一会不会超过m，最终输出结果。  AC代码 #include<bits/stdc++.h> using namespace std; int m...

题集  活动安排 国王的游戏 保护那些花  题意  基本都隐含着让最大贡献尽可能小  思路  贪心来思考，在局部让他对总贡献小，那么在全局就贡献小，这类问题，往往一个单位的贡献情况只取决于自身和前面一位，也就是说，交换自身和前一位对除了这俩以外的部分没有影响，那么便可以进行讨论 以保护那些花为例：我们不妨假设两只牛按的排列方式是最优的，也就是毁坏的花比小。 那么，毁坏的花为：,毁坏的花为： 两式相消可得出：  AC代码 #include <bits/stdc++.h> using namespace std; int cmp(pair<int,int>a,pair&lt...

题意  生成m位所有位和为s的最大数和最小数  思路  贪心：最大数为前面尽可能放9，最后剩下的不够9的放最后一位。最小数为后面尽可能放9，剩下的放前面，但如果有前导0，就给第一位加1，第一个非零位-1。这时发现，最小数其实就是最大数逆序然后改变前导0的结果 注意：三种特殊情况，第一种全放9也凑不够S，第二种s=0且m>1，第三种s=0且m=0，前两种输出-1，最后一种输出0 0  AC代码 #include<bits/stdc++.h> using namespace std; int main(){ int t; scanf("%d",&t); while(t--...

题意  在字符串S中找一个最短字串，使其包含26个字母  思路  暴力枚举会T 双指针：从头开始扫，更新右界直到扫全，然后更新左界直到缺字母，重复上述过程遍历整个串  AC代码 #include<bits/stdc++.h> using namespace std; int vis[26]; int main(){ string s; cin>>s; int slen=s.size(); int rst=1e7,cnt=0; if(slen<27)cout<<-1<<endl; else{ for(int l=0,r=0;l<slen...

题意  给定1~n的排列和中位数b，构造子列使得中位数是b  思路  比b大的记为1，小的记为-1，对b左右做后缀和和前缀和，统计每种答案个数，将前后和中互为相反数的相乘  AC代码 #include<bits/stdc++.h> using namespace std; #define base 100000 int a[101010]; int l[101010],r[101010],ctl[303030],ctr[303030];//记录左半边和右半边出现频率，反着记方便相乘 int main(){ int n,b,pos,ans=0; scanf("%d%d",&n...

前言  前缀和和差分是一对对称的操作，对前缀和数组差分可以得到原数组，对差分数组前缀和也可以得到原数组  题意  一条长为L线段等距离分布L+1个点，每次去掉一段中的所有点，去除m次后还剩多少点  思路   第一种思路：差分查询次数，统计当前点被查询的次数和上一个点被查询的次数的差，再前缀和，可求出每一个点被查询的次数，如果次数为0，说明没被查询过。   第二种思路：合并区间，把所有区间按左界排序，遍历，若当前区间左界小于合并区间右界，加入合并，更新合并区间右界为max(当前区间右界，合并区间右界)，托当前区间左界大于合并区间左界，答案+=合并区间长度，然后开始新的合并区间。 注意：这种思路并...

题意  计数两日期之间的回文日期  思路  枚举所有年份，构造月份判断是否合法 枚举所有月份和日期，构造年月日看是否在区间内 但是，构造年份检查月份还要分大小月以及平年闰年，相对麻烦，故构造年月日是更为便捷的解法  AC代码 #include<bits/stdc++.h> using namespace std; int main(){ int st,ed,ans=0; int up[13]={0,31,29,31,30,31,30,31,31,30,31,30,31}; cin>>st>>ed; for(int i=1;i<=12;i++){ for...

题意  给定一个由*和#构成的正方形矩阵，求其中以#为顶点的最大正方形，输出四个顶点坐标  思路  两个点确定一个正方形，三个点确定一个长方形，枚举所有的两个#，check当前两个#构造出的另外两个顶点是否为#，通过边长比较正方形大小 注意：计算几何中尽可能避免硬解方程组，多考虑向量和三角函数，本题使用三角推导另两个点最为便捷 附图：   AC代码 #include<bits/stdc++.h> using namespace std; char mp[120][120]; long long l=0; vector<int>ans(8); int n; void ch...

题意  给定多项式系数，输出多项式  思路  简单的模拟即可，注意如何划分模拟过程，先输出符号，再输出常数，最后输出指数。 不要贪心，不要想着一边读入一边输出，或者一次性同时处理符号，常数和指数  AC代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; scanf("%d",&n); int a[110]={0}; for(int i=n;i>=0;i--){ scanf("%d",&a[i]); } for(int i=n;i>=0;i--){ //符号 if(a[i]=...