链接：Dashboard - practice - Codeforces

3.18 A,B

题意：A有 $a_i$ 个颜色为 $i$ 的弹珠，B有 $b_i$ 个颜色为 $i$ 的弹珠，现在游戏规则如下：从A开始，两人轮流进行，每次选择一种大家都有的颜色，然后自己丢弃一颗该颜色的弹珠，对方丢弃所有该颜色的弹珠。定义最终分数为A的所有弹珠和与B的所有弹珠和的差。A想最大化分数，B想最小化分数，求最终的分数。

当A选择时，对于 $i$ 和 $j$ ，若A选择了 $i$ ，B选择了 $j$ ，那么必有：
$$
(a_i-1)-(b_j-1)>(a_j-1)-(b_i-1)
$$
即：
$$
a_i+b_i>a_j+b_j
$$
故按照 $a_i+b_i$ 降序排列，依次操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;

bool cmp(pair<int,int>x,pair<int,int>y)
{
    return x.first>y.first;
}

void solve()
{
    int n;
    cin>>n;
    int a[n+5]={0};
    int b[n+5]={0};
    pair<int,int>s[n+5];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i].first+=a[i];
        s[i].second=i;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        s[i].first+=b[i];
    }
    sort(s+1,s+n+1,cmp);

    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        if(i%2==1)
        {
            ans+=a[s[i].second]-1;
        }
        else
        {
            ans-=b[s[i].second]-1;
        }
    }
    cout<<ans<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    
    return 0;
}

3.18 C

题意：对于一个空数组，每次有两种操作：

$1\ x$ ：将 $2^x$ 插入数组；

$2\ w$ ：对于 $w$ ，能否从数组中选出若干个数使他们的和等于 $w$ 。

直接从最大的 $2^x$ 开始试，能选就选，这样一定最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
#define int long long

int pre[30];
int pw[40];

signed main()
{
    pre[0]=1;
    for(int i=1;i<=30;i++)pre[i]=pre[i-1]*2;
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int t,v;
        cin>>t>>v;
        if(t==1)pw[v]++;
        if(t==2)
        {
            bool flag=0;
            for(int p=30;p>=0;p--)
            {
                int cnt=v/pre[p];
                if(cnt<=pw[p])v-=cnt*pre[p];
                else v-=pw[p]*pre[p];
                
                if(v==0)
                {
                    flag=1;
                    break;
                }
            }
            if(flag)cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
    return 0;
}

3.19 D

题意：给定一个数列 $a $ ，问长度至少为3的子序列个数，其中子序列中每相邻3个元素的和为偶数。

设置状态 $dp[i][k_1][k_2]$ 表示子序列最后一个元素为 $a_i$ ，最后一个元素的奇偶性为 $k_1$ ，倒数第二个元素的奇偶性为 $k_2$ 时的子序列个数。转移方程为：
$$
dp[i][k_1][k_2]=\sum dp[j][k_1’][k_2’]
$$
其中满足 $k_2$ 即为 $a_j$ ， $k_1,k_2,k_2’$ 和为偶数。为了提升时间复杂度，设置累加数组 $s[2][2]$ ，表示最后两个元素的奇偶情况的个数，因此转移方程就变成了：
$$
dp[i][k_1][k_2]=s[k_2][k_2’]
$$

$$
s[k_1][k_2]+=dp[i][k_1][k_2]+even/odd
$$

更新累加数组时还要加上单独的一项，这是为了统计上只有两个元素的情况，而这是 $dp$ 统计不了的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n;
int a[200005];
int dp[200005][2][2];//0为奇，1为偶
int ans;
int s[2][2];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    s[(a[2]+1)%2][(a[1]+1)%2]++;
   
    int odd=0,even=0;
    if(a[1]%2==1)odd++;
    else even++;
    if(a[2]%2==1)odd++;
    else even++;
    
    for(int i=3;i<=n;i++)
    {
        if(a[i]%2==1)
        {
            dp[i][0][0]=s[0][1];
            dp[i][0][1]=s[1][0];
            s[0][0]=(s[0][0]+dp[i][0][0]+odd)%mod;
            s[0][1]=(s[0][1]+dp[i][0][1]+even)%mod;
        }
        else
        {
            dp[i][1][0]=s[0][0];
            dp[i][1][1]=s[1][1];
            s[1][0]=(s[1][0]+dp[i][1][0]+odd)%mod;
            s[1][1]=(s[1][1]+dp[i][1][1]+even)%mod;
        }

        if(a[i]%2==1)odd++;
        else even++;
    }
    
    for(int i=3;i<=n;i++)
    {
        ans=(ans+dp[i][(a[i]+1)%2][0]+dp[i][(a[i]+1)%2][1])%mod;
    }

    cout<<ans;
    return 0;
}

3.20 E

题意：给出三个数组 $l,r,c$ ，其中 $r$ 中的数不会重复。对三个数组分别排序，最后使得 $\sum c_i\times (r_i-l_i)$ 最小，且满足对每个 $i$ ，$r_i>l_i$ 。

考虑贪心：

  1. 尽可能不要使区间长度平均，尽可能使小的 $l$ 与大的 $r$ 配对。
  2. 长度越大的区间对应的 $c$ 应该越小。

