我是靠谱客的博主 寂寞保温杯，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 49 (Rated for Div. 2)ABCD题解，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
A
题意大概就是给出一个字符串，每个字符必须变成它的前一个或后一个（a和z只能变成1个），问你能不能变成一个回文串
直接两个指针同时从中间向两边挪，暴力模拟即可
#include <bits/stdc++.h>
using namespace std;
#define Y puts("YES")
#define N puts("NO")
const int MAXN = 200;
const int INF = 0x3f3f3f3f;
template <typename T> inline void read(T &x) {
int c = getchar();
bool f = false;
for (x = 0; !isdigit(c); c = getchar()) {
if (c == '-') {
f = true;
}
}
for (; isdigit(c); c = getchar()) {
x = x * 10 + c - '0';
}
if (f) {
x = -x;
}
}
int T, n;
char s[MAXN];
signed main() {
read(T);
while(T --) {
read(n);
scanf("%s", s);
int len = strlen(s);
int mid = (len >> 1);
int r = mid, l = mid - 1;
bool fg = 0;
while(r < len && l >= 0) {
if(s[l] == 'a') {
if(s[r] != 'a' && s[r] != 'c') {
fg = 1;
N;
break;
}
}
else if(s[l] == 'z') {
if(s[r] != 'z' && s[r] != 'x') {
fg = 1;
N;
break;
}
}
else {
if(s[r] - 1 == s[l] + 1) fg = 0;
else if(s[r] + 1 == s[l] - 1) fg = 0;
else if(s[r] == s[l]) fg = 0;
else {
fg = 1;
N;
break;
}
}
l--, r++;
//printf("!!!%d %dn", l, r);
}
if(!fg) Y;
}
return 0;
}B
说实话这题没太看懂，大概意思是1-n^2/2的数从左往右从上往下只填奇数行奇数列和偶数行偶数列，剩下的相反，给出(x,y)，求其对应的数。
其实看看就知道是个公式题，算是很好推的了，具体看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100100;
const int INF = 0x3f3f3f3f;
template <typename T> inline void read(T &x) {
int c = getchar();
bool f = false;
for (x = 0; !isdigit(c); c = getchar()) {
if (c == '-') {
f = true;
}
}
for (; isdigit(c); c = getchar()) {
x = x * 10 + c - '0';
}
if (f) {
x = -x;
}
}
#define LL long long
LL n, x, y, ans;
int q;
signed main() {
read(n);
if(n & 1) {
read(q);
while(q--) {
ans = 0;
read(x), read(y);
if(x & 1) {
if(y & 1) {
ans += (x >> 1) * (n >> 1) + (x >> 1) * ((n >> 1) + 1);
ans += ((y + 1) >> 1);
}
else {
ans += (n * n / 2) + 1;
ans += (x >> 1) * (n >> 1) + (x >> 1) * ((n >> 1) + 1);
ans += (y >> 1);
}
}
else {
if(y & 1) {
ans += (n * n / 2) + 1;
ans += (x >> 1) * (n >> 1) + ((x >> 1) - 1) * ((n >> 1) + 1);
ans += ((y + 1) >> 1);
}
else {
ans += (x >> 1) * ((n >> 1) + 1) + ((x >> 1) - 1) * (n >> 1);
ans += (y >> 1);
}
}
printf("%I64dn", ans);
}
}
else {
read(q);
while(q--) {
ans = 0;
read(x), read(y);
if(x & 1) {
if(y & 1) {
ans += (x - 1) * (n >> 1);
ans += ((y + 1) >> 1);
}
else {
ans += (n * n / 2);
ans += (x - 1) * (n >> 1);
ans += (y >> 1);
}
}
else {
if(y & 1) {
ans += (n * n / 2);
ans += (x - 1) * (n >> 1);
ans += ((y + 1) >> 1);
}
else {
ans += (x - 1) * (n >> 1);
ans += (y >> 1);
}
}
printf("%I64dn", ans);
}
}
return 0;
}C,
大意是从一些长度的木棍中选出四根组成一个矩形，要求矩形的周长平方除以面积的商最小，求长宽x和y
将这个式子写成(2x + 2y) ^ 2 / xy，转化一下，由均值不等式得当x==y时该式最小
然后，假设a < b < c, 设上式为一个函数f(x, y)，则f(a, b) < f(a, c)，f(b, c) < f(a, c)
所以将所有有至少两根的木棍长度排序，计算相领的两个长度的f(x, y)值，取最小
如果有4个一样长度的直接输出
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000100;
const int INF = 0x3f3f3f3f;
template <typename T> inline void read(T &x) {
int c = getchar();
bool f = false;
for (x = 0; !isdigit(c); c = getchar()) {
if (c == '-') {
f = true;
}
}
for (; isdigit(c); c = getchar()) {
x = x * 10 + c - '0';
}
if (f) {
x = -x;
}
}
#define LL long long
int T, n, l1, l2;
int a[MAXN], sum[MAXN / 30];
vector<int> v;
signed main() {
read(T);
while(T--) {
read(n);
bool fg = 0;
memset(sum, 0, sizeof(sum));
v.clear();
for(int i = 1; i <= n; i++) {
read(a[i]);
sum[a[i]]++;
if(sum[a[i]] == 4 && !fg) {
printf("%d %d %d %dn", a[i], a[i], a[i], a[i]);
fg = 1;
}
if(sum[a[i]] == 2) {
v.push_back(a[i]);
}
}
if(fg) continue;
sort(v.begin(), v.end());
double dlt = 1e50;
for(int i = 0; i < (int) v.size() - 1; i++) {
double x = (double) v[i], y = (double) v[i + 1];
double tmp = 8.000 + 4.000 * (x / y + y / x);
if(tmp < dlt) {
l1 = v[i], l2 = v[i + 1];
dlt = tmp;
}
}
printf("%d %d %d %dn", l1, l2, l2, l1);
}
return 0;
}D
一道tarjan的题，大概相当于求一个有向图中所有的出度为0的SCC，没什么好说的，看出来了之后做法就很粗暴了，具体可参看popular cow
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 10010;
const int INF = 0x3f3f3f3f;
template <typename T> inline void read(T &x) {
int ch = getchar();
bool f = false;
for (x = 0; !isdigit(ch); ch = getchar()) {
if (ch == '-') {
f = true;
}
}
for (; isdigit(ch); ch = getchar()) {
x = x * 10 + ch - '0';
}
if (f) {
x = -x;
}
}
#define LL long long
const int MAXN = 200100;
const int MAXE = 600400;
using std::min;
struct Edge {
int to, nxt;
Edge() {}
Edge(int _to, int _nxt) : to(_to), nxt(_nxt) {}
}E[MAXE];
int h[MAXN], ins[MAXN], dfn[MAXN], Clock_t, Stack[MAXN], SCC;
int top, belong[MAXN], in[MAXN], sz[MAXN], cnt, low[MAXN];
int vis[MAXN], n, m;
inline void add_edge(int u, int v) {
E[++cnt] = Edge(v, h[u]), h[u] = cnt;
//E[++cnt] = Edge(u, h[v]), h[v] = cnt;
}
int a[MAXN], c[MAXN];
void Tarjan(int x) {
ins[x] = 1;
low[x] = dfn[x] = ++Clock_t;
Stack[++top] = x;
for(int i = h[x]; ~i; i = E[i].nxt) {
int v = E[i].to;
if(!dfn[v]) {
Tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(ins[v]) low[x] = min(low[x], low[v]);
}
if(low[x] == dfn[x]) {
SCC++;int v;
do {
v = Stack[top--];
ins[v] = 0;
belong[v] = SCC;
sz[SCC] = min(sz[SCC], c[v]);
}while(v != x);
}
return ;
}
int out[MAXN];
signed main() {
read(n); memset(h, -1, sizeof(h)); memset(sz, 0x3f, sizeof(sz));
for(int i = 1; i <= n; i++) read(c[i]);
for(int i = 1; i <= n; i++) read(a[i]), add_edge(i, a[i]);
for(int i = 1; i <= n; i++) {
if(!dfn[i])
Tarjan(i);
}
int ans = 0;
for(int i = 1; i <= n; i++) {
for(int x = h[i]; ~x; x = E[x].nxt) {
int v = E[x].to;
if(belong[i] != belong[v]) out[belong[i]]++;
}
}
for(int i = 1; i <= SCC; i++) {
if(!out[i]) ans += sz[i];
}
printf("%dn", ans);
return 0;
}
最后
以上就是寂寞保温杯为你收集整理的Educational Codeforces Round 49 (Rated for Div. 2)ABCD题解的全部内容，希望文章能够帮你解决Educational Codeforces Round 49 (Rated for Div. 2)ABCD题解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复