2025山东CCPC题解

L - Stella

题目来源：L - Stella

解题思路
签到题，因为给出的字母不是按顺序，可以存起来赋其值，然后在比较。

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e5+5;
void solve()
{map<char,int>mp;mp['O']=1;mp['B']=2;mp['A']=3;mp['F']=4;mp['G']=5;mp['K']=6;mp['M']=7;string s1,s2;cin>>s1>>s2;if(mp[s1[0]]<mp[s2[0]]){cout<<"hotter"<<endl;return ;}else if(mp[s1[0]]>mp[s2[0]]){cout<<"cooler"<<endl;return ;}else{if(s1[1]<s2[1]){cout<<"hotter"<<endl;return ;}else if(s1[1]>s2[1]){cout<<"cooler"<<endl;return ;}else{cout<<"same"<<endl;return ;}}
}
signed main()
{IOS;int _=1;cin>>_;while(_--)solve(); return 0;
} 

D - Distributed System

题目来源：D - Distributed System

解题思路
这道题主要考察个差分的算法，如果不考虑mod n的情况就把数组第i项和第i+n项最后加起来，题目意思是第0到ai-1项每次都会增加1，当然不能遍历着去加，所以就用一个前缀和数组记录改变的情况，最后利用前缀和公式求出即可。
代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
int n,q,ans[N],b[N],k,x,y;
void solve()
{cin>>n>>q;vector<int>a(2*n+10,0);int sum=0;while(q--){cin>>x>>y;sum+=x/n;x%=n;a[y]++;a[y+x]--;}ans[0]=a[0];for(int i=1;i<n*2;i++)ans[i]=ans[i-1]+a[i];for(int i=0;i<n;i++)cout<<ans[i]+ans[i+n]+sum<<" ";cout<<endl;
}
signed main()
{IOS;int _=1;cin>>_;while(_--)solve(); return 0;
} 

I - Square Puzzle

题目来源：I - Square Puzzle

解题思路
这题没有什么规律，读完题后可以知道，一共就7种操作：右移第一行，右移第二行，右移第三行，下移第一列，下移第二列，下移第三列，顺时针旋转90度。因为只是三乘三的九宫格，将所有方式遍历一遍也一定不会超时，所以可以用广搜遍历每一种情况，然后将没种情况是否符合，如果符合看需要多少步，最终取最小，如果没有符合输出-1.

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
map<string,int>ans;
queue<string>q;
string youyi(string a,int op)//右移函数 
{if(op==1){char t=a[0];a[0]=a[2],a[2]=a[1],a[1]=t;return a;}if(op==2){char t=a[3];a[3]=a[5],a[5]=a[4],a[4]=t;return a;}if(op==3){char t=a[6];a[6]=a[8],a[8]=a[7],a[7]=t;return a;}
}
string xiayi(string a,int op)//下移函数 
{if(op==1){char t=a[0];a[0]=a[6],a[6]=a[3],a[3]=t;return a;} if(op==2){char t=a[1];a[1]=a[7],a[7]=a[4],a[4]=t;return a;}if(op==3){char t=a[2];a[2]=a[8],a[8]=a[5],a[5]=t;return a;}
} 
string xuanzhuan(string a)//顺时针旋转函数 
{char t=a[0];a[0]=a[6],a[6]=a[8],a[8]=a[2],a[2]=t;t=a[1];a[1]=a[3],a[3]=a[7],a[7]=a[5],a[5]=t;return a;
}
void bfs()
{q.push("123456789");ans["123456789"]=0;while(q.size()){string g=q.front();q.pop();string t;t=youyi(g,1);if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;t=youyi(g,2);if(ans[t]==0 )q.push(t),ans[t]=ans[g]+1;t=youyi(g,3);if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;t=xiayi(g,1);if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;t=xiayi(g,2);if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;t=xiayi(g,3);if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;t=xuanzhuan(g);if(ans[t]==0) q.push(t),ans[t]=ans[g]+1; }
}
void solve()
{string s;map<char,char>mp;for(int i=1;i<=9;i++){char ch;cin>>ch;mp[ch]='0'+i;}for(int i=1;i<=9;i++){char ch;cin>>ch;s+=mp[ch];}if(s=="123456789")cout<<"0"<<endl;else if(ans[s]==0)cout<<-1<<endl;else cout<<ans[s]<<endl;
}
signed main()
{IOS;bfs(); int _=1;cin>>_;while(_--)solve(); return 0;
} 

E - Greatest Common Divisor

题目来源：E - Greatest Common Divisor

解题思路
首先，答案一定是s=
∑ai+k的因数。因此对s因数分解，然后在因数中枚举答案x。
为了让答案为x，需要把每个ai增加到最近的x的倍数，剩下的操作次数还需要被x整除。如果x≤maxai，那么每x种数都要增加到同一个数，可以
一起计算。这种情况的复杂度为调和级数O(maxai logmaxai)。
如果x>maxai，那么所有数都增加到同一个数，直接O(1)计算。
整体复杂度O(n+√s+f(s)+maxai logmaxai)，其中
f(s)≈6×103是因数个数。
代码实现

G - Assembly Line

题目来源：G - Assembly Line

解题思路
题目意思是k名工人加工n个工件，第i个工件在第ti分钟加入工人wi的收件箱，每分钟工人在自己的收件箱拿出一个工件，完成加工后放入下
一个工人的收件箱（如果是最后一个工人则加工完成）。问
所有工件加工完成需要几分钟
工件i原本的结束时间是(ti+k−wi)，但每个时间点只能完成一个工件。
因此设ai表示从小到大排序后的工件完成时间，依次进行
更新ai←max(ai,ai−1+1)即可。复杂度O(nlogn)。
代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
int n,k,w,t,a[N];void solve()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>w>>t;a[i]=k-w+t;}sort(a+1,a+1+n);for(int i=1;i<=n;i++)a[i]=max(a[i],a[i-1]+1);cout<<a[n]<<endl;}
signed main()
{IOS;int _=1;cin>>_;while(_--)solve(); return 0;
}