Codeforces Round 1012 (Div. 2)（ABCD）

每个餐桌由四个单元格定义：(3x+1,3y+1), (3x+1,3y+2), (3x+2,3y+1), (3x+2,3y+2)其中 x,y 为非负整数。如果有多张桌子的距离相同，他们会选择 x 最小的单元格，如果仍然相同，他们会选择 y 最小的单元格。与有关比较的容器有map，set，priority_queue，sort的数组。当ti为1时，优先从小根堆取点，同时要考虑当前桌子比走过剩余的角距离

椰奶好喝

1193人浏览 · 2025-03-23 22:56:44

椰奶好喝 · 2025-03-23 22:56:44 发布

A. Treasure Hunt

翻译：

小 B 和他的朋友小 K 找到了一张藏宝图，现在他们只需要挖出埋在地下 a.5 米深处的宝藏。

他们轮流挖。第一天，小 B 挖；第二天，小 K 挖。小 B 每天正好挖 x 米，而小 K 挖了 y 米。他们开始好奇谁会先挖出宝藏，也就是谁一天内挖的总深度会超过 a.5 米。

但他们都忙着挖土，所以帮帮他们，告诉他们谁会挖到宝藏！

思路：

把B,K捆绑为一组，求到a.5跟前要几组，再特判加B与加K的情况。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;

void solve(){
    int x,y,a;
    cin>>x>>y>>a;
    int t = a/(x+y);
    if ((x+y)*t+x>a){
        cout<<"NO"<<endl;
    }else{
        cout<<"YES"<<endl;
    }
}

int main(){
    // 关闭输入输出流同步
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    int t;
    cin>>t;
    while (t--){
        solve();
    }
    return 0;
}

B. Pushing Balls

翻译：

埃克雷德有一个 n×m 网格，原本是空的，他已经在网格中推入了几个球（可能是零）。

        每次，他可以从网格中某一行的最左边缘或某一列的最上边缘将一个球推入网格。

        当一个球向一个位置移动时：

如果该位置上原本没有球，则进入的球将停止并占据该位置。
如果该位置上已经有一个球，则进入的球将停止并占据该位置，而原来的球将继续沿同一方向移动到下一个位置。

        请注意，如果某一行或某一列已满（即该行或该列中的所有位置都有球），他就不能将球推到该行或该列中。

        给定网格中每个位置是否有球的最终状态，您需要确定埃克雷德是否有可能推动小球达到最终状态。

思路：

每个有球的位置，向上或向左必定应能到边界（无球处不能走）。否则图必定不成立。

横着扫一遍，竖着扫一遍，标记所有能直直的到边界的点。判断有无未标记的有球点。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;

void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<char>> grid(n,vector<char>(m));
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    // 行
    for (int i=0;i<n;i++){
        if (grid[i][0]!='0'){
            for (int j=0;j<m;j++){
                if (grid[i][j]!='0'){
                    grid[i][j] = '2';
                }else{
                    break;
                }
            }
        }
    }
    // 列
    for (int j=0;j<m;j++){
        if (grid[0][j]!='0'){
            for (int i=0;i<n;i++){
                if (grid[i][j]!='0'){
                    grid[i][j] = '2';
                }else{
                    break;
                }
            }
        }
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (grid[i][j]=='1'){
                cout<<"NO"<<endl;
                return;
            }
        }
    }
    cout<<"YES"<<endl;
}

int main(){
    // 关闭输入输出流同步
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    int t;
    cin>>t;
    while (t--){
        solve();
    }
    return 0;
}

C. Dining Hall

翻译：

        在这个大王国里，有一个无限大的餐厅。

        它可以表示为一组单元格 (x,y)，其中 x,y 是自然数。大厅里还有无限多的餐桌。每个餐桌由四个单元格定义：(3x+1,3y+1), (3x+1,3y+2), (3x+2,3y+1), (3x+2,3y+2)其中 x,y 为非负整数。所有不属于任何表格的单元格都被视为走廊。

        任何客人都只能在走廊中移动，而且他们只能从边上过渡到相邻的单元格，每次过渡花费的时间相同。注意，他们只能在最后一次移动时坐在一张桌子旁，而且必须坐在一张桌子旁。

        在这个王国的晚宴上，有 n 位客人到来，每位客人都有一个特征 ti，可以是 0 也可以是 1。他们依次进入大厅，从单元格（0,0）开始走向一张桌子。如果第 i
