Codeforces Round 929 (Div. 3)

好吧，是这样的，这次手速场被爆锤，属于是自己太菜了。

E 题因为自己过于 fvv 卡了又卡，属于是炒鸡 fvv 了。

星空喵永远滴神喵！

Dashboard - Codeforces Round 929 (Div. 3) - Codeforces

非最终版本

等待完善。

A. Turtle Puzzle: Rearrange and Negate

Problem - A - Codeforces

嗯，不看翻译就读不懂题是这样的。

题目大意

给一个有 \(n\) 个元素的数组 \(a\) ，你可以依次进行以下俩次操作。

• 对数组任意方式重排，或不进行此操作。
• 选定区间 \([l,r]\) ，并将里面的所有数改为相反数，或不进行此操作。

求进行操作后的数组元素和。

多组数据，\(1\le t\le 1000,1\le n\le 50,-100\le a_i \le 100\)。

思路

很明显可以从小到大排序，然后对负数的区间进行操作。

所求答案即为所有数的绝对值。

代码

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

void solve()
{
    int n;
    ll ans=0,a;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        ans+=abs(a);
    }
    cout<<ans<<endl;
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

B. Turtle Math: Fast Three Task

Problem - B - Codeforces

题目大意

给一个有 \(n\) 个元素的数组 \(a\) ，你可以进行以下俩种操作。

• 选定一个数组元素并删除。
• 选定一个数组元素，并让其值加 \(1\) 。

求操作后使得数组元素和能为 \(3\) 的最小需要的操作次数。

多组数据，\(1\le t\le 10^4,1\le n\le 10^5,1\le a_i \le 10^4,\sum n \le2 \times10^5\)。

思路

显然操作数的范围是 \([0,2]\) 。

• 数组元素和模 \(3\) 余 \(0\) 的情况，操作数为 \(0\)。

• 数组元素和模 \(3\) 余 \(1\) 的情况：

  • 若存在一个元素模 \(3\) 余 \(1\)，删去这个元素，操作数为 \(1\)。

  • 给任意两个元素加 \(1\)，操作数为 \(2\)。

• 数组元素和模 \(3\) 余 \(2\) 的情况，操作数为 \(0\)。

代码

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

void solve()
{
    int n,a[5]={0},ai;
    cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++){
        cin>>ai;
        sum+=ai;
        a[ai%3]++;
    }
    int ans=(3-sum%3)%3;
    if(a[sum%3])ans=min(1,ans);
    cout<<ans<<endl;
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

C. Turtle Fingers: Count the Values of k

Problem - C - Codeforces

读假了。

题目大意

给定三个正整数 \(a,b,l\)，找到自然数 \(k,x,y\) 使得 \(l=k\times a^x\times b^y\)。

求出满足情况的 \(k\) 的个数。

多组数据，\(1\le t\le 10^4,2\le a,b\le 100,1\le l \le 10^6\)。

思路

根据 \(l\) 的范围，可以粗略地计算出 \(x,y\) 的范围，粗略估计 \(x\le 20,y\le20\) 。

枚举所有的因数，复杂度 \(O(k\log^2l)\)。

代码

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

void solve()
{
    ll a,b,l;
    cin>>a>>b>>l;
    set<ll> v;
    ll pa=1,pb=1,ans;
    for(int i=0;i<=20;i++){
        pb=1;
        for(int j=0;j<=20;j++){
            ans=pa*pb;
            if(l%ans==0){
                v.insert(ans);
            }
            if(ans>l)break;
            pb*=b;
        }
        if(pa>l)break;
        pa*=a;
    }
    cout<<v.size()<<endl;
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

D. Turtle Tenacity: Continual Mods

Problem - D - Codeforces

题目大意

给一个有 \(n\) 个元素的数组 \(a\) ，你可以对数组进行重排。

使得数组满足 \(a_1 \bmod a_2 \bmod \dots \bmod a_n\)，按照从左到右的计算顺序。

多组数据，\(1\le t\le 10^4,2\le n\le 10^5,1\le a_i \le 10^9,\sum n\le2\times 10^5\)。

思路

考虑 \(a<b\) 时，\(a \bmod b=a\neq0\)；\(a>b\)时。\(a \bmod b=c<b\)。

将数组从小到大进行排序，得到最小值 \(a_1\) 和最小值的个数 \(k\)。

• \(k=1\) 时显然成立。

• \(k>1\) 时，考虑重新构造一个比 \(a_1\) 还要小的数，如果数组中非最小值的元素不全为最小值的倍数，显然是可以构造出来的。此时出现新的最小值，且最小值的个数为 \(1\)。

代码

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int a[100005];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1,[](int a,int b){return a<b;});
    int min=a[1],sum=n,pt=n+1;
    for(int i=1;i<=n;i++){
        if(a[i]!=min){
            sum=i-1;
            pt=i;
            break;
        }
    }
    if(sum==1){
        cout<<"YES"<<endl;
        return;
    }else{
        for(int i=pt;i<=n;i++){
            if(a[i]%min){
                cout<<"YES"<<endl;
                return;
            }
        }
    }
    cout<<"NO"<<endl;
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

