2024 山东省ccpc省赛

目录

I（签到）

题目简述：

思路：

代码：

A（二分答案）

题目简述：

思路：

代码：

K（构造）

题目：

思路：

代码：

 F（后缀和+排序）

题目：

思路：

代码：

---

https://codeforces.com/gym/105385

I（签到）

题目简述：

判断一个字符串首位字符是否相同，如果初试状态不相同，是否可以经过整体左移后使其相同，如果相同输出左移次数，否则输出-1；

思路：

整体左移的操作是牵一发而动全身的，所以只有有俩相同且相邻字符时才可以通过左移操作使其符合条件

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long ll;
#define endl "\n"
#define PII pair<int,int>
//#define x first
//#define y second
//priority_queue<int, vector<int>, greater<int>> pq;//小根堆
//{并查集
//int fa[N];
//int n;
//void init(){
//	for(int i=0;i<=n;i++)fa[i]=i;
//}初始化
//int get(int x){
//	return fa[x]=(fa[x]==x?x:get(fa[x]));
//}查找
//void merge(int a,int b){
//	fa[get(a)]=get(b);
//}合并
//}
const int N=2e5+10;
void solve(){string s;cin >> s;if(s[0]==s[s.size()-1]){cout << 0 << endl;return ;}
特判一开始就符合条件的情况for(int i=0;i<s.size()-1;i++){if(s[i]==s[i+1]){cout << i+1 << endl;return ;}}cout <<-1 << endl;	
}	 
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q;cin >> q;while(q--)solve();
}

A（二分答案）

题目简述：

使用n台打印机同时打印k份试题，每台打印机都是周期性工作，第i台打印机，每ti秒打印一份，每打印li份就要休息wi秒，问打印完所需要的最短时间；

思路：

很明显是一个二分答案，且是最大值最小类型（时间越多越能完成打印任务，xxx√√√，找第一个对号，最大值当中符合条件的最小值）

确定完二分后就要写check函数，我们二分时间，然后找当前时间内所有打印机能打印的最大份数，如果份数>k返回1，否则返回0

那么如何确定最大份数呢？我们可以把每一周期看做每一段，根据时间可以算得有多少段，有多少段就有多少个li

因为不一定是完整周期，所以我们还要考虑，最后一段不完整的区间，用剩下的时间除以ti，但是需要注意这个结果可能会越界到wi时间里，也就是说剩下的时间除以ti的值最大只能是li

这个二分还要注意一下边界，右边界需要设置大一点；

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long ll;
#define endl "\n"
#define PII pair<int,int>
//#define x first
//#define y second
//priority_queue<int, vector<int>, greater<int>> pq;//小根堆
//{并查集
//int fa[N];
//int n;
//void init(){
//	for(int i=0;i<=n;i++)fa[i]=i;
//}初始化
//int get(int x){
//	return fa[x]=(fa[x]==x?x:get(fa[x]));
//}查找
//void merge(int a,int b){
//	fa[get(a)]=get(b);
//}合并
//}
const int N=2e5+10;
int t[N],l[N],w[N];int n,k;
bool check(int x)
{int num=0;int p=x;for(int i=1;i<=n;i++){p=x;
//		if(p/t[i]<=l[i]){
//			num+=p/t[i];
//			continue;
//		}int q=t[i]*l[i]+w[i];num+=p/q*l[i];p-=p/q*q;if(p/t[i]<=l[i])num+=p/t[i];else num+=l[i];if(num>=k)return 1;}return 0;
}
void solve(){cin>> n >>k;for(int i=1;i<=n;i++){cin >> t[i] >> l[i] >> w[i] ;}	int l=1,r=2e18;while(l+1!=r){int mid=l+r>>1;if(check(mid))r=mid;else l=mid;}cout << r << endl;
}	 
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q;cin >> q;while(q--)solve();
}

K（构造）

题目：

注意是不同行相同列

思路：

上面n-2行设置成i，然后最后两行前面n-2个数是从n-1—2*n-4

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long ll;
#define endl "\n"
#define PII pair<int,int>
//#define x first
//#define y second
//priority_queue<int, vector<int>, greater<int>> pq;//小根堆
//{并查集
//int fa[N];
//int n;
//void init(){
//	for(int i=0;i<=n;i++)fa[i]=i;
//}初始化
//int get(int x){
//	return fa[x]=(fa[x]==x?x:get(fa[x]));
//}查找
//void merge(int a,int b){
//	fa[get(a)]=get(b);
//}合并
//}
const int N=2e5+10;
void solve(){int n;cin >>n;cout << "Yes" <<endl;if(n>3){int a=2*n-3,b=2*n-2,c=2*n-1,d=2*n;
最后四个数单独揪出来for(int i=1;i<=n-2;i++){for(int j=1;j<=n;j++){cout << i << ' ' ;}cout << endl;;}
前n-2行都为iint js=0;for(int i=1;i<=2;i++){for(int j=n-1;j<n-1+n;j++){js++;if(js==n-1)cout << a << ' ';else if(js==n)cout << b << ' ';else if(js==2*n-1)cout << c << ' ';else if(js==2*n)cout << d << ' ';else cout << j <<' ';}cout << endl;}}if(n==2){cout << 1 << ' ' <<2 << endl;cout << 3 << ' ' << 4 << endl;}if(n==3){cout << 3 << ' ' << 2 << ' ' << 6 << endl;cout << 4 << ' ' << 3 << ' ' << 3 << endl;cout << 3 << ' ' << 1 << ' ' << 5 << endl;}
}	 
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q=1;
//	cin >> q;while(q--)solve();
}

 F（后缀和+排序）

题目：

思路：

1. 前缀和逆序处理：从后往前计算数组 a 的前缀和，将原数组转化为后缀和数组形式，a[i] 变为从 i 到 n 的元素和 。
2. 排序：对 a[2] 到 a[n] 排序，此时数组从大到小排列（a[1] 是原数组所有元素和，单独处理 ）。
3. 输出结果：
   • 先输出 a[1]，这是 k = 1 时的结果 。
   • 然后依次累加并输出后续元素，每次累加对应增加一段，实现对不同 k 值结果的计算与输出 

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long ll;
#define endl "\n"
#define PII pair<int,int>
//#define x first
//#define y second
//priority_queue<int, vector<int>, greater<int>> pq;//小根堆
//{并查集
//int fa[N];
//int n;
//void init(){
//	for(int i=0;i<=n;i++)fa[i]=i;
//}初始化
//int get(int x){
//	return fa[x]=(fa[x]==x?x:get(fa[x]));
//}查找
//void merge(int a,int b){
//	fa[get(a)]=get(b);
//}合并
//}
const int N=5e5+10;
int a[N];
void solve(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=n-1;i>=1;i--)a[i]+=a[i+1];sort(a+2,a+n+1);int sum=a[1];cout<<sum<<" ";for(int i=n;i>=2;i--) {sum+=a[i];cout<<sum<<" ";}cout<<endl;
}	 
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q=1;cin >> q;while(q--)solve();
}