Codeforces Round #294 (Div. 2) (ABCDE题解)

2024-03-20 14:32

本文主要是介绍Codeforces Round #294 (Div. 2) (ABCDE题解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

比赛链接:http://codeforces.com/contest/519

这场的题目实在有点水。。。前三题直接贴代码了


A. A and B and Chess
time limit per test:1 second
memory limit per test:256 megabytes

A and B are preparing themselves for programming contests.

To train their logical thinking and solve problems better, A and B decided to play chess. During the game A wondered whose position is now stronger.

For each chess piece we know its weight:

  • the queen's weight is 9,
  • the rook's weight is 5,
  • the bishop's weight is 3,
  • the knight's weight is 3,
  • the pawn's weight is 1,
  • the king's weight isn't considered in evaluating position.

The player's weight equals to the sum of weights of all his pieces on the board.

As A doesn't like counting, he asked you to help him determine which player has the larger position weight.

Input

The input contains eight lines, eight characters each — the board's description.

The white pieces on the board are marked with uppercase letters, the black pieces are marked with lowercase letters.

The white pieces are denoted as follows: the queen is represented is 'Q', the rook — as 'R', the bishop — as'B', the knight — as 'N', the pawn — as 'P', the king — as 'K'.

The black pieces are denoted as 'q', 'r', 'b', 'n', 'p', 'k', respectively.

An empty square of the board is marked as '.' (a dot).

It is not guaranteed that the given chess position can be achieved in a real game. Specifically, there can be an arbitrary (possibly zero) number pieces of each type, the king may be under attack and so on.

Output

Print "White" (without quotes) if the weight of the position of the white pieces is more than the weight of the position of the black pieces, print "Black" if the weight of the black pieces is more than the weight of the white pieces and print "Draw" if the weights of the white and black pieces are equal.

Sample test(s)
Input
...QK...
........
........
........
........
........
........
...rk...
Output
White
Input
rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR
Output
Draw
Input
rppppppr
...k....
........
........
........
........
K...Q...
........
Output
Black
Note

In the first test sample the weight of the position of the white pieces equals to 9, the weight of the position of the black pieces equals 5.

In the second test sample the weights of the positions of the black and the white pieces are equal to 39.

In the third test sample the weight of the position of the white pieces equals to 9, the weight of the position of the black pieces equals to 16.



#include <cstdio>int main()
{char s[10][10];int b = 0, w = 0;for(int i = 0; i < 8; i++){scanf("%s", s[i]);for(int j = 0; j < 8; j++){if(s[i][j] == 'q')b += 9;if(s[i][j] == 'r')b += 5;if(s[i][j] == 'b')b += 3;if(s[i][j] == 'n')b += 3;if(s[i][j] == 'p')b += 1;if(s[i][j] == 'Q')w += 9;if(s[i][j] == 'R')w += 5;if(s[i][j] == 'B')w += 3;if(s[i][j] == 'N')w += 3;if(s[i][j] == 'P')w += 1;}}if(w == b)printf("Draw\n");else if(w > b)printf("White\n");else printf("Black\n");
}




B. A and B and Compilation Errors
time limit per test:2 seconds
memory limit per test:256 megabytes

A and B are preparing themselves for programming contests.

B loves to debug his code. But before he runs the solution and starts debugging, he has to first compile the code.

Initially, the compiler displayed n compilation errors, each of them is represented as a positive integer. After some effort, B managed to fix some mistake and then another one mistake.

However, despite the fact that B is sure that he corrected the two errors, he can not understand exactly what compilation errors disappeared — the compiler of the language which B uses shows errors in the new order every time! B is sure that unlike many other programming languages, compilation errors for his programming language do not depend on each other, that is, if you correct one error, the set of other error does not change.

Can you help B find out exactly what two errors he corrected?

Input

The first line of the input contains integer n (3 ≤ n ≤ 105) — the initial number of compilation errors.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the errors the compiler displayed for the first time.

The third line contains n - 1 space-separated integers b1, b2, ..., bn - 1 — the errors displayed at the second compilation. It is guaranteed that the sequence in the third line contains all numbers of the second string except for exactly one.

The fourth line contains n - 2 space-separated integers с1, с2, ..., сn - 2 — the errors displayed at the third compilation. It is guaranteed that the sequence in the fourth line contains all numbers of the third line except for exactly one.

Output

Print two numbers on a single line: the numbers of the compilation errors that disappeared after B made the first and the second correction, respectively.

Sample test(s)
Input
5
1 5 8 123 7
123 7 5 1
5 1 7
Output
8
123
Input
6
1 4 3 3 5 7
3 7 5 4 3
4 3 7 5
Output
1
3
Note

In the first test sample B first corrects the error number 8, then the error number 123.

In the second test sample B first corrects the error number 1, then the error number 3. Note that if there are multiple errors with the same number, B can correct only one of them in one step.

这题这样做,纯属卖萌

