The 2024 Sichuan Provincial Collegiate Programming Contest部分题解(L,H,E,B,I)

题面链接:The 2024 Sichuan Provincial Collegiate Programming Contest

L. Beef Tripe in Soup Pot?

思路

签到，模拟不多说了

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n;cin>>n;vector<pll> r1,r2;for(int i=1;i<=n;i++){int a,b,c,d;cin>>a>>b>>c>>d;if(c==1&&d==0){r1.push_back({a,i});}else if(c==0&&d==1){r2.push_back({b,i});}else if(c==1&&d==1){if(a>b){r2.push_back({b,i});}else{r1.push_back({a,i});}}}sort(r1.begin(),r1.end());sort(r2.begin(),r2.end());cout<<r1.size()<<" ";for(auto [x,y]:r1){cout<<y<<" ";}cout<<"\n";cout<<r2.size()<<" ";for(auto [x,y]:r2){cout<<y<<" ";}cout<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;// cin>>_;while(_--) solve();return 0;
}

H. GG and YY's Stone Game

思路

签到的博弈题，不断维护3，第一个人拿1那么第二个人拿2，第一个人拿2第二个人拿1即可，这样就能够保证后手的一定会赢

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n;cin>>n;if(n%3==0){cout<<"1 "<<n/3<<"\n";}else{cout<<"0 "<<n/3+n%3<<"\n";}
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

E. L-Covering Checker

思路

要注意L可以旋转，必须有一个 . 且出现在右上角，之后我们根据题意查一遍所有位置是否合法即可

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;int n,m;
bool check(char ch,int x,int y,vector<vector<char>> &g){if(ch=='D'&&x<n){if(g[x+1][y]!='C') return true;}if(ch=='U'&&x>1){if(g[x-1][y]!='C') return true;}if(ch=='L'&&y>1){if(g[x][y-1]!='C') return true;}if(ch=='R'&&y<m){if(g[x][y+1]!='C') return true;}return false;
}void solve(){    cin>>n>>m;vector<vector<char>> g(n+10,vector<char>(m+10));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];}}if(g[1][m]!='.'){cout<<"No\n";return;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i==1&&j==m) continue;if(g[i][j]=='C'){if(g[i-1][j]=='D'&&g[i][j+1]=='L') continue;if(g[i][j+1]=='L'&&g[i+1][j]=='U') continue;if(g[i][j-1]=='R'&&g[i+1][j]=='U') continue;if(g[i-1][j]=='D'&&g[i][j-1]=='R') continue;cout<<"No\n";return;}else{if(g[i][j]=='.'){cout<<"No\n";return;}if(check(g[i][j],i,j,g)){cout<<"No\n";return;}}}}cout<<"Yes\n";}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

B. Link Summon

思路

合成6问最大的合成数，注意所有数可以当成本身合成也可以当成1合成，秉持着先合成6所需数量少的数先合成贪心地进行分类讨论

首先处理1-5    2-4     3-3

在处理完这三类情况下又可以进行分类讨论

一. 1有剩余：1. 2有剩余   2. 4有剩余

二. 5有剩余：1. 2有剩余   2. 4有剩余

三.1和5都没有剩余  ....

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){vector<int> cnt(6);for(int i=1;i<=5;i++){cin>>cnt[i];}int ans=0;//处理1-5int t=min(cnt[1],cnt[5]);cnt[1]-=t;cnt[5]-=t;ans+=t;//处理2-4t=min(cnt[2],cnt[4]);cnt[2]-=t;cnt[4]-=t;ans+=t;//处理3-3ans+=cnt[3]/2;cnt[3]=cnt[3]%2;if(cnt[5]){     //如果5有剩余if(cnt[4]){     //4残留cnt[5]-=cnt[3];ans+=cnt[3];if(cnt[5]>=cnt[4]){cnt[5]-=cnt[4];ans+=cnt[4];ans+=(cnt[5]/2);}else{cnt[4]-=cnt[5];ans+=cnt[5];ans+=(cnt[4]/3);}}else{if(cnt[5]>=cnt[2]+cnt[3]){cnt[5]-=cnt[2]+cnt[3];ans+=cnt[2]+cnt[3];ans+=(cnt[5]/2);}else{cnt[2]-=cnt[5];ans+=cnt[5];ans+=((cnt[2]+cnt[3])/3);}}}else if(cnt[1]){if(cnt[4]){if(cnt[1]>=2*cnt[4]){ans+=(cnt[4]);cnt[1]-=2*cnt[4];if(cnt[3]&&cnt[1]>=3){cnt[1]-=3;ans++;}ans+=(cnt[1])/6;}else{cnt[4]-=cnt[1]/2;ans+=cnt[1]/2;cnt[1]%=2;ans+=(cnt[1]+cnt[3]+cnt[4])/3;}}else{if(cnt[2]==0){if(cnt[3]){if(cnt[1]>=3){ans++;cnt[1]-=3;}ans+=cnt[1]/6;}else{ans+=cnt[1]/6;}}else{if(cnt[3]){ans++;cnt[1]--;cnt[2]--;}ans+=cnt[2]/3;cnt[2]=cnt[2]%3;if(cnt[2]==1){if(cnt[1]>=4){ans++;cnt[1]-=4;}}else if(cnt[2]==2){if(cnt[1]>=2){ans++;cnt[1]-=2;}}ans+=cnt[1]/6;}}}else{ans+=(cnt[2]+cnt[3]+cnt[4])/3;}cout<<ans<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

I. Container Scheduling

思路

vp赛时想到一个思路便是优先队列里面维护每个可填充矩形，最后发现当我们填充新矩形的时候要对之前的可填充矩形进行分割，维护起来的确有点麻烦，最后写的代码也是成功Wa4了

后来看了别人的题解也是恍然大悟

首先我们在加入一个新矩形时所选的右下角坐标根据题目要求我们要贪心的选择左下角，那么我们发现新加入的矩形的左下角坐标一定是之前加入矩形的左下角坐标和右下角坐标的一个情况，那么我们直接枚举所有可能的x和y判断是否合法即可，x和y要进行排序

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;int n,l,h;
struct node{int x,y,l,h;
};
bool suit(vector<node>&now,node t){if((t.x+t.l>l)||(t.y+t.h>h)){return false;}for(auto rec:now){int x=rec.x;int y=rec.y;int l=rec.l;int h=rec.h;//以下是判断新加入的矩形的边是否穿过此矩形if(((x>=t.x&&x<t.x+t.l)||(x+l>t.x&&x+l<=t.x+t.l))&&(y<t.y+t.h&&y+h>t.y)){return false;}if(((y>=t.y&&y<t.y+t.h)||(y+h>t.y&&y+h<=t.y+h))&&(x<t.x+t.l&&x+l>t.x)){return false;}}return true;
}void solve(){cin>>n>>l>>h;vector<int> X,Y;    //记录新添矩形可选择的坐标X.push_back(0);Y.push_back(0);vector<node> now;   //记录已填充矩形while(n--){int L,H;cin>>L>>H;bool f=false;for(auto x:X){for(auto y:Y){if(suit(now,{x,y,L,H})){f=true;now.push_back({x,y,L,H});cout<<x<<" "<<y<<"\n";X.push_back(x+L);Y.push_back(y+H);sort(X.begin(),X.end());sort(Y.begin(),Y.end());break;}}if(f) break;}if(!f) cout<<"-1\n";}
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;// cin>>_;while(_--) solve();return 0;
}