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

Solved Problem ID Title Ratio (Accepted / Submitted)
1001 Link with Bracket Sequence II 29.43% (389/1322)
1002 Link with Running 4.85% (199/4105)
1003 Magic 49.78% (113/227)
1004 Link with Equilateral Triangle 53.97% (1013/1877)
1005 Link with Level Editor II 18.11% (132/729)
1006 BIT Subway 37.86% (1059/2797)
1007 Climb Stairs 26.47% (724/2735)
1008 Fight and upgrade 4.55% (3/66)
1009 Fall with Full Star 10.76% (38/353)
1010 Fall with Intersection 4.57% (10/219)
1011 Link is as bear 23.56% (524/2224)

4.Link with Equilateral Triangle

Link with Equilateral Triangle
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 56 Accepted Submission(s): 40

Problem Description
Link has a big equilateral triangle with side length n. The big triangle consists of n2 small equilateral triangles with side length 1.

Link is going to fill numbers into each vertex of the small triangle with the following limits:

· The number filled in should be 0, 1, or 2.
· The left side of the big triangle should not be filled with 0. The right side of the big triangle should not be filled with 1. The bottom side of the big triangle should not be filled with 2.
· For each small triangle with side length 1, the sum of three vertices should not be a multiple of 3.

Link went crazy when he tried to do so because he couldn’t find any triangle satisfying all conditions above. Now, he turns to you for help.

Please tell Link: Is it possible to fill the triangle so that it satisfies all conditions above?

Input
Each test contains multiple test cases. The first line contains the number of test cases T (1≤T≤1000). Description of the test cases follows.

For each test case, there is only one line containing a single integer n (1≤n≤103).

Output
For each test case, output Yes if it is possible to do so. Output No if it is impossible to do so.

Sample Input
2
1
2

Sample Output
No
No

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

题意：

• 有一个大三角形，由n^2个边长为1的小三角形构成。
  每个小三角形的三个顶点需要填入0，1，2。
  每个大三角形的左边不能有0，右边不能有1，下面不能有2。
• 求给定的n是否存在满足条件的三角形。

思路：

• 可以证明一定没有，因此直接输出NO即可。
• 官方证明：
  

#include<bits/stdc++.h>
using namespace std;

int main(){
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        cout<<"No\n";
    }
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

6.BIT Subway

BIT Subway
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 67 Accepted Submission(s): 34

Problem Description
BIT(Beijing International Transport) subway, which can take people anywhere in a short time, is the most popular travel mode in 2050. One day, BIT subway launches a promotion as follows:

• If the total ticket price x you have spent this month is greater than or equal to 100 and you buy another ticket with ￥y, then you only need to pay ￥0.8y.
• If the total ticket price x you have spent this month is greater than or equal to 200 and you buy another ticket with ￥y, then you only need to pay ￥0.5y.

DLee is so happy that he can save more money to buy a house. However, a long time later, he notices that the real billing method is a bit different from what he thought. For example, DLee has spent ￥199 on tickets this month, he now buys a ￥10 ticket, then buys an ￥8 ticket:

• DLee thinks that he can buy only a part of the ticket instead of the whole ticket at a time. That is, for the ￥10 ticket, DLee thinks he can buy the ￥1.25 part of the ticket first and buy the ￥8.75 part of the ticket then. Under his misunderstanding, he needs to spend 199+1.25*0.8+8.75*0.5+8*0.5=￥208.375. Note that in this example, DLee has to spend ￥1.25 instead of only ￥1 to make x=200.
• The real billing method is that only if you have spent enough, you can get the discount, so it will be 199+10*0.8+8*0.5=￥211.

Now DLee wants to know in the previous months, how much difference did the billing method make.

Input
Each test contains multiple test cases. The first line contains one integer T(1≤T≤10), which means the months DLee wants to check. Description of the months follows.

The first line contains a single integer n(1≤n≤105), which means the number of tickets DLee bought in this month.

Then follows n integers a1,a2,…,an(1≤ai≤200), ai means the i-th ticket’s price.

Output
For each month, output one line with two numbers divided by a single whitespace with three decimal places. The first number represents the cost in DLee’s thought, and the second number represents the real cost.

Sample Input
3
7
20 20 20 20 18 7 8
13
30 20 23 20 7 20 11 12 30 20 30 15 13
3
10 200 10

