2022“杭电杯”中国大学生算法设计超级联赛（8）签到题5题

The first line contains an integer T (1≤T≤10) denoting the number of test cases.

Each test case consists of only one line containing a string s (|s|≤105).

Output
Output one line containing the lexicographically smallest string that you can get.

Sample Input
2
101001
01101100000000101010

Sample Output
001011
00000000001010101111

Hint
In the first test case, Jaina performs magic to the interval [3,5] and the string is changed to 100011. Then Jaina performs magic to the interval [1,3] and the string is changed to 001011.

Source
2022“杭电杯”中国大学生算法设计超级联赛（8）

题意：

• 给出一个 01 序列，每次操作可以任意翻转奇数长度的区间，求能达到的最小字典序。

思路：

• 只使用长度为 3 的翻转，那么位置奇偶性相同的位置可以随便换。
• 对奇数位置和偶数位置，分别把 0 放到前面、1 放到后面即可。

#include
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
char t[maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        string s;  cin>>s;
        int a = 0, b = 0, n = s.size();
        for(int i = 0; i < n; i++){
            if(s[i]=='1'){
                if(i%2==0)a++; //奇数位
                else b++;
            }
        }
        for(int i = n-1 ; i >= 0; i--){
            if(i%2==0){
                if(a>0){
                    t[i] = '1';
                    a--;
                }else{
                    t[i] = '0';
                }
            }else{
                if(b>0){
                    t[i] = '1';
                    b--;
                }else{
                    t[i] = '0';
                }
            }
        }
        t[n] = '\0';
        cout<<t<<"\n";
    }
    return 0;
}


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

11.Stormwind

Stormwind
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 60 Accepted Submission(s): 47

Problem Description
“So, people of Stormwind! Let us unite this day. Let us renew our promise to uphold and protect the Light, and together we will face down this dark new storm and stand firm against it—as humanity always has… and humanity always will!”

The crowd saved its greatest roars for the end. A chorus of “Long live King Varian! Long live King Varian!” rose into the sky with vigor and conviction. The cheers were unending, echoing deep into Elwynn Forest and faintly reaching even the distant peaks of the Redridge Mountains.

Varian Wrynn gained a rectangular piece of gold in the battle, with length n and width m. Now he wants to draw some lines on the gold, so that later he can cut the gold along the lines.

The lines he draws should satisfy the following requirements:

1. The endpoints of the lines should be on the boundary of the gold.
2. The lines should be parallel to at least one boundary of the gold.
3. After cutting along all the lines, each piece of gold is a rectangle with integer length and width.
4. After cutting along all the lines, the area of each piece of gold should be at least k.
5. Two lines should not share more than one common points.

Varian Wrynn wants to cut the gold in such a way that maximizes the lines he draws.

As Alliance’s Supreme King, he certainly doesn’t have time to do this. So he finds you! Please help him to cut the gold!

Input
The input consists of multiple test cases.

The first line contains an integer T (1≤T≤100) indicating the number of test cases.

Each test case consists of one line containing three integers n,m,k (1≤n,m,k≤105). Its guaranteed that n×m≥k.

Output
For each test case, output one line containing one integer, the maximum number of lines you can draw.

Sample Input
2
5 4 2
10 9 13

Sample Output
5
4

Hint
In the first test case, Varian Wrynn can draw 4 lines parallel to the boundary of length 4 and 1 line parrallel to the boundary of length 5. After cutting along the lines, he can get 10 pieces of gold of size 2.

Source
2022“杭电杯”中国大学生算法设计超级联赛（8）

题意：

• 一个 $n\ast m$ 的长方形，可以沿水平或竖直方向画若干条线，每条线的两端点都在长方形的边界上。
• 要求这些线划分出的每个小长方形面积都 $\ge k$，求最多可以画几条线。

思路：

• 枚举小长方形的某个边长的最小值，由此可以求出另一个边长允许的最小值，然后求出两个方向分别最多能画几条线。 时间复杂度 $O(k)$。

#include
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n, m, k;  cin>>n>>m>>k;
        int ans = 0;
        for(int x = 1; x <= k; x++){ //小正方形的长和宽(x*y)
            int y = (k+x-1)/x;       //y向上取整,确保x*y>=k
            if(x > n || y > m)continue;
            ans = max(ans, n/x+m/y-2);
        }
        cout<<ans<<"\n";
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 也可以直接分类讨论，先横着画或先竖着画，因为一条线是划到底的，所以根据k/n可以算出横着最多能画多少个，再根据左右两边剩余的面积分类后取max，复杂度 $O(1)$

