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;
}