首页 > 其他分享 >牛客周赛 Round 5

牛客周赛 Round 5

时间:2023-08-02 11:12:59浏览次数:60  
标签:周赛 int ++ cin up 牛客 second ans Round

牛客周赛 Round 5

A-游游的字母变换_牛客周赛 Round 5 (nowcoder.com)

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	 string s;
    cin >> s;
    for(int i = 0;i < s.size();i ++){
        if(s[i] >= 'A' && s[i] < 'Z') s[i]++;
        else if(s[i] > 'a' && s[i] <= 'z') s[i]--;
        else if(s[i] == 'Z') s[i] = 'A';
        else if(s[i] == 'a') s[i] = 'z';
        
    }
    cout << s << endl;
    
	return 0;
}

B-游游的排列构造_牛客周赛 Round 5 (nowcoder.com)

要使得\(a_i\)为前\(i\)个元素的最大值,我们可以考虑第一个放第\((n - k + 1)\)大元素,后面每两个依次放这个元素大\(1\),即\(k-1\),直到\(k = 0\),这样就能构成满足条件的序列了

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n,k;
    cin >> n >> k;
 
    for(int i = 1,j = 1;j <= n;j++){
        if(k > 0 && (j & 1)) {
            cout << n - k + 1 << ' ';
            k--;
        }else{
            cout << i ++ << ' ';
        }
    }

	return 0;
}

C-游游的二进制树_牛客周赛 Round 5 (nowcoder.com)

考虑\(1 \le n \le 10^3\),我们直接暴搜(其实最开始只是想骗点分),最开始我是傻傻的按01字符串转换成数字去判断是否满足条件的,但是最后只得了\(80pt\),QAQ,后来看了别人的,发现其实直接往左移一位就可以了qwq

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n,l,r;
    cin >> n >> l >> r;
    string s;
    cin >> s;
    s = " " + s;
    vector<int> g[n + 1];
    for(int i = 1,x,y; i < n;i ++){
        cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }

    int ans = 0;
    string str;
    function<void(int,int,int,int)> dfs = [&](int u,int v,int val,int len){

        if(val > r)
            return ;
        
        if(val >= l && val <= r && len > 1){
            ans ++;
        }

        for(auto i : g[u]){
            if(i == v) continue;
            dfs(i,u,(val << 1) + s[i] - '0',len + 1);
        }
    };

    for(int i = 1;i <= n;i ++){
        dfs(i,0,s[i] - '0', 1);
    }

    cout << ans << endl;

	return 0;
}

D-游游的矩阵统计_牛客周赛 Round 5 (nowcoder.com)(双指针)

当 上层\(k\)个元素和下层\(k\)个元素都不同时,我们知道此时恰好有\(k-1\)种不同的元素的\(2*2\)的子矩阵数量.

\[\begin{bmatrix} 1 & 1 & 1 & 1\\ 2 & 2 & 2 & 2 \end{bmatrix} \]

像这样,就有\(3\)个符合条件的子矩阵数量,

但是对于这样的我们不太好去判断

\[\begin{bmatrix} 1 & 2\\ 1 & 1 \end{bmatrix} \]

所以我们可以每次判断完成后记录最后上下两个元素去下一轮单独判断,当然最开始一列是没有前面的元素的,所以$ i \ne 0 || j \ne 0$,判断的同时,将判断完的的元素删去,好让指针指向下一个连续段

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int,int> PII;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n,m1,m2;
    cin >> n >> m1 >> m2;
    vector<PII> up(m1),down(m2);
    for(auto &[x,y] : up) 
        cin >> x >> y;
    for(auto &[x,y] : down)
        cin >> x >> y;

    map<int,int> mp;    
    int i = 0, j = 0, ans = 0;
    while(i < m1 || j < m2){
        mp[up[i].first]++;
        mp[down[j].first] ++;

        if((i != 0 || j != 0) && mp.size() == 2)
            ans ++;

        if(up[i].first != down[j].first){
            int k = min(up[i].second, down[j].second);
            up[i].second -= k;
            down[j].second -= k;
            ans += k - 1;
        }else{
            int k = min(up[i].second, down[j].second);
            up[i].second -= k;
            down[j].second -= k;
        }

        mp.clear();
        mp[up[i].first] ++;
        mp[down[j].first] ++;

        if(!up[i].second) i++;
        if(!down[j].second) j++;
    }

    cout << ans << endl;

	return 0;
}

E-小红的树构造_牛客周赛 Round 5 (nowcoder.com)

想要使得所有点权值乘积最小,肯定也要路径最短,那自然是菊花图啦

因此一共有\(2-2/3-3,2-3/3-2,2-2-2/3-3-3,2-2-3/2-3-2/3-2-2,3-2-3/2-3-3\)这几种路径,

为啥把\(2-2/3-3,2-2-2/3-3-3\)放一起呢,因为它们的乘积的因子数都是相同的,其他的只是位置不同,路径结果是一样的

