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

Codeforces Round 966 (Div. 3) VP

时间:2024-08-15 11:06:21浏览次数:12  
标签:966 int auto void cin VP vector solve Div

A. Primary Task

枚举所有情况即可

void solve(){
	string s;
	cin >> s;

	if (s.substr(0, 2) != "10" || s.size() < 3 || s[2] == '0' || (s.size() < 4 && s[2] < '2')) {
		cout << "NO\n";
	}
	else {
		cout << "YES\n";
	}
}

B. Seating in a Bus

简单模拟题

void solve(){
	int n;
	cin >> n;

	vector<int> a(n + 2);
	bool ok = true;
	for (int i = 1; i <= n; ++i) {
		int t;
		cin >> t;
		if (!ok) {
			continue;
		}
		if (i == 1) {
			a[t] = 1;
		}
		else {
			if (a[t - 1] || a[t + 1]) {
				a[t] = 1;
			}
			else {
				ok = false;
			}
		}
	}

	cout << (ok ? "YES\n" : "NO\n");
}

C. Numeric String Template
一时没想到低空间复杂度解法,直接上了map+并查集

void solve(){
	int n;
	cin >> n;

	vector<int> a(n);
	for (auto& x : a) {
		cin >> x;
	}

	int m;
	cin >> m;

	bool ok = false;
	map<int, vector<int>> mapp;

	for (int i = 0; i < n; ++i) {
		mapp[a[i]].push_back(i);
	}

	Dsu dsu(n + 1);
	for (const auto&[x, y] : mapp) {
		for (int i = 0; i < (int)y.size() - 1; ++i) {
			dsu.unionSet(y[i], y[i + 1]);
		}
	}

	for (int i = 0; i < m; ++i) {
		string s;
		cin >> s;

		if (s.size() != n) {
			cout << "NO\n";
			continue;
		}
		mapp.clear();
		for (int i = 0; i < n; ++i) {
			mapp[s[i]].push_back(i);
		}
		Dsu dsu2(n + 1);
		for (const auto&[x, y] : mapp) {
			for (int i = 0; i < (int)y.size() - 1; ++i) {
				dsu2.unionSet(y[i], y[i + 1]);
			}
		}

		bool same = true;
		for (int i = 0; i < n; ++i) {
			if (dsu.findSet(i) != dsu2.findSet(i)) {
				same = false;
				break;
			}
		}
		cout << (same ? "YES" : "NO") << '\n';
	}

}

D. Right Left Wrong

贪心问题,策略应该是让数字尽可能被多次数的操作,于是进行LR匹配即可

void solve(){
	int n;
	cin >> n;

	vector<int> a(n);
	for (auto& x : a) {
		cin >> x;
	}

	string s;
	cin >> s;

	long long ans = 0;
	vector<pair<int, int>> pairs;

	int l = -1;
	int r = n;
	while (l <= r) {
		size_t ll = s.find_first_of('L', l + 1);
		size_t rr = s.find_last_of('R', r - 1);
		if ((ll == s.npos) || (rr == s.npos)) {
			break;
		}
		if (ll <= rr) {
			pairs.emplace_back(ll, rr);
		}
		l = ll;
		r = rr;
	}

	vector<long long> pref(n + 1);
	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + a[i];
	}


	for (const auto&[x, y] : pairs) {
		ans += (pref[y + 1] - pref[x]);
	}

	cout << ans << '\n';

}

E. Photoshoot for Gorillas

跟D的出题意愿差不多,依然是统计出现次数最多的格子,不过是在二维中
二维差分即可
这里做的时候卡住了,第一次写二维差分,多减了一次权值没有补回来

void solve(){
	int n, m, k;
	cin >> n >> m >> k;

	int q;
	cin >> q;
	vector<int> a(q);
	for (auto& x : a) {
		cin >> x;
	}

	vector<vector<int>> grid(n + 2, vector<int>(m + 2));
	for (int i = 1; i + k <= n + 1; ++i) {
		for (int j = 1; j + k <= m + 1; ++j) {
			grid[i][j] ++;
			grid[i][j + k] --;
			grid[i + k][j] --;
			grid[i + k][j + k] ++;
			//for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cout << grid[i][j] << " \n"[j == m];
			//cout << endl;
		}
	}

	multiset<int> sett;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			grid[i][j] += (grid[i][j - 1] + grid[i - 1][j] - grid[i - 1][j - 1]);
			int t = grid[i][j];
			sett.insert(grid[i][j]);
			//for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cout << grid[i][j] << " \n"[j == m];
			//cout << endl;
		}
	}

	long long ans = 0;
	sort(a.rbegin(), a.rend());

	auto it = sett.rbegin();
	for (int i = 0; i < q; ++i) {
		ans += 1ll * a[i] * (*it);
		it ++;
		if (it == sett.rend()) {
			break;
		}
	}

	cout << ans << '\n';

}

