锐客网

  1. 首页 > it技术 > >

Codeforces Round #496 (Div. 3) ABCDE

codeforces

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]

    推荐阅读


    上一篇：Banner轮播图的使用方法

    下一篇：Flutter 中关于 DateTime 时间计算的问题