首页 > 其他分享 >CF894 div3

CF894 div3

时间：2023-08-26 23:11:52浏览次数：39  
标签：itl CF894 int div3 cin -- include itr

A. Gifi Carpet

给一个n行m列的字符矩阵，问能否找到四列，第一列中要有字符'v' , 第二列要有字符'i' , 第三列要有字符'k',第四列要有字符'a'.

\(1 <= n,m <= 20\)

题解

签到题。

#include<iostream>
using namespace std;
char s[30][30];

void Solve()
{
	int n , m , a , b , c , d;
	cin >> n >> m;
	for(int i = 1 ; i <= n ; ++i)
		cin >> (s[i] + 1);
	a = b = c = d = 0;
	for(int i = 0 + 1 ; i <= m ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
			if(s[j][i] == 'v') { a = i; break; }
		if(a) break;
	}
	for(int i = a + 1 ; i <= m ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
			if(s[j][i] == 'i') { b = i; break; }
		if(b) break;
	}
	for(int i = b + 1 ; i <= m ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
			if(s[j][i] == 'k') { c = i; break; }
		if(c) break;
	}
	for(int i = c + 1 ; i <= m ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
			if(s[j][i] == 'a') { d = i; break; }
		if(d) break;
	}
	if(a && b && c && d)
		cout << "YES" << '\n';
	else
		cout << "NO" << '\n';
}

int main()
{
	int T; cin >> T; while(T--) Solve(); return 0;
}

B.Sequence Game

初始有一个长度为m的序列A，然后经过一种变换之后得到序列B。

变换规则如下。

​ 初始B为空，然后第一步写下（加入）\(a_1\)

​ 然后对于\(a_i ， (2<=i<=m)\)，如果\(a_i >= a_{i-1}\)则写下。

例如 \(A = [4 , 3 , 2 , 6 , 3 , 3]\)，则\(B = [4,6,3]\)

其中4是第一个，所以写下。

其中6是A中的第四个元素，它大于前面的2，所以写下。

其中3是A中的最后一个3，它等于前面第5位上的3，所以写下。

现在的情况是，给出序列B，然后构造出一个序列A，使得A变换之后为B。 输出任意一个即可。

假设B的长度为n，则要求构造出的A序列长度m不得超过n的两倍。

\(1 <= n <= 2e5 , 1 <= a_i <= 1e9\)

题解

对于\(b_i >= b_{i-1}\)可以直接抄写在A中。

而如果\(b_i < b_{i-1}\)可以在第i个位置前面加一个等于\(b_i\)的数字。

例如对于\(B = [4 , 6 , 3]\) 构造出的\(A = [4 , 6 , 3 , 3]\)

#include<iostream>
using namespace std;
const int N = 2e5+10;
int B[N] , A[N];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T , n , m;
	cin >> T;
	while(T--)
	{
		cin >> n; m = 1;
		for(int i = 1 ; i <= n ; ++i) cin >> B[i];
		A[1] = B[1];
		for(int i = 2 ; i <= n ; ++i)
		{
			if(B[i] >= B[i-1])
				A[++m] = B[i];
			else
				A[++m] = B[i] , A[++m] = B[i];
		}
		cout << m << '\n';
		for(int i = 1 ; i <= m ; ++i)
			cout << A[i] << ' '; cout << '\n';
	}
	return 0;
}

C.Flower City Fence

有n个木块，从左到右依次排列，其中第i个木块的高度为\(a_i\).现在要讲这些木块翻转过来，问翻转过后的图形和之前是否一样。

所谓翻转就是从左到右，将木块放倒（旋转90度），左端对齐，依次垒高。

像这个图就是翻转前是\([5 , 4 , 3 , 2 , 1]\) ，翻转后最下方的是原来最左侧的，最上方的是原来最右侧的。

这个就是翻转前后图形一致的。

这个例子翻转前是\([4 , 2 , 1]\)，翻转之后就是\([3 , 2 , 1 , 1]\)所以是不一致的。

