s.shin / notes
← 所有笔记
算法题目//4 分钟阅读

cf（codeforces）#784 div4 A-H

cf #784 A-H 详细讲解

# Codeforces# 模拟# 贪心# 算法题

A题

  • 连写个div4 都这么困难，上分之路相当艰难啊😔
    题目很简单直接上代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	while (n--)
	{
		int rat;
		cin >> rat;
		if (rat >= 1900)
			cout << "Division 1" << endl;
		else if (rat >= 1600 && rat <= 1899)
			cout << "Division 2" << endl;
		else if (rat >= 1400 && rat <= 1599)
			cout << "Division 3" << endl;
		else if (rat <=1399)
			cout << "Division 4" << endl;
	}
	return 0;
}

B题

  • 题目大意：判断数组a中有没有出现至少三次的数，如果有就输出任意满足条件的数，如果没有就输出-1。
  • 思考：不把数存入数组中，而是每次输入一个数就在数组的对应位置加1，既数组中存放的是每一个该下标元素出现的次数。之后遍历数组寻找满足条件的元素，既然输出任意数那就输出第一个满足条件的数。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int a[maxn];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		int flag = 0;
		memset(a, 0,sizeof(a));
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			int x;
			cin >> x;
			a[x] += 1;
		}
		for (int i = 1; i <= n; i++)
		{
			if (a[i] >= 3)
			{
				cout << i<<endl;
				flag = 1;
				break;
			}
		}
		if(flag!=1)
			cout << "-1" << endl;
	}
	return 0;
}

C题

  • 题目大意：给定一个数组和两种操作，第一种操作是将所有下标为奇数的数组元素+1；第二种操作是将所有下标为偶数的数组元素+1，如果在执行任意操作后可以将该数组的所有元素奇偶性统一，则输出“YES”否则输出“NO”。
  • 思考：奇数下标和偶数下标的数组元素分开操作，如果有一组存在奇偶性不同的元素则输出“NO”，否则输出“YES”。
    没有一次ac的原因：判断为“NO”之后continue了导致后面的数没有输入完毕。
    修改后ac代码：
#include<bits/stdc++.h>
using namespace std;
int a[60];
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n;
		int flag1 = 0, flag2 = 0;
		bool answer = true;
		memset(a, 0, sizeof(a));
		scanf("%d", &n);   //每次循环记得把数据初始化
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			if (i % 2 == 0)   //对下标为偶数的数组元素进行处理
			{
				if (a[i] % 2 == 0 && flag1 == 0)  //以第一个元素的奇偶性作为标准定性
					flag1 = 1;
				else if (a[i] % 2 != 0 && flag1 == 0)
					flag1 = 2;
				else if (a[i] % 2 == 0 && flag1 == 2)
				{
					answer = false;
				}
				else if (a[i] % 2 != 0 && flag1 == 1)
				{
					answer = false;
				}
			}
			else   //对下标为奇数的数组元素进行操作，与上面类似
			{
				if (a[i] % 2 == 0 && flag2 == 0)
					flag2 = 1;
				else if (a[i] % 2 != 0 && flag2 == 0)
					flag2 = 2;
				else if (a[i] % 2 == 0 && flag2 == 2)
				{
					answer = false;
				}
				else if (a[i] % 2 != 0 && flag2 == 1)
				{
					answer = false;
				}
			}
		}
		if (answer)
			printf("YES\n");
		else
			printf("NO\n");
	}
}

D题

  • 题目大意：可以将相邻的两种字符变成BR或者RB，给定一串字符，判断是否可以将一串W字符变为所给字符串。
  • 思考：对于一串‘W’字符来说，可以将其变为任何同时含‘R’和‘B’字符的字符串。所以可将‘W’当成分隔点，判断在两个‘W’之间的字符串是否同时存在两种字符，如果只存在一种字符则输出“NO”。要留心两种情况，一种是给定字符串全为‘W’的字符串，一种是分段后最后一段字符串不以‘W’结尾。
#include<bits/stdc++.h>
using namespace std;
int t, n;
string s;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);	
	cin >> t;
	while (t--)
	{
		cin >> n;
		cin >> s;
		int r = 0, b = 0,flag=0;
		for (int i = 0; i < n; i++)
		{
			if (s[i] == 'B')
			{
				b++;      //用‘b’和‘r’来统计‘B’和‘R’的个数
			}
			else if (s[i] == 'R')
				r++;          
			else          //其中一个为0另一个不为0则输出“NO”，为什么不是其中一个为0或者另一个为0呢？要排除全为‘W’的情况。
			{
				if (b == 0 && r != 0)
				{
					cout << "NO" << endl;
					flag = 1;
					break;
				}
				if (r == 0 && b != 0)
				{
					cout << "NO" << endl;
					flag = 1;
					break;
				}
				b = 0, r = 0;
			}
		}
		if (flag == 0) //因为最后一段字符串可能不以‘W’结尾所以要再来一次。
		{
			if (b == 0 && r == 0) //已经结尾了最后都是‘W’
			{
				cout << "YES" << endl;
				flag = 1;
			}
			else if (b == 0 || r == 0)
			{
				cout << "NO" << endl;
				flag = 1;
			}
			if(flag==0)
				cout << "YES" << endl;
		}
	}
	return 0;
}

