CSP-J模拟赛day6——解析+答案

全人杯奖金

这道题比较简单，跟着题目走就行，只不过要判一下同分的情况

#include<bits/stdc++.h>
using namespace std;
const int INF=100000+10;
int mp[INF];

bool cmp(const int a1,const int a2){
return a1>a2;
}
int x,y,z,m;
int a,b,c,d,e;
int cnt,tmp;
long long ans;
int main(){
//freopen("bouns.in","r",stdin);
//freopen("bouns.out","w",stdout);
int n;
cin>>n;
for (int i=1;i<=n;i++){
cin>>mp[i];
}
sort(mp+1,mp+1+n,cmp);
cin>>x>>y>>z>>m;
cin>>a>>b>>c>>d>>e;

cnt+=x,tmp=cnt;
while (tmp<=n){
if (mp[tmp+1]==mp[cnt])tmp++;
else break;
}
ans+=(tmp-cnt+x)*a;
cnt=tmp;

cnt+=y,tmp=cnt;
while (tmp<=n){
if (mp[tmp+1]==mp[cnt])tmp++;
else break;
}
ans+=(tmp-cnt+y)*b;
cnt=tmp;

cnt+=z,tmp=cnt;
while (tmp<=n){
if (mp[tmp+1]==mp[cnt])tmp++;
else break;
}
ans+=(tmp-cnt+z)*c;
cnt=tmp;

while (cnt<=n){
if (mp[cnt+1]>=m)cnt++,ans+=d;
else break;
}

while (cnt<=n){
if (mp[cnt+1]>0)cnt++,ans+=e;
else break;
}
cout<<ans;
return 0;
}

寻宝

因为这道题的x过大，直接枚举是一定过不了的，但是我们不难发现，这是有循环的，所以我们直接在这里取余就可以了，但是我们又要注意一下当前房间是有楼梯的情况，所以我们可以在此基础上加上一圈在减去当前的情况（有楼梯为1，没有为0），如果是有的，那么就会少跑一点，如果没有，再跑一圈也是可以的。

#include<bits/stdc++.h>
using namespace std;

struct f{
int num,s;
};
f mp[10010][110];
int x,tot[10010];
long long ans;
int main(){
//freopen("treasure.in","r",stdin);
//freopen("treasure.out","w",stdout);
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++){
for (int j=0;j<m;j++){
cin>>mp[i][j].s>>mp[i][j].num;
if (mp[i][j].s==1)tot[i]++;
}
}
cin>>x;
for (int i=1;i<=n;i++){
int tmp1=mp[i][x].num,tmp2=mp[i][x].s;
ans+=tmp1,ans%=20123;
tmp1=tmp1%tot[i]+tot[i]-tmp2;
while (tmp1>0){
x=(x+1)%m;
if (mp[i][x].s==1)tmp1--;
}
}
cout<<ans%20123;
return 0;
}

卖青团的小姑凉

这道题是一道典型的用栈的题，但是因为 $l$ 与 $r$ 过大，所以不能直接存储，所以我们可以开一个结构体，存储左右边界，把结构体存进去，这样在每一次取的时候，用一个while循环来解决就行了

#include<bits/stdc++.h>
using namespace std;
struct f{
long long l,r;
};
stack<f> q;
f x;

long long tot(long long l1,long long r1){
int len=r1-l1+1;
return (l1+r1)*len/2;
}
int main(){
//freopen("sale.in","r",stdin);
//freopen("sale.out","w",stdout);
int n;
cin>>n;
for (int i=1;i<=n;i++){
int op;
cin>>op;
if (op==1){
cin>>x.l>>x.r;
q.push(x);
}else {
long long k,ans=0;
cin>>k;
while(k>0){
x=q.top();
q.pop();
if (x.r-x.l+1<=k)ans+=tot(x.l,x.r),k-=(x.r-x.l+1);
else {
long long ll=x.r-k+1;
ans+=tot(ll,x.r);
x.r=ll-1;
q.push(x);
break;
}
}
cout<<ans<<endl;
}
}
return 0;
}

求和

这道题有点难度，首先我们考虑暴力，就是维护出来每一段的然后再求和，但是这样的话就是 $O(n^2)$ 的时间复杂度，是过不了的，那么我们就要换一个思路。
经过我们的苦思冥想之后，我们想到了可以去计算每个点的贡献值，然后再用贡献值去乘上当前点的数量就可以，那么现在就是如何做的问题。因为要去重，所以是不能直接用乘法原理的，那么此时又有同学说了，能不能维护出来一个点左边有多少个不同于当前点的值，右边又有多少个。这样也是不行的，因为我们没有把所有的区间都统计到。
在此经过我们的苦思冥想之后，发现只要当前点到达左边第一个相同与当前点的下一项，再乘上当前点右边的数量，就可以覆盖所有的区间，那么我们就可以写了

#include<bits/stdc++.h>
using namespace std;
const long long INF=5e5+10;
const long long MOD=1e9+7;
long long a[INF],last[INF];
long long ans;
map<long long,long long> mp;
int main(){
//freopen("sum.in","r",stdin);
//freopen("sum.out","w",stdout);
long long n;
cin>>n;
for (long long i=1;i<=n;i++){
cin>>a[i];
last[i]=mp[a[i]];
mp[a[i]]=i;
}
for (long long i=1;i<=n;i++){
long long tmp=last[i]+1;
ans+=((i-tmp+1)*(n-i+1))%MOD*a[i]%MOD;
ans%=MOD;;
}
cout<<ans%MOD;
return 0;
}

原文地址：https://blog.csdn.net/CylMK/article/details/143055981

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！