UESTC 2023 Summer Training

雄关漫道真如铁，而今迈步从头越。

Day1

### E. Jewel of Data Structure Problems

题意

定义一个数组是奇的当且仅当它的逆序对数为奇数。定义一个排列的美丽度为它的最长奇子序列的长度，如果不存在则为 −1-1。给出一个排列 pp 和 qq 次更新，每次更新交换排列中两个数的位置。要求输出每次更新后 pp 的美丽度。

题解

用到了一些关于逆序对的性质。

首先，如果 pp 是奇的，那么答案就是 nn。我们可以求出 pp 初始的逆序对数，每次交换会改变它的奇偶性。

其次，我们记包含 pip_i 的逆序对数量为 cic_i。如果有一个 cic_i 为奇数，那么除去 pip_i 的子序列是奇的，答案就是 n−1n-1。为了求出 cic_i，我们要用到一个结论：cic_i 为偶数当且仅当 pi mod 2=i mod 2p_i\bmod 2=i\bmod 2。

否则，我们考虑一对逆序对 (pi,pj)(p_i,p_j)。将它们除去后的子序列逆序对数必然是奇的，答案为 n−2n-2。

最后，如果 pp 不存在逆序对，那么答案就是 −1-1。

所以我们维护 pp 的逆序对的奇偶性，满足 pi mod 2=i mod 2p_i\bmod 2=i\bmod 2 的 ii 的个数，满足 pi=ip_i=i 的 ii 的个数，按照上面的流程依次检验就可以了。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int p[maxn];
bool vis[maxn];
vector<int> g[maxn];
void dfs(int u)
{
    vis[u]=1;
    for(auto v:g[u]) 
        if(!vis[v]) dfs(v);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++) 
    {
        cin>>p[i];
        g[i].push_back(p[i]);
    }
    int ans=n&1,cnt1=0,cnt2=0;
    for(int i=1;i<=n;i++)
        if(!vis[i]) dfs(i),ans^=1;
    for(int i=1;i<=n;i++)
    {
        if(p[i]==i) cnt1++;
        if(p[i]%2==i%2) cnt2++;
    }
    while(q--)
    {
        int x,y;cin>>x>>y;
        ans^=1;
        if(p[x]==x) cnt1--;
        if(p[y]==y) cnt1--;
        if(p[x]%2==x%2) cnt2--;
        if(p[y]%2==y%2) cnt2--;
        swap(p[x],p[y]);
        if(p[x]==x) cnt1++;
        if(p[y]==y) cnt1++;
        if(p[x]%2==x%2) cnt2++;
        if(p[y]%2==y%2) cnt2++;
        if(ans) cout<<n<<'\n';
        else if(cnt2!=n) cout<<n-1<<'\n';
        else if(cnt1!=n) cout<<n-2<<'\n';
        else cout<<-1<<'\n';
    }
    return 0;
}

Day2

C. Lucky Array

题意

定义只含有 44 和 77 的数字为幸运数字。给出一个数组 aa，给定两种操作。

  1. 将区间 [l,r][l,r] 内的所有 aia_i 加上一个正数 dd。
  2. 查询区间 [l,r][l,r] 内的所有幸运数字。

保证任意时刻 ai≤10000a_i\leq 10000。

题解

一道线段树的好题。

本题的突破口在于 1000010000 以内的幸运数字只有 3030 个，且数字只会变大不会减小。所以我们可以记录下每个数字与比它大的幸运数字的差值，维护区间最小值和区间最小值的数量。在区间查询时，如果最小值为 00 就说明存在幸运数字。在区间修改时，如果一个区间的最小值为负数，说明区间有某些数已经超过了此前对应的幸运数字，需要更换对应的幸运数字，直接暴力更新。

