Codeforces Round 900 (Div. 3)(A-F)

比赛链接? :

Dashboard - Codeforces Round 900 (Div. 3) - Codeforces

A. How Much Does Daytona Cost?

题面 :?

思路 :

在序列中只要找到k，就返回true ;

代码 :?

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
const int N = 2e5+10;

inline void solve(){
	int n , k ; cin >> n >> k ;
	bool tag = false;
	for(int i=0;i<n;i++){
		int x ; cin >> x ;
		if(x==k) tag = true;
	}
	if(tag) cout << "Yes" << endl;
	else cout << "No" << endl;
	return ;
}
 
int main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

B. Aleksa and Stack

题面 :?

思路 :

在这道题中，只要满足任意两个相邻数的和，不能够不是3的倍数，且数组单调递增，那么便可以构造出这样一个序列，每两个相邻数中第一个数 mod 3 = 0,另一个数mod 3 = 1 ,然后递增的话，就可以使a1 = 3 *1 , a2= a1 + 1,a3 = 3 * 2,a4 = a3 + 1，即可满足题目条件；

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b); }
int lcm(int a,int b){ if(a==0||b==0) return 0; return (a*b)/gcd(a,b); }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
//numbers.erase(std::unique(numbers.begin(), numbers.end()), numbers.end()); // 去重操作
const int N = 2e5+10;

// 任意两个数的和不是3的倍数 

// 0, 1, 2
// 3 , 4 , 6, 7 

inline void solve(){
	int n ; cin >> n ;
	int x = 3;
	while(n>1){
		cout << x << " " << x + 1 << " ";
		x += 3;
		n -= 2;
	}
	if(n) cout << x ;
	cout << endl ;
	return ;
	
}
 
int main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

?C. Vasilije in Cacak

题面 :?

思路 :?

对于从??[1 ,n ]? 中 选k个数 的 和为x;

假如 n = 2 (并且假设k = 2,下面一样):

?????????1,2 --> 1, 2, 3
n = 3 :

????????1, 2 ,3 : 1,2,3,4,5,6 选两个 : 3-5?
n = 4 :

????????1,2,3,4 : 3-7 : ?

那么我们就可以发现一个规律 : 在[1,n]中取k个数和的范围是[最小的k个数相加，最大的k个数相加];

为了计算的方便，我们可以使用等差数列求和 : s = n*a1+(n-1)*n*d/2? ;

代码 :?

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;

LL n , k , x ;

// [1,n] 中 选k个数 的 和为x;

// 1,2 --> 1, 2, 3
//1, 2 ,3 : 1,2,3,4,5,6 选两个 : 3-5 
// 1,2,3,4 : 3-7 :  

// 等差数列求和 : s = n*a1+(n-1)*n*d/2 

inline void solve(){
	cin >> n >> k >> x;
	LL l = (1+k)*k/2 , r = (n+n-k+1)*k/2;
	if(x>=l && x<=r) cout << "Yes" << endl;
	else cout << "No" << endl;
	return ;
}
 
int main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

D. Reverse Madness

题面

思路 :?

l和r都是单调递增的，且对于每一段区间都是不相交的，所有可以很快找到x对应的li和ri来满足li<=x && x<=ri ；

找到之后就是进行区间的反转，对于每个区间假设li = 2,ri =6,如果x = 4,则a=b=4,如果x=3,则a=3,b=5;那么说明是关于终点对称的，那么就可以使用前缀和算法，来对每个点进行反转次数的统计，如果统计次数为偶那就不用反转了，为奇，则要反转，具体请看代码；

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
const int N = 2e5+10;

inline void solve(){
	int n,k;cin >> n >> k ;
	string s ; cin >> s ;
	s = ' ' + s ;
	vector<int> l(k+1) , r (k+1) ;
	for(int i=1;i<=k;i++) cin >> l[i] ;
	for(int i=1;i<=k;i++) cin >> r[i] ;
	int q ; cin >> q ;
	vector<int> x(q+1) ;
	for(int i=1;i<=q;i++) cin >> x[i] ;
	vector<pair<int,int>> sum(n+3) ;
	for(int i=1;i<=q;i++){
		int pos = lower_bound(r.begin()+1,r.end(),x[i]) - r.begin();
		int a = min(x[i] , r[pos]+l[pos]-x[i]);
		int b = max(x[i],r[pos]+l[pos]-x[i]);
		sum[a].first++ ; sum[b+1].first--;
		sum[a].second = b ; sum[b].second = a ;
	}
	for(int i=1;i<n;i++){
		sum[i].first += sum[i-1].first ;
	}
	int start = -1 , end = -1 ;
	for(int i=1;i<=n;i++){
		if(sum[i].first % 2 == 1){
			start = i ;
			int end = sum[i].second ;
			while(start <= end){
				while(start<=end && sum[start].first % 2 == 1){
					swap(s[start],s[end]);
					start ++;
					end--;
				}
				while(start <= end && sum[start].first % 2 == 0){
					start ++;
					end -- ;
				}
			}
			i = sum[i].second ;
		}
	}
	for(int i=1;i<=n;i++) cout << s[i] ;
	cout << endl; 
}
 
