首页 > 其他分享 >Codeforces Round 913 (Div. 3)

Codeforces Round 913 (Div. 3)

时间：2023-12-07 14:57:00浏览次数：37  
标签：int Codeforces long while solve ans Div 913 define

Codeforces Round 913 (Div. 3)

div3 两题 新纪录..

我再也不喝完酒打cf了

A. Rook

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

int board[10][10];

void solve(){
    string s;
    cin>>s;
    int x=s[0] - 'a' + 1;
    int y=s[1] - '0';
    for(int i=1;i<=8;i++){
        if(i!=y) cout<<s[0]<<i<<endl;
    }
    for(char c='a';c<='h';c++){
        if(c!=s[0]) cout<<c<<s[1]<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

B. YetnotherrokenKeoard

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

int board[10][10];

void solve(){
    string s;
    cin>>s;
    deque<pair<int,char>> path1,path2;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='b')
        {
            if(path1.size()) path1.pop_back();
        }
        else if(s[i]=='B')
        {
            if(path2.size()) path2.pop_back();
        }
        else if(s[i]>='a'&&s[i]<='z') path1.push_back({i,s[i]});
        else if(s[i]>='A'&&s[i]<='Z') path2.push_back({i,s[i]});
    }
    while(path1.size()&&path2.size())
    {
        if(path1.front().first<path2.front().first)
        {
            cout<<path1.front().second;
            path1.pop_front();
        }else
        {
            cout<<path2.front().second;
            path2.pop_front();
        }
    }
    while(path1.size()){
            cout<<path1.front().second;
            path1.pop_front();
    }
    while(path2.size()){
            cout<<path2.front().second;
            path2.pop_front();
    }
    cout<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

C. Removal of Unattractive Pairs

如果所有字符的数量都<=n/2，那么就一定可以两两消到最后。

否则就尽量消数量最多的字符

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

const int N = 2e5 + 10;
int cnt[26];
void solve(){
    memset(cnt,0,sizeof cnt);
    int n;
    string s;
    cin>>n>>s;
    for(int i=0;i<n;i++) cnt[s[i]-'a']++;
    int x=*max_element(cnt,cnt+26);
    if(x<=n/2) cout<<n%2<<endl;
    else       cout<<x*2-n<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

D. Jumping Through Segments

这题写的时候还看错题目了，搞得以为很难，

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

const int N = 2e5 + 10;
int ll[N],rr[N];
int n;

bool check(int mid){
    int l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        l = max(l-mid , 0ll);
        r = r + mid;
        if(ll[i]>r||rr[i]<l) return false;
        l = max(l,ll[i]);
        r = min(r,rr[i]);
    }
    return true;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>ll[i]>>rr[i];
    int l=0,r=1e18;
    int ans=1e18;
    while(l<=r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid - 1 , ans = mid;
        else           l = mid + 1;
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

E. Good Triples

这题的核心是要发现每一位都是单独独立的。不能有进位 如5+5+10=20 （5）+（5）+（1）+（0）=6 （2）+（0）= 2 5+5进位后右边只加了1。显然不能有进位。

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

int cnt[20];

void solve(){
    memset(cnt,0,sizeof cnt);
    for(int i=0;i<10;i++)
        for(int k=0;k+i<10;k++)
            for(int j=0;j+k+i<10;j++)
                cnt[i+k+j]++;
    int n;
    cin>>n;
    string s=to_string(n);
    int ans=1;
    for(int i=0;i<s.size();i++)
    {
        ans*=cnt[s[i]-'0'];
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

F. Shift and Reverse

将链变环，如果有一个点往后递增序列的长度为n，这个点就是起点。找到这个起点，然后暴力求两个解.

自己的码搓的太狗屎了，看看佬的码吧。

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int INF = 1e9;
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n * 2);
        for(int i = 0; i < n; i++) 
            cin >> a[i], a[i + n] = a[i];
    
        int ans = INF;
        for(int i = 0; i < n; i++){
            int j = i;
            while(j + 1 < 2 * n && a[j + 1] >= a[j]) j++;
            for(int k = i; k <= j && k < n; k++){
                int len = j - k + 1;
                if (len >= n){
                    ans = min(ans, (n - k) % n);
                    int rev = n - 1 - k;
                    ans = min(ans, n - 1 - rev + 2);
                }
            }
            i = j;
        }
        for(int i = 0; i < n; i++){
            int j = i;
            while(j + 1 < 2 * n && a[j + 1] <= a[j]) j++;
            for(int k = i; k <= j && k < n; k++){
                int len = j - k + 1;
                if (len >= n){
                    ans = min(ans, (n - k) % n + 1);
                    int rev = n - 1 - k;
                    ans = min(ans, n - 1 - rev + 1);
                }
            }
            i = j;
        }
        if (ans > INF / 2) ans = -1;
        cout << ans << '\n';
    }

}

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

const int N = 1e5 + 10;
int a[N] , du[N];
bool vis[N] , light[N] ,used[N];
int n;

void solve(){
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        light[i+1] = (s[i]=='1');
        vis[i+1]=false;
        used[i+1]=false;
        du[i+1]=0;
    }

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        du[a[i]]++;
    }

    queue<int> path;
    for(int i=1;i<=n;i++)
        if(!du[i]) path.push(i);
    vector<int> ans;
    while(path.size()){
        int u=path.front();path.pop();
        if(light[u]){
            light[u]    ^= 1;
            light[a[u]] ^= 1;
            vis[u] = true;
            ans.push_back(u);
        }
        if(--du[a[u]]==0) path.push(a[u]);
    }

    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&du[i]){
            int u=0;
            vector<vector<int>> que(2);
            for(int j=i;!used[j];j=a[j])
            {
                u ^= (light[j]==1);
                que[u].push_back(j);
                used[j] = true;
            }
            if(u){
                cout<<-1<<endl;
                return;
            }
            if(que[0].size()<que[1].size()){
                for(auto x:que[0]){
                    vis[x] = true;
                    ans.push_back(x);
                }
            }else{
                for(auto x:que[1]){
                    vis[x] = true;
                    ans.push_back(x);
                }
            }
            // break 没明白为什么这里不能break
        }
    }
    cout<<ans.size()<<endl;
    for(auto u:ans) cout<<u<<" ";
    cout<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

