A 分糖果
考虑分类讨论。
假如 (lfloorfrac{l}{n} floor ot=lfloorfrac{r}{n} floor)，则可以发现其中一定存在一个数 (mod n=n-1)，因此直接输出 (n-1)。
否则，选择 (r) 的答案一定是最优的，输出 (rmod n)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,l,r;
signed main()
{
scanf("%lld%lld%lld",&n,&l,&r);
if(l/n==r/n)
printf("%lld
",r%n);
else
printf("%lld
",n-1);
return 0;
}
B 插入排序
注意到 (n) 和操作 (1) 次数都非常的小，考虑暴力操作。
预处理出每个数有多少个数比它小，修改的时候暴力更改新数在原序列中的关系，查询可以直接得出结果。
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[100010],rk[100010];
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[j]<a[i]||(a[j]==a[i]&&j<i))
rk[i]++;
while(q--)
{
int opt;
scanf("%d",&opt);
if(opt==1)
{
int x,y;
scanf("%d%d",&x,&y);
for(int i=1;i<=n;i++)
if(a[i]>a[x]||(a[i]==a[x]&&i>x))
rk[i]--;
rk[x]=0;
a[x]=y;
for(int i=1;i<=n;i++)
if(a[i]>a[x]||(a[i]==a[x]&&i>x))
rk[i]++;
for(int i=1;i<=n;i++)
if(a[i]<a[x]||(a[x]==a[i]&&i<x))
rk[x]++;
}
else
{
int x;
scanf("%d",&x);
printf("%d
",rk[x]+1);
}
}
return 0;
}
C 网络连接
毒瘤大模拟。
对于一个服务器，考虑先判定串合法性，然后用 map 维护对应的串的出现情况。
对于客户端也是类似的，只要判定合法然后就可以在 map 中查询对应串的出现位置。
判定合法的时候有比较多的细节，需要仔细一些。
#include<bits/stdc++.h>
using namespace std;
int n;
map<string,int> mp;
string tp,id;
int getnumber(string x,int l,int r,int lim)
{
if(l>r)
return -1;
if(r-l+1>lim)
return -1;
if(l!=r&&x[l]=='0')
return -1;
for(int i=l;i<=r;i++)
if(x[i]<'0'||x[i]>'9')
return -1;
int res=0;
for(int i=l;i<=r;i++)
res=res*10+x[i]-'0';
return res;
}
bool check(string x)
{
int cntdian=0,cntmao=0,lstdian=-1;
for(int i=0;i<x.length();i++)
{
if(x[i]=='.')
{
cntdian++;
if(cntdian>3||cntmao!=0)
return 0;
}
if(x[i]==':')
{
cntmao++;
if(cntdian!=3||cntmao>1)
return 0;
}
}
if(cntdian!=3||cntmao!=1)
return 0;
for(int i=0;i<x.length();i++)
{
if(x[i]=='.'||x[i]==':')
{
int res=getnumber(x,lstdian+1,i-1,3);
if(res==-1||res>255)
return 0;
lstdian=i;
}
}
int res=getnumber(x,lstdian+1,x.length()-1,5);
if(res==-1||res>65535)
return 0;
return 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>tp>>id;
if(tp=="Server")
{
if(!check(id))
cout<<"ERR
";
else if(mp[id])
cout<<"FAIL
";
else
mp[id]=i,cout<<"OK
";
}
else if(tp=="Client")
{
if(!check(id))
cout<<"ERR
";
else if(!mp[id])
cout<<"FAIL
";
else
cout<<mp[id]<<'
';
}
}
return 0;
}
D 小熊的果篮
首先预处理出在第一轮哪些水果会被选出。
可以注意到一个水果在第 (i) 轮被删除的必要条件是 (i=1) 或前一个数在 (i-1) 轮被删除了。
因此在每一轮删除的时候，暴力判断下一个数是否要在下一轮被删除即可。
#include<bits/stdc++.h>
using namespace std;
int n,a[500010],lst[500010],nxt[500010];
bool in[500010];
int re[500010],cnt=0,kkk;
int pe[500010],tot=0;
int main()
{
a[0]=-1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),nxt[i]=i+1,lst[i]=i-1;kkk=n;
nxt[0]=1;in[n+1]=1;
lst[n+1]=n;
for(int i=1;i<=n;i++)
if(a[i]!=a[i-1])
re[++cnt]=i,in[i]=1;
while(1)
{
if(kkk==0)
return 0;
for(int i=1;i<=cnt;i++)
{
printf("%d",re[i]);kkk--;
if(i!=cnt)
putchar(' ');
lst[nxt[re[i]]]=lst[re[i]];
nxt[lst[re[i]]]=nxt[re[i]];
if(in[nxt[re[i]]]==0&&a[nxt[re[i]]]!=a[lst[re[i]]])
pe[++tot]=nxt[re[i]],in[nxt[re[i]]]=1;
}
cnt=tot;
for(int i=1;i<=tot;i++)
re[i]=pe[i];
tot=0;
puts("");
}
return 0;
}