Codeforces Round #674 (Div. 3)题解(A-F)

A. Floor Number

题目链接: A. Floor Number

题意: 去拜访朋友,只知道朋友加的门牌号为 n ,这栋楼里第一层有 2 间公寓,其它楼层则有 x 间,问朋友住在第几层

解题思路:

n\leq 2 则住在第一层,否则 1+\lceil \frac{n-2}{x}\rceil 即为答案

点此查看代码
#include <bits/stdc++.h>
 
#define F first 
#define S second
#define IS insert
#define PI acos(-1)
#define PB pop_back
#define EB emplace_back
#define SZ(x) (int)x.size()
#define MP(x, y) make_pair(x, y)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);
 
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;
 
const int N = 100010, M = 1010;
 
int T;
int n, x;
 
int main()
{
	IOS
	
	cin >> T;
	while (T -- )
	{
		cin >> n >> x;
		if (n <= 2) cout << "1\n";
		else cout << (n - 2 + x - 1) / x + 1 << '\n';
	}
    return 0;
}

B. Symmetric Matrix

题目链接: B. Symmetric Matrix

题意: 给定 n2\times 2 矩阵,每种矩阵有无限个,问是否能用这些矩阵构造成一个 m\times m 的矩阵,且这个矩阵沿正对角线对称

解题思路:

首先若 m 为奇数肯定不行

然后只要存在一种矩阵的右上角和左下角的数是相同的,就全部取这样的矩阵来构造目标矩阵

若不存在这样的矩阵,肯定不行,因为对称轴(正对角线)上的矩阵一定需要满足右上角和左下角的数相同

点此查看代码
#include <bits/stdc++.h>
 
#define F first 
#define S second
#define IS insert
#define PI acos(-1)
#define PB pop_back
#define EB emplace_back
#define SZ(x) (int)x.size()
#define MP(x, y) make_pair(x, y)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);
 
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;
 
const int N = 4, M = 1010;
 
int T;
int n, m;
int a[N];
 
