2022年5月1日14:39:50

文章目录

• 2022年5月1日14:39:50
• • A. Subtle Substring Subtraction
  • • 题目大意：
    • 测试样例：
    • 题解：
  • B. A Perfectly Balanced String?
  • • 题目大意：
    • 测试样例：
    • 题解：
  • C. Palindrome Basis
  • • 题目大意：
    • 测试样例：
    • 题解：
    • 附带题目：P1025 [NOIP2001 提高组] 数的划分
  • D. Lost Arithmetic Progression
  • • 题目大意：
    • 测试样例：
    • 题解：
• END:2022年5月1日17:23:38

A. Subtle Substring Subtraction

题目大意：

爱丽丝和鲍勃正在玩弦乐游戏。比赛将进行 $t$ 轮。在每一轮中，都会有一个由小写英文字母组成的字符串s。

爱丽丝首先移动，两个玩家交替轮流。 Alice 可以删除任何偶数长度的子串（可能为空），Bob 可以从 $s$ 中删除任何奇数长度的子串。

更正式地说，如果有一个字符串 s = s 1 s 2 . . . s k s=s_1s_2...s_k s=s1​s2​...sk​，玩家可以选择一个长度为相应奇偶校验的子字符串 s l sl+1 . . . sr−1 s r s_ls_{l+1}...s_{r−1}s_r sl​sl+1​...sr−1​sr​ 并将其删除。之后，字符串将变为 s = s 1 … sl−1 sr+1 … s k s=s_1…s_{l−1}s_{r+1}…sk s=s1​…sl−1​sr+1​…sk。

字符串变空后，回合结束，每位玩家计算本回合的得分。一个玩家的得分是他/她移除的所有角色的值的总和。 a 的值为 1，b 的值为 2，c 的值为 3，……，z 的值为 26。得分较高的玩家获胜。对于每一轮，确定获胜者以及获胜者和失败者得分之间的差异。假设两个玩家都打得最优化以最大化他们的分数。可以证明，平局是不可能的。

输入
输入的第一行包含一个整数 t ( 1 ≤ t ≤ 5 ⋅ 1 0 4 ) t (1≤t≤5⋅10^4) t(1≤t≤5⋅104)，表示轮数。

接下来的 $t$ 行中的每一行都包含一个由小写英文字母组成的字符串 s ( 1 ≤ ∣ s ∣ ≤ 2 ⋅ 1 0 5 ) s (1≤|s|≤2⋅10^5) s(1≤∣s∣≤2⋅105)，表示用于该回合的字符串。这里 $|s|$ 表示字符串 $s$ 的长度。

保证 $|s|$ 的总和总轮次不超过 2 ⋅ 1 0 5 2⋅10^5 2⋅105。

输出
对于每一轮，打印一行包含一个字符串和一个整数。如果 Alice 赢得这一轮，则字符串必须是“Alice”。如果 Bob 赢得了回合，则字符串必须是“Bob”。整数必须是他们的分数之间的差，假设两个玩家都打得最好。

测试样例：

**input**5abaabccbancodeforces**output**Alice 2Alice 4Alice 4Bob 14Alice 93

题解：

