今天难得是在白天比赛.过三题,一边写着看到都已经过了system test了,D题还是WA在最后的pretest了,之后再补上.
A
手快就行,写得多垃圾能AC就好.记得long long,再记得把中间的临时变量也开long long.
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
long long p, a, b, c;
void solve(){
cin >> p >> a >> b >> c;
long long na = a, nb = b, nc = c;
na += ((p - a) / a) * a;
nb += ((p - b) / b) * b;
nc += ((p - c) / c) * c;
while(na < p) na += a;
while(nb < p) nb += b;
while(nc < p) nc += c;
cout << min({na, nb, nc}) - p << endl;
}
int main(){
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
A
B
花里胡哨地绕了半天,其实这个在暗示你进制的东西:
其实等价于字典序大小.
比如这个数据:
4 2 5 3 6 1
不停地选一个位置截断到末尾,并把接下来的序列顺序尾首拼接,要让得到的序列字典序最大,那很明显了,不停从最大值处截取,依次得到子序列:
6 1 5 3 4 2
顺序连接起来即为答案.
复杂度要做点处理,代码有点乱了.
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, p[100010], pos[100010];
bool used[100010], numused[100010];
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", p + i);
pos[p[i]] = i;
}
memset(used, 0, sizeof(used));
memset(numused, 0, sizeof(numused));
int cur = n;
used[n + 1] = true;
while (cur >= 1) {
if (numused[cur]) {
cur--;
continue;
}
for (int i = pos[cur]; !used[i]; i++) {
if (p[i] == cur) {
for (int j = i; !used[j]; j++) {
used[j] = true;
numused[p[j]] = true;
printf("%d ", p[j]);
}
}
}
cur--;
}
puts("");
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}
B
C
一开始想到的是把t的每一个字符的最早出现位置和最晚出现位置都记录下来,然后扫描一遍 t 并检查相邻字符中后者最晚出现位置与前者最早出现位置之差,最大值为解,但是很显然直接这么做是不能保证这些位置是满足字符串是beautiful的条件的.
(插播,system test结束了,D竟然FST了差不多四分之一成为百人题)
所以,先用双指针从左到右扫描 s 和 t ,只有匹配时记录这个字符的位置,这时记录的是满足beautiful的最早出现位置.
然后同样地,从右到左再来一遍,现在记录的就是满足beautiful的最晚出现位置.
现在就可以检查相邻字符的最大差了.
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
typedef pair<int, int> P;
string s1, s2;
int l1, l2;
P pos[200010];
int main(){
cin >> l1 >> l2 >> s1 >> s2;
int p = 0;
for(int i = 0; p < s2.size() && i < s1.size(); i++)
if(s1[i] == s2[p]){
pos[p].first = i;
p++;
}
p--;
for(int i = s1.size() - 1; p >= 0 && i >= 0 ; i--)
if(s1[i] == s2[p]){
pos[p].second = i;
p--;
}
int ans = 0;
for(int i = 0; i < s2.size() - 1; i++)
ans = max(ans, pos[i + 1].second - pos[i].first);
// for(int i = 0; i < s2.size(); i++){printf("%d %d\n", pos[i].first, pos[i].second);}
cout << ans << endl;
return 0;
}
C
D
构造题,从剩下一个小时十分钟到结束都在看,也没调出来.
已经可以看到测试点了,看了最后一个pretest才发现我末尾处的处理完全就是错的(我还一直在想边界情况),那前17个测试点是不是太水了?
现有的思路是正确的:
设z=x-y,则x=y+z.
x,y都有a个0和b个1,并且y加上一个二进制数后变为x,仍然是a个0和b个1.
这意味着z的某一位加到y的对应位上,可以恰好使得y此位进位变为0,且高一位因此从0变为1.
所以想到把y假定为10...01...1,省略号及两端依次表示1个0和b-1个1,比如假定y为:
1000111
现在尝试在某一位上加一,使得结果的0和1个数不变,显然只有一个位置:
1000111 + 100 ------------ 1001011
如果z=100,那么x就是1001011,此时k=1,有解.
如果在原y基础上的另一位上额外再加一,仍不改变0和1的个数,有两个位置可选,比如选择靠前的位置:
1000111 + 1100 ------------ 1010011
会发现相对原y把"1"左移了两位,此时z=1100,x=1010011,k=2,有解.
你可以把这个"1"继续左移直到其左边没有0,此后你可以把下一个"1"通过这样的操作继续左移直到其左侧没有0,要注意的是z的每一位只能用一次,用后那一位就已经是1,不能再加了.观察之后会发现有解的条件是a + b - 2 >= k.
更要注意的是,决定z的某一位是否为1需要按照顺序来,比如想把100111加到111100,随着k的递增,变为1的位需要按照如下顺序:
k=1: z=100
k=2: z=1100
k=3: z=1110
k=4: z=1111
这遵循着把"1"不断地"搬运"到最左侧的过程.如果无序地处理会导致意外地多次进位改变0和1的数量.(我就是没考虑顺序WA的)
现在考虑边界情况,有两种,a=0和b=1,两种情况下都是只有k=0时才会有解,很容易处理.
由于位数很多,我开了个数组手动模拟二进制.
已经AC.
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
long long a, b, k;
int x[200010], y[200010];
bool z[200010];
int main() {
cin >> a >> b >> k;
memset(z, 0, sizeof(z));
if (b <= 1) {
if (k) {
cout << "No" << endl;
return 0;
} else
cout << "Yes" << endl;
} else if (!a) {
if (k) {
cout << "No" << endl;
return 0;
} else
cout << "Yes" << endl;
} else if (a + b - 2 >= k)
cout << "Yes" << endl;
else {
cout << "No" << endl;
return 0;
}
x[a + b] = y[a + b] = 1;
for (int i = 1; i <= a + b - 1; i++) {
if (i <= b - 1)
y[i] = 1;
else
y[i] = 0;
x[i] = y[i];
}
int t = k, hd = b - 1, ed = a + b - 2;
while(t){
for(int i = hd; i <= ed && t; t--, i++)
z[i] = true;
hd--;
ed = hd;
}
for (int i = 1; i <= a + b; i++) {
if (x[i] == 2) x[i] = 0, x[i + 1]++;
if(z[i]) x[i]++;
if (x[i] == 2) x[i] = 0, x[i + 1]++;
}
for (int i = a + b; i >= 1; i--) cout << x[i];
cout << endl;
for (int i = a + b; i >= 1; i--) cout << y[i];
cout << endl;
return 0;
}
D