代码

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=1e5+5;
int mp[]={4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777,114514};
int a[maxn],b[maxn],mn[4*maxn],cnt[4*maxn],tag[4*maxn];
void pushup(int p)
{
	mn[p]=min(mn[p*2],mn[p*2+1]);
    if(mn[p*2]<mn[p*2+1]) cnt[p]=cnt[p*2];
    else if(mn[p*2]>mn[p*2+1]) cnt[p]=cnt[p*2+1];
    else cnt[p]=cnt[p*2]+cnt[p*2+1];
}
void pushdown(int p)
{
    mn[p*2]-=tag[p],mn[p*2+1]-=tag[p];
    tag[p*2]+=tag[p],tag[p*2+1]+=tag[p];
    tag[p]=0;   
}
void build(int l,int r,int p)
{
	if(l==r) 
    {
        for(int i=0;i<=30;i++)
        {
            if(mp[i]>=a[l])
            {
                mn[p]=mp[i]-a[l];
                b[l]=i;
                break;
            }
        }
        cnt[p]=1;
        return;
    }
	int m=l+((r-l)>>1);
	build(l,m,p*2),build(m+1,r,p*2+1);
    pushup(p);
}
void rebuild(int l,int r,int p)
{
    if(mn[p]>=0) return;
    if(l==r)
    {
        int cur=mp[b[l]]-mn[p];
        for(int i=b[l]+1;i<=30;i++)
        {
            if(mp[i]>=cur)
            {
                mn[p]=mp[i]-cur;
                b[l]=i;
                break;
            }            
        }
        return;
    }
    int m=l+((r-l)>>1);
    pushdown(p);
    rebuild(l,m,p*2),rebuild(m+1,r,p*2+1);
    pushup(p);
}
void update(int ul,int ur,int k,int l,int r,int p)
{
	if(ul<=l&&ur>=r)
    {
        mn[p]-=k,tag[p]+=k;
        if(mn[p]<0) rebuild(l,r,p);
        return ;
    }
    int m=l+((r-l)>>1);
    if(tag[p]&&l!=r) pushdown(p);
    if(ul<=m) update(ul,ur,k,l,m,p*2);
    if(ur>m) update(ul,ur,k,m+1,r,p*2+1);
    pushup(p);
}
pii query(int ql,int qr,int l,int r,int p)
{
    if(ql<=l&&qr>=r) return {mn[p],cnt[p]};
    int m=l+((r-l)>>1);
    if(tag[p]&&l!=r) pushdown(p);
    pii ans1={-1,-1},ans2={-1,-1};
	if(ql<=m) ans1=query(ql,qr,l,m,p*2);
	if(qr>m) ans2=query(ql,qr,m+1,r,p*2+1);
    pii ans;
    if(ans1.first==-1) ans=ans2;
    else if(ans2.first==-1) ans=ans1; 
    else
    {
        if(ans1.first<ans2.first) ans=ans1;
        else if(ans1.first>ans2.first) ans=ans2;
        else ans={ans1.first,ans1.second+ans2.second};
    }  
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        string op;cin>>op;
        if(op=="count")
        {
            int l,r;cin>>l>>r;
            pii ans=query(l,r,1,n,1);
            if(ans.first>0) cout<<0<<'\n';
            else cout<<ans.second<<'\n';
        }
        else
        {
            int l,r,k;cin>>l>>r>>k;
            update(l,r,k,1,n,1);
        }
    }
    return 0;
}

G. Sum Over Zero

题意

将数组 aa 划分成尽可能多的不相交子段，且每个子段和都非负。

题解

树状数组优化dp。

记 fif_i 为前 ii 个位置能划分的最大子段数量，ss 为 aa 的前缀和。那么显然有转移方程

fi=max⁡(fi−1,max⁡si≥sj,j<i{fj+i−j})f_i=\max(f_{i-1},\max_{s_i\geq s_j,j<i}\{f_j+i-j\})

容易想到记录下 fj−jf_j-j，但这里的精妙之处在于，我们不按下标插入，而是按 sjs_j 的值插入。这样，每次我们查询小于等于 sis_i 的最大的 fj−jf_j-j 即可。可以将值域离散化后用树状数组实现。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int len,a[maxn],f[maxn];
ll sum[maxn],b[maxn];
int rk(ll x) {return lower_bound(b,b+len,x)-b+1;}
int c[maxn];
int lowbit(int x) {return x&-x;}
void insert(int x,int k)
{
    while(x<=len)
    {
        c[x]=max(c[x],k);
        x+=lowbit(x);
    }
}
int query(int x)
{
    int ans=-0x3f3f3f3f;
    while(x)
    {
        ans=max(ans,c[x]);
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i],b[i]=sum[i];
    sort(b,b+n+1);
    len=unique(b,b+n+1)-b;
    memset(c,-0x3f,sizeof(c));
    insert(rk(0),0);
    for(int i=1;i<=n;i++)
    {
        f[i]=max(f[i-1],query(rk(sum[i]))+i);
        insert(rk(sum[i]),f[i]-i);
    }
    cout<<f[n]<<'\n';
    return 0;
}

Day3

C. Destruction of a Tree

题意

给定一棵树，每次可以删掉一个度数为偶数的点和与它相连的边。判断是否可以将所有点删除，并给出方案。

题解

首先可以肯定，当结点个数为偶数时肯定不行。因为每次删除偶数条边，最后一定会有剩余。

