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

Problems
Solved Problem ID Title Ratio (Accepted / Submitted)
1001 Equipment Upgrade 33.53% (115/343)
1002 Boss Rush 13.79% (246/1784)
1003 Cyber Language 69.82% (1189/1703)
1004 Divide the Sweets 3.24% (7/216)
1005 Spanning Tree Game 9.83% (40/407)
1006 Dusk Moon 6.91% (32/463)
1007 Shallow Moon 4.35% (1/23)
1008 Laser Alarm 12.91% (131/1015)
1009 Package Delivery 11.41% (667/5847)
1010 Range Reachability Query 5.88% (3/51)
1011 Taxi 15.37% (213/1386)
1012 Two Permutations 18.29% (516/2821)

3.Cyber Language

Cyber Language
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 203 Accepted Submission(s): 145

Problem Description
You may have ever seen the following words written in cyber language: ‘‘KK’’, ‘‘DDW’’, ‘‘SMWY’’, which means ‘‘kan kan’’, ‘‘dai dai wo’’, ‘‘shen me wan yi’’, respectively.

To translate a Chinese sentence into cyber language, you need to find the first letter of each Chinese character, and write it in upper-case.

You will be given several Chinese sentences, please translate them into the cyber language described above.

Input
The first line contains a single integer T (1≤T≤10), the number of test cases. For each test case:

The only line contains several Chinese characters written in lower-case, separated by exactly one space. It is guaranteed that the length of each line is at least 1 and at most 50.

Output
For each test case, output a single line containing a string, denoting the corresponding word written in the cyber language.

Sample Input
3
kan kan
dai dai wo
shen me wan yi

Sample Output
KK
DDW
SMWY

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

题意：

• 无

思路：

• 签到模拟，遍历每个字符，如果一个字符的前一个字符是空格或者它是第一个字符，那么把它转大写输出。

#include
using namespace std;

int main(){
    int T;  cin>>T;  cin.get();
    string s;
    while(T--){
        getline(cin,s);
        for(int i = 0; i < s.size(); i++){
            if(i==0||s[i-1]==' '){
                cout<<(char)toupper(s[i]);
            }
        }
        cout<<"\n";
    }
    return 0;
}


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

9.Package Delivery

Package Delivery
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 946 Accepted Submission(s): 264

Problem Description
Little Q likes online shopping very much. In the next 109 days, there will be n packages delivered to the post office in total. Let’s label the next 109 days as day 1, day 2, …, day 109 respectively. For the i-th package, it will arrive at the post office at day li, and the deadline to take it back home is day ri, which means Little Q can take it back home at day x if and only if li≤x≤ri.

Every time Little Q comes to the post office, he can take at most k packages together back home at the same time. Note that Little Q can go to the post office multiple times during a single day. Please help Little Q determine how to take these n packages back home such that the number of times he will go to the post office is minimized.

Input
The first line contains a single integer T (1≤T≤3000), the number of test cases. For each test case:

The first line contains two integers n and k (1≤k≤n≤100000), denoting the number of packages and the number of packages Little Q can carry at the same time.

Each of the following n lines contains two integers li and ri (1≤li≤ri≤109), describing a package.

It is guaranteed that the sum of all n is at most 1000000.

Output
For each test case, output a single line containing an integer, denoting the minimum possible number of times that Little Q will go to the post office.

Sample Input
1
4 2
1 3
2 4
6 7
4 7

Sample Output
2

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

题意：

• 给出n个区间，每次可以去掉小于等于k个存在重叠的区间，求最少多少次去掉所有的区间。

思路：

• 考虑r最小的那个区间k，第一次取快递放在第rk 天一定不会使结果变差。
• 此时可能有很多区间覆盖了rk，那么为了尽量延后下一次取快递的日期，此时的最优策略应该是选择覆盖rk且r值最小的k个区间。
• 使用优先队列找到并去掉这些区间后，递归重复上述过程直至处理完所有n 个区间即可。

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

