A. Showstopper

对于两个序列 $a_1,a_2,\cdots ,a_{n}a\_1,\backslash ,a\_2,\backslash ,\backslash cdots,\backslash ,a\_n$ 和 $b_1,b_2,\cdots ,b_{n}b\_1,\backslash ,b\_2,\backslash ,\backslash cdots,\backslash ,b\_n$，可以进行任意次操作，每次操作可以将 $a_i,b_i(1⩽i⩽n)a\_i,\backslash ,b\_i\backslash ;(1\backslash leqslant\; i\; \backslash leqslant\; n)$ 进行互换.

问在进行任意次操作后，是否能够满足：

• $a_n=\max (a_1,a_2,\cdots ,a_n)a\_n=\backslash max(a\_1,\backslash ,a\_2,\backslash ,\backslash cdots,\backslash ,a\_n)$
• $b_n=\max (b_1,b_2,\cdots ,b_n)b\_n=\backslash max(b\_1,\backslash ,b\_2,\backslash ,\backslash cdots,\backslash ,b\_n)$

解题报告

按照题意，若 ，则让 $a_i,b_{i}a\_i,\backslash ,b\_i$ 进行交换. 随后，若 ，则让 $a_i,b_{i}a\_i,\backslash ,b\_i$ 进行交换.

在进行这些操作之后，检查序列 $a,ba,\backslash ,b$ 是否满足题意，若满足则输出 Yes，否则输出 No.

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n; cin>>n;
    vector<int>a(n+1),b(n+1);
    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)
        if(a[i]>a[n]) swap(a[i],b[i]);
    for(int i=1;i<n;++i)
        if(b[i]>b[n]) swap(a[i],b[i]);
    for(int i=1;i<n;++i)
        if(a[i]>a[n] || b[i]>b[n]){
            cout<<"No\n";
            return;
        }
    cout<<"Yes\n";
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

时间复杂度分析

每组测试数据的时间复杂度为 $O(n)O(n)$.

TAG

#模拟 #暴力

B. Three Sevens

某抽奖活动将会持续 $mm$ 天，第 $ii$ 天会有 $n_{i}n\_i$ 个人参与抽奖，他们的编号为 $a_{i,1},\cdots ,a_{i,n_i}a\_\{i,1\},\backslash ,\backslash cdots,\backslash ,a\_\{i,n\_i\}$.

每天都仅有一人获奖，并且第 $ii$ 天获奖的人不能再参加第 $i+1\sim mi+1\backslash sim\; m$ 天的抽奖.

现在对于给出的每天的参与抽奖的信息，问是否存在一个合法的抽奖活动的获奖名单.

解题报告

设 $ls{t}_{x}lst\_x$ 表示编号为 $xx$ 的人最后一次参与抽奖是第几天，即编号为 $xx$ 的人在第 $ls{t}_x+1\sim mlst\_x+1\; \backslash sim\; m$ 天都没有再参与抽奖.

这样的人就可能是第 $ls{t}_{x}lst\_x$ 天的获奖的人.

检查这 $mm$ 天是否都有这样的人存在即可.