但是，此时也不能挑选度数为偶数的结点直接删。因为将原树划分为若干棵子树后，可能有些子树的结点个数为偶数，就导致无解了。

考虑使用dp的方法：记 fi=0f_i=0 表示结点 ii 在父结点之前删除，fi=1f_i=1 则相反。可以得到转移方程：

fu=degu⊕{fv⊕1}v∈sonuf_u=deg_u\oplus \underset{v\in son_u}{\{f_v\oplus 1\}}

若 f1=1f_1=1 则无解。

输出时采用dfs，先遍历 fi=0f_i=0 的子结点，然后输出该结点，最后遍历 fi=1f_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
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
bool f[maxn];
vector<int> g[maxn];
void dfs0(int u,int fa)
{
    for(auto v:g[u])
    {
        if(v==fa) continue;
        dfs0(v,u);
        f[u]^=(f[v]^1);
    }
}
void dfs(int u,int fa)
{
    for(auto v:g[u])
        if(v!=fa&&!f[v]) dfs(v,u);
    cout<<u<<'\n';
    for(auto v:g[u])
        if(v!=fa&&f[v]) dfs(v,u);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        if(x) 
        {
            f[i]^=1,f[x]^=1;
            g[i].push_back(x),g[x].push_back(i);
        }
    }
    dfs0(1,0);
    if(f[1]) cout<<"NO"<<'\n';
    else
    {
        cout<<"YES"<<'\n';
        dfs(1,0);
    }
    return 0;
}

### D. Time to Raid Cowavans

题意

给出一个数组 aa。每次询问给定出发位置和步长，问从出发位置走到数组末尾所经过的元素和为多少。

题解

考虑根号分治。对于步长大于 n\sqrt{n} 的，可以直接暴力求解。对于步长小于 n\sqrt{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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B=600;
const int maxn=3e5+5;
int n,m,w[maxn];
ll ans[maxn];
vector<pair<int,int>> q[maxn];
vector<ll> v[B+5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;cin>>a>>b;
        q[b].push_back({a,i});
    }
    for(int b=1;b<=n;b++)
    {
        if(b>B)
        {
            for(auto _:q[b])
            {
                int a=_.first,id=_.second;
                ll sum=0;
                for(int i=a;i<=n;i+=b) sum+=w[i];
                ans[id]=sum;
            }
            continue;
        }
        for(int i=1;i<=b;i++)
        {
            ll sum=0;v[i].push_back(0);
            for(int k=i;k<=n;k+=b) 
            {
                sum+=w[k];
                v[i].push_back(sum);
            }
        }
        for(auto _:q[b])
        {
            int a=_.first,id=_.second;
            int st=(a-1)%b+1;
            ans[id]=v[st].back()-v[st][(a-st)/b];
        }
        for(int i=1;i<=b;i++) v[i].clear();
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

E. Report

题意

给出一个数组 aa。每次操作将区间 [1,r][1,r] 内的数升序或降序排列，要求输出最终的数组 aa。

题解

如果一个后执行操作的 rr 大于先执行操作的 rr，那么先执行的操作会被覆盖掉。去除掉那些被覆盖的操作后，应满足 rr 单调减少。

这时我们就可以直接进行模拟了。

题解

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e5+5;
int a[maxn],b[maxn];
stack<pii> stk;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k=1;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(m--)
    {
        int t,r;cin>>t>>r;
        k=max(k,r);
        while(!stk.empty()&&r>stk.top().second) stk.pop();
        stk.push({t,r});
    }
    for(int i=k+1;i<=n;i++) b[i]=a[i];
    sort(a+1,a+k+1);
    stack<pii> s;
    while(!stk.empty())
    {
        pii tmp=stk.top();stk.pop();
        s.push(tmp);
    }
    int p=1,q=k;
    while(!s.empty())
    {
        int t=s.top().first,r=s.top().second;s.pop();
        int l=s.empty()?1:s.top().second+1;
        if(t==1)
            for(int i=r;i>=l;i--) b[i]=a[q--];
        else
            for(int i=r;i>=l;i--) b[i]=a[p++];
    }
    for(int i=1;i<=n;i++) cout<<b[i]<<" \n"[i==n];
    return 0;
}

Day4

E. Imbalance Value of a Tree

题意

给定一棵树，每个点有点权 aia_i。记 I(i,j)I(i,j) 表示点 ii 到点 jj 路径上最大点权和最小点权的差值。求 ∑i=1n∑j=inI(i,j)\sum\limits_{i=1}^n\sum\limits_{j=i}^nI(i,j)。

题解

将最大值和最小值拆开考虑。我们考虑对于 aia_i，它会在多少条路径上成为最大值。这里有一个技巧，将点权转化为边权：令 (u,v)(u,v) 的边权为 max⁡(au,av)\max(a_u,a_v)。将边权从小到大排序后依次加入，利用并查集维护连通性。每条边的贡献为两侧连通块大小的乘积。最小值也是相同的道理。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int a[maxn];
struct edge
{
    int u,v,w;
}e1[2*maxn],e2[2*maxn];
int f[maxn],siz[maxn];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
bool cmp1(edge x,edge y) {return x.w<y.w;}
bool cmp2(edge x,edge y) {return x.w>y.w;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        e1[i]={u,v,max(a[u],a[v])},e2[i]={u,v,min(a[u],a[v])};
    }
    sort(e1+1,e1+n,cmp1),sort(e2+1,e2+n,cmp2);
    ll ans=0;
    for(int i=1;i<=n;i++) f[i]=i,siz[i]=1;
    for(int i=1;i<n;i++)
    {
        int u=find(e1[i].u),v=find(e1[i].v),w=e1[i].w;
        if(u==v) continue;
        ans+=1ll*siz[u]*siz[v]*w;
        f[u]=v,siz[v]+=siz[u];
    }
    for(int i=1;i<=n;i++) f[i]=i,siz[i]=1;
    for(int i=1;i<n;i++)
    {
        int u=find(e2[i].u),v=find(e2[i].v),w=e2[i].w;
        if(u==v) continue;
        ans-=1ll*siz[u]*siz[v]*w;
        f[u]=v,siz[v]+=siz[u];
    }
    cout<<ans<<'\n';
    return 0;
}

