Codeforces

用于记录 CF比赛 补题

提示
这是一个提示

注意
这是一个警告

警告
这是一个危险信号

成功
这是一个成功信号

 点击折叠

这是被隐藏的内容

DIV2(1030)

B

TipS
纯属构造题，一开始思路没问题，但是就是 , 其实对于每一行操作都是固定的，前面翻转，后面翻转，总体翻转，因为每一行都需要整体翻转，所以是可以省去的。

#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;

signed main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		cout << 2 * n - 1 << endl;
		cout << 1 << " " << 1 << " " << n << endl;
		for(int i = 2; i <= n; i++){
			cout << i << " " << 1 << " " << i - 1 << endl;
			cout << i << " " << i << " " << n << endl;
		}
	}
	return 0;
}

EDU-181

C

题目意思是求 [l, r] 区间内的数字,不是 {2, 3, 5, 7}的倍数的数字的个数题目理解:
因为让你求不是{2, 3, 5, 7}的倍数的数字, 那我是不是可以求是 {2, 3, 5, 7}的倍数的数字个数,那现在怎么求呢? 可以想到 容斥定理,求是 2，3，5，7的倍数的数字，相当于

#include<bits/stdc++.h>
using namespace std;
#define int long long 
/*
	其实是判断 l -> r中不是 2,3,5,7倍数的数字个数
	1 - r 
	2 + 3 + 5 + 7 - （2,3) - (2, 5) - (2 ,7)
*/
int dx[8] = {2,3,5,7,30,42,70,105}; // + 
int dy[7] = {6,10,14,15,21,35,210}; // - 

void slove(){
	int l, r;
	cin >> l >> r;
	auto sum = [&](int en) -> int{
		if(en == 2) return 0;
		int ans = 0;
		for(int i = 0; i < 8; i++){
			ans += (en / dx[i]);
		}
		for(int i = 0; i < 7; i++){
			ans -= (en / dy[i]);
		}
		return ans;
	};
	int ans = r - l + 1, last = sum(r) - sum(l);
	cout << ans - last << endl;
}
signed main(){
	int t;
	cin >> t;
	while(t--){
		slove();
	}

}

DIV1 + DIV2(1048)

C

针对于这个问题其实比较简单,但是答案有体现了一个很有用的思想: 逆向思维,如果正着想感觉思路有点过于复杂,或者过程难以描述,可以尝试反着想,因为反向想的话过程可能就是唯一或者比较有规律的

#include<bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	int t;
	cin >> t;
	while(t--){
		int k, x;
		cin >> k >> x;
		int kk = (1ll << k);
		if(!x || x == kk * 2){
			cout << "-1\n";
			continue;
		}
		int y = 2 * kk - x;
		vector<int> ans; ans.clear();
		while(x != kk){
			if(x > y){
				x -= y; y *= 2;
				ans.push_back(2);
			}else {y -= x; x *= 2, ans.push_back(1);}
		}
		cout << ans.size() << "\n";
		while(!ans.empty()){
			cout << ans.back() << " ";
			ans.pop_back();
		}
		cout << endl;
	}
}