Codeforces Round #496 (Div. 3) ABCDE

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 #include using namespace std; const int maxn = 200005; typedef long long ll; ll a[40]; ll x[maxn]; int flag[maxn]; map mp; void init() { ll pos=1; for(int i=0; i<=32; i++) { a[i]=pos; pos=pos*2; } return ; } int main() { init(); ios::sync_with_stdio(false); int n; cin>>n; for(int i=1; i<=n; i++) { cin>>x[i]; mp[x[i]]=i; } for(int i=1; i<=n; i++) { for(int j=0; j<=32; j++) { if(a[j]-x[i]<0)continue; if(mp[a[j]-x[i]]&&mp[a[j]-x[i]]!=i) { flag[mp[a[j]-x[i]]]=1; flag[i]=1; break; } } } int ans=0; for(int i=1; i<=n; i++) { if(flag[i]) ans++; } cout<

D. Polycarp and Div 3 题意
将一个数字序列分成多个段,使分出的段中是3的倍数的段数最多
解法
从前向后遍历,如果当前数值本身就是3的倍数,那么直接更新答案,然后将起点更新,如果当前值不是3的倍数,就从当前值往回找,找到起点位置,看是否能构成3的倍数,再更新起点。
D题代码
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef pair pii; typedef pair pll; typedef pair pli; typedef pair pdd; const int maxn = 2e5+5; const int Mod=1000000007; const int INF = 0x3f3f3f3f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const double e=exp(1); const db PI = acos(-1); const db ERR = 1e-10; #define Se second #define Fi first #define pb push_back #define dbg(x) cout<<#x<<" = "<< (x)<< endl char str[maxn]; int main() { scanf("%s",str); int len=strlen(str); int ans=0,pos=-1; for (int i=0; ipos; j--)//如果不是,查看以当前值结尾是否存在3的倍数 { now=now+(str[j]-'0'); if(now%3==0)//存在,更新答案,更新起点,跳出循环 { ans++; now=0; pos=i; break; } } } cout

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 #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef pair pii; typedef pair pll; typedef pair pli; typedef pair pdd; const int maxn = 2e5+5; int a[maxn]; map mp; int main() { ios::sync_with_stdio(false); int n,m,pos; long long ans=0; scanf("%d%d",&n,&m); for(int i=0; i=0; i--) { if(a[i]

    推荐阅读