【过题记录】 7.29 （杭电，环形dp）

昵称检索

跳到每个名字最前面的最后一位之后暴力枚举月份
然后对应月份枚举日期
将答案累加即可

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6+100;
int Ne[N][26] , st[26];
int Nen[N][26];
int now[26],nowd[26];
int f[N],di[N];
int num[N];
int n,m;
string name[N];
string s;
bool isr[] = {0,1,0,1,0,1,0,1,1,0,1,0,1};

int Do(int x){
	int S = 0;
	for (int i = 0; (1<<i) <= x; i++)
	  if ((x>>i)&1) S++;
	return S;
}

void Work(){
	cin>>n>>m;
	cin>>s;
	for (int i = 1; i <= n; i++) cin>>name[i];
	for (int i = 0; i < 26; i++) st[i] = m+1,now[i] = m+1;
	for (int i = 0; i <= 9; i++) nowd[i] = m+1;
	for (int i = m-1; i >= 0; i--){
		for (int j = 0; j < 26; j++) Ne[i][j] = now[j];
		now[s[i]-'a'] = i;
	}
	for (int i = 0; i < m; i++)
	  if (st[s[i]-'a'] == m+1) st[s[i]-'a'] = i;
	for (int i = m-1; i >= 0; i--){
		if (s[i]<'0' || s[i]>'9'){
			f[i] = f[i+1]; di[i] = di[i+1]; for (int j = 0; j <= 9; j++) Nen[i][j] = nowd[j]; continue;
		}
		int ch = s[i]-'0';
		for (int j = 0; j <= 9; j++) Nen[i][j] = nowd[j];
		di[i] = di[i+1]; di[i]|=(1<<ch);
		nowd[ch] = i;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		int noww = st[name[i][0]-'a'];
		for (int j = 1; j < name[i].size(); j++){
			if (noww >= m) break;
			noww = Ne[noww][name[i][j]-'a'];
		}
		if (noww >= m) continue;
		for (int j = 0; j <= 1; j++){
			int Noww = Nen[noww][j];
			if (Noww >= m) continue;
			int ma,mi; if (j == 0) ma = 9,mi =1; else ma = 2,mi=0;
			for (int k = mi; k <= ma; k++){
				int Now = Nen[Noww][k];
				if (Now >= m) continue;
				int mon = j*10+k;
				for (int dd = 0; dd <= 2; dd++){
					int Nowd = Nen[Now][dd];
					if (Nowd >= m) continue;
					ans+=num[di[Nowd+1]];
					if (dd == 0 && (di[Nowd+1]&1)) ans--;
				}
				if (mon!=2){
					int Nowd = Nen[Now][3];
					if (Nowd >= m) continue;
					int Num = di[Nowd+1];
					int s1 = (Num&1),s2 = ((Num>>1)&1);
					if (isr[mon]) ans+=s1+s2; else ans+=s1;
				}
			}
		}
	}
	cout<<ans<<endl;
	for (int i = 0; i < m; i++) f[i] = 0,di[i] = 0;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	for (int i = 0; i < (1<<10); i++) num[i] = Do(i);
	int t; cin>>t; while (t--) Work();
	return 0;
}
/*
100
4 15
a05bcd022931130
a
b
c
d
*/

最优k子段

首先，本题要我们求最大的最小值
直接二分答案，二分那个最小值
注意到本题的数据是均匀随机的，而质数的密度在随机的情况下约等于
$$1/logn$$
Check的时候，对于一个位置i，就是想找到一个位置j，满足：
$$sum[i]-sum[j]>=x\&\&isp(i-j)$$
我们把 { s u m [ j ] , j } \{sum[j],j\} {sum[j],j}放入set里面
对于位置i，在set里面从小到大找j，直到找到满足条件的j即可。
又由于数据随机分布，所以根据质数密度，每$logn$里面必然有一个质数
所以set只需要存储$logn$哥数据即可
时间复杂度$(n\ast logn\ast logans)$
对于随机均匀生成的数据，可以用期望次数去理解。
真是长见识了

#include<iostream>
#include<set>
using namespace std;

const int N = 2e5+10;

typedef pair < int , int > pii;
int n,k;
int a[N];
bool isp[N];

bool Isp(int x){
	for (int i = 2; i*i <= x; i++)
	  if (x%i == 0) return 0;
	return 1;
}

