放假欠了好多，写点

有几个题写下来感觉还是蛮有意思的

可能还是写题太少题感没形成吧，经常找不到切入点，有些题其实并不复杂就是不知道用什么方法切进去

CF1633D Make Them Equal

link

题意

现有一个长度为nn的值全为11的数组aa。定义操作：
选择一个xx，任取aa中的一个元素aia_i，使其加上⌊aix⌋\lfloor \frac{a_i}{x} \rfloor（即令ai=ai+⌊aix⌋a_i=a_i+\lfloor \frac{a_i}{x}\rfloor）

给定长度为nn的数组b,cb,c，若通过上述操作使ai=bia_i=b_i，即可获得cic_i分

求kk次操作后最大的分

n≤103,bi≤103,k≤106n\le10^3,b_i\le 10^3,k\le 10^6

解法

显然想要让aia_i从11变成小于10001000的某个数所需操作数是一定的。可以dpdp预处理出从11加到不大于10001000的所有整数jj最少需要多少次操作djd_j，问题转换成背包问题，物品价值为cic_i，体积为dbid_{b_i}，背包空间为kk，复杂度为O(nk)O(nk)，仍然过大

注意到对j≤1000j\le 1000，有dj≤12d_j\le 12，因此枚举背包空间时只需枚举到min(k,12n)min(k,12n)

复杂度O(n2)O(n^2)

Code

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 <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=1000+100;
int T;
int n,K;
int d[1000+1];
int b[maxn],c[maxn];
int dp[maxn*12];

void Work()
{
    read(n),read(K);
    for(int i=1;i<=n;++i)
        read(b[i]);
    for(int i=1;i<=n;++i)
        read(c[i]);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;++i)
    {
        for(int j=min(12*n,K);j-d[b[i]]>=0;--j)
            dp[j]=max(dp[j],dp[j-d[b[i]]]+c[i]);
    }
    printf("%d\n",dp[min(12*n,K)]);
}

void pre()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    for(int i=1;i<=1000;++i)
    {
        for(int j=1;j<=i;++j)
        {
            if(i+i/j>1000)
                continue;
            d[i+i/j]=min(d[i+i/j],d[i]+1);
        }
    }
}