因此算法可以为：将 $l,r$ 一起排序，从右端点开始遍历，遇到 $r$ 就加入小根堆中，遇到 $l$ 就将其与目前最小的 $r$ 配对，因为这样能使越小的 $l$ 与越大的 $r$ 配对。然后再将 $c$ 排序处理答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int c[n+5];
        pair<int,int>a[2*n+5];
        for(int i=1;i<=n;i++)cin>>a[i].first,a[i].second=1;
        for(int i=1;i<=n;i++)cin>>a[i+n].first,a[i+n].second=2;
        for(int i=0;i<n;i++)cin>>c[i];
        
        sort(a+1,a+2*n+1);
        sort(c,c+n);

        // for(int i=1;i<=2*n;i++)cout<<a[i].first<<" "<<a[i].second<<endl;cout<<endl;
        
        // for(int i=0;i<n;i++)cout<<c[i]<<" ";

        priority_queue<int,vector<int>,greater<int> >q;
        vector<int>ans;

        for(int i=2*n;i>=1;i--)
        {
            if(a[i].second==2)q.push(a[i].first);
            else
            {
                int tmp=q.top();
                q.pop();
                ans.push_back(tmp-a[i].first);
            }
        }

        sort(ans.rbegin(),ans.rend());
        int sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=ans[i]*c[i];
        }
        cout<<sum<<endl;
    }
    return 0;
}

3.21 F

题意：给一个长度为 $n$ 的数组 $a$ ，有两种操作：

  • 将最后一个元素移动到第一个，其他元素依次向后排。
  • 将数组倒转。

现要使数组非递减，求最小操作次数，如果无解输出-1.

可以观察到，倒转后再进行操作1相当于把第一个元素放在最后，因此有如下贪心：

将 $a$ 赋值一份接在 $a$ 后面，使 $a$ 的长度变成 $2n$ 。遍历 $a’$ ，若有解，那么一定存在一段长度为 $n$ 的子序列满足非递减或非递增。找到对应序列后，分别考虑将后面元素移到前面更优还是将前面元素移到后面更优。注意要找到所有的满足条件的子序列最后求最大值。

特别判断有连续相同元素的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n*2+5];
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i+n]=a[i];
        }
        
        if(n==1)
        {
            cout<<"0\n";
            continue;
        }
        if(n==2)
        {
            if(a[1]<=a[2])cout<<"0\n";
            else cout<<"1\n";
            continue;
        }

        bool flag=0;
        int pre=-1;
        int cnt=1;
        int pos=0;
        int ans=0x3f3f3f3f;
        int c0=1;


        if(a[2]==a[1])cnt=2,pre=-1,c0++;
        if(a[2]>a[1])cnt=2,pre=1;
        if(a[2]<a[1])cnt=2,pre=0;

        for(int i=3;i<=2*n;i++)
        {
            if(pre==-1)
            {
                cnt++;
                if(a[i]!=a[i-1])pre=a[i]>a[i-1],c0=1;
                else c0++;

            }
            else if(a[i]==a[i-1])
            {
                cnt++;
                c0++;
            }
            else 
            {
                if(pre == (a[i]>a[i-1]))cnt++;
                else
                {
                    pre=(a[i]>a[i-1]);
                    cnt=c0+1;
                    c0=1;
                }
            }

            if(cnt==n)
            {
                flag=1;
                pos=i;
                if(pos==n)
                {
                    if(pre==1 || pre==-1)ans=0;
                    else ans=1;
                    break;
                }

                int ans1=pos-n+1;
                int ans2=2*n-pos;

                if(pre==1)ans1++;
                if(pre==0)ans2++;
                ans=min(ans,min(ans1,ans2));

                i=i-n+2;
                cnt=1;
                pre=-1;
                c0=1;
            }
        }

        if(!flag)
        {
            cout<<"-1\n";
            continue;
        }
        cout<<ans<<'\n';
    }
}

3.22 G

题意：有 $n$ 个区间 $[l_i,r_i]$ ，从坐标0开始移动，每次最大移动长度为 $k$ ，但是需要在第 $i$ 次移动后落入区间 $[l_i,r_i]$ ，求最小的 $k$ 。

二分模板题。在判断时每次求出可以移动的范围是多少，依次更新即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n;
int l[N],r[N];

bool check(int k)
{
    int pl=0,pr=0;
    for(int i=1;i<=n;i++)
    {
        pl=max(0,pl-k);
        pr=pr+k;
        if(pl>r[i] || pr<l[i])return false;
        pl=max(pl,l[i]);
        pr=min(pr,r[i]);
    }
    return true;
}

void solve()
{
    cin>>n;
    int maxx=0;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        maxx=max(maxx,r[i]);
    }

    int ll=0,rr=maxx+1;
    while(ll<rr)
    {
        int mid=ll+rr>>1;
        if(check(mid))rr=mid;
        else ll=mid+1;
    }

    cout<<ll<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

3.23 H

题意：给出 $n$ ，找这样的数字组合 $(a,b,c)$ 使得 $a+b+c=n$ 且 $a,b,c$ 各位数组的和等于 $n$ 的各数位的和，求这样的组合个数。顺序不同会算成不同的组合。$n\leq 1e7$

