首页 > 其他分享 >牛客练习赛133

牛客练习赛133

时间:2025-01-10 21:32:55浏览次数:1  
标签:std 练习赛 string int cin 133 牛客 mp ans

A 万年沉睡的宝藏

题意:有一些岛和一些宝藏,都用字符串来描述,会有4个操作:给一个岛加一个宝藏,问这个岛有多少宝藏,某个宝藏是否在这个岛上,有多少岛上有至少一个宝藏。

用map存string和set就行了,注意特判没有这个岛的情况。

点击查看代码
void solve() {
    int q;
    std::cin >> q;
    std::map<std::string, std::set<std::string> > mp;
    while (q -- ) {
    	int op;
    	std::cin >> op;
    	if (op == 1) {
    		std::string s, t;
    		std::cin >> s >> t;
    		mp[s].insert(t);
    	} else if (op == 2) {
    		std::string s;
    		std::cin >> s;
    		int ans = mp.count(s) ? mp[s].size() : 0;
    		std::cout << ans << "\n";
    	} else if (op == 3) {
    		std::string s, t;
    		std::cin >> s >> t;
    		int ans = mp.count(s) ? mp[s].count(t) : 0;
    		std::cout << ans << "\n";
    	} else {
    		std::cout << mp.size() << "\n";
    	}
    }
}

B 完美主义追求者

题意:给你a和b,求a个点的二叉树有多少个本质不同的,对b取模。

猜了一下是a的阶乘个,不会证明。
因为a很大,无法算阶乘,但注意b只有1e6,当a<b时暴力,否则a>=b时因为因子乘了一个b,模数肯定是0.
(赛时写的python,以为要用高精度算阶乘,结果wa了一发,后来发现正确做法后只需要随便改一下就行了,所以还是python代码)

点击查看代码
import math

a, b = map(int, input().split());

if a < b:
	ans = 1
	for i in range(1, a + 1):
		ans = ans * i % b
	print(ans)
else:
	print(0)

C 异或与位移

题意:一个长度位n的数组a,和一个k,a的值在-k + 1到 k - 1之间,m个询问,给你一个二进制数y,它是由一个x变过来的:第i次变化中,如果\(a_i\) > 0就让x和x左移\(a_i\)位异或,否则和x右移\(a_i\)位异或。求这个x。

举个例子,对于一个二进制数abc(a, b, c等于0或1), 它左移2位等于110,那么就是c00 ^ abc = 110这是可以求出来abc的,先根据那几个0来确定后面几位,如何根据后面的数确定前面的数。右移一样的思路。

点击查看代码
void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++ i) {
    	std::cin >> a[i];
    }

    while (m -- ) {
    	std::string s;
    	std::cin >> s;
    	s = std::string(k - (int)s.size(), '0') + s;
    	bool flag = true;
    	for (int i = n - 1; i >= 0; -- i) {
			std::string t(k, '?');
    		if (a[i] > 0) {
    			for (int j = k - a[i]; j < k; ++ j) {
    				t[j] = s[j];
    			}

    			for (int j = k - a[i] - 1; j >= 0; -- j) {
    				if (t[j + a[i]] == '?') {
    					flag = false;
    					break;
    				}

    				t[j] = ((t[j + a[i]] ^ s[j]) & 1) + '0';
    			}
	    	} else {
	    		for (int j = 0; j < -a[i]; ++ j) {
	    			t[j] = s[j];
	    		}

	    		for (int j = -a[i]; j < k; ++ j) {
	    			if (t[j + a[i]] == '?') {
	    				flag = false;
	    				break;
	    			}

	    			t[j] = ((t[j + a[i]] ^ s[j]) & 1) + '0';
	    		}
	    	}

	    	if (t.find('?') != t.npos) {
	    		flag = false;
	    	}

	    	if (!flag) {
	    		break;
	    	}

    		s = t;
	    	// std::cout << s << "\n";
    	}

    	if (!flag) {
    		std::cout << -1 << "\n";
    		continue;
    	}

    	int p = s.find('1');
    	if (p == s.npos) { 
    		std::cout << "0\n";
    	} else {
    		std::cout << s.substr(p) << "\n";
    	}
    }
}

D 被拒绝在外的打卡