Sample Output
110.400 111.400
213.000 216.900
196.000 215.000

Hint
For the first case, DLee thinks the cost is: 20+20+20+20+18+2+((7−2)+8)*0.8=￥110.4, the real cost is: 20+20+20+20+18+7+8*0.8=￥111.4

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

题意：

• 现在你要买票，超过100块打八折，超过200块打5折。
• 打折有两种算法，一种是超过的钱数打折，一种是超过的物品打折。
  求两种打折下算出的钱数。

思路：

• 对于第二种超过的物品打折，因为按照顺序购买的，所以直接枚举到超过，然后下一件物品开始打折即可。
• 对于第一种超过的钱数打折，可以知道算出是个分段函数，直接输出即可。
  

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        double sum1 = 0, sum2 = 0, op = 1;
        for(int i = 1; i <= n; i++){
            int x;  cin>>x;
            sum1 += x;
            sum2 += x*op;
            if(sum2 >= 100)op = 0.8;
            if(sum2 >= 200)op = 0.5;
        }
        if(sum1 >= 100 && sum1<=225){
            sum1 = (sum1-100)*0.8+100;
        }else if(sum1 > 225){
            sum1 = (sum1-225)*0.5+200;
        }
        printf("%.3lf %.3lf\n", sum1, sum2);
    }
    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
 

7.Climb Stairs

Climb Stairs
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 93 Accepted Submission(s): 40

Problem Description
DLee came to a new level. What is waiting for him is a tall building with n floors, with a monster on each stair, the i-th of which has health point ai.

DLee starts from the ground(which can be regarded as the 0-th floor), with a base attacking point a0. He can choose to jump 1,2,…,k floors up or walk 1 floor down, but he cannot go to floors whose monster has a health point strictly greater than his attacking point, nor can he go to floors which had been visited. Once he comes and defeats a monster he can absorb his health point and add it to his attacking point.

Note that DLee should always be on floors {0,1,2,3,…,n}.

Now DLee asks you whether it is possible to defeat all the monsters and pass the level.

Input
There are T test cases.

In each test case, the first line contains three integers: n,a0,k(1≤n,k≤105,1≤a0≤109), representing the number of floors, base attacking point, and the maximum number of floors that DLee can jump.

The second line contains n integers a1,…,an(1≤ai≤109), representing the health point of each monster.

The sum of n does not exceed 106.

Output
For each test case, output “YES” or “NO” to show whether it’s possible to defeat all monsters.

Sample Input
4
6 1 4
2 2 1 1 9 3
4 2 2
2 3 8 1
3 1 2
3 1 2
7 2 3
4 3 2 7 20 20 20

Sample Output
YES
YES
NO
NO

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

题意：

• 有n个位置，每个位置的怪物有ai点血。
• 初始站在位置0，有a0点伤害，每次可以跳到前面1-k的位置或者往后1个位置。
• 干掉怪物后获得对应血量的攻击力，求能不能干掉所有怪物。

思路：

• 因为要求打完所有的怪物，所以跳过了某个怪物肯定还要回去打他，如果我们从x跳到了y，那y-1,y-2,y-3,x这段的怪肯定还要退回来打的，并且必须这一轮打完。因此y肯定越小越好，我们只需要找到当前能够打掉的最近的怪（必须退到x+1，即y->x+1这一段都能打得过） 过去干掉就行了。
• 关于如何维护，官方做法是sgt。这里也可以用二分+前缀和做。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const int maxn = 1e5+10;

LL a[maxn], s[maxn], n, a0, k;
LL calc(LL x){ //能走到x点的最小的y
    LL l = x, r = n+1;
    while(l < r){
        LL mid = l+r>>1;
        if(s[mid]-s[x]+a0 >= a[x])r = mid;//[x+1,mid]+a0>=a[x]
        else l = mid+1;
    }
    return r;
}

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        cin>>n>>a0>>k;
        for(int i = 1; i <= n; i++){
            cin>>a[i];  s[i] = s[i-1]+a[i];
        }
        int ok = 0;
        LL now = 1, lst = 0; //当前(想去)的位置, 上次(当前)的位置
        while(now <= n){
            ok = 0;
            LL pos = 0;
            for(int i = now; i <= min(lst+k, n); i++){ //往右找能走的点
                pos = max(pos, calc(i));  //最小的y要取max
                if(pos==i){               //直到某个点直接就能走到
                    ok = 1;
                    a0 += s[i]-s[now-1];  //走到i点
                    lst = now;
                    now = i+1;
                    break;
                }
            }
            if(ok==0)break;
        }
        if(ok==0)cout<<"NO\n";
        else cout<<"YES\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
 

