Codeforces Round #246 (Div. 2) (ABCD详细题解)

2024-03-20 14:08

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

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


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

The Saratov State University Olympiad Programmers Training Center (SSU OPTC) has n students. For each student you know the number of times he/she has participated in the ACM ICPC world programming championship. According to the ACM ICPC rules, each person can participate in the world championship at most 5 times.

The head of the SSU OPTC is recently gathering teams to participate in the world championship. Each team must consist of exactly three people, at that, any person cannot be a member of two or more teams. What maximum number of teams can the head make if he wants each team to participate in the world championship with the same members at least k times?

Input

The first line contains two integers, n and k (1 ≤ n ≤ 2000; 1 ≤ k ≤ 5). The next line contains n integers: y1, y2, ..., yn (0 ≤ yi ≤ 5), where yi shows the number of times the i-th person participated in the ACM ICPC world championship.

Output

Print a single number — the answer to the problem.

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

In the first sample only one team could be made: the first, the fourth and the fifth participants.

In the second sample no teams could be created.

In the third sample two teams could be created. Any partition into two teams fits.

题目大意:有n个人,每个人已经参加了yi次比赛,要求三个人组一个队,每个人组多参加5次比赛,每个人只能在一个队里,现在求至少参加k次,可以组出几个队

题目分析:贪心,按参加次数从小到大排序,要注意必须3人一队

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[2005];int main()
{int n, k, ans = 0;scanf("%d %d", &n, &k);for(int i = 0; i < n; i++)scanf("%d", &a[i]);sort(a, a + n);for(int i = 0; i < n - (n % 3); i += 3)if(a[i] + k <= 5 && a[i + 1] + k <= 5 && a[i + 2] + k <= 5)ans ++;printf("%d\n", ans);
}


B. Football Kit
time limit per test
1 second
memory limit per test
256 megabytes

Consider a football tournament where n teams participate. Each team has two football kits: for home games, and for away games. The kit for home games of the i-th team has color xi and the kit for away games of this team has color yi (xi ≠ yi).

In the tournament, each team plays exactly one home game and exactly one away game with each other team (n(n - 1) games in total). The team, that plays the home game, traditionally plays in its home kit. The team that plays an away game plays in its away kit. However, if two teams has the kits of the same color, they cannot be distinguished. In this case the away team plays in its home kit.

Calculate how many games in the described tournament each team plays in its home kit and how many games it plays in its away kit.

Input

The first line contains a single integer n (2 ≤ n ≤ 105) — the number of teams. Next n lines contain the description of the teams. The i-th line contains two space-separated numbers xi, yi (1 ≤ xi, yi ≤ 105xi ≠ yi) — the color numbers for the home and away kits of the i-th team.

Output

For each team, print on a single line two space-separated integers — the number of games this team is going to play in home and away kits, correspondingly. Print the answers for the teams in the order they appeared in the input.

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

题目大意:这题是考阅读理解的,n个球队,每个球队和剩下n-1只球队打2场比赛,一场在主场,一场在客场,每个球队有一个主场卡和客场卡,如果A队去B队的主场打比赛,可是A队的客场卡数字与B队主场卡数字相同,则A队用他们的主场卡,输入的顺序就是队伍的顺序,问每队分别要用多少次自己的主场卡和客场卡

题目分析:每队用几次自己的主场卡,取决于他的客场卡和多少个队的主场卡相同(记为cnt[away]),我们先预处理出各个主场卡的数量,显然每个队至少要用n-1次自己的主场卡,然后还要用cnt[away]次主场卡来避免重复,所以一共要用n-1+cnt[away]次主场卡,因为总的比赛次数确定为2n - 2,所以客场卡用的次数为n-1-cnt[away]


#include <cstdio>
#include <cstring>
int const MAX = 1e5 + 5;
int x[MAX], y[MAX], cnt[MAX];int main()
{int n;scanf("%d", &n);memset(cnt, 0, sizeof(cnt));for(int i = 0; i < n; i++){scanf("%d %d", &x[i], &y[i]);cnt[x[i]] ++;}for(int i = 0; i < n; i++)printf("%d %d\n",  n - 1 + cnt[y[i]], n - 1 - cnt[y[i]]);
}



C. Prime Swaps
time limit per test:2 seconds
memory limit per test:256 megabytes

You have an array a[1], a[2], ..., a[n], containing distinct integers from 1 to n. Your task is to sort this array in increasing order with the following operation (you may need to apply it multiple times):

  • choose two indexes, i and j (1 ≤ i < j ≤ n; (j - i + 1) is a prime number);
  • swap the elements on positions i and j; in other words, you are allowed to apply the following sequence of assignments: tmp = a[i], a[i] = a[j], a[j] = tmp (tmp is a temporary variable).

You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5n operations.

Input

The first line contains integer n (1 ≤ n ≤ 105). The next line contains n distinct integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).

Output

In the first line, print integer k (0 ≤ k ≤ 5n) — the number of used operations. Next, print the operations. Each operation must be printed as "i j" (1 ≤ i < j ≤ n; (j - i + 1) is a prime).

If there are multiple answers, you can print any of them.

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

题目大意:给n个数排序,每次交换两个数字ai,aj,要求是j - i + 1是素数,最多交换5n次,求交换顺序

题目分析:不知道怎么证明这个5n次,但是感觉这样做就是最优了的,对于数字val,记录其原始位置pos[val],我们要做的是从最小数开始排序,如果当前数字不在其排序位,那么在满足题意要求情况下,将它交换到与其排序位最接近的地方