假设 $n$ 为三位数，设三个数各数位的和分别为 $x,y,z$ ，$n$ 各数位分别为 $x’,y’,z’$ 那么有：
$$
100x+10y+z=100x’+10y’+z’
$$

$$
x+y+z=x’+y’+z’
$$

注意到 $x’,y’,z’$ 均小于等于9，那么一定有 $x=x’,y=y’,z=z’$ 。因此单独考虑每一位即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int ans=1;
    
    int n;
    cin>>n;

    while(n)
    {
        int tmp=n%10;
        n/=10;
        ans*=(tmp+2)*(tmp+1)/2;
    }

    cout<<ans<<endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

3.24 I

题意：给定一个正 $n$ 边形，每条边上有 $a_i$ 个点，现在以给的点为顶点连线构成三角形，每个点最多出现在一个三角形中，且三角形之间不能交叉，求最多可构造的三角形数量。

又被math干破防了

若只考虑两条相邻的边分别有 $a_i,a_j$ 个点，考虑最优构造方式：

  1. 若满足 $a_i\geq 2a_j$ 或 $a_j\geq 2a_i$ ，那么最大值就是 $a_j$ 或 $a_i$ 。
  2. 若 $a_i$ 与 $a_j$ 的数量一样多，那么每条边取相邻的3个点，6个点为一对，每6个点可以构造出2个三角形，故数量为 $\lfloor (a_i+a_j)/3\rfloor$ 。
  3. 否则假设 $a_i>a_j$ ，先 $a_i$ 取两个点，$a_j$ 取一个点，每次构成一个三角形，直至 $a_i=a_j $ ，然后按照情况2得到答案。

这样的话可以枚举以边 $a_i$ 为分界线，把 $1-a_i$ 的边上的点与 $a_{i+1}-a_n$ 的边上的点做匹配，相当于在两条边之间构造三角形。

但是需要注意的是要让点最多的边作为 $a_1$ ，其他边依次顺移，这样是为了使分界线两边差距太大导致不优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int n;
    cin>>n;
    int aa[n+2]={0},a[n+2]={0};
    int pre1[n+5]={0},pre2[n+5]={0};
    
    int maxx=0;int p;
    for(int i=1;i<=n;i++)
    {
        cin>>aa[i];
        if(maxx<aa[i])
        {
            maxx=aa[i];
            p=i;
        }
    }
    for(int i=p;i<=n;i++)a[i-p+1]=aa[i];
    for(int i=1;i<p;i++)a[n-p+1+i]=aa[i];

    for(int i=1;i<=n;i++)pre1[i]=pre1[i-1]+a[i];
    for(int i=n;i>=1;i--)pre2[i]=pre2[i+1]+a[i];

    int ans=0;
    for(int i=1;i<n;i++)
    {
        int l=pre1[i];
        int r=pre2[i+1];
        if(l<r)swap(l,r);
        int t;
        if(l>=r*2)t=r;
        else
        {
            t=l-r;
            l-=2*t;
            r-=t;
            t+=(l+r)/3;
        }
        ans=max(ans,t);
    }
    
    
    cout<<ans;
    return 0;
}

3.25 J

题意：给定一个字符串，每次只能选最大的子序列进行操作：将 $a_1a_2…a_{n-1}a_n$ 变为 $a_na_1…a_{n-2}a_{n-1}$ 。求能否将字符串变为非递减顺叙？如果可以求最小操作次数。

每次能选择的子序列是固定的，因此可以通过倒序遍历储存最大字母位置来获得第一次操作的子序列。因此最大操作次数就是该子序列的长度减1。操作后等效于将子序列倒序排列。然后判断字符串是否是非递减的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        char s[n+2],x[n+2]="";
        cin>>s;
        for(int i=0;i<n;i++)x[i]=s[i];
        int p=n-1;

        vector<int>pos,v;
        pos.push_back(p);
        v.push_back(s[p]-'a');
        int cnt=1;

        for(int i=n-2;i>=0;i--)
        {
            if(s[i]>=s[p])
            {
                cnt++;
                p=i;
                pos.push_back(p);
                v.push_back(s[p]-'a');
            }
        }

        int cnt2=0;
        for(int i=pos.size()-1;;i--)
        {
            if(v[i-1]==v[i])cnt2++;
            else break;
        }

        cnt-=cnt2;

        for(int i=0;i<pos.size();i++)
        {
            char c=v[v.size()-i-1]+'a';
            x[pos[i]]=c;
        }

        bool flag=1;
        for(int i=1;i<n;i++)
        {
            if(x[i]-'a'<x[i-1]-'a')
            {
                flag=0;
                break;
            }
        }
        if(flag)cout<<cnt-1<<"\n";
        else cout<<-1<<"\n";
    }
    return 0;
}

3.26 K

题意：给定一个长度为 $n$ 的数列 $a$ ，可以执行 $k$ 次操作，每次选择两个不同的数相减，将其绝对值添加到数组的末尾，求操作后数组 $a$ 的最小值。

注意到当 $k$ 大于等于3时，最小值一定是0：第一次和第二次都选相同的两个数相减得到两个相同的差，再相减得到0。

当 $k=1$ 时，直接排序后求相邻两数相减的最小值。