#include <cstdio>
#include <map>
using namespace std;
map <int, int> mp, mp2;int main()
{int n, get;scanf("%d", &n);mp.clear();mp2.clear();for(int i = 0; i < n; i++){   scanf("%d", &get);mp[get]++;mp2[get]++;}for(int i = 0; i < n - 1; i++){scanf("%d", &get);mp[get]--;}map <int, int> :: iterator it;map <int, int> :: iterator it2;for(it = mp.begin(); it != mp.end(); it++){if(it -> second != 0){printf("%d\n", it -> first);break;}}for(int i = 0; i < n - 2; i++){scanf("%d", &get);mp[get]++;}for(it = mp.begin(); it != mp.end(); it++){it2 = mp2.find(it -> first);if(it -> second != it2 -> second){printf("%d\n", it -> first);break;}}
}



C. A and B and Team Training
time limit per test:1 second
memory limit per test:256 megabytes

A and B are preparing themselves for programming contests.

An important part of preparing for a competition is sharing programming knowledge from the experienced members to those who are just beginning to deal with the contests. Therefore, during the next team training A decided to make teams so that newbies are solving problems together with experienced participants.

A believes that the optimal team of three people should consist of one experienced participant and two newbies. Thus, each experienced participant can share the experience with a large number of people.

However, B believes that the optimal team should have two experienced members plus one newbie. Thus, each newbie can gain more knowledge and experience.

As a result, A and B have decided that all the teams during the training session should belong to one of the two types described above. Furthermore, they agree that the total number of teams should be as much as possible.

There are n experienced members and m newbies on the training session. Can you calculate what maximum number of teams can be formed?

Input

The first line contains two integers n and m (0 ≤ n, m ≤ 5·105) — the number of experienced participants and newbies that are present at the training session.

Output

Print the maximum number of teams that can be formed.

Sample test(s)
Input
2 6
Output
2
Input
4 5
Output
3
Note

Let's represent the experienced players as XP and newbies as NB.

In the first test the teams look as follows: (XP, NB, NB), (XP, NB, NB).

In the second test sample the teams look as follows: (XP, NB, NB), (XP, NB, NB), (XP, XP, NB).


#include <cstdio> int main()
{int n, m, ans;scanf("%d %d", &n, &m);ans = 0;while(n && m){   if(n >= m && n - 2 >= 0){n -= 2;m--;ans++;}else if(n < m && m - 2 >= 0){m -= 2;n--;ans++;}else {n--;m--;}}printf("%d\n", ans);
}



D. A and B and Interesting Substrings
time limit per test:2 seconds
memory limit per test:256 megabytes

A and B are preparing themselves for programming contests.

After several years of doing sports programming and solving many problems that require calculating all sorts of abstract objects, A and B also developed rather peculiar tastes.

A likes lowercase letters of the Latin alphabet. He has assigned to each letter a number that shows how much he likes that letter (he has assigned negative numbers to the letters he dislikes).

B likes substrings. He especially likes the ones that start and end with the same letter (their length must exceed one).

Also, A and B have a string s. Now they are trying to find out how many substrings t of a string s are interesting to B (that is, t starts and ends with the same letter and its length is larger than one), and also the sum of values of all letters (assigned by A), except for the first and the last one is equal to zero.

Naturally, A and B have quickly found the number of substrings t that are interesting to them. Can you do it?

Input

The first line contains 26 integers xa, xb, ..., xz ( - 105 ≤ xi ≤ 105) — the value assigned to letters a, b, c, ..., z respectively.

The second line contains string s of length between 1 and 105 characters, consisting of Lating lowercase letters— the string for which you need to calculate the answer.

Output

Print the answer to the problem.

Sample test(s)
Input
1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 1 8 1 1 1 1 1 1
xabcab
Output
2
Input
1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 1 8 1 1 1 1 1 1
aaa
Output
2
Note

In the first sample test strings satisfying the condition above are abca and bcab.

In the second sample test strings satisfying the condition above are two occurences of aa.


题目大意:给26个字母赋值,然后输入一个字符串,求首位和末位字符相同且首位和末位之间(不含端点)值的和为0的子串的个数


题目分析:预处理出前缀和,可以发现要满足中间和为0,只需要找前缀和相同的两个字符即可,然后用map离散一下数据,map[字符][对应的前缀和],每次ans加上对应的map值,相当于动态规划的过程


#include <cstdio>
#include <map>
#define ll long long
using namespace std;
int a[30];
char s[100005];
ll cnt[100005];
map <ll, ll> mp[26];int main()
{ll ans = 0, tmp = 0;for(int i = 0; i < 26; i++)scanf("%d", &a[i]);scanf("%s", s + 1);for(int i = 1; s[i]; i++)cnt[i] += cnt[i - 1] + a[s[i] - 'a'];for(int i = 1; s[i]; i++){ans += mp[s[i] - 'a'][cnt[i - 1]];mp[s[i] - 'a'][cnt[i]]++;}printf("%I64d\n", ans);
}



