Logo __vector__ 的博客

博客

论如何 AK ARC211

...
__vector__
2025-12-01 19:07:17

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. 从 $1$ 号点出发建立 dfs 树，子节点的蓝色标记指向父节点。
  2. 删除已经用过的边。
  3. 从 $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？  
*/

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

Server Time: 2025-12-15 04:11:46 | OpenSource Project