1.分糖果
原题：https://www.luogu.com.cn/problem/P7909
原代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,l,r;
int main(){
cin>>n>>l>>r;
if(r%n==n-1)cout<<n-1;
else if(l%n==n-1)cout<<n-1;
else if((r-(r%n)-1)>=l)cout<<n-1;
else{
ll ans=-1e9;
for(ll i=l;i<=r;i++)ans=max(ans,i%n);
cout<<ans;
}
return 0;
}
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,l,r;
int main(){
cin>>n>>l>>r;
if(r-n<n)cout<<r-n;
else{
ll ans=-1e9;
for(ll i=l;i<=r;i++)ans=max(ans,i%n);
cout<<ans;
}
return 0;
}
解题思路：
当r-n<n时，直接输出r%n，否则遍历l到r，枚举每个数模n的最大值
错误原因：
直接遍历l到r，复杂度很高，所以超时
2.插入排序
原题：https://www.luogu.com.cn/problem/P7910
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+255;
struct node{
int id,v;
}a[N];
int w[N],n,q,op,x,y;
bool cmp(node a,node b){
if(a.v==b.v)return a.id<b.id;
return a.v<b.v;
}
void init(){
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i].v,a[i].id=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)w[a[i].id]=i;
}
void Solve(){
while(q--){
cin>>op>>x;
if(op==1){
cin>>y;
int nump=w[x];
if(a[nump].v>y){
a[nump].v=y;
for(int j=nump;j>1;j--){
if(a[j].v<a[j-1].v||a[j].v==a[j-1].v&&a[j].id<a[j-1].id){
w[a[j].id]=j-1;
w[a[j-1].id]=j;
swap(a[j],a[j-1]);
}else break;
}
}else if(a[nump].v<y){
a[nump].v=y;
for(int j=nump;j<n;j++){
if(a[j].v>a[j+1].v||a[j].v==a[j+1].v&&a[j].id>a[j+1].id){
w[a[j].id]=j+1;
w[a[j+1].id]=j;
swap(a[j],a[j+1]);
}else break;
}
}
}else cout<<w[x]<<'\n';
}
}
int main(){
init();
Solve();
return 0;
}
解题思路：
这道题模拟会超时，可以定义一个数组，存储每个数的位置，每次更新数值时，更新排名，输出即可
3.网络连接
原题：https://www.luogu.com.cn/problem/P7911
代码：
#include<bits/stdc++.h>
#include<cstdio>
#define ll long long
using namespace std;
map<string,int>Ser;
int n;
bool isok(char s[]){
int a=-1,b=-1,c=-1,d=-1,e=-1;
int t=sscanf(s,"%d.%d.%d.%d:%d",&a,&b,&c,&d,&e);
if(t!=5)return 0;
if(a<0||a>255)return 0;
if(b<0||b>255)return 0;
if(c<0||c>255)return 0;
if(d<0||d>255)return 0;
if(e<0||e>65535)return 0;
char s1[35];
sprintf(s1,"%d.%d.%d.%d:%d",a,b,c,d,e);
int len=strlen(s);
for(int i=0;i<len;i++)if(s[i]!=s1[i])return 0;
return 1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
char op[35],s[35];
cin>>op>>s;
if(op[0]=='S'){
if(!isok(s))cout<<"ERR\n";
else if(Ser.count(s))cout<<"FAIL\n";
else Ser[s]=i,cout<<"OK\n";
}else if(op[0]=='C'){
if(!isok(s))cout<<"ERR\n";
else if(!Ser.count(s))cout<<"FAIL\n";
else cout<<Ser[s]<<'\n';
}
}
return 0;
}
解题思路：
大模拟，按题目要求模拟即可
4.小熊的果篮
原题：https://www.luogu.com.cn/problem/P7912
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+255;
struct node{
int v,pre,next;
}a[N];
int n,tb[N][3],js=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].v);
a[i].pre=i-1;
a[i].next=i+1;
}
a[0].v=a[0].pre=-1;
a[0].next=1;
js=1;
tb[1][0]=tb[1][1]=tb[1][2]=1;
for(int i=2;i<=n;i++){
if(a[i].v==a[tb[js][1]].v){
tb[js][1]=i;
tb[js][2]++;
}else{
tb[++js][0]=i;
tb[js][1]=i;
tb[js][2]=1;
}
}
while(js){
int js1=0;
for(int i=1;i<=js;i++){
printf("%d ",tb[i][0]);
int p=tb[i][0];
tb[i][0]=a[p].next;
a[a[p].pre].next=a[p].next;
a[a[p].next].pre=a[p].pre;
if(tb[i][2]>=2){
if(js1==0||a[tb[i][0]].v!=a[tb[js1][1]].v){
tb[++js1][0]=tb[i][0];
tb[js1][1]=tb[i][1];
tb[js1][2]=tb[i][2]-1;
}else{
tb[js1][1]=tb[i][1];
tb[js1][2]+=tb[i][2]-1;
}
}
}
puts("");js=js1;
}
return 0;
}
解题思路：
双向链表模拟即可