#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int const MAX = 1e5 + 5;
int a[MAX], x[5 * MAX], y[5 * MAX], pos[MAX];
bool prime[MAX];void get_prime()
{memset(prime, true, sizeof(prime));prime[1] = false;for(int i = 2; i <= sqrt(MAX); i++)if(prime[i])for(int j = i * i; j <= MAX; j += i)prime[j] = false;
}int main()
{int n;scanf("%d", &n);get_prime();for(int i = 1; i <= n; i++){scanf("%d", &a[i]);pos[a[i]] = i;}int cnt = 0;for(int i = 1; i <= n; i++){for(int now = pos[i]; now > i; ){int tmp = i;while(!prime[now - tmp + 1])tmp ++;             //找到与其排序位最接近的点x[cnt] = tmp;y[cnt ++] = now;        //交换一次并记录pos[a[tmp]] = now;      //更换被交换数的posswap(a[tmp], a[now]);   //交换两个数now = tmp;              //当前数字继续向前交换}}printf("%d\n", cnt);for(int i = 0; i < cnt; i++)printf("%d %d\n", x[i], y[i]);
}




D. Prefixes and Suffixes
time limit per test:1 second
memory limit per test:256 megabytes

You have a string s = s1s2...s|s|, where |s| is the length of string s, and si its i-th character.

Let's introduce several definitions:

  • A substring s[i..j] (1 ≤ i ≤ j ≤ |s|) of string s is string sisi + 1...sj.
  • The prefix of string s of length l (1 ≤ l ≤ |s|) is string s[1..l].
  • The suffix of string s of length l (1 ≤ l ≤ |s|) is string s[|s| - l + 1..|s|].

Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.

Input

The single line contains a sequence of characters s1s2...s|s| (1 ≤ |s| ≤ 105) — string s. The string only consists of uppercase English letters.

Output

In the first line, print integer k (0 ≤ k ≤ |s|) — the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers li ci. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substring ci times. Print pairs li ci in the order of increasing li.

Sample test(s)
Input
ABACABA
Output
3
1 4
3 2
7 1
Input
AAA
Output
3
1 3
2 2
3 1

题目大意:给一个字符串,求其前缀等于后缀的子串,输出子串的长度和其在原串中出现的次数,子串长度要求增序输出

题目分析:绝对的好题,必须透彻理解next数组,我们先求出原字符串的next数组,next[i]表示串0-i的最大前后缀子串相等的长度,所以长度不愁了,知道next,直接从最后一位向前嵌套迭代即可,关键是出现了多少次,这个我们用一个num数组来记录,num初始化为1,每个串至少出现1次,还是根据next数组上述的性质,拿样例解释下吧。。。
index   0   1    2   3    4   5   6   7
str       A   B   A   C   A   B   A
next   -1   0    0   1    0   1    2   3
num    0   4    2   2    1   1    1   1
计算出next数组,num[7] = 1,next[7] = 3显然012和456都是ABA是相等的所以num[3] = num[3] + num[7] = 2,再看A这个子串
num[7] = 1,next[7] = 3, num[3] = 2,next[3] = 1,num[1] = 3到此的意思是我从7到3到1,A出现了3次分别是0-6的最后一位,0-2的最后一位和第一位
。。。next[5] = 1,num[5] = 1,num[1] = num[1] + num[5] = 4,这里算上了0-4的最后一位的A,所以最后A的出现了4次。
所以通过这个性质我们也可以通过嵌套迭代出num数组num[next[i]] += num[i]
这类题感觉怎么讲都难讲清楚,要自己切身去体会体会



#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 1e5 + 10;
int next[MAX], le[MAX], t[MAX], num[MAX];
char s[MAX];void get_next()
{int i = 0, j = -1;next[0] = -1;while(s[i] != '\0'){if(j == -1 || s[i] == s[j]){i ++;j ++;next[i] = j;}elsej = next[j];}
}int main()
{scanf("%s", s);int len = strlen(s);get_next();for(int i = 1; i <= len; i++)num[i] = 1;for(int i = len; i >= 0; i--)if(next[i])num[next[i]] += num[i];for( int i = 0; i <= len; i++)printf("num[%d] = %d\n", i, num[i]);int cnt = 0;le[cnt] = len;t[cnt ++] = 1;len = next[len];while(len){le[cnt] = len;t[cnt ++] = num[len];len = next[len];}printf("%d\n", cnt);for(int i = cnt - 1; i >= 0; i--)printf("%d %d\n", le[i], t[i]);
}




心塞。。。已经很久没能操出E了,操题之路从未停止
To be continue。。

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



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

相关文章

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

python连接本地SQL server详细图文教程

《python连接本地SQLserver详细图文教程》在数据分析领域,经常需要从数据库中获取数据进行分析和处理,下面:本文主要介绍python连接本地SQLserver的相关资料,文中通过代码... 目录一.设置本地账号1.新建用户2.开启双重验证3,开启TCP/IP本地服务二js.python连接实例1.

Nginx中配置HTTP/2协议的详细指南

《Nginx中配置HTTP/2协议的详细指南》HTTP/2是HTTP协议的下一代版本,旨在提高性能、减少延迟并优化现代网络环境中的通信效率,本文将为大家介绍Nginx配置HTTP/2协议想详细步骤,需... 目录一、HTTP/2 协议概述1.HTTP/22. HTTP/2 的核心特性3. HTTP/2 的优