codeforces round 894题解 A~F

本文主要是介绍codeforces round 894题解 A~F，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Gift Carpet

A. Gift Carpet

题目大意

有n*m个格子，每个格子中有一个字符，问是否有从左往右的四列格子中，分别包含v，i，k，a四个字符。

思路

就从左往右枚举每一列，记录v，i，k，a有没有且是不是按顺序出现的。

AC代码

#include<iostream>
#include<map>
using namespace std;
char di[25][25];
char p[4] = { 'v','i','k','a' };
int main() {int t; cin >> t;while (t--) {map<char,int> mp;int n, m; cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> di[i][j];}}int tot = 0;for (int j = 1; j <= m; j++) {for (int i = 1; i <= n; i++) {if (di[i][j] == p[tot]) {tot++;break;}}if (tot == 4) {break;}}if (tot-1 == 3) cout << "YES" << endl;elsecout << "NO" << endl;}
}

B. Sequence Game

B. Sequence Game

题目大意

给定一个数组b，数组b中的元素是数组a中的元素中满足 a[i-1]<=a[i] 条件的a[i]。求一个可能的数组a。

思路

反着推回去，如果b[i-1]大于b[i]，就在b[i]前面加上一个小于等于它的数。

AC代码

#include<iostream>
using namespace std;
const int M = 2e5 + 5;
typedef long long ll;
ll b[M];
ll a[M];
int main() {int t; cin >> t;while (t--) {int n; cin >> n;for (int i = 1; i <= n; i++) {cin >> b[i];}int tot = 0;a[++tot] = b[1];for (int i = 2; i <= n; i++) {if (b[i] >= b[i - 1]) {a[++tot] = b[i];}else {a[++tot] = b[i];a[++tot] = b[i];}}cout << tot << endl;for (int i = 1; i <= tot; i++) {cout << a[i] << " ";}cout << endl;}
}

C. Flower City Fence

C. Flower City Fence

题目大意

判断高度递减，宽度相等的几块长木板组成的形状是否是轴对称图形。

思路

不太好表述，可以就这样例画一画图，就会发现一些有趣的事情

AC代码

#include<iostream>
#include<map>
#include<cstring>
using namespace std;
typedef long long ll;
const int M = 2e5 + 5;
ll a[M];
ll cnt[M];
int main() {int t; cin >> t;while (t--) {int n; cin >> n;map<int, int> mp;memset(cnt, 0, sizeof(cnt));for (int i = 1; i <= n; i++) {cin >> a[i];}int f = 0;int pre = 0; mp[pre] = 0;for (int i = 1; i <= n; i++) {ll len = a[i];/*if (len > n||len<n) {f = 1;break;}if(len==n)*/mp[len]=mp[pre]+1;pre = len;}/*for (auto it : mp) {cout << it.first << " " << it.second << endl;}*/for (auto it : mp) {if (it.first>n||a[it.first] != it.second) {f = 1;break;}}if (f == 1) {cout << "NO" << endl;}elsecout << "YES" << endl;}
}

D. Ice Cream Balls

D. Ice Cream Balls

题目大意

给定一个集合，给定一个数n，求得到n种无序二元关系所需要的集合元素的最少数量。即{1，2}、{2，1}视为一种二元关系。

思路

给一个集合
{1，2，3，4}，可以组成的二元关系如下：

• {1，2}、{1，3}、{1，4}、{2，3}、{2，4}、{3，4} 一共6种，不难看出是C（4，2） 的排列组合关系。

而{1，1，2，3，4} 比上面多了一组{1，1}
{1，1，2，2，3，4} 比上面多了两组{1，1}、{2，2}
所以只要求出得到最接近n种无序关系的不同元素的数量s，然后再和n做差，将得到的差加到s种就可以得到结果。即s+n-(s-1)*s/2。
寻找不同元素数量的过程可以用二分查找来完成。注意二分边界。

AC代码

#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bool che(ull x, ull n) {if (x * (x - 1) >= 2 * n) return false;elsereturn true;
}
ull check(ull n) {ull l = 2; ull r = 2e9+10;ull res = 0;while (l < r) {ull mid = (l + r) >> 1;if (che(mid, n)) {//	res = mid;l = mid+1;}elser = mid;}ull tmp = ((l -1) * l) / 2;//cout << tmp << endl;/*ull cha =n-tmp;cout << cha << endl;*/if (tmp == n) {return l;}else {ull p = l - 1; ull s = p * (p - 1) / 2;//	cout << s << endl;return p+n - s;}
}
int main() {int t; cin >> t;while (t--) {ull n; cin >> n;if (n == 1) {cout << "2" << endl;continue;}ull p=check(n);cout << p << endl;}
}

E. Kolya and Movie Theatre

E. Kolya and Movie Theatre

题目大意

思路

分析可知，当第i天最后一次去电影院是，减去的数大小为 i*d，所以可以枚举最后一次去电影院是哪一天，这里就是核心，剩下的用单增优先队列或者multiset处理就好，维护队列大小为m。队满后如果队头小于当前元素，就弹出队头，压入当前元素，这样可以保证每次更新都是最优的。

AC代码

#include<iostream>
#include<set>using namespace std;
const int M = 2e5 + 5;
typedef long long ll;
ll a[M];
multiset<ll> p;
void sove() {p.clear();ll n, m, d; cin >> n >> m >> d;ll sum = 0; ll ans = 0;for (int i = 1; i <= n; i++) {cin >> a[i];if (a[i] > 0 && p.size() < m) {p.insert(a[i]);sum += a[i];}else if (p.size() >= m && *p.begin() < a[i]) {sum -= *p.begin();p.erase(p.begin());sum += a[i];p.insert(a[i]);}ans = max(ans, sum - i * d);}cout << ans << endl;
}int main() {int t; cin >> t;while (t--) {sove();}
}

F. Magic Will Save the World

F. Magic Will Save the World

题目大意

一个魔法师，每秒钟可以恢复w个单位的水魔法和f个单位的火魔法，有n个怪，每个怪都有血量，求魔法师最少多久消灭所有的怪。

思路

** 后面补上，先上代码**

AC代码

#include<iostream>
#include<bitset>
using namespace std;
typedef long long ll;
int s[105];
int pre[105];
const int M = 1e6 + 10;
bitset<M> bt;
int main() {int t; cin >> t;while (t--) {int w, f; cin >> w >> f;int n; cin >> n;int num = 0;bt.reset();bt[0] = 1;for (int i = 1; i <= n; i++) {cin >> s[i];bt |= bt << s[i];num += s[i];}//	ll bitn=toBit(n);//	cout << bitn << endl;int ans = 0x3f3f3f3f;for (int i = 0; i <= num; i++)if(bt[i]){//	cout << "sumw  " << sumw << endl;int p1 = num - i;//	cout << p3 << endl;ans = min(ans, max((i+w-1)/w,(p1+f-1)/f));}cout << ans << endl;}
}

这篇关于codeforces round 894题解 A~F的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---