当 $k=2$ 时，用 $set$ 记下任两个数相减得到的差，相当于第一次操作后能产生的数，然后对于第二次操作，枚举数组 $a$ ，每次在 $set$ 中找和它最相近的数相减更新答案。用 $set.lower$_$bound$ 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int>a;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }

    if(k>=3)
    {
        cout<<0<<endl;
        return ;
    }

    sort(a.begin(),a.end());
    if(k==1)
    {
        int ans=a[0];
        for(int i=1;i<n;i++)ans=min(ans,a[i]-a[i-1]);
        cout<<ans<<endl;
        return ;
    }

    set<int>d;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            d.insert(a[j]-a[i]);
        }
    }
    
    int ans=min(a[0],*d.begin());
    for(auto i:a)
    {
        if(d.lower_bound(i)!=d.end() && d.lower_bound(i)!=d.begin())
        {
            int it1=*d.lower_bound(i);
            int it2=*(--d.lower_bound(i));
            ans=min(ans,min(abs(it1-i),abs(it2-i)));
        }
        if(d.lower_bound(i)==d.end())
        {
            int it=*(--d.lower_bound(i));
            ans=min(ans,abs(it-i));
        }
        if(d.lower_bound(i)==d.begin())
        {
            int it=*d.lower_bound(i);
            ans=min(ans,abs(it-i));
        }
    }
    cout<<ans<<endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

3.27 L,M

题意：给定两个长为 $n$ 的数组 $a,b$ ，每次可以进行如下操作：在 $a$ 中选择一个区间 $[l,r]$ ，然后将这个区间中的所有数变成这个区间中最大的数。问否通过有限次操作后将 $a$ 变得和 $b$ 一样。

可以观察到以下结论：

  • 只能将 $a_i$ 变小，故若存在 $a_i>b_i$ ，不可能满足。

  • 若 $a_i!=b_i$ ，若考虑 $a_i$ 右边，如果 $a_{i+1}>b_i$ ，那么一定右边不行。左边同理。

  • 若 $a_i!=b_i$ ，若考虑 $a_i$ 右边，若存在 $a_j=b_i$ ，但 $i$ 与 $j$ 之间存在 $b_k<b_i$ ，那么也是无解的。左边同理。

  • 因此若 $a_i!=b_i$ ，考虑 $a_i$ 右边有解，那么一定满足最近的 $a_j=b_i$ 之间所有 $a_k<a_i$ ，$b_k>=b_i$ 。

题目的数据有 $n^2\leq10^6$ 和 $n\leq 2\times 10^5$ 两种。

  1. $O(n^2)$ ：

    从小到大考虑 $a$ 中的所有元素，每次都将每个数覆盖最大的区间，这样是不会对后来产生影响的，因为小数不会覆盖大的数，而大数可以覆盖小的数。若在覆盖小数的过程中发现这个数匹配，那么区间扩展停止。最后检查 $a$ 是否与 $b$ 相等。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    #include<bits/stdc++.h>
    using namespace std;

    void solve()
    {
        int n;
        cin>>n;
        vector<int>num[n+1];
        int a[n],b[n];
        for(int i=0;i<n;i++)cin>>a[i],num[a[i]].push_back(i);
        for(int i=0;i<n;i++)cin>>b[i];


        for(int i=1;i<=n;i++)
        {
            for(auto j:num[i])
            {
                for(int k=j-1;k>=0;k--)
                {
                    if(a[k]<a[j] && a[k]!=b[k])a[k]=a[j];
                    else break;
                }
                for(int k=j+1;k<n;k++)
                {
                    if(a[k]<a[j] && a[k]!=b[k])a[k]=a[j];
                    else break;
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(a[i]!=b[i])
            {
                cout<<"NO\n";
                return ;
            }
        }
        cout<<"YES\n";
        return ;
    }

    int main()
    {
        int t;
        cin>>t;
        while(t--)solve();
        return 0;
    }

  2. $O(n)$ ：

    直接按照结论检查每一个 $a_i$ 是否满足条件，最后实现时从最小的 $b_i$ 开始，因此也不会造成影响。需要统计离每个 $a_i$ 最近的比它大的数、离每个 $b_i$ 最近的最小的数，用单调栈完成统计。头尾扫两遍再汇总，分别实现找 $(i,j)$ 和 $(j,i)$ 。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    #include <bits/stdc++.h>
    using namespace std;

    #define pb push_back
    #define ff first
    #define ss second

    typedef long long ll;
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    typedef pair<ld, ld> pld;

    const int INF = 1e9;

    int main()
    {
        ios_base::sync_with_stdio(0); cin.tie(0);
        int T;
        cin >> T;
        for(int tt = 1; tt <= T; tt++)
        {
            int n;
            cin >> n;
            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];
            bool val[n + 1];
            memset(val, false, sizeof(val));
            for(int t = 0; t < 2; t++)
            {
                int prvb[n + 1]; //prev smaller
                int nxta[n + 1]; //next greater
                stack<pii> s;
                s.push({INF, n + 1});
                for(int i = n; i >= 1; i--)
                {
                    while(s.top().ff <= a[i]) s.pop();
                    nxta[i] = s.top().ss;
                    s.push({a[i], i});
                }
                while(!s.empty()) s.pop();
                s.push({0, 0});
                for(int i = 1; i <= n; i++)
                {
                    while(s.top().ff >= b[i]) s.pop();
                    prvb[i] = s.top().ss;
                    s.push({b[i], i});
                }
                int m[n + 1];
                memset(m, 0, sizeof(m));
                for(int i = 1; i <= n; i++)
                {
                    m[a[i]] = i;
                    if(a[i] <= b[i] && m[b[i]]) val[i] |= prvb[i] < m[b[i]] && nxta[m[b[i]]] > i;
                }
                reverse(a + 1, a + n + 1);
                reverse(b + 1, b + n + 1);
                reverse(val + 1, val + n + 1);
            }
            bool ans = true;
            for(int i = 1; i <= n; i++) ans &= val[i];
            cout << (ans ? "YES" : "NO") << endl;
        }
        return 0;
    }

3.29 N

题意：给出长度为 $n$ 的数组 $a$ ，将其划分成 $k$ 个连续子序列，使得 $sum=\sum i\times sum_i$ 最大，$i$ 是区间标号，$sum_i$ 是这个区间内所有元素的和。求这个值。

初始默认每个数都单独一个区间并求出 $sum$ 。若选择把一个数 $a_i$ 合并到前一个区间，那么 $sum$ 会减少 $suf_{i}$ ，$suf_i$ 是从 $a_i$ 到 $a_n$ 的和，因为往后所有区间的 $i$ 都减少1。故只有当 $suf_i$ 是负数时才合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n+2];
        int pre[n+2];
        pre[0]=0;
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            pre[i]=pre[i-1]+a[i];
            sum+=a[i]*i;
        }
        for(int i=2;i<=n;i++)
        {
            if(pre[n]-pre[i-1]<=0)sum-=pre[n]-pre[i-1];
        }
        cout<<sum<<endl;
    }
    return 0;
}