E. Turtle vs. Rabbit Race: Optimal Trainings

Problem - E - Codeforces

玉玉了，又是写错二分又是看错数据范围的，debug一个小时，果然是菜狗行为。

题解的严谨度

该题题解有部分的乱搞，等我在改改......

题目大意

给定一个长度为 \(n\) 的序列 \(a_i\) 。

给定一个值 \(u\)，我们认为处理后的输出由 \(k\) 部分组成：

• 第 \(1\) 个部分的值为 \(u\)。
• 第 \(2\) 个部分的值为 \(u-1\)。
• 第 \(3\) 个部分的值为 \(u-2\)。
• \(\dots\)
• 第 \(k\) 个部分的值为 \(u+1-k\)，这个值可以为负。

在给定 \(u\) 的情况下，给定 \(l\) ，你需要找到 \(r\)，使得区间 \([l,r]\) 的和为 \(k\) 时，也就是 \(a_l+a_{l+1}+\dots+a_{r-1}+a_r=k\) 时，处理后的输出最大。

如果有多个 \(r\) 能取得最大值，选出最小的一个。

你需要回答 \(q\) 组询问，每组包含 \(l\) 和 \(u\) 。

多组数据，\(1\le t\le 10^4,1\le n\le 10^5,1\le a_i \le 10^4,1\le q\le 10^5,1\le l \le n,1\le u \le 10^9\)。

且满足 \(\sum n\le2\times 10^5,\sum q\le 2\times 10^5\) 。

思路

给定值 \(u\)，返回 \(\cfrac{k(2u+1-k)}{2}\) 。

对序列前缀和处理，找到使得返回值最大的 \(r\)，三分查找出最大值。

复杂度 \(O(n+q\log n)\)。

代码是乱搞的，其实二分查找第一个 \(sum_r-sum_{l-1}\) 大于等于 \(u\) 的答案，然后再左右判断一下返回值有没有最大的。

代码

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
ll a[100005];
ll sum[100005];
ll getl(ll l,ll r,ll u){
    ll lp=l,rp=r;
    while(lp<rp){
        ll mid=(lp+rp)/2;
        if(sum[mid]-sum[l-1]>=u+1){
            rp=mid;
        }else{
            lp=mid+1;
        }
    }
    return lp;
}
ll count(ll l,ll r,ll u){
    ll a=sum[r]-sum[l-1];
    ll anso=(u+u-a+1)*a/2;
    return anso;
}
void solve()
{
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    ll q,l;
    ll u,ansp;
    cin>>q;
    for(ll i=1;i<=q;i++){
        cin>>l>>u;
        ll ansl=getl(l,n,u);
        ansp=ansl;
        if(count(l,min(ansl+1,n),u)>count(l,ansp,u)){
            ansp=min(ansl+1,n);
        }
        if(count(l,max(ansl-1,l),u)>=count(l,ansp,u)){
            ansp=max(ansl-1,l);
        }
        cout<<ansp<<' ';
    }
    cout<<endl;
    return ;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    cin>>t;
    while(t--)solve();
    return 0;
}

F. Turtle Mission: Robot and the Earthquake

题目大意

给定一个有 \(n\) 行和 \(m\) 列的网格。行的编号为 \(0, 1, \ldots, n-1\) ，列的编号为 \(0, 1, \ldots, m-1\) 。在这个世界里，列是 循环 的 (即每列的顶部和底部单元格是相邻的) 。第 \(i\) 行和第 \(j\) 列 ( \(0 \le i < n, 0 \le j < m\) ) 上的单元格表示为 \((i,j)\) 。

在任何时刻，单元格 \((i,j)\) 的状态可以用整数 \(a _ {i,j}\) 来描述：

• 如果是 \(a _ {i,j} = 1\) ，则 \((i,j)\) 处有一块石头。
• 如果是 \(a _ {i,j} = 0\) ，则 \((i,j)\) 处什么都没有。

