Codeforces Round #704 (Div. 2)
A - Three swimmers
题意
三个人游泳，从左侧台子出发，来回一次的时间分别是 a , b , c a, b, c a,b,c 分钟，他们在泳池里不间断的来回。你在第 p p p 分钟到达，问第一个出现在左侧的人至少要多少时间才出现？
思路
分别计算三个人各需要多久回来，取最小。
代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 9;
const ll MOD = 1e9 + 7;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
ll a, b, c, p;
scanf("%lld%lld%lld%lld", &p, &a, &b, &c);
a = (p / a + (p % a > 0 ? 1 : 0)) * a - p;
b = (p / b + (p % b > 0 ? 1 : 0)) * b - p;
c = (p / c + (p % c > 0 ? 1 : 0)) * c - p;
cout << min(a, min(b, c)) << endl;
}
return 0;
}
B - Card Deck
题意
n n n 张卡片叠成一堆，每张上都写了数字，从下往上的第 i i i 张上写着 p i p_i pi 。现在要求你按照以下规则重新排列卡片，使得 ∑ i = 1 n n n − i ⋅ p i \sum_{i = 1} ^n n ^{n - i} · p_i ∑i=1nnn−i⋅pi 的值最大：
- 选取从上往下数的第 i i i 张；
- 把第 i i i 张即其上方的所有卡片一起放到新的一堆的顶上；
- 一直重复，直到原来的那堆为空
思路
可以证明，最优情况一定是每次选取原堆剩余中的最大的元素所在的位置，移动其及其上的所有卡片（可以自己比较一下对于7 1 2 3 4 5 6，是6在底下还是7在底下大）。
代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 9;
const ll MOD = 1e9 + 7;
struct node
{
int data;
int id;
}a[N];
bool vis[N];
int num[N];
bool cmp(node& a, node& b)
{
if(a.data == b.data)
return a.id > b.id;
return a.data > b.data;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
fill(vis, vis + n + 1, 0);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i].data);
num[i] = a[i].data;
a[i].id = i;
}
sort(a, a + n, cmp);
for(int i = 0; i < n; i++)
{
if(vis[a[i].id])
continue;
for(int j = a[i].id; j < n; j++)
{
if(vis[j])
break;
printf("%d ", num[j]);
vis[j] = 1;
}
}
printf("\n");
}
return 0;
}
C - Maximum width
题意
给定字符串 s , t s, t s,t （长度分别为 n , m n, m n,m ），要求你构造一个序列 p p p ，使得 1 ≤ p 1 < p 2 < ⋯ < p m ≤ n 1 \leq p_1 \lt p_2 \lt \dots \lt p_m \leq n 1≤p1<p2<⋯<pm≤n 且对于所有的 i ∈ [ 1 , m ] i \in [1, m] i∈[1,m] ，有 s p i = t i s_{p_i} = t_i spi=ti。现在你要输出 m a x ( p i + 1 − p i ) max(p_{i + 1} - p_i) max(pi+1−pi) 的最大值。
思路
记录每个点可以取的左右限，这个左右限受三个因素影响：第一， t i t_i ti 在 s s s 中出现位置的左右限；第二， t i − 1 t_{i - 1} ti−1 的左限要小于 t i t_i ti 的左限；第三， t i + 1 t_{i + 1} ti+1 的右限要大于 t i t_i ti 的右限。只有二、三满足了，序列 p p p 的元素才能递增。
最后只要取 m a x ( t i + 1 r − t i l ) max(t_{{i + 1}_r} - t_{i_l}) max(ti+1r−til) 即可，即下一个元素的最大值-上一个元素的最小值。
代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 9;
const ll MOD = 1e9 + 7;
char s[N], t[N];
struct node
{
vector<int> pos;
int id = 0;
}a[N];
struct node_
{
int l, r;
}b[N];
int main()
{
int n, m;
cin >> n >> m;
cin >> s;
cin >> t;
for(int i = 0; i < n; i++)
{
a[s[i] - '0'].pos.push_back(i);
}
int ans = 0;
b[m - 1].r = a[t[m - 1] - '0'].pos.back();
for(int i = m - 2; i >= 0; i--)
{
while(a[t[i] - '0'].pos.back() >= b[i + 1].r)
a[t[i] - '0'].pos.pop_back();//直接删除尾部，以后肯定用不到
b[i].r = a[t[i] - '0'].pos.back();
}
b[0].l = a[t[0] - '0'].pos[0];
for(int i = 1; i < m; i++)
{
int idx = a[t[i] - '0'].id;//因为直接删除首部元素不太方便，所以用下标记录了。其实r的更新也可以用下标记录
while(a[t[i] - '0'].pos[idx] <= b[i - 1].l)
idx++;
b[i].l = a[t[i] - '0'].pos[idx];
a[t[i] - '0'].id = idx;
}
for(int i = 0; i < m - 1; i++)
{
int x = b[i].l;
int y = b[i + 1].r;
ans = max(ans, y - x);
}
cout << ans << endl;
return 0;
}
D - Genius’s Gambit
题意
有两个数，这两个数在二进制表示下0的个数相同、1的个数相同。给定0和1的个数 a , b a, b a,b，以及数字 k k k ，问是否有满足条件的两个数字，这两个数字相减得到的数字里1的个数恰好是 k k k 个？在二进制表示下输出两个数字，找不到答案输出-1。
思路
最简单的构造方法是相减得到的数恰好是
2
k
−
1
2^k - 1
2k−1，即只有
k
k
k 个
1
1
1。假设个位是第
1
1
1 位，那么两个数字就在第
1
1
1 位和第
k
k
k 位不同，其他地方都相同，即：
{
1
⋯
⏟
a
+
b
−
k
−
2
1
⋯
⏟
k
−
2
0
1
⋯
⏟
a
+
b
−
k
−
2
0
⋯
⏟
k
−
2
1
\left\{\begin{aligned} 1\underbrace{\cdots}_{\rm a + b - k - 2}1\underbrace{\cdots}_{\rm k - 2}0\\ \\ 1\underbrace{\cdots}_{\rm a + b - k - 2}0\underbrace{\cdots}_{\rm k - 2}1 \end{aligned} \right.
⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧1a+b−k−2
⋯1k−2
⋯01a+b−k−2
⋯0k−2
⋯1
因此，我们可以得到给定
a
,
b
,
k
a, b, k
a,b,k 有答案的充要条件：
{
a
+
b
−
k
−
2
>
0
a
>
2
b
>
1
.
\begin{cases} a + b - k - 2 > 0 \\ a > 2 \\ b > 1 \end{cases}.
⎩⎪⎨⎪⎧a+b−k−2>0a>2b>1.
特判
k
=
0
k = 0
k=0 的情况，一定是成功的（两个数一样就行），再特判无答案的情况，其他的就按照上面构造即可。
代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 9;
const ll MOD = 1e9 + 7;
int s[N], t[N];
int main()
{
int a, b, k;
cin >> a >> b >> k;
if(k == 0)
{
cout << "Yes" << endl;
for(int i = 0; i < b; i++)
{
cout << 1;
}
for(int i = 0; i < a; i++)
{
cout << 0;
}
cout << endl;
for(int i = 0; i < b; i++)
{
cout << 1;
}
for(int i = 0; i < a; i++)
{
cout << 0;
}
cout << endl;
return 0;
}
else if(k > a + b - 2 || a == 0 || b == 1)
{
cout << "No" << endl;
return 0;
}
if(k == a + b - 2)
{
cout << "Yes" << endl;
for(int i = 0; i < b; i++)
{
cout << 1;
}
for(int i = 0; i < a; i++)
{
cout << 0;
}
cout << endl;
cout << 10;
for(int i = 1; i < b - 1; i++)
{
cout << 1;
}
for(int i = 1; i < a; i++)
{
cout << 0;
}
cout << 1;
cout << endl;
return 0;
}
cout << "Yes" << endl;
s[k] = 1;
t[k] = 0;
t[0] = 1;
int cnt0 = 1, cnt1 = 1;
for(int i = 1; i < a + b; i++)
{
if(i == k)
continue;
if(cnt0 < a)
{
cnt0++;
s[i] = t[i] = 0;
}
else
{
s[i] = t[i] = 1;
}
}
for(int i = a + b - 1; i >= 0; i--)
{
cout << s[i];
}
cout << endl;
for(int i = a + b - 1; i >= 0; i--)
{
cout << t[i];
}
cout << endl;
return 0;
}
总结
- B题第一次WA是简单错误，但是一WA就脑子空白，想不出错在哪，最后推翻重写。赛后重新看第一次的代码，一下就发现了；
- C题开始读题错误，导致错了很久，其实开始的方法是可行的（赛后也得到了验证），但是一直没有怀疑自己读错题，一直在检查代码，拖了更久才过；
- D题赛场上少判了一个b=1，但是当时有点坚持不住了，去看standing、看预估分去了，最后在比赛结束前5秒看出来错误了，但是根本来不及交上去了……
- 总而言之，就是心态很存在问题叭。还是要慢慢来，不害怕掉分！
多多包涵，共同进步