Codeforces Round 892 (Div. 2)

A. United We Stand

簡述題意

給定一個長度為 $ n $ 的數列 $ a $ ，要求將 $ a $ 的每個元素分配到數列 $ b $ ,$ c $ 中，滿足以下兩個要求

1. $ b,c $ 不為空，即 $ l_b \geq 1 , l_c \geq 1 $ 。
2. 對于任意 $ i $ 和 $ j $ $ (1\leq i \leq l_b ,1\leq j \leq l_c) $ ，$ c_j $ 不為 $ b_i $ 的約數 。

如果有分配方案滿足兩個條件，第一行輸出$ l_b,l_c $ 接下來兩行分別輸出數列$ b,c $ 。
如果沒有分配方案滿足兩個條件則輸出-1。

共有 $ T $ 組數據，$ T\leq500 $ ，$ 2 \leq n \leq 100 $ ，$ 1 \leq a_i \leq 10^9 $

思路

首先，對于 $ \forall x,y(x>y) $ , $ x $ 一定不為 $ y $ 的約數，基于這個事實，可以考慮將 $ a $ 中的所有最大值放進 $ b $ 中，其余的放進 $ a $ 中，這樣便能滿足條件2；但是有一種特殊情況便是 $ a $ 中只由一個數字組成，如果仍然依照上面的思路將所有最大值放進數組 $ b $ 中，就會導致 $ a $ 為空，如果在 $ a,b $ 皆不為空的情況下無論如何分配 $ a $ 中的元素均不能滿足條件1，所以遇見這種特殊情況的時候直接輸出-1 。

代碼實現

沒什么需要注意的，排序之后特判一下特殊情況，從后面往前面找到第一次出現最大值的位置 $ x $ , $ l_b $ 就為 $ x-1 $ ，$ l_c $ 則為 $ n-x+1 $ ，然后直接輸出 $ b,c $ 即可。

代碼如下：