另外这些木块的高度是不增的，所以不用担心反转之后出现下面一层比上面一层短的情况。

\(1 <= n <= 2e5 , 1 <= a_i <= 1e9\)

题解

仔细观察一下，翻转之后坐标为i的高度应该是原序列中有多少大于等于i本身的数字个数。

#include<algorithm>
#include<iostream>
using namespace std;
const int N = 2e5+10;
int A[N] , B[N] , t[N];

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T , n , tmp , F;
	cin >> T;
	while(T--)
	{
		cin >> n; F = 1;
		for(int i = 1 ; i <= n ; ++i)
			cin >> A[i];
		for(int i = 1 ; i <= n ; ++i)
			B[i] = A[i];
		sort(B + 1 , B + 1 + n);
		for(int i = 1 ; i <= n ; ++i)
		{
			tmp = lower_bound(B + 1 , B + 1 + n , i) - B;
			if(A[i] != n - tmp + 1)
			{
				F = 0;
				break;
			}
		}
		cout << (F ? "YES" : "NO") << '\n';
	}
	return 0;
}

D.Ice Cream Balls

制作一个双筒冰激凌要用到两个冰球。冰球的种类可以分为1，2，3，4。。。也就是无限多种。现在问需要准备最少多少个冰球使得能够做出的双筒冰激凌的种类数恰好为n。 两个冰球可以选择相同的。

\(\{1 , 2\}\) 与 \(\{1 , 3\}\) 认为是两种方案。

\(\{1 , 2\}\) 与 \(\{2 , 1\}\) 认为是一种方案。

\(1 <= n <= 1e18\)

题解

首先要注意两个关键，一是问的是多少个冰球而非多少种。而是可拼凑的种类数要恰好为n。

能够拼凑数量最多的做法就是选择的冰球两两不同类，如果选择了k个，那么也就是有k种冰球。

凑出来的双筒冰激凌数量就是\(k * (k - 1) / 2\) 种。

但是这样很有可能无法恰好有n种，这时考虑多选一个第i种，那么方案中就会多出\(\{i , i\}\) 这样1个。

而且如果i再多也不会增加方案数了。

最终的方法就是先选不同的，直到再选的话\(k * (k - 1) / 2\)就会大于n。

然后再用之前已经选过的凑足n，需要\(n - k * (k - 1) / 2\)个。

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; 
	long long n , m;
	cin >> T;
	while(T--)
	{
		cin >> n; m = sqrt(n * 2.0);
		while((m + 1) * m / 2 <= n && (m + 1) * m > 0) m++;
		cout << m + n - m * (m - 1) / 2 << '\n';
	}
	return 0;
}

E.Kolya and Moive Theatre

有n场电影即将上映，一天上映一场。而每场电影都有一个欢乐值\(a_i \ \ (-1e9 <= a_i <= 1e9)\),若观看电影就会获得相应的欢乐值。

同时还有一个规则，如果之前看过电影，那么下一个观看的电影的欢乐值就会减少\(d * cnt\)其中d是一个给定的值（正数），cnt是两场电影之间的天数。

最多可以看m场电影。

而在这n场电影的前一天，看过了一场电影。相当于是在第0天看过了一场电影。（这一场不计入m中，但要计算\(d * cnt\) ）

\(1 <= n <= 2e5\)

题解

可以发现，所有\(d * cnt\)的和取决于最晚的一场电影。如果最晚的电影实在第T天，那么总的\(d * cnt = d *T\)所以可以枚举最后一场电影的时间，然后从前面的电影中选出最大的m个（或者少于m个）。

具体一点的话，可以用一个小根堆来维护。小根堆中的元素表示已经选择的元素，新来一个元素时，如果小根堆未满m-1，则直接加入。

如果满了，就先弹出原本的最小的，然后加入当前元素。

这里也可以先加入当前元素，再弹出最小的。 关于是否要强制选择当前元素的细节部分可以稍稍琢磨一下。

