Codeforces Round #496 (Div. 3)A. Tanya and Stairways time limit per test
1 second memory limit per test
256 megabytes input
standard input output
standard output Little girl Tanya climbs the stairs inside a multi-storey building. Every time Tanya climbs a stairway, she starts counting steps from 11 to the number of steps in this stairway. She speaks every number aloud. For example, if she climbs two stairways, the first of which contains 33 steps, and the second contains 44 steps, she will pronounce the numbers 1,2,3,1,2,3,41,2,3,1,2,3,4.
You are given all the numbers pronounced by Tanya. How many stairways did she climb? Also, output the number of steps in each stairway.
The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.
Input The first line contains nn (1≤n≤10001≤n≤1000) — the total number of numbers pronounced by Tanya.
The second line contains integers a1,a2,…,ana1,a2,…,an (1≤ai≤10001≤ai≤1000) — all the numbers Tanya pronounced while climbing the stairs, in order from the first to the last pronounced number. Passing a stairway with xx steps, she will pronounce the numbers 1,2,…,x1,2,…,x in that order.
The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.
Output In the first line, output tt — the number of stairways that Tanya climbed. In the second line, output tt numbers — the number of steps in each stairway she climbed. Write the numbers in the correct order of passage of the stairways.
Examples input Copy
7 1 2 3 1 2 3 4
output Copy
2 3 4
input Copy
4 1 1 1 1
output Copy
4 1 1 1 1
input Copy
5 1 2 3 4 5
output Copy
1 5
input Copy
5 1 2 1 2 1
output Copy
3 2 2 1
题意分析: 1.题是什么? 题目会给你n个数字,其实就是一定数量如x组1,2,3,4,5,6......,其实就是x个楼梯; 最后要输出的结果就是x个数字,xi表示第i组的数字数目,其实也就是第i个楼梯的台阶数目.
2.思路 这道题设置一个数组保存答案然后挨个检查输入是不是1就好了,不是1就叠加台阶数目steps,是1就说明上一个楼梯已经走完了,可以把上一个楼梯的台阶数存进答案数组并且把台阶数重置为 1了,就是这样了.
3.小细节 因为我们设置的触发是1,所以我们要注意以下俩方面:
1.第一个输入的一定会是1,而第一个楼梯前面是没有有效楼梯的,故而我们为了简单可以直接废掉第一个1,也就是如代码中for循环前读掉1不做处理.
2.由于是1做触发最后一个楼梯是无法被存进答案数组的,故而需要我们对最后一个楼梯额外处理,也就是代码中for循环后面所做的a[anum++]=steps;
ac代码
#include void solve(){
int n,t;
scanf("%d",&n);
int a[10000],anum=0,steps=1;
scanf("%d",&t);
//废掉第一个1
for(int i=1;
i
B. Delete from the Left time limit per test
1 second memory limit per test
256 megabytes input
standard input output
standard output You are given two strings ss and tt. In a single move, you can choose any of two strings and delete the first (that is, the leftmost) character. After a move, the length of the string decreases by 11. You can't choose a string if it is empty.
For example:
- by applying a move to the string "where", the result is the string "here",
- by applying a move to the string "a", the result is an empty string "".
You are required to make two given strings equal using the fewest number of moves. It is possible that, in the end, both strings will be equal to the empty string, and so, are equal to each other. In this case, the answer is obviously the sum of the lengths of the initial strings.
Write a program that finds the minimum number of moves to make two given strings ss and tt equal.
Input The first line of the input contains ss. In the second line of the input contains tt. Both strings consist only of lowercase Latin letters. The number of letters in each string is between 1 and 2?1052?105, inclusive.
Output Output the fewest number of moves required. It is possible that, in the end, both strings will be equal to the empty string, and so, are equal to each other. In this case, the answer is obviously the sum of the lengths of the given strings.
Examples input Copy test
west
output Copy 2
input Copy codeforces
yes
output Copy 9
input Copy test
yes
output Copy 7
input Copy b
ab
output Copy 1
Note In the first example, you should apply the move once to the first string and apply the move once to the second string. As a result, both strings will be equal to "est".
In the second example, the move should be applied to the string "codeforces" 88 times. As a result, the string becomes "codeforces" →→ "es". The move should be applied to the string "yes" once. The result is the same string "yes" →→ "es".
In the third example, you can make the strings equal only by completely deleting them. That is, in the end, both strings will be empty.
In the fourth example, the first character of the second string should be deleted.
`题意分析:
1.题是什么? 其实就是给你两个字符串,你要删除两个字符串左边的某些字符使两个字符串相同,然后问你最少删多少个,由于题目认为空串与空串是相同的故而肯定是有答案的,大不了两个串全部删掉.
2.思路 其实只要判断两个字符串的最长相同后缀就好了,两个串相同后缀前方的都是要删的.求出a串长度为alen,b串长度为blen,相同后缀最长为samesuffix,故而最后答案就是alen+blen-2*samesuffix
ac代码
#include
#include const int maxn=100005;
char a[2*maxn],b[2*maxn];
void solve(){
scanf("%s%s",&a,&b);
int alen=strlen(a),blen=strlen(b);
int t1=alen-1,t2=blen-1;
int samesuffix=0;
while(t1>=0&&t2>=0){
if(a[t1]!=b[t2]) break;
else samesuffix++;
t1--,t2--;
}
printf("%d\n",alen+blen-2*samesuffix);
}int main(){
solve();
return 0;
}
C. Summarize to the Power of Two time limit per test
3 seconds memory limit per test
256 megabytes input
standard input output
standard output A sequence a1,a2,…,ana1,a2,…,an is called good if, for each element aiai, there exists an element ajaj (i≠ji≠j) such that ai+ajai+aj is a power of two (that is, 2d2d for some non-negative integer dd).
For example, the following sequences are good:
- [5,3,11][5,3,11] (for example, for a1=5a1=5 we can choose a2=3a2=3. Note that their sum is a power of two. Similarly, such an element can be found for a2a2 and a3a3),
- [1,1,1,1023][1,1,1,1023],
- [7,39,89,25,89][7,39,89,25,89],
- [][].
Note that, by definition, an empty sequence (with a length of 00) is good.
For example, the following sequences are not good:
- [16][16] (for a1=16a1=16, it is impossible to find another element ajaj such that their sum is a power of two),
- [4,16][4,16] (for a1=4a1=4, it is impossible to find another element ajaj such that their sum is a power of two),
- [1,3,2,8,8,8][1,3,2,8,8,8] (for a3=2a3=2, it is impossible to find another element ajaj such that their sum is a power of two).
You are given a sequence a1,a2,…,ana1,a2,…,an. What is the minimum number of elements you need to remove to make it good? You can delete an arbitrary set of elements.
Input The first line contains the integer nn (1≤n≤1200001≤n≤120000) — the length of the given sequence.
The second line contains the sequence of integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).
Output Print the minimum number of elements needed to be removed from the given sequence in order to make it good. It is possible that you need to delete all nn elements, make it empty, and thus get a good sequence.
Examples input Copy 6
4 7 1 5 4 9
output Copy 1
input Copy 5
1 2 3 4 5
output Copy 2
input Copy 1
16
output Copy 1
input Copy 4
1 1 1 1023
output Copy 0
Note In the first example, it is enough to delete one element a4=5a4=5. The remaining elements form the sequence [4,7,1,4,9][4,7,1,4,9], which is good.
题意分析:
1.题是什么? 其实就是给你n个数字,决定删除其中某些数字,问你该删除多少个,一个数字只要能与其它任意一个数字相加和为2的幂次数,就不用被删除,否则删除.
2的幂次数: 1, 2, 4, 8 ,16 ,32....
2.思路 抓住题的核心,一个数字不被删除一定是有另外至少一个数字需要与他相加和满足为2的幂次数,我们又发现每个数字最大为10^9,最小为1,而2的30次方为1073741824,故而我有了一个危险的想法:
首先能与数字x相加和为2的幂次数的数字只有30个,就是2-x,4-x,8-x,.......1073741824-x,故而如果我们将这n个数字每个数字可配对的另一半都存进一个set集合,处理完之后去set中将这n个数字挨个检查是否于set中存在,存在就说明有另一个数字在找他,他不用被删除!,不存在就说明没有数字能与他配对,他必须删除.
3.小细节
这里其实有个bug,就是如果出现只出现一个数字4,他会通过8-4=4把自己存进set里,这样找的时候实际上是他自己找到可以和自己配对,这是不允许的,而处理这个也挺简单,这种数字其实只有30个,就是1,2,4,8......536870912,也就是2的0次方到2的29次方这么30个数字,特殊的做一个flag数组,使之至少出现两次才能把自己放进set中就好啦.
ac代码
#include
#include
#include
using namespace std;
void solve(){
int muti[31];
//预处理2的幂次数
muti[0]=1;
for(int i=1;
i<31;
i++) muti[i]=muti[i-1]*2;
int n;
scanf("%d",&n);
int flag[30];
//对每个数只能生效一次
for(int i=0;
i<30;
i++) flag[i]=false;
int a[120000];
set s;
for(int i=0;
i0;
j--){
if(muti[j]<=a[i]) break;
else{
if(muti[j]==a[i]*2){ //判断是否2的幂次数出现
if(flag[j-1]) s.insert(a[i]);
else flag[j-1]=true;
}
else s.insert(muti[j]-a[i]);
}
}
}
int ans=0;
for(int i=0;
i
D. Polycarp and Div 3 time limit per test
3 seconds memory limit per test
256 megabytes input
standard input output
standard output Polycarp likes numbers that are divisible by 3.
He has a huge number ss. Polycarp wants to cut from it the maximum number of numbers that are divisible by 33. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after mm such cuts, there will be m+1m+1 parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by 33.
For example, if the original number is s=3121s=3121, then Polycarp can cut it into three parts with two cuts: 3|1|213|1|21. As a result, he will get two numbers that are divisible by 33.
Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.
What is the maximum number of numbers divisible by 33 that Polycarp can obtain?
Input The first line of the input contains a positive integer ss. The number of digits of the number ss is between 11 and 2?1052?105, inclusive. The first (leftmost) digit is not equal to 0.
Output Print the maximum number of numbers divisible by 33 that Polycarp can get by making vertical cuts in the given number ss.
Examples input Copy 3121
output Copy 2
input Copy 6
output Copy 1
input Copy 1000000000000000000000000000000000
output Copy 33
input Copy 201920181
output Copy 4
Note In the first example, an example set of optimal cuts on the number is 3|1|21.
In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by 33.
In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and 3333 digits 0. Each of the 3333 digits 0 forms a number that is divisible by 33.
In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers 00, 99, 201201 and 8181 are divisible by 33.
题意分析:
1.题是什么?
大概就是会给你一个2*10^5长度的数字,要你把这个数字分成连续的x段,每段被重新理解为一个数字,我们必须尽可能分出尽量多的能被3整除的数字段,特殊的,0也能被3整除,我们最后要输出的就是能被3整除的数字段有多少.
2.思路
贪心法则咯,从左到右做贪心,发现一个能被3整除的数字段就答案加1然后重置一些东西,而0自然就遇到就视作一个能被3整除的数字段.
难点在于数字段是任意组装的 比如对于1121中的那个2,我们需要判断112是不是3的整数倍也要判断12是不是3的整数倍,也要判断2是不是3的整数倍,数字小的时候逐个判断没问题,可是大了之后复杂度为n*n,对于120000的数据自然是要爆掉,故而我们必须发现一种高效的方法去判断以下问题:
前方的相邻数字段所代表数字*10加上我新的这个数字是否是3的整数倍!
我们会发现其实我们其实只关心有没有,并不关心是哪一段与这个数字相加满足被3整除,故而我们只用记录前方所有数据段的某种属性,只要这属性能有效的代表这个数据段与后面的计算,如下
147
这个段中7前方分别有14和4,我们自然看得出147是能被3整除的,那如果我们把14记录为2,4记录为1,我们会发现27是3的倍数,13如同47一样也不是3的倍数.
没错,算法的核心就是将前方所有数据段对3整除剩下的余数可能出现的所有情况归总记录下来,对于新出现的数字就只需要进行最多三次处理就能知道是否存在相邻数字段能被3整除,故而复杂度为n;
ac代码
#include const int maxn=100005;
char a[2*maxn];
bool flag[3][2];
//滚动的flag数组,flag[i][now]为真表示前方存在相邻某个数字段对3余数为i
void restflag(int t){
flag[0][t]=true;
//前面没有数字段也可以理解为前方对3余数为0,这个非常重要
for(int i=1;
i<3;
i++) flag[i][t]=false;
}void solve(){
scanf("%s",&a);
restflag(0);
int ans=0,now=0;
for(int i=0;
a[i];
i++){
int t=a[i]-'0';
if(t==0){
ans++;
restflag(now);
}
else{
restflag((now+1)%2);
//先初始化一下当前flag
for(int j=0;
j<3;
j++){
if(flag[j][now]){
if((j*10+t)%3==0){
ans++;
restflag((now+1)%2);
//既然发现了整除3的自然要重置一下
break;
}
else flag[(j*10+t)%3][(now+1)%2]=true;
}
}
now=(now+1)%2;
//滚动flag数组
}
}
printf("%d\n",ans);
}int main(){
solve();
return 0;
}
E1. Median on Segments (Permutations Edition) time limit per test
3 seconds memory limit per test
256 megabytes input
standard input output
standard output You are given a permutation p1,p2,…,pnp1,p2,…,pn. A permutation of length nn is a sequence such that each integer between 11 and nn occurs exactly once in the sequence.
Find the number of pairs of indices (l,r)(l,r) (1≤l≤r≤n1≤l≤r≤n) such that the value of the median of pl,pl+1,…,prpl,pl+1,…,pr is exactly the given number mm.
The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used.
For example, if a=[4,2,7,5]a=[4,2,7,5] then its median is 44 since after sorting the sequence, it will look like [2,4,5,7][2,4,5,7] and the left of two middle elements is equal to 44. The median of [7,1,2,9,6][7,1,2,9,6] equals 66 since after sorting, the value 66 will be in the middle of the sequence.
Write a program to find the number of pairs of indices (l,r)(l,r) (1≤l≤r≤n1≤l≤r≤n) such that the value of the median of pl,pl+1,…,prpl,pl+1,…,pr is exactly the given number mm.
Input The first line contains integers nn and mm (1≤n≤2?1051≤n≤2?105, 1≤m≤n1≤m≤n) — the length of the given sequence and the required value of the median.
The second line contains a permutation p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n). Each integer between 11 and nn occurs in pp exactly once.
Output Print the required number.
Examples input Copy 5 4
2 4 5 3 1
output Copy 4
input Copy 5 5
1 2 3 4 5
output Copy 1
input Copy 15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9
output Copy 48
Note In the first example, the suitable pairs of indices are: (1,3)(1,3), (2,2)(2,2), (2,3)(2,3) and (2,4)(2,4).
题意分析: 1.题是什么? 还是给你n个数字,还有一个m,告诉你这n个数字中有且仅有一个等于m,问你在这n个数字组成的串的所有子串在排序后中位数为m的子串有多少个;
【codeforce|Codeforces Round #496 (Div. 3)(暂时只有前五道)】特别的 1 2 3 4 的中位数定义其实是2.5,不过我们题中取左边的数字也就是2.
2.思路 原始思路就是对每一子串排序然后检查其中位数是不是m,可是这样的复杂度为n^3*logn,妥妥的爆掉,故而我们思考我们是多做了什么事导致复杂度这么高?
其实我们现在最棘手的是确定某个子串之后在找他的中位数还得做个nlogn的排序,复杂度陡升,其实我们不用找这个子串的中位数是多少,我们只需要确定它的中位数是不是m,故而我们可以换一种判断方法:
对于串a,如果a中大于m的数字有larger个,小于m的数字有smaller个,(不存在等于m的,因为题目保重m只有一个),那么只要-1
运用上面的这种判断方法我们判断一个串中位数是否为m的复杂度降到了n!
然后我们发现对于所有的串a,a都可以被分成三部分,m左边的部分,m自己,m右边的部分.
而只要左边部分的larger-smaller加上右边部分的larger-smaller满足条件,串a的中位数就是m,这里其实是一种折半,故而我们只用考虑左边的这部分能与多少个右边的部分匹配.比如:
5 4
2 4 5 3 1
这组测试用例中
4的左串有2和空larger-smaller为-1,0,
4的右串有空和5和5 3和5 3 1,larger-smaller为0,1,0,-1
处理这个左右串复杂度为n,接下来我们要做的就是对于每一个左串找有多少右串的larger-smaller与之和满足判断条件大于等于0小于等于1.
这里对每一个左串在进行右边的匹配的时候可以先对右边进行排序,然后二分查找,可以优化到logn
故而算法总复杂度最终为n*logn,可以接受
ac代码
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=100005;
int a[2*maxn],tleft[2*maxn],tright[2*maxn],leftnum,rightnum;
void solve(){
int n,m,pos;
scanf("%d%d",&n,&m);
for(int i=0;
i=0){
if(a[l]>m) t++;
else t--;
tleft[leftnum++]=t;
}
tleft[leftnum++]=0;
rightnum=0;
int r=pos;
t=0;
while(++rm) t++;
else t--;
tright[rightnum++]=t;
}
tright[rightnum++]=0;
sort(tright,tright+rightnum);
ll ans=0;
for(int i=0;
i
E2. Median on Segments (General Case Edition) time limit per test
3 seconds memory limit per test
256 megabytes input
standard input output
standard output You are given an integer sequence a1,a2,…,ana1,a2,…,an.
Find the number of pairs of indices (l,r)(l,r) (1≤l≤r≤n1≤l≤r≤n) such that the value of median of al,al+1,…,aral,al+1,…,ar is exactly the given number mm.
The median of a sequence is the value of an element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used.
For example, if a=[4,2,7,5]a=[4,2,7,5] then its median is 44 since after sorting the sequence, it will look like [2,4,5,7][2,4,5,7] and the left of two middle elements is equal to 44. The median of [7,1,2,9,6][7,1,2,9,6] equals 66 since after sorting, the value 66 will be in the middle of the sequence.
Write a program to find the number of pairs of indices (l,r)(l,r) (1≤l≤r≤n1≤l≤r≤n) such that the value of median of al,al+1,…,aral,al+1,…,ar is exactly the given number mm.
Input The first line contains integers nn and mm (1≤n,m≤2?1051≤n,m≤2?105) — the length of the given sequence and the required value of the median.
The second line contains an integer sequence a1,a2,…,ana1,a2,…,an (1≤ai≤2?1051≤ai≤2?105).
Output Print the required number.
Examples input Copy 5 4
1 4 5 60 4
output Copy 8
input Copy 3 1
1 1 1
output Copy 6
input Copy 15 2
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
output Copy 97
Note In the first example, the suitable pairs of indices are: (1,3)(1,3), (1,4)(1,4), (1,5)(1,5), (2,2)(2,2), (2,3)(2,3), (2,5)(2,5), (4,5)(4,5) and (5,5)(5,5).
题意分析:
1.题是什么? 其实题和E1大致相同,只是E1中限制了出现的数字为1到n的数且每个数有且仅有一个,故而是较简单的特例,这个E2就除去了这个限制.
2.思路 既然每个数字可能不止出现一次我们判断中位数的公式也得变:
对于串a,如果a中大于m的数字有larger个,小于m的数字有smaller个,等于m的有num个,那么-num
故而E1的思维在这里已经行不通了,一方面范围根据num是变化的,一方面如果对于每个等于m的数都做一个这个过程复杂度为n*n*logn不行.
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 【动态规划】Codeforce 1282B2 K for the Price of One (Hard Version)
- 数论|Mister B and Astronomers CodeForces - 819D（数论）
- Codeforces Round #Pi (Div. 2) （ABCD）
- codeforce|Codeforces Round #643 (Div. 2) C. Count Triangles-- 差分、前缀和