#include<bits/stdc++.h>
using namespace std;
const unsigned int N=105;
int n,a[N];
inline int r(){
    int x=0,y=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')
        y=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
bool cmp(int x,int y){
    return x<y;
}
void solve(){
    n=r();
    for(register int i=1;i<=n;i++)
    a[i]=r();
    sort(a+1,a+n+1,cmp);
    if(a[n]==a[1]){
        puts("-1");
        return;
    }
    int x=n;
    for(register int i=n;i>1;i--){
        if(a[i-1]==a[i]){
            x=i-1;
            continue;
        }
        break;
    }
    printf("%d ",x-1);
    printf("%d\n",n-x+1);
    for(register int i=1;i<=x-1;i++)
    printf("%d ",a[i]);
    printf("\n");
    for(register int i=x;i<=n;i++)
    printf("%d ",a[i]);
    printf("\n");
}
signed main(){
    int T=r();
    while(T--)
    solve();
}

B. Olya and Game with Arrays

簡述題意

這里有 $ n $ 個數列，第 $ i $ 個數列包含 $ m_i $ 個正整數 。

現在你可以在每個數列中挑出至多一個元素移動至另外一個數列（當然也可以不移動），一個數列中可以接受多個元素加入進來，但是一個數列中只有一個元素可以被挑出移動至其他數列，所有操作在同一時刻完成 。

美麗值的定義是每個數列中的最小值之和，即 $ \sum_{i=1}^{n} min_{j=1}^{m_i}a_{i,j} $ 。

現在求通過操作后，這 $ n $ 個數列最大的美麗值 。

共有 $ T $ 組數據 ， $ 1 \leq T \leq 25000 $ ，$ 1 \leq n \leq 25000 $ ，$ 2 \leq m \leq 50000 $ ，$ 1 \leq a_{i,j} \leq 10^9 $ 。

思路

我們先思考一下一個數列如何移動能讓這次移動對答案的貢獻最大，肯定是將數列中的最小值移出去，若第 $ i $ 個數列中的最小值為 $ x_i $，次小值為 $ y_i $ 那么將這個數列中的最小值移出去對答案的貢獻是 $ y_i-x_i $ ，為了讓答案盡可能的大，我們先假設每個數列都將它的次小值移出去，當前的答案是 $ \sum_{i=1}^{n}y_i $ ，但是必須要找到一個數列來接受這些被移出的最小值，我們發現，若第 $ i $ 個數列接受了這些最小值，答案將會減去 $ y_i - min_{i=1}^{n} x_i $ ，為了讓答案最大，所以我們需要讓 $ y_i $ 最小，所以最終的答案就是 $ \sum_{i=1}^{n}y_i -min_{j=1}^{n} y_j+min_{k=1}^{n}x_k $ 。

代碼實現

由于影響答案的只有每個數列的最小值和次小值，所以在讀入的時候記錄每一個數列的最小值和次小值，在記錄每個數列最小值的最小值和每個數列次小值的最小值 即可 ，注意多測清空，開long long 。

代碼如下

#include<bits/stdc++.h>
#define int long long
#define INF (int)1e9+15
using namespace std;
const unsigned int N=25005;
int n,m,mxa[N],mxb[N];//mxa記錄每個數列的最小值,mxb記錄每個數列的次小值
inline int r(){
    int x=0,y=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')
        y=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
void solve(){
    int ans=0,mm=INF;//mm記錄所有數列中的最小值
    n=r();
    for(register int i=1;i<=n;i++){
        m=r();
        mxa[i]=mxb[i]=INF;
        for(register int j=1;j<=m;j++){
            int x=r();
            mm=min(mm,x);
            if(x<mxa[i]){
                mxb[i]=mxa[i];
                mxa[i]=x;
                continue;
            }
            mxb[i]=min(x,mxb[i]);
        }
    }
    for(register int i=1;i<=n;i++){
        int tmp=mm;
        for(register int j=1;j<=n;j++){
            if(i==j)
            continue;
            //printf("tmp=%d\n",tmp);
            tmp+=mxb[j];
        }
        ans=max(ans,tmp);
    }
    printf("%lld\n",ans);
    return;
}
signed main(){
    int T=r();
    while(T--)
    solve();
}

C.Another Permutation Problem

題意簡述

給出一個 $ n $ ，你可以任意改變長度為 $ n $ 的排列中的元素位置使得這個排列的價值最大 。

長度為 $ n $ 排列的定義是 $ \forall i \in [1,n] $ ， $ p_i \in [1,n] $ 且排列中沒有重復出現的元素 。

排列 $ p $ 的價值的定義為 : 排列中的每一個元素的大小乘上它在排列中的位置減去排列中一個數乘上他所在的位置的最大值，即 $ (\sum_{i=1}^{n} p_i \cdot i)-(max_{j=1}^{n}p_j \cdot j) $ 。

求改變排列中元素的順序后排列的最大值 。

共有 $ T $ 組數據 ，$ 1 \leq T \leq 30 $ , $ 2 \leq n \leq 250 $ , 保證每組數據 $ n $ 的總和不超過 $ 500 $ 。

思路

第一眼看見這道題沒有任何思路，看樣例感覺像是反轉一下 $ p_n $ 和 $ p_{n-1} $ 的位置，但是通過暴力求全排列算出的答案發現 $ n=5 $ 時并不符合這個規律，在通過暴力求全排列求 $ n $ 更大時候的方案符合 $ p $ 為 $
1,2,3,...,x,n,n-1,n-2,...,x+2,x+1 $

觀察 $ n $ 的大小，我們可以枚舉 $ x $ 的位置，每次枚舉后算出當前方案下排列的價值，取最大值輸出即可，時間復雜度 $ O(n^2) $ 。

代碼

注意多測清空

#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
const unsigned int N=255;
int n,sol[N],tmp[N],ans,t_max=-INF;
bool vis[N];
inline int r(){
	int x=0,y=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')
		y=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*y;
}
int get_sol(int x){//算出當前方案下排列的價值
	int res=0;
	t_max=-INF;
	for(register int i=1;i<=x;i++){
		res+=i*i;
		t_max=max(t_max,i*i);
	}
	for(register int i=x+1;i<=n;i++){
		res+=(n-(i-(x+1)))*i;
		t_max=max(t_max,(n-(i-(x+1)))*i);
	}
	res-=t_max;
	return res;
}
void solve(){
	n=r();
	ans=0;
	for(register int i=0;i<=n;i++)
	ans=max(get_sol(i),ans);
	printf("%d\n",ans);
	return;
}
signed main(){
	int T=r();
	while(T--)
	solve();
}