A. Circle Coloring

簽到，abc三個陣列找到一個符合要求的就行了

#include <bits/stdc++.h>
using namespace std;
int a[105],b[105],c[105];
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        for(int i=1;i<=n;i++)cin>>c[i];
        int last=a[1];
        cout<<last<<' ';
        for(int i=2;i<=n-1;i++){
            if(a[i]!=last)cout<<a[i]<<' ',last=a[i];
            else if(b[i]!=last)cout<<b[i]<<' ',last=b[i];
            else if(c[i]!=last)cout<<c[i]<<' ',last=c[i];
        }
        if(a[n]!=a[1]&&a[n]!=last)cout<<a[n];
        else if(b[n]!=a[1]&&b[n]!=last)cout<<b[n];
        else if(c[n]!=a[1]&&c[n]!=last)cout<<c[n];
        cout<<endl;
    }
}

B. Arrays Sum

想了挺久的B
發現一個b能夠消掉不同的k-1個數位（另一個為0）
不過要記得特判一下$cnt=1$的情況以及保證$ans>=1$

#include <bits/stdc++.h>
using namespace std;
int a[105];
int main(){
    int t;cin>>t;
    while(t--){
        int n,k;cin>>n>>k;
        set<int>q;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            q.insert(a[i]);
        }
        int cnt=q.size();//統計有幾個不同的數位
        if(k==1){
            if(cnt==1)cout<<1<<endl;
            else cout<<-1<<endl;
            continue;
        }
        int ans;
        if((cnt-1)%(k-1)==0)ans=(cnt-1)/(k-1);
        else ans=(cnt-1)/(k-1)+1;
        cout<<max(1,ans)<<endl;//這裡大概是賽後fst的點？
    }
}

C. Discrete Acceleration

就模擬，也發現有二分時間的做法
由於比賽時變數定義太混亂，就不上程式碼了

D. Searchlights

看錯了n和m的資料範圍，還以為是1e6的，在想怎麼用O($nlogn$)做，實際上最大隻有2000
根據題意，強盜必須在x和y至少一個方面大於探照燈which means 如果$x<=c_j-a_i$，那麼$y>=d_j-b_i+1$
因為上界不大，因此我們用f陣列的下標存每個x的位置，讓其等於y的最小值，即$f_{(}{c}_j-a_i)=max(f_{(}{c}_j-a_i),d_j-b_i+1)$，所以用O($nm$)處理
最後f陣列記錄字尾的最大值，然後加上向右需要移動的距離求個最小值
為什麼是求字尾的最大值呢，比如對於$1<x<C$，1到x-1的這段只需要向右移動x就行，x到C的這段需要向上移動，向上移動的距離就是x到C每個點需要移動的最大值，所以是記錄字尾的最大值
時間複雜度$O(nm+C)$

#include <bits/stdc++.h>
using namespace std;
int a[2005],b[2005],c[2005],d[2005],f[2000005];
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    for(int i=1;i<=m;i++)cin>>c[i]>>d[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]<=c[j]){
                f[c[j]-a[i]]=max(f[c[j]-a[i]],d[j]-b[i]+1);
            }
        }
    }
    int ans=2000000+2;
    int maxs=0;
    for(int i=1000001;i>=0;i--){
        maxs=max(maxs,f[i]);
        ans=min(ans,i+maxs);
    }
    cout<<ans<<endl;
}

再給一個二分的做法

#include <bits/stdc++.h>
using namespace std;
int a[2005],b[2005],c[2005],d[2005],f[2000005];
int n,m;
bool check(int mid){
    for(int i=0;i<=mid;i++)f[i]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int sum=c[j]+d[j]-a[i]-b[i]-mid;
            if(a[i]<=c[j]&&b[i]<=d[j]&&sum>=0){
                f[max(0,c[j]-a[i]-sum)]++;
                f[c[j]-a[i]+1]--;
            }
        }
    }
    for(int i=1;i<=mid;i++)f[i]+=f[i-1];
    for(int i=0;i<=mid;i++)if(f[i]==0)return 1;
    return 0;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    for(int i=1;i<=m;i++)cin>>c[i]>>d[i];
    int l=0,r=2e6,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<endl;
}

剩餘待補題完寫