最近网课也开始了，牛客上一堆比赛题目也没补，所以就D题后面的也懒得补了
A.Three String
水题
#include <cstdio>
#include <cstring>
using namespace std;
char a[], b[], c[];
int main() {
int t;
scanf("%d", &t);
while (t--) {
memset(a, , sizeof(a));
memset(b, , sizeof(b));
memset(c, , sizeof(c));
scanf("%s%s%s", a, b, c);
int len = strlen(a), ans = ;
for (int i = ; i < len; i++) {
if (c[i] == a[i] || c[i] == b[i])
continue;
ans = -;
break;
}
if (ans == -)
puts("NO");
else
puts("YES");
}
return ;
}
B.Motarack's Birthday
其实也挺水的...但是我场上脑子有点问题，第一反应是三分（？）因为它应该是只有一个极值的函数，可以用三分来做
这是我的代码，写的很复杂而且很奇怪
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5 + ;
int a[N], n;
inline int val(int b) {
int maxn = ;
for (int i = ; i <= n; i++) {
if (a[i - ] == - && a[i] == -)
continue;
if (a[i - ] == -)
maxn = max(maxn, (int)abs(b - a[i]));
else if (a[i] == -)
maxn = max(maxn, (int)abs(b - a[i - ]));
else
maxn = max(maxn, (int)abs(a[i] - a[i - ]));
}
return maxn;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
int l = , r = 1e9;
while (r - l >= ) {
int l1 = l + (r - l) / ;
int r1 = r - (r - l) / ;
int a = val(l1), b = val(r1);
if (a <= b)
r = r1;
else
l = l1;
}
int a, b = 1e9 + ;
if (l != r) {
for (int i = l; i <= r; i++) {
int z = val(i);
if (z < b)
b = z, a = i;
}
}
else
a = l, b = val(l);
printf("%d %d\n", b, a);
}
return ;
}
然后题解肯定不是这样的啦，最后答案的范围肯定在和-1相邻的数字之间，若这些数字中最大的是maxn， 最小的是minn，则差的最大就是max(abs(maxn - val), abs(minn - val))，所以val等于（maxn + minn）/2就行了，代码很简单，我也懒得写了。
C.Ayoub's function
场上想了很久（还是太菜了），后来突然灵机一动，想到可以用总数减去只有0的个数，然后就可以发现000...000的序列越短越好，然后就可以直接O(1)出来了。
#include <cstdio>
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--) {
long long n, m;
scanf("%lld %lld", &n, &m);
long long ans = 1ll * n * ( + n) / ;
if ((n - m) % (m + ) == ) {
long long b = (n - m) / (m + );
ans -= 1ll * (m + ) * b * (b + ) / ;
}
else {
long long b = (n - m) / (m + );
long long c = (n - m) % (m + );
ans -= (m + - c) * b * (b + ) / ;
ans -= c * (b + ) * (b + ) / ;
}
printf("%lld\n", ans);
}
return ;
}
D.Time to Run
很容易发现它是欧拉通路，因为它没有奇度顶点，然后想一个构造的方法就行了，然后我就随便想了一个，结果有一堆细节上的问题QAQ
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
int r = * m * n - * n - * m;
if (k > r) {
puts("NO");
return ;
}
puts("YES");
n--; m--;
//RDU
if (k == )
return ;
if (n == ) { //这种情况要特殊考虑
if (k <= m) {
puts("");
printf("%d R\n", k);
}
else {
puts("");
printf("%d R\n%d L", m, k - m);
}
return ;
}
if (m == ) { //同上
if (k <= n)
printf("1\n%d D\n", k);
else
printf("2\n%d D\n%d U\n", n, k - n);
return ;
}
int kk = k;
int t = , cnt = ;
while (k > ) { //第一遍先找要多少次操作
if (t == (n + )) {
if (k <= m) {
cnt++;
break;
}
else {
cnt++;
k -= m;
}
if (k <= m) {
cnt++;
break;
}
else {
cnt++;
k -= m;
}
if (k <= n) {
cnt++;
break;
}
else {
cnt++;
k -= m;
}
break;
}
if (k <= m * ) {
if (k / > )
cnt++;
int y = k % ;
if (y == )
cnt++;
else if (y == )
cnt++;
break;
}
else {
cnt++;
k -= m * ;
}
if (k <= m) {
cnt++;
break;
}
else {
cnt++;
k -= m;
}
cnt++;
k--;
t++;
}
t = ;
k = kk;
printf("%d\n", cnt);
while (k > ) {
if (t == (n + )) { //这个要注意，最后一行就要往回走
if (k <= m) {
printf("%d R\n", k);
break;
}
else {
printf("%d R\n", m);
k -= m;
}
if (k <= m) {
printf("%d L\n", k);
break;
}
else {
printf("%d L\n", m);
k -= m;
}
if (k <= n) {
printf("%d U\n", k);
break;
}
else {
printf("%d U\n", m);
k -= m;
}
break;
}
if (k <= m * ) {
if (k / > )
printf("%d RDU\n", k / );
int y = k % ;
if (y == )
puts("1 R");
else if (y == )
puts("1 RD");
break;
}
else {
printf("%d RDU\n", m);
k -= m * ;
}
if (k <= m) {
printf("%d L\n", k);
break;
}
else {
printf("%d L\n", m);
k -= m;
}
printf("1 D\n");
k--;
t++;
}
return ;
}