2022杭电多校联赛第三场 题解

比赛传送门
作者： fn

---

签到题

1003题 Cyber Language / 网络语言

题目大意
找到每个字符串的第一个字母，变成大写字母并输出。

考察内容
签到

分析
按题意模拟即可。

#include<bits/stdc++.h>
#include<string>
using namespace std;
string s;
int t;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
int main(){
    
	js;    
    cin>>t;
	getline(cin,s);
    while(t--){
    
		getline(cin,s);
		bool flag = false;
		for(int i = 0;i < s.length();i++){
    
			if(i==0) cout<<(char)(s[i]-32); // 转大写 
			else{
    
				if(flag){
    
					cout<<(char)(s[i]-32); // 转大写 
					flag = false;
				}
				else if(s[i]==' '){
    
				 	flag = true;	
				}	
			}
		}
		cout<<endl;
	}
}

---

基本题

1009题 Package Delivery / 取快递

题目大意
给定 $n$ 个区间，每次操作选择一个点，把最多 $k$ 个经过该点区间消除。
求最少操作次数。

考察内容
排序，贪心，复杂度优化

分析
先按照区间右端点排序，枚举右端点即可。
用 $minl$ 数组预处理后缀的最小左端点，优化一下就能通过。

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e5+10;

ll n,k;
struct node{
    
	ll l,r;
	int id;
}a[N];

bool cmp(node x,node y){
    
	if(x.r!=y.r)return x.r<y.r;
	if(x.l!=y.l)return x.l<y.l;
	return x.id<y.id;
}

bool vis[N];
ll minl[N]; 

int main(){
     
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
    
		cin>>n>>k;
		for(int i=1;i<=n;i++){
    
			cin>>a[i].l>>a[i].r;
			a[i].id=i;
		}
		sort(a+1,a+n+1,cmp); // 按照右端点升序排序
		
		minl[n]=a[n].l; // 记录左端点最小值 
		for(int i=n-1;i>=1;i--){
    
			minl[i]=min(minl[i+1],a[i].l);
		}
		
		memset(vis,0,sizeof(vis[0])*(n+1));
		
		ll ans=0;
		
		if(k==1){
     // 如果一次只能拿一件 
			cout<<n<<endl; // 答案就是n次 
			continue;
		} 
		
		// k>=2时 
		// O(n^2)暴力+贪心做法 
		for(int i=1;i<=n;i++){
     // 枚举右端点 
			if(vis[i])continue;
			
			ll p=a[i].r; // 在右端点时才去拿快递(ddl战士) 
			ans++; // 加一次 
			ll cnt=1; // 目前拿了1件 
			vis[i]=1; // 用上 
			
			for(int j=i+1;j<=n;j++){
     // 往后找可以顺带带走的区间 
				if(cnt>=k)break; // 拿不下了，break 
				if(vis[j])continue; 
				
				if(minl[j]>p){
    
					break; // 后面都找不到minl更小的了，提前截止 
				}
				
				if(a[j].l<=p){
     // a[j]左端点<=拿快递时间，顺带带走
					cnt++; // 多拿1件 
					vis[j]=1; 
				}
			}
			
			int h=2000;
			if(i%h==0){
     // 每h个i重新建立minl数组 
				minl[n+1]=1e18; 
				
				// 记录左端点最小值 
				for(int i=n;i>=1;i--){
    
					if(vis[i])minl[i]=minl[i+1];
					else minl[i]=min(minl[i+1],a[i].l);
				}
			} 
		} 
		
		cout<<ans<<endl;
	}
	return 0;
}
/* 输入： 1 4 2 1 7 2 6 3 5 7 8 输出： 2 // 5,7两天 */ 

---

进阶题

1012题 Two Permutations / 两个排列

题目大意
给定两个排列队列 $P,Q$ ，求出队后形成序列 $S$ 的方案数量。

考察内容
动态规划，复杂度优化

