A. Tanya and Stairways 题意
给你一个序列,序列是按照 1?a,1?b,1?c...1 ? a , 1 ? b , 1 ? c . . . 的顺序出现的,输出所有的a,b,c….
做法
直接遍历,出现1的前一位就要输出,特判最后一位
A. Tanya and Stairways 代码
#include
#include
#include
#include
using namespace std;
const int maxn = 100005;
int a[maxn];
vector ans;
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=0;
i>a[i];
if(a[i]==1&&i!=0)
{
ans.push_back(a[i-1]);
}
}
ans.push_back(a[n-1]);
cout
B. Delete from the Left 题意
给你两个字符串,每次操作可以选择一个字符串删掉他的第一个字母,问最少用多少次操作来让两个字符串相同
解法
找两个串的最长公共后缀就可以了。
B题代码
#include
#include
#include
#include
using namespace std;
int main()
{
ios::sync_with_stdio(false);
string str1,str2;
cin>>str1>>str2;
int len1=str1.size();
int len2=str2.size();
if(len1
C. Summarize to the Power of Two 题意
给你n个数,如果某个数可以加上另一个数得到2的次幂数,那么称这个数为好数,求序列中有多少个数不是好数
解法
用map存一下每个数最后出现的位置,之后暴力算每一个二的次幂数减当前数得到的值是否存在就可以了
C题代码
#include
#include
#include
#include
D. Polycarp and Div 3 题意
将一个数字序列分成多个段,使分出的段中是3的倍数的段数最多
解法
从前向后遍历,如果当前数值本身就是3的倍数,那么直接更新答案,然后将起点更新,如果当前值不是3的倍数,就从当前值往回找,找到起点位置,看是否能构成3的倍数,再更新起点。
D题代码
#include
#include
#include
#include
#include
#include
E1. Median on Segments (Permutations Edition) 【Codeforces Round #496 (Div. 3) ABCDE】题意
给你n个数1-n的序列,再给一个m,问按区间排序后以m作为中位数的区间有多少个
解法
由于每个数都不同,我们就可以先找到m,从m向左遍历,找到到每个下标位置有多少个大于m的数/小于m的数。然后再从m向右遍历计算贡献,计算贡献的时候,如果m到当前下标存在a个大于m的点,那么就找左边有多少个位置存在a/a-1个小于m的点,如果当前下标大于小于m的数量相等,就找左边有多少个位置存在0个大于m的点,或者存在1个大于m的点,如果当前下标存在a个小于m的点,就找左边有多少个位置存在a/a+1个大于m的点。乘积算贡献
E1代码
#include
#include
#include
#include
#include
#include
推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- Codeforces|Codeforces Round #643 (Div. 2) B.Young Explorers