A 摘苹果

题目描述：

关卡管理员每天都会摘一些苹果，具体的，在第 $i$ 天，关卡管理员会得到 $i^2$ 个苹果，比如第一天 $1$ 个苹果，第二天 $4$ 个苹果，第三天 $9$ 个苹果。

每天的苹果关卡管理员都会留下来，关卡管理员想知道他如果想攒下至少 $k$ 个苹果，需要最少多少天。

关卡管理员会问旅行者 $Orz$ 很多个问题，需要一一作出回答。

输入描述：

输入多行。

每行输入一个整数 $k$ 表示关卡管理员想要攒下的苹果数量。

$k=0$ 作为终止标记，并不是表示做了一次 $k=0$ 的询问，而是说没有问题了，询问结束，不需要再回答。

输出描述：

输出多行。

对于每个询问输出一个整数表示关卡管理员最少需要的天数。

样例 #1

5
15
0

2
4

说明/提示：

• 【样例解释】：
• 对于第一组测试数据：第 $1$ 天摘到 $1^2$ 个苹果，第 $2$ 天摘到 $2^2$ 个苹果，一共摘到 $1^2 + 2^2 = 1 + 4 = 5$ 个苹果。所以需要 $2$ 天时间。

数据范围：

• 记询问次数为 $T$ 。

  对于 $20\%$ 的数据 $k \le 15,T=1$ 。

  对于另外 $20\%$ 的数据 $k \le 100$ 。

  对于另外 $40 \%$ 的数据 $k \le 10^6$ 。

  对于全部数据满足 $T \le 1000,0 \le k$

参考代码

#include <bits/stdc++.h> 

using namespace std;      
using ll = long long; 

// 安全计算 S(d) = 1^2 + ... + d^2
ll sum_sq(ll d) {
    if (d <= 0) return 0; // 处理边界情况
    ll p1 = d;
    ll p2 = d + 1;
    ll p3 = 2 * d + 1;

    // 执行除以 2
    if (p1 % 2 == 0) p1 /= 2;
    else p2 /= 2;

    // 执行除以 3
    if (p1 % 3 == 0) p1 /= 3;
    else if (p2 % 3 == 0) p2 /= 3;
    else p3 /= 3;

    // 此时相乘结果即为 S(d)，且不会溢出 long long
    return p1 * p2 * p3;
}

int main() {
    // IO 优化
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);

    ll k; // 目标苹果数
    // 循环读入，直到 k 为 0
    while (cin >> k && k != 0) {
        ll l = 1, r = 2000000; // 二分查找的天数范围 [l, r]
        ll ans = r;          // 初始化答案为上界

        // 开始二分查找
        while (l <= r) {
            ll mid = l + (r - l) / 2; // 计算中间天数
            ll s = sum_sq(mid);      // 计算 mid 天的总苹果数

            if (s >= k) { // 苹果数已足够或超过
                ans = mid;      // mid 是一个可能的解，记录下来
                r = mid - 1;    // 尝试更少的天数
            } else { // 苹果数不足
                l = mid + 1;    // 需要更多的天数
            }
        }
        // 输出找到的最小天数
        cout << ans << "\n";
    }

    return 0;
}

题解

本题要求找到最少的天数，使得累计摘到的苹果数量至少为 $k$。第 $i$ 天摘 $i^2$ 个苹果，所以 $d$ 天累计的苹果数是平方和 $S(d) = \sum_{i=1}^{d} i^2 = \frac{d(d+1)(2d+1)}{6}$。 观察到累计苹果数随天数增加而单调递增，因此可以使用二分答案的方法来查找满足条件的最少天数。 二分查找的范围可以设定一个合理的上界（例如，当 $d \approx \sqrt[3]{3k}$ 时，$d^3/3 \approx k$，对于 $k=10^6 \times 1000 = 10^9$（假设 $k$ 的最大值是 $10^6$ 且 $T$ 很大，但 $k$ 的实际最大值是 $10^6$。实际 $k$ 上限是 $10^{18}$ 如果 $d^3/3 \approx k$），$d$ 大约是 $1.4 \times 10^6$，代码中设定为 $2 \times 10^6$ 足够）。 对于每个二分的 mid 天，计算 sum_sq(mid)。如果 sum_sq(mid) >= k，说明 mid 天可能是一个解，尝试在 [l, mid-1] 区间找更少的天数；否则，说明天数不足，需要在 [mid+1, r] 区间找。 sum_sq 函数中，为了避免乘法溢出和保证整除，先分别对 $d, d+1, 2d+1$ 中的某些项执行除以2和除以3的操作。因为 $d(d+1)$ 必为2的倍数， $d(d+1)(2d+1)$ 必为3的倍数。

