Reincarnation

正因为梦易碎，才格外美好。

号家军集训 动态规划选做

发表于 更新于 分类于
本文字数： 7k 阅读时长 ≈ 6 分钟

讲师：张隽恺

Loj3215 Muzyka pop

题目简介

题目名称：

题目来源：

评测链接 ：https://loj.ac/p/3215
评测链接 ：https://www.luogu.com.cn/problem/P5985

形式化题意：给定 以及一个长度为 的权值序列 ，要求你构造出一个长度为 的贡献序列 ，满足以下条件：

  • （请注意，这里还有一种说法是 ，但似乎不会影响写法）
  • 最大。（ 是 二进制表示下 的个数）

数据范围：

你发现 的范围像是一个区间 ，而 的范围又像是个数位 ，所以我们考虑一个比较经典的 ，在数位限制下跑区间 。

记 表示当前最高二进制位为 ，仅考虑区间 内的贡献，是否卡着 的上界的最大贡献。

而我们考虑 单调递增，那么考虑二进制上单独一位，会存在一个 使得 该位为 ，而 该位为 ，想清楚过后，这个转移就很明显了：

然后考虑 的限制，也就是数位 常见的卡上界转移。这里要区间 ，所以递推式可能会好写点。

需要注意的是，虽然似乎题面上要求 两两不同，但似乎所有人的写法中都没有强调这一点，笔者不清楚是否为什么 。

AC Code
 
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
// ----- Eternally question-----
// Problem: #3215. 「PA 2019」Muzyka pop
// Contest: LibreOJ
// URL: https://loj.ac/p/3215
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-09-06 19:06:42
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e2+10,MAXNUM=1e2+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int B=62;
int N;
ll M,val[MAXN],pre[MAXN];
ll Dp[MAXNUM][MAXN][MAXN][2];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M),M<<=1;
	for(int i=1;i<=N;++i) read(val[i]);
	for(int i=1;i<=N;++i) pre[i]=pre[i-1]+val[i];
	for(int len=2;len<=N;++len)
		for(int l=1;l+len-1<=N;++l)
		{
			int r=l+len-1;
			Dp[0][l][r][0]=Dp[0][l][r][1]=-INF;
		}
	for(int i=1;i<=B;++i)
		for(int op=0;op<=1;++op)
			for(int len=1;len<=N;++len)
				for(int l=1;l+len-1<=N;++l)
				{
					int r=l+len-1;
					Dp[i][l][r][op]=-INF;
					for(int k=(!op||((M>>i)&1)?l-1:r);k<=r;++k)
					{
						ll tmp=Dp[i-1][l][k][op&!((M>>i)&1)]+Dp[i-1][k+1][r][op]+pre[r]-pre[k];
						checkMax(Dp[i][l][r][op],tmp);
					}
				}
	write(Dp[B][1][N][1]);
	return 0;
}
/*

*/

CF1290F Making Shapes

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1290/F

形式化题意：有 个向量 ，你需要用这些向量（可以多次使用）形成一个封闭的凸多边形，且要求这个凸多边形的横纵坐标极差均不超过 ，求构成的凸多边形的个数。对 取模。

数据范围：，保证不存在 向量，以及不存在向量两两共线。

考虑转化题意为构造一个非负整数序列 满足：

  • ；
  • ；
  • 。

因为要求是一个凸多边形，所以一定是首先一段正，然后在中间某一部分某一个轴变成了负数，之后二者均为负数。

而 这个条件可以视作 ，所以我们考虑正负分别维护， 维同理。

我们考虑将 视作数位的限制，并对 （分别表示 维的正数和和负数和）按位求和。那么现在有一个问题在于位与位之间的进位处理，但显然因为 的范围较小，所以实际进位不会超过太大，所以我们从低位开做之后不用怎么管进位的问题，只需要继承 即可。然后维护 对于 的限制即可，状压转移。

时间复杂度 。

AC Code
 
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
// ----- Eternally question-----
// Problem: F. Making Shapes
// Contest: Codeforces - Codeforces Round 616 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1290/F
// Memory Limit: 768 MB
// Time Limit: 5000 ms
// Written by: Eternity
// Time: 2023-09-06 19:51:05
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=35,MAXM=25;
const int Mod=998244353;
int X[MAXM],Y[MAXM],N,M;
int Dp[MAXN][MAXM][MAXM][MAXM][MAXM][2][2];
inline bool get(bool f,bool cur,bool ref)
{
	if(cur!=ref) return cur>=ref;
	return f;
}
int Dfs(int pos,int a,int b,int c,int d,bool lim1,bool lim2)
{
	if(!(M>>pos)) return (!a)&&(!b)&&(!c)&&(!d)&&(!lim1)&&(!lim2);
	int &res=Dp[pos][a][b][c][d][lim1][lim2];
	if(~res) return res;
	res=0;
	int bit=M>>pos&1,s=(1<<N)-1;
	for(int i=0;i<=s;++i)
	{
		int _a=a,_b=b,_c=c,_d=d;
		for(int j=1;j<=N;++j)
			if(i>>(j-1)&1)
			{
				X[j]>0?_a+=X[j]:_c-=X[j];
				Y[j]>0?_b+=Y[j]:_d-=Y[j];
			}
		if((_a&1)==(_c&1)&&(_b&1)==(_d&1))
			res=(res+Dfs(pos+1,_a>>1,_b>>1,_c>>1,_d>>1,get(lim1,_a&1,bit),get(lim2,_b&1,bit)))%Mod;
	}
	return res;
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int i=1;i<=N;++i) read(X[i],Y[i]);
	std::memset(Dp,-1,sizeof(Dp));
	write((((Dfs(0,0,0,0,0,0,0)%Mod-1+Mod)%Mod)+Mod)%Mod);
	return 0;
}
/*

*/
相关文章