E. A and B and Lecture Rooms
time limit per test:2 seconds
memory limit per test:256 megabytes

A and B are preparing themselves for programming contests.

The University where A and B study is a set of rooms connected by corridors. Overall, the University has n rooms connected by n - 1 corridors so that you can get from any room to any other one by moving along the corridors. The rooms are numbered from 1 to n.

Every day А and B write contests in some rooms of their university, and after each contest they gather together in the same room and discuss problems. A and B want the distance from the rooms where problems are discussed to the rooms where contests are written to be equal. The distance between two rooms is the number of edges on the shortest path between them.

As they write contests in new rooms every day, they asked you to help them find the number of possible rooms to discuss problems for each of the following m days.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of rooms in the University.

The next n - 1 lines describe the corridors. The i-th of these lines (1 ≤ i ≤ n - 1) contains two integers ai and bi (1 ≤ ai, bi ≤ n), showing that the i-th corridor connects rooms ai and bi.

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries.

Next m lines describe the queries. The j-th of these lines (1 ≤ j ≤ m) contains two integers xj and yj (1 ≤ xj, yj ≤ n) that means that on the j-th day A will write the contest in the room xj, B will write in the room yj.

Output

In the i-th (1 ≤ i ≤ m) line print the number of rooms that are equidistant from the rooms where A and B write contest on the i-th day.

Sample test(s)
Input
4
1 2
1 3
2 4
1
2 3
Output
1
Input
4
1 2
2 3
2 4
2
1 2
1 3
Output
0
2
Note

in the first sample there is only one room at the same distance from rooms number 2 and 3 — room number 1.

题目大意:给一棵树,m次查询,查询到两个点距离相等的点的个数


题目分析:动态LCA,用树上倍增法,num数组记录以某个节点为根的子树里节点的数目

注意分几种情况:

为方便,deep[u]的深度总是大于deep[v]

1.|deep[u] - deep[v]|%2 == 1,必然不存在到达u,v距离相等的点,深度差奇数倍,结论很显然

2.deep[u] == deep[v],ans = n - num[u所在的子树] - num[v所在的子树]。

3.deep[u] != deep[v],在u到v的路径中找出到达u, v相等的节点x,则ans=num[x所在的子树] - num[u(u在x的子树上)].


#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int const MAX = 200005;struct Edge
{int id, next;
}e[MAX];int pre[MAX], cnt;
int num[MAX], deep[MAX], fa[MAX][20];void AddEdge(int u, int v)
{e[cnt].id = v;e[cnt].next = pre[u];pre[u] = cnt++;e[cnt].id = u;e[cnt].next = pre[v];pre[v] = cnt++;
}void init(int u)
{for(int i = 1; i < 20; i++)if(deep[u] >= (1 << i))fa[u][i] = fa[fa[u][i - 1]][i - 1];
}void dfs(int u)
{init(u);for(int i = pre[u]; i != -1; i = e[i].next){int v = e[i].id;if(!deep[v]){fa[v][0] = u;deep[v] = deep[u] + 1;dfs(v);num[u] += num[v];}}
}int LCA(int u, int v)
{if(deep[u] < deep[v])swap(u, v);int i;for(i = 0; (1 << i) <= deep[u]; i++);i--;for(int j = i; j >= 0; j--)if(deep[u] - (1 << j) >= deep[v])u = fa[u][j];if(u == v)return u;for(int j = i; j >= 0; j--){if(fa[u][j] != -1 && fa[u][j] != fa[v][j]){u = fa[u][j];v = fa[v][j];}}return fa[u][0];
}int main()
{int n, m, u, v;scanf("%d", &n);cnt = 0;memset(pre, -1, sizeof(pre));for(int i = 0; i < n - 1; i++){scanf("%d %d", &u, &v);AddEdge(u, v);}for(int i = 1; i <= n; i++)num[i] = 1;memset(deep, 0, sizeof(deep));deep[1] = 1;dfs(1);scanf("%d", &m);while(m--){scanf("%d %d", &u, &v);if(deep[u] < deep[v])swap(u, v);if((deep[u] - deep[v]) % 2) printf("0\n");else{int w = LCA(u, v), tmpu = u, tmpv = v;int d = (deep[u] + deep[v] - 2 * deep[w]) / 2 - 1;for(int i = 0; i < 20; i++)if(d & (1 << i))tmpu = fa[tmpu][i];if(deep[u] == deep[v]){d = deep[v] - deep[w] - 1;for(int i = 0; i < 20; i++)if(d & (1 << i))tmpv = fa[tmpv][i];printf("%d\n", n - num[tmpu] - num[tmpv]);}else printf("%d\n", num[fa[tmpu][0]] - num[tmpu]);}}
}



这篇关于Codeforces Round #294 (Div. 2) (ABCDE题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829779

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述