2024 杭电多校 4 补题
多层血条
模拟, 只会最覆盖最上面的一层血量, 所以不用担心下层血量是什么, 只用找到最上面的那一层是什么即可
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
|
#include <bits/stdc++.h>
using namespace std;
string h="ABCDE";
void solve(){
int n,m,hp,dmg;
cin>>n>>m>>hp>>dmg;
int lst=(hp/m)%5,x=m;
string upp;
upp.resize(m+1,' ');
if(hp<=m){
for(int i=1;i<=hp;i++)upp[i]=h[0],x=i;
}
else{
int rest=hp%m;
// cout<<rest<<endl;
for(int i=1;i<=m;i++){
if(rest)upp[i]=h[lst],x=i,rest--;
else upp[i]=h[(lst-1+5)%5];
}
}
while(dmg){
if(upp[x]=='.')break;
upp[x]='.';
x--;
dmg--;
if(x==0)x=m;
}
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
if((i==0&&j==0)||(i==0&&j==m+1)||(i==n+1&&j==0)||(i==n+1&&j==m+1))cout<<"+";
else if(i==0||i==n+1)cout<<"-";
else if(j==0||j==m+1)cout<<"|";
else cout<<upp[j];
}
cout<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
昵称检索
昵称分姓名和生日两部分, 而姓名需在生日前, 那么就要找尽量前的姓名, 尽量后的生日
预处理 $nxt[i][j]$ 表示 $s[i][n]$ 中字符 $j$ 最靠左的出现位置, 从左到右找到名字的最后一位在哪, 记为 $a[i]$, 同理,倒着求生日的最后一位在哪, 记为 $b[i]$
最后找有多少对 $(i, j)$ 满足 $i < j$ 即可.
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
typedef long long ll;
const int N=1e6+7, mod=1e9+7;
int n,m,ans[N];
int day[15] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
string s,a;
int vis[26],mp[N][26];
int fd(int *u){
int x=m+1;
for(int i=3;~i;i--){
x--;
if(x<1)return 0;
x=mp[x][u[i]];
}
return x;
}
int fc(){
int x=0;
for(int i=0;i<a.size();i++){
x++;
if(x>m)return m+1;
x=mp[x][a[i]-'a'];
}
return x;
}
void solve(){
cin>>n>>m>>s;
for(int i=0;i<10;i++)vis[i]=0;
for(int i=1;i<=m;i++){
if(s[i-1]>='0'&&s[i-1]<='9')vis[s[i-1]-'0']=i;
for(int j=0;j<=9;j++)mp[i][j]=vis[j];
}
for(int i=0;i<=m+1;i++)ans[i]=0;
for(int i=1;i<=12;i++){
for(int j=1;j<=day[i];j++){
int p[4];
p[0]=i/10,p[1]=i%10,p[2]=j/10,p[3]=j%10;
int x=fd(p);
if(x)ans[x]++;
}
}
for(int i=m;i>1;i--)ans[i-1]+=ans[i];
for(int j=0;j<26;j++)vis[j]=m+1;
for(int i=m;i;i--){
if(s[i-1]>='a'&&s[i-1]<='z')vis[s[i-1]-'a']=i;
for(int j=0;j<26;j++)mp[i][j]=vis[j];
}
int sum=0;
while(n--){
cin>>a;
int x=fc();
if(x<m)sum+=ans[x+1];
}
cout<<sum<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
最优 $k$ 子段
前缀和统计区间和, 用二分找答案
开一个 set 存当前前缀和和位置, 判断合法区间条件为, 当前位置能否和 set 中所存的元素构成大于等于 $lim$ 的一个片段, 同时片段长度要为质数, 如果能找到, 就将当前记录个数 + 1.
二分条件即为 check 返回的值是否大于等于 $k$, 需要注意 $k * 2 \leq n$, 因为最小的质数为 2, $k * 2$ 是 $n$ 的最小长度
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
typedef long long ll;
const int N=1e8+7, mod=1e9+7;
bool ip[N];
int n,k;
ll a[N];
int check(int lim){
set<pair<int,int>> s;
s.insert({0,0});
int res=0;
for(int i=1;i<=n;i++){
auto it = s.begin();
while(it != s.end()){
if(a[i] - it->first < lim) it = s.end();
else if(ip[i - it->second]) break;
else it++;
}
if(it != s.end()) res++, s.clear();
s.insert({a[i], i});
}
return res;
}
void solve(){
cin >> n >> k;
for(int i=1; i<=n; i++){
cin >> a[i];
a[i]+=a[i-1];
}
if(2*k > n){
cout << "impossible\n";
return;
}
int l = -2000, r = N;
while(l < r){
ll mid = (l + r + 1) >> 1;
if(check(mid) >= k) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(ip, 1, sizeof(ip));
ip[0] = ip[1] = 0;
for(int i=2; i*i<=N; i++){
if(ip[i]){
for(int j=i*i; j<=N; j+=i) ip[j]=0;
}
}
int t;
cin >> t;
while(t--) solve();
return 0;
}
|