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
- 9.Package Delivery
- 12.Two Permutations
- 2.Boss Rush
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<bits/stdc++.h>
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;
}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<bits/stdc++.h>
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;
}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<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 = 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;
}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<leni) units of damage at the (x+j)-th frame if Little Q uses the i-th skill at the x-th frame. Note that leni can be greater than ti, for example, the burning skill can burn the boss for a long period, but takes a little time to cast the fire.
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<bits/stdc++.h>
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;
}