【题解】牛客寒假集训营第二场 （C~J后八题）
牛牛与棋盘
https://ac.nowcoder.com/acm/contest/9982/H
Level 0 牛牛与棋盘
对标cf难度：700
知识点：模拟
签到题。按题意直接打印即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll n,i,j,k,t,_=1;
// cin>>_;
while(_--){
cin>>n;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if((i+j)%2==0)cout<<0;
else cout<<1;
}
cout<<endl;
}
}
}
level 2 牛牛的“质因数”
对标cf难度：1600
知识点：dfs/dp，数论
我们可以根据x以及x的最小素因子k，推出的值（p≤k）：等价于在
的前面添加一个p。这个用dfs搜索即可得出答案（需要先筛出4e6以内的素数）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 4000600
int mod = 1e9+7;
int num[N], prim[5000060];
int pn = 0;
void table(){
memset(num, -1, sizeof(num));
for(int i = 2;i < N;i++){
if(num[i]) prim[pn++] = i;
for(int j = 0;j < pn && 1LL*i*prim[j] < N;j++){
num[i*prim[j]] = 0;
if(i % prim[j] == 0) break;
}
}
}
ll power(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
ll inv(ll x){
return power(x,mod-2);
}
int a[100010][2];
ll res=0,n;
ll gao(ll x){
int cnt=0;
while(x)x/=10,cnt++;
return cnt;
}
void dfs(ll x,ll val,ll cnt,ll p){ //当前的值 当前的贡献 当前的位数 当前的最小素因子位置
res=(res+val)%mod;
for(int i=0;i<=p;i++){
if(x*prim[i]<=n){
dfs(x*prim[i],(val+power(10,cnt)*prim[i])%mod,cnt+gao(prim[i]),i);
}
else break;
}
}
int main(){
table();
ll i,j,k,m,t,_=1;
// cin>>_;
while(_--){
cin>>n;
for(i=0;prim[i]<=n;i++){
dfs(prim[i],prim[i],gao(prim[i]),i);
}
cout<<res;
}
}
level 2 牛牛想要成为hacker
对标cf难度：1500
知识点：构造
前面用斐波那契数列填充，后面全部用1即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000600
int mod = 1e9+7;
int num[N], prim[500060];
int pn = 0;
ll res=0,n;
ll a[100010];
int main(){
a[0]=2;
a[1]=3;
ll i,j,k,m,t,_=1;
for(i=2;i<=40;i++)a[i]=a[i-1]+a[i-2];
// cout<<a[40]<<endl;
// cin>>_;
while(_--){
cin>>n;
for(i=0;i<n;i++){
if(i<40)cout<<a[i]<<" ";
else {
cout<<1<<" ";
// cout<<a[i]<<" ";
}
}
}
}
level 3 牛牛与交换排序
对标cf难度：1700
知识点：数据结构（双端队列）
这道题使用双端队列（deque）可以达到O(1)进行模拟翻转操作。
具体的方式是：正常情况下队列头进尾出，翻转后尾进头出，用一个变量记录是否翻转的状态即可。
由于k是固定的，并且翻转的区间单调递增，所以可以一次遍历解决本题。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll res=0,n;
ll a[100010],b[100010];
int main(){
ll i,j,k,m,t,_=1;
// cin>>_;
while(_--){
cin>>n;
int m1=0;
for(i=1;i<=n;i++){
cin>>a[i];
}
for(i=1;i<=n;i++){
if(a[i]!=i)break;
}
if(i==n+1){
cout<<"yes\n1";
}
else{
j=i;
for(i=1;i<=n;i++)if(a[i]==j)break;
int p=i,out=p-j+1;
deque<int>q;
for(i=j;i<p;i++)q.push_back(a[i]);
int jud=0,temp=j,tt=1;
// cout<<p<<endl;
for(i=p;i<=n;i++){
if(tt){q.push_back(a[i]);}
else q.push_front(a[i]);
if(q.back()==temp){
q.pop_back();
tt=0;
}
else if(q.front()==temp){
q.pop_front();
tt=1;
}
else {jud=1;break;}
temp++;
}
if(!jud){
j=0;
for(deque<int>::iterator it=q.begin();it!=q.end();it++){
b[j++]=(*it);
// cout<<(*it)<<endl;
}
// cout<<temp<<" "<<p<<endl;
if(b[0]==temp){
for(i=0;i<j;i++){
if(b[i]!=temp+i)jud=1;
}
}
else{
for(i=0;i<j;i++){
if(b[i]!=n-i)jud=1;
}
}
}
if(jud)cout<<"no";
else cout<<"yes"<<endl<<out;
}
// cout<<a[i-1];
}
}
/*
5
3 4 5 1 2
*/
level 3 牛牛与字符串border
对标cf难度：1800
知识点：字符串
分类讨论。
如果，那么k、2k、...都要满足要求，在纸上画一下容易得出重复段长度为gcd(k,n)。
如果，可以发现重复段长度为
即可。
用桶记录一下每个对应位置的次数，求出最大值。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m,i,j;
string s;
cin>>n>>m;
cin>>s;
string out="";
int g=__gcd(n,m);
if(n<m*2&&n!=m)g=n-m;
for(i=0;i<g;i++){
int tong[26]={0};
for(j=i;j<n;j+=g){
tong[s[j]-'a']++;
}
int ma=0,mi=0;
for(j=0;j<26;j++){
if(tong[j]>ma)ma=tong[j],mi=j;
}
out+='a'+mi;
}
for(i=0;i<n/g;i++)cout<<out;
for(i=0;i<n%g;i++)cout<<out[i];
cout<<endl;
}
}level 3 牛牛与整除分块
对标cf难度：1700
知识点：数论
将n/k分为两部分：若，那么每个n/k都是不同的。否则每个n/k都是相同或连续的。
但需要注意特判一种特殊情况：若，那么
，这时n/x向下取整是x-1，和n/k=x+1相差为2，需要特判。
ps:这道题卡输入卡吐了。。不关同步cin会超时，关同步带endl会超时。
目前经过实验得出的结论是：关闭同步，并且不使用endl而是用'\n'是最快的，其次是scanf。不关同步或者使用endl都特别慢，遇到1e6级别的输入输出直接爆炸。。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000600
int mod = 1e9+7;
int num[N], prim[500060];
int pn = 0;
ll res=0,n;
ll a[100010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
a[0]=1;
a[1]=1;
ll i,j,k,m,t,_=1;
scanf("%lld",&_);
// cin>>_;
while(_--){
scanf("%lld%lld",&n,&k);
if(k*k<=n)printf("%lld\n",k);
else {
ll cnt=sqrt(n);
cnt+=5;
while(cnt*cnt>n)cnt--;
int jud=0;
if(cnt*(cnt+2)==n)jud++;
printf("%lld\n",cnt+(n/cnt-n/k)-jud);
}
// cout<<a[i-1];
}
}
level 4 牛牛与比赛颁奖
对标cf难度：2100
知识点：离散化、差分前缀和
这道题题意很明显，思路也很明显，按照题意模拟就行。注意数据范围到了1e9，这样离散化一下就变成1e5的数量级了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000600
int mod = 1e9+7;
int num[N], prim[500060];
int pn = 0;
ll res=0,n;
ll a[100010][2],lsh[300030],sum[300030],tong[100010];
map<int,int>mp;
int main(){
ll i,j,k,m,t,_=1;
// cin>>_;
while(_--){
cin>>n>>m;
int c1=n/10+(n%10!=0),c2=n/4+(n%4!=0),c3=n/2+(n%2!=0);
c1=max(c1,1);
c1=max(c1,1);
c1=max(c1,1);
set<int>s;
for(i=0;i<m;i++){
int l,r;
cin>>l>>r;
a[i][0]=l;
a[i][1]=r;
s.insert(r+1);
s.insert(l);
s.insert(r);
}
j=1;
for(set<int>::iterator it=s.begin();it!=s.end();it++){
lsh[j]=(*it);
mp[(*it)]=j++;
}
for(i=0;i<m;i++){
int l=a[i][0],r=a[i][1];
sum[mp[l]]++,sum[mp[r+1]]--;
}
for(i=1;i<300000;i++){
sum[i]+=sum[i-1];
}
for(i=1;i<300000;i++){
if(sum[i]){
tong[sum[i]]+=lsh[i+1]-lsh[i];
}
}
// for(i=1;i<=m+1;i++)cout<<tong[i]<<endl;
// cout<<endl;
int o1=0,o2=0,o3=0,temp=0;
// cout<<c1<<" "<<c2<<" "<<c3<<endl;
int ou1=0,ou2=0,ou3=0;
for(i=m;i>0;i--){
temp+=tong[i];
// cout<<i<<" "<<temp<<endl;
if(temp>=c1&&!o1)o1=i;
if(temp>=c2&&!o2)o2=i;
if(temp>=c3&&!o3)o3=i;
}
for(i=m;i>0;i--){
if(i>=o1)ou1+=tong[i];
else if(i>=o2)ou2+=tong[i];
else if(i>=o3)ou3+=tong[i];
}
cout<<ou1<<" "<<ou2<<" "<<ou3<<endl;
// cout<<tong[o3]<<" "<<tong[o2]<<" "<<tong[o1]<<endl;
}
}
level 4 牛牛与跷跷板
对标cf难度：2000
知识点：最短路、双指针
看到这个题应该第一时间想到bfs求最短路，但怎么建图是个难点。
我的方法是:首先开1e5个vector。第i个vector存纵坐标为i的跷跷板（用结构体，存l、r以及跷跷板编号）。
然后对每个vector进行排序，这样在搞第i个vector的时候，可以用另外一个指针扫下一个vector，这样就能达成O(n)建图了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000600
int mod = 1e9+7;
int num[N], prim[500060];
int pn = 0;
ll res=0,n;
struct line{
int l,r,i;
};
vector<line>a[100010];
vector<int>g[100010];
int dep[100010],visited[100010];
bool cmp(line a,line b){
return a.l<b.l;
}
map<int,int>mp;
void out(){
int i,j;
for(i=0;i<4;i++){
cout<<i<<":"<<endl;
for(j=0;j<g[i].size();j++){
cout<<g[i][j]<<" ";
}
cout<<endl;
}
}
int main(){
ll i,j,k,m,t,_=1;
// table();
// cout<<a[40]<<endl;
// cin>>_;
while(_--){
cin>>n;
for(i=1;i<=n;i++){
int y;
line temp;
cin>>y;
cin>>temp.l>>temp.r;
temp.i=i;
a[y].push_back(temp);
}
for(i=0;i<=1e5;i++)sort(a[i].begin(),a[i].end(),cmp);
for(i=0;i<=1e5;i++){
k=0;
for(j=0;j<a[i].size();j++){
if(j<a[i].size()-1&&a[i][j].r==a[i][j+1].l){
int u=a[i][j].i,v=a[i][j+1].i;
g[u].push_back(v);
g[v].push_back(u);
}
if(i==1){
// cout<<a[i][0].l<<" "<<a[i+1][0].r<<endl;
}
while(k<a[i+1].size()&&a[i+1][k].r<=a[i][j].l)k++;
while(k<a[i+1].size()&&a[i+1][k].l<a[i][j].r){
int u=a[i][j].i,v=a[i+1][k].i;
g[u].push_back(v);
g[v].push_back(u);
k++;
}
k--;
}
}
// out();
queue<int>q;
q.push(1);
visited[i]=1;
while(!q.empty()){
int temp=q.front();
for(i=0;i<g[temp].size();i++){
if(!visited[g[temp][i]]){
visited[g[temp][i]]=1;
dep[g[temp][i]]=dep[temp]+1;
q.push(g[temp][i]);
}
}
q.pop();
}
cout<<dep[n];
}
}
/*
4
1 2 5
0 0 4
1 0 1
2 0 3
*/
剩下的两道题一个数据结构，一个图论，都是我比较弱的部分（我有个数据结构和图论很强的队友，所以先不补了ww这两个题让队友补）
这场比赛的题目质量非常高，%%%%%%%智乃姐姐
投递理想汽车等公司10个岗位 >
