【题解】Codeforces Round #619 (Div. 2)

缺乏、安全感 2023-07-05 11:43 8阅读 0赞

> 比赛链接：[https://codeforces.com/contest/1301][https_codeforces.com_contest_1301]

###  ###

*  A. Three Strings（思维）
 *  B. Motarack's Birthday（思维）
 *  C. Ayoub's function（思维）
 *  D. Time to Run（构造）

# A. Three Strings（思维） #

> **原题链接：**[https://codeforces.com/contest/1301/problem/A][https_codeforces.com_contest_1301_problem_A]

*  **题意：** 给三个相同长度 n 字符串 a，b，c，c 每个字符必须和 a 或者 b 的相应下标字符交换，问经过 n 次变换后 a 是否可以和 b 相同。
 *  **思路：** a 的字符与 c 的相同或者 b 的字符与 c 的相同既符合交换。如果三个字符都相同也是一样的，交换后还是 a 和 b 还是相同。

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            string a,b,c;   cin>>a>>b>>c;
            ll len=a.length();
            int flag=1;
            for(int i=0;i<len;i++){ 
                if(a[i]==c[i] || b[i]==c[i])
                    continue;
                else{ 
                    flag=0;
                    break;
                }
            }
            if(flag)   cout<<"YES"<<endl;
            else    cout<<"NO"<<endl;
        }
        return 0;
    }

# B. Motarack’s Birthday（思维） #

> **原题链接：**[https://codeforces.com/contest/1301/problem/B][https_codeforces.com_contest_1301_problem_B]

*  **题意：** 给一个长度为 n 的数组，-1 代表没有数，你需把空位补上相同的 k ，使得数组相邻元素中的最大的差值的绝对值最小。
 *  **思路：** 先找出旁边有空位的数的最大值和最小值，然后取中间值作为 k，将空位全部补上，遍历一遍数组，输出最大的差值的绝对值。

**Code：**

#include <iostream>
    #include <cstring>
    #include <cmath>
    #define inf 0x3f3f3f3f
    using namespace std;
    typedef long long ll;
    const int N=1e5+10;
    int a[N];
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            memset(a,0,sizeof(a));
            int n;  cin>>n;
            int maxn=0,minn=inf,flag=0;
            for(int i=1;i<=n;i++){ 
                cin>>a[i];
                if(a[i]!=-1)    flag=1;
            }
            for(int i=1;i<=n;i++){ 
                if(a[i]!=-1 && (a[i-1]==-1 || a[i+1]==-1)){ 
                    maxn=max(maxn,a[i]);
                    minn=min(minn,a[i]);
                }
            }
     
            if(!flag){ 
                cout<<0<<' '<<0<<endl;
                continue;
            }
            int mid=(maxn+minn)/2;
            for(int i=1;i<=n;i++){ 
                if(a[i]==-1)
                    a[i]=mid;
            }
            int ans=0;
            for(int i=2;i<=n;i++)
                ans=max(ans,(int)abs(a[i]-a[i-1]));
            cout<<ans<<' '<<mid<<endl;
        }
        return 0;
    }

# C. Ayoub’s function（思维） #

> **原题链接：**[https://codeforces.com/contest/1301/problem/C][https_codeforces.com_contest_1301_problem_C]

*  **题意：** 给长度 n ，m 个 1，构造出一个含 1 子串数量最大的字符串，求最多的含 1 子串数量。
 *  **思路：**

1.  用子串总数量减掉不含 1 子串数量即为含 1 子串数量。一个字符串子串数量为 n\*(1+n) / 2。
2.  m 个 1 把 n-m 个 0 分割成 m+1 部分，要使得含 1 子串数量最多，就得将 0 平均分给这 m+1 部分。a = (n-m) / (m+1)就是平均每份 0 的数量，剩下的 b = (n-m)%(m+1) 就在 m+1 份放个 1 。没放 1 的部分就有 m+1-b 份。
3.  放 1 部分不含 0 的子串数量有 b\*(a+2)\*(a+1)/2 ，不放 1 部分不含 0 的子串数量有 c(1+a)a/2。

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            ll n,m;    cin>>n>>m;
            ll a = (n-m)/(m+1);
            ll b = (n-m)%(m+1);
            ll c = m+1-b;
            cout<<(1+n)*n/2-b*(a+2)*(a+1)/2-c*(1+a)*a/2<<endl;
        }
        return 0;
    }