贪心就完了。Alice先删，所以除了n==1Bob赢，其余Alice必赢。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;const int inf=0x3f3f3f3f;const int maxn=1e6+5;void solve(){    string s;    cin >> s;    int n = s.length();    if(n==1){//奇数个Bob一定赢 cout << "Bob " << s[0] - 'a' + 1 << "\n"; return;    }    int sum = 0;    for(auto i:s)//所有字母值之和 sum += i - 'a' + 1;    if (n % 2 == 0)     //Alice把所有全删除掉 cout << "Alice " << sum << "\n";    else  //Alice把前n-1或者后n-1个字母删掉 cout << "Alice " << sum - 2 * min(s[0] - 'a' + 1, s[n - 1] - 'a' + 1) << "\n"; // sum=a+b;   a=sum=b;  a-b=sum-2*b;}int main(){    ios::sync_with_stdio(0);    int t;    cin>>t;    while(t--)    solve();    return 0;}

B. A Perfectly Balanced String?

题目大意：

如果对于所有可能的三元组 $(t,u,v)$ 使得 $t$ 是 $s$ 的非空子串并且 $u$ 和 $v$ 是 $s$ 中存在的字符，那么我们称一个字符串 $s$ 是完全平衡的，$u$ 和 $v$ 在 $t$ 中频率之间的差异不大于 $1$。

例如，字符串 “$aba$” 和 “$abc$” 是完全平衡的，但 “$abb$” 不是，因为对于三元组 (“$bb$”,‘$a$’,‘$b$’)，条件不满足。

给你一个字符串 $s$ 仅由小写英文字母组成。你的任务是确定 $s$ 是否完全平衡。

如果 b 可以通过从 a 的开头删除一些字符（可能为 0）和从 a 的结尾删除一些字符（可能为 0）来获得，则字符串 b 称为另一个字符串 a 的子字符串。

输入
输入的第一行包含一个整数 t ( 1 ≤ t ≤ 2 ⋅ 1 0 4 ) t (1≤t≤2⋅10^4) t(1≤t≤2⋅104)，表示测试用例的数量。

接下来的 $t$ 行中的每一行都包含一个字符串 s ( 1 ≤ ∣ s ∣ ≤ 2 ⋅ 1 0 5 ) s (1≤|s|≤2⋅10^5) s(1≤∣s∣≤2⋅105)，由小写英文字母组成。

保证 $|s|$ 的总和在所有测试用例中不超过 2 ⋅ 1 0 5 2⋅10^5 2⋅105。

输出
对于每个测试用例，如果 $s$ 是一个完美平衡的字符串，则打印“YES”，否则打印“NO”。

您可以在任何情况下打印每个字母（例如，“YES”、“Yes”、“yes”、“yEs”都将被识别为肯定答案）。

测试样例：

**input**5abaabbabcaaaaaabcba**output**YESNOYESYESNO

题解：

如果字符串是周期性的并且重复模式包含所有不同的字母，则该字符串是完全平衡的。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;const int inf=0x3f3f3f3f;const int maxn=1e6+5;void solve(){    string s;    cin >> s;    int n = s.length();    set<char> c;    bool ok = true;    int k;    for(k=0;k<n;k++){ if(c.find(s[k])==c.end()) //若在set c 中找不到则 c.find(x) == c.end()     c.insert(s[k]); else     break;    }    for(int i=k;i<n;i++){ if(s[i]!=s[i-k])     ok = false;    }    if(ok) cout << "YES\n";    else cout << "NO\n";}int main(){    ios::sync_with_stdio(0);    int t;    cin>>t;    while(t--)    solve();    return 0;}

C. Palindrome Basis

题目大意：

给你一个正整数 $n$。 如果某个正整数 $a$ 在颠倒其数字的顺序后保持不变，则称其为不带前导零回文的整数。 找出将 $n$ 表示为正回文整数之和的不同方式的数量。 如果至少一个回文整数的频率不同，则两种方式被认为是不同的。 例如，5=4+1 和 5=3+1+1 被认为是不同的，但 5=3+1+1 和 5=1+3+1 被认为是相同的。

形式上，您需要找到总和等于 n 的正回文整数的不同多重集的数量。

由于答案可能很大，因此 模 1 0 9 + 7 10^9+7 109+7 输出。

输入
输入的第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1≤t≤104)，表示测试用例的数量。

每个测试用例包含一行输入，其中包含单个整数 n ( 1 ≤ n ≤ 4 ⋅ 1 0 4 ) n (1≤n≤4⋅10^4) n(1≤n≤4⋅104) — 所需的回文整数之和。

输出
对于每个测试用例，打印一个表示所需答案模 1 0 9 + 7 10^9+7 109+7 的整数。

测试样例：

**input**2512**output**774

笔记
对于第一个测试用例，有 7 种方法将 5 划分为正回文整数之和：

• 5=1+1+1+1+1
• 5=1+1+1+2
• 5=1+2+2
• 5=1+1+3
• 5=2+3
• 5=1+4
• 5=5

对于第二个测试用例，共有 77 种方法将 12 分区为正整数之和，但其中，分区 12=2+10、12=1+1+10 和 12=12 不是 12 的有效分区作为 正回文整数之和，因为 10 和 12 不是回文数。 因此，有 74 种方法可以将 12 划分为正回文整数的总和。

题解：

First, we need to observe that the number of palindromes less than 4 ⋅ 1 0 4 4\cdot 10^4 4⋅104 is relatively very small. The number of $5$-digit palindromes are $300$ (enumerate all $3$-digit numbers less than $400$ and append the first two digits in the reverse order). Similarly, the number of $4$-digit, $3$-digit, $2$-digit and $1$-digit palindromes are $90$, $90$, $9$ and $9$ respectively, giving a total of $M=498$ palindromes.

Now, the problem can be solved just like the classical partitions problem which can be solved using Dynamic Programming.

Let d pk,m = dp_{k,m} = dpk,m​= Number of ways to partition the number $k$ using only the first $m$ palindromes. It is not hard to see that d pk,m = d pk,m−1 + d pk− p m ,m dp_{k,m} = dp_{k,m-1} + dp_{k-p_m,m} dpk,m​=dpk,m−1​+dpk−pm​,m​ where p m p_m pm​ denotes the mth m^{th} mth palindrome. The first term corresponds to the partitions of $k$ using only the first $m-1$ palindromes and the second term corresponds to those partitions of $k$ in which the mth m^{th} mth palindrome has been used atleast once. As base cases, d pk,1 = 1 dp_{k,1}=1 dpk,1​=1 and d p1,m = 1 dp_{1,m}=1 dp1,m​=1. The final answer for any $n$ will be d pn,M dp_{n,M} dpn,M​.

The time and space complexity is $\mathcal{O}(n\cdot M)$.

首先，我们需要观察到小于 4 ⋅ 1 0 4 4\cdot 10^4 4⋅104 的回文数相对非常少。 $5$-digit 回文数是 $300$（枚举所有小于 $400$ 的 $3$-digit 数字并以相反的顺序附加前两位数字）。类似地，$4$-digit、$3$-digit、$2$-digit 和 $1$-digit 回文数分别为 $90$、$90$、$9$ 和 $9$，总共有 $M=498$ 个回文。

现在，这个问题可以像经典的分区问题一样解决，可以使用动态编程解决。

令 d pk,m = dp_{k,m} = dpk,m​= 仅使用前 $m$ 回文数来划分数字 $k$ 的方法数。不难看出 d pk,m = d pk,m−1 + d pk− p m ,m dp_{k,m} = dp_{k,m-1} + dp_{k-p_m,m} dpk,m​=dpk,m−1​+dpk−pm​,m​ 其中 p m p_m pm​ 表示 mth m^{th} mth 回文。第一项对应于仅使用第一个 $m-1$ 回文的 $k$ 的分区，第二项对应于 $k$ 的那些分区，其中 mth m^{th} mth 回文至少被使用过一次。作为基本情况， d pk,1 = 1 dp_{k,1}=1 dpk,1​=1 和 d p1,m = 1 dp_{1,m}=1 dp1,m​=1。任何 $n$ 的最终答案都是 d pn,M dp_{n,M} dpn,M​。

时间和空间复杂度为$\mathcal{O}(n\cdot M)$。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;const int inf=0x3f3f3f3f;const int maxn=1e6+5;const int N = 40004, M = 502;const ll MOD = 1000000007;ll dp[N][M];int reverse(int n){    int r=0;    while(n>0)    { r=r*10+n%10; n/=10;    }    return r;}bool palindrome(int n){    return (reverse(n)==n); }void solve(){    int n;    cin >> n;    cout << dp[n][M-1] << '\n';}int main(){    ios::sync_with_stdio(0);    int t;    cin>>t;    vector<int> palin;    palin.push_back(0);    for(int i=1;i<2*N;i++){ if(palindrome(i))     palin.push_back(i);    }    for(int i=1;i<M;i++) dp[0][i]=1;    for(int i=1;i<N;i++){ dp[i][0]=0; for(int j=1;j<M;j++){     if(palin[j]<=i)  dp[i][j]=(dp[i][j-1]+dp[i-palin[j]][j])%MOD;     else  dp[i][j]=dp[i][j-1]; }    }    while(t--) solve();    return 0;}

附带题目：P1025 [NOIP2001 提高组] 数的划分

题目描述
将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：n=7n=7，k=3k=3，下面三种分法被认为是相同的。

1,1,5
1,5,1
5,1,1

问有多少种不同的分法。

输入格式
$n,k（6<n\le 200，2\le k\le 6）$

输出格式
11 个整数，即不同的分法。

输入
7 3
输出
4

四种分法为：
1,1,5
1,2,4
1,3,3
2,2,3

题解

这题其实是排列组合里的题，可以把一个数值为 n 的数当做 n 个小球，划分的份数 k 当做 k 个盒子，那么本题可以转化为“将 n 个小球放到 k 个盒子中，小球之间与盒子之间没有区别，并且最后的结果不允许空盒”

将 n 个小球放到 k 个盒子中的情况总数 =
a.至少有一个盒子只有一个小球的情况数 + b.没有一个盒子只有一个小球的情况数

这样进行划分是因为这种分类可以使a和b都有能写出来的表达式：

a.因为盒子不加区分，那么 1 的情况数与“将 n-1 个小球放到 k-1个盒子中”的情况数一样

b.没有一个盒子只有一个小球，那么把每个盒子中拿出来一个小球，对应的是“把 (n-k) 个小球放到 k 个盒子中的情况数”

然后将上面的思路化为动态转移方程：

设 f[n][k] 代表将 n 个小球放到 k 个盒子中且没有空盒的情况，
那么f[n][k] = f[n-1][k-1] + f[n-k][k]

而当 k=1 时只有 1 种方法(小球全部放进1个盒子)

int f[1010][100];int n, k;void solve(){    cin >> n >> k;    for (int i = 1; i <= n; i++) f[i][1] = 1; //当 k=1 时只有 1 种方法    for (int i = 1; i <= n; i++) for (int j = 2; j <= k; j++) // 1的情况已经处理，从2开始，否则会访问0。     if (i >= j)  //小细节：只有n>=k时才能有数分。  f[i][j] = f[i - 1][j - 1] + f[i - j][j];    printf("%d\n", f[n][k]);     //输出从n中分出k份的方案数}

本题数据量小，爆搜+剪枝也可以：

$last$：上次划分所用分数
$cur$：划分的次数
$sum$：目前所组合的值
需要保证的条件：i ≤ n − s u m k − c u r i\le \dfrac{ n - sum}{k-cur} i≤k−curn−sum​

void dfs(int last,int sum,int cur){    if(cur==k){ if(sum==n) cnt++; return;    }    for(int i=last;sum+i*(k-cur)<=n;i++)//剪枝 dfs(i,sum+i,cur+1);}int main(){    scanf("%d%d",&n,&k);    dfs(1,0,0);    printf("%d",cnt);}

D. Lost Arithmetic Progression

题目大意：

很久以前，您想到了两个有限算术级数 $A$ 和 $B$。然后您发现了另一个序列 $C$，其中包含 $A$ 和 $B$ 共有的所有元素。不难看出，$C$ 也是有限算术级数。多年后，你忘记了 $A$ 是什么，但记住了 $B$ 和 $C$。出于某种原因，你下定决心要找到这个丢失的算术级数。在你开始这个永恒的搜索之前，你想知道有多少不同的有限算术级数存在，它们可能是你丢失的级数 $A$。

如果两个算术级数的第一项、共同差或项数不同，则它们被认为是不同的。

可能有无限多这样的级数，在这种情况下，您甚至不会尝试寻找它们！在所有这些情况下打印 -1。

即使它们的数量有限，答案也可能非常大。因此，您只对找到模 109 + 7 10^9+7 109+7 的答案感兴趣。

输入
输入的第一行包含一个整数 $t(1\le t\le 100)$，表示测试用例的数量。

每个测试用例的第一行包含三个整数 $b、q$ 和 y （ − 1 0 9 ≤ b ≤ 1 0 9 、 1 ≤ q ≤ 1 0 9 、 2 ≤ y ≤ 1 0 9 ） y（-10^9≤b≤10^9、1≤q≤10^9、2≤y≤10^9） y（−109≤b≤109、1≤q≤109、2≤y≤109），分别表示 $B$ 的第一项、公差和项数。

每个测试用例的第二行包含三个整数 $c、r$ 和 z （ − 1 0 9 ≤ c ≤ 1 0 9 、 1 ≤ r ≤ 1 0 9 、 2 ≤ z ≤ 1 0 9 ） z（-10^9≤c≤10^9、1≤r≤10^9、2≤z≤10^9） z（−109≤c≤109、1≤r≤109、2≤z≤109），分别表示 $C$ 的第一项、公差和项数。

输出
对于每个测试用例，打印包含单个整数的单行。

如果有无限多的有限算术级数可能是您丢失的级数 A，请输出 -1。

否则，打印有限算术级数的数量，这可能是您丢失的级数 A 模 109+7。特别是，如果没有这样的有限算术级数，则打印 0。

测试样例：

**input**8-3 1 7-1 2 4-9 3 110 6 32 5 57 5 42 2 1110 5 30 2 92 4 3-11 4 121 12 2-27 4 7-17 8 2-8400 420 10000000000 4620 10**output**010-10-1210273000

题解：

如果$C$ 的所有元素都不存在于$B$ 中，那么答案是$0$。检查以下 $4$ 条件就足以检查 $C$ 的所有元素是否存在于 $B$ 中 -

• $B\le$ 的第一项 $C$ 的第一项，即$b\le c$。
• $B\ge$ 的最后一项 $C$ 的最后一项，即 $b+(y-1)q\ge c+(z-1)r$。
• $C$的公差必须能被$B$的公差整除，即$r\mathrm{m}\mathrm{o}\mathrm{d}q=0$。
• $C$ 的第一项必须在 $B$ 中，即 $(c-b)\mathrm{m}\mathrm{o}\mathrm{d}q=0$。

现在假设满足以下条件。让我们用 $[a,d,n]$ 表示具有第一项 $a$、共同差 $d$ 和 $n$ 项数的算术级数 (AP)。

如果 $b>c-r$ 则有无限数量的级数可以是 $A$ 像 $[c,r,z]$, $[c-r,r,z+1]$, $[c-2r,r,z+2]$ 等等。类似地，如果 $b+(y-1)q<c+zr$，则有无限个级数可以是 $A$，例如 $[c,r,z]$, $[c,r,z+1]$, $[c,r,z+2]$ 等等。

否则，有有限数量的级数可以是 $A$。让我们数一数。令 $A$ 为 AP $[a,p,x]$ 和 $l=a+(x-1)p$。可以看出，对于任何有效的 $A$，$lcm(p,q)=r$, $(c-a)\mathrm{m}\mathrm{o}\mathrm{d}p=0$, $a>c-r$ 和 $l<c+rz$。前两个条件是微不足道的。第三个条件是必要的，因为如果 $a\le c-r$ 那么 $c-r$ 将始终出现在 $A$ 和 $B$ 中，这与 $C$ 包含 $A$ 和 $B$ 共有的所有术语的事实相矛盾.同样，第四个条件也是必要的。

根据第一个条件，$p$ 唯一可能取的值是 $r$ 的因数，它可以在 O ( r ) \mathcal{O}(\sqrt{r}) O(r ​) 中枚举。 $lcm$ 条件可以在 $\mathcal{O}(\log r)$ 中检查。对于 $p$ 的特定值，有满足条件 2 和 3 的 $a$ 的 r p \frac{r}{p} pr​ 可能值和满足条件 2 和 3 的 r p \frac{r}{p} pr​ 可能值条件 2 和 4。因此，答案是 ∑ l c m ( p , q ) = r (rp )2 \displaystyle\sum_{lcm(p,q)=r}\Big(\frac{r}{p}\Big)^2 lcm(p,q)=r∑​(pr​)2。

时间复杂度： O ( t  r   log ⁡ r ) \mathcal{O}(t\,\sqrt{r}\,\log r) O(tr ​logr)

#include using namespace std;typedef long long ll;typedef long double ld;typedef pair<int, int> pii;const int inf = 0x3f3f3f3f;const int maxn = 1e6 + 5;const ll MOD = 1000000007;ll gcd(ll a, ll b){    return a % b == 0 ? b : gcd(b, a % b);}ll lcm(ll a, ll b){    ll g = gcd(a, b);    return (a * b) / g;}void solve(){    ll b, c, q, r, y, z;    cin >> b >> q >> y;    cin >> c >> r >> z;    ll e = b + q * (y - 1);    ll f = c + r * (z - 1);    if (c < b || c > e || f < b || f > e || r % q != 0 || (c - b) % q != 0) cout << 0 << '\n';    else if (c - r < b || f + r > e) cout << -1 << '\n';    else{ ll ans = 0; for (ll p = 1; p * p <= r; p++){     if (r % p == 0){  if (lcm(p, q) == r){      ll a = ((r / p) * (r / p)) % MOD;      ans = (ans + a) % MOD;  }  if (p * p != r && lcm(r / p, q) == r){      ll a = (p * p) % MOD;      ans = (ans + a) % MOD;  }     } } cout << ans << '\n';    }}int main(){    ios::sync_with_stdio(0);    int t;    cin >> t;    while (t--) solve();    return 0;}

END:2022年5月1日17:23:38