初始时刻为 \(0\) 时刻，每个石头以每单位时间 \(1\) 个单元的速度循环向上移动。从形式上看，对于某个区域 \(0 \le i < n, 0 \le j < m\) ，如果 \((i,j)\) 中包含一块石头，那么它将从 \((i, j)\) 移动到 \((i - 1, j)\) 。如果 \((i - 1, j)\) 中包含一块石头，那么它将从 \((i, j)\) 移动到 \((n - 1, j)\) ，或在 \(i=0\) 的情况下移动到移动到 \((n - 1, j)\) 。

机器人最初位于 \((0,0)\) 。它必须移动到 \((n-1,m-1)\) 处进行地震救援(移动到最右下方的单元格)。地震不会改变机器人的位置，只会改变世界中岩石的位置。

假设机器人的当前位置为 \((x,y)\) ( \(0 \le x < n, 0 \le y < m\) )，那么它可以在 \(0 \le x < n, 0 \le y < m\) 中移动。它可以执行以下操作：

• 循环向上移动一格，即使用 \(1\) 单位时间从 \((x,y)\) 移动到 \(((x+n-1) \bmod n, y)\) 。
• 向下循环移动一个单元格，即以 \(1\) 为时间单位从 \((x,y)\) 移动到 \(((x+1) \bmod n, y)\) 。
• 向右移动一格，即使用 \(1\) 个时间单位从 \((x,y)\) 到 \((x, y+1)\) 。(只有在 \(y < m-1\) 时，机器人才能执行此操作)。

注意，机器人不能使用操作向左移动，也不能停留在某一位置。

不幸的是，机器人在与石头碰撞后会爆炸。因此，当机器人位于 \((x,y)\) 处，而 \(((x+1) \bmod n, y)\) 或 \(((x+2) \bmod n, y)\) 处有一块岩石时，机器人不能向下移动，否则就会被石头击中。

同样，如果 \(y+1 < m\) 和 \(((x+1) \bmod n, y+1)\) 处有一块岩石，机器人就不能向右移动，否则就会被石头击中。

然而，值得注意的是，如果在 \((x \bmod n, y+1)\) 和 \(((x+1) \bmod n, y)\) 处有一块石头，机器人仍然可以安全地向右移动。

求到达 \((n-1,m-1)\) 时不与任何岩石相撞所需的最短时间。如果无法做到，输出 \(-1\) 。

思路

考虑移动的相对变换，我们可以认为机器人进行了以下操作：

1. 机器人相对石头的位置不动。
2. 机器人相对石头向右移动一格，同时向下移动一格。
3. 机器人相对石头向下移动两格。

从 \((0,0)\) 开始进行 BFS ，分别进行操作 \(2\) 和操作 \(3\)，并更新是否访问，计算出第一列到倒数第二列内各点是否能访问，以及到达需要的步数。

• 在相对运动的视角中，一个点如果有多条访问路径，那么这些路径的曼哈顿距离相等，也就是操作次数相等。
• 容易得到每个点只会被访问一次。

考虑到最后一列没有任何石头，因此我们不需要对最后一列进行 BFS。

通过最后一列，我们可以向上移动或向下移动，来达到终点。如果倒数第二列无法到达，最后一列也无法到达。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define Mod 998244353
using namespace std;
int a[1005][1005],dis[1005][1005];
void solve()
{
    int n, m;
    cin>>n>>m;
    for (int i=0; i < n;i++) {
        for (int j=0; j < m; j++) { 
            cin >> a[i][j];
        }
    }
    memset(dis,-1,sizeof(dis));
    queue<pair<int, int>> q;
    q.emplace(0,0);
    dis[0][0]=0;
    while (!q.empty()) {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        if (y<m-1&&a[(x+1)%n][y+1]==0&&dis[(x+1)%n][y+1]==-1) {
            q.emplace((x+1)%n, y+1);
            dis[(x+1)%n][y+1]=dis[x][y]+1;
        }
        if (a[(x+1)%n][y]==0&&a[(x+2)%n][y]==0&&dis[(x+2)%n][y]==-1) {
            q.emplace((x+2)%n, y);
            dis[(x+2)%n][y]=dis[x][y]+1;
        }
    }
    int ans=-1;
    for (int i=0; i<n;i++) {
        int val=dis[i][m-1];
        if (val!=-1) {
            if (val%n!=(i+1)%n) val+=(i+1-val%n+n)%n;
            if (ans==-1||ans>val) ans=val;
        }
    }
    cout<<ans<<endl;
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

G. Turtle Magic: Royal Turtle Shell Pattern

等待更新

我还没补题。