A~E题 A题 先找到>=l的最小x的倍数再判断是否<=r 或者先找到<=r的最大x的倍数再判断是否>=l都可以 void solved() { int l,r,x; cin>>l>>r>>x; int mi=(l+x-1)/x*x;//>=l的最小x的倍数 cout<<(mi<=r?mi:-1); // int ma=r/x*x;//<=r的最大x的倍数 // cout<<(ma>=l?ma:-1); }  B题 满足条件的最短长度区间[x,n*x]往左右两边扩 左边右边均最多扩x-1...

CDE题 C题：构造 #include<bits/stdc++.h> using namespace std; void put0(int x) { while(x>0)cout<<0,x--; } void put1(int x) { while(x>0)cout<<1,x--; } void put01(int x) { while(x>0)cout<<0<<1,x--; } void solved() { int a,b,k;cin>>a>>b>>k; if(k==0) { ...

B题 题意：现已给出长度为n的数组a，表示n张已确定值的牌（1<=ai<=m）。还有k张没有确定值的鬼牌，每张可为[1,m]内任意一个值。问从这n+k张牌中选出x张数值连续的牌，求x能达到的最大值。 ——————————————————————————————————— 思路：双指针维护窗口，窗口内的数值是可在使用不超过k张鬼牌的情况下连续的数。 用队列来实现双指针不容易出现边界错误且代码更短逻辑更清晰 时间复杂度：排序O(nlogn)+双指针O(n) void solved() { int n,m,k; cin>>n>>m>>k; vector...

E题 容易想到，只考虑前i个数的序列乘积的个位只有10种状态：个位为0~9 定义f[i][j]:前i个数中，序列乘积的个位为j的方案数 贡献：前i个数中，以a[i]结尾的序列且乘积个位为6能提供的贡献 这里与题意序列贡献有所不同，因为我们根据f[i][j]定义已知序列在前面的方案总数，我们只考虑当前序列作为序列的前缀还会在后面还会出现多少次，出现多少次就贡献了多少答案 结论：以a[i]结尾的序列作为序列的前缀还能在后面出现的次数为2^(n-i)（后面每个数有可选可不选两种抉择） 用样例一解释 3 4 4 6 序列[4,4]贡献答案 2（446 和 44_）（f[1][4]×a[2]×2^(3-...

D题 暴力bfs遍历找最短路 唯一的变化是，碰到墙后要for循环反向走到对面的墙前即可，遇到终点要提前退出 #include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> PII; int n,g[1005][1005],step[1005][1005]; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; int bfs() { queue<pair<int,int>> q; q.pu...

I题 #include<bits/stdc++.h> #define int long long using namespace std; int n,m; vector<int> h[1000005];//邻接表 bool check(int l,int r)//检查r是否可以加入[l,r-1]的友好区间区间组成新的友好区间 { auto ptr1=lower_bound(h[r].begin(),h[r].end(),l); auto ptr2=lower_bound(h[r].begin(),h[r].end(),r-1); if(ptr1==h[r].end()...

I题  首先容易知道一共只有4×n×m种状态，定义in[i][j][k]：以k方向射入(i,j)后被不同镜子反射的次数  （ 将上，下，左，右 映射为 0，1，2，3 ） （ 询问只可能是这些状态，所以先处理出所有的in[i][j][k]即可实现O(1)查询 ）  离线处理光链   光链的一定从迷宫外射入且一定会射出迷宫，处理迷宫四周射入的光链即可 搜索每条光链，然后存下路径及其信息 逆向遍历路径，遇到的镜子是第一次反射就cnt加1，遍历过程中给每个状态点赋为cnt（逆向遍历很好的解决了不同种类镜子反射的问题）（用哈希判断镜子是否是第一次反射）   处理光环   遍历所有4×n×m的状态点，还...

E题 看了官方讲解视频的思路后才写出来 1.设f[l,r]==(a l ​ & a l+1 ​ &...& a r ​ )⊕(a l ​ ∣ a l+1 ​ ∣...∣ a r ​) 2.根据f[l,r]表达式，仅观察[l,r]中二进制数第k位的情况下，同时出现1和0才能使f[l,r]的第k位是1 3.那么符合题意的区间f[l,r]的二进制数最高位1的位数必须在[k1,k2-1]中 4.用双指针或者二分预处理出数组l[k][i]:在第k位下，从第i个数到第l[k][i]个数第一次同时出现0和1，即第一次出现f[l,r]在第k位下等于1 #include<bits/...

H,E题 H题方法一：贪心求上升子序列的最少个数 #include<bits/stdc++.h> using namespace std; int n,m,cnt,a[5005],f[5005]; int main() { cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; vector<int> b; for(int i=1;i<=n;i++)//贪心求上升子序列的最少个数 { int idx=0,gap=0x3f3f3f3f; for(int j=0;j<b.size();j++...