Codeforces Round #223 (Div. 2)

2024-06-01 21:18
文章标签 codeforces round div 223

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

好惨啊只水掉两题,C题调了半天WA,结果早上起来发现是一个地方少取模。改了秒过了。

感觉当时有点急躁。A,B都没看清题目WA了次。C题也是下标的处理细节自己比较乱。。写起来就乱了


A. Sereja and Dima
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sereja and Dima play a game. The rules of the game are very simple. The players have n cards in a row. Each card contains a number, all numbers on the cards are distinct. The players take turns, Sereja moves first. During his turn a player can take one card: either the leftmost card in a row, or the rightmost one. The game ends when there is no more cards. The player who has the maximum sum of numbers on his cards by the end of the game, wins.

Sereja and Dima are being greedy. Each of them chooses the card with the larger number during his move.

Inna is a friend of Sereja and Dima. She knows which strategy the guys are using, so she wants to determine the final score, given the initial state of the game. Help her.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of cards on the table. The second line contains space-separated numbers on the cards from left to right. The numbers on the cards are distinct integers from 1 to 1000.

Output

On a single line, print two integers. The first number is the number of Sereja's points at the end of the game, the second number is the number of Dima's points at the end of the game.

Sample test(s)
input
4
4 1 2 10
output
12 5
input
7
1 2 3 4 5 6 7
output
16 12

A:两个人玩游戏,可以从头或从尾取数字,每个人都尽量取大,求最后每个人数字和。

思路:模拟就可以了。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;int n, num[1005];
bool cmp(int a, int b) {return a > b;
}
int main() {int ans1 = 0, ans2 = 0;scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%d", &num[i]);int l = 0, r = n - 1, j = 0;while (l <= r) {if (num[l] > num[r]) {if (j % 2 == 0)ans1 += num[l++];elseans2 += num[l++];}else {if (j % 2 == 0)ans1 += num[r--];elseans2 += num[r--];}j++;}printf("%d %d\n", ans1, ans2);return 0;
}

B. Sereja and Stairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sereja loves integer sequences very much. He especially likes stairs.

Sequence a1, a2, ..., a|a| (|a| is the length of the sequence) is stairs if there is such index i (1 ≤ i ≤ |a|), that the following condition is met:

a1 < a2 < ... < ai - 1 < ai > ai + 1 > ... > a|a| - 1 > a|a|.

For example, sequences [1, 2, 3, 2] and [4, 2] are stairs and sequence [3, 1, 2] isn't.

Sereja has m cards with numbers. He wants to put some cards on the table in a row to get a stair sequence. What maximum number of cards can he put on the table?

Input

The first line contains integer m (1 ≤ m ≤ 105) — the number of Sereja's cards. The second line contains m integers bi (1 ≤ bi ≤ 5000) — the numbers on the Sereja's cards.

Output

In the first line print the number of cards you can put on the table. In the second line print the resulting stairs.

Sample test(s)
input
5
1 2 3 4 5
output
5
5 4 3 2 1
input
6
1 1 2 2 3 3
output
5
1 2 3 2 1
B:给一些数字,要求组成递增再递减序列。问最长长度。

思路:构造问题,数字最大5000,可以开一个数组来记录数字,然后从小往上找,个数为2的用掉,在从上往下找,个数为1的用掉。注意处理最大的那个数字的细节就可以了,

代码:

#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 100005;int n, num, vis[5005], Max, ans;void init() {ans = 0;scanf("%d", &n); Max = 0;memset(vis, 0, sizeof(vis));for (int i = 0; i < n; i++) {scanf("%d", &num);Max = max(Max, num);vis[num]++;}
}void solve() {int i, flag = 0, res[N], resn = 0;if (vis[Max] >= 2) flag = 1;for (i = 0; i <= Max; i++) {if (vis[i] >= 2) {vis[i]--;ans++;res[resn++] = i;}}if (flag) Max--;for (i = Max; i >= 0; i--) {if (vis[i] >= 1) {vis[i]--;ans++;res[resn++] = i;}}printf("%d\n", ans);for (i = 0; i < resn - 1; i++)printf("%d ", res[i]);printf("%d\n", res[resn - 1]);
}int main() {init();solve();return 0;
}

C. Sereja and Prefixes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sereja loves number sequences very much. That's why he decided to make himself a new one following a certain algorithm.

