2020年牛客多校第三場

補題過程：

F題：

首先我們如果a和b不互質，那麼 d = f = b / g c d ( a , b ) d=f=b/gcd(a,b) d=f=b/gcd(a,b)， c − e = a / g c d ( a , b ) c-e=a/gcd(a,b) c−e=a/gcd(a,b)，是以直接令 c = g c d ( a , b ) + 1 c=gcd(a,b)+1 c=gcd(a,b)+1, e = g c d ( a , b ) e=gcd(a,b) e=gcd(a,b)就行了。

然後如果我們講左邊式子通分可以知道d，f是b的質因子，并且 d ∗ f = b d*f=b d∗f=b證明如下：

如果 d ∗ f = k ∗ b d*f=k*b d∗f=k∗b，那麼 c f − e d = k ∗ a cf-ed=k*a cf−ed=k∗a是以約分後不變。其次 c f − e d = a cf-ed=a cf−ed=a有解的條件是 a 模 g c d ( d , f ) a模gcd(d,f) a模gcd(d,f)等于0，是以 g c d ( d , f ) gcd(d,f) gcd(d,f)隻能等于1，不然等價 g c d ( d , f ) ∣ a 且 g c d ( d , f ) ∣ b gcd(d,f)|a且gcd(d,f)|b gcd(d,f)∣a且gcd(d,f)∣b這樣的話和之前a,b互質相悖。是以d和f互質。

是以我們分子直接用exgcd就可以求出來。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6 + 5;
bool notprime[maxn]; int pri[maxn],tot,cnt[maxn],num[maxn],cnt1;
void get(){
    for(int i=2;i<=2e6;i++){
        if(!notprime[i]) pri[++tot]=i;
        for(int j=1;j<=tot && i*pri[j]<=2e6;j++){
            notprime[i*pri[j]]=true;
            if(i%pri[j]==0) break;
        }
    }
}
int exgcd(int a,int b,int &x,int &y){
    if(b==0){ x=1; y=0; return a; }
    int r = exgcd(b,a%b,x,y);
    int t = x;
    x = y;
    y = t - a/b * y;
    return r;
}
signed main(){
    get();
    int t; scanf("%lld",&t);
    while(t--){
        int a,b; scanf("%lld%lld",&a,&b);
        int gcd=__gcd(a,b);
        if(gcd!=1){
            a/=gcd,b/=gcd;
            cout<<a+1<<' '<<b<<' '<<1<<' '<<b<<endl;
        }
        else{
            if(!notprime[b]){
                printf("-1 -1 -1 -1\n");
                continue;
            }
            int c,d,e,f,ok=0;
            for(int i=2;i<=sqrt(b);i++){
                if(b%i==0&&__gcd(i,b/i)==1){
                    d=i,f=b/i;
                    int r=exgcd(d,f,e,c);
                    if(c<0){
                        c=-c;
                    }else if(e<0){
                        e=-e;
                        swap(d,f);
                        swap(e,c);
                    }
                    ok=1;
                    printf("%lld %lld %lld %lld\n",c*a,d,e*a,f);
                    break;
                }
            }
            if(!ok) printf("-1 -1 -1 -1\n");
        }
    }
}

           

G題：

開始是n個連通塊，然後我們q次詢問，每次詢問就把和這個連通塊相連接配接的所有連通塊都合并到目前詢問連通塊上面。合并的時候用啟發式合并就好了。

#include <bits/stdc++.h>
using namespace std;
const int N=8e5+10;
int pre[N],n,m;
vector<int> g[N];
int find(int x)
{
    if(x==pre[x]) return x;
    return pre[x]=find(pre[x]);
}
void merge(vector<int> &x,vector<int> &y)
{
    if(x.size()>y.size()) swap(x,y);
    for(auto it:x) y.push_back(it);
}
void work(int x)
{
    if(find(x)!=x) return ;
    vector<int> tmp=g[x]; 
    for(auto it:tmp){
        if(find(it)!=find(x)){
            merge(g[find(it)],g[find(x)]);
            pre[find(it)]=find(x);
        }
    }
}
signed main()
{
    int t; scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++) g[i].clear();
        for(int i=0;i<n;i++) pre[i]=i;
        for(int i=1;i<=m;i++){
            int a,b; scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        int q; scanf("%d",&q);
        while(q--){
            int x; scanf("%d",&x);
            work(x);
        }
        for(int i=0;i<n;i++) printf("%d ",find(i));
        puts("");
    }
}
           

