挖土機杯總結
2022-10-16 21:56:55 星期日
https://www.luogu.com.cn/contest/87102
前言
本次時J組課程最后一次模擬賽，題目難度略低，思維能力考察靈活，還有代碼能力
對于這一次T1，30多分鐘AC，感覺慢了，T2考試沒想，T3想出來結果代碼不會，T4沒時間
T1
T1就是一個模擬分數的運算，需要考察gcd和lcm，考試時我因為沒寫草稿模擬程序運行結果浪費10多分鐘調試，還好對了，考試T1一定要細心，細心，細心，一定要找一些數據自己模擬，對拍。
T2
考試時沒想出，其實暴力就可以70了，把每個精靈坐標按R1<R2<R3排序，這樣去暴力枚舉每個精靈最大值，并且更新總體最大值。滿分AC就要減小枚舉量。題目中有一個數學公式特別重要，決定了聲望最大值來源，其實就是把文字提示換成數學，想不到思路一定要看看題目中的公式之類考慮特殊性質，本題特殊性質就是當倆個坐標一樣時，聲望取值只跟不同那個有關系，又因為R1<R2<R3不難想到排序一次，把a大的排前提前是b,c相同，我們就可以保證第i個所可以合并的必定在他前面，這樣再去求出最大值即可。
代碼：
點擊查看代碼
#include<bits/stdc++.h>
#define N 500050
using namespace std;
int n,r[4],maxnum1=-1,maxnum2=-1,maxn1=-1,maxn2=-1;
struct node{
int a,b,c,num;
}x[N];
int sw(int w){
return pow(w,3)/4;
}
bool cmp(node a,node b){
if(a.b!=b.b) return a.b<b.b;
if(a.c!=b.c) return a.c<b.c;
return a.a>b.a;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d%d",&r[1],&r[2],&r[3]);
sort(r+1,r+1+3);
x[i].a=r[1],x[i].b=r[2],x[i].c=r[3],x[i].num=i;
if(maxn1<x[i].a){
maxn1=x[i].a;
maxnum1=x[i].num;
}
}
sort(x+1,x+1+n,cmp);
for(int i=2;i<=n;++i){
if(x[i].b==x[i-1].b&&x[i].c==x[i-1].c){
int k=min(x[i].a+x[i-1].a,min(x[i].b,x[i].c));
if(k>maxn2) maxn2=k,maxnum2=i;
}
}
if(maxn1>maxn2){
cout<<0<<endl<<maxnum1<<endl<<sw(maxn1)<<endl;
}
else{
cout<<1<<endl<<x[maxnum2].num<<" "<<x[maxnum2-1].num<<endl<<sw(maxn2);
}
return 0;
}
T3
T3正解為貪心，這個貪心我們畫一條數軸，對于每個點都是k，類似補作業，肯定是把今天截至的先寫完，所以貪心就是把d天必須消滅的優先消滅，思路不難，代碼能力不太好,本題我卡在怎么優先處理今天必須完成的。其實很簡單，今天必須完成的就是昨天剩下的，只要我們把昨天遍歷一次先修改就好了。
代碼：
點擊查看代碼
#include<bits/stdc++.h>
#define maxn 300030
using namespace std;
int n,k,ans,endd;
struct node{
int d,m;
}e[maxn];
vector <node> a[maxn];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i){
scanf("%d%d",&e[i].d,&e[i].m);
a[e[i].d].push_back(e[i]);
endd=max(endd,e[i].d);
}
for(int i=1;i<=endd+1;++i){
int sum=0;
for(auto &t : a[i]) sum+=t.m;
for(auto &t : a[i-1]) sum+=t.m;
sum=min(k,sum);ans+=sum;
for(auto &t : a[i-1]){
int sum1=min(t.m,sum);
t.m-=sum1,sum-=sum1;
}
for(auto &t : a[i]){
int sum1=min(t.m,sum);
t.m-=sum1,sum-=sum1;
}
}
cout<<ans<<endl;
return 0;
}
T4
正解為桶排，這個確實沒有想到，這一題加深了我對于桶排序使用理解。
對于柱子我們枚舉可以組成的高度，把每一個高度組成都算一遍，如高度為h的柱子可能由h-1和1，h-2和2......最后從大到小排一次，最大的便是組成柱子最多數量，枚舉可能的h高度，選用最小的柱子h2到最大柱子h2。
代碼：
點擊查看代碼
#include<bits/stdc++.h>
#define maxn 6060
using namespace std;
int n,cnt[maxn],ans[maxn],minn=1e9,maxx=-1,sum=1;//sum記得初始化為1，至少有一個
bool cmp(int a,int b){
return a>b;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
int a;
scanf("%d",&a);
cnt[a]++;
minn=min(a,minn);
maxx=max(a,maxx);
}//桶排序
for(int i=minn*2;i<=maxx*2;++i){
for(int j=1;;j++){
if(j>i-j) break;
if(i-j==j) ans[i]+=cnt[j]/2;
else{
ans[i]+=min(cnt[j],cnt[i-j]);
}
}
}//枚舉每一個可能的h是由怎么組成的
sort(ans+1,ans+1+maxx*2,cmp);
cout<<ans[1]<<" ";
for(int i=2;i<=maxx*2+1;++i){
if(ans[i]!=ans[i-1]) break;
sum++;
}
cout<<sum<<endl;
return 0;
}
浙公網安備 33010602011771號