int main()
{
	IOS
	
	cin >> T;
	while (T -- )
	{
		cin >> n >> m;
		
		bool flag = false, ok = false;
		while (n -- )
		{
			for (int i = 0; i < N; i ++ ) cin >> a[i];
			if (a[1] == a[2]) flag = true;
		}
		
		if (m & 1) cout << "NO\n";
		else if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
    return 0;
}

C. Increase and Copy

题目链接: C. Increase and Copy

题意: 一开始有一个序列,里面有一个数 1 ,每次操作可以使得序列中任意一个数加 1 ,也可以往数列里面加入一个数列中已经有的数,求最小步数,使得序列中所有数之和不小于 n

解题思路:

第一种操作为总和的贡献一定是 1 ,第二种操作为总和的贡献取决于所选的数,但因为要求最小步数达到目标,因此尽量选择大的数是更好的,序列中若存在两种或以上的数值,那么较小的数值永远不会被选到,因此在构造序列时,应先执行第一种操作,使得这个数变为某个值之后,只执行第二种操作

假设第一种操作的次数是 a ,第二种操作的次数是 b ,操作的过程就是 (1+a)\times (b+1)\geq n ,求 min\{a+b\}

于是根据经验(其实是懒得翻叫什么定律)知道 a+1\sqrt n 附近,用二分找到最大的 x 使得 x^2\leq n ,以及最小的 x 使得 x^2 \geq n ,比对二者的结果找到最小值即可

不过此时仍然没有考虑得很细致,实际上只需要找到最大的 x 使得 x^2\leq n ,就可以了

点此查看代码
#include <bits/stdc++.h>
 
#define F first 
#define S second
#define IS insert
#define PI acos(-1)
#define PB pop_back
#define EB emplace_back
#define SZ(x) (int)x.size()
#define MP(x, y) make_pair(x, y)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);
 
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;
 
const int N = 100010, M = 1010;
 
int T;
LL n;
 
int main()
{
	IOS
	
	cin >> T;
	while (T -- )
	{
		cin >> n;
		
		LL l = 0, r = n;
		while (l < r)
		{
			LL mid = l + r + 1LL >> 1LL;
			if (mid * mid <= n) l = mid;
			else r = mid - 1LL;
		}
		LL a1 = 2 * (r - 1) + (n - r * r + r - 1) / r;
		
		l = 0, r = n;
		while (l < r)
		{
			LL mid = l + r >> 1LL;
			if (mid * mid >= n) r = mid;
			else l = mid + 1LL;
		}
		LL a2 = 2 * (r - 1) + n / (r * r);
		
		cout << min(a1, a2) << '\n';
	}
    return 0;
}

D. Non-zero Segments

题目链接: D. Non-zero Segments

题意: 给定一个全部数都不为 0 的序列,每次操作可以选择在两个数之间插入一个数,求最少的操作数使得不存在和为 0 的连续子序列

解题思路:

对于一个和为 0 的子序列,只需要将一个无限大的数插入某个位置,即让这个子序列的和不为 0 ,同时也让包含这个子序列的所有序列和不为 0

这样这个问题就转化为了区间选点的模板题,也就是选择最少的点,使得每个区间都存在至少一个点

利用前缀和找出所有和为 0 的子序列的左右端点即可

注意事项: 这里的区间之间重叠的端点是不能覆盖两个区间的,只需令每个区间的右端点往前一个单位即可

点此查看代码
#include <bits/stdc++.h>
 
#define F first 
#define S second
#define IS insert
#define PI acos(-1)
#define PB pop_back
#define EB emplace_back
#define SZ(x) (int)x.size()
#define MP(x, y) make_pair(x, y)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);
 
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;
 
const int N = 2000010, M = 1010;
 
int n, a[N];
LL s[N];
vector<PII> seq;
 
bool cmp(PII a, PII b)
{
	if (a.S != b.S) return a.S < b.S;
	else return a.F > b.F;
}
 
int main()
{
	IOS
	
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
 
	map<LL, int> h;
	h[0LL] = 0;
	for (int i = 1; i <= n; i ++ )
	{
		s[i] = s[i - 1] + a[i];
		if (h.count(s[i]))
		{
			int r = i - 1, l = h[s[i]] + 1;
			seq.EB(MP(l, r));
		}
		h[s[i]] = i;
	}
	
	sort(ALL(seq), cmp);
	int res = 0, pos = -0x3f3f3f3f;
	for (auto u : seq)
		if (u.F > pos)
		{
			res ++ ;
			pos = u.S;
		}
	cout << res << '\n';
    return 0;
}

E. Rock, Paper, Scissors

题目链接: E. Rock, Paper, Scissors

题意: AB 玩剪刀石头布,事先已经决定好玩 n 局,每个人分别出剪刀、石头、布的数量也是不变的,但每个人的顺序可以随意安排,问 A 最多和最少能赢多少局

解题思路:

最多能赢多少局很简单, min\{A出石头,B出剪刀\}+min\{A出剪刀,B出布\}+min\{A出布,B出石头\} 即为答案

最少能赢多少局稍微有点复杂,但由于数据量小,可以直接暴力考虑

最少能赢多少局,换句话说就是找到最多有多少局不能赢,也就是找到一种对垒的顺序,使得 A 不能赢的局最多,双方的对垒一共有 9 种情况,其中 A 不能赢的情况有 6 种,用排列枚举这 6 种情况的顺序,计算每种顺序下, A 能赢的局数,并更新答案即可

点此查看代码
#include <bits/stdc++.h>
 
#define F first 
#define S second
#define IS insert
#define PI acos(-1)
#define PB pop_back
#define EB emplace_back
#define SZ(x) (int)x.size()
#define MP(x, y) make_pair(x, y)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);
 
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;
 
const int N = 6, M = 1010;
 
int n;
vector<int> a, b;
 
 
int main()
{
	IOS
	
	cin >> n;
	
	a.resize(3), b.resize(3);
	for (auto &u : a) cin >> u;
	for (auto &u : b) cin >> u;
	
	int mina = 0x3f3f3f3f, maxa = 0;
	maxa = min(a[0], b[1]) + min(a[1], b[2]) + min(a[2], b[0]);
	
	vector<PII> order;
	order.EB(MP(0, 0));
	order.EB(MP(0, 2));
	order.EB(MP(1, 1));
	order.EB(MP(1, 0));
	order.EB(MP(2, 2));
	order.EB(MP(2, 1));
	sort(ALL(order));
	
	do
	{
		vector<int> ta = a, tb = b;
		for (auto u : order)
		{
			int t = min(ta[u.F], tb[u.S]);
			ta[u.F] -= t, tb[u.S] -= t;
		}
        // 计算A在此顺序下能赢的局数
		int cur = min(ta[0], tb[1]) + min(ta[1], tb[2]) + min(ta[2], tb[0]);
		mina = min(mina, cur);
	}while (next_permutation(ALL(order)));
	cout << mina << ' ' << maxa << '\n';
    return 0;
}

F. Number of Subsequences

题目链接: F. Number of Subsequences

题意: 给定一个只含 a,b,c,? 四种字符的字符串,其中 ? 可以替换成 a,b,c 三种字符的任意一种,计算所有可能的字符串中,存在多少个子串 abc

解题思路:

比较典型的DP

先这么考虑,整个串有 cnt? ,对于某个子串,且这个子串是以下情况的其中一种:

  • abc
  • ?bc
  • a?c
  • ab?
  • a??
  • ?b?
  • ??c
  • ???

那么包含这个子串的字符串个数为 3^{cnt-k} ,其中 k 为这个子串所含有的 ?

然后问题就变得清晰起来了,只需要找到这个字符串中,含有以上八种情况的子串分别有多少个,这个问题可以用DP解决

f[i,j,k] 表示前 i 个字符,与以上八种情况匹配的长度为 j ,含有 k 个问号的所有子串,保存的属性是数量

如果当前状态的匹配长度小于 3 ,则可以做以下转移:

  • s[i]? ,当前状态可以转移到 f[i+1,j+1,k+1]
  • s[i]a ,且当前的匹配长度为 0 ,且当前的匹配长度为 1 ,那么当前状态可以转移到 f[i+1,1,k]
  • s[i]b ,且当前的匹配长度为 1 ,那么当前状态可以转移到 f[i+1,2,k]
  • s[i]c ,且当前的匹配长度为 2 ,那么当前状态可以转移到 f[i+1,3,k]

在代码实现中可以写得简便些

点此查看代码
#include <bits/stdc++.h>
 
#define F first 
#define S second
#define IS insert
#define PI acos(-1)
#define PB pop_back
#define EB emplace_back
#define SZ(x) (int)x.size()
#define MP(x, y) make_pair(x, y)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);
 
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;
 
const int N = 200010, M = 5, mod = 1e9 + 7;
 
int n;
int f[N][M][M];
string s;
 
int qp(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = (LL)res * a % mod;
		a = (LL)a * a % mod;
		b >>= 1;
	}
	return res;
}
 
int main()
{
	IOS
	
	cin >> n >> s;
	
	int cnt = 0;
	for (auto u : s) cnt += u == '?';
	
	f[0][0][0] = 1;
	for (int i = 0; i < n; i ++ )
		for (int j = 0; j <= 3; j ++ )
			for (int k = 0; k <= 3; k ++ )
				if (f[i][j][k])
				{
                    // 记得先将本状态转移到下一个长度中
					f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % mod;
					// 判断当前字符是否能转移当前状态
                    if (k < 3 && (s[i] == '?' || s[i] == 'a' + j))
					{
						int t = s[i] == '?' ? 1 : 0;
						f[i + 1][j + 1][k + t] = (f[i + 1][j + 1][k + t] + f[i][j][k]) % mod;
					}
				}
	
	int res = 0;
	for (int i = 0; i <= 3; i ++ )
		if (cnt >= i)
			res = (res + (LL)f[n][3][i] * qp(3, cnt - i) % mod) % mod;
			
	cout << res << '\n';
    return 0;
}
1赞

Discourse 这边要打公式, $ 两边要加空格 :rofl:

例如这样子 $a+b$ 这样子。

我悟出来了
一直用Typora还真不习惯加空格。。

已阅

粤 ICP 备 2020080455 号