A
注意到 $5$ 是一个特殊的数字，因为除了 $5$ 以外任意相同数字都允许相邻。
- 如果给定的数字存在 $5$。
假设有 $x$ 个 $5$，那么强制使用 $x-1$ 个其他数字将这些 $5$ 隔开。
令 $y$ 表示不是 $5$ 的数字数量。
若 $y \le x-1$，那么显然添加 $x-1-y$ 个非 $5$ 数字填到空里面，就能变得合法。
否则，先对于总共 $x-1$ 个空，每个空填一个数字，剩下的没填的数字，填到已经填了的且填的数值和自己相同的空里面即可。
综上，答案为 $\max(0,x-1-y)$。 - 如果给定的数字不存在 $5$。
可以证明除了仅存在两种数字，且这两种数字加起来总和为 $10$ 的情况的答案是 $1$，其余情况答案均为 $0$。
考虑将所有相同数字放到一起，视为合并为一个数字。
然后，升序排列所有数字。
如果存在相邻两个数字满足加起来总和为 $10$，那么就将其中一个数字与自己另一个邻居数字交换，然后就合法了。
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
ll a[10];
void solve(int id_of_test){
FOR(i,1,9)read(a[i]);
if(a[5]){
ll rst=-a[5];
FOR(i,1,9)rst+=a[i];
if(rst>=a[5]-1){
puts("0");
}else{
printf("%lld\n",a[5]-1-rst);
}
}else{
int cnt=0;
FOR(i,1,9)cnt+=(a[i]!=0);
if(cnt==1)puts("0");
else if(cnt==2){
FOR(i,1,9){
FOR(j,i+1,9){
if(a[i]&&a[j]){
if(i+j==10){
puts("1");
return;
}
}
}
}
}else{
puts("0");
}
}
}
int main()
{
int T;
read(T);
FOR(_,1,T){
solve(_);
}
return 0;
}
/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*/B
观察样例，猜结论：
- 一定可以仅使用 $0,1$ 构造出满足要求的数列。
为了简单的构造答案，考虑让同一种数字构成一个连续段。
首先考虑什么情况下能仅使用 $0$ 构造出答案。
此时，有以下几条限制：
1. 第一个数列长度至少为 $y$。
2. 第二个数列长度至少为 $z$。
3. 第三个数列长度至少为 $z$。
进而推导出：
1. 第一个数列长度等于 $y$。
2. 第二个数列，第三个数列的长度等于 $z$。
可以推导出，当且仅当 $x=y$ 才能与题目条件不冲突。
现在知道 $x=y$ 时可以仅使用 $0$ 构造出答案，其他情况则不可以，考虑其他情况怎么构造答案。
考虑这样：
- 第一个数列先 $x$ 个 $0$，然后 $y$ 个 $1$。
然后可以推导出：
- 第二个数列至少拥有 $x$ 个 $0$。
- 第三个数列至少拥有 $y$ 个 $1$。
- 第二个数列不允许有超过 $x$ 个 $1$。
接下来考虑怎么满足数列二，三的最长公共子串长度为 $z$。
这样构造：
- 第二个数列拥有 $z$ 个 $0$。
- 第三个数列加上 $z$ 个 $0$。
然后本题就做完了。
综上：
- 第一个数列有 $x$ 个 $0$ 和 $y$ 个 $1$。
- 第二个数列有 $z$ 个 $0$。
- 第三个数列有 $y$ 个 $1$ 和 $z$ 个 $0$。
C
考虑将所有极长的连续的同一类型的格子分别缩为一个连续段。
首尾如果是树的话就可以忽略掉，因为反正不可能删掉，所以接下来可以假设首尾均为空段。
首先每次操作必然恰好删除一个树段，否则可以通过将本次操作拆分为多次操作来增加贡献，也就是说每次操作必然选中相邻两个空段。
考虑最大奖金的形式是什么。
首先，每个空段的最大值必然会被算进总奖金一次。
然后，每次操作结束之后相当于合并了两个空段和它们中间的那个树段，生成了一个新的空段，最大值相当于三段最大值的 max。
除了最终产生的那个长度为 $n$ 的空段，其余所有中途产生的空段的最大值也都会被算进总奖金一次。
那么答案将会是，每个空段的最大值的总和，加上合并过程中产生的空段的最大值总和，减去 $\max\limits_{i=1}^n r_i$。
注意到只有合并过程中产生的空段的最大值总和不固定。
那么贪心的考虑，能否让每次产生的空段的最大值都等于 $\max\limits_{i=1}^n r_i$ 呢？
这显然是可以的，只需要保证选中的两个空段以及中间的树段的最大值是 $\max\limits_{i=1}^n r_i$ 就行了。
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
const int maxn=2e5+5;
char s[maxn];
int cost[maxn];
int n;
vector<pii> rle(){
vector<pii> seq;
int l=1,r=n;
while(s[l]=='#')l++;
while(s[r]=='#')r--;
int lst=l;
FOR(i,l,r){
if(s[i]!=s[i-1]){
if(i!=l)seq.eb(mkpr(lst,i-1));
lst=i;
}
}
if(s[r]=='.')seq.eb(lst,r);
vector<pii> res;
for(auto [l,r]:seq){
// printf("[%d,%d]\n",l,r);
int mx=0;
FOR(i,l,r)ckmx(mx,cost[i]);
int cnt=0;
FOR(i,l,r)cnt+=(mx==cost[i]);
res.eb(mkpr(mx,cnt));
}
return res;
}
void solve(int id_of_test){
scanf("%d",&n);
scanf("%s",s+1);
FOR(i,1,n){
scanf("%d",&cost[i]);
}
auto res=rle();
int mx=0;
ll ans=0;
for(auto [_mx,_cnt]:res)ckmx(mx,_mx);
for(int i=0;i+2<res.size();i+=2){
if(max({res[i].fi,res[i+1].fi,res[i+2].fi})==mx){
ans+=1ll*res[i].se*res[i+2].se;
}
}
printf("%lld\n",ans);
}
int main()
{
int T;
T=1;
FOR(_,1,T){
solve(_);
}
return 0;
}
/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*/D
首先考虑无解情况是什么。
如果存在一个节点 $x$，使得 $1,2$ 无论如何都必须经过一条公共边才能到达 $x$，那么是无解的。
这种情况可以换个描述方式，若存在一个桥，使得断开这个桥之后 $1,2$ 处于同一连通分量，那么无解。
考虑剩下的情况，现在边双缩点之后图将会形成一条链，且 $1,2$ 所在的边双连通分量将会位于链的两端。
因为 $1,2$ 的路径上不能挂其他节点，$1,2$ 路径以外也不能挂其他节点，否则无解。
然后就能惊喜的发现，且显然的，只要这样做就是对的：
- 从 $1$ 号点出发建立 dfs 树，子节点的蓝色标记指向父节点。
- 删除已经用过的边。
- 从 $2$ 号点出发建立 dfs 树，子节点的黄色标记指向父节点。
E
主要记录我对官方题解的理解。
考虑树的形态确定的情况下，$R$ 数列将会是怎样的。
首先 $Q_1 = N$。
然后假设 $1$ 的直接连接的子节点有 $x$ 个，那么必然分别填 $N-1,N-2,\cdots,N-x$。
接下来 Takahashi 肯定是递归访问到标记着 $N-x$ 的节点。
随后注意到，这个标记着 $N-x$ 的节点，其子节点的权值一定小于 $N-x$。
所以访问完权值为 $N-x$ 的点之后必然访问其子树（如果存在的话），若没有子树的话，回溯到权值为 $N-x+1$ 的点。
然后使用相同方法给这个权值为 $N-x$ 的点的子节点填权值。
如果循环往复，注意到 Takahashi 的行走过程，访问点的顺序就是 DFS 序，只不过按照点权从小到大依次搜索。
那么此时也就有了一些结论。
对于一个节点 $u$，假设其有 $x$ 个子节点，令第 $i$ 个子树单独提出来得到的 $R$ 数组为 $s_i$，那么这些子节点的权值必然是按照 $s_i$ 字典序降序排列（特别的，若一个是另一个的前缀，则短的在前面）且连续的一组数字。
假设子节点们已经按照上述规则排序，$u$ 节点权值为 $m$，此时，$u$ 节点作为根的得到的 $R$ 数组形式如下：
$$
m,m-x,s_1,m-x+1,s_2,m-x+2,s_3,\cdots,m-1,s_x
$$
考虑怎么判定给定的 $P$ 数组能否得到。
首先必须满足 $P_1 = N$。
随后，设计一个检查函数 chk(l,r,mx)，表示当前正在处理的子树的权值（不含根）对应 $P_l,P_{l+1},\cdots,P_r$，且根节点的权值为 $mx$，此时是否合法。
根节点的子节点个数必然等于 $mx-P_l$。
那么现在可以提取出根节点的所有子节点所占用的 $P$ 数组下标，其权值必然分别是 $mx-P_l,mx-P_l+1,\cdots,mx-1$。
对于每个子节点，其在 $P$ 数组中后面的连续一段小于 $N-p_2$ 的数值，均为其子树对应的权值，此时递归进这一段判定其合法性，另外还要判定这一段数字是连续的一段数字，可以考虑使用 ST 表维护区间极差来做到这一点。
另外，还要判定按照根节点权值升序排序后相邻两个子树分别被 Takahashi 遍历得到的数组（是 $P$ 的子数组）满足字典序降序（一个是另一个的前缀则短的在前面），这一部分可以暴力维护，总复杂度可以发现并不会高于归并排序。
另外，还需要判定权值在 $[mx-P_l,mx-1]$ 之间的节点，其位置必须升序排列并且不能超出 $[l,r]$ 范围。
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
const int maxn=2e5+5;
int n;
int p[maxn],pos[maxn];
struct ST{
int mx[19][maxn],mn[19][maxn];
void bd(){
FOR(i,1,n){
mx[0][i]=mn[0][i]=p[i];
}
FOR(i,1,18){
FOR(j,1,n-(1<<i)+1){
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
}
}
}
int qmx(int l,int r){
int _=__lg(r-l+1);
return max(mx[_][l],mx[_][r-(1<<_)+1]);
}
int qmn(int l,int r){
int _=__lg(r-l+1);
return min(mn[_][l],mn[_][r-(1<<_)+1]);
}
int qrg(int l,int r){
return qmx(l,r)-qmn(l,r);
}
}st;
bool chk(int l,int r,int mx){
// printf("[%d,%d, mx %d]\n",l,r,mx);
int mn=p[l];
vi rem;
FOR(i,mn,mx){
if(pos[i]>=l&&pos[i]<=r)rem.eb(pos[i]);
else return 0;
}
for(int i=0;i+1<rem.size();i++){
if(rem[i]>rem[i+1]){
return 0;
}
}
#define getlen(i) ((i+1==rem.size())?(r-rem[i]):rem[i+1]-rem[i]-1)
for(int i=0;i<rem.size();i++){
int len=getlen(i);
if(len){
if(st.qrg(rem[i]+1,rem[i]+len)+1!=len)return 0;
if(chk(rem[i]+1,rem[i]+len,st.qmx(rem[i]+1,rem[i]+len))==0)return 0;
}
if(i+1<rem.size()){
int len2=getlen(i+1);
int s1=rem[i],s2=rem[i+1];
bool ok=0;
FOR(_,1,min(len,len2)){
if(p[s1+_]-len!=p[s2+_]){
if(p[s1+_]-len<p[s2+_]){
return 0;
}
ok=1;
break;
}
}
if(!ok){
if(len>len2)return 0;
}
}
}
return 1;
}
void solve(int id_of_test){
read(n);
FOR(i,1,n){
read(p[i]);
pos[p[i]]=i;
}
st.bd();
if(p[1]!=n){
puts("No");
return;
}
puts(chk(2,n,n-1)?"Yes":"No");
}
int main()
{
int T;
read(T);
FOR(_,1,T){
solve(_);
}
return 0;
}
/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*/
鲁ICP备2025150228号