#include<bits/stdc++.h>
using namespace std;
const int N=50000+5;
void solve(){
    int m; cin>>m;
    vector<int>a_lst(N);
    vector a(m,vector<int>());
    for(int i=0;i<m;++i){
        int n; cin>>n;
        while(n--){
            int x; cin>>x;
            a[i].push_back(x);
            a_lst[x]=i;
        }
    }
    vector<int>ans;
    for(int i=0;i<m;++i){
        bool have_answer=0;
        for(auto &x:a[i])
            if(a_lst[x]==i){
                have_answer=1;
                ans.push_back(x);
                break;
            }
        if(!have_answer){
            cout<<"-1\n";
            return;
        }
    }
    for(auto &x:ans)
        cout<<x<<' ';
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

时间复杂度分析

每组测试数据的时间复杂度为 $O\left({\sum }_{i=1}^m{n}_i\right)O\backslash left(\backslash sum\backslash limits\_\{i=1\}^mn\_i\backslash right)$.

TAG

#模拟 #暴力

C. Candy Store

商店里有 $nn$ 种糖果，编号为 $1\sim n1\; \backslash sim\; n$. 第 $ii$ 种糖果总共有 $a_{i}a\_i$ 块，每块卖 $b_{i}b\_i$ 元.

现在对糖果进行装袋销售，第 $ii$ 种糖果每袋装 $d_{i}d\_i$ 块，要求 $d_{i}d\_i$ 能整除 $a_{i}a\_i$（即对于同种糖果，要求每袋糖果的块数一样）. 这样每袋的售价为 $c_i=b_i\cdot d_{i}c\_i=b\_i\backslash cdot\; d\_i$.

现在将装袋好的糖果按照种类编号依次摆开，开始贴价格标签.

如果相邻的两种糖果，每袋的售价相同，则可以共用一个价格标签.

问使用最少的价格标签数量.

解题报告

考虑对于两种糖果 $(a_i,b_i),(a_j,b_j)(a\_i,\backslash ,b\_i),\backslash ;(a\_j,\backslash ,b\_j)$，如果能够找到一个价格标签 $cc$ 让它们共用，则 $cc$ 应该满足：

• $a_i\cdot b_i\mathrm{\%}c=0a\_i\backslash cdot\; b\_i\; \backslash ,\backslash \%\backslash ,c=0$
• $a_j\cdot b_j\mathrm{\%}c=0a\_j\backslash cdot\; b\_j\; \backslash ,\backslash \%\backslash ,c=0$
• $c\mathrm{\%}{b}_i=0c\backslash ,\backslash \%\backslash ,b\_i\; =0$
• $c\mathrm{\%}{b}_j=0c\backslash ,\backslash \%\backslash ,b\_j\; =0$

如果满足 $c\mathrm{\%}{b}_i=0c\backslash ,\backslash \%\backslash ,b\_i=0$ 和 $a_i\cdot b_i\mathrm{\%}c=0a\_i\backslash cdot\; b\_i\; \backslash ,\backslash \%\backslash ,c=0$，则 $a_i\mathrm{\%}\frac{c}{b_i}=0a\_i\; \backslash ,\backslash \%\backslash ,\backslash frac\{c\}\{b\_i\}=0$ 是肯定满足的.

即若 $x\mathrm{\%}y=0x\backslash ,\backslash \%\backslash ,y=0$，则一定有 $xk\mathrm{\%}yk=0xk\backslash ,\backslash \%\backslash ,yk=0$.

即需要满足：

• $cc$ 是 $a_i\cdot b_{i}a\_i\backslash cdot\; b\_i$ 和 $a_j\cdot b_{j}a\_j\backslash cdot\; b\_j$ 的公约数.
• $cc$ 是 $b_{i}b\_i$ 和 $b_{j}b\_j$ 的公倍数.

进一步地说：

• $cc$ 能被 $\gcd (a_i\cdot b_i,a_j\cdot b_j)\backslash gcd(a\_i\backslash cdot\; b\_i,\backslash ;a\_j\backslash cdot\; b\_j)$ 整除.
• $cc$ 能整除 $\mathrm{l}\mathrm{c}\mathrm{m}(b_i,b_j)\{\backslash rm\; lcm\}(b\_i,\backslash ;b\_j)$.
• $\gcd (a_i\cdot b_i,a_j\cdot b_j)\backslash gcd(a\_i\backslash cdot\; b\_i,\backslash ;a\_j\backslash cdot\; b\_j)$ 能整除 $\mathrm{l}\mathrm{c}\mathrm{m}(b_i,b_j)\{\backslash rm\; lcm\}(b\_i,\backslash ;b\_j)$.

故如果 ${}_{l⩽i⩽r}\{a_i\cdot b_i\}\backslash gcd\_\{l\backslash leqslant\; i\; \backslash leqslant\; r\}\; \backslash \{a\_i\backslash cdot\; b\_i\backslash \}$ 能整除 ${\mathrm{l}\mathrm{c}\mathrm{m}}_{l⩽i⩽r}\{b_i\}\{\backslash rm\; lcm\}\_\{l\backslash leqslant\; i\; \backslash leqslant\; r\}\backslash \{b\_i\backslash \}$，则说明存在一个价格标签 $cc$ 能够让第 $l\sim rl\backslash sim\; r$ 种糖果共用.

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve(){
    int n; cin>>n;
    LL GCD=0,LCM=1;
    int ans=1;
    for(int i=1;i<=n;++i){
        LL a,b; cin>>a>>b;
        GCD=gcd(GCD,a*b);
        LCM=lcm(LCM,b);
        if(GCD%LCM){
            ++ans;
            GCD=a*b;
            LCM=b;
        }
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

时间复杂度分析

每组测试数据的时间复杂度约为 $O(n\log (a_i\cdot b_i))O\backslash big(n\backslash log\; (a\_i\backslash cdot\; b\_i)\backslash big)$.

TAG

#数学 #数论 #最大公约数GCD

D. Shocking Arrangement

给一个序列 $a_1,\cdots ,a_{n}a\_1,\backslash ,\backslash cdots,\backslash ,a\_n$，保证 ${\sum }_{i=1}^n{a}_i=0\backslash sum\backslash limits\_\{i=1\}^n\; a\_i=0$.

现在可以对序列重新排序，要求：

其中 $\mathrm{\mid }x\mathrm{\mid }|x|$ 代表 $xx$ 的绝对值.

问重新排序后是否能够满足要求.

解题报告

考虑如何求 $\underset{1⩽l⩽r⩽n}{}\mathrm{\mid }{a}_l+\cdots +a_r\mathrm{\mid }\backslash max\backslash limits\_\{1\backslash leqslant\; l\; \backslash leqslant\; r\; \backslash leqslant\; n\}|a\_l+\backslash cdots+a\_r|$.

考虑前缀和 $su{m}_k={\sum }_{i=1}^k{a}_{i}sum\_k=\backslash sum\backslash limits\_\{i=1\}^ka\_i$，有

只需要保证 $sum\in (\min \{a\},\max \{a\}]sum\backslash in\backslash big(\backslash min\backslash \{a\backslash \},\backslash max\backslash \{a\backslash \}\backslash big]$，就一定有

设当前重新排序排到了第 $ii$ 个位置，对于前缀和 $su{m}_{i}sum\_i$，有：

• 若 $su{m}_{i-1}⩽0sum\_\{i-1\}\backslash leqslant\; 0$，则从序列 $aa$ 中选择一个非负整数作为 $a_{i}a\_i$.
• 若 $su{m}_{i-1}>0sum\_\{i-1\}>0$，则从序列中选择一个负数作为 $a_{i}a\_i$.
• 可以发现，这样可以保证 $\min \{sum\}>\min \{a\}\backslash min\backslash \{sum\backslash \}>\backslash min\backslash \{a\backslash \}$，并且由于 ${\sum }_{p=1}^n{a}_p=0\backslash sum\backslash limits\_\{p=1\}^na\_p=0$，所以如上两种情况肯定都能得到满足.

但特别地，若序列 $aa$ 全由 $00$ 组成，此时有 $\max \{a\}=\min \{a\}\backslash max\backslash \{a\backslash \}=\backslash min\backslash \{a\backslash \}$，则不论怎么重新排序都不能满足 $\min \{sum\}>\min \{a\}\backslash min\backslash \{sum\backslash \}>\backslash min\backslash \{a\backslash \}$，此时题目无解.

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n; cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;++i) cin>>a[i];
    if(*max_element(a.begin(),a.end())==0){
        cout<<"No\n";
        return;
    }
    queue<int>pos,neg;
    for(int i=0;i<n;++i)
        if(a[i]>=0) pos.push(a[i]);
        else neg.push(a[i]);
    vector<int>ans;
    int sum=0;
    for(int i=0;i<n;++i){
        if(sum<=0){
            ans.push_back(pos.front());
            pos.pop();
        } else {
            ans.push_back(neg.front());
            neg.pop();
        }
        sum+=ans[i];
    }
    cout<<"Yes\n";
    for(auto &x:ans) cout<<x<<' ';
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

时间复杂度分析

每组测试数据的时间复杂度为 $O(n)O(n)$.

TAG

#贪心 #数学 #最大子段和