AtCoder Regular Contest 088

题解

目录

• AtCoder Regular Contest 088
  • C. Multiple Gift
    • 思路
    • 代码
  • D. Wide Flip
    • 思路
    • 代码
  • E. Papple Sort
    • 思路
    • 代码
  • F. Christmas Tree
    • 思路
    • 代码

C. Multiple Gift

题目大意：构造一个序列$A$，使$\forall A_i \in [X,Y]$且$forall i \in[1,\mid A\mid)$有$A_i \mid A_{i+1}$，求$\mid A \mid_{max}$。$1 \leq X,Y \leq 10^{18}$。

思路

• 贪心构造即可，$A_i=X \times 2^{i-1}$，复杂度$O(\log Y)$。

代码

#include <cstdio>
int main(){
    unsigned long long x,y;
    scanf("%llu%llu",&x,&y);
    int ans=0;
    while(x<=y) x<<=1,++ans;
    printf("%d",ans);
    return 0;
}

D. Wide Flip

题目大意：给你一个01串$S$，每次可以选一段长度不小于$k$的区间$[l,r]$对$S_l$~$S_r$取反。求使$S$能够变为全0串的$k_{max}$。$1 \leq\mid S \mid\leq 10^5$。

思路

• 这题考试时居然没想出来，其实很简单，分类讨论即可；
• 这题可以换个说法，不一定非要将$S$变为全0的，变成全1的也可以，因为这样最后对整个串取反即可，不影响答案；
• 那么，我们只需要考虑怎么将所有字符变成相同的；
• 设$n=\mid S \mid$；
• 对于相邻且不同的两个字符$S_i$和$S_{i+1}$，我们可以先后对区间$[i,n]$和$[i+1,n]$取反，使$S_i$变为与$S_{i+1}$相同的字符，并且对其它字符没有影响；
• 当然，反过来操作$S_{i+1}$也可以；
• 这样$k_{max}=\min_{S_i \neq S_{i+1}}\{\max(i,n-i)\}$；
• 扫一遍就可以了，总复杂度为$O(n)$。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
using std::min;
const int MAXN=1e5+5;
char s[MAXN];
int main(){
    scanf("%s",s);
    int n=strlen(s),ans=n;
    for(int i=1;i<n;++i){
        if(s[i]!=s[i-1])
            ans=min(ans,max(i,n-i));
    }
    printf("%d",ans);
    return 0;
}

E. Papple Sort

题目大意：给你一个字符串$S$，每次可以交换相邻两个字符，求使$S$变为回文串的最小交换次数（无解则输出$-1$）。$1 \leq \mid S \mid \leq 2 \times 10^5$。

思路

• 这题太神了Orz；
• 设$n=\mid S \mid$；
• 首先肯定是特判无解情况；
• 然后考虑将问题转化，如果我们确定了每个字符的最终位置，那么只要将每个字符的最终位置上赋值为最初位置，求一下逆序对即可（答案显然是逆序对数的一半）；
• 并且，最终位置其实是可以贪心构造的，我们求出每个字符第一次出现和最后一次出现的位置，每次用两个指针$l,r$分别向右向左跳到该字符的下一个位置，则$final\_pos(r)=n-l+1$，也就是对称的构造即可；
• 为什么这样是对的？
• 首先可以证明，对于每种字符，肯定是对称匹配的，也就是一个贪心配对问题；
• 而我们构造最终的回文串为什么是对的，这个其实也不难理解；
• 按照上面的配对方式，如果保持$l$不动，每个$r$确实应当在这个位置，而如果令$l$也动了，肯定不是更优的选择（两个都动了吗）；
• 而这样构造的合法性也很显然，$final\_pos$的值互不相同；
• 于是总复杂度就是求逆序对的复杂度$O(n \log n)$。

代码

#include <cstdio>
#include <cstring>
const int MAXN=2e5+5,INF=0x7f7f7f7f;
int n;
int a[MAXN];
char s[MAXN];
inline int chr_idx(char c){return c-'a';}
template<class T>
long long mge_sort(T a[],int l,int r){
    static T tmp[MAXN];
    if(l==r) return 0;
    int mid=l+r>>1;
    long long ret=mge_sort(a,l,mid)+mge_sort(a,mid+1,r);
    int lp=l,rp=mid+1,cur=l-1;
    while(lp<=mid && rp<=r){
        if(a[lp]<=a[rp]) tmp[++cur]=a[lp++];
        else{
            ret+=mid-lp+1;
            tmp[++cur]=a[rp++];
        }
    }
    while(lp<=mid) tmp[++cur]=a[lp++];
    while(rp<=r) tmp[++cur]=a[rp++];
    memcpy(a+l,tmp+l,(r-l+1)*sizeof(T));
    return ret;
}
inline void deal(){
    static int fir_pos[26],last_pos[26],pre[MAXN],nex[MAXN];
    static bool use[MAXN];
    for(int i=n;i;--i){
        nex[i]=fir_pos[chr_idx(s[i])];
        fir_pos[chr_idx(s[i])]=i;
    }
    for(int i=1;i<=n;++i){
        pre[i]=last_pos[chr_idx(s[i])];
        last_pos[chr_idx(s[i])]=i;
    }
    for(int i=0;i<26;++i){
        if(!fir_pos[i]) continue;
        for(int l=fir_pos[i],r=last_pos[i];r;l=nex[l],r=pre[r])
            a[n-l+1]=r;
    }
}
inline bool spj(){
    static int cnt[26];
    for(int i=1;i<=n;++i)
        ++cnt[chr_idx(s[i])];
    int tot=0;
    for(int i=0;i<26;++i){
        if(cnt[i]&1) ++tot;
    }
    return tot==(n&1);
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    if(!spj()){
        printf("-1");
        return 0;
    }
    deal();
    printf("%lld",mge_sort(a,1,n)>>1);
    return 0;
}

