2022.5.2 比赛题整理

2022.5.2 2022初一测试五

链接集合

80 + 80 + 20 + 0 = 180 80 + 80 +20 + 0 = 180 80+80+20+0=180

会拿部分分了，有进步。

T1：模拟，最后一个大数据打表。

T2：概率问题，贪心。

T3：找规律/性质，模拟。

dp 好题 {color{Red}{text{dp 好题}}} dp 好题T4：dp + 前缀和 + 预处理最长相同前缀长度。

bitset 可以节省空间！！ {color{Red}{text{bitset 可以节省空间！！}}} bitset 可以节省空间！！

1. n ≤ 1 0 6 n leq 10^6 n≤106

   此时开个 bitset 作为标记，然后根据题意模拟即可。

2. n = 299999995 n = 299999995 n=299999995

   此时把 bitset 开大，模拟，跑这个点，挂机出答案。

v i s vis vis 开 bool 类型的数组也可以。

#include
using namespace std;

#define int long long
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
const int maxn = 1e8 + 5;
int n, t;
bitset vis;

signed main()
{
	scanf("%lld", &n);
	if(n == 299999995) {printf("1199999979n"); return 0;};
	rep(i, 1, n)
	{
		t = i;
		while(vis[t]) t += i;
		vis[t + i - 1] = 1;	
	} 
	printf("%lldn", t + n - 1);
	return 0;
}

贪心。

策略就是从大到小遍历，每次计算选择了当前硬币后的概率，比较选和不选的大小，大则选，小则结束遍历即可（因为是从大到小遍历的，所以后面的数只会让概率更小）。

关于计算选择后概率：

开两个变量， u p up up 和 d o w n down down，

u p up up 累计的，都是已经选定某个硬币朝上，所以与 u p up up 相乘的，都是 ( 1.0 − a [ j ] ) (1.0-a[j]) (1.0−a[j])；

d o w n down down 累计的，都是没有选定哪个硬币朝上，而每加入一个硬币 j j j，都先把 a j a_j aj​ 与 d o w n down down 相乘，代表选定这个硬币朝上，再把这个乘积累计进 u p up up 中，最后给 d o w n down down 乘上 ( 1.0 − a j ) (1.0-a_j) (1.0−aj​)，为下一次选新的硬币朝上做准备。

最后的答案当然就是 u p up up。

#include
using namespace std;

#define rep(i, a, b) for(register int i = a; i <= b; ++i)
int n;
double a[205];
long long st;
double ans;

int main()
{
//	freopen("D:/0502Bin.txt", "r", stdin);
	scanf("%d", &n);
	st = 1 << n;
	rep(i, 1, n) cin >> a[i];
	sort(a + 1, a + n + 1);
	double up = a[n], dn = 1.0 - a[n];
	for(int i = n - 1; i >= 1; --i)
	{
		if(up * (1.0 - a[i]) + dn * a[i] > up)
			up = up * (1.0 - a[i]) + dn * a[i],
			dn *= (1.0 - a[i]);
		else break;
	} 
	printf("%.7lfn", up);
	return 0;
} 

首先不难发现，当把房子围成一个正六边形时，长度最小。

然后我们还能得到，对于边长为 ( a + 1 ) (a+1) (a+1) 的正六边形（ a > 0 a>0 a>0），它的长度可以表示为 6 a 6a 6a。

这样我们就可以在房子里面掏去一个最大的正六边形，剩下多出的房子在该正六边形每条边上扩充即可。

关于扩充，给出下面这张丑图：（我尽力了，没办法它就是丑）

此时最大的这个正六边形边长为 4， a a a 为 3。

绿色边围出的就是房子中掏去的最大的一个正六边形，红色边则是第一次对一条边进行扩充，灰色边表示扩充前的边。

蓝色边围出的是第二次对第一次扩充的边的邻边进行扩充的结果。

不难发现，对于第一次的扩充，扩充后长度仅仅比原先多 1，但可以多容下 2 个房子（还有你会发现只扩 1 个位置出来和扩 2 个位置出来长度都是增加 1）。

而对于第二次的扩充，长度也只比原先多 1，但可以多容下 3 个房子，之后的每一次扩充，都和第二次一样，能多容下 a a a 个房子。

#include
using namespace std;

int n, ans;

int main()
{
	scanf("%d", &n), n -= 1;
	if(!n) {printf("6n"); return 0;}
	int a = 1;
	while(n >= a * 6) n -= a * 6, a += 1;//掏出一个最大的正六边形
	ans = a * 6;
	if(!n) {printf("%dn", ans); return 0;}
	ans += 1, n -= a - 1;//开始扩充
	while(n > 0) n -= a, ans += 1;
	printf("%dn", ans);
	return 0;
}

首先，看到“分成 k k k 段”，我们就不难想到计数 dp。

设 f i f_i fi​ 代表 s [ 1 , i ] s[1,i] s[1,i]，显然不够，所以我们可以想到设 f i , j f_{i,j} fi,j​，表示在 s [ 1 , i ] s[1,i] s[1,i] 中，最后一个分段是 [ j , i ] [j,i] [j,i]。

这样一来，我们就得到了一个暴力 O ( n 3 ) O(n^3) O(n3) 的做法：

枚举 f i , j f_{i,j} fi,j​，对于每一个 f i , j f_{i,j} fi,j​，枚举 k ∈ [ 1 , j ) k in [1,j) k∈[1,j)，然后对比 s [ k , j − 1 ] s[k,j - 1] s[k,j−1] 和 s [ j , i ] s[j,i] s[j,i] 的大小，如果前者小于后者，则合法，那就给 f i , j f_{i,j} fi,j​ 加上 f k , j − 1 f_{k,j - 1} fk,j−1​。