#include<iostream>
#include<queue>
using namespace std;
const int N = 2e5+10;
int A[N];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T , n , m , d;
	long long Answer , Sum;
	priority_queue<int , vector<int> , greater<int> > Q;
	cin >> T;
	while(T--)
	{
		cin >> n >> m >> d; Answer = 0ll; Sum = 0ll;
		for(int i = 1 ; i <= n ; ++i)
			cin >> A[i];
		for(int i = 1 ; i <= n ; ++i)
		{
			if(A[i] < 0) continue;
			if(Q.size() < m) 
				Q.push(A[i]) , Sum += A[i];
			else
			if(Q.top() < A[i])
				Sum -= Q.top() , Q.pop() ,
				Sum += A[i] , Q.push(A[i]);
			Answer = max(Answer , Sum - 1ll * d * i);
		}
		cout << Answer << '\n';
		while(Q.size()) Q.pop();
	}
	return 0;
}

F.Magic Will Save the World

有n个怪兽，每个怪兽都有相应的体力值\(a_i\),当体力值为0时，怪兽死亡。

每秒钟可以获得w个单位的水系能量和f个单位的火系能量（初始都为0）.

对于一个怪物，可以使用水系能量或者火系能量将其打死，消耗等于怪兽体力值的能量。

只能是水系或者火系，不能两者混合。

问最少需要多长时间才能消灭所有的怪兽。

\(1 <= n <= 100 , \ \ \ 1 <= a_i <= 1e4 , \ \ 1 <= w , f <= 1e9\)

题解

二分答案。

将一部分分给水系能量，然后看另一部分的和是否小于等于火系能量的和。

然后反着再来一遍。

可以先用dp预处理出来这些怪物的体力值可以组合成哪些和。

具体见代码，代码更简洁。

#include<algorithm>
#include<iostream>
using namespace std;
const int N = 105;
int Sum;
int s[N] , dp[1000005];

bool Check(int n , int w , int f , int k)
{
	int flag = 1;
	long long W = 1ll * w * k;
	long long F = 1ll * f * k;
	
	if(W >= Sum || F >= Sum) return true;
	if(W + F < Sum) return false;

	// 可以被W 水系能力处理，并且剩下的部分可以交给火系能量
	for(int i = W ; i >= 0 && Sum - i <= F ; --i)
		if(dp[i]) return true;

	// 同理
	for(int i = F ; i >= 0 && Sum - i <= W ; --i)
		if(dp[i]) return true;
	return false;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T , n , w , f , l , r , mid; 
	cin >> T;
	while(T--)
	{
		cin >> w >> f >> n; Sum = 0;
		for(int i = 1 ; i <= n ; ++i) cin >> s[i] , Sum += s[i];
		
		// 做的时候没有预处理，但是这题的数据小，所以也算是正确的复杂度。
		// 写题解的时候才发现QAQ，不亏是div3。
		// 没有预处理 1731ms ， 由于处理 156ms。
		for(int i = 1 ; i <= Sum ; ++i) dp[i] = 0;
		dp[0] = 1;
		
		for(int i = 1 ; i <= n ; ++i)
		{
			for(int j = Sum ; j >= s[i] ; --j)
				dp[j] |= dp[j - s[i]];
		}
		
		l = 1; r = Sum;
		while(l < r)
		{
			mid = (l + r) >> 1;
			if(Check(n , w , f , mid)) r = mid; else l = mid + 1;
		}
		cout << l << '\n';
	}
	return 0;
}

G.The Great Equalizer

给出一个序列。循环执行如下操作。

  1. 如果序列中只有一个数字，结束并返回这个数字。
  2. 将序列从小到大排序并去重，设去去重之后有n个元素。
  3. 则让第一个元素（最小的）加上n，第二个加上n-1，……，最后一个（最大的）加上1.

然后，现在会有一些操作，如将i个元素修改成val。要求对于每个操作之后输出序列变换的结果。

\(1 <= n <= 2e5 , 1 <= a_i <= 1e9\)

