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

#include
using namespace std;
const int maxn = 5e5+10;
vector<int>G[maxn];
long long siz[maxn];
long long res = 0;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)

void dfs(int u , int fa){
    siz[u]++;
    for(int v : G[u]){
        if(v==fa)continue;
        dfs(v,u);
        siz[u] += siz[v];
    }
    return ;
}
void dfs2(int u, int fa, long long ans){
    res = max(res, ans);
    for(int v : G[u]){
        if(v==fa)continue;
        dfs2(v, u, ans+siz[u]);
    }
}

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        for(int i = 0; i <= n; i++){
            G[i].clear();
            siz[i] = 0;
        }
        for(int i = 1; i < n ;i++){
            int u, v;  cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        res = 0;
        dfs(1,0);
        dfs2(1,0,0);
        cout<<res+1<<"\n";//叶节点0没有子节点，但是有非负值1，最后加上
    }
    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

∘ For each i (1≤i

• 1
• 2
• 3
• 4
• 5
• 6
• 7

Find the lexicographically largest possible array after k times operations.

Array x is lexicographically greater than array y if there exists an index i ( 1≤i≤n ) such that xi > yi and for every j(1≤j

Input
The first line of the input contains one integer T (1≤T≤100 ) — the number of test cases. Then T test cases follow.

The first line of the test case contains two integers n,k (1≤n,k≤300000)

The second line of the test case contains n integers a1,a2,…,an(1≤ai≤300000)

The sum of n over all testcases doesn’t exceed 106.

The sum of k over all testcases doesn’t exceed 106.

Output
For each testcase,one line contains n integers ,a1,a2,…,an — the lexicographically largest possible array after k times operations.

Don‘t have spaces at the end of the line

Sample Input
2
7 3
1 4 2 1 4 2 4
5 2
4 3 5 4 5

Sample Output
4 4 2 4 2 1 1
5 4 5 4 3

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

题意：

• 给出一个长为n的数组（3e5），可以进行k次（3e5）操作。
• 每次操作可以选一个区间[l,r]，让这个区间的a[l]放到a[r]的位置，其他数全部往前移动一格。
• 求最后这个数组的字典序最大是多少，输出新数组。

思路：

• 考虑一次操作，我们会贪心的从头往后找到第一个a[i]
• 考虑优化：注意到每次操作本质是将一个元素拿出，然后把后面所有元素往前移，最后再把拿出的元素插入到拿出位置的后面的某个位置。所以k次操作可以先弹出k个元素，最后再插入回去（不会跟原数组产生影响，因为即便后面第一个小于a[i]的数也被弹出去了，最后归并的时候堆里从大到小往外拿，还是会放到a[i]后面去的）。
• 从前往后k次遇到a[i]对应放到第一个小于a[i]的数的前面）。

//1012 - priority_queue & AC
#include
using namespace std;
const int maxn = 3e5+10;
int a[maxn], b[maxn], c[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n, k;  cin>>n>>k;
        for(int i = 1; i <= n; i++)cin>>a[i];
        priority_queue<int>q; //默认大根堆
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            while(cnt && b[cnt]<a[i] && k){ //a[i-1]
                q.push(b[cnt]); //a[i-1]
                k--;
                cnt--;
            }
            b[++cnt] = a[i]; //维护剩余数组
        }
        //归并
        int num = 0, t = 1;
        for(int i = 1; i <= n; i++){
            if(t > cnt){
                c[++num] = q.top();  q.pop();
            }else if(q.size()==0){
                c[++num] = b[t];  t++;
            }else{
                if(q.top()>b[t]){
                    c[++num] = q.top();  q.pop();
                }else{
                    c[++num] = b[t];  t++;
                }
            }
        }
        for(int i = 1; i <= n; i++){
            cout<<c[i]<<" \n"[i==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

//1012 - list & TLE
#include
using namespace std;
const int maxn = 3e5+100;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
int a[maxn];
// void Print(auto first, auto last){
//     for (; first != last; ++first)
//         cout << *first << " ";
//     cout << endl;
// }
void Print2(auto first, auto last){
    last--;  last--;
    for (; first != last; ++first)
        cout << *first << " ";
    cout<< (*last)<<"\n";
}

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        int n, k;  cin>>n>>k;
        for(int i = 1; i <= n; i++){
            cin>>a[i];
        }
        a[n+1] = -1;
        n++;
        list<int>lst(a+1,a+n+1);
        // Print(lst.begin(),lst.end());
        int nk = 0;
        for(auto i = lst.begin(); ; ){
            auto x = i, y = i; y++;
            if((*i) == -1)break;
            if((*x) < (*y)){
                //找到第一个
                auto cur = y;
                while((*cur) >= (*x))cur++;
                
                //在cur前面插入x
                lst.insert(cur,1,(*x));
                lst.erase(i);
                i = y;
                if(i!=lst.begin())i--;
                nk++;
                // Print(lst.begin(),lst.end());
                if(nk==k)break;
            }else{
                i++;
            }
        }
        Print2(lst.begin(),lst.end());
    }
    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

10.Planar graph

Planar graph
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/262144 K (Java/Others)
Total Submission(s): 289 Accepted Submission(s): 112

Problem Description
We say an undirected graph is a planar graph, if it exists a way to draw it on a planar, such that no two edges have intersection except the endpoint. For example, the graph below is a planar graph:

But this graph below is not a planar graph, since it can be proved that no matter how to draw this graph on a planar, at least two edges have intersection which is not an endpoint:

For a planar graph, it has some areas separated by edges. For example, the planar graph below has 4 areas (Note that the area 1 is the infinite planar outside):

Give you a planar graph with n vertices and m edges. Each area sets a country. You are the designer and you want to build some tunnels on the edges such that: From one city, you can travel to any other city by going through some tunnels or passing some cities(i.e. you can’t cross one edge unless it sets a tunnel). For example, for the graph above, you can build tunnels like this:

In the picture above, you can travel from city 2 to city 3 by going through tunnel 1, passing the city 1, then going through tunnel 3, passing the city 4, finally going through tunnel 2, and you can arrive to city 3. You can check that from any city you can travel to any other city.

You want the number of tunnels as small as possible. Print the minimum number of tunnels and the ID of edges you build tunnel on.

Input
The first line contains one integer T(1≤T≤15), described the number of test cases.

For each test case:

The first line contains two integers n,m(1≤n≤105,0≤m≤2×105) separated by a space, described the number of vertices and edges.

Next m lines, the i-th line contains two integers u,v(1≤u,v≤n), separated by a space, described the endpoint of the i-th edge. The ID of the i-th edge is i.

It is guaranteed that the given graph is a planar graph. But this graph may have self-loop, parallel edge and the graph may not connected.

Output
The output contains 2T lines.

For each test case:

The first line contains one integer f, described the minimum number of tunnels you have to build.

The second lines contains f integers separated by spaces, the i-th integer described the ID of edges the i-th tunnel built on.

If for a fixed minimum number of tunnels, it has many ways to build the tunnels, print the lexicographically smallest answer.

Sample Input
1
5 7
1 1
1 2
1 3
3 4
3 4
2 4
2 5

Sample Output
3
1 2 4

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

题意：

• 给出一张n（1e5）个点m（2e5）条边的无向图，这个图有自环和重边。
  并且这个图是平面图（即它存在一种在平面上绘制它的方法，这种画法它的点除了端点之外没有两条边有交点，即所有的边都不会相交。）
• 按照平面图画法画出来后，这张图把平面分成了若干个面积区域，现在要求我们删掉最少的边让你可以从任意一个区域到达其他所有的区域，求删掉哪些边，有多种方案时输出边的字典序最小的。

思路：

• 一开始的想法是特判掉自环和重边的情况，剩下一个普通图，然后跑tarjan求边双联通分量和桥，找有多少环，然后每个环选条字典序最小的边更新到答案上去。但是写挂了。（不知道是代码还是思路）
• 后来猜想，既然每个连通分量都不含圈，这个图删掉边最后的样子应该大概可能是一棵树（题目说图不连通那就好几棵树嘛），，，然后问题就变成了求字典序最大的生成树嘛（把不在生成树中的边都去掉，去掉的边要编号尽量小，那么生成树的边就编号尽量大）。
• 不确定对不对，但是反正很好敲，于是Kruskal硬水上去，直接就过了。值得一提的是PE了好几发，行末需要有空格没空格PE也是醉了，还有换行什么的（
• 官方证明（平面图欧拉定理）
  

//1010
#include
using namespace std;
const int maxn = 2e6+10;

int fa[maxn+10];
void init(int n){for(int i = 1; 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 count(int n){int cnt=0; for(int i = 1; i <= n; i++)if(fa[i]==i)cnt++;return cnt;}

struct edge{ int u, v, w;}e[maxn];
bool cmp(edge a, edge b){return a.w>b.w; }

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n, m;  cin>>n>>m;
        init(n+1);
        for(int i = 1; i <= m; i++){
            cin>>e[i].u>>e[i].v;  e[i].w = i;
        }
        sort(e+1,e+m+1,cmp);
        vector<int>ans(m+1, 0);
        int res = 0;  //Kruskal
        for(int j = 1; j <= m; j++){
            int x = find(e[j].u), y = find(e[j].v);
            if(x != y){
                merge(x,y);
                ans[e[j].w] = 1;
                res++;
            }
        }
        cout<<m-res<<'\n';  //不在生成树中的边
        vector<int>vc;
        for(int i = 1; i <= m; i++){
            if(!ans[i])cout<<i<<" ";
        }
        cout<<"\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

9.Map

Map
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 524288/262144 K (Java/Others)
Total Submission(s): 328 Accepted Submission(s): 119
Special Judge

Problem Description
Sakuyalove has a large world map M and a small world map m. Both of the them are in the shape of rectangle. The small map m is compressed from the large map M. If the length of M is a and the width of M is b, then the length of m is ka and the width of m is kb, where 0

Input
The first line contains one integer T(1≤T≤105), described the number of test cases.

Each test case contains eight lines. Each line has two integers x,y(−103≤x,y≤103) separated by one space.

The first four lines are the coordinates of the upper left corner, the upper right corner, the lower right corner and the lower left corner of M.

The last four lines are the coordinates of the upper left corner, the upper right corner, the lower right corner and the lower left corner of m.

It is guaranteed that m is within M, both of the them are in the shape of rectangle, and m is compressed from M.

Please note that the upper left corner, the upper right corner, the lower right corner and the lower left corner of m and M are one-to-one corresponding. For example, in the picture of Hint below, the correspondence of points is A−a, B−b, C−c, D−d. But A−c, B−d, C−a, D−b is not allowed.

Output
Your output should contains T lines. Each line contains two real numbers x,y separated by one space, represents the coordinates of the point P. Your absolute error should not exceed 10−6.

Sample Input
1
0 5
15 5
15 0
0 0
3 2
9 5
10 3
4 0

Sample Output
6.000000 2.000000

Hint
In the first example, the picture is like this:

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

题意：

• 给出8个点的坐标，分别是一个大矩形和一个小矩形的四个点。保证这个小矩形落在大矩形的内部，位置随意。
• 然后这个大矩形是一张大地图，小矩形是小地图，等比例缩放，求图中某个点在大地图和小地图中表示的位置是一样的，即对应的长宽比例相同，输出这个点的坐标。

思路：

• 直观的想法就是二分点的坐标，然后求在大矩形和小矩形中对应的长宽比例，判断是多了还是少了，然后再去移动。根据小矩形平行，垂直，斜放三种情况分类讨论，每次直线相交算出距离，比例等数据，然后二分点。或者找单峰函数，三分大概也可以。但是又又又写挂了（
• 最后是巴拿赫不动点定理，结论题，长见识了。
  

#include
using namespace std;
typedef long long LL;

LL X[5], Y[5], x[5], y[5];
LL cross(LL a1, LL a2, LL a3, LL a4){return a1 * a4 - a2 * a3;}

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        for(int i = 1; i <= 4; i++)cin>>X[i]>>Y[i];
        for(int i = 1; i <= 4; i++)cin>>x[i]>>y[i];
        LL Ux = X[4] - X[1], Uy = Y[4] - Y[1];
        LL Vx = X[2] - X[1], Vy = Y[2] - Y[1];
        LL ux = x[4] - x[1], uy = y[4] - y[1];
        LL vx = x[2] - x[1], vy = y[2] - y[1];
        double p = cross(X[1] - x[1], vx - Vx, Y[1] - y[1], vy - Vy) / (double)cross(ux - Ux, vx - Vx, uy - Uy, vy - Vy);
        double q = cross(ux - Ux, X[1] - x[1], uy - Uy, Y[1] - y[1]) / (double)cross(ux - Ux, vx - Vx, uy - Uy, vy - Vy);
        cout<<fixed<<setprecision(6)<<x[1]+p*ux+q*vx<<' '<<y[1]+p*uy+q*vy<<"\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

7.Shinobu loves trip

Shinobu loves trip
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/262144 K (Java/Others)
Total Submission(s): 960 Accepted Submission(s): 219

Problem Description
As a cold-blooded, hot-blooded, and iron-blooded vampire, Shinobu loves traveling around.

There are P countries in total, numbered 0,1,…,P−1.(It is guaranteed that P is a prime number)

It is known that when Shinobu is in the country numbered i, the next country she visits must be the country numbered (i⋅a)modP (a is a constant parameter), and it takes Shinobu 1 day to go from one country to another.

In order to travel smoothly, Shinobu has customized n travel plans, and the i-th travel plan is represented by the starting country si and the travel days di.

For example, if P=233, a=2, a plan’s starting country is 1 and travel days is 2, then Shinobu will visit the city {1,2,4} according to this plan.

Playf knows these travel plans and the value of parameter a, now he wants to ask you q questions. The i-th question asks how many travel plans will make shinobu visit the country xi.

Input
The first line of the input contains one integer T (1≤T≤5 ) — the number of test cases. Then T test cases follow.

For each testcase, the first line contains four integers P, a, n, q(2≤a

Each of the next n lines contains two integers si, di(0≤si

Each of the next q lines contains one integer xi(0≤xi

It is guaranteed that P is a prime number.

Output
For each testcase, print q lines, the i-th line contains one integer — the answer to the i-th question.

Sample Input
2
3 2 1 1
1 1
2
5 4 3 2
1 4
4 3
2 100000
4
2

Sample Output
1
2
1

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

题意：

• 总共有P（素数, <1e9+7）个国家，i号国家只有一条通往编号i*a modP的国家的路，时间为1天。
• 现在有n（<1000）个旅行计划，从si出发，旅行di天。
• 现在有q（<1000）个询问，每次询问对于第xi个国家，有多少个旅行计划会访问到它。

思路：

• 从s走d天后会来到(s*a^d)%P, 判断一个点xi 是否会被计划（s,d）经过，只需要判断是否存在一个k<=d，满足(s*a^k)%P=xi， 由于P，xi，s都已知，所以可以知道a^k的值。
• 可以预处理出所有的a^k, 查询算出来的a^k是否在预处理的数里面，如果不在那么计划就不经过，如果在，就根据算出的k值判断是否满足<=d的条件。
• 需要特判s==0的情况（因为0乘任何数都=0，所以0号点到不到其他任何点，并且要经过0也必须是起点就是0才行）。 对于每个查询q，遍历所有计划n, 根据预处理的结果O(1)计算得到答案，复杂度O(nq)

#include
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
LL s[maxn], d[maxn], inv_s[maxn];

LL pows(LL a, LL x, LL p) { if(x==0)return 1; LL t = pows(a, x>>1, p); if(x%2==0)return t*t%p; return t*t%p*a%p; }

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        LL P, a, n, q;  cin>>P>>a>>n>>q;
        //预处理出f[a^k] = k
        unordered_map<int,int>f;
        LL ak = 1, k = 0;
        while(k<maxn && !f.count(ak)){
            f[ak] = k++;  ak = ak*a%P;
        }
        //si*a^k%P=xi, k = f[xi*inv(si)%P], k<=d[i]
        for(int i = 1; i <= n; i++){
            cin>>s[i]>>d[i];
            if(s[i])inv_s[i] = pows(s[i],P-2,P);
        }
        while(q--){
            LL x;  cin>>x;
            LL ans = 0;
            if(x==0){
                for(int i = 1; i <= n; i++)if(s[i]==0)ans++;
            }else{
                for(int i = 1; i <= n; i++){
                    if(s[i]==0)continue;
                    LL akk = x*inv_s[i]%P;
                    if(f.count(akk) && f[akk]<=d[i])ans++;
                }
            }
            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