-如果第 i 位客人的特征值 ti=1，他们就会坐在离他们最近、还有空位的桌子上；如果 ti=0，他们就会坐在离他们最近、没有空位的桌子上，尽管将来可能会有其他人加入。如果有多张桌子的距离相同，他们会选择 x 最小的单元格，如果仍然相同，他们会选择 y 最小的单元格。

单元格到表的距离定义为到该表上最近的未占用单元格的距离。两个单元格之间的距离计算为移动到共用一条边的相邻单元格的次数。请注意，除了最后一次移动（这次移动会将您移到表格上的最后一个单元格），不允许穿过属于表格的单元格。

为了更好地理解这些条件，您可以参考注释中的图片。

您没有时间计算每个人的座位，所以请告诉每位来宾他们将坐在哪一格。

思路：

下图为每个桌子（x,y）四个角的距离，可看出要找桌子的顺序和一个桌子内四个角的优先级：

该题要考虑比较三个参数距离，x，y。与有关比较的容器有map，set，priority_queue，sort的数组。这里使用priority_queue小根堆。从边角开始，按顺序以桌子为单位走。

当ti为1时，优先从小根堆取点，同时要考虑当前桌子比走过剩余的角距离小的可能，这点由上图也可看出。

其他情况，把桌子推一位并把除左下角外的其他角放入待判断的小根堆。

实现：

#include<bits/stdc++.h>
using namespace std;
int n;
void solve(){
    cin>>n;
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
    int x = 1,y = 1,dis = 2;
    vector<array<int,2>> ans(n);
    for (int id,i=0;i<n;i++){
        cin>>id;
        // pq.top()[0]<dis保证上一层没有更小的
        if (id && !pq.empty() && pq.top()[0]<dis){
            auto [_,xx,yy] = pq.top();
            pq.pop();
            ans[i] = {xx,yy};
        }else{
            ans[i] = {x,y};
            // 这块桌子的所有
            pq.push({x+y+1,x+1,y});
            pq.push({x+y+1,x,y+1});
            pq.push({x+y+4,x+1,y+1});
            // 斜着遍历
            if (y==1){
                swap(x,y);
                y+=3;
            }else{
                x+=3;
                y-=3;
            }
            dis = x+y;
        }
    }
    for (auto [x,y]:ans){
        cout<<x<<" "<<y<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while (t--) solve();
}

D. Simple Permutation

翻译：

定一个整数 n，构建一个长度为 n 的排列 $p_1,p_2,...,p_n$ 长度为 n 的排列组合，该排列组合满足以下性质：

对于 1≤i≤n，定义 $c_i = \lceil \frac{p_1+p_2+,,,+p_i}{i} \rceil$ ，那么在 $c_1,c_2,...,c_n$ 中中至少有 ⌊n3⌋-1 个质数。

思路：

贝特朗假设：对任一实数 x≥1，在 x 及 2x 之间必有一素数。

在此基础上找到n/3以上的素数p，以p，p-1，p+1，p-2，p+2，。。。的形式构造答案。

实现：

#include<bits/stdc++.h>
using namespace std;
const int MX = 1e5+10;
int n;
vector<int> prime,a(MX,0);
void solve(){
    cin>>n;
    if (n==2){
        cout<<"2 1\n";
        return;
    }
    int p = *lower_bound(prime.begin(),prime.end(),n/3);
    cout<<p;
    int l = p-1,r = p+1;
    for (;l>=1 && r<=n;l--,r++){
        cout<<" "<<l<<" "<<r;
    }
    for (int i=1;i<=l;i++){
        cout<<" "<<i;
    }
    for (int i=n;i>=r;i--){
        cout<<" "<<i;
    }
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 求质数
    for (int i=2;i<MX;i++){
        if (!a[i]){
            prime.push_back(i);
            for (int j=2*i;j<MX;j+=i){
                a[j] = 1;
            }
        }
    }
    int t;
    cin>>t;
    while (t--) solve();
}