输入样例

3
2 4 8
3
1 6
2 10
3 1

输出样例

10 12 15

题解

每次操作（由序列计算最终值的时候）之后相邻元素的差值都会减少一。

所以操作次数就等于排完序之后相邻元素的差值的最大值。

然后还有一点就是最大值一直是最大值。

因为最大值和次大值最少差1，而每次两者之间的差距只会缩小一，直至相等。所以最大值是不变的。

而最终的答案就是最大值加上操作数。

所以要维护排序之后的相邻元素的最大值。

这里使用了两个multiset来维护，一个是S，用来维护原序列，方便找到相邻元素的差值。

另一个是R，用来维护相邻元素的差值。

当有元素发生“有无”的变化时，根据其在S中的状况，相应删减R中的元素。

#pragma GCC optimize(2)
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
const int N = 2e5+10;
int A[N] , B[N];

multiset<int>::iterator F;
inline void Del(multiset<int> &R , int val)
{
	F = R.lower_bound(val);
	if(F != R.end())
		R.erase(F);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T , n , Q , x , y , m;
	multiset<int> S , R;
	multiset<int>::iterator itl , itr; 
	cin >> T;
	while(T--)
	{
		/*
			S维护原序列，方便找到相邻元素的差值。
			R维护相邻元素的差值。
		*/
		cin >> n;
		for(int i = 1 ; i <= n ; ++i) cin >> A[i];
		for(int i = 1 ; i <= n ; ++i)
			S.insert(A[i]);
		
		for(int i = 1 ; i <= n ; ++i) B[i] = A[i];
		sort(B + 1 , B + 1 + n);
		m = unique(B + 1 , B + 1 + n) - B - 1;

		for(int i = 1 ; i < m ; ++i)
			R.insert(B[i+1] - B[i]);

		cin >> Q;
		for(int i = 1 ; i <= Q ; ++i)
		{
			cin >> x >> y;

			itl = S.lower_bound(A[x]);
			itr = S.upper_bound(A[x]);

			// 这个判断等价于 A[x] 这个元素在S中只有一个
			if((++itl) == itr)
			{
				--itl;
				if(itl != S.begin() && itr != S.end())
				{
					--itl;
					Del(R , A[x] - *itl);
					Del(R , *itr - A[x]);
					R.insert(*itr - *itl); 
					// 删完之后会产生一个新的
					// 如1 2 3 删除2之后会产生 1 3这样差值
				}
				else
				if(itl != S.begin() && itr == S.end())
				{
					--itl;
					Del(R , A[x] - *itl);
				}
				else
				if(itl == S.begin() && itr != S.end())
				{
					Del(R , *itr - A[x]);
				}				
			}

			S.erase(S.lower_bound(A[x]));
			
			// 这里是判断y在S中没有出现
			itl = S.lower_bound(y);
			if((itl == S.end()) || (*itl != y)) // count() 复杂度
			{
				itl = S.lower_bound(y);
				itr = S.upper_bound(y);
				
				if(itl != S.begin() && itr != S.end())
				{
					--itl;
					R.insert(y - *itl);
					R.insert(*itr - y);
					Del(R , *itr - *itl);
				}
				else
				if(itl != S.begin() && itr == S.end())
				{
					--itl;
					R.insert(y - *itl);
				}
				else
				if(itl == S.begin() && itr != S.end())
				{
					R.insert(*itr - y);
				}				
			}

			S.insert(y); A[x] = y;
			cout << *(--S.end()) + (R.empty() ? 0 : *(--R.end())) << ' ';
		}
		cout << '\n'; S.clear(); R.clear();
	}
	return 0;
}

			// cout << "RQ-A" << '\n';
			// for(int j = 1 ; j <= n ; ++j)
			// 	cout << A[j] << ' ';
			// cout << '\n';
			// cout << "RQ-S" << '\n';
			// for(auto tmp:S)
			// 	cout << tmp << ' ';
			// cout << '\n';
			// cout << "RQ-T" << '\n';
			// for(auto tmp:R)
			// 	cout << tmp << ' ';
			// cout << '\n';
			// cout << '\n';

			// cout << "RQ\n";
			// for(auto val:S)
			// 	cout << val << ' ';
			// cout << '\n';

