2025山东CCPC题解

L - Stella

题目泉源：L - Stella

解题思路
签到题，因为给出的字母不是按次序，可以存起来赋其值，然后在比力。
代码实现

1. #include<bits/stdc++.h>
2. #define int long long
3. #define endl '\n'
4. #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
5. using namespace std;
6. const int N=1e5+5;
7. void solve()
8. {
9.         map<char,int>mp;
10.         mp['O']=1;
11.         mp['B']=2;
12.         mp['A']=3;
13.         mp['F']=4;
14.         mp['G']=5;
15.         mp['K']=6;
16.         mp['M']=7;
17.         string s1,s2;
18.         cin>>s1>>s2;
19.         if(mp[s1[0]]<mp[s2[0]])
20.         {
21.                 cout<<"hotter"<<endl;
22.                 return ;
23.         }
24.         else if(mp[s1[0]]>mp[s2[0]])
25.         {
26.                 cout<<"cooler"<<endl;
27.                 return ;
28.         }
29.         else
30.         {
31.                 if(s1[1]<s2[1])
32.                 {
33.                         cout<<"hotter"<<endl;
34.                         return ;
35.                 }
36.                 else if(s1[1]>s2[1])
37.                 {
38.                         cout<<"cooler"<<endl;
39.                     return ;
40.                 }
41.                 else
42.                 {
43.                         cout<<"same"<<endl;
44.                         return ;
45.                 }
46.         }
47. }
48. signed main()
49. {
50.         IOS;
51.         int _=1;
52.         cin>>_;
53.         while(_--)solve();
54.         return 0;
55. }

复制代码

D - Distributed System

题目泉源：D - Distributed System

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

1. #include<bits/stdc++.h>
2. #define int long long
3. #define endl '\n'
4. #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
5. using namespace std;
6. const int N=1e6+5;
7. int n,q,ans[N],b[N],k,x,y;
8. void solve()
9. {
10.         cin>>n>>q;
11.         vector<int>a(2*n+10,0);
12.         int sum=0;
13.         while(q--)
14.         {
15.                 cin>>x>>y;
16.                 sum+=x/n;
17.                 x%=n;
18.                 a[y]++;
19.                 a[y+x]--;
20.         }
21.         ans[0]=a[0];
22.         for(int i=1;i<n*2;i++)
23.                 ans[i]=ans[i-1]+a[i];
24.         for(int i=0;i<n;i++)
25.                 cout<<ans[i]+ans[i+n]+sum<<" ";
26.         cout<<endl;
27. }
28. signed main()
29. {
30.         IOS;
31.         int _=1;
32.         cin>>_;
33.         while(_--)solve();
34.         return 0;
35. }

复制代码

I - Square Puzzle

题目泉源：I - Square Puzzle

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

1. #include<bits/stdc++.h>
2. #define int long long
3. #define endl '\n'
4. #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
5. using namespace std;
6. const int N=1e6+5;
7. map<string,int>ans;
8. queue<string>q;
9. string youyi(string a,int op)//右移函数
10. {
11.         if(op==1)
12.         {
13.                 char t=a[0];
14.                 a[0]=a[2],a[2]=a[1],a[1]=t;
15.                 return a;
16.         }
17.         if(op==2)
18.         {
19.                 char t=a[3];
20.                 a[3]=a[5],a[5]=a[4],a[4]=t;
21.                 return a;
22.         }
23.         if(op==3)
24.         {
25.                 char t=a[6];
26.                 a[6]=a[8],a[8]=a[7],a[7]=t;
27.                 return a;
28.         }
29. }
30. string xiayi(string a,int op)//下移函数
31. {
32.         if(op==1)
33.         {
34.                 char t=a[0];
35.                 a[0]=a[6],a[6]=a[3],a[3]=t;
36.                 return a;
37.          }
38.          if(op==2)
39.          {
40.                  char t=a[1];
41.                  a[1]=a[7],a[7]=a[4],a[4]=t;
42.                  return a;
43.          }
44.          if(op==3)
45.          {
46.                  char t=a[2];
47.                  a[2]=a[8],a[8]=a[5],a[5]=t;
48.                  return a;
49.          }
50. }
51. string xuanzhuan(string a)//顺时针旋转函数
52. {
53.         char t=a[0];
54.         a[0]=a[6],a[6]=a[8],a[8]=a[2],a[2]=t;
55.         t=a[1];
56.         a[1]=a[3],a[3]=a[7],a[7]=a[5],a[5]=t;
57.         return a;
58. }
59. void bfs()
60. {
61.         q.push("123456789");
62.         ans["123456789"]=0;
63.         while(q.size())
64.         {
65.                 string g=q.front();
66.                 q.pop();
67.                 string t;
68.                 t=youyi(g,1);
69.                 if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
70.                 t=youyi(g,2);
71.                 if(ans[t]==0 )q.push(t),ans[t]=ans[g]+1;
72.                 t=youyi(g,3);
73.                 if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
74.                 t=xiayi(g,1);
75.                 if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
76.                 t=xiayi(g,2);
77.                 if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
78.                 t=xiayi(g,3);
79.                 if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
80.                 t=xuanzhuan(g);
81.                 if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
82.         }
83. }
84. void solve()
85. {
86.     string s;
87.     map<char,char>mp;
88.     for(int i=1;i<=9;i++)
89.     {
90.             char ch;
91.             cin>>ch;
92.             mp[ch]='0'+i;
93.         }
94.         for(int i=1;i<=9;i++)
95.         {
96.                 char ch;
97.                 cin>>ch;
98.                 s+=mp[ch];
99.         }
100.         if(s=="123456789")cout<<"0"<<endl;
101.         else if(ans[s]==0)cout<<-1<<endl;
102.         else cout<<ans[s]<<endl;
103. }
104. signed main()
105. {
106.         IOS;
107.         bfs();
108.         int _=1;
109.         cin>>_;
110.         while(_--)solve();
111.         return 0;
112. }

复制代码

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)。
代码实现

1. #include<bits/stdc++.h>
2. #define int long long
3. #define endl '\n'
4. #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
5. using namespace std;
6. const int N=1e6+5;
7. int n,k,w,t,a[N];
9. void solve()
10. {
11.    cin>>n>>k;
12.    for(int i=1;i<=n;i++)
13.    {
14.            cin>>w>>t;
15.            a[i]=k-w+t;
16.    }
17.    sort(a+1,a+1+n);
18.    for(int i=1;i<=n;i++)
19.    a[i]=max(a[i],a[i-1]+1);
20.    cout<<a[n]<<endl;
21.        
22. }
23. signed main()
24. {
25.         IOS;
26.         int _=1;
27.         cin>>_;
28.         while(_--)solve();
29.         return 0;
30. }

复制代码