我们发现，要想降到 O ( n 2 ) O(n^2) O(n2)，需要将上述枚举 k k k 的 O ( n ) O(n) O(n) 降到 O ( 1 ) O(1) O(1)。

转而来看第三档分：字母一样。

这就意味着，对于枚举到的 f i , j f_{i,j} fi,j​， k k k 的取值范围变为 [ m a x ( 1 , 2 ∗ j − i ) , j − 1 ] [max(1,2* j - i),j - 1] [max(1,2∗j−i),j−1]。

2 ∗ j − i 2 * j - i 2∗j−i 怎么来的？由 ( j − 1 ) − k + 1 < i − j + 1 (j - 1) - k + 1 < i - j + 1 (j−1)−k+1

这个可以用前缀和维护，所以在这个数据点上，我们把复杂度降到了 O ( n 2 ) O(n^2) O(n2)。

2 就启发我们用前缀和思想去优化 1。

对于两个字符串 s 1 ,   s 2 s1, s2 s1, s2，我们设他们最长相同前缀长度为 d d d，那么此时这两个字符串的大小关系就取决于 s 1 [ d + 1 ] s1[d+1] s1[d+1] 和 s 2 [ d + 1 ] s2[d + 1] s2[d+1] 的大小关系。

这就引导着我们用一个数组 d i f i , j dif_{i,j} difi,j​ 去记录 s [ 1 , i ] s[1,i] s[1,i] 和 s [ 1 , j ] s[1,j] s[1,j] 的最长相同前后缀的长度。预处理的复杂度为 O ( n 2 ) O(n^2) O(n2)。

此时再反观我们 1 中设的状态，发现如果 f i , j f_{i,j} fi,j​ 代表的是 s [ 1 , i ] s[1,i] s[1,i] 中的划分情况，我们很难用上述的 d i f dif dif 数组进行快速的计算。因为对于 s [ j , i ] s[j,i] s[j,i] 与 s [ k , j − 1 ] s[k,j - 1] s[k,j−1] 中， s [ k , j − 1 ] s[k,j - 1] s[k,j−1] 的起始位置是不确定的。

所以我们考虑把状态反过来。

定义 f i , j   ( i < j ) f_{i,j} (i

定义 d i f i , j   ( i < j ) dif_{i,j} (i

定义 s u m i , j   ( i < j ) sum_{i,j} (i 4

然后我们尝试通过这两个数组来 O ( n 2 ) O(n^2) O(n2) 解决此题。

对于 f i , j f_{i,j} fi,j​，设 d = d i f i , j d = dif_{i,j} d=difi,j​。

• 若 i + d < j i + d < j i+d

  123456789
  abaaababb
  i   j
  

  此时 i = 1 ,   j = 5 ,   d = 3 ,   n = 9 i = 1, j = 5, d = 3, n = 9 i=1, j=5, d=3, n=9，可以发现 k k k 的取值范围就是 8~9。

  我们由此可以得出：当 s [ i + d ] < s [ j + d ] s[i+d]

• 若 i + d ≥ j i + d geq j i+d≥j，例如：

  123456789
  abaabaabb
  i  j 
  

  此时 i = 1 ,   j = 4 ,   d = 5 ,   n = 9 i = 1, j = 4, d = 5, n = 9 i=1, j=4, d=5, n=9，我们还发现 s [ i , j − 1 ] s[i,j - 1] s[i,j−1] 与 s [ j , j + ( j − i ) − 1 ] s[j,j+(j - i) - 1] s[j,j+(j−i)−1] 完全相同。所以为保证字典序严格递增，可以得到 k k k 的取值范围就是 8~9。

  我们由此可以得出：当 j + ( j − i ) ≤ n j+(j-i)leq n j+(j−i)≤n 时， f i , j = s u m j , j + ( j − i ) + 1 f_{i,j} = sum_{j,j+(j-i)+1} fi,j​=sumj,j+(j−i)+1​。

这样就得到 O ( n 2 ) O(n^2) O(n2) 的做法了。

#include
using namespace std;
 
#define rint register int
const int maxn = 3e3 + 5;
const int mod = 1e9 + 7;
char s[maxn];
int n;
int sum[maxn][maxn];
int f[maxn][maxn];
int dif[maxn][maxn];
 
int main()
{
    scanf("%d%s", &n, s + 1);
    for(rint j = n; j; --j)
        for(rint i = j - 1; i; --i)
            dif[i][j] = (s[i] == s[j] ? dif[i + 1][j + 1] + 1 : 0);
    sum[n][n + 1] = 1;
    for(rint i = n - 1; i >= 1; --i)
    {
        for(rint j = i + 1; j <= n; ++j) 
        {
            int k = dif[i][j];
            if(i + k < j) f[i][j] = (s[i + k] < s[j + k] ? sum[j][j + k + 1] : 0);
            else f[i][j] = (j + (j - i) <= n ? sum[j][j + (j - i) + 1] : 0);
        }
        sum[i][n + 1] = 1;
        for(rint j = n; j > i; --j)
            sum[i][j] = (sum[i][j + 1] + f[i][j]) % mod; 
    } 
    printf("%dn", sum[1][2]);
    return 0;
}

期中考RP += inf; //2022-05-04

—— E n d End End——