A. Tales of a Sort

题意

给定一个序列 {an}\{a_n\}。

现在每次操作为 ∀i,ai←max⁡(0,ai−1)\forall i, a_i\leftarrow \max(0,a_i-1)。
求进行多少次操作后序列变为有序？

解法

进行模拟，每次遇到一个逆序的就不断进行操作直到这个逆序被消除。

复杂度 O(n2)O(n^2)（可优化至 O(n)O(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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 55;
int a[N];
void solve(int kase){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }

    ll ans = 0;
    for(int i=1;i<n;i++){
        if(a[i]>a[i+1]){
            ans += a[i];
            int k = a[i];
            for(int j=1;j<=n;j++){
                a[j]=max(0,a[j]-k);
            }
        }
    }

    printf("%lld\n",ans);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Good Arrays

题意

给定序列 {an}\{a_n\}，请问是否存在序列 {bn}\{b_n\}，使得 ∑ai=∑bi\sum a_i = \sum b_i 并且 ∀i,ai≠bi,bi>0\forall i, a_i\ne b_i,b_i>0。

解法

假设有 pp 个数为 11，剩下 n−pn-p 个数不为 11，它们的和为 sumsum。

我们给出一个充要条件。当且仅当 p≤sum−(n−p)p\le sum-(n-p) 时存在。

证明：

  1. p>sum−(n−p)p>sum-(n-p)
    此时 pp 个 11 至少要变为 22，需要后面的数分出来 pp，但是后面的数最多只能分出来 sum−(n−p)sum-(n-p)，所以一定无解。
  2. p≤sum−(n−p)p\le sum-(n-p)
    令后面的 n−pn-p 个数每一个都少一，前面的 pp 个数每一个都加 11，剩下差的全部加给第一个数。这是一个合法方案。
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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int n=read();
    vector<int> v;
    for(int i=0;i<n;i++){
        v.push_back(read());
    }

    if(n==1){
        NO;
        return;
    }

    sort(all(v));
    int cnt = 0;
    ll sum=0;
    for(int i=0;i<n;i++){
        if(v[i]!=1)sum+=v[i]-1;
        else cnt ++;
    }

    if(sum>=cnt)YES;
    else NO;
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. To Become Max

题意

给定序列 {an}\{a_n\} 和 kk。

你最多可以进行 kk 次如下操作：
选定 ai<ai+1a_i<a_{i+1} 的一个 ii，然后给 aia_i 加上 11。

请问序列的最大值最多是多少？

解法

二分答案。考虑如何判断能否达到 xx。

若一个位置是 xx，那后面至少是 x1,x−2,…x_1,x-2,\ldots，因此我们可以枚举所有的位置，判断能否让这个位置达到 xx。

复杂度 O(n2log⁡M)O(n^2\log 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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1005;
int a[N];
ll s[N];
int n,k;

bool check(int x){
    for(int i=1;i<=n;i++){
        int lst = k;
        for(int j=i;j<=n;j++){
            int need = (x-(j-i))-a[j];
            if(need<=0)return true;

            if(lst>=need)lst-=need;
            else break;
        }
    }
    return false;
}

void solve(int kase){
    n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        s[i]=s[i-1]+a[i];
    }
    a[n+1]=-1e8;

    ll l=0,r=2e8;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }

    printf("%lld\n",l);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. More Wrong

题意

交互题。

给定一个 1∼n1\sim n 的排列。每次你可以询问一段连续区间 $[l,r] $内的逆序对个数，每次询问的花费为 (r−l)2(r-l)^2，请在不超过花费 5n25n^2 的情况下，找出排列中最大数 nn 的所在位置。

解法

考虑分治。

设 f(l,r)f(l,r) 为 [l,r][l,r] 中最大值的位置。

当区间长度为 11 时，直接返回 ll。
当区间长度为 22 时，询问一次 [l,r][l,r] 内的逆序对，得到最大值。

当区间长度大于等于 22 时，先求出左区间和右区间的最大值。然后我们考虑到底哪个才是真正的最大值。
我们用到这个结论：若 [l,r][l,r] 和 [l,r−1][l,r-1] 内逆序对个数相同，那么 ara_r 是 [l,r][l,r] 内的最大值，询问两次得到哪个才是最大值。

这个的花费是够的。（证明略）

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<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int query(int l,int r){
    if(l==r)return l;
    if(r==l+1){
        printf("? %d %d\n",l,r);fflush(stdout);
        int x=read();
        if(x==1)return l;
        return r;
    }

    int mid = (l+r)>>1;
    int lmax = query(l,mid);
    int rmax = query(mid+1,r);
    printf("? %d %d\n",lmax,rmax);fflush(stdout);
    int x1=read();
    int x2;
    if(lmax!=rmax-1){
        printf("? %d %d\n",lmax,rmax-1);fflush(stdout);
        x2=read();
    }
    else x2=0;
    if(x1==x2)return rmax;
    return lmax;
}


void solve(int kase){
    int n=read();
    printf("! %d\n",query(1,n));fflush(stdout);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

E1. PermuTree (easy version)

题意

有一个根为 11 的树。请你给 1∼n1\sim n 的每个节点赋一个 1∼n1\sim n 的互不重复的权值，使得令 au<alca⁡(u,v)<ava_u<a_{\operatorname{lca}(u,v)}<a_v 的 (u,v)(u,v) 数量最多，并求出这个数量。

解法

考虑对每个节点单独判断。这是因为内部的大小和外部是没有关系的。无论是什么样的大小关系，都可以构造出合法的。

那么这个节点的值就是子结点中比它小的乘上子节点中比它大的。可以证明子节点的子树中一定要么比根节点小要么比根节点大。
于是可以进行一次背包求出最大值，复杂度 O(n2)O(n^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;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 5005;
vector<int> G[N];
int sz[N];

ll ans;

void dfs(int u,int f){
    sz[u]=1;
    vector<int> s;
    int sum = 0;
    

    for(int v:G[u]){
        if(v==f)continue;
        dfs(v,u);
        sz[u]+=sz[v];
        s.push_back(sz[v]);
        sum += sz[v];
    }

    if(s.size()<2)return;
    bitset<5005> dp;
    dp[0]=1;
    for(auto p:s){
        dp |= dp<<p;
    }

    ll v = 0;
    for(int i=0;i<sum;i++){
        if(dp[i]){
            v=max(v,(ll)i*(sum-i));
        }
    }
    ans += v;
}

int main(){
    int n=read();
    ans = 0;
    for(int i=1;i<=n;i++)G[i].clear();

    for(int i=2;i<=n;i++){
        int x=read();
        G[i].push_back(x);
        G[x].push_back(i);
    }

    dfs(1,1);

    printf("%lld\n",ans);
    return 0;
}