struct node{ int l, r, id; }a[maxn], b[maxn];
bool cmpl(node x, node y){  return x.l<y.l; }
bool cmpr(node x, node y){  return x.r<y.r; }
int del[maxn];

typedef pair<int,int>P;
priority_queue<P,vector<P>,greater<P> >q; //左键小根堆

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].l>>a[i].r;  a[i].id=i;
            b[i] = a[i];
            del[i] = 0; //初始化
        }
        sort(a+1,a+n+1,cmpr);
        sort(b+1,b+n+1,cmpl);
        int ans = 0, j = 1;
        for(int i = 1; i <= n; i++){
            if(del[a[i].id])continue; //共同标识id，标识这个元素被删了
            while(j<=n && b[j].l<=a[i].r){//覆盖rk的
                q.push(P(b[j].r, b[j].id));  j++;//按r值从小到大排
            }
            ans++; //去掉rk
            for(int t=1; t <= k; t++){//去掉k个或全部
                if(q.empty())break;
                del[q.top().second] = 1;
                q.pop();
            }
        }
        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

12.Two Permutations

Two Permutations
Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1038 Accepted Submission(s): 276

Problem Description
There are two permutations P1,P2,…,Pn, Q1,Q2,…,Qn and a sequence R. Initially, R is empty. While at least one of P and Q is non-empty, you need to choose a non-empty array (P or Q), pop its leftmost element, and attach it to the right end of R. Finally, you will get a sequence R of length 2n.

You will be given a sequence S of length 2n, please count the number of possible ways to merge P and Q into R such that R=S. Two ways are considered different if and only if you choose the element from different arrays in a step.

Input
The first line contains a single integer T (1≤T≤300), the number of test cases. For each test case:

The first line contains a single integer n (1≤n≤300000), denoting the length of each permutation.

The second line contains n distinct integers P1,P2,…,Pn (1≤Pi≤n).

The third line contains n distinct integers Q1,Q2,…,Qn (1≤Qi≤n).

The fourth line contains 2n integers S1,S2,…,S2n (1≤Si≤n).

It is guaranteed that the sum of all n is at most 2000000.

Output
For each test case, output a single line containing an integer, denoting the number of possible ways. Note that the answer may be extremely large, so please print it modulo 998244353 instead.

Sample Input
2
3
1 2 3
1 2 3
1 2 1 3 2 3
2
1 2
1 2
1 2 2 1

Sample Output
2
0

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

题意：

• 给出两个长为n的排列P和Q，每次随机从P或Q中选一个数字放入新序列得到长为2n的数组S。
• 求从PQ得到S的方案数有多少种。

思路：

• 首先特判序列 S 中每个数字出现次数不都为2的情况，此时答案为0。
• 因为PQ都是1e5以内的排列，所以不难记录1-n每个数字在PQ中的位置，甚至S也是同理，每个数字只会出现两次。
• 然后拿P去匹配S，不难想到DP。当P的前i项，Q的前j项匹配上了S时的方案数。但是因为状态n方会爆空间和时间。
• 考虑用性质去优化。Pi这个数字在S中最多出现2次，因此第二维只需要2个空间就可以记录下来，毕竟这个数字不是在P就肯定在S了，如果不在S那就是0了。
  因此状态 f[i,j] 表示 P 的前 i 项匹配上了S，且Pi 匹配 S 中数字Pi 第 j 次出现的位置时的方案数。
• 转移时枚举 Pi+1 匹配哪个位置，那么Pi 匹配的位置与Pi+1 匹配的位置中间的那段连续子串需要完全匹配Q 中对应的子串。 可以用字符串Hash进行O（1）的判断。

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL maxn = 3e5+10, mod = 998244353;
LL a[maxn], b[maxn], c[maxn*2], pc[maxn*2][2];//记录c中每个数第i次出现的位置
LL f[maxn][2], ans, n, n2;//pi与s匹配，pi在s中第j次出现（即q中的pi是否已出现在s中）