11.Link is as bear

Link is as bear
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 223 Accepted Submission(s): 91

Problem Description
Link, a famous bear magician in Bear Institute of Talented(BIT), has recently learned new magic.

That is, given a array a containing n elements a1,…,an, and Link can cast the following magic:

Link can choose two integers l,r such that 1≤l≤r≤n, making all ai=xor(l,r) where l≤i≤r and xor(l,r) denotes the bitwise-xor(⊕) of all elements in [l,r]. More formally, xor(l,r)=al⊕al+1⊕…⊕ar.

Link can cast this magic any time(possibly, zero) and can choose l,r arbitrarily. However, since Link has a sort of Obsessive-Compulsive Disorder(OCD), he wants all elements to become the same after his operation. Now, he wonders about the maximum of this same value.

What’s more, Link finds that the given array has a weird property: there always exists at least one pair of x,y(x≠y) such that ax=ay.

Input
The first line contains an integer T(1≤T≤3∗104), the number of the test cases.

The first line of each test case is an interger n(1≤n≤105), the length of the array a.

The second line of each test case containing n integers, while the i-th denoting ai(0≤ai≤1015). It’s guaranteed that there always exists at least one pair of x,y(x≠y) such that ax=ay.

It’s also guaranteed that Σn≤106.

Output
For each test case, output a single intergers indicating the maximum of the same value after Link’s operations.

Sample Input
2
5
10 10 10 10 10
4
1 1 2 1

Sample Output
10
3

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

题意：

• 给出一个长为n的数组，每次可以令一个区间[l,r]的值都变成整个区间异或后的值。保证1-n中存在某个数出现两次。
• 可以操作无数次。最后要求1-n的值都相同且取到最大，求这个最大值。

思路：

• 可以证明，从这n个数里任取一些数异或起来的方案，都是可以构造出对应的操作来做到的。所以，问题完全等价于给n个数，从中选一些数，使得这些数的异或和最大。
• 这是线性基的板题，抄一个板子即可。
• 官方证明：
  

//N个数中选择任意个异或和最大
//1.dfs, 每个数选或不选，第n层ans维护最大值
//2.线性基：由一个集合构造出来的另一个集合，即向量空间的一组基，多用于异或题。
/*
线性基的性质:
+ 对于原数组，我们用最少个数作为基础，用这些数之间的异或 就可以 表示所以子集合的异或和，类似于用10个数来表示1~1023的所有数
+ 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
+ 线性基没有异或和为 0 的子集。
+ 线性基中每个元素的二进制最高位互不相同。
*/
#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const int maxn = 2e6+10;
LL a[maxn], d[80];

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        memset(d,0,sizeof(d));
        LL n;  cin>>n;
        for(int i = 1; i <= n; i++)cin>>a[i];
        //构造线性基, 对原集合的每个数p转为二进制，从高位向低位扫
        //https://oi-wiki.org/math/basis/
        for(int i = 1; i <= n; i++){
            LL x = a[i];
            for(LL j = 63; j >= 0; j--){
                if((x>>j)&1){//对于第j位是1的
                    //如果d[j]不存在, 那么令d[j]=x并结束扫描
                    if(!d[j]){ d[j] = x; break; }
                    //如果存在，令x=x^d[j]
                    x ^= d[j];
                }
            }
        }
        //线性基求最大异或和：
        //将线性基从高位向低位扫，若xor上当前扫到的d[x]答案变大，就把答案异或上d[x]
        //因为从高往低位扫，若当前扫到第i位，意味着可以保证答案的第i位为1，且后面没有机会改变第i位
        LL ans = 0;
        for(int i = 63; i >= 0; i--){
            ans = max(ans, ans^d[i]);
        }
        cout<<ans<<"\n";
        //其他例子：
        //查询原集合内任意几个元素 xor 的最小值，就是线性基集合所有元素中最小的那个。
        //查询某个数是否能被异或出来，类似于插入，如果最后插入的数p被异或成了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
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
 

