首页 > 其他分享 >Codeforces Round 871 (Div. 4)

Codeforces Round 871 (Div. 4)

时间：2023-05-08 20:14:16浏览次数：28  
标签：ch int Codeforces 871 read while && Div getchar

A. Love Story

#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;
}


void solve(){
    string s;
    cin >> s;
    int res = 0;
    for( int i = 0 ; i < s.size() ; i ++ )
        res += s[i] != "codeforces"[i];
    cout << res <<"\n";
    return;
}

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

B. Blank Space

#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;
}


void solve(){
    int n = read() , res = 0 , cnt = 0;
    for( int x ; n ; n -- ){
        x = read();
        if( x == 1 ) cnt = 0;
        else cnt ++ , res = max( res , cnt );
    }
    printf("%lld\n" , res);
    return;
}

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

C. Mr. Perfectly Fine

dp一下就好了

#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;
}


void solve(){
    int n = read();
    vector<int> f( 4 , 1e18 ) , g;
    f[0] = 0;
    for( int x , y ; n ; n -- ){
        x = read() , y = read();
        if( y > 1 ) y -= 8;
        g = f;
        for( int i = 0; i < 4 ; i ++ )
            f[i|y] = min( f[i|y] , g[i] + x );
    }
    if( f[3] == 1e18 ) printf("-1\n");
    else printf("%lld\n" , f[3] );
    return;
}

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

D. Gold Rush

只有当前的数字是三的倍数才可以分。最多可以分\(\log_3n\)次，为了避免重复的情况可以加一个记忆化

#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;
}

int n , m , f = 0;

set<int> vis;

void dfs( int x ){
    if( f == 1 || x < m || vis.count(x) ) return;
    if( x == m ){
        f = 1;
        return;
    }
    if( x % 3 ) return;
    dfs( x / 3 ) , dfs( x / 3 * 2 );
    return;
}

void solve(){
    n = read() , m = read() , f = 0;
    dfs(n);
    cout << ( f ? "yes\n" : "no\n");
    return;
}

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

E. The Lakes

就搜一下就好了吧。

#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;
}

constexpr int dx[] = { 0 , 0 , 1 , -1 };
constexpr int dy[] = { 1 , -1 , 0 , 0};


void solve(){
    int n = read() , m = read() , res = 0;
    vector<vector<int>> g(n+1,vector<int>(m+1 , 0));
    for(int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= m ; j ++ )
            g[i][j] = read();
    vector<vector<bool>> vis( n+1 , vector<bool>(m+1 , 0) );
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= m ; j ++ ){
            if( vis[i][j] || g[i][j] < 1 ) continue;
            int cnt = 0;
            queue<pair<int,int>> q;
            q.emplace( i , j );
            while( !q.empty() ){
                auto [x,y] = q.front();
                q.pop();
                if( vis[x][y] ) continue;
                vis[x][y] = 1 , cnt = cnt + g[x][y];
                for( int l = 0 , fx , fy ; l < 4 ; l ++ ){
                    fx = x + dx[l] , fy = y + dy[l];
                    if( fx < 1 || fy < 1 || fx > n || fy > m || g[fx][fy] < 1 || vis[fx][fy] ) continue;
                    q.emplace(fx , fy);
                }
            }
            res = max( res , cnt );
        }
    printf("%lld\n" , res );
    return;
}

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

F. Forever Winter

因为题目保证了\(x>1,y>1\)所以度为 1 的点一定是叶子节点。从叶子点向内走一步就是第一次扩展的点，在走一步就是根节点。然后根据度数计算\(x,y\)

#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;
}

const int N = 1e6 + 5, M = 1505;
int pos[M][M], px[N], py[N];

int sum(int x) {
    return x * (x + 1) * (x * 2 + 1) / 6;
}

void solve() {
    int n = read() , m = read();
    vector<vector<int>> g(n+1);
    for( int u , v ; m ; m -- ){
        u = read() , v = read();
        g[u].push_back(v) , g[v].push_back(u);
    }
    int x , y;
    for( int i = 1 ; i <= n ; i ++ ){
        if( g[i].size() != 1 ) continue;
        x = g[i].front();
        for( auto v : g[x] ){
            if( g[v].size() != 1 ) y = v;
        }
        x = g[x].size() - 1 , y = g[y].size();
        printf("%lld %lld\n" , y , x);
        break;
    }
}

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

G. Hits Different

一个比较简单的模拟。首先要知道\(1^2+2^2+3^2+\cdots+n^2=\frac{n(n-1)(2n-1)}{6}\)

所以只要计算出每一层的左右端点即可。

#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;
}

const int N = 1e6 + 5, M = 1505;
int pos[M][M], px[N], py[N];

int sum(int x) {
    return x * (x + 1) * (x * 2 + 1) / 6;
}

void solve() {
    int n = read(), res = 0;
    for (int i = px[n], l = py[n], r = py[n]; i >= 1; i--) {
        res += sum(pos[i][r]) - sum(pos[i][l] - 1);
        l = max(1ll, l - 1), r = min(r, i - 1);
    }
    printf("%lld\n", res);
}

