本文主要是介绍ICPC-思维-CFJamie and Binary Sequence+No to Palindromes!【刷题记录】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://codeforces.com/contest/916/problem/B
Jamie and Binary Sequence
没有一丝丝防备，被审题给坑了（看完题解，折服于贪心）
大家肯定会想到分解成二进制数，然后进行每一位拆分，使得1的个数刚好等于k，但是题目不是构造题。。。。
要求
1.y最小：所有幂次的最大值最小
所以在1的数量符合条件的情况下，每一位幂次要么全往后移（使得y值减小），要么不操作。
2.字典序最大：大的值放前面（负数也是一样）
比如：
1 3 ans=-1 -2 -2
1 4 ans=-2 -2 -2 -2
3.在第一步操作之后，可能会产生1的数量不够，然后为了保持字典序最大，从最后一个1开始拆分，直到数量符合
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e6;
ll n,m;
map<int,int>vis;
int main(){cin>>n>>m;vis.clear();int sum=0;int i=0;int l=0;int r=-1;while(n>0){if(n&1){vis[i]++;sum++;if(r<0)r=i;l=i;}i++;n>>=1;}if(sum>m){printf("No\n");return 0;}else {printf("Yes\n");multiset<int>ms;for(int j=l;j>=-63;j--){//1.从前往后分if(sum+vis[j]<=m){sum+=vis[j];vis[j-1]+=2*vis[j];vis[j]=0;}else break;}for(int k=l;k>=-63;k--){for(int j=0;j<vis[k];j++)ms.insert(k);}int y=ms.size();//2.从最小位进行补位while(y<m){int t=*ms.begin();ms.erase(ms.begin());ms.insert(t-1);ms.insert(t-1);y++;}for(auto it=ms.rbegin();it!=ms.rend();it++)printf("%d ",*it);printf("\n");}return 0;
}
https://codeforces.com/contest/791/problem/C
Bear and Different Names
这个呀，才是构造题。
就是NO的时候让每一段的最后一位等于第一位，这样就不会对中间部分的其他的可能的yes产生影响了
然后呀，这个最坑的一个是名字问题，首字母大写，而且有50个名字，单个字符还不够。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e6;
ll n,m;
int name[105];
int main(){int a,b,c;cin>>n>>m;string s;for(int i=1;i<=n;i++)name[i]=i;//坑点50个名字for(int i=1;i<=n-m+1;i++){cin>>s;if(s[0]=='N'){name[i+m-1]=name[i];}}for(int i=1;i<=n;i++){if(name[i]<26)cout<<char('A'+name[i])<<" ";else {cout<<"A"<<char('a'+name[i]-26)<<" ";}}return 0;
}
https://codeforces.com/contest/237/problem/C
Primes on Interval
质数打表，求质数个数的前缀和，再二分答案（长度）。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e6;
ll n,m;
int a,b,k;
vector<int>prim;
bool vis[maxn+5];
int prisum[maxn+5];
void init(){mem(vis,1);vis[1]=0;prisum[1]=0;for(int i=2;i<=maxn;i++){if(vis[i]){prim.push_back(i);prisum[i]=prisum[i-1]+1;}else prisum[i]=prisum[i-1];for(int j=0;j<prim.size()&&1LL*i*prim[j]<=maxn;j++){vis[i*prim[j]]=0;if(i%prim[j]==0)break;}}
}
bool check(int l){for(int i=a;i<=b-l+1;i++){if(prisum[i+l-1]-prisum[i-1]<k)return false;}return true;
}
int main(){init();cin>>a>>b>>k;int l=0,r=b-a+2,mid,ans=-1;while(l<=r){mid=(l+r)/2;if(check(mid)){ans=mid;r=mid-1;}else l=mid+1;}if(ans>0&&ans<=b-a+1)cout<<ans<<endl;else cout<<"-1\n";return 0;
}
https://codeforces.com/contest/900/problem/C
Remove Extra One
前缀里维护一个区间最大值mx和区间第二大的值mxs
如果一个数是被挡住了，那么他一定是小于前缀区间的最大值，但是大于前缀区间的第二大值。
注意因为第一个不算record数，所以一开始的最大值的数值被定义为-1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e5;
ll n,m;
int b,k;
int a[maxn+5];//i这个数后面有多少个被隐藏的记录数
int main(){cin>>n;int mx=0;int mxs=0;mem(a,0);for(int i=1;i<=n;i++){cin>>m;if(m>mx){//之前的最大值挡不住mxs=mx;///更新最大值mx=m;a[m]=-1;//最大值找后面被它挡住的数}else if(m>mxs){//最大值挡住当前这数a[mx]++;mxs=m;}}a[0]=-1*maxn;int ans=0;for(int i=1;i<=n;i++){//第一个元素是不算record的。if(a[i]>a[ans])ans=i;}cout<<ans<<endl;return 0;
}
https://codeforces.com/contest/464/problem/A
No to Palindromes!
将字符串转化为p进制
然后进行进位判断，同时对于回文部分判断处理有：
相邻相同，第二位+1，后面改成abcabc…
相隔一个相同，第三位+1，后面改成abcabc…
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e5;
ll n,m;
int b,k;
string s;
int a[maxn+5];
int main(){cin>>n>>m;//m-pcin>>s;for(int i=0;i<n;i++)a[i]=s[i]-'a';a[n-1]++;///进制+1while(1){///进位处理for(int i=n-1;i>0;i--){if(a[i]>=m){a[i-1]+=a[i]/m;a[i]=a[i]%m;}}if(a[0]/m>0){cout<<"NO\n";break;}///找回文int repeat=-1;for(int i=0;i<n;i++){if(i+1<n&&a[i]==a[i+1]){repeat=i+2;}if(i+2<n&&a[i]==a[i+2]){repeat=i+3;}if(repeat>=0)break;}if(repeat>=0){//有回文for(int i=0;repeat+i<n;i++){a[i+repeat]=i%3;}a[repeat-1]++;continue;}for(int i=0;i<n;i++)cout<<char(a[i]+'a');printf("\n");break;}return 0;
}
https://codeforces.com/contest/900/problem/B
Position in Fraction
给你分子a，分母b，数字c，求在这个分数的小数形式里，c的位置
这个我想到小数的分类
本质是判断 a * 10 - b的倍数【最大的，小于等于（a*10）】=余数（假设这种叫法）
有限小数：余数为0。。。这里很好判断
无限循环：余数重复。。。这里可能没有c
无限不循环：余数不重复。。。这里我猜测会出现一个c
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e5;
ll m;
int a,b,c;
string s;
map<int,int>hhh;
int main(){cin>>a>>b>>c;int d=__gcd(a,b);a=a/d;b=b/d;ll p=a,temp;int ans=0;hhh.clear();bool f=false;for(int i=1;;i++){temp=p*10/b;p=p*10-temp*b;if(temp==c){//找到ans=i;f=true;break;}if(hhh.find(p)!=hhh.end()){//循环break;}else hhh[p]=i;}if(f)cout<<ans<<endl;else cout<<"-1\n";return 0;
}
https://codeforces.com/problemset/problem/399/B
Red and Blue Balls
这里是找规律
发现和二进制有关系。
从左往右，直到最后一个蓝色球
蓝色是1，红色是0，再翻转这个二进制，就是答案。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e5;
ll m;
int u,v;
string s;
ll num[105];
bool n[105];
int edge[105][105];
int main(){//ios::sync_with_stdio(false);cin>>m;cin>>s;int cur=0;ll sum=0;ll p=1;mem(n,0);for(int i=0;i<m;i++){if(s[i]=='B'){cur=i;n[i]=1;}num[i]=p;p=p*2LL;}for(int i=0;i<=cur;i++){sum=sum+num[i]*n[i];}cout<<sum<<endl;return 0;
}
这篇关于ICPC-思维-CFJamie and Binary Sequence+No to Palindromes!【刷题记录】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