且\(3,2\)这样单独组合的因子数要小于它们混合组合的因子数,因此我们要尽量的把\(2,3\)中数量最多的放菊花图的中心

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n,k;
	cin >> n >> k;
	n -= k;
	if(n > k) swap(n,k);//看谁数量更多就放中心

	const int mod = 1e9 + 7;
	auto ksm = [&](int a,int b){//快速幂
		int res = 1;
		while(b){
			if(b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	};

	int ans = 1;
	ans = ksm(3,k - 1) % mod;
    //2-2/3-3有k-1条边
	ans = ans * ksm(4,n) % mod;
    //2-3/3-2有n条边
	ans = ans * ksm(4,(k - 1) * (k - 2) / 2) % mod;
    //2-2-2/3-3-3有(k-1)*(k-2)/2条边,因为有个点在中心
	ans = ans * ksm(6,(k - 1) * n) % mod;
    //2-2-3...有(k-1)*n条边
	ans = ans * ksm(6,n * (n - 1) / 2) % mod;
    //3-3-2...有n*(n-1)/2条边
	cout << ans << endl;
	return 0;
}

标签:周赛,int,++,cin,up,牛客,second,ans,Round
From: https://www.cnblogs.com/Kescholar/p/17600069.html

相关文章

  • 1853 Round 887 (Div. 2)
    Desorting定义一次操作为选定一个\(i\),令\(a_{1\simi}\)自增,\(a_{i+1\simn}\),自减,求使得整个序列无序的最小操作次数若序列一开始就无序,输出\(0\)否则找到相邻两数差值最小的位置,在这个位置不断使用操作,可以证明这是最优方案#include<bits/stdc++.h>usingna......
  • 1851 Round 888 (Div. 3)
    EscalatorConversations判断两人台阶是否为\(k\)的倍数且在\((0,m)\)内即可#include<bits/stdc++.h>usingnamespacestd;signedmain(){ intT; scanf("%d",&T); for(intn,m,k,H;T;--T){ scanf("%d%d%d%d",&n,&m,&a......
  • 1848 Round 885 (Div. 2)
    VikaandHerFriends给定一张网格图,Vika在\((x,y)\)处,她的\(k\)个朋友分别在\((x_{1\simk},y_{1\simk})\)处,每次所有人都必须移动到相邻各格子,询问Vika能否永远逃离她烦人的朋友考虑对格子进行黑白染色,每次移动一定会变换格子颜色,那么只有相同颜色的人才会碰......
  • 1855 Round 889 (Div. 2)
    DaltontheTeacher给定序列\(a_{1\simn}\),定义一次操作为交换序列中的某两个数,求使得\(\foralli,a_i\not=i\)的最少操作次数对于所有数据,\(n\leq10^5\)计算出\(a_i=i\)的位置数量\(sum\),若\(sum\)为偶数,则让其两两配对交换即可;否则会剩下一个数,在其他......
  • 牛客暑假多校 2023 第五场
    目录写在前面GDHCEI写在最后写在前面战犯在此。我宣布二周年这首是神。以下按个人向难度排序。G尺取法,右端点单调右移过程中右移调整左端点,使区间内每种数都至少出现1次,4出现至少\(k\)次即可。///*By:Luckyblock*/#include<cmath>#include<cstdio>#include<......
  • Educational Codeforces Round 152 (Rated for Div. 2)
    Preface经典秒完SB题然后开始坐牢1h,写了个E的假算法T在24个点就不管了打lol去了妈的怎么稍微难点的题就是想不到呢A.MorningSandwich签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>......
  • Codeforces Round 889 (Div. 2)
    CodeforcesRound889(Div.2)T1​ 思路:我们将\(i\nep_i\)的数量记下来,再判断这个数的奇偶性,如果为偶,那么答案就为这个数/2,如果为奇,那么就是这个数/2+1。T2​ 思路:我们枚举\(1\simn\),我们记录连续是\(n\)的因数的个数,如果不连续了就\(break\),答案就是个数......
  • Codeforces Round 885 (Div. 2)
    CodeforcesRound885(Div.2)A.VikaandHerFriends题目大意太长了click思路可以手动模拟一下,可以发现当两个人的\(x+y\)值就行相同的就能抓到了#include<bits/stdc++.h>usingnamespacestd;intmain(){intT;cin>>T;while(T--){......
  • Codeforces Round 887 (Div. 2)
    CodeforcesRound887(Div.2)A.Desorting题目大意给出一个长度为\(n\)的数组\(a\),可以执行这个操作任意次。选择一下标\(i\),使得\(a_{1...i}\)加上\(1\),\(a_{i+1...n}\)减少\(1\)。问最少几次操作使得数组\(a\)无序。思路首先如果\(a\)原本就无序的......
  • Codeforces Round 885 (Div. 2) 题解
    A.VikaandHerFriends看一下样例就可以发现,Vika以及她的朋友都不能走对角线,在这种情况下Vika和朋友的距离为偶数,且朋友一定追不上Vika所以直接判断Vika和朋友的距离是否都为偶数即可B.VikaandtheBridge显然贪心,枚举颜色,找到相邻距离最大的两块木板,记该距离为\(......