//字符串哈希
const LL di = 233;
LL h[maxn*2], fb[maxn*2], fc[maxn*2];
void init(LL ed){ h[0] = 1; for(LL i = 1; i < ed; i++)h[i]=h[i-1]*di; }
LL ask(LL f[], LL l, LL r){ return f[r]-f[l-1]*h[r-l+1]; }
LL check(LL bl, LL br, LL cl, LL cr){//O(1)判断序列q[bl,br]和s[cl,cr]是否相同
    if(bl>br)return 1;
    if(bl<1||br>n || cl<1||cr>n2)return 0;
    return ask(fb,bl,br)==ask(fc,cl,cr);
}

int main(){
    IOS;
    init(maxn*2);
    LL T;  cin>>T;
    while(T--){
        memset(pc,0,sizeof(pc));
        memset(f,0,sizeof(f));
        //input
        cin>>n;
        for(LL i = 1; i <= n; i++)cin>>a[i];
        for(LL i = 1; i <= n; i++)cin>>b[i], fb[i]=fb[i-1]*di+b[i];
        n2 = n*2;
        for(LL i = 1; i <= n2; i++){
            cin>>c[i];  fc[i] = fc[i-1]*di+c[i];
            if(pc[c[i]][0]==0)pc[c[i]][0] = i; else pc[c[i]][1] = i;
        }
        //特判不都为2
        LL ii;  for(ii = 1; ii <= n; ii++)if(!pc[ii][0] || !pc[ii][1])break;
        if(ii<=n){  cout<<"0\n";  continue; }
        //处理其他的
        for(LL j = 0; j < 2; j++){            //p[1]在s中出现1,2次的位置
            LL x = pc[a[1]][j];               //s的[1,x-1]都是q
            if(check(1,x-1,1,x-1))f[1][j] = 1;
        }
        for(LL i = 1; i < n; i++){            //p前i个与s匹配
            for(LL j = 0; j < 2; j++){
                if(f[i][j]){
                    LL x = pc[a[i]][j];       //p[i]在s中的位置
                    for(LL k = 0; k < 2; k++){//枚举p[i]是第几次出现
                        LL y = pc[a[i+1]][k]; //p[i+1]在s中的位置
                        if(y <= x) continue;   //[x+1,y-1]必须为q子串
                        if(check(x-i+1,y-i-1, x+1, y-1)){//p匹配了i个，位置在s的x，所以q就是x-i个
                            f[i+1][k] = (f[i+1][k]+f[i][j]+mod)%mod;
                        }
                    }
                }
            }
        }
        LL ans = 0;
        for(LL j = 0; j < 2; j++){            //p[n]后面的整段都必须在q中
            if(f[n][j]){
                LL x = pc[a[n]][j];
                if(check(x-n+1, n, x+1, n2)){ //x-n即为q当前匹配了的个数，一直到末尾(包含)即可
                    ans = (ans+f[n][j]+mod)%mod;
                }
            }
        }
        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
59
60
61
62
63
64
65
66
67
68
69
70
71
72

2.Boss Rush

Boss Rush
Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1243 Accepted Submission(s): 326

Problem Description
Finally, Little Q gets his weapon at level 105 in the RPG game, now he is trying to beat the boss as soon as possible. The boss has H units of health point (HP), Little Q needs to cause at least H units of damage to beat the boss.

Little Q has learnt n skills, labeled by 1,2,…,n. Each skill can not be used multiple times, because there is not enough time for Little Q to wait for the skill to cool down. Assume Little Q uses the i-th skill at the x-th frame, the actor controlled by him will take ti frames to perform, which means Little Q will not be allowed to use other skills until the (x+ti)-th frame. The length of the damage sequence of the i-th skill is leni, which means the skill will cause di,j (0≤j

The game starts at the 0-th frame. Your task is to help Little Q beat the boss as soon as possible, or determine Little Q can’t beat the boss using all the skills at most once.

Input
The first line contains a single integer T (1≤T≤100), the number of test cases. For each test case:

The first line contains two integers n and H (1≤n≤18, 1≤H≤1018), denoting the number of skills and the HP of the boss.

For each skill, the first line contains two integers ti and leni (1≤ti,leni≤100000), the second line contains leni integers di,0,di,1,…,di,leni−1 (1≤di,j≤109).

It is guaranteed that the sum of all leni is at most 3000000, and there are at most 5 cases such that n>10.

Output
For each test case, output a single line containing an integer, denoting the first frame to beat the boss. If it is impossible to beat the boss, please print ‘’-1’’ instead.

Sample Input
3
1 100
5 3
50 60 70
2 100
2 3
40 40 100
100 2
20 5
1 1000
1 1
999

Sample Output
1
2
-1

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

题意：

• BOSS有H点血。你有n个技能，每个技能只能用一次，且用完后ti秒内不能用其他技能，效果是leni秒内每秒造成d[i,lenj]点伤害。
• 求最少用多少时间可以干掉boss。

思路：

• 二分答案，转化为判断 T 秒内能否打败BOSS，即求出 T 秒内能打出的最高伤害，判断是
  否大于等于H。
• 从前往后依次发动若干个技能，则下一个技能可以发动的时刻等于之前发动过的技能的时间之和，因此只和之前发动过哪些技能有关。因为技能数量很小，因此可以状压枚举，令ss[S]表示发动集合S的所有技能需要花费的时间，可以预处理后O1得到结果
• 设f(s)表示发动了s集合的技能后在T秒内最多能结算多少伤害 ，枚举不在S中的某个技能x作为下一个技能进行转移，由于技能发动时刻已知，因此可以O(1) 计算出在T秒内下一个技能可以结算多少伤害。

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL maxn = 2e5+10;

LL n, hp, t[20], len[20], d[20][maxn], ss[(1<<20)+1], f[(1<<20)+1];
LL check(LL T){
    for(LL S=0; S < (1<<n); S++)f[S] = -1;
    f[0] = 0;                        //f[S], 集合S可以打出的最大伤害，由不在S中的进行转移
    for(LL S=0; S < (1<<n); S++){
        if(f[S] >= hp)return 1;      //可以干掉boss
        if(f[S] < 0)continue;        //无法转移到技能S 
        if(ss[S] > T)continue;       //发动S需要的时间已经>T了，再见
        LL cur = ss[S], w = f[S];    //当前用的时间，造成的伤害
        for(LL i = 0; i < n; i++){ 
            if(!(S>>i&1)){           //枚举不在S中的技能进行转移
                if(cur+len[i]-1<=T){ //时间<=T，可以全伤
                    f[S|(1<<i)] = max(f[S|(1<<i)], w+d[i][len[i]-1]);
                }else{               //时间不够，用T-cur的全部时间去打多少算多少
                    f[S|(1<<i)] = max(f[S|(1<<i)], w+d[i][T-cur]); 
                }
            }
        }
    }
    return 0;
}

int main(){
    IOS;
    LL T;  cin>>T;
    while(T--){
        cin>>n>>hp;
        LL sum = 0;
        for(LL i = 0; i < n; i++){
            cin>>t[i]>>len[i];   //等待,伤害
            sum += t[i]+len[i]-1;
            for(LL j = 0; j < len[i]; j++)cin>>d[i][j];
            for(LL j = 1; j < len[i]; j++)d[i][j] += d[i][j-1];
        }
        for(LL S = 1; S < (1<<n); S++){ //ss[S]: 发动集合S需要的前置时间
            ss[S] = ss[S-(S&-S)]+t[__builtin_ctz(S&-S)];//+=末位技能发动需要的时间
        }
        LL l = 0, r = sum, ans = -1;
        while(l <= r){
            LL mid = l+r>>1;
            if(check(mid)){
                ans = mid;
                r = mid-1;
            }else l = mid+1;
        }
        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