写麻了,每次wa一发后就发现了问题,前前后后de一个小时bug,最后还是没过,感觉应该还是思路的问题。
待补。

标签:std,练习赛,string,int,cin,133,牛客,mp,ans
From: https://www.cnblogs.com/maburb/p/18664754

相关文章

  • 2025.1.8 练习赛总结
    总览本文同步发表与:洛谷:https://www.luogu.com.cn/article/hdzdhnif。博客园:<>。打得不好,在赛时只做了A题。昨晚的睡眠使我刚好处于困和不困的叠加态,导致想题的时候脑子极乱。A:Gym103430F。B:CF578B。C:CF1407D。D:洛谷P11122。E:CF1208D。A-Gym103430F-X-Mag......
  • 牛客 NC20032 激光炸弹 二维前缀和
    #include<bits/stdc++.h>usingnamespacestd;inta[5010][5010];intpre[5010][5010];constintN=5e3;intmain(){ intn,m; cin>>n>>m; for(inti=0;i<n;i++) { intx,y,z; cin>>x>>y>>z; a[x][y]=z; } pre[0][0......
  • BHQ-3 acid|cas:1338332-66-3|BHQ-3酸
    BHQ-3acid,也被称为BHQ-3羧酸或黑洞猝灭剂3羧酸,是一种具有特别暗猝灭特性的多功能有机化合物。以下是对BHQ-3acid的详细介绍:一、基本特性英文名称:BHQ-3acidCAS号:1338332-66-3分子式:C33H35N6O2+分子量:547.68外观:深紫色粉末结构式:二、化学结构BHQ-3acid的分子中含有一个......
  • 《计算机组成及汇编语言原理》阅读笔记:p133-p159
    《计算机组成及汇编语言原理》学习第11天,p133-p159总结,总计27页。一、技术总结1.segment(1)定义Broadlyspeaking,acontiguoussectionofmemory.Morespecifically,asectionofmemoryreferencedbyoneofthesegmentregistersofthe80x86family.Theme......
  • 2024牛客寒假算法基础集训营2(个人训练)
    TokitsukazeandCats思路1对没有只猫我们只需要枚举它的四个方向,看一下有没有猫,如果有他们就会公用一条边,需要注意的是这个方法会重复计算同一条共用的边,最后除2就行代码1#include<bits/stdc++.h>typedefstd::pair<int,int>pii;#defineINF0x3f3f3f3f#defineMOD......
  • 牛客小白月赛108 题解(出题人题解)
    比赛链接A$y=0$的情况,答案是$0$。$y>0$的情况,我们把每两次按钮先捆绑在一起,算出$k=\lceil\frac{y}{x+1}\rceil$。然后判断是否可以在前$2k-1$次就完成任务,即判断$(k-1)(x+1)+1\gey$。如果上式成立,答案是$2k-1$,否则是$2k$。B提供一个比较暴力的做法。对于......
  • [题解]P1333 瑞瑞的木棍
    P1333瑞瑞的木棍我们将颜色看作节点,每个木棍左右的两个颜色之间连接无向边。可以用并查集维护连通性,每添加一条边\((u,v)\)就合并\(u,v\)所在集合,最终所有节点都在一个集合中\(\iff\)该图联通。在回顾下无向图存在欧拉通路的判定条件,满足其一即可:无向图是欧拉图\(\iff\)非零......
  • P11331 题解
    blog。写了好几天,人都要死了。提供一个不同的切入口,方便大家理解这个分段是在干嘛,以及一个更容易的线段树DS。题解一堆废话,大家看看就行(\(O(N^3)\)先把\(a_i\ne-1\)且无论如何无法成为前缀max的位置ban掉。由于答案只与premax的位置有关,于是设\(dp_{i,j}\)表示确定......
  • 003. 字符串的展开(牛客NOIP2007)
    003.字符串的展开(牛客NOIP2007)题目描述在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串中,含有类似于“d-h”或“4-8”的子串,我们就把它当作一种简写,输出时,用连续递增的字母或数字串替代其中的减号,即,将上面两个子串分别输出为“de......
  • 牛客 NC16644 字符串展开 模拟
    #include<bits/stdc++.h>usingnamespacestd;intp1,p2,p3;strings;booljudge_char(charx,chary){ if(x>='a'&&x<='z'&&y>='a'&&y<='z') return1; return0;}booljud......