Sereja takes a blank piece of paper. Then he starts writing out the sequence in m stages. Each time he either adds a new number to the end of the sequence or takes l first elements of the current sequence and adds them c times to the end. More formally, if we represent the current sequence as a1, a2, ..., an, then after we apply the described operation, the sequence transforms intoa1, a2, ..., an[, a1, a2, ..., al] (the block in the square brackets must be repeated c times).

A day has passed and Sereja has completed the sequence. He wonders what are the values of some of its elements. Help Sereja.

Input

The first line contains integer m (1 ≤ m ≤ 105) — the number of stages to build a sequence.

Next m lines contain the description of the stages in the order they follow. The first number in the line is a type of stage (1 or 2). Type 1 means adding one number to the end of the sequence, in this case the line contains integer xi (1 ≤ xi ≤ 105) — the number to add. Type 2 means copying a prefix of length li to the end ci times, in this case the line further contains two integers li, ci (1 ≤ li ≤ 105, 1 ≤ ci ≤ 104)li is the length of the prefix, ci is the number of copyings. It is guaranteed that the length of prefix li is never larger than the current length of the sequence.

The next line contains integer n (1 ≤ n ≤ 105) — the number of elements Sereja is interested in. The next line contains the numbers of elements of the final sequence Sereja is interested in. The numbers are given in the strictly increasing order. It is guaranteed that all numbers are strictly larger than zero and do not exceed the length of the resulting sequence. Consider the elements of the final sequence numbered starting from 1 from the beginning to the end of the sequence.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cincout streams or the %I64dspecifier.

Output

Print the elements that Sereja is interested in, in the order in which their numbers occur in the input.

Sample test(s)
input
6
1 1
1 2
2 2 1
1 3
2 5 2
1 4
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
output
1 2 1 2 3 1 2 1 2 3 1 2 1 2 3 4
C:给定m次操作,操作有1,2。1的话代表把x加入序列末,2代表把序列前缀长度为l,复制c遍加到末尾,然后输入n个数,输出n个数下标对应的数字。

思路:由于复制长度最长10^5,只要开一个10^5的数组来存放前10^5的数字,就可以了。剩下的数字去模拟过程找出下标。用一个now来表示当前找到第几个。由于n个数肯定是递增的,所以只要从左往右一个个找过去,对应m操作一共只需要找一遍,复杂度O(m) + O(n)足以。

代码:

#include <stdio.h>
#include <string.h>const int N = 100005;__int64 num[N];
int sn = 0, ansn = 0, save[N], ans[N], m, n;
struct CZ {int v, x;__int64 l, c;
} cz[N];void init() {scanf("%d", &m);for (int i = 0; i < m; i++) {scanf("%I64d", &cz[i].v);if (cz[i].v == 1)scanf("%I64d", &cz[i].x);else scanf("%I64d%I64d", &cz[i].l, &cz[i].c);}scanf("%d", &n);for (int j = 0; j < n; j++)scanf("%I64d", &num[j]);
}void table() {for (int i = 0; i < m; i++) {if (cz[i].v == 1) {save[sn++] = cz[i].x;if (sn == 100000) return;}else {for (int k = 0; k < cz[i].c; k++) {for (int j = 0; j < cz[i].l; j++) {save[sn++] = save[j];if (sn == 100000) return;}}}}
}void solve() {table(); int j = 0, i = 0;__int64 now = 0;while(i < n) {while(j < m) {if (cz[j].v == 1) {now ++; if (now == num[i]) {ans[ansn++] = cz[j].x;i++;if (i >= n) return;j++;break;}j++;}else {__int64 nn = now;now += cz[j].l * cz[j].c;if (now >= num[i]) {while (i < n) {if (num[i] <= now) {ans[ansn++] = save[(num[i++] - nn - 1) % cz[j].l % 100000];if (i >= n) return;}else {j++;break;}}}else {j++;}}}}}int main() {init();solve();for (int i = 0; i < ansn - 1; i++)printf("%d ", ans[i]);printf("%d\n", ans[ansn - 1]);return 0;
}


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



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

相关文章

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

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

创建一个大的DIV,里面的包含两个DIV是可以自由移动

创建一个大的DIV,里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;

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#271 (Div. 2) D.(dp)

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/474/problem/D We s

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There