G. Hyper String

题意

给出 nn 个base串。给出字符串 tt 由 mm 个base串 i1,i2,⋯ ,imi_1,i_2,\cdots,i_m 拼接而成。再给出字符串 ss。求 ss 和 tt 的LCS的长度。

题解

状态设计很巧妙。

我们回忆一下一般的LCS该怎么做：记 fi,jf_{i,j} 表示串 ss 的前 ii 位和串 tt 的前 jj 位的LCS长度，有转移

fi,j=max⁡(fi−1,j,fi,j−1,fi−1,j−1+1[si=tj])f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+1[s_i=t_j])

但是这里串 ss 会很长，不能作为状态的一维，所以我们改变一下状态的设计。记 fi,jf_{i,j} 表示 ss 的前 ii 位，LCS长度为 jj 时，串 tt 最后一个匹配位置的最小值。那么转移时考虑 ss 的第 ii 位是否参与匹配，如果不匹配，那么就用 fi−1,jf_{i-1,j} 转移；如果匹配，就用串 tt 中 fi−1,j−1f_{i-1,j-1} 右侧 sis_i 首次出现的位置转移。为此，我们需要预处理出 nxt1i,j,knxt1_{i,j,k} 表示base串 ii 中位置 jj 右侧字符 kk 第一次出现的位置和 nxt2i,knxt2_{i,k} 表示串 tt 中第 ii 个串右侧字符 kk 第一次出现的位置。具体细节可以参考代码。

代码

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;
typedef pair<int,int> pii;
int a[2005];
vector<vector<int>> nxt1[2005];
pii nxt2[2005][26],f[2005][2005];
string base[2005],s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>base[i];
    int m;cin>>m;
    for(int i=1;i<=m;i++) cin>>a[i];
    cin>>s;
    for(int i=0;i<=n;i++)
    {
        int siz=(int)base[i].size();
        nxt1[i].resize(siz+1);
        for(int j=0;j<=siz;j++) nxt1[i][j].resize(26);
        if(i==0)
        {
            for(int j=0;j<=siz;j++)
                for(int k=0;k<26;k++) nxt1[i][j][k]=-1;
            continue;
        }
        for(int k=0;k<26;k++) nxt1[i][siz][k]=-1;
        for(int j=siz-1;j>=0;j--)
        {
            for(int k=0;k<26;k++) nxt1[i][j][k]=nxt1[i][j+1][k];
            nxt1[i][j][base[i][j]-'a']=j+1;
        }
    }
    for(int k=0;k<26;k++) nxt2[m][k]={-1,-1};
    for(int i=m-1;i>=0;i--)
    {
        for(int k=0;k<26;k++) 
        {
            nxt2[i][k]=nxt2[i+1][k];
            if(nxt1[a[i+1]][0][k]!=-1) nxt2[i][k]={i+1,nxt1[a[i+1]][0][k]};
        }
    }
    int k=(int)s.size();
    for(int i=0;i<=k;i++)
        for(int j=0;j<=k;j++) f[i][j]={-1,-1};
    for(int i=0;i<=k;i++) f[i][0]={0,0};
    for(int i=1;i<=k;i++)
        for(int j=1;j<=i;j++)
        {
            f[i][j]=f[i-1][j];
            int x=f[i-1][j-1].first,y=f[i-1][j-1].second;
            char ch=s[i-1];
            if(x==-1&&y==-1) continue;
            if(nxt1[a[x]][y][ch-'a']!=-1) 
            {
                if(f[i][j]==make_pair(-1,-1)) f[i][j]={x,nxt1[a[x]][y][ch-'a']};
                else f[i][j]=min(f[i][j],{x,nxt1[a[x]][y][ch-'a']});
            }
            else if(nxt2[x][ch-'a']!=make_pair(-1,-1)) 
            {
                if(f[i][j]==make_pair(-1,-1)) f[i][j]=nxt2[x][ch-'a'];
                else f[i][j]=min(f[i][j],nxt2[x][ch-'a']);
            }
        }
    int ans=0;
    for(int j=1;j<=k;j++)
        for(int i=1;i<=k;i++)
            if(f[i][j]!=make_pair(-1,-1)) ans=j;
    cout<<ans<<'\n';
    return 0;
}