D

題解：

首先我們分析一下無解的情況：

我們一個黑點的最大貢獻是4，是以如果n4<m則是無解的。

然後再看看下屆，我們知道如果我們黑點靠近的越多，貢獻越小，是以我們假設所有黑點聚內建一個長為x，寬為y的矩形，那麼當n定下來的時候這個時候點對是最小的為(x+y)2，而如果沒有填滿矩形如圖

那麼他的效果和一個填滿這個矩形的效果是一樣的。是以我們可以知道m需要大于等于2(x+y),且此時ab必須大于n（矩陣内黑點的最大數量），又均值不等式可以知道2(x+y)>=4sqrt(xy)，當且僅當x=y的時候取最小。是以m>=4sqrt(xy)>=4sqrt(n)，是以 m 2 > = 16 ∗ n m^2>=16*n m2>=16∗n。是以上下界都找到了。然後就是兩種情況填充。

當我們m>2n+2的時候我們先填充成一條鍊，然後補x個貢獻為4的點。

當m<=2n+2的時候我們就按照矩形填充就行了。

#include <bits/stdc++.h>
using namespace std;
int n,m;
signed main()
{
    int t; scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        if(m%2!=0||m>4*n||m*m<16*n) puts("No");
        else{
            puts("Yes");
            if(m>2*n+2){
                int x=(m-2*n-2)/2,y=n-x;
                for(int i=1;i<=x;i++) printf("%d %d\n",i,i);
                for(int i=5;i<=y+5;i++) printf("1 %d\n",i);
            }else{
                int x=m/4,y=m/2-x;
                for(int i=1;i<=x;i++) printf("%d 1\n",i);
                for(int j=2;j<=y;j++) printf("1 %d\n",j);
                int rest=n-(x+y-1);
                for(int i=2;i<=x&&rest>0;i++)
                    for(int j=2;j<=y&&rest>0;j++,rest--)
                        printf("%d %d\n",i,j);
            }
        }
    }
}
           

E

題解：

這裡1，2，3，4…排列均為第幾小的數。

首先我們知道最小值就是構造出1,2,3,4,5,6…2n這樣的序列，他們兩兩之間的差之和最小值最小。

然後我們構造次小值。因為是絕對值，其實就是兩個數之間的舉例。我們以長度為4的鍊為例，我們以3，4為右端點，(因為12,34比對過了，并且pi!=qi是以比對過的不能在比對)。是以可以有兩種比對方法，一個是14,23或者13,24。在數軸上面畫一下，發現兩種方案的和是一樣的。然後觀察6為長度的鍊，同理比對過的不能在比對，是以我們枚舉右端點，因為右端點越小代價越小，是以我們6肯定要選，因為沒有比他大的數了。然後5也必須選，因為除了6沒有比5更大的數了而56已經比對過一次了。剩下就看3,4明顯選3為右端點的話更優(更靠左)是以右端點就是3,5,6。然後其他長度的鍊都可以用這兩個長度解決了。

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,a[N],dp[N],res;
inline void solve(){
    cin>>n; res=0;
    for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
    sort(a+1,a+1+n); for(int i=1;i<=n;i++)dp[i]=1e18; dp[0]=0;
    for(int i=2;i<=n;i+=2)	res+=a[i]-a[i-1];
    for(int i=4;i<=n;i++){
        dp[i]=dp[i-4]+a[i]+a[i-1]-a[i-2]-a[i-3];
        if(i>=6)	dp[i]=min(dp[i],dp[i-6]+a[i]+a[i-1]+a[i-3]-a[i-2]-a[i-4]-a[i-5]);
    }
    printf("%lld\n",res+dp[n]);
}
signed main(){
    int T; cin>>T; while(T--) solve();
    return 0;
}