分析
一维dp，用map存状态。
时间复杂度 $O(n)$。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ll long long
#define N 600005
#define mod 998244353
using namespace std;
template <typename T>
void inline read(T& x) {
    
    int f = 1;
    x = 0;
    char s = getchar();
    while (s < '0' || s > '9') {
    
        if (s == '-')
            f = -1;
        s = getchar();
    }
    while (s <= '9' && s >= '0')
        x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int t, n, a[N], b[N], c[N], p[N], q[N];
void inline add(int& x, int y) {
     // 加法取模 
    x += y;
    if (x >= mod)
        x -= mod;
}

void solve() {
    
    map<ll, int> mp[2];
    
    // 读入数据 
    read(n);
    for (int i = 1; i <= n; i++)
        read(a[i]), p[a[i]] = i;
    for (int i = 1; i <= n; i++)
        read(b[i]), q[b[i]] = i;
    for (int i = 1; i <= (n << 1); i++)
        read(c[i]);
    
    mp[0][0] = 1; 
    for (int i = 1; i <= (n << 1); i++){
     // 枚举s的每一位 
        mp[i & 1].clear();
        int j = p[c[i]];
        int k = q[c[i]];
        if (j > 0 && j <= min(i, n))
            add(mp[i & 1][j], mp[i - 1 & 1][j - 1]);

        if (i >= k)
            add(mp[i & 1][i - k], mp[i - 1 & 1][i - k]);
    }
    printf("%d\n", mp[0][n]);
}

int main() {
     // dp
    read(t);
    while (t) {
    
        t--;
        solve();
    }
    return 0;
}

---

1002题 Boss Rush / 打Boss

题目大意

boss有 $H$ 单位的生命值。
你会使用 $n$ 个技能，每个技能最多使用1次。每个技能释放消耗的时间为 $t_i$ ，造成的伤害是一个序列。

游戏从第0帧开始，求打败Boss的所需最少时间，如果无法打败Boss输出 “-1” 。

考察内容
动态规划，二分答案

分析
二分答案，把问题转化为判断 $T$ 帧内能否打败 Boss，即求出 $T$ 帧内能打出的最高伤害，判断是否大于等于 $H$。

#include<cstdio>
typedef long long ll;
const int N=18,M=100005;
int Case,n,i,j,S,t[N],d[N],l,r,ans,mid,sum[(1<<N)+1];
ll hp,f[(1<<N)+1],dmg[N][M];
inline void up(ll&a,ll b){
    a<b?(a=b):0;}
bool check(int T){
    
    int S,i;
    for(S=0;S<1<<n;S++)f[S]=-1;
    f[0]=0;
    for(S=0;S<1<<n;S++){
      
        ll w=f[S];
        if(w<0)continue;
        if(w>=hp)return 1;
        int cur=sum[S];
        if(cur>T)continue;
        for(i=0;i<n;i++)if(!(S>>i&1)){
    
            if(cur+d[i]-1<=T)up(f[S|(1<<i)],w+dmg[i][d[i]-1]);
            else up(f[S|(1<<i)],w+dmg[i][T-cur]);
        }
    }
    return 0;
}
int main(){
    
    scanf("%d",&Case);
    while(Case--){
    
        scanf("%d%lld",&n,&hp);
        ans=-1, l=r=0;
        for(i=0;i<n;i++){
    
            scanf("%d%d",&t[i],&d[i]);
            r+=t[i]+d[i]-1;
            for(j=0;j<d[i];j++)scanf("%lld",&dmg[i][j]);
            for(j=1;j<d[i];j++)dmg[i][j]+=dmg[i][j-1];
        }
        for(S=1;S<1<<n;S++)sum[S]=sum[S-(S&-S)]+t[__builtin_ctz(S&-S)];
        
        // 二分答案 
        while(l<=r){
     
            mid=(l+r)>>1;
            if(check(mid))r=(ans=mid)-1;else l=mid+1;
        }
        printf("%d\n",ans);
    }
}

---