标签：int,Codeforces,long,while,solve,ans,Div,913,define
From： https://www.cnblogs.com/zfxyyy/p/17881975.html

相关文章

  • 【题解】CodeForces 1902F Trees and XOR Queries Again
    传送门：https://codeforces.com/contest/1902/problem/F数据结构题，这里讲两种思路。$ST$表思路：判定“从若干个数中能否取出其中一些，使得异或和为$x$”的问题，第一时间想到线性基，本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性基可以合并，方法为“暴力将......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    Preface补题，妈的现在EduE都做不来这搞毛啊A.LineTrip签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>#include<algorithm>#include<queue&......
  • Codeforces Round 913 (Div. 3)（A~F）
    A.Rook题意：在一个国际象棋棋盘中，横坐标为a-h，纵坐标为1-8，字母在前，数字在后，输入一个棋子的位置，输出该棋子所在的行与列中非棋子本身位置的所有位置。分析：模拟。代码：#include<iostream>#include<algorithm>usingnamespacestd;typedeflonglongll;constintN=2e5......
  • 【题解】CodeForces 686E Optimal Point
    传送门：https://codeforces.com/contest/686/problem/E前言：本题解来源于作者某天晚上和一位朋友的发电内容（没错，这个作者直接把自己和朋友发电时发的话用markdown排了一下，传上来了），当时本来就比较口语化，加上作者的做法又实在太过离谱，因此可能语言表述不够清晰，对此深感抱歉qwq；离......
  • Codeforces Round 912 (Div. 2)
    Preface这场题莫名很对我胃口，因为F是个究极套路题，还是我最拿手的2-SAT，想+写不到半小时就搞定了然后E的核心思想和上周末VP的一场省赛的题一样，因此看一眼就会了唯一抽象的是D2要用对超集的sosdp，由于之前没写过就不知道还能这么搞A.HalloumiBoxes当\(k\ge2\)时，我们总可以通......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    Preface补题，经典不会F，看了会题解发现看不懂，索性直接开摆A.JaggedSwaps判断\(a_1\)是否为\(1\)即可#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>#include<al......
  • CodeForces 1497E2 Square-free division (hard version)
    洛谷传送门CF传送门感觉和CF1889C2Doremy'sDryingPlan(HardVersion)有异曲同工之妙。显然去除每个数的平方因子后，两个数相乘为完全平方数当且仅当它们相等。考虑若确定了分段方案，那么修改次数就是，每一段重复出现的数的个数。那么我们设\(f_{i,j}\)为\([1,i]\)......
  • Codeforces Round 805 (Div. 3)
    CodeforcesRound805(Div.3)基本情况A、B、C题秒了。D题一开始读错题了，以为是DP，后面发现是简单贪心，拖了点时间才AC。不过无所谓，因为E题没思路了。但是总感觉C做的太不优雅。C.TrainandQueries我的做法就纯用STL无脑模拟。跑了\(701ms\)#include<iostream>#inclu......
  • [Codeforces Round 855 (Div. 3)](https://codeforces.com/contest/1800)
    CodeforcesRound855(Div.3)A.IsItaCat?为什么这个A这么麻烦#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intn;strings;cin>>n>>s;s=""+s;......
  • Educational Codeforces Round 159 总结
    最失败的一集。C开题顺序搞错，不小心先开了C，以为是A。还好C不难。题意大概是在给定的数组最后添一个数（所有数两两不同），再自定义一个数\(k\)，数组中每个数可以加上若干个\(k\)，最后使得所有数字相等。要求加\(k\)的次数最少。如果不加最后一个数，那么显然把所有的数加到与最大......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99