4.1 O

题意：给出一个长度为 $n$ 的数组 $a $ ，给出 $q$ 次询问，每次给出一个数 $k$ 。在每一次询问中，可以对任意一个数进行+1操作，一共不能超过 $k$ 次操作，求所有数的 $&$ 的最大值。$nq\leq 10^5$

从最高位开始依次向下遍历，判断能否将这一位全变为1，若需要的操作数不超过 $k$ ，那么就可以操作，否则继续。要注意每次如果操作可行，需要把对应的 $a[i]$ 进行更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Max=(int)1<<61;
signed main()
{
    int n,q;
    cin>>n>>q;
    int aa[n+5];
    for(int i=1;i<=n;i++)cin>>aa[i];
    while(q--)
    {
        int ans=0;
        int sum;
        cin>>sum;
        int a[n+5];
        for(int i=1;i<=n;i++)a[i]=aa[i];
        for(int i=60;i>=0;i--)
        {
            int tot=0;
            int x=(int)1<<i;
            for(int p=1;p<=n;p++)
            {
                if((a[p]>>i)&1)continue;
                int d;
                if(x>a[p])d=x-a[p];
                else 
                {
                    d=(x+Max-a[p])%x;
                    if(d==0)d=x;
                }
                tot+=d;
                if(tot>sum)break;
            }
            if(tot<=sum)
            {
                sum-=tot;
                ans+=x;

                for(int p=1;p<=n;p++)
                {
                    if((a[p]>>i)&1)continue;
                    int d;
                    if(x>a[p])d=x-a[p];
                    else 
                    {
                        d=(x+Max-a[p])%x;
                        if(d==0)d=x;
                    }
                    a[p]+=d;
                }
            }
        }
        cout<<ans<<endl;
    }
    // system("pause");
    return 0;
}

4.2 P

题意：给出长为 $n$ 的数组 $a$ ，每个数都不相等。现需要添加一个数 $a_{n+1}$ ，其值任意指定，然后选定数 $x$ ，每次操作使每个数加上 $x$ ，最后使所有数都相等。求最少操作次数。

最后考虑 $a_{n+1}$ ，先考虑 $x$ 。

先处理出所有数与最大数的差。若把最终的数设定为最大的数，那么 $x$ 就是所有差的最大公因数。若最终的数设定为比最大数大，设最终数与最大数的差为 $d$ ，那么 $x$ 使 $d$ 的因子，而其他的差都增加了 $d$ ，那么仍需要 $x$ 是所有差的最大公因数。故 $x$ 就是所有差的最大公因数。

考虑 $a_{n+1}$ 。$a_{n+1}$ 可以是 $maxa-kx$ ，也可是 $maxa+x$ ，比较哪种更优即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define int long long
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        map<int,int>q;
        int n;
        cin>>n;
        int a[n+1];
        int maxx=-1000000005;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            q[a[i]]=1;
            maxx=max(maxx,a[i]);
        }

        if(n==1)
        {
            cout<<"1\n";
            continue;
        }

        int gcd=0;
        for(int i=1;i<=n;i++)
        {
            int t=maxx-a[i];
            gcd=__gcd(gcd,t);
        }

        int ap;
        for(int i=maxx;;i-=gcd)
        {
            if(q[i]!=1)
            {
                ap=i;
                break;
            }
        }
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=1LL*(maxx-a[i])/gcd;
        }
        LL t1=(maxx-ap)/gcd+ans;
        LL t2=ans+n;
        cout<<min(t1,t2)<<endl;
    }
    return 0;
}