# D. Time to Run（构造） #

> **原题链接：**[https://codeforces.com/contest/1301/problem/D][https_codeforces.com_contest_1301_problem_D]

*  **题意：** 给一个 n\*m 的图，路线在图中已标出，问能否在图中走 k 步，路线不能重复，点可以重复。如果不能走，输出“NO”，否则输出 “YES” ，总步骤，每个步骤不能超出 4 个步数，并且总步骤数不能超过 3000 次。
 *  **思路：** 走法如图所示  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]

1.  当没走到第 m 列时，每一列都要进行 n-1 次 “D”，n-1 次 “RLU”，1 次 “R”。
2.  当走到第 m 列时，要进行 n-1 次 “D”，n-1 次 “U”，m-1 次 “L”。

**Code：**

#include <iostream>
    #include <vector>
    using namespace std;
    struct node{ 
        int cnt;
        string str;
        node(int sum,string s){ 
            cnt=sum;
            str=s;
        }
    };
    vector<node> a;
    void push(node x){ 
        if(x.cnt!=0)
            a.push_back(x);
    }
    int main(){ 
        int n,m,k;  cin>>n>>m>>k;
        if(4*n*m-2*n-2*m<k)
            cout<<"NO"<<endl;
        else{ 
            cout<<"YES"<<endl;
            int cow=1;
            while(k){ 
                if(cow!=m){ 
                    if(k>=(n-1)){ 
                        push({ n-1,"D"});
                        k-=(n-1);
                    }
                    else{ 
                        push({ k,"D"});
                        k=0;
                    }
                    if(k==0)    break;
                    if(k>=3*(n-1)){ 
                        push({ n-1,"RLU"});
                        k-=3*(n-1);
                    }
                    else{ 
                        push({ k/3,"RLU"});
                        if(k%3==1)  push({ 1,"R"});
                        else if(k%3==2) push({ 1,"RL"});
                        k=0;
                    }
                    if(k==0)    break;
                    if(k>=1){ 
                        push({ 1,"R"});
                        k--;
                    }
                }
                else{ 
                    if(k>=n-1){ 
                        push({ n-1,"D"});
                        k-=(n-1);
                    }
                    else{ 
                        push({ k,"D"});
                        k=0;
                    }
                    if(!k)  break;
                    if(k>=n-1){ 
                        push({ n-1,"U"});
                        k-=(n-1);
                    }
                    else{ 
                        push({ k,"U"});
                        k=0;
                    }
                    if(!k)  break;
                    if(k>=m-1){ 
                        push({ m-1,"L"});
                        k-=(m-1);
                    }
                    else{ 
                        push({ k,"L"});
                        k=0;
                    }
                }
                cow++;
            }
            cout<<a.size()<<endl;
            for(int i=0;i<a.size();i++)
                cout<<a[i].cnt<<' '<<a[i].str<<endl;
        }
        return 0;
    }

[https_codeforces.com_contest_1301]: https://codeforces.com/contest/1301
[https_codeforces.com_contest_1301_problem_A]: https://codeforces.com/contest/1301/problem/A
[https_codeforces.com_contest_1301_problem_B]: https://codeforces.com/contest/1301/problem/B
[https_codeforces.com_contest_1301_problem_C]: https://codeforces.com/contest/1301/problem/C
[https_codeforces.com_contest_1301_problem_D]: https://codeforces.com/contest/1301/problem/D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200214225108406.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA==,size_16,color_FFFFFF,t_70