Codeforces VK Cup 2015 Wild Card Round 1 (AB)

2024-03-20 14:18

本文主要是介绍Codeforces VK Cup 2015 Wild Card Round 1 (AB),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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


A. Reposts
time limit per test:1 second
memory limit per test:256 megabytes

One day Polycarp published a funny picture in a social network making a poll about the color of his handle. Many of his friends started reposting Polycarp's joke to their news feed. Some of them reposted the reposts and so on.

These events are given as a sequence of strings "name1 reposted name2", where name1 is the name of the person who reposted the joke, and name2 is the name of the person from whose news feed the joke was reposted. It is guaranteed that for each string "name1 reposted name2" user "name1" didn't have the joke in his feed yet, and "name2" already had it in his feed by the moment of repost. Polycarp was registered as "Polycarp" and initially the joke was only in his feed.

Polycarp measures the popularity of the joke as the length of the largest repost chain. Print the popularity of Polycarp's joke.

Input

The first line of the input contains integer n (1 ≤ n ≤ 200) — the number of reposts. Next follow the reposts in the order they were made. Each of them is written on a single line and looks as "name1 reposted name2". All the names in the input consist of lowercase or uppercase English letters and/or digits and have lengths from 2 to 24 characters, inclusive.

We know that the user names are case-insensitive, that is, two names that only differ in the letter case correspond to the same social network user.

Output

Print a single integer — the maximum length of a repost chain.

Sample test(s)
Input
5
tourist reposted Polycarp
Petr reposted Tourist
WJMZBMR reposted Petr
sdya reposted wjmzbmr
vepifanov reposted sdya
Output
6
Input
6
Mike reposted Polycarp
Max reposted Polycarp
EveryOne reposted Polycarp
111 reposted Polycarp
VkCup reposted Polycarp
Codeforces reposted Polycarp
Output
2
Input
1
SoMeStRaNgEgUe reposted PoLyCaRp
Output
2


题目大意:求最长链的节点数

题目分析:用map 字符串hash一下,然后跑下floyd,代码写的丑


#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
map <string, int> mp;
map <string, int> :: iterator it;
int const MAX = 505;
int g[MAX][MAX], cnt;int Floyd()
{int ans = 1;for(int k = 0; k < cnt; k++){for(int i = 0; i < cnt; i++){for(int j = 0; j < cnt; j++){if(g[i][k] && g[k][j]){g[i][j] = g[i][k] + g[k][j];ans = max(ans, g[i][j]);}}}}return ans;
}void trans(string a)
{int i = 0;while(a[i]){if(a[i] >= 'A' && a[i] <= 'Z')a[i] += 'a' - 'A';i++;}
}int main()
{int n;cnt = 0;scanf("%d", &n);while(n--){string a, tmp, b;cin >> a >> tmp >> b;int i = 0;while(a[i]){if(a[i] >= 'A' && a[i] <= 'Z')a[i] += 'a' - 'A';i++;}i = 0;while(b[i]){if(b[i] >= 'A' && b[i] <= 'Z')b[i] += 'a' - 'A';i++;    }mp[a] = cnt++;it = mp.find(a);if(it == mp.end())mp[a] = cnt++;it = mp.find(b);if(it == mp.end())mp[b] = cnt++;g[mp[a]][mp[b]] = 1;}int ans = Floyd();printf("%d\n", ans + 1);
}



B. Photo to Remember
time limit per test:2 seconds
memory limit per test:256 megabytes

One day n friends met at a party, they hadn't seen each other for a long time and so they decided to make a group photo together.

Simply speaking, the process of taking photos can be described as follows. On the photo, each photographed friend occupies a rectangle of pixels: the i-th of them occupies the rectangle of width wi pixels and height hi pixels. On the group photo everybody stands in a line, thus the minimum pixel size of the photo including all the photographed friends, is W × H, where W is the total sum of all widths and H is the maximum height of all the photographed friends.

As is usually the case, the friends made n photos — the j-th (1 ≤ j ≤ n) photo had everybody except for the j-th friend as he was the photographer.

Print the minimum size of each made photo in pixels.

Input

The first line contains integer n (2 ≤ n ≤ 200 000) — the number of friends.

Then n lines follow: the i-th line contains information about the i-th friend. The line contains a pair of integers wi, hi (1 ≤ wi ≤ 10, 1 ≤ hi ≤ 1000) — the width and height in pixels of the corresponding rectangle.

Output

Print n space-separated numbers b1, b2, ..., bn, where bi — the total number of pixels on the minimum photo containing all friends expect for the i-th one.

Sample test(s)
Input
3
1 10
5 5
10 1
Output
75 110 60 
Input
3
2 1
1 2
2 1
Output
6 4 6 


题目大意:给n个wi和hi,去删去第i个wi和hi后剩下的wi的和与hi的最大值的积

题目分析:直接模拟出最大和次大值,如果最大值不止一个标记一下,然后就没什么东西了。。。

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
int const MAX = 2 * 1e6 + 5;
ll w[MAX], h[MAX];int main()
{int n;ll sum = 0, ma1 = 0, ma2 = 0, pos = 0;bool flag = false;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%I64d %I64d", &w[i], &h[i]);sum += w[i];if(ma1 < h[i]){ma1 = h[i];pos = i;}}for(int i = 0; i < n; i++){if(i == pos)continue;if(h[i] == ma1){flag = true;continue;}ma2 = max(ma2, h[i]);}for(int i = 0; i < n; i++){if(h[i] == ma1){if(flag)printf("%I64d ", (sum - w[i]) * ma1);elseprintf("%I64d ", (sum - w[i]) * ma2);}   elseprintf("%I64d ", (sum - w[i]) * ma1);}printf("\n");
}


这篇关于Codeforces VK Cup 2015 Wild Card Round 1 (AB)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

性能测试工具 wrk,ab,locust,Jmeter 压测结果比较

前言 在开发服务端软件时,经常需要进行性能测试,一般我采用手写性能测试代码的方式进行测试,那有什么现成的好的性能测试工具吗? 性能测试工具 wrk,ab,locust,Jmeter 压测结果比较 详见: 性能测试工具 wrk,ab,locust,Jmeter 压测结果比较 Jmeter性能测试 入门

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

CF Bayan 2015 Contest Warm Up A.(模拟+预处理)

A. Bayan Bus time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/problem/A The fi

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接:点击打开链接 C. 题目链接:点击打开链接 解题思路: 对于给定的字符串,取出现次数最多的字母(可以同时有多个)。由这些字母组成长度为n的字符串,求有多少种组合。最后用数学知识即可。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <climits>