4.4 Q

题意：给定一个长度为 $n$ 的数组 $a$ ，每次操作选择一个整数 $x$ ，使数组的每个数都变成 $\lfloor \frac{a_i+x}{2}\rfloor$ 。若要把它们变得一样，最少需要操作多少次。

假设把所有的数都变成数组中最小的数 $a_{min}$ ，那么只需要每次都使 $x$ 为 $a_{min}$ ，且操作次数就是让 $a_{max}$ 变成 $a_{min}$ 的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin>>n;
    int a[n+5];
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int minn=a[1],maxx=a[n];
    int d=maxx-minn;
    int ans=d==0?0:log2(d)+1;
    cout<<ans<<endl;
    if(ans<=n)
    {
        for(int i=1;i<=ans;i++)cout<<a[1]<<" ";cout<<endl;
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

4.5 R

题意：有 $n$ 个怪兽排成一排，每个怪兽有生命值 $a_i$ ，现在选择一个怪兽对其使用连锁闪电，连锁闪电每次会随机向左右相邻的怪兽扩散，且每次扩散伤害减1。一次闪电消灭所有怪兽，求最小的初始伤害。

假设选定 $i$ 为第一个目标，那么只要闪电全部向左扩散后，再全部向右扩散后能消灭怪兽，或者先全部向右扩散，再全部向左扩散后能消灭全部怪兽即可。

预处理两个数组，分别储存从左往右和从右往左依次消灭怪兽时每个怪兽需要的伤害值。

假设闪电先向左扩散再向右扩散，那么在向右扩散时需要满足右边怪兽所需要的最大伤害值，另一种情况同理。

因此枚举第一个目标位置，然后比较上述左右的伤害值max，然后与 $a_i$ 比较取最大值。

在闪电先向左再向右时虽然只考虑了右边能否全部消灭，但不用担心左边，因为该值会与先向右再向左的值比较，若大于，那么左边一定可以消灭掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
#define int long long

int a[300005];
int pre[300005],suf[300005];

signed main()
{
    int n;
    cin>>n;
    int maxx=0;
    int p;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pre[i]=a[i]+n-i;//3,2,1,0
        suf[i]=a[i]+i-1;//0,1,2,3
    }

    for(int i=1;i<=n;i++)pre[i]=max(pre[i],pre[i-1]);
    for(int i=n;i>=1;i--)suf[i]=max(suf[i+1],suf[i]);

    int ans=1e9+3e5+1;
    for(int i=1;i<=n;i++)
    {
        int tmp=a[i];
        if(i>1)tmp=max(tmp,pre[i-1]);
        if(i<n)tmp=max(tmp,suf[i+1]);
        ans=min(ans,tmp);
    }
    cout<<ans;
    return 0;
}

4.6 S

题意：给出一棵二叉树，每个节点有一个字母：$U$ 表示回到这个点的父亲，$L$ 表示去到这个点的左儿子，$R$ 表示去到这个点的右儿子。现在从根出发，要到达任一个叶子结点。每次操作可以改变一个节点的指令，求最小操作次数。

从根出发dfs，更新到达每一个节点的操作次数，最后比较叶子结点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;

int op[300005];
int n;
vector<int>g[300005];
int d[300005];

void dfs(int now)
{
    // cout<<now<<endl;
    if(g[now][0]!=0)
    {
        int nxt=g[now][0];
        if(op[now]==1)d[nxt]=d[now];
        else d[nxt]=d[now]+1;
        dfs(nxt);
    }

    if(g[now][1]!=0)
    {
        int nxt=g[now][1];
        if(op[now]==2)d[nxt]=d[now];
        else d[nxt]=d[now]+1;
        dfs(nxt);
    }

}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        if(c=='L')op[i]=1;
        if(c=='R')op[i]=2;
        if(c=='U')op[i]=0;
    }

    vector<int>leaf;
    for(int i=1;i<=n;i++)
    {
        g[i].clear();
        d[i]=0;
        int ls,rs;
        cin>>ls>>rs;
        if(ls==0 && rs==0)
        {
            leaf.push_back(i);
        }
        g[i].push_back(ls);
        g[i].push_back(rs);
    }

    dfs(1);

    int ans=0x3f3f3f3f;
    for(auto i:leaf)
    {
        ans=min(ans,d[i]);
    }
    cout<<ans<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

4.8 T

题意：构造一棵有 $n$ 个节点的树，给出 $q$ 个询问，每次询问是否存在两个叶子结点它们的距离是 $d_i$ 。在每次询问中可以最多执行一次操作：选择 $u,v_1,v_2$ ，其中 $u,v_1$ 有边，$u,v_2$ 无边，将 $u,v_1$ 之间的边删去，在 $u,v_2$ 之间连一条边。给出构造的初始的数与每次的操作。$n,q\leq 500$

