Codeforces Round 713 (Div. 3)
A-B Palindrome
给定字符串只含有\('?'\ '0' \ '1'\),给定字符串中1的个数\(a\)和0的个数\(b\)，你需要将？替换成0 或 1，使得该字符串变成回文串，并且使得1的个数为a，0的个数为b
题解：构造 + 模拟
注意以下几点：
- 字符串长度为\(a+b\)，a和b只能有一个是奇数；
- 对于两个对应的位置，如果一个位置确定，那么另一个位置如果是？，也是确定的
- 如果对应的两个位置都是确定的，但是如果不一样，该字符串是不合法的
模拟的过程：
- 如果长度为奇数，先确定中间的位置是1还是0
- 将所有可以确定的问号都替换掉，并检查字符串是否合法
- 将只剩未确定问号的字符串中1的数量和0的数量计算出来，然后a和b各自减去这些数量，如果a或b小于0，说明不合法
- 替换所有未确定的问号，如果1有多余就用1，0有多余就用0，如果两个都没有多余的了，说明不合法
- 如果以上步骤都合法，说明可以构造出这样一个合法字符串
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
void solve()
{
int a, b;
cin >> a >> b;
string s;
cin >> s;
int n = a + b;
s = " " + s;
if (a % 2 == 1 && b % 2 == 1)
{
cout << -1 << endl;
return;
}
if (a % 2 == 1)
{
if (s[n / 2 + 1] == '?')
{
s[n / 2 + 1] = '0';
}
else if (s[n / 2 + 1] == '1')
{
cout << -1 << endl;
return;
}
}
else if (b % 2 == 1)
{
if (s[n / 2 + 1] == '?')
{
s[n / 2 + 1] = '1';
}
else if (s[n / 2 + 1] == '0')
{
cout << -1 << endl;
return;
}
}
for (int i = 1; i <= n / 2; ++i)
{
if (s[i] != s[n - i + 1] && s[i] != '?' && s[n - i + 1] != '?')
{
cout << -1 << endl;
return;
}
else if (s[i] != s[n - i + 1] && (s[i] == '1' || s[n - i + 1] == '1'))
{
s[i] = s[n - i + 1] = '1';
}
else if (s[i] != s[n - i + 1] && (s[i] == '0' || s[n - i + 1] == '0'))
{
s[i] = s[n - i + 1] = '0';
}
}
for (int i = 1; i <= n; ++i)
{
if (s[i] == '0')
a--;
else if (s[i] == '1')
b--;
}
if (a < 0 || b < 0)
{
cout << -1 << endl;
return;
}
for (int i = 1; i <= n / 2; ++i)
{
if (s[i] == s[n - i + 1] && s[i] == '?')
{
if (a >= 2)
{
a -= 2;
s[i] = s[n - i + 1] = '0';
}
else if (b >= 2)
{
b -= 2;
s[i] = s[n - i + 1] = '1';
}
else
{
cout << -1 << endl;
return;
}
}
}
cout << s.substr(1) << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Permutation by Sum
现在又一个由排列构成的序列\(P\)\([1,n]\)，给定序列长度n，区间端点\(l,r\)，以及\(s\)，让你利用这个序列构造出\(s=p_l+p_{l+1}+...+p_r\)
如果无法构造输出\(-1\)
题解：构造 + 思维
- 什么情况下可以构造出来：
\(len = r-l+1\),如果序列为\(1,2,3.....n\)
那么只有\(s>=1+2+..+i(长度为len)\)并且\(s<=n+n-1+n-2+...+i(长度为len)\)时可以构造出
如何构造(举个样例)：
1） \(1,2,3...10\) \(len = 4 , s = 16\)
2）取\(1,2,3,4\)
3）\(dif = s - (1+2+3+4) = 6\), \(6/4=1,6\%4=2\)
4）\(1,2,3,4 --> 2,3,4,5 --> 2,3,6,5\)
完成构造
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, l, r, s;
int a[N];
void solve()
{
cin >> n >> l >> r >> s;
map<int, int> mp;
int len = r - l + 1;
if ((n - len + 1 + n) * len / 2 < s || (1 + 1 + len - 1) * len / 2 > s)
{
cout << -1 << endl;
return;
}
int dif = s - (1 + 1 + len - 1) * len / 2;
int x = dif / len, plus = dif % len;
int cnt = 0;
for (int i = l; i <= r; ++i)
{
a[i] = ++cnt;
a[i] += x;
mp[a[i]]++;
}
if (plus)
{
for (int i = l; i <= r; ++i)
{
if (a[i] + plus <= n && !mp[a[i] + plus])
{
mp[a[i]] = 0;
a[i] += plus;
mp[a[i]] = 1;
break;
}
}
}
cnt = 0;
for (int i = 1; i <= n && cnt < l - 1; ++i)
{
if (!mp[i])
{
mp[i] = 1;
cnt++;
cout << i << " ";
}
}
for (int i = l; i <= r; ++i)
cout << a[i] << " ";
cnt = 0;
for (int i = 1; i <= n && cnt < n - r; ++i)
{
if (!mp[i])
{
mp[i] = 1;
cnt++;
cout << i << " ";
}
}
cout << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Education
一个人想要尽快得到\(m\)元钱，他现在有\(0\)元，他在公司中的职位为\(1\)，职位越高每天工资越高，每一天他有两种选择：
- 得到相应职位对应的工资 \(a_i\)
- 花去\(b_i\)的钱使得自己的职位上升一级
求这个人最少几天能够获得\(m\)元钱
题解：贪心 + 模拟
一开始以为是\(dp\),后来发现是个贪心问题，对于一个人来说他想获得m元钱的最快方法就是先快速到达一个理想的职位，然后一直拿工资，直到获得m元
所以，该题我们只需要枚举在每个职位能够多久获得m元，然后取\(min\)即可
接下来的事情只剩下模拟了，注意使自己职位上升也要算一天
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, m;
int a[N];
int b[N];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i < n; ++i)
cin >> b[i];
int ans = INF;
int now = 0;
int sum = 0;
for (int i = 1; i <= n; ++i)
{
ans = min(ans, sum + (long long)(ceil(1.0 * max(0ll, m - now) / a[i])));
if (i < n)
{
int p = (long long)ceil(1.0 * max(0ll, (b[i] - now)) / a[i]);
sum += p + 1;
now += p * a[i] - b[i];
}
}
cout << ans << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Short Task
规定\(d(n)=\sum_{k|n}k\),即\(d(n)\)为n的约数之和，现在每次询问给定c，求出最小的n使得\(d(n)=c,c<=1e7\)，如果不存在输出-1
题解：约数之和 : 需要知道调和级数和如何求约数之和
引理：调和级数：\(n+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n}=nlogn\)
首先n一定小于1e7,我们先\(nlogn\)预处理出le7以内的所有\(d(n)\),然后\(map\)映射一下即可，查询出直接查询\(map\)即可
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e7 + 10, M = 4e5 + 10;
int d[N];
int ans[N];
void solve()
{
int n;
cin >> n;
if (!ans[n])
cout << -1 << endl;
else
cout << ans[n] << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
for (int i = 1; i < N; ++i)
for (int j = i; j < N; j += i) //i是j的约数，复杂度是调和级数nlogn
d[j] += i;
for (int i = 1; i < N; ++i)
{
if (d[i] > N - 10)
continue;
if (!ans[d[i]])
ans[d[i]] = i;
}
while (T--)
{
solve();
}
return 0;
}