E题

  • 题目大意：给定n个长度为2的字符串，由小写的拉丁字母’a’到’k’组成，输出i<j且第i个字符串和第j个字符串仅在一个位置不同的索引对(i,j)的个数。答案可能不适合 32 位整数类型，因此您应该使用 64 位整数（如C++中的long long）以避免整数溢出
  • 思考：其实不用管i<j这个条件，因为如果i>j换个位置就行了。题目的意思就能理解成避免重复，比如（ab，aa）不能换成（aa，ab）再算作一次。（注意同一个字符串可能出现多次）那这道题就很简单了，a-k有11个字符，我用一个二维数组代表每两个字符，比如说aa就是a[0][0]然后每次输入的时候在对应的位置加一，同时判断之前的数组和这次输入的字符串只有一个字符不同的个数，累加。
#include<bits/stdc++.h>
using namespace std;
int a[12][12];
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		long long ans = 0;
		cin >> n;
		memset(a, 0, sizeof(a));  //每次循环初始化
		while (n--)
		{
			string s;
			cin >> s;
			for (int i = 0; i < 11; i++)
			{
				if (a[s[0] - 'a'][i] != 0 && i != s[1] - 'a')    //先固定第一个字符
					ans += a[s[0]-'a'][i];
				if (a[i][s[1] - 'a'] != 0 && i != s[0] - 'a')  //再固定第二个字符，每次要确保不能重复
					ans += a[i][s[1] - 'a'];
			}
			a[s[0] - 'a'][s[1] - 'a']++; //标记
		}
		cout << ans << endl;
	}
	return 0;
}

F题

  • 题目大意：桌子上从左往右摆放着糖果。 糖果是从左到右编号的。 第i个糖果的权重是wi。 爱丽丝和鲍勃吃糖果。 爱丽丝可以从左边吃任意数量的糖果(她不能跳过糖果，她连续吃)。 Bob可以从右边吃任意数量的糖果(他不能跳过糖果，他连续吃)。 当然，如果Alice吃了糖果，Bob就不能吃了(反之亦然)。 他们想要公平。 他们的目标是吃同样重量的糖果。 他们总共能吃多少糖果?
  • 思考：题目的意思已经相当明显了，就是一道前缀后缀和加双指针的题目，要注意用memset初始化会tle所以要手动初始化。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int a[maxn];
int sum1[maxn], sum2[maxn];
int MAX = 0;
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n, ans = 0, MAX = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			sum1[i] = a[i] + sum1[i - 1];
		}
		for (int i = n; i > 0; i--)
		{
			sum2[i] = sum2[i + 1] + a[i];
		}
		int l = 1, r = n;
		while (l < r)
		{
			if (sum1[l] == sum2[r])
			{
				ans = l + n - r + 1;
				l++;
				continue;
			}
			if (sum1[l] > sum2[r])
				r--;
			else if (sum1[1] < sum2[r])
				l++;
		}
		printf("%d\n", ans);
		for (int i = 1; i <= n; i++)
		{
			a[i] = 0, sum1[i] = 0, sum2[i] = 0;
		}    //初始化
	}
	return 0;
}

G题

  • 题目大意：有一个n行m列的网格，以及三种类型的单元格:一个空单元格，用’.‘表示。 一块石头，用’*'表示。 一个障碍，用小写的拉丁字母o表示。 所有的石头都会掉落，直到它们碰到地板(最下面一排)、障碍物或其他已经无法移动的石头。 (换句话说，只要石头能掉下来，它们就会掉下来。) 模拟过程。 生成的网格是什么样的?
  • 思考：很简单的递归，细节看代码。
#include<bits/stdc++.h>
using namespace std;
char a[55][55];
void move_s(int i,int j)
{
	if (a[i + 1][j] == '.')
	{
		a[i + 1][j] = '*';
		a[i][j] = '.';
		move_s(i + 1, j);
	}
	else
		return;
	return;
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		memset(a, 0, sizeof(a));
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)
		{
			scanf("%s", a[i]);
		}
		for (int i = n - 2; i >= 0; i--)
		{
			for (int j = 0; j < m; j++)
			{
				if (a[i][j] == '*')
					move_s(i, j);
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				printf("%c", a[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

H题

  • 题目大意：说实话身为一个蒟蒻我第一次见这种题目刚开始连题目都读不懂。😤去看了别人的博客才知道做法的。就是给你一串数，你有k次操作的机会可以将一个数的二进制中的0变成1，要求你操作后对该串数求与的结果最大值。
  • 思考：求与运算只要有一个位置不为1则为0，如果能在k次操作内把最高位的0变成1那结果肯定是最大的，如果不行就变次一位。所以我们要找每一位上0的个数，看能不能把该位变成1.
#include<bits/stdc++.h>
using namespace std;
int a[35];  //存放1的个数
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		memset(a, 0, sizeof(a));
		int n, k;
		scanf("%d%d", &n, &k);
		for (int i = 0; i < n; i++)
		{
			int z;
			scanf("%d", &z);
			int j=0;
			while (z)
			{
				a[j++] += z & 1;  //关于位运算的性质，可以自己演算一下，每个数&1之后就可以得到该数二进制的最后一个数。
				z >>= 1;   //然后再将该数除以2可得该数二进制除去最后一位的数。
			}   

		}
		int ans = 0;
		for (int i = 30; i >= 0; i--) //要从30开始是因为每次存入的是反的。
		{
			if (n - a[i] <= k)
			{
				k -= n - a[i];  //n是总数量，如果n-a[i]<=k说明在执行<=k次操作后能把该位上的0全部变成1.
				a[i] = n;
			}
			if (a[i] == n)
				ans += pow(2, i);
		}
		printf("%d\n", ans);
	}
	return 0;
}
✳

谢谢你读到这里。

更新于 2022-07-01

搜索笔记

搜索文章标题、标签和正文。

↑ ↓ 选择 · Enter 阅读Esc 关闭