构造这棵树初始为一条链，每次只维护以2号点为根的两个叶子的距离，其中令一个叶子为节点1。若距离不够，那么从链的尾端移点到2号节点上；若距离大了，从2号节点的另一条链上移点到初始链的尾端。可以开两个数组分别维护尾端的链的节点和2号点另一条链的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int n,d;
    cin>>n>>d;
    int a[d+1];
    for(int i=1;i<=d;i++)cin>>a[i];
    for(int i=1;i<n;i++)cout<<i<<" "<<i+1<<endl;

    int lk1[n+1],lk2[n+1];
    lk2[0]=2;
    for(int i=0;i<=n-2;i++)lk1[i]=i+2;
    int l1=n-2,l2=0;

    bool flag=0;
    for(int i=1;i<=d;i++)
    {
        if(!flag&&a[i]==n-1)
        {
            cout<<"-1 -1 -1\n";
            continue;
        }
        else flag=1;

        if(a[i]==1+l2)
        {
            cout<<"-1 -1 -1\n";
            continue;
        }
        if(a[i]>1+l2)
        {
            int lft=a[i]-l2-1;
            int u=lk1[l1-lft+1];
            int v1=lk1[l1-lft];
            int v2=lk2[l2];
            cout<<u<<" "<<v1<<" "<<v2<<endl;

            l1-=lft;
            for(int i=1;i<=lft;i++)lk2[l2+i]=lk1[l1+i];
            l2+=lft;
        }
        if(a[i]<1+l2)
        {
            int ex=l2+1-a[i];
            int u=lk2[l2-ex+1];
            int v1=lk2[l2-ex];
            int v2=lk1[l1];
            cout<<u<<" "<<v1<<" "<<v2<<endl;

            l2-=ex;
            for(int i=1;i<=ex;i++)lk1[i+l1]=lk2[l2+i];
            l1+=ex;
        }
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

4.9 U

题意：给出一个长为 $n$ 的数组 $a$ ，每次执行一次操作：首先将第一个数移到最后，然后让这个数依次向前移动直到前一个数严格小于它。求让这个数组有序的最少操作次数，若不能输出-1。

首先考虑-1的情况：

例如 1,5,3，可以观察到当一个数从后往前移时若移过的数不满足单调递减时，不存在答案。因为这种情况下，后面的数是乱序的，而这些数永远无法成为第一个数（更小的数排在前面），因此无法通过操作使其有序。

所以只需要两个指针指向头尾比较即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n+1];
        for(int i=1;i<=n;i++)cin>>a[i];

        int tail=n;
        int minn=a[n];
        int head=1;
        bool flag=1;
        int cnt=0;
        while(tail!=head)
        {
            if(minn<a[head])
            {
                cnt++;
                head++;
                continue;
            }
            else
            {
                while(a[head]<=minn && tail>head+1)
                {
                    tail--;
                    if(a[tail]>minn)
                    {
                        flag=0;
                        break;
                    }
                    minn=a[tail];
                }
                if(minn<a[head])
                {
                    cnt++;
                    head++;
                    continue;
                }
                break;
            }
        }
        if(flag)cout<<cnt<<endl;
        else cout<<"-1\n";
    }
    return 0;
}

4.10 V

题意：给出一个长度为 $n$ 的数组 $a$ ，另有一个数组 $b$ ，每个元素 $b_i=2^{a_i}$ 。求不同的组合 $(i,j)$，$i<j$ 的数量，使得 $b_i^{b_j}=b_j^{b_i}$ 。

$$
2^{a_i^{2^{a_j}}}=2^{a_j^{2^{a_i}}}\rightarrow 2^{a_j}a_i=2^{a_i}a_j\rightarrow \frac{2^{a_i}}{a_i}=\frac{2^{a_j}}{a_j}
$$

令 $f(x)=\frac{2^x}{x}$ ，可以做出它的图像，发现只有当 $x=1,x=2$ 时两个值相等，其他情况只有当 $x$ 相同时才能使两个值相等。

注意什么时候要int转long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        map<int,int>a;
        a.clear();
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            a[x]++;
        }
        LL ans=0;
        ans+=1LL*a[1]*a[2];
        for(auto i:a)
        {
            ans+=1LL*i.second*(i.second-1)/2;
        }
        cout<<ans<<endl;
    }
    return 0;
}

4.16 W

题意：给出一个长度为 $n$ 的数组 $a$ ，现在要让其变得非递减，每次可进行以下操作：选择 $a_i$ 与任一 $x$ ，使得 $1\leq x<a_i$ ，然后将 $a_i$ 替换成 $x$ 与 $a_i-x$ 。求最少操作次数。

倒序枚举，因为最后的数一定不会变。枚举到 $a_i$ 时与 $a_{i+1}$ 进行比较，若小于那么继续；若大于，考虑拆分 $a_i$ 。首先求出至少要拆成多少个数，即 $a_i\div a_{i+1}$ ，然后使所有数尽量平均分配即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[200005];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=0;
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]<=a[i+1])continue;

        if(a[i]%a[i+1]==0)ans+=a[i]/a[i+1]-1,a[i]=a[i+1];
        else
        {
            int t=a[i]/a[i+1];
            ans+=t;
            a[i]=a[i]/(t+1);
        }

    }
    cout<<ans<<endl;
}

signed main()
{
    int t;
    cin>>t;
    while(t--)solve();
}