set < pii > s;
int sum[N];
bool Check(int x){
	int cnt = 0;
    s.clear();
    s.insert({0,0});
	for (int i = 1; i <= n; i++){
		sum[i] = sum[i-1]+a[i];
		s.insert({sum[i],i});
		while (s.size() > 20) s.erase(prev(s.end()));
		set<pii>::iterator it;  
		for (it = s.begin(); it != s.end(); it++){
			int fi = (*it).first , se = (*it).second;
			if (sum[i]-fi >= x && isp[i-se]){
				cnt++;
				s.clear();
				sum[i] = 0; s.insert({0,i});
				break;
			}
		}
	}
	return cnt >= k;
}
int noww = 0;
void Work(){
    noww++;
	cin>>n>>k;
	for (int i = 1; i <= n; i++) cin>>a[i];
	if (k*2 > n){
		printf("impossible\n");
		return;
	}
	int l = -2010 , r = 2e8;
	while (l+1 < r){
		int Mid = l+r>>1;
		if (Check(Mid)) l = Mid; else r = Mid;
	}
	if (Check(r)) printf("%d\n",r); else if (Check(l)) printf("%d\n",l); else printf("impossible\n");
	return;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	isp[1] = 0;
	for (int i = 2; i < N; i++) isp[i] = Isp(i);
	int t; cin>>t; while (t--) Work();
    return 0;
}

Naptime G

这是一个环形dp
拿到这个题，我的第一想法是设$f[i][j]$表示前i个时刻，睡了j分钟的最大值。
但是这样转移显然要$n^3$，会超时。
所以我们考虑转换dp状态
$f[i][j][0/1]$表示前i个时刻，睡了j分钟，当前分钟睡/不睡的最大值
这样转移就简单了:
$$f[i][j][1]=max(f[i-1][j-1][1]+a[i],f[i-1[j-1][0])$$
$$f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1])$$
答案就是$max(f[n][b][0],f[n][b][1])$
初值就是$f[1][0][0]=f[1][1][1]=f[1][1][0]=0$
但是这样子是没有环的答案
显然这道题是有环的
那么怎么处理环呢？
对于环的问题，我们有两种一般的处理思路：
第一种是倍长，第二种是强制连接。
我刚开始选择了第一种，但是发现转移会有问题。
可能一天睡了两次。
这样是不行的。
所以这次我们选择第二种，强制连接。
也就是说，强制让n和1连接
放在这道题来说，就是强制让n号点和1号点都睡觉
这样环就连起来了
这时候，初值就是:
$f[1][1][1]=a[1],f[1][1][0]=0,f[1][0][0]=0$
而后答案就是$f[n][b][1]$
这样就做到了强制连接
另外这题因为会卡内存所以需要用到滚动数组

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3831;
int n,b;
int a[N*2];
int f[3][N][2];
int sum[N];

int ans = 0;

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>b;
	for (int i = 1; i <= n; i++) cin>>a[i];
	for (int i = n+1; i <= 2*n; i++) a[i] = a[i-n];
	for (int i = 1; i <= 2*n; i++) sum[i] = sum[i-1]+a[i];
	memset(f,-0x3f,sizeof f);
	f[1][0][0] = 0; f[1][1][1] = 0; f[1][1][0] = 0;
	for (int i = 2; i <= n; i++){
	    f[i&1][0][0] = f[i-1&1][0][0];
		for (int j = 1; j <= b; j++)
	      f[i&1][j][1] = max(f[i-1&1][j-1][0],f[i-1&1][j-1][1]+a[i]),f[i&1][j][0] = max(f[i-1&1][j][1],f[i-1&1][j][0]);
	}
	ans = max(f[n&1][b][0],f[n&1][b][1]);
	memset(f,-0x3f,sizeof f);
	f[1][1][1] = a[1]; f[1][1][0] = 0; f[1][0][0] = 0;
	for (int i = 2; i <= n; i++){
	    f[i&1][0][0] = f[i-1&1][0][0];
		for (int j = 1; j <= b; j++)
	      f[i&1][j][1] = max(f[i-1&1][j-1][0],f[i-1&1][j-1][1]+a[i]),f[i&1][j][0] = max(f[i-1&1][j][1],f[i-1&1][j][0]);
	}
	ans = max(ans,f[n&1][b][1]);
	cout<<ans<<endl;
}
/*
16 10
0
0
13
0
0
12
12
0
0
10
10
10
10
10
10
10
*/