Codeforces Round 1006 div.3

A

题意

• 给定n,k,p,能否在判断np和k的关系

思路

• 就简单签到

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,k,p;
		scanf("%d%d%d",&n,&k,&p);
		if(abs(k)>n*p)printf("-1\n");
		else{
			int rst=abs(k)/p;
			if(k%p!=0)rst++;
			printf("%d\n",rst);
		}
	}
	return 0;
}

B

题意

• 给定由-和_组成的字符串，求形如-_-子列的个数

思路

• 想要总个数最大，尽可能让所有_被尽可能多的使用到，所以将-分为两半，计算即可

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,s0=0,s1=0;
		char s;
		scanf("%d ",&n);
		for(int i=0;i<n;i++){
			scanf("%c",&s);
			if(s=='-')s0++;
			else s1++;
		}
		long long ans=1ll*s0/2*s1;
		if(s0%2)ans*=s0/2+1;
		else ans*=s0/2;
		printf("%lld\n",ans);
	}
}

C

题意

• 给定n,x生成一个长为n，或和为x的数组，使得最小的不被包含在数组里的非负整数最大

思路

• 由于要求或和为n，所以数组中可填的只有可能是小于n的数，从0开始枚举，记录当前或和，如果或和或上当前数仍小于等于n，ans就包含当前数，更新或和，否则就填0，特判最后一位等不等于n

注意!!

• 从二进制判断一个数x是否包含在另一个数y内的方法：

  

• 解释：对于单一位置来看，如果x超过y只有一种情况即：x=1，y=0此时会改变x当前位为1，不等于x

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,x;
		scanf("%d %d",&n,&x);
		int sum=0;
		for(int i=0;i<n;i++){
			if(i==n-1&&(sum|i)!=x){
				printf("%d",x);
			}else if(((sum|i)&x)==(sum|i)){
				sum|=i;
				printf("%d ",i);
			}else{
				printf("0 ");
			}
		}
		printf("\n");
	}
	return 0;
}