B 考试秘籍

说明

派蒙做了一个好梦，梦里他误入了一个神秘山洞，洞里长了一棵参天巨树，树上长满了各种学习资料和参考答案（数学的），派蒙一眼就瞄上了那本考试秘籍，里面写了未来百年内的考试答案，派蒙心想这下自己不是无敌了吗。

可是看守巨树的隐山猊兽不允许派蒙摘走整本秘籍，派蒙献出了唯一一根棒棒糖，隐山猊兽才允许他撕下几页。

派蒙想带走 $a$ 页到 $b$ 页，请问派蒙至少得撕下几张纸带走呢？

注意，书的第 11 页和第 12 页在同一张纸上，但是 12 页和 13 页不在同一张纸上。

输入格式

输入两个整数，分别代表 $a$ 和 $b$。

输出格式

输出需要撕掉的张数。

样例

2 7 

4

提示

样例解析： 

第 2 ~ 7 页分别在第 1,2,3,4 张上，所以需要撕掉 4 张。 

数据范围： 

1 <= a <= b <= 10⁸。

参考代码

#include <bits/stdc++.h> 

using namespace std;
using ll = long long; 

int main() {
    ios::sync_with_stdio(0); // 关闭同步流
    cin.tie(0);
    cout.tie(0);

    int a, b; // 输入的起始页码和结束页码
    cin >> a >> b;

    // 书的装订方式：第 (2k-1) 页和第 (2k) 页在同一张纸上。
    // 因此，页码 p 所在的纸张编号可以计算为 (p+1)/2 (使用整数除法)。
    // 例如：
    // 页1: (1+1)/2 = 1号纸
    // 页2: (2+1)/2 = 1号纸
    // 页3: (3+1)/2 = 2号纸

    // 计算起始页码 a 所在的纸张编号 sa
    int sa = (a + 1) / 2; 

    // 计算结束页码 b 所在的纸张编号 ea
    int ea = (b + 1) / 2;

    // 需要撕掉的纸张包括从第 sa 张到第 ea 张 (含首尾)。
    // 总张数为 ea - sa + 1。
    int res = ea - sa + 1;

    cout << res << endl;

    return 0;
}

题解

题目描述了书页的装订方式：第1页和第2页在同一张纸上，第3页和第4页在同一张纸上，以此类推。这意味着奇数页 $p$ 和偶数页 $p+1$ 在同一张纸上。 我们可以找到一个规律来确定任意页码 $x$ 所在的纸张是第几张。

• 页码 1, 2 在第 1 张纸上。
• 页码 3, 4 在第 2 张纸上。
• 页码 $2k-1, 2k$ 在第 $k$ 张纸上。 由此可见，页码 $x$ 所在的纸张编号是 $\lceil x/2 \rceil$。在整数除法中，这等价于 (x + 1) / 2。 所以，要带走从第 $a$ 页到第 $b$ 页的内容，我们首先需要确定第 $a$ 页所在的纸张编号 sa = (a + 1) / 2，以及第 $b$ 页所在的纸张编号 ea = (b + 1) / 2。 需要撕下的总张数就是从第 sa 张到第 ea 张（包括这两张），即 ea - sa + 1。

C 填补问号

题目描述

可鲁贝洛斯 拥有一个包含小写英文字母和?的字符串，其中?表示一个未知的小写英文字母。

可鲁贝洛斯 首先将所有的?替换为小写英文字母，在所有的替换情况中，是否存在一个字符串中有且仅有一个"demontheone"这样的子串。

子串：字符串中任意个连续的字符组成的子序列称为该串的子串。例如原字符串为："abdemontheonep"，其中"demontheone"就是原字符串的一个子串。

输入格式

第一行，一个整数$T$，表示可鲁贝洛斯 有$T$个字符串。对于每次字符串，均需要回答问题。

接下来$T$行，每行一个字符串，其中字符串中只包含小写英文字母和字符?，第$i$行，表示可鲁贝洛斯 的第$i$个字符串。

输出格式

输出共$T$行，每行输出"Yes"或"No"，若可鲁贝洛斯的第$i$个字符串经过合理替换后，有且仅有一个"demontheone"这样的子串，则输出"Yes"，否则输出"No"。

3
abc?emontheone
demont?e?ne
demn?theone

Yes
Yes
No

样例解释1

对于第一个字符串，如果将第一个?替换为d，则替换后的字符串为"abcdemontheone"，内部存在唯一的一个子串"demontheone"，所以输出"Yes"。

对于第二个字符串，如果将第一个?替换为 'h'，第二个?替换为o，则替换后的字符串为"demontheone"，内部存在唯一的一个子串"demontheone"，所以输出"Yes"。