int32_t main() {
    for (int i = 1, t = 0; t <= 1e6; i++)
        for (int j = 1; j <= i && t <= 1e6; j++)
            t++, pos[i][j] = t, px[t] = i, py[t] = j;
    for (int t = read(); t; t--)
        solve();
    return 0;
}

H. Don't Blame Me

f[i][j]表示前 i 位的非空子序列凑出 j 的方案数。所以只要枚举每一个选或不选，再枚举每一个数的前一个数即可。但是注意的是\(f[i][j]\)无法表示全空的情况，但是又会有前 i 个只选a[i]的情况，这种情况无法从之前的状态转移得来，所以f[i][a[i]]要单独加 1

#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;
}

const int mod = 1e9+7;

void solve(){
    int n = read() , k = read();
    vector<vector<int>> f( n+1 , vector<int>(64 , 0) );
    for( int i = 1 , x ; i <= n ; i ++ ) {
        x = read();
        f[i][x] ++;
        for( int j = 0 ; j < 64 ; j ++ )
            f[i][j] = ( f[i][j] + f[i-1][j] ) % mod;
        for( int j = 0 ; j < 64 ; j ++ )
            f[i][j&x] = ( f[i][j&x] + f[i-1][j] ) % mod;
    }
    int res = 0;
    for( int i = 0 ; i < 64 ; i ++){
        auto t = bitset<6>(i);
        if( t.count() == k ) res = ( res + f[n][i] ) % mod;
    }

    printf("%lld\n" , res );
}

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

标签：ch,int,Codeforces,871,read,while,&&,Div,getchar
From： https://www.cnblogs.com/PHarr/p/17382967.html

相关文章

  • Codeforces Round 871 (Div. 4)
    A.LoveStory题意:给定n个长度为10的字符串，问其与codeforces字符串的对应下标字母不同的个数。分析:对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可code:#include<bits/stdc++.h>usingnamespacestd;intmain(){ std::ios::sync_wit......
  • CF R870 div.2
    C 输出"NO"的充要条件是要在最初就选择\(k\)个物品，使得\(k\midN\)。发现朴素做法是\(O(TM)\)，可以对\(N\)的约数进行枚举，优化为\(O(T\sqrt(N))\)，再特判\(N\leqM\)和\(N=1\)的情况。#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;int......
  • 图片填满div，真让人头大
    家人们，这图片到底怎样才能完全填满div啊，想问度娘结果搜索的问题都乱七八糟的（怎么那么多问题QAQ），描述问题都描述不来具体问题如下：图片有自己的分辨率大小，例如宽100px，高100px，将图片添加到div中：<divclass="xx"><imgsrc="xxx"></div>接着用css代码编辑样式的时候，首先设置di......
  • Codeforces Round 871 (Div. 4)
    CodeforcesRound871(Div.4)A-LoveStory#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;constintN=1e5+5,INF=0x3f3f3f3f,Mod=1e6;constdoubleeps=1e-6;typedeflonglongll;i......
  • Codeforces 871 div4(重拳出击)
    Codeforces871div4ABC简单题D题意每次操作可以将当前的数分成两份，一份是\(\frac{1}{3}\)，一份是\(\frac{2}{3}\)，问当前数n可否进行若干次操作，最终出现一份大小为m的片。递归一下就好了，数据最大才\(10^7\)代码voiddfs(intx){ if(x==m){flag=1;return;} if(flag)re......
  • Codeforces Round 870 (Div. 2)
    CodeforcesRound870(Div.2)A-TrustNobody思路：枚举每一种说谎人数x，若a[i]大于x则说谎人数加一，判断最后说谎总人数是否为x，若是则输出x，结束枚举；若没有满足的x则-1#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;......
  • Codeforces 1817F - Entangled Substrings（SA）
    为什么赛时不开串串题？为什么赛时不开串串题？为什么赛时不开串串题？为什么赛时不开串串题？为什么赛时不开串串题？一种SA做法，本质上和SAM做法等价，但是说来也丢人，一般要用到SAM的题我都是拿SA过的/wul考虑将\(ac\)看作一个整体。记\(\text{occ}(S)\)为\(S\)出现位置的集......
  • Codeforces Round 848 (Div. 2)C
    B.TheForbiddenPermutation一定要注意题目中说的是对于alli满足才算不好的，我们做的时候只要破坏一个i这个a就不算好的了,被这一点坑了，没注意到all。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=2e5+10;intp[N],a[N];vo......
  • Codeforces Round 856 (Div. 2)C
    C.ScoringSubsequences思路：我们想要找到满足的最大值的长度最长的的区间，因为单调不减，所以更大的数一定在最大值的里面包含，所以我们用两个指针维护这样一个满足当前i的最大值区间，当新来一个数，这时我们答案里面一定要包含这个数，我们看能否保持这个长度，能不能保持需要看j指针所指......
  • Codeforces——870
    A.TrustNobody题目大意给你一个长度为\(n\)的数组\(a\)，\(a\)中每个元素\(a_i\)表示当前人认为\(n\)个人中至少有\(a_i\)个人说谎，让你找出说谎的人的个数。思路：枚举说谎人数\(x\)，遍历\(a\)数组，对于当前\(a_i\)，如果有\(a_i\geqx\)，那么显然第\(i\)个人在说谎，记录人数看是否等......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99