Codeforces Round 1703&1702

wenzhuan

发布于 2022-08-15 12:47:36

4660

发布于 2022-08-15 12:47:36

文章被收录于专栏：你会烧尽还是结冰

上班阶段的忙里偷闲（甚至还没做完）

因为只是div4和div3 我又拖了很久没有写（）所以不怎么写题意就贴个代码

1703A: YES or YES?

题目链接

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
    string s; cin>>s;
    for(int i=0; i<s.size(); ++i) s[i]=tolower(s[i]);
    return puts(s=="yes"?"YES":"NO");
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1703B: ICPC Balloons

题目链接

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
    int n,ans(0); string s;
    cin>>n>>s; vector<int>cnt(26);
    for(auto c: s){
        if(!cnt[c-'A']) ans+=2;
        else ans++;
        cnt[c-'A']++;
    }
    return printf("%d\n",ans);
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1703C: Cypher

题目链接

模拟

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
    int n; cin>>n;
    vector<int>vv(n);
    for(int i=0; i<n; ++i)
        cin>>vv[i];
    for(int i=0; i<n; ++i){
        int k; string s;
        cin>>k>>s;
        for(auto c: s){
            if(c=='U') vv[i]--;
            else vv[i]++;
        }
        cout<<(vv[i]+10)%10<<' ';
    }
    return printf("\n");
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1703D: Double Strings

题目链接