Day5

C. Bombing buildings

题意

给定一个数组 hh。有两种类型的操作：

  • 将一个位置的数改为 00，代价为 xx。
  • 选择一个区间 [l,r][l,r]，满足 hrh_r 是 ll 右侧第一个不小于 hlh_l 的数，将这个区间内的数都改为 00，代价为 yy。

求将整个数组改为 00 的最小代价。

题解

状态的设计比较巧妙。

记 fl,rf_{l,r} 为将区间 [l,r][l,r] 内大于等于 hlh_l 的数改为 00 的代价。考虑转移：

  • 若 hr<hlh_r<h_l，则 fl,r=fl,r−1f_{l,r}=f_{l,r-1}
  • 若 hr≥hlh_r\geq h_l，则 fl,r=min⁡(fl,r−1+x,min⁡hm≤hr{fl,m−1+fm,r−1+y})f_{l,r}=\min(f_{l,r-1}+x,\min\limits_{h_m\leq h_r}\{f_{l,m-1}+f_{m,r-1}+y\})。其中前者对应对位置 rr 使用操作 11，后者对应枚举操作 22 的左端点，由于 ff 为清空区间内大于等于左端点的数的花费，所以这部分可以理解为先将该区间 [m,r−1][m,r-1] 内大于等于 hmh_m 的数清空，然后对区间 [m,r][m,r] 使用一次操作 22。

代码

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;
typedef long long ll;
int h[505];
ll f[505][505];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,x,y;cin>>n>>x>>y;
        for(int i=1;i<=n;i++) cin>>h[i];
        for(int len=2;len<=n+1;len++)
            for(int i=0;i<=n-len+1;i++)
            {
                int j=i+len-1;
                if(h[j]<h[i]) f[i][j]=f[i][j-1];
                else
                {
                    f[i][j]=f[i][j-1]+x;
                    for(int k=j-1;k>=i+1;k--)
                        if(h[k]<=h[j]) f[i][j]=min(f[i][j],f[i][k-1]+f[k][j-1]+y);
                }
            }
        cout<<f[0][n]<<'\n';
    }
    return 0;
}

G. No Arithmetic subsequence

题意

构造一个 n×nn\times n 的网格。网格内的数为 1∼n×n1\sim n\times n 的排列，且满足任意一行和任意一列中都不存在一个子序列构成等差数列。

题解

先考虑构造一个符合条件的 nn 的排列。首先，我们将数按奇偶分开，前半部分放奇数，后半部分放偶数。这样，等差子序列一定不会跨越这两部分。然后，在两部分采用相同的方法，分别递归处理。

代码

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;
typedef pair<int,int> pii;
pii a[505],b[505];
void solve(int l,int r)
{
    if(l==r) return;
    int p=l,q=r;
    for(int i=l;i<=r;i++)
    {
        if(a[i].second&1) b[p++]=a[i];
        else b[q--]=a[i];
    }
    for(int i=l;i<=r;i++) a[i]=b[i],a[i].second>>=1;
    solve(l,p-1),solve(q+1,r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) a[i].first=a[i].second=i;
        solve(1,n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cout<<(a[i].first-1)*n+a[j].first<<" \n"[j==n];
    }
    return 0;
}
ACM
#训练
UESTC 2023 Summer Training
https://je3ter.github.io/2023/07/10/ACM/UESTC 2023 Summer Training/
作者
Je3ter
发布于
2023年7月10日
许可协议