4.17 X

题意：太麻烦了不想写。

构造题，但是好像构造出来的不如std简单，，，

只有当 $k$ 很小或是奇数时无解。假设首先将第一排走完，往下来到点 $(2,m)$ ，此时若向左走一步，那么就会浪费两步，以此类推，每向左走一步就浪费两步。那么可以在这一个圈内将多余的步数走完再不绕路地走向终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;

int row[20][20];
int col[20][20];

void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=20;i++)
        for(int j=1;j<=20;j++)row[i][j]=0,col[i][j]=0;

    if((k-n-m+2)%2==1 || k<n+m-2)
    {
        cout<<"NO\n";
        return ;
    }
    cout<<"YES\n";
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<m;j++)
        {
            row[i][j]=j%2;
        }
    }
    col[1][1]=0,col[1][m]=m%2;

    int d=k-(n+m-2);
    int br=d%(2*m);
    int step=br/2;


    if(step==0)
    {
        int st=col[1][m];
        for(int i=2;i<n;i++)
        {
            st^=1;
            col[i][m]=st;
        }
    }
    else
    {
        int st=row[1][m-step];
        for(int i=2;i<n;i++)
        {
            st^=1;
            col[i][m-step]=st;
        }
        st=col[n-1][m-step];
        for(int i=m-step;i<m;i++)
        {
            st^=1;
            row[n][i]=st;
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            if(row[i][j]==1)cout<<"R ";
            else cout<<"B ";
        }
        cout<<endl;
    }

    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(col[i][j]==1)cout<<"R ";
            else cout<<"B ";
        }
        cout<<endl;
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

4.18 Y

题意：给出长为 $n$ 的两个数组 $a,b$ ，给出常数 $k$ ，要求将数组 $b$ 重新排列，使得 $a_i>b_i$ 的数量是 $k$ 。

首先将 $a$ 按降序排列，$b$ 升序排列，考虑贪心：

  1. 将 $b$ 前 $k$ 小的元素分配给 $a$ 的前 $k$ 大的元素，将 $b$ 以后的元素分配给 $a$ 的以后的元素。
  2. 两段分配时一定是大的匹配大的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;

struct ppp
{
    int val;
    int id;
}a[200005],b[200005];

int n,k;

bool cmp1(ppp x,ppp y)
{
    return x.val>y.val;
}

bool cmp2(ppp x,ppp y)
{
    return x.val<y.val;
}

bool cmp3(ppp x,ppp y)
{
    return x.id<y.id;
}

void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].val;
        a[i].id=i;
    }
    for(int i=1;i<=n;i++)cin>>b[i].val;
    sort(a+1,a+n+1,cmp1);//倒序
    sort(b+1,b+n+1,cmp2);//顺序

    for(int i=1;i<=k;i++)
    {
        if(b[k-i+1].val>=a[i].val)
        {
            cout<<"NO\n";
            return ;
        }
        b[k-i+1].id=a[i].id;
    }

    for(int i=1;i<=n-k;i++)
    {
        if(b[n-i+1].val<a[i+k].val)
        {
            cout<<"NO\n";
            return ;
        }
        b[n-i+1].id=a[i+k].id;
    }
    sort(b+1,b+n+1,cmp3);
    cout<<"YES\n";
    for(int i=1;i<=n;i++)cout<<b[i].val<<" ";cout<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

4.22 Z

题意：给出一个长度为 $n$ 的数组 $a$ ，只包含1和2，然后给出 $q$ 次询问，每次询问如下：

  1. $1\ s$ ：判断是否存在一个连续子序列的和为 $s$ 。
  2. $2\ i\ v$ ：将 $a[i]$ 替换为 $v$ 。

注意到若某一 $sum$ 可以得到，那么 $sum-2$ 一定可以得到。所以根据 $s$ 分类讨论：

  1. 若 $(sum-s)%2=0$ ，那么一定可行。
  2. 若 $(sum-s)%2=1$ ，找到最前面和最后面的两个1，分别以两个1为起点和终点判断。目的是为了使 $s$ 能够由某一个 $s$ 不断-2得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;


int a[100005];

void solve()
{
    int n,q;
    cin>>n>>q;
    set<int >pos;

    int tot=0;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        tot+=a[i];
        if(a[i]==1)pos.insert(i);
    }

    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int sum;
            cin>>sum;
            if(sum>tot)
            {
                cout<<"NO\n";
                continue;
            }

            if((tot-sum)%2==0)
            {
                cout<<"YES\n";
                continue;
            }

            if(pos.size()==0)
            {
                cout<<"NO\n";continue;
            }

            int s1=tot-(*pos.begin()-1)*2;
            int s2=tot-(n-*pos.rbegin())*2;
            // cout<<*pos.begin()<<" "<<*pos.rbegin()<<endl;
            // cout<<s1<<" "<<s2<<endl;
            if(sum<=max(s1,s2))cout<<"YES\n";
            else cout<<"NO\n";
        }
        else
        {
            int id,v;
            cin>>id>>v;
            tot=tot-a[id]+v;
            if(a[id]==1)pos.erase(pos.find(id));
            a[id]=v;
            if(v==1)pos.insert(id);
            
        }
        
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}