#include
using namespace std;
int calc(int n, int m, int k){
    int ans = 0;
    int t = k/n;
    if(k%n!=0)t++;
    int tt = m-(m/t-1)*t;
    if(t+tt<=m){
        int h = k/t;
        if(k%t!=0)h++;
        int hh = n-(n/h-1)*h;
        if(h+hh<=n){
            ans = m/t+n/h-2;
        }else{
            ans = m/t-1;
        }
    }else{
        int h = k/tt;
        if(k%tt!=0)h++;
        int hh = n-(n/h-1)*h;
        if(h+hh<=n){
            ans = n/h-1;
        }else{
            ans = 0;
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n, m, k;  cin>>n>>m>>k;
        int ans = max(calc(n,m,k), calc(m,n,k));
        cout<<ans<<'\n';
    }
    return 0;
}


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

8.Orgrimmar

Orgrimmar
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 300 Accepted Submission(s): 134

Problem Description
"In my memory, the last time such a tragic farewell to a respected Horde leader was at the top of Thunder Bluff. That day, Mother Earth was crying for him too. "

"This time, it is the Shadow of the Horde who has left us. At this moment, the entire Horde is whispering affectionately for him. "

“Son of Sen’jin, leader of the Darkspear tribe, Warchief of the Horde - Vol’jin.”

Born in the cunning and vicious troll race, he spent his life explaining to the world what loyalty and faith are.

A dissociation set of an undirected graph is a set of vertices such that if we keep only the edges between these vertices, each vertex in the set is connected to at most one edge.

The size of a dissociation set is defined by the size of the set of vertices.

The maximal dissociation set of the graph is defined by the dissociation set of the graph with the maximum size.

Sylvanas has a connected undirected graph that has n vertex and n−1 edges, and she wants to find the size of the maximal dissociation set of the graph.

But since she just became the warchief of the Horde, she is too busy to solve the problem.

Please help her to do so.

Input
The input consists of multiple test cases.

The first line contains one integer T (1≤T≤10) denoting the number of test cases.

The following are T test cases.

For each test case, the first line contains one integer n (n≤500000), which is the number of vertices.

The following n−1 lines each contains two integers x and y denoting an edge between x and y.

It is guaranteed that the graph is connected.

Output
For each test case, output one line containing one integer indicating the answer.

Notes:
In this problem, you may need more stack space to pass this problem.
We suggest you to add the following code into your main function if you use C++.

int main() {
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
// YOUR CODE
...
exit(0);
}

1
2
3
4
5
6
7
8

And if you use the code above please DON’T forget to add exit(0); in the end of your main function, otherwise your code may get RE.

Sample Input
2
5
1 2
2 3
3 4
4 5
10
1 2
2 4
3 2
5 3
6 4
7 5
8 3
9 8
10 7

Sample Output
4
7

Source
2022“杭电杯”中国大学生算法设计超级联赛（8）

题意：

• 求一棵树的最大分离集的大小。
• 最大分离集指的是原图点集的一个子集，满足这个集合内的点互相之间最多只有一条边（即要么是孤点，要么是只有两个点相连的离散状态）。

思路：

• 可以贪心的考虑一个点是否去掉，对于倒数第二层的点来说，如果叶子节点的个数>=2的话，肯定要将它去掉，不然分离集的大小就会少了那么多的叶子，得不偿失。 而当叶子个数=1的时候，去掉当前点的父节点明显是更优的，因为其余的点更能够和其他点构成分离集。
• 因此确定了去点的策略，可以直接dfs，返回值维护当前节点是否去掉，若一个点的儿子的节点的个数>1，那么就去掉这个点，答案+1即可。如果>=2，那么就去掉这个点的父节点。 最后输出n-ans。

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 500010;

vector<int>G[maxn];
int ans = 0;
int dfs(int u, int f){
    int x = 0, y = -1;
    for(int v : G[u]){
        if(v==f)continue;
        x += dfs(v,u); 
        if(x>1 && y==-1)y = 0, ans++;
    }
    if(y==0)return 0;
    return x+1;
}

int main(){
    int size(512<<20);  // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    IOS;
    int T;  cin>>T;
    while(T--){
        int n;   cin>>n;
        for(int i = 0; i <= n; i++)G[i].clear();
        ans = 0;
        for(int i = 1; i < n; i++){
            int u, v;  cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1,-1);
        cout<<n-ans<<'\n';
    }
    exit(0);
    return 0;
}


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

• 令$dp[x][0],dp[x][1],dp[x][2]$ 分别表示仅考虑x这个子树，x号点未选，x号点选择了但是度数为0，x号点选了且度数为1的选且x子树内部满足分离集定义选择点数的最大值。

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 500010;

//分别表示x号点未选，x号点选了且度数0，x号点选了且度数1。x子树内部满足分离集定义的，选择点数的最大值
vector<int>G[maxn];
int f[maxn][3]; 
int dfs(int u, int fa){
    f[u][0] = 0;  f[u][1] = f[u][2] = 1;
    for(int v : G[u]){
        if(v==fa)continue;
        dfs(v, u);
        f[u][0] += max({f[v][0], f[v][1], f[v][2]}); //x不选,与子树不冲突,随便加
        f[u][2] += f[v][0];                          //x选了,且有父亲边, 因此子树不能选
        f[u][2] = max(f[u][2], f[u][1]+f[v][1]);     //x选了,且有儿子边，与之取max
        f[u][1] += f[v][0];                          //x选了,孤点,加上儿子的最大集数量
        f[u][2] = max(f[u][2], f[u][1]);             //x选了,有边,与无边取个max
    }
}

int main(){
    int size(512<<20);  // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    IOS;
    int T;  cin>>T;
    while(T--){
        int n;   cin>>n;
        for(int i = 0; i <= n; i++){ G[i].clear(); f[i][0]=f[i][1]=f[i][2]=0;}
        for(int i = 1; i < n; i++){
            int u, v;  cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1,-1);
        cout<<max({f[1][0], f[1][1], f[1][2]})<<"\n";
    }
    exit(0);
    return 0;
}


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

7.Darnassus

Darnassus
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1632 Accepted Submission(s): 341

Problem Description
Even the World Tree must bow to the cycle of life. Everything born will die.

Archimonde has hurt it once, Sylvanas burnt it again.

Now the World Tree is slowly recovering.

The World Tree is burnt apart into n parts. Now it tries to rebuild itself.

Each part of the World Tree has an attribute pi, and all pi (1≤i≤n) forms a permutation of 1,2,3…n.

For all 1≤i

The World Tree is very smart, so it will grow some edges such that all its n parts become connected (in other words, you can go from any part to any other part using only the edges that have been grown), spending the minimum energy.

Please calculate the minimum energy the World Tree needs to spend.

Input
The input consists of multiple test cases.

The first line contains an integer T (1≤T≤5) denoting the number of test cases.

For each test case, the first line contains a single integer n(1≤n≤50000).

The second line contains n integers pi (1≤pi≤n), it’s guaranteed that all pi forms a permutation.

Output
For each test case, output one line containing one integer indicating the answer.

Sample Input
2
5
4 3 5 1 2
10
4 7 3 8 6 1 9 10 5 2

Sample Output
7
24

Source
2022“杭电杯”中国大学生算法设计超级联赛（8）

题意：

• 给出一个长为n的排列 $p$，把每个位置视为点，建一个无向图，$i,j$ 之间的边权为 $|i-j|\ast |p_i-p_j|$。求这个图的最小生成树。

思路：

• 依次连接 $i,i+1(1\le i<n)$，这样的生成树每条边边权都 $\le n-1$，因此存在一种最小生成树中也只有边权 $\le n-1$ 的边（Kruskal 算法的原理）。
• $|i-j|\ast |p_i-p_j|\le n-1$ 意味着 $|i-j|$ 和 $|p_i-p_j|$ 必有至少一个 $\le \sqrt{n-1}$，因此可以在 $O(n\sqrt{n})$ 的时间复杂度内找到所有这样的边，然后使用 Kruskal 算法求出最小生成树即可。
• 总时间复杂度 $o(n\sqrt{n}\alpha (n))$。

#include
using namespace std;
typedef long long LL;
const int maxn = 50010;

int readint(){
    int x=0, op=1;  char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch=='-')op=-1; ch = getchar(); }
    while(ch >= '0' && ch <= '9'){ x=x*10+ch-'0'; ch = getchar(); }
    return x*op;
}

