oj: CodeForces
题目顺序为倒叙。
D. Genius’s Gambit
oj: CodeForces
题意
给定 3 3 3 个整数 a , b , k a,b,k a,b,k。
找出满足以下条件的两个二进制数 x , y x,y x,y：
- x x x 和 y y y 的二进制形式都是由 a a a 个 0 0 0 和 b b b 个 1 1 1 构成。
- x − y x-y x−y 的二进制形式中有 k k k 个 1 1 1 。
x x x 和 y y y 没有前导 0 0 0 。
题解
由于 x − y x-y x−y 没有前导 0 0 0 限制，所以我们假设 x − y x-y x−y 是由 k k k 个连续的 1 1 1 构成。我们假设这个值为 z z z 。
那么问题就转化成如何从 a + b a+b a+b 个二进制位中选出 b b b 个作为 1 1 1 ，其他的作为 0 0 0 来生成一个二进制数，其值加上 z z z 之后也是由 a a a 个 1 1 1 和 b b b 个 0 0 0 构成。
例如 z = 11 1 2 , a = 3 , b = 3 z=111_2,a=3,b=3 z=1112,a=3,b=3，那么考虑到 x x x 和 y y y 没有前导 0 0 0 ，又要维持 a + b a+b a+b 的长度，所以 x x x 和 y y y 的第 1 1 1 位一定都是 1 1 1 ，那么 x x x 和 y y y 就是这样的形式：
1*****
。
然后我们在 y y y 的末尾放一个 1 1 1 ：
100001
，来消去 z z z 中的所有 1 1 1 ，同时进位，此时求得的 x x x 为
101000
。
然后我们就可以在 y y y 中 0 0 0 对应的且没有被选过的位置中取出 b − 2 b-2 b−2 个作为 1 1 1 ，这样就能保持 x x x 和 y y y 中的 1 1 1 的数量始终同步。例如 x x x 和y可以分别是(
111000
,
110001
), (
101100
,
100101
), (
101010
,
100011
)。
不满足以上推导的没有解。
代码
#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int a, b, k;
string ans, ant;
void init() {
ans.clear();
ant.clear();
}
void sol() {
init();
if(k == a + b) {
cout << "No\n";
return;
}
int l = min(a + b - k - 1, k ? b - 1 : b);
_for(i, l) ans.push_back('1');
_for(i, a) ans.push_back('0');
_for(i, b - l) ans.push_back('1');
_for(i, a + b) ant.push_back('0');
int f = 0;
for(int i = ans.size() - 1; i >= 0; --i) {
int tem = ans[i] - '0' + (ans.size() - i <= k) + f;
if(tem == 1) ant[i] = '1', f = 0;
else if(tem == 2) f = 1;
else if(tem == 3) ant[i] = '1', f = 1;
}
if(f || ans[0] == '0' || ant[0] == '0') {
cout << "No\n";
return;
}
cout << "Yes\n";
cout << ant << "\n" << ans << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while(cin>>a>>b>>k) {
sol();
}
return 0;
}
C. Maximum width
oj: CodeForces
题意
给定两个字符串 s s s 和 t t t，存在一个数组 p p p 使得每一个 i ∈ [ 1 , m ] i \in [1,m] i∈[1,m] 都有 s p i = t i s_{p_i}=t_i spi=ti。
求出 max 1 ≤ i < m ( p i + 1 − p i ) \max\limits_{1 \le i < m} \left(p_{i + 1} - p_i\right) 1≤i<mmax(pi+1−pi)。
题解
对每个 s [ i ] s[i] s[i] 求出其对应的最靠左的 t [ j ] t[j] t[j] 和最靠右的 t [ k ] t[k] t[k]，那么答案就至少是 k − j k-j k−j。
代码
#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
typedef long long LL;
const int maxn = 200005;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n, m;
char s[maxn], t[maxn];
int ml[maxn], mr[maxn];
void sol() {
scanf("%s%s", s, t);
int p = 0;
_for(i, m) {
while(s[p] != t[i]) ++p;
ml[i] = p++;
}
p = n - 1;
for(int i = m - 1; i >= 0; --i) {
while(s[p] != t[i]) --p;
mr[i] = p--;
}
int ans = 0;
for(int i = 1; i < m; ++i) {
ans = max(ans, mr[i] - ml[i - 1]);
}
printf("%d\n", ans);
}
int main() {
n = read(), m = read();
sol();
return 0;
}
B. Card Deck
oj: CodeForces
题意
给定一个长度为 n n n 的数组 p p p。你可以执行以下操作：取出旧数组的后几位，保持其顺序不变，放到新数组里，直到旧数组为空。
求出新数组中 ∑ i = 1 n n n − i ⋅ p i \sum\limits_{i = 1}^{n}{n^{n - i} \cdot p_i} i=1∑nnn−i⋅pi 的最大值。
题解
让最大的值尽量靠前。
每次找剩余数组中的最大值，然后将最大值及其后面的一段取出放到新数组中。
代码
#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
#define nl(i, n) (i == n - 1 ? "\n" : " ")
using namespace std;
typedef long long LL;
const int maxn = 100005;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n, a[maxn];
vector<int> ans;
int num[maxn];
void init() {
ans.clear();
}
void sol() {
init();
_for(i, n) a[i] = read();
_for(i, n) num[a[i]] = i;
int p = n - 1;
for(int i = n; i > 0; --i) {
for(int j = num[i]; j <= p; ++j) ans.push_back(a[j]);
p = min(p, num[i] - 1);
}
_for(i, ans.size()) printf("%d%s", ans[i], nl(i, ans.size()));
}
int main() {
int T = read();
_for(i, T) {
n = read();
sol();
}
return 0;
}
A. Three swimmers
oj: CodeForces
题意
有 n n n 个游泳选手，他们每人游泳的速度不一样，第 i i i 个人需要 a [ i ] a[i] a[i] 分钟完成一个来回，并且他们在无止境地训练。你在第 p p p 分钟到达现场，请问你最少需要等待多少分钟才能和其中一位选手见面。
题解
对每个选手求出最短等待时间，然后取最小值。
先求出 p p p 对 a [ i ] a[i] a[i] 上取整的商，就可以很容易求出等待时间了。
代码
#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
LL p, a, b, c;
void sol() {
if(p == 0) {
printf("0\n");
return;
}
LL ans = INF;
ULL t = 1;
ans = min(ans, t * (p + a - 1) / a * a - p);
ans = min(ans, t * (p + b - 1) / b * b - p);
ans = min(ans, t * (p + c - 1) / c * c - p);
long long an = ans;
printf("%lld\n", an);
}
int main() {
int T = read();
_for(i, T) {
p = read(), a = read(), b = read(), c = read();
sol();
}
return 0;
}
![The beautiful values of the palace（找规律+离散化）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)