2024辽宁省赛-补题（含2024湖南、山东补题链接）
目录
ProblemB.比分幻术
题目，输入，输出：
样例：
题意：
给出比分A-B ，交换A，B后的输出比分即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
char a,b,c;
cin >> a >> b >> c;
cout << c << b <<a;
return 0;
}
ProblemJ.结课风云
题目、输入、输出：
样例：
题意：
输入n代表学生的总个数，a，b，c，分别代表平时分满分，考试分满分，不挂科分数
接下来n行输入每个学生的平时分x，考试分y，最后输入老师给学生平时分加上的分数d，求老师这样操作能使多少学生从挂科变成不挂科
思路：
模拟：定义cnt为给学生平时分加上d后从挂科变不挂科的总个数，当x+y<c时，令x=min( x+d , a)，如果x+y >= c ，则cnt++，最后输出cnt。
代码：
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>v;
int main(){
int n,a,b,c;
cin >> n >> a >> b >> c;
int x,y;
for(int i=0;i<n;i++) {
cin >> x >> y;
v.push_back({x,y});
}
int d;
cin >> d;
int cnt=0;
for(int i=0;i<n;i++){
x=v[i].first,y=v[i].second;
if(x+y>=c) continue; //原本不挂科
x=min(a,x+d); //min: +d后不能超过平时分满分
if(x+y>=c) cnt++; //+d后不挂科
}
cout << cnt ;
return 0;
}
ProblemA.爱上字典
题目、输入、输出：
样例：
题意：
给出一行文本，含不确定个数字符串，一个字符串由一个单词组成，或者由一个单词加一个特殊字符组成，给出n个已学单词(全为小写字母组成)，不会的单词需要查字典，查过的单词都记住，且所有单词不区分大小写(大写字母只可能在单词首位出现)，输出需要查询字典的次数。
思路：
已经学会的单词标记一下，用字符流遍历文本，处理每个字符串，如果首位是大写则转为小写，末尾是特殊字符则去掉，得到一个规范的单词，如果此单词没有被标记则标记一下，查字典次数cnt++，最后输出cnt。
代码：
#include <bits/stdc++.h>
using namespace std;
map<string,int>m;
int main(){
string s;
getline(cin,s);
int n;
cin >> n;
while(n--){
string x;
cin >> x;
m[x]=1;
}
stringstream u(s);
int cnt=0;
while(u>>s){
if(s[0]>='A'&&s[0]<='Z') s[0]=s[0]-'A'+'a'; //首字母转小写
char c=s[s.size()-1];
if(c==','||c=='.'||c=='!'||c=='?') s.pop_back();
//末尾特殊字符去掉
if(m[s]==0) cnt++;
m[s]=1;
}
cout << cnt ;
return 0;
}
ProblemC.排插串联
题目、输入、输出：
样例：
题意：
电路是有根树（共 n + 1 个节点，0 号为插座，功率固定 2200W；叶子节点是电器，其余是插排）。每个插排有功率限制，电器有运行功率。某节点实际功率为其子树所有电器功率之和，超过该节点限制则违规。允许交换任意插排的限制功率（可零次），判断能否通过交换使电路无违规。输入 n 及 n 行（每行 f i 和 a i，若为叶子节点，a i 是电器运行功率；否则是插排原限制功率），无违规输出 “YES” 或 “NO”。
思路：
排插的功率可以排插位置可以互换，贪心出小的排插功率放在需要排插位的小电器功率父节点上。
先用v存每个节点的子节点，再用v1存所有排插节点的功率（v[i].size()!=0即为排插），v1从小到大排序，最后插入插座2200，一开始wa了一发就是因为将2200直接放进去排序了，这样可能将比2200更大的功率放在根节点插座，/(ㄒoㄒ)/~~。
利用树的遍历，返回叶子节点电器的功率，向根节点返回累加，用v2存起每个需要排插位的最小电器功率，最后v2从小到大排序，进行一一比较，如果v1[i]<v2[i]则说明超限，输出“NO”，如果没有则输出“YES”。
模拟样例一（如下图所示）：
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
map<int,int>m;
vector<int>v[N];
vector<int>v1,v2;
int dfs(int x){
if(v[x].size()==0) return m[x];
int res=0;
for(auto i:v[x]){
res+=dfs(i);
}
v2.push_back(res); //存需要排插位的电器功率
return res;
}
signed main(){
int n;
cin >> n;
int f,a;
for(int i=1;i<=n;i++){
cin >> f >> a;
m[i]=a; //存i节点的功率
v[f].push_back(i); //存i的子节点
}
//存排插功率
for(int i=1;i<=n;i++) if(v[i].size()) v1.push_back(m[i]);
sort(v1.begin(),v1.end());
v1.push_back(2200); //最后才插入2200（根）
int d=dfs(0);
sort(v2.begin(),v2.end());
for(int i=0;i<v2.size();i++) {
if(v2[i]>v1[i]){ //超限
cout << "NO";
return 0;
}
}
cout << "YES";
return 0;
}
ProblemL.龙之研习
题目、输入、输出：
样例：
题意：
T组测试数据，每组测试数组输入一个k，代表2024年后的第k个平年（k=1时对应2025，k=2时对应2026），输出第k个平年对应的年份。
思路：
K的大小1到1e18，时间复杂度最多O(lnk)，因为随着年份的增大，平年越多，可以用二分来做，二分出 2024年后的 平年个数少于等于k 的最小年份，平年个数=年份-闰年个数，闰年个数可以利用容斥原理来求：例如年份n=100 , 能整除4的闰年: 4 16...100 对应+n/4的时候会将100加进去，所以要-n/100，不要整除100的年份，二分结束后，最后输出左边界l即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
int sum;
int check(int n,int k){
int a=4,b=100,ans=0; //ans:第1年到n年中闰年个数
while(a<=n||b<=n){
ans+=n/a; //能整除4*100^k
ans-=n/b; //不能整除100^(k+1)
a*=100,b*=100;
//eg:年份n=100 , 能整除4的闰年(a=4): 4 16...100 对应+n/4的时候会将100加进去，所以要-n/100,不要整除100的年份
} //《容斥原理》
int res=n-ans-sum; //res：平年个数
if(n==2024) return res;
else if(res>=k) return 1;
else return 0;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
sum=check(2024,0); //计算2024前的平年个数 sum
int T;
cin >> T;
while(T--){
int k;
cin >> k;
int l=2025,r=9e18; //二分出 (平年个数-sum)>=k 的最早年份
while(l<r){
int mid=l+r>>1;
if(check(mid,k)) r=mid;
else l=mid+1;
}
cout << l <<'\n';
}
return 0;
}
ProblemE.俄式简餐
题目、输入、输出：
样例：
题意：
给出T组测试数据，每组测试数据输入n,m, 表示需要构造的n行m列，构造不出来输出“NO”，否则输出“YES”以及构造矩阵，构造的部分必须是从以下模型中选择，一个整体模型用一个数字表示，要求数字不能跳号：
思路：
上面两个模型需要构造出一个矩阵，构造基础部分为（1，4），（2，6）两个矩阵：
如果这两个基础矩阵构造不出来就输出“NO”；
讨论能构造出来条件：
- 只放（1，4）
如n=1，m=4（竖放n，m互换同理）：
2.（1，4）（2，6）组合放，包括了只放（2，6）的情况：底座两个6是4的倍数，所以底座最多一个6
如n=2，m=10（竖放n，m互换同理）：
为什么：没有一横一竖的组合？
因为这样行是4的倍数，一定可以用只放（1，4）来填满
最后分类讨论上面的情况即可，具体看代码注释。
代码：
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,m;
cin >> n >> m;
vector<vector<int>> v(n+2,vector<int>(m+2,0));
int cnt=1;
//——只放（1，4）——
if(m%4==0){ //列%4==0,全放(1,4)
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
v[i][j]=cnt;
if(j%4==0) cnt++;
}
}
}
else if(n%4==0){ //行%4==0,全放(4,1)
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
v[i][j]=cnt;
if(i%4==0) cnt++;
}
}
}
//——（1，4）（2，6）组合放——
//底座两个6是4的倍数，所以底座最多一个6 ，包括了——只放（2，6）的情况
//去掉6列，剩余列数为4的倍数 ，且行数为2的倍数
else if(m-6>=0&&(m-6)%4==0&&(n%2)==0){
for(int i=1;i<=n;i++){
for(int j=1;j<=6;j++){ //先填n行前6列
if(i%2) {
v[i][j]=cnt;
if(j==3) cnt++;
}
else {
if(j==1||j==6) v[i][j]=v[i-1][j],cnt++;
else v[i][j]=cnt;
}
}
}
for(int i=1;i<=n;i++){ //后填n行剩余列
for(int j=7;j<=m;j++){
v[i][j]=cnt;
if((j-6)%4==0) cnt++;
}
}
}
//去掉6行，剩余行数为4的倍数 ，且列数为2的倍数
else if(n-6>=0&&(n-6)%4==0&&(m%2)==0){
for(int j=1;j<=m;j++){
for(int i=1;i<=6;i++){ //先填m列前6行
if(j%2) {
v[i][j]=cnt;
if(i==3) cnt++;
}
else {
if(i==1||i==6) v[i][j]=v[i][j-1],cnt++;
else v[i][j]=cnt;
}
}
}
for(int j=1;j<=m;j++){ //后填m列剩余行
for(int i=7;i<=n;i++){
v[i][j]=cnt;
if((i-6)%4==0) cnt++;
}
}
}
else {
cout << "NO"<<'\n';
return ;
}
cout << "YES"<<'\n';
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout << v[i][j]<<" ";
cout << '\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--) solve();
return 0;
}
ProblemD.都市叠高
题目、输入、输出：
样例：
题意：
将n个点划分成若干段，使得每段中的最远点对的距离之 和最大，问最大值是多少。
思路：
Dp
设dpi 是以第i 个回合后的最大得分， 转移为dpi = i max j=1 (dpj−1 + dis(pi,pj))，dp0 = 0。 答案为dpn。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5010;
double f[N]; //第 i 回合后的最大得分。
vector<pair<int,int>>v;
signed main(){
int n;
cin >> n;
int a,b;
v.push_back({0,0});
for(int i=1;i<=n;i++) {
cin >> a>>b;
v.push_back({a,b});
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
int x1=v[i].first,y1=v[i].second;
int x2=v[j].first,y2=v[j].second;
int dx=x1-x2,dy=y1-y2;
double d=sqrt(dx*dx+dy*dy); //d: 两坐标间距离
if(f[j-1]+d>f[i]) f[i]=f[j-1]+d; //i和j连，+f[j-1]:j-1回合最大
}
}
printf("%.10lf",f[n]);
return 0;
}
2024湖南省赛补题
2024 CCPC山东邀请赛
更多推荐
48
0- 0
已为社区贡献4条内容
所有评论(0)