Day2 CF713 div3 vp A-G

深碍√TFBOYSˉ_ 2024-03-27 11:26 75阅读 0赞

[Dashboard - Codeforces Round \#713 (Div. 3) - Codeforces][Dashboard - Codeforces Round _713 _Div. 3_ - Codeforces]

**感觉中规中矩，rk4k+确实是我现在的水平，一直徘徊在绿灰边缘23333，其实很大原因在于不补题，看了CF Analytics的题目rating，几乎只写1200-的题，1600+的题都没几道，那确实活该吧，乐**

**其实以前想过把题补完，但是补不动，感觉越补越神秘，所以干脆不补了，但是现在感觉没以前那么神秘了，清晰了很多，所以现在补题肯定是要全部补掉的**

![7a3f3de1d3f1e3c107f8af9b299bfb77.png][]

**A的签到速度还可以，B是模拟，我码力一直很低能，平时比赛模拟题直接扔给队友，但是现在感觉，该家训了。C是个分类讨论的构造，写了一万年写出来一坨wa2的答辩，太典了，1h才ac。然后是D，直接枚举就好了，感觉D<<C啊，20min码完直接过（wa一发是数组开小了），虽然C也是一眼但是感觉细节有点点多**

A. Spy Detected!

模拟

题意:

给定n个数，问出现一次的那个数的下标就好了

思路：

直接模拟

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e2+10;
    int n;
    int a[mxn];
    void solve(){
        map<int,int> mp;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
        for(int i=1;i<=n;i++){
            if(mp[a[i]]==1){
                cout<<i<<'\n';
                return;
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

B. Almost Rectangle

模拟

题意：

有个点矩阵，给定两个星的坐标，让你补另外两颗星，使其变成矩形

思路：

直接模拟，但是要注意特判两颗星在同一行和同一列的情况

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=4e2+10;
    int n,ok=0,x1,y1,x2,y2;
    char s[mxn][mxn];
    void solve(){
        ok=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>s[i][j];
                if(!ok&&s[i][j]=='*'){
                    x1=i;
                    y1=j;
                    ok=1;
                }else if(ok&&s[i][j]=='*'){
                    x2=i;
                    y2=j;
                }
            }
        }
        //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<'\n';
        if(x1==x2){
            int t=x1==1?n:1;
            s[t][y1]='*';
            s[t][y2]='*';
        }else if(y1==y2){
            int t=y1==1?n:1;
            s[x1][t]='*';
            s[x2][t]='*';
        }else{
            s[x1][y2]='*';
            s[x2][y1]='*';
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) cout<<s[i][j];
            cout<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

C. A-B Palindrome

题意：

给定一个字符串，由0，1，？构成。现在给定0的个数和1的个数，让你修改里面的？使其变成回文串

明天写C，细节有点多

D. Corrupted Array

构造+枚举

题意：

给定长度为n+2的集合，它由一个任意数x，一个数sum，和其他n个数构成，其中sum是其他n个数的和，让你还原（构造）其他这n个数

思路：

构造

注意到给定的数列的顺序是任意的，因此可以把它看成是集合

集合可以直接排序，或者用map哈希

由于不知道x是哪个，我们考虑枚举x

然后sum一定是剩下的数中最大的那个

但是注意特判x是最大的数字的情况

如果枚举之后找不到这样的x，就无解

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=2e5+10;
    int n;
    int a[mxn],b[mxn],sum[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n+2;i++) cin>>b[i],sum[i]=0;
        sort(b+1,b+1+n+2);
        for(int i=1;i<=n+2;i++) sum[i]=sum[i-1]+b[i];
        int ansx=-1,s=-1;
        for(int i=1;i<=n+2;i++){
            if(i!=n+2){
                int x=b[i];
                if(sum[n+1]-x==b[n+2]){
                    ansx=i;
                    s=n+2;
                    break;
                }
            }else{
                if(sum[n]==b[n+1]){
                    ansx=n+2;
                    s=n+1;
                    break;
                }
            }
        }
        if(ansx==-1||s==-1){
            cout<<-1<<'\n';
            return;
        }
        vector<int> v;
        for(int i=1;i<=n+2;i++){
            if(i==ansx||i==s) continue;
            else v.push_back(b[i]);
        }
        for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

剩下的明天补，一点该睡觉了捏

[Dashboard - Codeforces Round _713 _Div. 3_ - Codeforces]: https://codeforces.com/contest/1512
[7a3f3de1d3f1e3c107f8af9b299bfb77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/74578401486847f88b10c2d3f1c79a1a.png