比赛传送门
作者： fn

---

签到题

1003题 Cyber Language / 网络语言

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

考察内容
签到

分析
按题意模拟即可。

#include
#include
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;
	}
}
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

---

基本题

1009题 Package Delivery / 取快递

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

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

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

#include
#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两天 

*/ 
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

---

进阶题

1012题 Two Permutations / 两个排列

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

考察内容
动态规划，复杂度优化，字符串哈希

分析
方法一：
二维dp，$f[i][j]$ 的状态表示是 $S$ 的前 $i$ 个用了 $P$ 的前 $j$ 个。
把第一位滚动掉，并用unordered_map存状态。
时间复杂度 $O(n)$。

方法一代码：

#pragma GCC optimize(3)
#include 
#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() {
    unordered_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;
}
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

方法二(更快)：

dp+字符串哈希。

字符串哈希传送门

方法二代码：

#include
typedef unsigned long long ull;
const int N=300005,P=998244353;
const int S=233; // 一个常数，用于字符串哈希 

int Case,n,i,j,k,x,y;
int a[N],b[N],c[N*2],pc[N][2],f[N][2],ans;
ull p[N*2],fb[N],fc[N*2];

inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;} // 加法取模 

inline ull ask(ull*f,int l,int r){return f[r]-f[l-1]*p[r-l+1];} // 返回字符串的哈希值 

inline bool check(int bl,int br,int cl,int cr){ // 判断序列b,c中的两段子串是否相等 
  	if(bl>br)return 1; 
  	if(bl<1||br>n||cl<1||cr>n+n)return 0;
  	return ask(fb,bl,br)==ask(fc,cl,cr);
}

int main(){ // dp+字符串哈希 
	// 预处理常数S的幂次，存入p数组 
  	for(p[0]=i=1;i<N*2;i++)p[i]=p[i-1]*S;
  	
  	scanf("%d",&Case);
  	while(Case--){
  		// 输入数据 
  	  	scanf("%d",&n);
  	  	
  	  	// 初始化pc 
		for(i=1;i<=n;i++)pc[i][0]=pc[i][1]=0;
  	  	
  	  	for(i=1;i<=n;i++)scanf("%d",&a[i]);
  	  	for(i=1;i<=n;i++){
  	  		scanf("%d",&b[i]);
			fb[i]=fb[i-1]*S+b[i];
  	  	}
  	  	for(i=1;i<=n+n;i++){
  	  	  	scanf("%d",&x);
  	  	  	c[i]=x;
  	  	  	fc[i]=fc[i-1]*S+x;
  	  	  	if(!pc[x][0])pc[x][0]=i; // 数字x第1次出现 
			else pc[x][1]=i; // 数字x第2次出现 
  	  	}
  	  	
  	  	// 特判序列 S 中每个数字出现次数不都为 2 的情况
  	  	for(i=1;i<=n;i++)if(!pc[i][0]||!pc[i][1])break;
  	  	if(i<=n){
  	  	  	puts("0"); // 此时答案为 0
  	  	  	continue;
  	  	}
  	  	
  	  	// 初始化f 
  	  	for(i=1;i<=n;i++)for(j=0;j<2;j++)f[i][j]=0;
  	  	
  	  	// dp转移，时间复杂度 O(n)
  	  	for(j=0;j<2;j++){
  	  	  	x=pc[a[1]][j];
  	  	  	if(check(1,x-1,1,x-1))f[1][j]=1;
  	  	}
  	  	for(i=1;i<n;i++){ // 枚举 P 的前 i 项匹配上了 S 
			for(j=0;j<2;j++){ // Pi 匹配 S 中数字 Pi 第 j 次出现的位置
				if(f[i][j]){ 
		  	  	  	x=pc[a[i]][j];
		  	  	  	for(k=0;k<2;k++){
		  	  	  	  	y=pc[a[i+1]][k];
		  	  	  	  	if(y<=x)continue;
		  	  	  	  	if(check(x-i+1,y-i-1,x+1,y-1))up(f[i+1][k],f[i][j]); // 匹配成功则转移 
		  	  	  	}
		  	  	}
			}
  	  	}

  	  	
  	  	ans=0; // 记录答案 
  	  	for(j=0;j<2;j++){
			if(f[n][j]){
	  	  	  	x=pc[a[n]][j];
	  	  	  	if(check(x-n+1,n,x+1,n+n))up(ans,f[n][j]); // 匹配成功则累加答案 
	  	  	}
  	  	}
  	  	printf("%d\n",ans); // 输出 
  	}
}
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
73
74
75
76
77
78
79
80
81
82
83

---

1002题 Boss Rush / 打Boss

题目大意

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

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

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

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

#include
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);
    }
}
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

---