int main()
{
    pre();
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

CF1638B Odd Swap Sort

link

题意

给定长度为nn序列，对序列元素可做如下操作：
任取1≤i≤n1\le i \le n，若ai+ai+1a_i+a_{i+1}为奇数则可以交换它们的位置，否则不允许

问序列是否能通过若干次上述操作变为单调不减

n≤2⋅105n\le 2\cdot10^5

解法

留意到可以交换的两数奇偶性不同，考虑极端情况：全为奇数或偶数，此时无法进行任何操作，若初始序列非单调不减则答案为否

显然，在同时包含奇数和偶数的序列中，若奇子序列和偶子序列至少有一个非单调不减，则答案亦为否，因为在操作过程中必然需要交换两个奇偶性相同的数

复杂度O(n)O(n)

code

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
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define lb(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=100000+100;
int T;
int n;

void Work()
{
    read(n);
    int o=-1,e=0;
    int flag=0;
    for(int i=1;i<=n;++i)
    {
        int x;
        read(x);
        if(x&1)
        {
            if(x<o)
                flag=1;
            o=x;
        }
        else
        {
            if(x<e)
                flag=1;
            e=x;
        }
    }
    if(flag)
        puts("No");
    else
        puts("Yes");
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

CF1638C Inversion Graph

link

题意

给定排列，排列中的每个逆序对之间连一条无向边，问在排列中有多少个连通块

n≤105,∑n≤2⋅105n\le10^5,\sum n\le 2\cdot 10^5

解法

因为是排列，从里面挑一个子序列出来离散化一下还是一个排列。所以排列相关的题目里经常能见到向当前排列中一个个加入元素考察影响的思路

之前见过的题里处理排列元素的顺序除了有从左往右扫的，也有按照元素大小从小到大做的，不过后者一般跟计数的关系更大一些

从左往右扫，考察向当前前缀插入一个新数字对前缀造成的影响

注意到每个连通块都是序列中连续的一串我没注意到，可以证明该性质对所有排列成立

考察插入过程，假设当前前缀为p1...kp_{1...k}，插入pk+1p_{k+1}后，若其与pi(1≤i≤k)p_i(1\le i\le k)连通，则其必与pi...kp_{i...k}处于同一连通块中。因为pi>pk+1p_i>p_{k+1}，对任意i<j<k+1i<j<k+1，若有pj>pk+1p_j>p_{k+1}，则pjp_j与pk+1p_{k+1}连通，否则pip_i与pjp_j连通，进而与pk+1p_{k+1}连通。

考察插入过程，在上述分析中还发现插入一个新的元素可能会使当前存在的连通块发生合并。
对于两个相邻的连通块，显然若后一个块中最小的元素比前一个块中最大的元素小时，这两个块发生合并。
显然插入的元素最先影响到靠后的连通块，我们可以从后往前考虑插入元素如何使当前存在的连通块发生合并——用栈维护这些连通块。

使用pair维护每个块的最小值和最大值并保存在栈中。插入新元素时，可以将其视为一个单独的块入栈，然后从栈顶开始不断向下进行合并。

答案即为站中元素个数。

复杂度O(n)O(n)

Code

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 <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=100000+100;
int T;
int n;
int a[maxn];
pii stk[maxn];

void Work()
{
    read(n);
    for(int i=1;i<=n;++i)
        read(a[i]);
    int top=0;
    for(int i=1;i<=n;++i)
    {
        stk[++top]={a[i],a[i]};
        while(top>1 && stk[top].first < stk[top-1].second)
        {
            stk[top-1].second=max(stk[top-1].second,stk[top].second);
            stk[top-1].first=min(stk[top-1].first,stk[top].first);
            --top;
        }
    }
    printf("%d\n",top);
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

CF1644C Increase Subarray Sums

link

我是傻逼

题意

给定长度为nn的序列和常数xx，可以选择序列中若干个数让它们的值变大xx。问在选择增大0,1…n0,1\dots n个数的情况下，序列的最大子串和分别是多少。

n≤5000n\le 5000

x>0x>0

解法

利用求一般的最大子串和的思想（dpidp_i表示以aia_i为结尾的最大子串和，dpi=max{dpi−1+ai,ai}dp_i=max\{dp_i-1+a_i,a_i\}ans=max{dpi}ans=max\{dp_i\}），设状态dpi,jdp_{i,j}表示当前已增大了jj个数，以aia_i为结尾的最大子串和

转移方程

dpi,j=max{dpi−1,j+ai,ai,dpi−1,j−1+ai+x,ai+X}dp_{i,j}=max\{dp_{i-1,j}+a_i,a_i,dp_{i-1,j-1}+a_i+x,a_i+X\}

边界条件

dp0,0=0,dpi,0=max{dpi−1,0+ai,ai}dp_{0,0}=0,dp_{i,0}=max\{dp_{i-1,0}+a_i,a_i\}

增大kk个数时的答案为

max{dpi,k}max\{dp_{i,k}\}

复杂度O(n2)O(n^2)

Code

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 <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=5000+100;
int T;
int n,X;
int a[maxn];
int dp[maxn][maxn];

void Work()
{
    read(n),read(X);
    for(int i=1;i<=n;++i)
        read(a[i]);
    for(int i=0;i<=n;++i)
        for(int j=0;j<=n;++j)
            dp[i][j]=0;
    for(int i=1;i<=n;++i)
    {
        dp[i][0]=max(dp[i-1][0]+a[i],a[i]);
        for(int j=1;j<=n;++j)
        {
            dp[i][j]=max(max(dp[i-1][j]+a[i],a[i]),max(dp[i-1][j-1]+a[i]+X,a[i]+X));
        }
    }
    for(int i=0;i<=n;++i)
    {
        int ans=0;
        for(int j=1;j<=n;++j)
            ans=max(ans,dp[j][i]);
        printf("%d ",ans);
    }
    puts("");
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

CF1644D Cross Coloring

link

认真读题

题意

在大小为n×mn\times m和颜色数量kk，初始全为白色的棋盘上给定qq次涂色操作(xi,yi)(x_i,y_i)。对于第ii次操作，可以将第xix_i行和第yiy_i列涂成kk种颜色中的一种。

问棋盘最终可能有多少种不同的涂色情况，对大质数取模

n,m,k,q≤2⋅105n,m,k,q\le2\cdot 10^5

解法

最后会有一些格子是白色，它们对答案没有影响。

考虑每次操作对答案产生的贡献。如果一次操作中涂色的格子全部被以后的操作覆盖了，那么这次操作对答案是没有贡献的；否则，这些格子中未被覆盖的格子最后颜色一致，共有kk种可能。

对于一次操作，若以下条件满足任意一条：

  1. 行xix_i，列yiy_i均出现在了之后的操作中
  2. 以后的操作中所有行均被覆盖
  3. 以后的操作中所有列均被覆盖

则此次操作对答案没有贡献

对于涂色覆盖类问题，可以按染色从晚到早的顺序处理，以便于处理覆盖关系。

从后往前处理，只需要维护每一行、每一列是否被覆盖即可。若一次操作有贡献，对答案乘上kk

复杂度O(n+m)O(n+m)

Code

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
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const ll mod=998244353;
const int maxn=200000+100;
int T;
int n,m,K,q;
int X[maxn],Y[maxn];
int row[maxn],col[maxn];

void Work()
{
    read(n),read(m),read(K),read(q);
    for(int i=1;i<=q;++i)
    {
        read(X[i]);
        read(Y[i]);
    }
    for(int i=1;i<=n;++i)
        row[i]=0;
    for(int i=1;i<=m;++i)
        col[i]=0;
    ll ans=1;
    int rc=0,cc=0;
    for(int i=q;i;--i)
    {
        int x=X[i],y=Y[i];
        if(row[x] && col[y])
            continue;
        if(rc==n || cc==m)
            continue;
        rc+=(!row[x]);
        cc+=(!col[y]);
        row[x]=col[y]=1;
        ans=ans*K%mod;
    }
    printf("%lld\n",ans);
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

See also

CF1638D Big Brush