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

Codeforces Round #847 (Div. 3)

时间：2023-01-29 16:44:37浏览次数：47  
标签：847 ch return int auto Codeforces read vector Div

A. Polycarp and the Day of Pi

先纯一下圆周率前30位，然后暴力就好了

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::string;

int read(){...}

const string tmp = "314159265358979323846264338327";

void solve(){
    string s; cin >> s;
    int res = 0;
    for( int i = 0 ; i < std::min( s.size() , tmp.size() ) ; i ++ ){
        if( s[i] == tmp[i] ) res ++;
        else break;
    }
    printf("%d\n" , res );

}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

B. Taisia and Dice

令s-r为第一个数，保证序列不上升，且和为s。dfs枚举一下就行。

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::string;

const int N = 55;
int a[N] , n , s , r ;
bool flag ;

int read(){...}

void dfs( int i , int sum ){
    if( flag ) return;
    if( i == n + 1 ){
        if( sum != 0 ) return ;
        flag = true;
        for( int j = 1 ; j <= n ; j ++ ) printf("%d%c" , a[j] , " \n"[j==n] );
        return;
    }
    for( int j = std::min( a[i-1] , sum ) ; j >= 1  ; j -- )
        a[i] = j , dfs( i+1 , sum - j );
    return ;
}

void solve(){
    n = read() , s = read() , r = read() , flag = false;
    memset( a , 0 , sizeof a ) , a[1] = s - r;
    dfs( 2 , r );
    return ;
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

C. Premutation

每个位置的数一定出现了n-1次，而没有出现该数的序列就是这个数缺失的序列，这个序列后面的数向前错一位保证对其

#include <bits/stdc++.h>

using namespace std;

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

void solve(){
    int n = read();
    vector< vector<int> > a( n ,  vector<int>(n-1) );
    for( auto & it : a )
        for( auto &i : it ) i = read();
    vector<int> vis(n);
    for( int i = 0 ; i < n ; i ++ ){
        map<int,int> st;
        for( int j = 0 ; j < n ; j ++ ){
            if( vis[j] ) st[ a[j][i-1] ] ++;
            else st[ a[j][i] ] ++;
        }
        for( auto [ k , v] : st ){
            if( v == 1 ){
                for( int j = 0 ; j < n ; j ++ )
                    if( vis[j] == 0 && a[j][i] == k ) vis[j] = 1;
            }
            else printf("%d " , k );
        }
    }
    printf("\n");
    return;
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

但是看了jiangly发现有更简单的做法，当找到出第一个数，第一数确实的序列是[2,n]的完整序列

#include <bits/stdc++.h>

using namespace std;


int read() {...}

void solve() {
    int n = read() , t;
    vector<vector<int> > a(n, vector<int>(n - 1));
    for (auto &it: a)
        for (auto &i: it) i = read();
    map<int, int> st;
    for (auto it: a) st[it[0]]++;
    for (auto [k, v]: st) if (v == n - 1) t = k;
    for (auto it: a) {
        if (it[0] == t) continue;
        printf("%d ", t);
        for (auto i: it) printf("%d ", i);
        printf("\n");
        return;
    }
    return;
}

int32_t main() {
    for (int t = read(); t; t--)
        solve();
    return 0;
}

D. Matryoshkas

数字很少，直接暴力就好。

#include <bits/stdc++.h>

using namespace std;

int read(){...}

void solve(){
    int n = read() , res = 0 , t;
    map<int,int> st;
    for( int i = 1 , x ; i <= n ; i ++ ) x = read() , st[x]++;
    while( !st.empty() ){
        vector<int> erase;
        res ++ , t = -1;
        for( auto &[k,v] : st ){
            if( k == t+1 || t == -1 ) t = k , v --;
            else break;
            
            if( v == 0 ) erase.push_back(k);
        }
        for( auto it : erase ) st.erase(it);
    }
    printf("%d\n" , res );
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

E. Vlad and a Pair of Numbers

我这里是先用lowbit把原来的数拆开，然后这些数保证了异或为x，然后因为\(x=\frac{a+b}{2}\)，所以\(a+b-x=x\)，也就是说还有x保证和是a+b，这部分因为异或是0所以要平均分，即\(\frac{x}{2}\)并且些数lowbit拆开后不能与x拆开的数重复。

#include <bits/stdc++.h>

using namespace std;

#define int long long

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

#define lowbit(x) ( x &-x )

void solve(){
    int x = read();
    if( x & 1 ) {
        printf("-1\n");
        return ;
    }
    set<int> a , b ;
    for( int t = x , p ; t > 0 ; ) p = lowbit(t) , a.insert(p) , t -= p;
    for( int t = (x >> 1) , p ; t > 0 ; ) p = lowbit(t) , b.insert(p) , t -= p;
    for( auto i : b ){
        if( a.count(i) ) {
            printf("-1\n");
            return ;
        }
    }
    int A = 0 , B = 0;
    for( auto i : a ) A += i ;
    for( auto i : b ) A += i , B += i ;
    cout << A << " " << B << "\n";
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

赛后发现有\(O(1)\)的做法，观察我构造的值，\(a=\frac{x}{2},b=\frac{3x}{2}\)直接验证就好

#include <bits/stdc++.h>

using namespace std;

#define int long long

int read(){...}

void solve(){
    int x = read() , a = x / 2 , b = a * 3 ;
    if(( a ^ b) != x || a + b != x * 2 ) printf("-1\n");
    else printf("%d %d\n" , a , b );
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

F. Timofey and Black-White Tree(补题)

直接bfs，在保证最优性的情况下，层数下降的非常快，大概是\(n\times(\frac11+\frac12+\frac12+\frac14+\frac14+\frac14+\frac14+\frac18 \cdots)\)的情况。知道了这个性质我就想写了一个dfs

#include <bits/stdc++.h>

using namespace std;

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

int n , ans;
vector<int> c , res , color;
vector<vector<int>> e;

void dfs( int u , int fa , int dis ){
    if( dis >= ans ) return;
    for( auto v : e[u] ){
        if( v == fa ) continue;
        if( color[v] == 1 ) {
            ans = min( ans , dis + 1 );
            return;
        }
        dfs( v , u , dis + 1 );
    }
}

void solve(){
    n = read() , ans = INT_MAX;
    c = vector<int>(n) , res.clear() , color = vector<int>(n+1 , 0 ) , e = vector<vector<int>>( n+1 );
    for( auto &i : c ) i = read();
    for( int i = 1 , u , v ; i < n ; i ++ ){
        u = read() , v = read();
        e[u].push_back(v) , e[v].push_back(u);
    }
    color[ c[0] ] = 1;
    for( int i = 1 ; i < n ; i ++ ){
        color[ c[i] ] = 1;
        dfs( c[i] , -1 , 0 );
        cout << ans << " ";
    }
    cout << "\n";
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

然后TLE20，觉得可能dfs的问题又写了一下bfs

#include <bits/stdc++.h>

using namespace std;

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

int n , ans;
vector<int> c , res , color;
vector<vector<int>> e;

#define mp make_pair

void solve(){
    n = read() , ans = INT_MAX;
    vector<int> c(n) , color( n+1 , 0 );
    vector< vector<int> > e(n+1);
    for( auto &i : c ) i = read();
    for( int i = 1 , u , v ; i < n ; i ++ ){
        u = read() , v = read();
        e[u].push_back(v) , e[v].push_back(u);
    }
    color[ c[0] ] = 1;

    for( int i = 1 ; i < n ; i ++ ){
        color[ c[i] ] = 1;
        unordered_set<int> vis;
        queue< pair<int,int> > q;
        q.push( mp( c[i] , 0 ) ) , vis.insert(c[i]);
        while( !q.empty() ){
            auto [ u , dis ] = q.front(); q.pop();
            if( dis >= ans ) break;
            bool flag = false;
            for( auto v : e[u] ){
                if( vis.count(v) ) continue;
                if( color[v] == 1 ) {
                    ans = min( ans , dis + 1 );
                    flag = true;
                    break;
                }
                q.emplace( v , dis + 1 ) , vis.emplace(v);
            }
            if( flag ) break;
        }
        printf("%d " , ans );
    }
    printf("\n");
    return;
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

还是TLE20，我们换个角度来思考一下，只有新增加的点可能会影响答案，所以我们维护一个每个点到黑点的最短距离，没次加入一个点后，用bfs去更像一下整张图的最短距离

#include <bits/stdc++.h>

using namespace std;

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

int n , ans;
vector<int> c , res , color;
vector<vector<int>> e;

#define mp make_pair

void solve(){
    n = read() , ans = INT_MAX;
    vector<int> c(n) , color( n+1 , 0 );
    vector< vector<int> > e(n+1);
    for( auto &i : c ) i = read();
    for( int i = 1 , u , v ; i < n ; i ++ ){
        u = read() , v = read();
        e[u].push_back(v) , e[v].push_back(u);
    }
    vector<int> dis( n+1 , n );
    for( auto i : c ){
        ans = min( ans , dis[i] );
        if( ans < n ) printf( "%d " , ans );
        queue<int> q;
        q.push( i ) , dis[i] = 0;
        while( !q.empty() ){
            auto u = q.front() ; q.pop();
            if( dis[u] + 1 >= ans ) break;
            for( auto v : e[u] ){
                if( dis[u] + 1 >= dis[v] ) continue;
                dis[v] = dis[u] + 1 , q.push( v );
            }
        }
    }
    printf("\n");
    return;
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

标签：847,ch,return,int,auto,Codeforces,read,vector,Div
From： https://www.cnblogs.com/PHarr/p/17073108.html

相关文章

  • Codeforces Round #847 (Div. 3) ABCDE
    url:Dashboard-CodeforcesRound#847(Div.3)-CodeforcesA.PolycarpandtheDayofPi题意:判断给的字符串前多少位跟PI一样思路:打个表,然后遍历一下即可,遇......
  • Codeforces Global Round 1
    A  题解：倒叙枚举即可。1#include<bits/stdc++.h>2usingnamespacestd;34typedeflonglongll;5constllN=1e6+3;6llb,k,a[N];7voidSolv......
  • Educational Codeforces Round 2 个人总结A-D
    EducationalCodeforcesRound3A.USBFlashDrives降序排序后，贪心，甚至不会爆longlongvoidsolve(){intn,m;cin>>n>>m;vector<int>a(n);for(......
  • Codeforces Round #801 (Div. 2) and EPIC Institute of Technology Round A - D
    题目链接A#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;#defineintlonglongconstintN=1e3+10;intn,m;intg[N][N......
  • 定位的div环形圆形排列
    要实现一个类似于下图的效果，十个标签从中间随机出现的动画效果，若没有十个则按定义位置出现1.将十个标签都固定在中心位置，通过class,并且动态生成标签颜色<div......
  • Codeforces Round #847 F
    F.TimofeyandBlack-WhiteTree题链因为是一棵树的形式我们不妨考虑dpdp[u]表示u节点子树内黑点离u的最近距离我们每添加一个点当然会更新他及他链上面父亲的dp值......
  • Codeforces Round #816 (Div. 2)
    D.2+doors要让字典序最小就要让每个数字在满足条件的同时都尽可能的小并且排在前面的数字变小的优先级要比排在后面的数字的优先级更大。\[\begin{aligned}1\operator......
  • Codeforces Round #847 (Div. 3)
    E.VladandaPairofNumbers题目抽象为给\(n\)\((1\len\le2^{29})\)，求\(x\)满足\((n-x)\oplus(n+x)=n\)，输出\(n-x\)和\(n+x\)。显然\(n\)为奇数肯定不行......
  • CF 1790E. Vlad and a Pair of Numbers_Codeforces Round #847 (Div. 3)
    给出整数x，求一对整数(a,b)，满足：\(a\bigoplusb=x\)，\(\frac{a+b}{2}=x\)（\(\frac{a+b}{2}\)不四舍五入，也就是\(2\mida+b\)）如果不存在这样的(a,b)输出-1分析：如果x的最......
  • # CF#847 (Div. 3)ABCDE题解
    CodeforcesRound#847(DFiv.3)APolycarpandtheDayofPiProblem-A-Codeforces题目描述OnMarch14,thedayofthenumber$\pi$iscelebratedallov......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99