int main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

E. Iva & Pav

题面 :

思路 :?

// f(l,r)=al & al+1 &…& ar
// 给定一个 l , k ,求最大的r,满足f(l , r) >= k ;
// 定l,则f随着r单调递减?
// & : 按位与?

按位与的特点是，对于某一位，[l,r]上的所有数的该位上为1，结果才为1,那么我们可以采用前缀和的思想，用bit[i][j]来存[1,i]上第j位上为1的个数，具体实现请看代码，再获得bit数组之后，因为在l确定之后，f(l,r)随着r的增大具有单调递减的性质，所有可以使用二分来进行操作；

具体实现请看代码 ；

代码 :?

// f(l,r)=al & al+1 &…& ar
// 给定一个 l , k ,求最大的r,满足f(l , r) >= k ;
// 定l,则f随着r单调递减 
// & : 按位与 
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
const int N = 2e5 + 10 ;

inline void solve(){
	int n ; cin >> n ;
	vector<array<int,32>> bit(n+1);
	for(int i=1;i<=n;i++){
		int x ; cin >> x ;
		for(int j = 0;j<32;j++){
			bit[i][j] = 0 ;
			bit[i][j] += x % 2 ;
			x /= 2 ;
			bit[i][j] += bit[i-1][j] ; // 进行前缀和操作，统计i前面j位上为1的个数 
		}	
	} 
	auto check = [&](int l,int r ,int c){
		vector<int> b(32) ;
		for(int i=0;i<32;i++){
			b[i] = bit[r][i] - bit[l-1][i] ;
		}
		int ans = 0 ;
		for(int i=0;i<32;i++){
			if(b[i]==r-l+1) ans += pow(2,i);
		}
		return ans >= c ; 
	};
	int q ; cin >> q ;
	while(q--){
		int l , k ; cin >> l >> k ;
		int L = l, R = n;
		int ans = -1 ;
		while(L<=R){
			int mid = (L+R)>>1 ;
			if(check(l,mid,k)){
				ans = mid ;
				L = mid + 1; 
			}else{
				R = mid - 1 ;
			}
		}
		cout << ans << " " ;
	}
	cout << endl ;
}
 
int main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

F. Vasilije Loves Number Theory

题面 :?

思路 :?

• ?1 : n *= x，然后问是否存在一个a使得gcd(n,a)=1并且n*a的约数个数等于n，
• gcd(n,a)=1 --> n,a互质
• 由于n,a互质，那么 d(n)*d(a)=d(n*a)，那么就是要d(a) = n / d(n)，所以n % d(n)一定要等于零?

然后就可以通过唯一分解定理来解;

具体实现请看代码 :

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
const int N = 2e5+10;

// 1 : n *= x，然后问是否存在一个a使得gcd(n,a)=1并且n*a的约数个数等于n，
// gcd(n,a)=1 --> n,a互质
// --> d(n)*d(a)=d(n*a)，那么就是要d(a) = n / d(n)，所以n % d(n)一定要等于零 

inline void solve(){
	int n,q;cin>>n>>q;
	int cnt = 1 ; // 记录因数的数量 
	map<int,int> doc ;
	// 质因数分解 : 
	// num = b1^c1 + b2 ^c2 + .... + bn^cn ; 
	for(int i=2;i*i<=n;i++){
		// i相当于上面的b,c相当于上面的c ; 
		if(n%i==0){
			int c =  0 ;
			while(n%i==0) n/=i,c++;
			doc[i] = c ;
			cnt *= (c+1);
		}
	}
	if(n>1) doc[n] = 1 , cnt *= 2 ; // 最后剩下的n本身也是一个质因数 
	int now = cnt;auto doc2 = doc ;
	while(q--){
		int op ; cin >> op ;
		if(op == 2){
			now = cnt  ;
			doc2 = doc ;
		}else{
			int x ; cin >> x ;
			for(int i=2;i*i<=x;i++){
				if(x%i==0){
					int c =  0 ;
					while(x%i==0) x/=i,c++;
					now /= (doc2[i]+1);
					doc2[i] += c; 
					now *= (doc2[i]+1);
				}
			}
			if(x>1){
				now /= (doc2[x]+1);
				doc2[x]+=1;
				now *= (doc2[x]+1);
			}
			int t = now  ;
			for(auto it:doc2){
				int x = it.first ;
				int y = it.second ;
				while(y>0 && t % x== 0){
					t /= x ;
					y -- ;
				}
			}
			cout << (t==1?"YES":"NO")<<endl; 
		}
	}
}
 
int main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}