对于第三个字符串，无论怎么替换，均不存在"demontheone"这样的子串，所以输出"No"。

3
abc?demontheone??
?demontheonedemontheone
demontheo?edemontheon?

Yes
No
Yes

样例解释2

对于第一个字符串，如果将三个?均替换为a，则替换后的字符串为"abcademontheoneaa"，内部存在唯一的一个子串"demontheone"，所以输出"Yes"。

对于第二个字符串，无论怎么替换?，字符串中最少有两个demontheonedemontheone这样的子串，所以输出"No"。

对于第三个字符串，如果将第一个?替换为 'n'，第二个?替换为a，则替换后的字符串为"demontheonedemontheona"，内部存在唯一的一个子串"demontheone"，所以输出"Yes"。

数据范围

对于$60\%$的数据，满足字符串中?的个数最多有一个。

对于$100\%$ 的数据，满足$1 \le T \le 8$，每个字符串的长度$\le 100$ ，每个字符串中有若干个?。

格式说明

输出时每行末尾的多余空格，不影响答案正确性

参考代码

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

string aa = "demontheone";

bool is_aa(int k, string s) {
    for (int i = k; i < k + 11; i++) {
        if (s[i] != aa[i - k]) {
            return 0;
        }
    }
    return 1;
}

void solve() {
    string s; cin >> s;
    if (s.length() < 11) {
        cout << "No\n";
        return ;
    }
    vector <int> w;
    int cnt = 0;
    int len = s.length();
    for (int i = 0; i < len - 10; i++) {
        if (is_aa(i, s)) {
            cnt++;
        }
        if (s[i] == '?') w.push_back(i);

    }
    if (cnt >= 2) {
        cout << "No\n";
        return ;
    }
    else if (cnt == 1) {
        cout << "Yes\n";
        return ;
    }
    int it = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == aa[it] || s[i] == '?') {
        	it++;
        	if (it == 11) {
        		cout << "Yes\n";
        		return ;
			}
		} 
		else {
			it = 0;
		}
    }
    cout << "No\n";
}

int main() {
    int T; cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D 01串

说明

派蒙 拿到了一个 $01$ 串，她准备将若干个字符'1' 染成红色，将若干个字符'0' 染成蓝色，但有个限制：如果一个'0' 和一个'1' 相邻，那么它们不能同时染色。

派蒙 想知道，最多可以染多少个字符？

输入格式

输入仅有一行字符串$s$，为派蒙拿到的 $01$ 串。

字符串长度$|s|$不超过$200000$。

输出格式

一个正整数，代表能染色的最多字符。

110011

4

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int vis[N];

int main(){
	
	string s;
	cin >> s;
	int ans = 1;
	vis[0] = 1;
	for(int i = 1;i <s.size();i++){
		if(s[i] == s[i-1]){
			ans ++;
			vis[i] = 1;
		}
		else{
			if(vis[i-1] == 0) {
				ans ++;
				vis[i] = 1;
			}
		}
	}
	
	cout << ans;
	
	return 0;
}

题解

题目要求对一个01串进行染色，'1'染红色，'0'染蓝色。限制是相邻的'0'和'1'不能同时染色。目标是最大化染色字符的数量。

这是一个贪心问题。我们从左到右遍历字符串：

1. 第一个字符：无论它是什么，总可以对它进行染色。因为没有更左边的字符与它形成限制。
2. 对于后续字符 s[i] (i > 0)：
   • 如果 s[i] 与 s[i-1] 相同 (例如都是'0'或都是'1')： 这两个字符如果要染色，会被染成相同的颜色（比如两个'0'都染蓝色）。它们之间没有“相邻的'0'和'1'”这种情况，所以如果 s[i-1] 能染，s[i] 也能染。更进一步，由于它们相同，它们不会互相限制。因此，如果决定染 s[i]，它不会与 s[i-1] 产生冲突，因为它们颜色相同。所以，只要 s[i] 和 s[i-1] 相同，s[i] 就可以染色。
   • 如果 s[i] 与 s[i-1] 不同 (一个是'0'，一个是'1')： 这种情况下，它们是相邻的'0'和'1'。根据规则，它们不能同时染色。为了最大化染色数量，我们采取贪心策略：如果 s[i-1] 没有被染色，那么我们就可以染 s[i]。如果 s[i-1] 已经被染色了，那么 s[i] 就不能再染了。

代码实现：

• 使用 vis 数组记录每个字符是否被染色。
• 初始化 vis[0]=1，ans=1，表示第一个字符被染色。
• 从第二个字符开始遍历：
  • 如果 s[i] == s[i-1]，则 vis[i]=1，ans++。
  • 如果 s[i] != s[i-1]：
    • 检查 vis[i-1]。如果 vis[i-1] == 0 (前一个没染)，则 vis[i]=1，ans++。

这个贪心策略保证了局部最优，并且由于决策只依赖于前一个字符的状态，可以推广到全局最优。

E 派蒙计数

题目描述

派蒙 有一个 $n$ 长序列 $A = a_1,...,a_n$，他想知道同时满足以下条件的四元 $(i,j,k,l)$ 的数量：

• $1 \leq i \lt j \lt k \lt l \leq n$
• $a_i \leq a_j \leq a_k \leq a_l$。

输入格式

第一行一个正整数 $n$，

第二行 $n$ 个整数 $a_1,...,a_n$。

输出格式

一个整数表示答案。

8
1 2 3 3 4 3 2 1

9

6
1 1 1 2 2 3

15

提示

【数据范围】

对于所有数据：$1 \leq n \leq 5 \times 10^3，1 \leq a_i \leq 10^{9}$。

测试点编号	$n$
$1 \sim 6$	$n\leq 10^2$
$7 \sim 20$	$n\leq 5 \times 10^3$

参考代码

DP版本

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
int a[5005];
ll dp[5][5005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n < 4) {
        cout << 0 << "\n";
        return 0;
    }

    for (int i = 0; i < n; ++i) {
        dp[1][i] = 1LL; 
    }

    for (int l = 2; l <= 4; ++l) { 
        for (int i = 0; i < n; ++i) { 
            dp[l][i] = 0LL; 
            for (int j = 0; j < i; ++j) { 
                if (a[j] <= a[i]) {
                    dp[l][i] += dp[l-1][j]; 
                }
            }
        }
    }

    ll ans = 0LL;
    for (int i = 0; i < n; ++i) {
        ans += dp[4][i]; 
    }

    cout << ans << "\n";

    return 0;
}