标签：itl,CF894,int,div3,cin,--,include,itr
From： https://www.cnblogs.com/sybs5968QAQ/p/17659670.html

相关文章

  • codeforces 891 (div3)857E - Power of Points
    E.点的力量每个测试限时2秒每个测试限制内存为256兆字节输入以标准格式输入输出以标准格式输出给定n个具有整数坐标x1,…xn的点，这些点位于数线上。对于某个整数s，我们构建段[s,x1]，[s,x2]，…，[s,xn]。注意，如果xi<s，则段将类似于[xi,s]。段[a,b]覆盖了所有整数点a，a+1，a+2，…，b。......
  • CF div3 883
    题目链接E2按值域分治的技巧前置:\(f(k,n)=1+k+k^2+...+k^n\)\(①\):假设答案最终的\(n=2\),对于\(1+k+k^2\),我们在\([2,10^9]\)的范围二分\(k\)即可\(②\):假设答案最终的\(n>2\),那么形式至少是\(1+k+k^2+k^3......
  • Codeforces Round 878 (Div3）
    B.BinaryCafe\(1\leqn,k\leq10^9\)题解：思维考虑两种情况第一种：钱足够多，每种咖啡都可以买的情况下，答案为\(2^k\)第二种：钱不够多，因为任一面值的钱数都有唯一的二进制表达方式，所以答案为\(n+1\)所以我们不妨先判断一下\(2^k\)有没有超过\(10^9\)，如果超过了说明钱......
  • Codeforces 874 div3 (A-G)
    Codeforces874div3A题意计算每两个相邻字符的不同种类B题意重排一个数组b，使得\(|a_i-b_i|\leqk\)思路根据相对大小去一一对应,这样每个位置的绝对值最小，数据保证有解代码voidsolve(){ cin>>n>>k; for(inti=1;i<=n;i++)cin>>a[i].first,a[i].second=i; for(in......
  • Codeforces Round 642 (Div3）
    K-periodicGarland给定一个长度位\(n\)的\(01\)串，每次操作可以将\(1\)变为\(0\)或者将\(0\)变为\(1\)，现在你需要通过操作使得所有\(1\)之间的距离为\(k\)，求最少的操作次数，注意全为\(0\)也算\(1<=n<=1e6,1<=k<=n\)\(dp\)/贪心:最大子段和思想方法一：\(dp\)\(O(n)\)状......
  • JUDDIV3 部署
    JUDDIV3部署了2天了，不用脑子的集成版就下了，用脑子的dist版怎么都不知道。哪个朋友知道一定要告诉我啊！09的那家伙算是网络传人了，写了一片就NND百度疯......
  • juddiv3 client publisher代码
    packagejuddiv3admin.juddiv3;importjava.util.ArrayList;importjava.util.List;importjuddiv3admin.gui.GUI;importorg.apache.juddi.api_v3.*;import......
  • juddiv3 tmodel的代码
    环境：juddiv3+tomcat6.0+MySQL5.1+MyEclipse7.5WSDL在UDDI中的注册：    我们有两种方法和UDDI进行通信：   一、用soapui工具直接编写SOAP消息和UDDI进行......
  • CF855 Div3 VP 游记
    比赛链接好长时间不写博文了甚至快忘记了（今天水一发Div3游记，在Div4比赛之前。第一次VP，当然得选一个简单点的了，打了50分钟多一点。排名不错，400多。$T1$：开始时......
  • codeforces 598 div3 Minimize the Permutation（贪心找规律）
    题目大意：有n个排列数。现在定义操作：交换第i和i+1个元素。我们对每个i位置只能操作一次。问经过这种操作后，我们最少能够得到的字典序序列是多少。解题思路：我们贪心从小到大选......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99