标签:966,int,auto,void,cin,VP,vector,solve,Div
From: https://www.cnblogs.com/yxcblogs/p/18360492

相关文章

  • Codeforces Round 966 (Div. 3)
    A-PrimaryTask给一个数\(x\),判断其是否形如\(\overline{ab}\)满足\(a=10,b\ge2\)且无前导零。模拟判断即可。code#include<bits/stdc++.h>usingnamespacestd;constintmaxn=3e5+3;intT;stringn;voidsolve(){ cin>>n; if((n=="1"||n=="10......
  • IPSec VPN
    目录一、背景二、简介1、概述2、协议架构 ①安全协议: ②封装模式: ③安全联盟(SA): ④互联网秘钥交换协议(IKE): 阶段一:IKESA 阶段二:IPSecSA3、特点三、执行流程 数据包出站: 数据包入站:四、基本配置 实验要求 IPSec配置前的准备 思科厂商......
  • MX Weekly 赛时/VP 记录
    感觉题目质量比较高,所以挖了个坑((。X2前三题简单不写洛谷-P10855傻逼赛时想出两种正确思路都他妈的没仔细想,真糖丸了不妨将题目中要求的式子化简。\[\begin{equation}\begin{split}\sum\limits_{i=1}^n\sum\limits_{j=1}^i\gcd(j,i\oplusj)^k&=\sum\limits_{j=1}^n\su......
  • DeiT-LT:印度科学院提出针对长尾数据的`DeiT`升级模型 | CVPR 2024
    DeiT-LT为ViT在长尾数据集上的应用,通过蒸馏DIST标记引入CNN知识,以及使用分布外图像并重新加权蒸馏损失来增强对尾类的关注。此外,为了减轻过拟合,论文建议用经过SAM训练的CNN教师进行蒸馏,促使所有ViT块中DIST标记学习低秩泛化特征。经过DeiT-LT的训练方案,DIST标记成为尾类的专家,分......
  • StarNet:关于 Element-wise Multiplication 的高性能解释研究 | CVPR 2024
    论文揭示了staroperation(元素乘法)在无需加宽网络下,将输入映射到高维非线性特征空间的能力。基于此提出了StarNet,在紧凑的网络结构和较低的能耗下展示了令人印象深刻的性能和低延迟来源:晓飞的算法工程笔记公众号论文:RewritetheStars论文地址:https://arxiv.org/abs/240......
  • Codeforces Round 966 (Div. 3)
    Abstract第二次打CodeForce。A.PrimaryTaskIdea签到题。意思就是说给一个字符串,要你判断一下前两位是不是10,除去前两位后后面的部分是不是一个大于等于2的数(不能有前导零)。Code#include<bits/stdc++.h>usingnamespacestd;voidsolve(){stringtext;......
  • Codeforces Round 947 (Div. 1 + Div. 2)
    [传送门](Dashboard-CodeforcesRound947(Div.1+Div.2)-Codeforces)###A.枚举一个位置,把他前面和后面反转一下判断就行。###B.找到最小的数和最小的不是它的倍数的数当作$i$和$j$,判断合不合法即可。###C.不知道怎么就模出来了操作长度一定小于等于3,然后......
  • Codeforces Round 946 (Div. 3)
    ###G.一眼看上去很想个背包,然后发现好像不大能做。考虑反悔贪心。对于当前的$c_i$,如果到现在攒的钱足够买这个,那就直接买了它。如果钱不够,就从之前的买过的里面把一个最大的给退掉,然后买这个,优先队列维护即可。```c++#include<bits/stdc++.h>#defineintlonglongu......
  • Codeforces Round 964 (Div. 4)
    ###A.```c++#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+7;voidsolve(){  intx;  cin>>x;  cout<<x/10+x%10<<endl;}intmain(){  intT;  cin>>T;  while(T--)solve();......
  • DRM:清华提出无偏差的新类发现与定位新方法 | CVPR 2024
    论文分析了现有的新类别发现和定位(NCDL)方法并确定了核心问题:目标检测器往往偏向已知的目标,忽略未知的目标。为了解决这个问题,论文提出了去偏差区域挖掘(DRM)方法,以互补的方式结合类无关RPN和类感知RPN进行目标定位,利用未标记数据的半监督对比学习来改进表征网络,以及采用简单高效的m......