哎呀，补题解工作量好大…
查了下发现csdn不支持排列文章顺序，只能从十多天开始补 otz
今天摸鱼没去实验室 结果寝室玩了一天的物语…
不过雷暴雨天没出门不亏 校门口都淹了XD看任天堂独立游戏直面会去
太拉了这也 就loop hero和风来之国想买
7月30日题记
题目列表
1.CF 1554B
2.CF 1554C
3.CF_1206C
4.CF_1200C
5.CF_1200B
6.CF_841B
7.CF_1202A
8.CF_1234C
这几篇题解都是我从自己的CSDN里搬来的，不然显得我没打过ACM www
1.CF1554B
题目大意
给一个长度为n的数组和一个正整数k，找到满足( i * j−k * ( ai | aj ) )最大的一组下标(i,j)
解题思路
3e5的数据，比赛的时候看了看只想到暴力没思路，直接睡觉去了，后来看了题解恍然大悟
题解的意思 :
$ ∵a_i <= n，k<=min(n,100) $
$∴a_i |a_j <=2 * n $
$∵k<=100$
∴对比i * j的最大值n * (n-1) 逊色很多。
∴最大值最有可能在最后两位上取到，
让我们来看看最后两位的最小值
让或的值最大0，k拉满
最小值: n * (n-1) - 200 * n
那我们来看看中间取到的最大值
要让或的值变成了0
最大值: i * n
$ ∴n^2 - 201 * n < i * n $
$ ∴n - 201 < i $
看到这里就可以暴力了:O
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int maxn=1e5+10;
long long d[maxn];
long long f(long long x,long long y){
return x*y-k*(d[x]|d[y]);
}
int main(){
int t;
long long i,j;
scanf("%d",&t);
long long maxx;
while(t--){
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++){
scanf("%lld",&d[i]);
}
maxx=f(n-1,n);
for(i=max(1,n-2*k+1);i<=n;i++){
for(j=i+1;j<=n;j++){
maxx=max(maxx,f(i,j));
}
}
printf("%lld\n",maxx);
}
return 0;
}
2.CF1554C
题目大意
给两个数n和m，合成数组 $[n\bigoplus0,n\bigoplus1,n\bigoplus2,…,n\bigoplus m]$输出数组中没出现过的最小非负整数。
解题思路
正着思考很难，能想到的只有暴力枚举，可以反向思考：
$a_i=n\bigoplus i (i<=m)$
$n\bigoplus a_i=i$
$要求最小的非负整数不属于[a_i]$
$也就是要求最小的非负整数k$
$使得n\bigoplus k>m$
$也就是n\bigoplus k>=m+1$
这样就把暴力的思路转化成二进制运算的思路
AC代码
t=int(input())
ln=-1
lm=-1
for alsfkjsdlkjdsg in range(t):
n,m=[int(i) for i in input().split()]
if(n==ln and m==lm):
print(ans)
else:
if(n>m):
print(0)
else:
mm=bin(m+1)[2:]
nn=bin(n)[2:].rjust(len(mm),'0')
ans=''
pos=0
while(True):
if pos==len(mm):
break
if(mm[pos]>nn[pos]):
ans+='1'
elif(mm[pos]==nn[pos]):
ans+='0'
else:
break
pos+=1
ans=ans.ljust(len(mm),'0')
exec("ans=0b{}".format(ans))
print(ans)
lm=m
ln=n
3.CF1206C
题目大意
构造题，给一个数字，判断是否能用(1-2n)构造一个环满足从环上任取两个长度为n的区间的差相差小于等于1 并给出构造
解题思路
看到这道题的第一反应是一道要求连续区间相等的题，那道题相等的本质就是产生循环。而这道题是要求小于等于1，也就是说区间的端点和另一边外面的一个元素要相差1才能满足条件，如图
也就是说对于i来说它对面的数就是和它相差1的数字，然后为了满足全局条件，要用类似蛇形的方式排列
然后我们来考虑什么时候不能构造，如下图，当n是偶数的时候它是无法循环起来的，而奇数的时候是可以连起来的，n是奇数的时候相邻次移动的差会在+1和-1之间反复，而n是偶数的时候这种平衡会被打破，至于原因我也不是很清楚7O7
AC代码
#include<bits/stdc++.h>
using namespace std;
vector<int>xs;
int main(){
int n;
scanf("%d",&n);
int i,j,k;
if(n%2==0)
printf("NO\n");
else{
printf("YES\n");
int tmp=1,coun=0;
if(n==1)
printf("1 2");
else{
while(tmp<=2*n){
printf("%d ",tmp);
if(tmp+1<=2*n)
xs.push_back(tmp+1);
if(tmp+2<=2*n)
xs.push_back(tmp+2);
if(tmp+3<=2*n)
printf("%d ",tmp+3);
tmp+=4;
}
for(i=0;i<n;i++){
printf("%d ",xs[i]);
}
}
}
return 0;
}
4.CF1200C
原题链接
#### 题目大意
有一个由两圈有隔板圆环组成的房间，给出每圈的隔板数，问能否从一个隔间前往另一个隔间
#### 解题思路
一看就知道和什么公因数 公倍数这种关系有关系。按这个思路多画几个图不难发现他们的最大公因数就是最终整个房间隔开的区域数，然后我们只需要求出两个输入点所在的区域是否相同就行了，最后写代码的时候可能会有点绕，但问题不大，多调一调就可以出来了。
#### AC代码
cpp #include<bits/stdc++.h> using namespace std; long long n,m; long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b); } int main(){ int q; long long s1,s2,s3,s4; long long obj,tmpa,tmpb; scanf("%lld %lld %d",&n,&m,&q); obj=gcd(n,m); while(q--){ scanf("%lld%lld%lld%lld",&s1,&s2,&s3,&s4); tmpa=s1==1?(s2-1)/(n/obj):(s2-1)/(m/obj); tmpb=s3==1?(s4-1)/(n/obj):(s4-1)/(m/obj); if(tmpa==tmpb) printf("YES\n"); else printf("NO\n"); } return 0; }
5.CF1200B
原题链接
#### 题目大意
爬楼梯，玩家从起点开始行动，在每个状态点上可以从背包里拿方块网上叠，也可以把下面的方块放进口袋里，进入下一个状态点的条件是和当前状态点的高度差小于等于k值，判断能否到达终点。
#### 解题思路
一看就是贪心，既然没有步数限制，能到达终点就算成功，那么我们的方块越多越好，所以每次走到下一状态都要回收方块，如果必须花方块也没办法。最后就是贪心的细节要做好，我先wa了一次是没有考虑到下一阶段的高度减去高度差如果小于0就没办法回收最大方块数。wa了第二次是只判断到最后一个点的背包方块数是否大于等于0，但中间如果方块不够也是没法进行的，所以还需要在游戏中途进行判断。
#### AC代码
cpp #include<bits/stdc++.h> using namespace std; int d[105]; int main(){ int t; scanf("%d",&t); int n,m,k; int su; int i,j; while(t--){ su=0; scanf("%d%d%d",&n,&m,&k); for(i=0;i<n;i++){ scanf("%d",&d[i]); } for(i=0;i<n-1;i++){ su+=max(0,d[i+1]-k)-d[i]; if(su>m) break; } if(su<=m) printf("YES\n"); else printf("NO\n"); } return 0; }
6.CF841B
原题链接
#### 题目大意
给一个数组，第一个玩家从数组里删除一个和为奇数的连续子区间，第二个玩家删除一个和为偶数的连续子区间，最后不能删除的一方输掉游戏。
#### 解题思路
一看以为是题博弈论，实际上是套着皮的奇偶贪心，如果一开始总和是奇数，直接全部删掉，先手获胜；如果一开始总和是偶数，偶数 - 奇数 = 奇数，然后因为 奇数 - 偶数 = 奇数 所以只要数组里有一个奇数先手就可以获胜。
#### AC代码
cpp #include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int d[maxn]; int main(){ int n; scanf("%d",&n); int i,j,k; long long su=0; int flag=0; for(i=0;i<n;i++){ scanf("%d",&d[i]); su+=d[i]; if(d[i]%2) flag=1; } if(su%2) printf("First\n"); else{ if(flag) printf("First\n"); else printf("Second\n"); } return 0; }
7.CF1202A
[原题链接]https://codeforces.com/problemset/problem/1202/A()
#### 题目大意
给两个二进制的字符串，第二个可以左移k位，把左移后的第二个串和第一个串相加再逆序，求结果字典序最小的k值。
#### 解题思路
要字典序最小，我们先来看个例子10010和1，要让相加逆序后的字典序最小肯定要把第一个串中最后一位1变成0，那就贪心让第二个串的最后一个1去加上可以加到的第一个串从后往前的第一个1。没错，lowbit操作，虽然我用的是python的字符串查找(doge
#### AC代码
python t=int(input()) for alsgjsdkgljd in range(t): a=input() b=input() #exec("c=0b{}".format(b)) #p=c&(-c)#lowbit p=b[::-1].find('1')+1 coun=0 while(a[-p]!='1'): p=p+1 coun=coun+1 print(coun)
8.CF1234C
题目大意
有六种管道类型 地图是2行n列，给出地图，要求能否从起点(0,0)到达终点(2,n+1)
解题思路
这道题目和之前的牛客多校赛一道bfs差不多，虽然这个题出的更早2333。那道题的题解我听了，大致思路是差不多的，虽然题面给了六种管道，但是实际上因为有任意旋转操作，所以只有直管和弯管两种管道类型，然后我们只要关注当前点坐在坐标的管道类型，因为只有两行，所以是不可能往走回头路的那它能前往的位置一定是固定的，模拟一下看看会出界还是会到达终点就可以了。牛客的那道题目不局限于2行，所以要用bfs来搜索，它那个加了旋转限制的其实是障眼法，因为每次只需要旋转要前往的方块就行了，虽然我还没补（doge
AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int mp[4][maxn];
int main(){
int q;
int n;
int i,j,k;
char tmp;
int x,y,lx,ly;
scanf("%d",&q);
while(q--){
scanf("%d",&n);
mp[1][0]=666;
mp[2][n+1]=0;
mp[1][n+1]=0;
getchar();
for(i=1;i<=n;i++){
scanf("%c",&tmp);
mp[1][i]=((tmp=='1'||tmp=='2')?1:2);
}
getchar();
for(i=1;i<=n;i++){
scanf("%c",&tmp);
mp[2][i]=((tmp=='1'||tmp=='2')?1:2);
}
x=0;
y=1;
while(mp[y][x]!=0){
if(mp[y][x]==1){
if(abs(lx-x)){
ly=y;
lx=x;
++x;
}
else{
break;
}
}
else if(mp[y][x]==666){
if(mp[1][1]==1){
ly=1;
lx=1;
x=2;
}
else{
ly=1;
lx=1;
y=2;
x=1;
}
}
else{//2
if(abs(lx-x)){
ly=y;
lx=x;
y=3-y;
}
else{
ly=y;
lx=x;
x++;
}
}
}
if(x==n+1&&y==2)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}