【长期】板刷Codeforces 1500-1700 的构造题
https://codeforces.com/problemset/page/1?tags=constructive+algorithms%2C1500-1700&order=BY_RATING_ASC
每天三道，记录一下
（题意比较明显的，不说了。）
8.18
（1/3，做出第二道）
B. Plus and Multiply
https://codeforces.com/problemset/problem/1542/B
思路：找规律，发现 \(n=a^k + pb\), 即只要找到一个整数 \(p\) 满足等式即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve () {
queue <int> q;
int n, a, b;
cin >> n >> a >> b;
if (a == 1) {
if ((n-1) % b) cout << "No\n";
else cout << "Yes\n";
return ;
}
bool find = false;
int x = 1;
while (x <= n) {
if ((n - x) % b) x *= a;
else {
find = true;
break;
}
}
if (find) cout << "Yes\n";
else cout << "No\n";
}
signed main () {
int t;
cin >> t;
while (t --) {
solve ();
}
}
//Ax+B
//A%a==0,B%b==0
//n=a^k+pb
B. Codeforces Subsequences
https://codeforces.com/problemset/problem/1368/B
多写几项，不难发现"ccooddeforces"这样优先重复出现次数较少的更优，具体见下表：
\(2^1 * 1^9, 2^2 * 1^8, ..., 2^{10} * 1^0 (11,12,...20)\)
\(3^1 * 2^9, 3^2 * 2^8, ..., 3^{10} * 2^0 (21,22,...,30)\)
$4^1 * 3^9, 4^2 * 3^8, ..., 4^{10} * 2^0 (31,32,...,40) $
...
(前面是能构成的满足条件的串的数量，括号里面是串的长度)
大致统计一下就会发现 \(40^{10}\geq 10^{16}\)
因此出答案：
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main () {
int n, num1, num2;
cin >> n;
string s = "codeforces";
if (n == 1) {
cout << "codeforces";
return 0;
}
for (int i = 2; i <= 40; i++) {
bool find = false;
for (int j = 1; j <= 10; j++) {
int x = pow (i, j) * pow (i-1, 10-j);
if (x >= n) {
num1 = i, num2 = j;
find = true;
break;
}
}
if (find) break;
}
//cout << num1 << ' ' << num2 << endl;
for (int i = 0; i < 10; i++) {
for (int j = 1; j < num1; j++) {
cout << s[i];
}
if (i < num2) cout << s[i];
}
//for (int i = 1; i <= 10; i++) cout << pow(4,i)*pow(3,10-i) << ' ';
//cout << pow (40, 10);
}
//2^1, 2^2, ..., 2^10 (11,12,...20) (2,4,8,16,32,64,128,256,512,1024)
//3^1 * 2^9, 3^2 * 2^8, ..., 3^10 * 2^0 (21,22,...,30) (1536 2304 3456 5184 7776 11664 17496 26244 39366 59049)
//4^1 * 3^9, 4^2 * 3^8, ..., 4^10 * 2^0 (31,32,...,40)
//...
D. Binary String To Subsequences
https://codeforces.com/problemset/problem/1399/D
规则：如果00/11相邻就把他们划分开
上一个屁股后面如果能接上去就接，否则新开一个
模拟题
注意学习写法
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int pos[N];
void solve () {
int n, k = 0;
string s;
cin >> n >> s;
vector <int> v[2], ans;
for (auto i : s) {
int x = i - '0';
if (v[!x].empty()) {
v[x].push_back (++k);
ans.push_back (k);
}
else {
ans.push_back (v[!x].back());
v[x].push_back (v[!x].back());
v[!x].pop_back();
}
}
cout << k << endl;
for (auto i : ans) cout << i << ' ';
cout << endl;
}
int main () {
ios::sync_with_stdio (0);cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t --) {
solve ();
}
}
//如果00/11相邻就把他们划分开
//上一个屁股后面如果能接上去就接，否则新开一个
8.19
（2/3，做出第二、三道）
可能对于01串之类的比较敏感
C. Omkar and Baseball
https://codeforces.com/problemset/problem/1372/C
看乱序的有多少段
0段:0
1段:1
大于1段:2(可以通过一些操作变为连续)
#include <bits/stdc++.h>
using namespace std;
void solve () {
int n, x;
cin >> n;
int l = n + 1, r = 0, len = 0;
for (int i = 1; i <= n; i++) {
cin >> x;
if (x != i) {
len ++;
l = min (l, i), r = max (r, i);
}
}
if (len == 0) cout << "0\n";
else if (len == (r-l+1)) cout << "1\n";
else cout << "2\n";
}
int main () {
int t;
cin >> t;
while (t --) {
solve ();
}
}
//看乱序的有多少段
//0段:0
//1段:1
//>1段:2(可以通过一些操作变为连续)
C. Binary String Reconstruction
https://codeforces.com/problemset/problem/1400/C
只要保证0的左边第x个和右边第x个都是0即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
string s;
int x, n;
int a[N];
void solve () {
cin >> s >> x;
n = s.size();
for (int i = 0; i < n; i++) a[i] = 1;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
int st = i - x, ed = i + x;
//cout << st << ' ' << ed << endl;
if (st >= 0) a[st] = 0;
if (ed < n) a[ed] = 0;
}
}
for (int i = 0; i < n; i++) {
bool suc = false;
if (s[i] == '1') {
int st = i - x, ed = i + x;
if (st >= 0 && a[st] == 1) suc = true;
if (ed < n && a[ed] == 1) suc = true;
if (!suc) {
cout << "-1\n";
return ;
}
}
}
for (int i = 0; i < n; i++) cout << a[i];
cout << endl;
}
int main () {
int t;
cin >> t;
while (t --) {
solve ();
}
}
//只要保证0的左边第x个和右边第x个都是0即可
F. Binary String Reconstruction
https://codeforces.com/problemset/problem/1352/F
构造规则:s2+1的1串 连接 s0+1的0串 然后 依次补充s1-1个10
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
string s;
int s0, s1, s2;
void solve () {
cin >> s0 >> s1 >> s2;
if (s2) for (int i = 0; i <= s2; i++) cout << 1;
if (s0) for (int i = 0; i <= s0; i++) cout << 0;
if (s2 == 0 && s0 == 0) {
for (int i = 0; i <= s1; i++) {
if (i & 1) cout << 1;
else cout << 0;
}
}
else if (s2 == 0) {
if (s1) {
// for (int i = 0; i <= s0; i++) cout << 0;
// }
// else {
for (int i = 0; i < s1; i++) {
if (i & 1) cout << 0;
else cout << 1;
}
}
}
else if (s0 == 0) {
if (s1) {
// for (int i = 0; i <= s2; i++) cout << 1;
// }
// else {
for (int i = 0; i < s1; i++) {
if (i & 1) cout << 1;
else cout << 0;
}
}
}
else {
for (int i = 1; i < s1; i++) {
if (i & 1) cout << 1;
else cout << 0;
}
}
cout << endl;
}
int main () {
int t;
cin >> t;
while (t --) {
solve ();
}
}
//构造规则:s2+1的1串 和 s0+1的0串 然后 依次补充s1-1个10
8.20
（1/3，做出第二道）
D. Non-zero Segments
https://codeforces.com/problemset/problem/1426/D
统计前缀和，如果出现过了，就插一个很大的数
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main () {
int n, ans = 0, sum = 0;
cin >> n;
set<int> s;
//s.insert (0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
if (s.count (sum) || sum == 0) {
ans ++;
sum = x;
s.clear ();
//s.insert (0);
}
s.insert (sum);
}
cout << ans << endl;
}
D2. Sage's Birthday (hard version)
https://codeforces.com/problemset/problem/1419/D2
构造规则：偶数位从小到大填，然后后续的数字再接着从小到大填到奇数位上
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], n;
int main () {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 2) {
cout << "0\n";
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}
sort (a + 1, a + n + 1);
vector <int> v(n+1);
int cnt = 0;
for (int i = 2; i <= n; i += 2) {
v[i] = a[++cnt];
}
for (int i = 1; i < n; i += 2) {
v[i] = a[++cnt];
}
if (v[n] == 0) v[n] = a[n];
cnt = 0;
for (int i = 2; i < n; i++) {
if (v[i] < v[i-1] && v[i] < v[i+1])
cnt ++;
}
cout << cnt << endl;
for (int i = 1; i <= n; i++) cout << v[i] << ' ';
}
//构造数组使得“相邻左边的和右边的数字都比它大”这样的数字出现的尽可能多
//最多能有(n-1)/2个
//2 4 6 ...填最小，然后填最大
C. Even Picture
https://codeforces.com/problemset/problem/1368/C
可恶的样例。。害得我被误导了。
其实只要按照这样“阶梯型”去构造就很 \(easy\) 了
#include <bits/stdc++.h>
using namespace std;
int n;
int dx[] = {-1, 0, 1};
int main () {
cin >> n;
cout << n * 3 + 4 << endl;
cout << "0 0\n1 0\n";
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) {
cout << i + dx[j] << ' ' << i << endl;
}
}
cout << n << ' ' << n + 1 << endl;
cout << n + 1 << ' ' << n + 1 << endl;
}
//灰格子连通
//每个灰格子都有偶数个邻居
//灰色格子的四面都是灰色格子的数量为n
//阶梯型2-3-3-..-3-2构造即可
//n=几就是几层3