只需要两个拼起来不需要多个

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
string s[maxn];
map<string,int>mp;
int find_ans(string s0, int len){
    string t=""; t+=s0[0];
    for(int i=1; i<len; ++i){
        string s1=s0.substr(i);
        if(mp.count(t)&&(mp.count(s1))) return 1;
        t+=s0[i];
    }
    return 0;    
}
int cmp(int a, int b){
    return s[a].size()<s[b].size();
}
int solve(){
    int n; cin>>n; mp.clear();
    for(int i=0; i<n; ++i) cin>>s[i];
    vector<int>ord(n),ans(n);
    for(int i=0; i<n; ++i) ord[i]=i;
    sort(ord.begin(),ord.end(),cmp); 
    int len0=s[ord[0]].size(),ff(0);
    for(int i=0; i<n; ++i){
        mp[s[ord[i]]]++; int len=s[ord[i]].size();
        if(!ff&&len==len0) ans[ord[i]]=0;
        else ff++,ans[ord[i]]=find_ans(s[ord[i]],len);
    }
    for(int i=0; i<n; ++i) cout<<ans[i];
    return printf("\n");
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1703E: Mirror Grid

题目链接

美团笔试出过秋招的小朋友可以看看

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
string s[maxn];
int solve(){
    int n,ans(0); cin>>n;
    for(int i=0; i<n; ++i) cin>>s[i];
    for(int i=0; i<n; ++i) for(int j=0; j<n; ++j){
        int tmp=(int)s[i][j]+s[j][n-i-1]+s[n-i-1][n-j-1]+s[n-j-1][i]-4*'0';
        if(tmp<=2) s[i][j]=s[j][n-i-1]=s[n-i-1][n-j-1]=s[n-j-1][i]='0';
        else s[i][j]=s[j][n-i-1]=s[n-i-1][n-j-1]=s[n-j-1][i]='1';
        ans+=min(tmp, 4-tmp);
    }
    return printf("%d\n", ans);
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1703F: Yet Another Problem About Pairs Satisfying an Inequality

嘴完待补

1703G: Good Key, Bad Key

嘴完待补

1702A: Round Down the Price

题目链接

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
    int n; scanf("%d", &n);
    long long d=1; while(d<=n) d*=10;
    return printf("%d\n", n-d/10);
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1702B: Polycarp Writes a String from Memory

题目链接

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
    string s;
    cin>>s;
    set<char>st;
    int ans(0);
    for(char c: s){
        st.insert(c);
        if(st.size()==4){
            st.clear();
            st.insert(c);
            ans++;
        }
    }
    if(st.size()) ans++;
    return printf("%d\n",ans);
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1702C: Train and Queries

题目链接

离散化后存一个pair记录最远和最近

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
    int n,k; scanf("%d%d", &n,&k);
    vector<int>arr(n+1);
    map<int,pair<int,int>>pos;
    for(int i=1; i<=n; ++i){
        scanf("%d", &arr[i]);
        if(!pos.count(arr[i])) pos[arr[i]]={i,i};
        else pos[arr[i]].second=i;
    }
    for(int i=0; i<k; ++i){
        int a,b; scanf("%d%d", &a,&b);
        if(!pos.count(a)||!pos.count(b)) puts("NO");
        else puts(pos[b].second>pos[a].first?"YES":"NO");
    }
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1702D: Not a Cheap String

题目链接

简单贪心

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
char s[maxn];
int cmp(int a,int b){
    return s[a]<s[b];
}
int solve(){
    int k; scanf("%s%d", s,&k);
    int len=strlen(s),sum(0),cnt=len;
    vector<int>arr(len);
    for(int i=0; i<len; ++i) arr[i]=i;
    sort(arr.begin(),arr.end(),cmp);
    for(int i=0; i<len; ++i) sum+=s[i]-'a'+1;
    for(int i=len-1; i>=0; --i){
        if(sum<=k) break;
        sum-=s[arr[i]]-'a'+1;
        cnt=i;
    }
    sort(arr.begin(),arr.begin()+cnt);
    for(int i=0; i<cnt; ++i) putchar(s[arr[i]]);
    return putchar('\n');
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1702E: Split Into Two Sets

题目链接

找环，需要环不是奇数

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n,ff,vis[maxn];
vector<int>vv[maxn];
set<int>ss;
void dfs(int st, int fa){
    vis[st]++;
    ss.insert(st);
    if(vis[st]==2){
        ff=!(ss.size()&1);
        return;
    }
    if(!ff) return;
    for(int i=0; i<vv[st].size(); ++i){
        int num=vv[st][i];
        if(num==fa) continue;
        dfs(num, st);
    }
}
int solve(){
    scanf("%d", &n); ff=1;
    vector<int>cnt(n+1);
    for(int i=0; i<n; ++i){
        int a,b; scanf("%d%d", &a,&b);
        if(a==b) ff=0; 
        cnt[a]++; cnt[b]++;
        if(cnt[a]>2||cnt[b]>2) ff=0;
        if(!ff) continue;
        vv[a].push_back(b);
        vv[b].push_back(a);
    }
    for(int i=1;i<=n;++i)
        if(!vis[i]){
            ss.clear();
            ss.insert(i);
            dfs(i,0);
        }
    for(int i=1; i<=n; ++i)
        vis[i]=0, vv[i].clear();
    return puts(ff?"YES":"NO");
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1702F: Equate Multisets

题目链接

暴力过了（……）加了个小剪枝可能是假的反正过了（摊手）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
    int n; scanf("%d", &n);
    map<int,int>s1;
    for(int i=0; i<n; ++i){
        int a; scanf("%d", &a);
        s1[a]++;
    }
    for(int i=0; i<n; ++i){
        int b,b1; scanf("%d", &b); 
        if(i>1e5&&s1.size()>1e5) continue;
        b1=b; while(b1){
            int b2=b1;
            while(b2<=(--s1.end())->first){
                if(s1.count(b2)){
                    s1[b2]--;
                    if(!s1[b2]) s1.erase(b2);
                    b2=-1;
                    break;
                }
                b2*=2;
            }
            if(b2==-1) break;
            if(s1.count(b1)){
                s1[b1]--;
                if(!s1[b1]) s1.erase(b1);
                break;
            }
            b1/=2;
        }
    }
    return puts(s1.size()||s1.size()>1e4?"NO":"YES");
}
int main(){
    int _; scanf("%d",&_); while(_--) solve();
}

1702G1&G2: Passable Paths

已嘴待补

其他

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=19q8g0m4dwk3l

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

Codeforces Round 1703&1702

Codeforces Round 1703&1702

1703A: YES or YES?

1703B: ICPC Balloons

1703C: Cypher

1703D: Double Strings

1703E: Mirror Grid

1703F: Yet Another Problem About Pairs Satisfying an Inequality

1703G: Good Key, Bad Key

1702A: Round Down the Price

1702B: Polycarp Writes a String from Memory

1702C: Train and Queries

1702D: Not a Cheap String

1702E: Split Into Two Sets

1702F: Equate Multisets

1702G1&G2: Passable Paths

其他

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