int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

int p[maxn], pos[maxn];
struct edge{ int u, v; };
vector<edge>e[maxn];

int main(){
    int T = readint();
    while(T--){
        int n = readint();
        init(n+1);
        for(int i = 1; i <= n; i++){
            p[i] = readint();  pos[p[i]] = i;  e[i].clear();
        }
        int m = min(100,(int)sqrt(n)); //优化
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j-i<=m && j<=n; j++){     //j-i<=sqrt(n-1)
            	//i,j之间至少有一条<=n-1的边，因此i-j或pi-pj至少一个<=sqrt(n-1)
                int tmp = (j-i)*abs(p[j]-p[i]);        //任意两个点(i,j为点,i-j)间有一条边
                if(tmp <= n-1)e[tmp].push_back({i,j}); //边权<=n-1
                tmp = (j-i)*abs(pos[j]-pos[i]);        //任意两个权值(i,j为权值,pi-pj)间也有一条边
                if(tmp <= n-1)e[tmp].push_back({pos[i],pos[j]});
            }
        }
        LL ans = 0;
        int cnt = n-1;
        for(int i = 1; i <= n; i++){                  //按边权桶排
            for(int j = 0; j < e[i].size(); j++){     //Kruskal求最小生成树
                int u = find(e[i][j].u), v = find(e[i][j].v);
                if(u != v){
                    merge(e[i][j].u, e[i][j].v);
                    cnt--;
                    ans += i;
                }
                if(cnt==0)break;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}


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