Codeforces Round 979 (Div. 2) 总结

A

首先第一位的贡献一定是 \(0\)，然后考虑接下来 \(n-1\) 位，我们可以把最大值和最小值放在第一位和第二位，这样贡献就是 \((max-min) \times (n-1)\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1005;
int n;
void solve()
{
    int mx=0,mi=N;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        mx=max(mx,x);
        mi=min(mi,x);
    }
    cout<<(mx-mi)*(n-1)<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B

因为不同位置的 \(1\) 和 \(0\) 组成的子序列算作不同的，观察可知，当只有一个 \(1\) 时最小，为 \(1\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
int n;
void solve()
{
    cin>>n;
    cout<<1;
    for(int i=1;i<n;i++) cout<<0;
    cout<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE 
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C

充分理解下题意，当 \(1\) 的左右都是 \(0\) 时，才能用 \(and\) 操作消掉 \(1\)。所以如果开头或结尾是 \(1\)，或者有连续的两个 \(1\)，输出 YES。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
string s;

void solve()
{
    cin>>n>>s;
    s="0"+s;
    int st=0;
    if(s[1]=='1'||s[n]=='1') st=1;
    for(int i=1;i<n;i++) if(s[i]=='1'&&s[i+1]=='1') st=1;
    if(st) puts("YES");
    else puts("NO");
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

D

首先 \(\texttt{L}\) 和 \(\texttt{R}\) 相当于左移和右移，以及我们只需要考虑右移（或左移）即可。

对于每个形如 \(\texttt{RRR} \dots \texttt{LLL} \dots\) 的子串 \([l,r]\)，其中的 \(p_i\)(\(l \le i \le r\)) 显然可以到达 \([l,r]\) 中的任一位置，也就是说我们可以任意安排 \([l,r]\) 的顺序。
可知 \(s\) 由多个上述子串构成。

而对于 \(1 \le i < n\)，若 \(s_i=\texttt{L}\) 且 \(s_{i+1}=\texttt{R}\)，都会在 \(i\) 处形成一个断点。也就是说 \([1,i]\) 中的数都不可能右移到 \([i+1,n]\) 的位置。因为只考虑右移，我们只考虑最大值，序列要合法就必须所有的 \([l,r]\) 的最大值小于等于 \(r\)。

因此我们考虑每个 \(\texttt{L} \texttt{R}\)，下标为 \(i\) 和 \(i+1\)，如果 \([1,i]\) 的最大值大于 \(i\)，就说明不可以实现。统计这样不合法的 \(\texttt{L} \texttt{R}\) 的个数 \(cnt\)，等于 \(0\) 输出 YES。

最后思考修改后会有什么影响，就是看看改之前和改之后是不是 \(\texttt{L} \texttt{R}\)，更新 \(cnt\) 即可。

我用的是 ST 表维护区间最值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,q;
int log_2[N];
int a[N];
string s;
int f[N][25];
void init()
{
    for(int i=1;i<=n;i++) f[i][0]=a[i];
    for(int j=1;j<=20;j++) 
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int query(int l,int r)
{
    int t=log_2[r-l+1];
    return max(f[l][t],f[r-(1<<t)+1][t]);
}
bool check(int x)
{
    return query(1,x)>x;
}

void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    init();
    cin>>s;
    s='0'+s;
    int cnt=0;
    for(int i=2;i<n;i++)
        if(s[i]=='L'&&s[i+1]=='R') 
            if(check(i))
                cnt++;
    while(q--)
    {
        int x;
        cin>>x;
        if(s[x]=='L')
        {
            s[x]='R';
            if(s[x+1]=='R') if(check(x)) cnt--;
            if(s[x-1]=='L') if(check(x-1)) cnt++;
        }
        else 
        {
            s[x]='L';
            if(s[x-1]=='L') if(check(x-1)) cnt--;
            if(s[x+1]=='R') if(check(x)) cnt++;
        }
        if(!cnt) puts("YES");
        else puts("NO");
    }
}
int main ()
{
    for(int i=2;i<=N-5;i++) log_2[i]=log_2[i/2]+1;
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}