F. Christmas Tree

题目大意：你有$A$个长度最多为$B$的路径。每次可以选在不同连通块中的两个点，将它们合成一个点。最后要求合并成一个与所给的树同构的树。求$A$的最小值及此时$B$的最小值。

思路

• 这题开始都没看懂啥意思。。。
• 设树中度数为奇数的点有$cnt_{odd}$个，则$A \geq cnt_{odd}$，因为每个度数为奇数的点一定是奇数个路径的端点，那每次选两个路径端点合并就可以达到这个下限了；
• 也就是度数为奇数的点恰为一条路径的端点，度数为偶数的点不能为路径端点；
• 现在考虑最小化$B$，不妨二分答案；
• 设$dp(u)$是以$u$为子树在满足条件下$u$的所在的链的最小点数（剩下的链跨过$u$连接两个儿子）；
• 对于度数为偶数的点$u$，它有奇数个儿子，而为了满足之前的要求——$u$不能为路径端点，我们肯定要将那些儿子所在的链配成$\frac{k-1}{2}$对，剩下一个和$u$配对；
• 对于度数为奇数的点$u$，它有偶数个儿子，并且它需要恰好是一条路径端点。这也很好处理，新增一个$dp$值为$0$的空儿子即可转化为上面那种情况了；
• 另外，这些对儿子的$dp$值之和不能超过$B$（因为少加了一个$u$的贡献，相当于路径长度而不是点数，所以不加$1$），不然不符合二分出的$B$的要求；
• 并且我们要想使与$u$同色的儿子的$dp$值尽可能小（这是一个贪心的决策），这个是有单调性的（如果$u$与一个$dp$值小的儿子配对是合法的，和一个$dp$值更大的配对也一定合法）；
• 那么将这些儿子按$dp$值排序，可以二分一个与$u$配对的儿子，验证的话就是将剩下的贪心配对（最大的配最小的），满足条件的话，这个二分的结果就是成立的；
• 设与$u$配对的儿子是$v$，则$dp(u)=dp(v)+1$；
• 每层DP结束后还要检查与$dp(u)$的值，大于$B+1$的话这个$B$也是不合法的；
• 最后实现上有一个细节就是根节点由于没有父亲，度数就是儿子数，和之前讨论的情况不太相同。一个简单的转化方式是选一个度数为$1$的点当根，这就免去了很多讨论；
• 总结一下：这题首先二分答案，再用DP验证。验证时又用了贪心的思想，同时又使用二分去进行这个贪心的决策，还是很妙的；
• 由于是二分套二分，总复杂度就是$O(n\log^2 n)$。

代码

#include <cstdio>
#include <algorithm>
#include <vector>
using std::sort;
using std::vector;
const int MAXN=1e5+5;
int rt,n,A,B;
int he[MAXN],deg[MAXN];
int dp[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
inline bool cmp_dp(int a,int b){return dp[a]<dp[b];}
inline bool check(vector<int> &vec,int son){
    for(int l=0,r=vec.size()-1;l<r;++l,--r){
        if(l==son) ++l;
        if(r==son) --r;
        if(dp[vec[l]]+dp[vec[r]]>B)
            return false;
    }
    return true;
}
inline int bin_chop_son(vector<int> &vec){
    int l=0,r=vec.size()-1,mid;
    while(l<=r){
        mid=l+r>>1;
        if(check(vec,mid)) r=mid-1;
        else l=mid+1;
    }
    return l;
}
bool treeDP(int u,int fa){
    vector<int> vec;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=fa){
            if(!treeDP(v,u)) return false;
            vec.push_back(v);
        }
    }
    if(vec.size()==0){
        dp[u]=1;
        return true;
    }
    //度数为奇数，则儿子为偶数个
    if(deg[u]&1) vec.push_back(0);
    sort(vec.begin(),vec.end(),cmp_dp);
    int v=bin_chop_son(vec);
    if(v==vec.size()) return false;
    dp[u]=dp[vec[v]]+1;
    return dp[u]<=B+1;
}
inline void bin_chop_B(){
    int l=0,r=n;
    while(l<=r){
        B=l+r>>1;
        if(treeDP(rt,0)) r=B-1;
        else l=B+1;
    }
    B=l;
}
inline void cal_A(){
    int cnt=0;
    for(int i=1;i<=n;++i)
        cnt+=deg[i]&1;
    A=cnt>>1;
}
int main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        ++deg[u],++deg[v];
        addE(u,v),addE(v,u);
    }
    cal_A();
    for(int i=1;i<=n;++i){
        if(deg[i]==1){
            rt=i;
            break;
        }
    }
    bin_chop_B();
    printf("%d %d",A,B);
    return 0;
}