@Dmaxiya 2026-04-27T07:36:47.000000Z 字数 7627 阅读 2

AIM Tech Round 5 (Div. 1 + Div. 2)

Codeforces

Contests 链接：AIM Tech Round 5 (Div. 1 + Div. 2)
过题数：3
排名：750/8224

A. Find Square

题意

在一个 $n\times m$ 的网格中，最初每个格子的颜色都是白色的，其中有一个长和宽都为奇数的长方形，长方形区域内的所有格子都是黑色的，问这个长方形的中心的坐标。

输入

第一行为两个整数 $n,m~(1\leq n,m\leq115)$ ，接下去 $n$ 行每行一个长度为 $m$ 的字符串，字符串只包含 W 和 B 两种字符，W 表示白色方格，B 表示黑色方格。

输出

输出长方形的中心格坐标。

样例

输入
5 6 `WWBBBW` `WWBBBW` `WWBBBW` `WWWWWW` `WWWWWW`
输出
2 4

输入
3 3 `WWW` `BWW` `WWW`
输出
2 1

题解

每遇到一个 B 字符，都取横坐标与纵坐标的 $\min$ 和 $\max$ ，就能得到左上角与右下角的坐标，取中点，就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200 + 100;
int n, m, maxx, maxy, minx, miny;
char str[maxn][maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        minx = miny = INT_MAX;
        maxx = maxy = -1;
        for(int i = 1; i <= n; ++i) {
            scanf("%s", str[i] + 1);
            for(int j = 1; j <= m; ++j) {
                if(str[i][j] == 'B') {
                    minx = min(minx, i);
                    miny = min(miny, j);
                    maxx = max(maxx, i);
                    maxy = max(maxy, j);
                }
            }
        }
        printf("%d %d\n", (maxx + minx) / 2, (maxy + miny) / 2);
    }
    return 0;
}

B. Unnatural Conditions

题意

定义函数 $s(x)$ 为数字 $x$ 的每个十进制位相加的和，给定两个整数 $n,m$ ，构造两个整数 $a,b$ ，使得：

$s(a)\geq n$

$s(b)\geq n$

$s(a+b)\leq m$

输入

输入包含两个整数 $n,m~(1\leq n,m\leq1129)$ 。

输出

输出两行，每行一个整数，分别表示整数 $a.b$ ，要求两个整数的长度都不超过 $2230$ ，两个整数都不能有前导零。

样例

输入
6 5
输出
6 7
提示
$s(6)=6\geq6,s(7)=7\geq6,s(6+7)=s(13)=4\leq5$ 。

输入
8 16
输出
35 53

题解

由于 $89+11=100$ ，因此由 $x$ 个 $8$ 加一个 $9$ 与由 $x+1$ 个 $1$ 组成的数字相加，一定能得到 $10^{x+1}$ ，因此只要令 $x=1128$ ，就能满足所有的 $n$ 和 $m$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
int n, m;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        for(int i = 0; i < 1128; ++i) {
            printf("8");
        }
        printf("9\n");
        for(int i = 0; i < 1129; ++i) {
            printf("1");
        }
        printf("\n");
    }
    return 0;
}

C. Rectangles

题意

给定 $n$ 个矩形，其中一定有一个点，存在于至少 $n-1$ 个矩形的内部或者边上，求这个点的坐标。

输入

第一行为一个整数 $n~(2\leq n\leq 132674)$ ，接下去 $n$ 行每行四个整数 $x_1,y_1,x_2,y_2~(10^{-9}\leq x_1<x_2\leq10^9,10^{-9}\leq y_1<y_2\leq10^9)$ ，表示每个矩形的左下角与右上角坐标。

输出

输出两个整数 $x$ 和 $y$ ，表示存在于至少 $n-1$ 个矩形内的点的坐标。

样例

输入
3 0 0 1 1 1 1 2 2 3 0 4 1
输出
1 1

输入
3 0 0 1 1 0 1 1 2 1 0 2 1
输出
1 1
提示
第一、二组数据所示矩形如图，其中被高亮的点是可能的答案：

输入
4 0 0 5 5 0 0 4 4 1 1 4 4 1 1 4 4
输出
1 1

输入
5 0 0 10 8 1 2 6 7 2 3 5 6 3 4 4 5 8 1 9 2
输出
3 4
提示
第三、四组数据所示矩形如图：

题解

