【题解】牛客OI周赛7-普及组
牛客OI周赛7-普及组<救救XX系列>题解：
A 救救喵咪（cat）
题解：
十分简单的签到题，不作讲解。
正确代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1000
using namespace std;
int N;
bool ans_flag=1;
struct Node{
int x,y;
}node[maxn+5];
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%d%d",&node[i].x,&node[i].y);
}
for(int i=1;i<=N;i++){
int ans=0;
int x=node[i].x,y=node[i].y;
for(int j=1;j<=N;j++)
if(i!=j&&node[j].x>x&&node[j].y>y)ans++;
printf("%d\n",ans);
}
return 0;
}
B 救救兔子（rabbit）
题解：
对于10%的数据：
简单的暴力，对于询问直接扫一遍序列，不断更新最接近的元素，输出答案。
对于40%的数据：
在10%数据的基础上套一个循环，对于每个询问处理方法和10%的一样。
对于100%的数据：
是一道使用二分法查找的基础题。对序列进行排序，直接二分就完了……如果这样还不会写的话，请学习二分法，是一种基础算法。
正确代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100000
using namespace std;
int A[maxn+5],N,M,B;
inline void Ef(int x){
int l=1,r=N,m;
if(x<=A[1]){
printf("%d\n",A[1]);
return;
}
if(x>=A[N]){
printf("%d\n",A[N]);
return;
}
while(l<=r){
m=(l+r)>>1;
if(A[m]==x){
printf("%d\n",x);
return;
}
if(A[m]>x)r=m-1;
else l=m+1;
}
if(A[l]-x<x-A[r]){
printf("%d\n",A[l]);
return;
}
else {
printf("%d\n",A[r]);
return;
}
return;
}
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++)scanf("%d",&A[i]);
sort(A+1,A+N+1);
scanf("%d",&M);
while(M--){
scanf("%d",&B);
Ef(B);
}
return 0;
}
C 救救企鹅（penguin）
题解：
对于50%的数据：
暴力，扫描 S 串，用A串去匹配，如果匹配成功就做标记，把标记过的地方转化成B串，最后输出，效率O(N^2)
对于100%的数据：
解法1：
原理和50%的一样，只是在匹配的时候使用 kmp 算法来进行优化，就能够完成。
关于 kmp ：请参考网络上各种博客，核心思想就是使用一个 next 数组来记录字符串前 i 位最长的相同的前后缀长度，然后在匹配的时候跳着匹配，就能够极大地提高字符串匹配的效率。
解法2：
使用字符串哈希来提高匹配效率，效率与kmp一样。其余部分与50%的一样，不多加赘述。
关于字符串哈希算法： noip 普及组有时会考到。学习请参考网络上各种博客，核心思想是将字符串压成数字来达到快速比对的目的。
正确代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxl 5000000
using namespace std;
char S[maxl+5],A[maxl+5],B[maxl+5];
int ls,la,lb,k,nx[maxl+5],ans[maxl+5],last=0;
int main(){
scanf("%s%s%s",S+1,A+1,B+1);
ls=strlen(S+1);
la=strlen(A+1);
lb=strlen(B+1);
k=0;
for(int i=2;i<=la;i++){
while(k&&A[i]!=A[k+1])k=nx[i];
if(A[i]==A[k+1])k++;
nx[i]=k;
}
k=0;
for(int i=1;i<=ls;i++){
while(k&&S[i]!=A[k+1])k=nx[i];
if(S[i]==A[k+1])k++;
if(k==la&&i-la+1>last){
last=i;
ans[i-la+1]=1;
}
}
for(int i=1;i<=ls;i++)
if(ans[i]==0)printf("%c",S[i]);
else {
printf("%s",B+1);
i=i+la-1;
}
return 0;
}
D 数糖纸（candy）
题解：
对于20%的数据：
枚举 l 和 r ，把 l 到 r 间的数取出来放到数组 Q 中，对 Q 排序，统计 Q 中不同元素个数判断是否为 r-l+1 即可。
对于40%的数据：
对原数组离散化，枚举 l ，从左到右枚举 r ，用一个计数数组 num[i] 记录 l 到 r 中数字 i 的个数，考虑 r 每向右移一位， l 到 r 中多了一个数，扔进计数数组
如果扔完数字 i 后 num[i]>1 则说明已经不符合了（否则则不断维护答案）。此时 r 不管如何向右移动答案都不再增加，直接 break 掉 r 的循环。
效率O(n^2)
对于100%的数据：
要标记数字是否存在，看到 x<=1e9，所以考虑用离散化，然后开一个 last 数组， last[i] 表示数字 i 上次出现的位置， via 数组记录数离散化过的数 i 是否出现过。用双指针法，固定一端 l ， r++ ，如果 r 位置上的数字没有出现过，当前答案就++，如果出现过，就更新当前答案，维护一下 via 数组和左指针。记得即时更新答案最大值。最后输出最大值。
正确代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<algorithm>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define inf (int)1e8
typedef unsigned long long ull;
using namespace std;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f*=-1; c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return f*x;
}
const int maxn=1e6+50;
struct Num{
int id;
int data;
}num[maxn];
bool cmp(const Num&a,const Num&b){
if(a.data<b.data)return 1;
return 0;
}
int c[maxn],N,cnt=0,top=0,stk[maxn],ans,max_ans=1,last[maxn];
int l,r;
bool via[maxn];
int main(){
N=read();
for(int i=1;i<=N;i++){
num[i].data=read();
num[i].id=i;
}
sort(num+1,num+N+1,cmp);
num[0].data=-1;
for(int i=1;i<=N;i++){
if(num[i].data!=num[i-1].data)cnt++;
c[num[i].id]=cnt;
}
l=1;r=1;via[c[r]]=1;ans=1;last[c[r]]=r;
while(l<=N&&r<N){
r++;
if(via[c[r]]==0){
ans++;
}
else {
for(int j=l;j<=last[c[r]];j++)via[c[j]]=0;
l=last[c[r]]+1;
ans=r-last[c[r]];
}
via[c[r]]=1;
max_ans=max(max_ans,ans);
last[c[r]]=r;
}
printf("%d\n",max_ans);
return 0;
}
题解也见：https://www.cnblogs.com/AlenaNuna/default.html?page=1
By:AlenaNuna
投递阿里巴巴集团等公司10个岗位
查看7道真题和解析