2024CSP-X 山东小学组题目程序代码

购物（buy）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,w;
 4 int a[200010];
 5 int main() {
 6     cin>>n>>m>>w;
 7     for(int i=1; i<=n; i++) cin>>a[i];
 8     sort(a+1,a+1+n,greater<int>());
 9     long long ans=0,t=0,sum=0,num=0;
10     for(int i=1; i<=n; i++) {
11         ans+=a[i];
12         sum+=a[i];
13         t++;
14     //    cout<<ans<<' '<<sum<<' '<<t<<endl;
15         if(t==m) {
16             if(w<sum) ans=ans-sum+w;
17             sum=0;
18             t=0;
19         }
20     }
21     if(w<sum) ans=ans-sum+w;
22     cout<<ans<<endl;
23     return 0;
24 }

消灭怪兽 (monster) 45分暴力枚举

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,k;
 4 int a[1000010];
 5 long long sum[1000010];
 6 int main() {
 7     cin>>n>>k;
 8     for(int i=1; i<=n; i++) {
 9         cin>>a[i];
10         sum[i]=sum[i-1]+a[i];
11     }
12     int cnt=0;
13     for(int i=1; i<=n; i++) {
14         for(int j=i; j<=n; j++) {
15             long long t=sum[j]-sum[i-1];
16             if(t%k==0) {
17                 cnt++;
18                 //cout<<i<<' '<<j<<' '<<t<<endl; 
19             }
20         }
21     }
22     cout<<cnt;
23     return 0;
24 }

消灭怪兽 (monster) 100分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,k;
 4 int a[1000010];
 5 long long sum[1000010];
 6 long long cnt[2*1000010];
 7 int main() {
 8     cin>>n>>k;
 9     long long ans=0;
10     for(int i=1; i<=n; i++) {
11         cin>>a[i];
12         sum[i]=sum[i-1]+a[i];
13         //if(a[i]%k==0) ans++;//区间中一个数，这个数是K的倍数
14         cnt[sum[i]%k]++;
15         //cout<<sum[i]<<" "<< sum[i]%k<<endl;
16     }
17     cnt[0]++;
18     for(int i=0; i<k; i++) {
19         if(cnt[i]>1) {
20             ans+=(1+cnt[i]-1)*(cnt[i]-1)/2;
21             //cout<<i<<' '<<cnt[i]<<' '<<(1+cnt[i]-1)*(cnt[i]-1)/2<<endl;
22         }
23     }
24     cout<<ans;

翻硬币 (coin)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int a[2000010];
 5 int main() {
 6     cin>>n>>m;
 7     for(int i=1; i<=m; i++) {
 8         int x,y;
 9         cin>>x>>y;
10         a[x]+=1;
11         a[y+1]-=1;
12     }
13     int sum=0;
14     for(int i=1; i<=n; i++) {
15         sum+=a[i];
16         if(sum%2==0) cout<<0;
17         else cout<<1;
18     }
19     return 0;
20 }

刷题 (question)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long n,m,r;
 4 long long a[1000010];
 5 
 6 long long check(long long mid) {
 7     long long s=0,t=0,mmax=0;
 8     for(int i=1; i<=n; i++) {
 9         s=s+a[i];
10         if(a[i]>mmax) mmax=a[i];
11         //cout<<"before "<<i<<' '<<t<<' '<<s<<' '<<mmax<<endl;
12         if(s>mid+mmax) {
13             s=a[i];
14             t++;
15             mmax=a[i];
16         }
17         //cout<<"after "<<i<<' '<<t<<' '<<s<<' '<<mmax<<endl;
18     }
19     if(s!=0) t++;
20     //cout<<"** "<<mid<<' '<<t<<endl;
21     return t;
22 }
23 
24 
25 int work(long long l,long long r) {
26     while(l<r) {
27         long long mid=(l+r)/2;
28         long long t=check(mid); 
29         ///cout<<endl<<"&& "<<l<<' '<<r<<" "<<t<<endl;
30         if(t<=m) r=mid;
31         else l=mid+1;
32         
33     }
34     return l;
35 }
36 
37 int main() {
38     cin>>n>>m;
39     for(int i=1; i<=n; i++) {
40         cin>>a[i];
41         r+=a[i];
42     }
43     cout<<work(0,r+1);
44     //cout<<check(5370);
45     return 0;
46 }