把数组随机排列几次，每次都取矩形的交，每当与某个矩形取交集为空集的时候，就跳过这个矩形，并计数 $+1$ ，如果计数值小于等于 $1$ ，则最后得到的矩形交一定是 $n-1$ 个矩形的交。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <algorithm>
#include <ctime>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
struct Node {
    int x1, y1, x2, y2;
    bool judge() {
        return x1 <= x2 && y1 <= y2;
    }
};
Node operator^(const Node &a, const Node &b) {
    Node tmp;
    tmp.x1 = max(a.x1, b.x1);
    tmp.y1 = max(a.y1, b.y1);
    tmp.x2 = min(a.x2, b.x2);
    tmp.y2 = min(a.y2, b.y2);
    return tmp;
}
int n;
Node ans;
Node node[maxn];
void Rand() {
    for(int i = 0; i < n; ++i) {
        swap(node[i], node[rand() % n]);
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    srand((unsigned)time(NULL));
    while(scanf("%d", &n) != EOF) {
        for(int i = 0; i < n; ++i) {
            scanf("%d%d%d%d", &node[i].x1, &node[i].y1, &node[i].x2, &node[i].y2);
        }
        while(true) {
            int cnt = 0;
            Node tmp = node[0];
            Node ttmp;
            for(int i = 1; i < n; ++i) {
                ttmp = tmp ^ node[i];
                if(!ttmp.judge()) {
                    ++cnt;
                    continue;
                }
                tmp = ttmp;
            }
            if(cnt <= 1) {
                ans = tmp;
                break;
            }
            Rand();
        }
        printf("%d %d\n", ans.x1, ans.y1);
    }
    return 0;
}

D. Array Restoration

题意

有一个长度为 $n$ 的序列，可以对这 $n$ 个序列进行 $q$ 次操作，第 $i$ 次操作选择一个区间 $[l_i,r_i]$ ，将这个区间内的所有数字用 $i$ 替换，每个位置上的数字至少被一个区间覆盖，最后将这个序列中的某几个数字改为 $0$ 。现在题目给出最终的序列，问是否存在合法的 $q$ 次操作，能够得到给出的序列，求 $q$ 次操作后（将序列某些数字变为 $0$ 之前）的序列。

输入

第一行为两个整数 $n,q~(1\leq n,q\leq2\times10^5)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(0\leq a_i\leq q)$ 。

输出

如果给出的序列无法从上面的操作中得到，输出 $NO$ ，否则在第一行输出 $YES$ ，第二行输出 $q$ 次操作之后的 $n$ 个整数。

样例

输入
4 3 1 0 2 3
输出
YES 1 2 2 3
提示
将 $0$ 用 $1$ 替换也是合法的，但是用 $3$ 替换是不合法的。

输入
3 10 10 10 10
输出
YES 10 10 10
提示
不论前 $q-1$ 次操作是怎么样，第 $q$ 次操作是选择区间 $[1,3]$ 即可。

输入
5 6 6 5 6 2 2
输出
NO
提示
由于第 $5$ 次操作必须在第 $6$ 次操作之前，所以不可能先将区间 $[1,3]$ 更新为 $6$ 之后再将区间 $[2,2]$ 更新为 $5$ 。

输入
3 5 0 0 0
输出
YES 5 4 2
提示
有许多种操作对于 $0~0~0$ 而言都是合法的。

题解

由于数字大的一定比数字小的后更新，所以每个数字出现的左端点与右端点之间的数字不能小于它自身，可以用线段树维护最小值，从 $q$ 到 $1$ 询问第 $i$ 个数字出现的左端点 $L_i$ 与右端点 $R_i$ ，如果在查询区间最小值时遇到 $0$ 的情况，就向下将 $0$ 更新为当前数字再进行查询。记得首先查询序列内是否有数字 $q$ ，如果没有数字 $q$ 就将其中任意一个 $0$ 修改为 $q$ ，如果无法修改则直接输出 $NO$ 。所有询问与更新结束后，如果序列中仍含有 $0$ ，就将所有 $0$ 赋值为 $1$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, q;
int num[maxn], L[maxn], R[maxn];
int Min[maxn << 2];
void push_up(int rt) {
    Min[rt] = min(Min[rt << 1], Min[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
    if(l == r) {
        Min[rt] = num[l];
        return ;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    push_up(rt);
}
void update(int x, int l, int r, int rt) {
    if(l == r) {
        Min[rt] = x;
        num[l] = x;
        return ;
    }
    int m = (l + r) >> 1;
    if(Min[rt << 1] == 0) {
        update(x, l, m, rt << 1);
    }
    if(Min[rt << 1 | 1] == 0) {
        update(x, m + 1, r, rt << 1 | 1);
    }
    push_up(rt);
}
int query(int L, int R, int x, int l, int r, int rt) {
    if(L <= l && r <= R) {
        if(Min[rt] == 0) {
            update(x, l, r, rt);
        }
        return Min[rt];
    }
    int m = (l + r) >> 1;
    int ret = INT_MAX;
    if(L <= m) {
        ret = min(ret, query(L, R, x, l, m, rt << 1));
    }
    if(m < R) {
        ret = min(ret, query(L, R, x, m + 1, r, rt << 1 | 1));
    }
    push_up(rt);
    return ret;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("10.out", "w", stdout);
    #endif // Dmaxiya
    while(scanf("%d%d", &n, &q) != EOF) {
        for(int i = 0; i <= q; ++i) {
            L[i] = n + 1;
            R[i] = 0;
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
            L[num[i]] = min(L[num[i]], i);
            R[num[i]] = max(R[num[i]], i);
        }
        if(L[q] > R[q]) {
            if(L[0] != n + 1) {
                num[L[0]] = q;
                L[q] = R[q] = L[0];
            } else {
                printf("NO\n");
                continue;
            }
        }
        build(1, n, 1);
        bool flag = true;
        for(int i = q; i >= 1; --i) {
            if(L[i] > R[i]) {
                continue;
            }
            if(query(L[i], R[i], i, 1, n, 1) < i) {
                flag = false;
                break;
            }
        }
        if(!flag) {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        for(int i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            if(num[i] == 0) {
                printf("1");
            } else {
                printf("%d", num[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

E. Down or Right

题意

这是一道交互题，有一个 $n\times n$ 的网格，其中有一些网格是可以行走的，而有一些是无法行走的，在可以行走的网格中，下一步只能往右或下两个方向移动到下一格可以行走的网格中，但是我们并不知道这个网格哪些格子是可以行走的那些无法行走。 $Bob$ 要从 $(1,1)$ 点走到 $(n,n)$ 点，每次可以询问他从 $(x_1,y_1)$ 点是否能到达 $(x_2,y_2)$ 点， $Bob$ 将会回答 $YES$ 或者 $NO$ ，且每次询问 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的哈密顿距离不能小于 $n-1$ ，最终输出从 $(1,1)$ 到 $(n,n)$ 的合法行走方案。询问的次数不能超过 $4n$ 。

输入

第一次输入为一个整数 $n~(2\leq n\leq500)$ ，后面的输入为 $YES$ 或者 $NO$ ，取决于输出的询问。

输出

如果为询问，则按照 $?~x_1~y_1~x_2~y_2$ 的格式询问，如果已经可以求得路径，则第一个字符为 !，空一格之后，输出 $2n-2$ 个字符，第 $i$ 个字符为 D 表示第 $i$ 步需要往下走，为 R 表示需要往右走。

样例

输入
4 YES NO YES YES
输出
? 1 1 4 4 ? 1 2 4 3 ? 4 1 4 4 ? 1 4 4 4 ! RDRRDD
提示
网格中的可行走方格与不可行走方格如下图：

题解

如果“左上的点”表示与点 $(1,1)$ 的哈密顿距离不大于 $n-1$ 的所有点，“右下的点”表示与点 $(n,n)$ 的哈密顿距离不大于 $n-1$ 的点，则先从 $(1,1)$ 开始询问左上的点是否能到达 $(n,n)$ ，能往右就尽量往右走，再从 $(n,n)$ 开始询问 $(1,1)$ 能否到达右下的点，能往上就尽量往上，最后这两条路径一定会重合于某一点 $(x,y)$ ，其中 $x-1+y-1=n-x+n-y=n-1$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 20000 + 100;
int n, cntl, cntr;
char ret[10];
char ansl[maxn], ansr[maxn];
int dis(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
    #ifdef Dmaxiya
//    freopen("test.txt", "r", stdin);
//    freopen("10.out", "w", stdout);
    #endif // Dmaxiya
    scanf("%d", &n);
    int x = 1, y = 1;
    while(dis(1, 1, x, y + 1) <= n - 1) {
        int xx = x;
        int yy = y + 1;
        printf("? %d %d %d %d\n", xx, yy, n, n);
        fflush(stdout);
        scanf("%s", ret);
        if(ret[0] == 'Y') {
            ansl[cntl++] = 'R';
            ++y;
        } else {
            ansl[cntl++] = 'D';
            ++x;
        }
    }
    x = y = n;
    while(dis(x - 1, y, n, n) <= n - 1) {
        int xx = x - 1;
        int yy = y;
        printf("? %d %d %d %d\n", 1, 1, xx, yy);
        fflush(stdout);
        scanf("%s", ret);
        if(ret[0] == 'Y') {
            ansr[cntr++] = 'D';
            --x;
        } else {
            ansr[cntr++] = 'R';
            --y;
        }
    }
    ansl[cntl] = '\0';
    printf("! %s", ansl);
    for(int i = cntr - 1; i >= 0; --i) {
        printf("%c", ansr[i]);
    }
    printf("\n");
    fflush(stdout);
    return 0;
}

AIM Tech Round 5 (Div. 1 + Div. 2)

A. Find Square

题意

输入

输出

样例

题解

过题代码

B. Unnatural Conditions

题意

输入

输出

样例

题解

过题代码

C. Rectangles

题意

输入

输出

样例

题解

过题代码

D. Array Restoration

题意

输入

输出

样例

题解

过题代码

E. Down or Right

题意

输入

输出

样例

题解

过题代码

内容目录

选择主题