题解

题目要求计算满足 $1 \leq i < j < k < l \leq n$ 且 $a_i \leq a_j \leq a_k \leq a_l$ 的四元组 $(i,j,k,l)$ 的数量。这本质上是求解长度为4的非降子序列的数量。

我们可以使用动态规划（DP）来解决这个问题。 定义 dp[len][idx] 为：以序列中第 idx 个元素 a[idx] 结尾的，长度为 len 的非降子序列的数量。

状态初始化： 对于长度为1的非降子序列：任何单个元素 a[idx] 本身都构成一个长度为1的非降子序列。 所以，dp[1][idx] = 1 对于所有的 0 \leq idx < n。

状态转移： 我们要计算 dp[len][i]（以 a[i] 结尾，长度为 len 的非降子序列）。 这个子序列的前 len-1 个元素构成了以某个 a[j]（其中 j < i 且 a[j] \leq a[i]）结尾的、长度为 len-1 的非降子序列。 因此，状态转移方程为： dp[len][i] = sum(dp[len-1][j]) 对于所有 0 \leq j < i 且 a[j] \leq a[i]。

我们依次计算 len 从 2 到 4 的 dp 值：

• dp[2][i] = sum(dp[1][j]) for j < i, a[j] <= a[i]
• dp[3][i] = sum(dp[2][j]) for j < i, a[j] <= a[i]
• dp[4][i] = sum(dp[3][j]) for j < i, a[j] <= a[i]

最终答案： 所求的四元组数量，就是所有以任意元素结尾的、长度为4的非降子序列数量的总和。 ans = sum(dp[4][i]) 对于所有的 0 \leq i < n。

代码中的数组索引从0开始，逻辑与上述描述一致。

另解

直接计数

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

const int N = 5010;

int L[N],R[N],a[N];

signed main(){
	
	int n;cin >> n;
	
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
	}
	
	// 预处理L数组 L[i]:表示 i的左侧有多少个元素小于等于a[i]
	
	// 预处理R数组 R[i]:表示 i的右侧 有多少个元素大于等于a[i]
	
	for(int i = 1;i <= n;i ++){
		// L[i]
		
		for(int j = 1;j < i;j ++){
			if(a[j] <= a[i]) L[i] ++;
		}
	}
	
	
	for(int i = n;i >= 1;i --){
		for(int j = i + 1;j <= n;j ++){
			if(a[j] >= a[i]) R[i] ++;
		}
	}
	
	// 枚举四元组 中间的两个元素
	
	int ans = 0;
	
	for(int j  = 1;j <= n;j ++){
		for(int k = j + 1;k <= n;k ++){
			// j < k
			
			if(a[j] <= a[k])
				ans += L[j] * R[k];
		}
	}
	
	cout << ans;
	
	
	
	return 0;
}