1.Link with Bracket Sequence II

Link with Bracket Sequence II
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 299 Accepted Submission(s): 127

Problem Description
Link has a bracket sequence of length n. Today, Link finds out that some brackets of the sequence were lost.

Of course, he wants you to calculate how many ways are there to fill the sequence so that it will be a valid bracket sequence.

Note that there are m types of brackets in Link’s world.

Here’s the definition of a valid bracket sequence:

· A sequence of length 0 is a valid bracket sequence.
· If A is a valid bracket sequence, x is some type of left bracket, y is the same type of right bracket, xAy is a valid bracket sequence.
· If A,B are both valid bracket sequences, then AB is also a valid bracket sequence.

Input
Each test contains multiple test cases. The first line contains the number of test cases T(1≤T≤20). Description of the test cases follows.

The first line contains two integers n(1≤n≤500),m(1≤m<109+7), which is the length of Link’s bracket sequence and the types of brackets.

The second line contains n integers a1,a2,…,an(|ai|≤m). The i-th integer ai describes the i-th character in the sequence:

· If ai=0, it means the bracket in this position is lost.
· ai>0, it means the i-th character in the sequence is the ai-th type of left bracket.
· ai<0, it means the i-th character in the sequence is the −ai-th type of right bracket.

It is guaranteed that there are at most 15 test cases with n>100.

Output
For each test case, output one integer in a line, which is the number of ways to fill the bracket sequence so that it is a valid bracket sequence. Since the answer can be huge, just print it modulo 109+7.

For some reason, there could be no way to make it a valid bracket sequence.

Sample Input
3
4 2
1 0 0 -1
4 2
0 0 0 -1
6 3
0 0 0 0 0 0

Sample Output
3
4
135

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

题意：

• 长为n（<500）的括号序列，由m（<1e7）种括号构成，a[i]>0表示左括号，<0表示右括号，=0表示暂时没放括号，数字对应括号的种类。
• 求给0的地方放置括号最多有多少种合法的方案。

思路：

• 因为括号种类太大，完全没有操作空间，所以肯定从n下手。500的数据大概是2维dp。直接的想法状态i肯定表示到第i个数为止，但是j不管用什么表示好像都没办法表示所有的情况，尤其是括号有m种的情况记不下来，如果只是左比右多多少好像也没法计算具体的方案数。所以最后是个区间DP，让g[i,j] 表示 [i,j] 区间形成一个合法括号序列的方案数，最后答案显然就是 g[1, n ]。
• 考虑转移。枚举 i,j 位置上填写的内容，如果形成匹配的括号对，设使得i,j匹配的方案数为k，则k*g[i+1,j-1]表示，i,j位置上的括号互相匹配的且区间[i,j]为合法括号序列的方案数，令其为f[i,j]。
• 之后，还可以用g[i,k]+f[k+1,j]为g[i,j]进行转移。就可以dp出g数组的值了。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL maxn = 510, mod = 1e9+7;
LL a[maxn], f[maxn][maxn], g[maxn][maxn];

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        memset(g,0,sizeof(g));
        memset(f,0,sizeof(f));
        int n, m;  cin>>n>>m;
        for(int i = 1; i <= n; i++)cin>>a[i];
        if(n%2==1){ cout<<"0\n";  continue; }
        for(int i = 0; i <= n; i++)g[i+1][i] = 1;
        for(int len = 2; len <= n; len+=2){    //枚举区间长度
            for(int l = 1; l+len-1 <= n; l++){ //枚举区间起点
                int r = l+len-1;               //计算区间终点
                if(a[l]>=0 && a[r]<=0){        //端点l,r上的括号可以匹配()
                    int k;
                    if(!a[l] && !a[r])k = m;      //都是0，合法方案有m种
                    else if(!a[l] || !a[r])k = 1; //有一个不是0，合法方案1种
                    else if(!(a[l]+a[r]))k = 1;   //都不是0，合法方案1种
                    else k = 0;                   //区间l,r端点处括号不匹配
                    f[l][r] = k*g[l+1][r-1]%mod;
                }
                for(int k = l; k <= r; k += 2){//用f[l][r]为g[l][r]转移
                    g[l][r] = (g[l][r]+g[l][k-1]*f[k][r])%mod;
                }
            }
        }
        cout<<g[1][n]<<"\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
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/126040156