Gym 102152
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
http://codeforces.com/gym/102152
A B Memory Management System
It is your first day in your new job and guesses what, your first task is already waiting for you! Your task is to build a memory management system.
In this system, the memory will consist of m bytes ordered from 1 to m. Originally, there are n files in the system, such that the ith file is occupying all bytes from li to ri (inclusive). It is guaranteed that no two files share the same memory position (byte).
The main goal of the system is to answer multiple queries such that each query consists of a file of size k bytes, and the system must determine if there exist at least k consecutive bytes that can be reserved and assigned to that file.
Formally, at the jth query, you are given an integer kj and your task is to find a pair of integers lj and rj, such that:
All bytes between lj and rj (inclusive) are free (not occupied).
rj?lj+1≥kj.
If there are multiple solutions, find the one with the maximum rj. If there are still multiple solutions, find the one with maximum lj.
If the jth file cannot be saved in the system, both lj and rj must be ?1.
Please note that you are not reserving the bytes for the files in the queries, you are just checking if there exists an empty space for the file in the system. So, an empty byte in the system can be assigned to multiple queries files. However, if a byte is originally occupied in the system, you cannot use it for the queries files.
Input
The first line contains an integer T (1≤T≤10) specifying the number of test cases.
The first line of each test case contains three integers n, m, and q (0≤n≤m, 1≤m≤105, 1≤q≤min(105,m)), in which n is the number of files in the system originally, m is the number of bytes the system contains, and q is the number of queries.
Then n lines follow, each line contains two integers li and ri (1≤li≤ri≤m), giving the files in system. It is guaranteed that no two files share the same memory position (byte).
Then q lines follow, each line contains an integer kj (1≤kj≤m), giving the queries.
Output
For each query j, print two space-separated integers lj and rj, as described in the problem statement. If there are multiple solutions, find the one with the maximum rj. If there are still multiple solutions, find the one with maximum lj. If the file cannot be saved in the system, both lj and rj must be ?1.
Example
Input
2
3 9 2
1 1
5 5
8 9
3
2
2 5 3
5 5
1 2
1
2
4
Output
2 4
6 7
4 4
3 4
-1 -1
Note
In the first test case, the memory system can be represented as “OFFFOFFOO”, in which ‘O’ represent an occupied position and ‘F’ represent a free position.
The first file needs to occupy 3 bytes. So, the only available answer is 24.
The second file needs to occupy 2 bytes. There are 3 available intervals, which are: 23, 34, and 67. The interval that satisfies the problem conditions is 67.
此题答案来自https://blog.csdn.net/weixin_43824158/article/details/89072459
#include
using namespace std;
map >mp;
//pair分别对应L,R
int a[100010];
int main()
{
int t,n,m,q,l,r;
scanf("%d",&t);
while(t--)
{
mp.clear();
memset(a,0,sizeof(a));
scanf("%d%d%d",&n,&m,&q);
for(int i=1;
i<=n;
i++)
{
scanf("%d%d",&l,&r);
for(int j=l;
j<=r;
j++)
a[j]=1;
}
int ans=0;
for(int i=m;
i>=1;
i--)//从后往前寻找简单些，因为我从前往后找TLE了～～
{
int s,sum=0;
if(a[i]==0)//空闲
{
s=i;
//记录最后一个空闲的位置
while(a[i]==0&&i>=1)//往前找空闲位置
{
i--;
sum++;
}
}
if(sum>ans)//足够大了才有更新的余地
{
for(int j=ans+1;
j<=sum;
j++)//只需更新原来没有记录的即可，因为只要更新过的肯定是最优的
{
mp[j].first=s-j+1;
//l位置
mp[j].second=s;
//r位置
}
ans=sum;
//更新最优值
}
}
while(q--)
{
int x;
scanf("%d",&x);
if(x>ans)//没有最大连续长度为x的
printf("-1 -1\n");
//还卡printf也是醉了
else
printf("%d %d\n",mp[x].first,mp[x].second);
}
}
return 0;
}
C Large GCD
This problem is very simple so the problem setters decided that its statement should be simple too. You are given two integers n and m such that gcd(n,m)≡1, and your task is to find the value of the function F(n,m) as follows:
F(n,m)=gcd(5n+7n,5m+7m)
In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, the gcd of 8 and 12 is 4.
Input
The first line contains an integer T (1≤T≤105) specifying the number of test cases.
Each test case consists of a single line contains two integers n and m (1≤n,m≤109,gcd(n,m)≡1).
Output
For each test case, print a single line containing the value of the function F(n,m) as described in the statement.
Example
Input
2
2 3
5 3
Output
2
12
Note
In the first test case, the value of the function can be found as follow:
F(2,3)=gcd(52+72,53+73)
F(2,3)=gcd(74,468)
F(2,3)=2
In the second test case, the value of the function can be found as follow:
F(5,3)=gcd(55+75,53+73)
F(5,3)=gcd(19932,468)
F(5,3)=12
题记：这题就是找规律了，找到就很简单，找不到就凉凉。
#include
using namespace std;
int main(){
int t, a, b;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &a, &b);
if(a%2 == 0 || b % 2==0) printf("2\n");
else printf("12\n");
}
return 0;
}
D E D-Building Strings
You are given a string s of length n consisting of lowercase English letters. This string can be used to build other strings. The cost of each letter in s is given by another string c of length n consisting of digits, such that the cost of using the letter si is ci coins.
Also, you are given another string p of length m consisting of unique lowercase English letters. Your task is to find the minimum cost to build string p by using the letters of s. Can you?
Input
The first line contains an integer T (1≤T≤500) specifying the number of test cases.
The first line of each test case contains two integers n and m (1≤n≤103,1≤m≤26), in which n is the length of strings s and c, and m is the length of string p.
Then 3 lines follow, each line contains a string, giving the string s, c, and p, respectively. Both strings s and p contains only lowercase English letters, while string c contains only digits. Also, string p is consisting of unique letters.
Output
For each test case, print a single line containing the minimum cost of building the string p by using the letters of string s. If string p cannot be built using string s, print ?1.
Example
Input
3
4 2
abcd
1234
ac
4 4
abcd
1234
abec
5 3
abcba
24513
acb
Output
4
-1
8
Note
In the first test case, you have to use the 1st and 3rd letters of string s to build string p. So, the total cost is 1+3=4.
In the second test case, you cannot build string p using s because the letter ‘e’ from p does not exist in s. So, the answer is ?1.
In the third test case, the optimal way is to use the 1st, 3rd, and 4th letters of string s to build p. So, the total cost is 2+5+1=8.
题记：需要注意字母对应的数字是可以为0的。
#include
#include
#include
using namespace std;
char a[1005];
char str[1005];
char b[1000];
int main()
{
int t, n, m, i, j, k;
scanf("%d", &t);
while (t--)
{
int t[1005];
memset(t, -1, sizeof(t));
scanf("%d%d", &n, &m);
scanf("%s", str);
scanf("%s", a);
for (i = 0;
i < n;
i++)
{
if (t[str[i]] > a[i]-'0'||t[str[i]]==-1)
t[str[i]] = a[i]-'0';
}
int ans = 0;
scanf("%s", b);
int flag = 0;
for (i = 0;
i < strlen(b);
i++)
{
if (t[b[i]] == -1)
{
flag = 1;
break;
}
ans += t[b[i]];
}
if (flag)
printf("-1\n");
else
printf("%d\n", ans);
}
return 0;
}
F E-camelCase
Camel case is a naming convention practice for multi-word identifiers in programming languages. In this practice, each word except for the first word will begin with an uppercase letter, with no intervening spaces or punctuation.
For example, “problem”, “contestName”, and “contestStartingTime” are all following the camel case practice, while “Server”, “ProblemName”, and “first-Place” are not.
in this problem, you are given a variable name that is following the camel case naming practice, and your task is to determine if the variable name is accepted or not. A variable name is accepted if it is consisting of no more than 7 words.
文章图片
Input
The first line contains an integer T (1≤T≤100) specifying the number of test cases.
Each test case consists of a single line containing a string s of length no more than 100, giving a variable name. It is guaranteed that the variable name is following the camel case practice as described in the statement, and it contains only lowercase and uppercase English letters.
Output
For each test case, print a single line containing “YES” (without quotes) if the given variable name is accepted. Otherwise, print “NO” (without quotes).
Example
Input
2
weFoundYou
isTheCamelCaseTheBestWayToNameAVariable
Output
YES
NO
Note
In the first test case, the variable name consists of 3 words, which are: “we”, “Found”, and “You”. So, this variable name is accepted.
In the second test case, the variable name consists of 11 words, which are: “is”, “The”, “Camel”, “Case”, “The”, “Best”, “Way”, “To”, “Name”, “A”, “Variable”. So, this variable name is not accepted.
题记：找出有几个大写字母即可，注意第一个单词是小写字母开头（也算一个单词）。
#includeusing namespace std;
char str[1005];
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>str;
int flag=0;
if(str[0]<'a'||str[0]>'z')
{
printf("NO\n");
continue;
}
int sum=1;
for(int i=1;
i='A'&&str[i]<='Z')
sum++;
if(sum>7)
{
flag=1;
break;
}
if(!isalpha(str[i]))
{
flag=1;
break;
}
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
G H The Universal String
Have you ever heard about the universal string? This is the largest string in the world, and it is the mother of all strings that will ever exist in any programming language!
The universal string is an infinite string built by repeating the string “abcdefghijklmnopqrstuvwxyz” infinitely. So, the universal string will look like this:
" …nopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklm…"
You are given a string p and your task is to determine if p is a substring of the universal string. Can you?
A substring of s is a non-empty string x = s[l… r] = slsl+1… sr (1 ≤ l ≤ r ≤ |s|). For example, “code” and “force” are substring of “codeforces”, while “coders” is not.
Input
The first line contains an integer T (1≤T≤103) specifying the number of test cases.
Each test consists of a single line containing a non-empty string p of length no more 103 and consisting only of lowercase English letters.
Output
For each test case, print “YES” (without quotes) if the given string is a substring of the universal string. Otherwise, print “NO” (without quotes).
Example
Input
3
abcde
abd
wxyzabc
Output
YES
NO
YES
题记：把字符串逐个遍历即可。
#includeusing namespace std;
char str[1005];
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>str;
int flag=0;
for(int i=0;
i I Array Negations
You are given an array a of n integers, and an integer k. You have to make k negation operations such that at each operation you need to choose an element ai from the array and replace it with ?ai.
Your task is to find the optimal way to make the k negation operations such that at the end the sum of the array a is as maximal as possible. Can you?
Input
The first line contains an integer T (1≤T≤100) specifying the number of test cases.
The first line of each test case contains two integers n and k (1≤n≤104, 0≤k≤104), in which n is the size of the array, and k is the number of negation operations to be made.
Then a line follows contains n integers a1,?,an (?100≤ai≤100), giving the array a.
Output
For each test case, print a single line containing the maximum sum of array a after making the required number of negation operations.
Example
Input
3
3 1
4 6 2
4 2
-1 0 2 1
5 2
1 7 -4 2 -3
Output
8
4
17
Note
In the first test case, the optimal way is to make the negation operation on a3. After this, the array will be = [4,6,?2], and its sum is 8.
题记：没有0的情况每次变符号都在最小的数上进行，有0的情况先把负数变号，当负数全部变完后直接全部数加起来即可。
#includeusing namespace std;
int a[10005];
int main()
{
int t,n,m,i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(i=0;
i J Grid Beauty
You are given a grid g consisting of n rows each of which is divided into m columns.
You can swap any two integers in the same row infinitely, but you cannot swap two integers from two different rows.
Your task is to maximize the beauty of the grid by rearranging integers in each row. The beauty of the grid is the number of pairs (i,j) (1
The first line contains an integer T (1≤T≤5) specifying the number of test cases.
The first line of each test case contains two integers n and m (1≤n,m≤103), giving the number of rows and columns in the grid, respectively.
Then n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 108 (inclusive).
Output
For each test case, print a single line containing the beauty of the grid.
Example
Input
2
2 3
1 2 3
4 1 2
3 3
5 7 9
3 2 9
5 3 2
Output
2
3
Note
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
【Gym 102152(CDZSC——2020寒假大一愉悦个人赛)】题记：略。
#includeusing namespace std;
int a[1005][1005];
int main()
{
int t,n,m,i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int ans=0;
for(i=0;
ima;
for(i=0;
i K L
