A. Tanya and Stairways（模拟）
- time limit per test：1 second
- memory limit per test：256 megabytes
Little girl Tanya climbs the stairs inside a multi-storey building. Every time Tanya climbs a stairway, she starts counting steps from 1 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 3 steps, and the second contains 4 steps, she will pronounce the numbers 1,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≤1000) — the total number of numbers pronounced by Tanya.
The second line contains integers a1,a2,…,an (1≤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 x steps, she will pronounce the numbers 1,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 t — the number of stairways that Tanya climbed. In the second line, output t numbers — the number of steps in each stairway she climbed. Write the numbers in the correct order of passage of the stairways.
Examples
7
1 2 3 1 2 3 42
3 4 4
1 1 1 14
1 1 1 1 5
1 2 3 4 51
5 5
1 2 1 2 13
2 2 1 传送门
http://codeforces.com/contest/1005/problem/A
题意
小T爬楼梯，楼梯有多层，每层步数不一样，但是都是从第1步到第$x_i$步。现给定一个数字序列，问小T一共爬了多少层，每层多少步。
题解
只需要考虑序列中1的数量以及每个1后面的数字数量即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int a[maxn];
int ans[maxn];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
ans[i] = 1;
int sum = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i] == 1) // 1的数量
sum++;
else // 1后面的数字数量
ans[sum]++;
}
printf("%d\n", sum);
printf("%d", ans[1]);
for (int i = 2; i <= sum; ++i)
printf(" %d", ans[i]);
return 0;
}B. Delete from the Left（模拟）
- time limit per test：1 second
- memory limit per test：256 megabytes
You are given two strings s and t. 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 1. 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 s and t 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⋅10^5$, 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
test
west2codeforces
yes9test
yes7b
ab1Note
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" 8 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.
传送门
http://codeforces.com/contest/1005/problem/B
题意
给定两个字符串s和t，现要从左至右删去s串和t串的一些字符使s串和t串相等，问删去的最少的字符数量，极端情况为s串和t串都变为空串，输出s.length()+t.length()。
题解
从右往左统计相同的字符数量即可，具体参见代码。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
int ls = s.length(), lt = t.length();
int sum = 0, ans = ls + lt;
while (s[--ls] == t[--lt] && ls >= 0 && lt >= 0) // 记得大于等于0的条件
sum++;
printf("%d\n", ans - sum*2);
return 0;
}C. Summarize to the Power of Two（map）
- time limit per test：3 seconds
- memory limit per test：256 megabytes
A sequence a1,a2,…,an is called good if, for each element aiai, there exists an element ajaj (i≠j) such that ai+aj is a power of two (that is, $2^d$ for some non-negative integer d).
For example, the following sequences are good:
- [5,3,11](for example, for a1=5 we can choose a2=3. Note that their sum is a power of two. Similarly, such an element can be found for a2 and a3),
- [1,1,1,1023],
- [7,39,89,25,89],
- [].
Note that, by definition, an empty sequence (with a length of 0) is good.
For example, the following sequences are not good:
- [16](for a1=16, it is impossible to find another element aj such that their sum is a power of two),
- [4,16](for a1=4, it is impossible to find another element aj such that their sum is a power of two),
- [1,3,2,8,8,8](for a3=2, it is impossible to find another element aj such that their sum is a power of two).
You are given a sequence a1,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≤120000) — the length of the given sequence.
The second line contains the sequence of integers a1,a2,…,an($1≤a_i≤10^9$).
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
6
4 7 1 5 4 915
1 2 3 4 521
1614
1 1 1 10230Note
In the first example, it is enough to delete one element a4=5. The remaining elements form the sequence [4,7,1,4,9], which is good.
传送门
http://codeforces.com/contest/1005/problem/C
题意
给定一个序列，如果对于对于序列中的任何一个数$a_i$，都能找到该序列中的另一个数$a_j$，使得$a_i+a_j$之和是2的幂，则称这个序列是好的，现要删去最少的数使一个序列变成好的，空序列也符合要求。
题解
之前是想着打个表保存2的幂，也就31个数，然后使用二分查找，对于$a_i$，2的幂减去$a_i$是否在表中，但是觉得时间复杂度还是很高，就没做下去了。后面看网上的题解，做法类似，但是使用map实现，不需要使用二分查找。
思路就是 我先打一个2次幂的表，之后把我的a[i] 放到map里，之后对于每一个a[i]，我们和表里的每一个数相减，看看得到的数是不是在map里，就好了，需要注意的是 如果相减得到的数和我们的a[i]相等的话，我们要数map里的数字要有两个以上才行。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 120010;
int a[maxn];
int sum[32];
map <int, int> M;
int main()
{
for (int i = 0; i <= 30; ++i) // 打表
sum[i] = 1 << i;
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
if (!M.count(a[i])) // 查看是否存在返回1和0
M[a[i]] = 1;
else
M[a[i]]++;
}
int ans = 0, i, j;
for (i = 0; i < n; ++i)
{
for (j = 0; j <= 30; ++j)
{
int tmp = sum[j] - a[i];
if (tmp == a[i]) // 相等时，看该数是否超过两个
{
if (M[tmp] >= 2)
break;
}
else
{
if (M[tmp]) // 看是否存在
break;
}
}
if (j == 31) // 如果没有找到
ans++;
}
printf("%d\n", ans);
return 0;
}D. Polycarp and Div 3（思维）
- time limit per test：3 seconds
- memory limit per test：256 megabytes
Polycarp likes numbers that are divisible by 3.
He has a huge number s. Polycarp wants to cut from it the maximum number of numbers that are divisible by 3. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after m such cuts, there will be m+1 parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by 3.
For example, if the original number is s=3121, then Polycarp can cut it into three parts with two cuts: 3|1|21. As a result, he will get two numbers that are divisible by 3.
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 3 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⋅10^5$, inclusive. The first (leftmost) digit is not equal to 0.
Output
Print the maximum number of numbers divisible by 3 that Polycarp can get by making vertical cuts in the given number s.
Examples
31212611000000000000000000000000000000000332019201814Note
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 3.
In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and 33 digits 0. Each of the 3333digits 0 forms a number that is divisible by 3.
In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers 00, 99, 201 and 81 are divisible by 3.
传送门
http://codeforces.com/contest/1005/problem/D
题意
给定一个数s，对其进行切割，问最多能获取多少个被3整除的数。
题解
刚开始是想着一遍循环，用sum累加，如果sum%3等于0，那么答案加1，sum变为0，但是这样是不对的，因为当前数不一定要与前面的数配合，也可以与后面的数配合。网上题解是分三种情况考虑的。
考虑将每个数字模3以后的结果。
如果对于当前数字能被3整除（0、3、6、9）模3结果为0的数，则直接个数加1
如果是两个数字那就有四种可能(1,1) (2, 2) (1, 2) (2, 1)其中后两个组合之和为3能被3整除
如果是三个数字对于之前两个数字的组合只剩下(1, 1)和(2, 2) 那么下个数不管是1还是2都可以组成一个3的整数倍所以总结一下有三种情况
1.当前数字模3为0
2.现有的数字之和模3为0（当前正在处理的）
3.有三个数字了一定可以做到模3为0然后一个一个数字处理即可。
太菜了，想不到，还有一种dp的做法没看懂。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
string s;
cin >> s;
int l = s.length();
int sum = 0, ans = 0, n = 0, tmp;
for (int i = 0; i < l; ++i)
{
tmp = (s[i] - '0') % 3; // 考虑取余3后的情况
sum += tmp;
n++;
if (tmp == 0 || sum % 3 == 0 || n == 3) // 一个数，两个数，三个数
{
ans++;
sum = n = 0;
}
}
printf("%d\n", ans);
return 0;
}由于期末复习，差不多一个月没怎么写题，随便做了几个CF的题找下感觉，发现还是一样的菜
。
The end.
2018-07-11 星期三