2020牛客国庆集训派对day5 部分题解

前言

自己还是好菜啊qwq

B Hyperdrome

题意：给一个整数n以及一串长度为n的字符串。求他有多少个子区间中的字符能够通过重新排列形成一个回文串。
分析：
1. 因为能够重新排列，所以不能直接用manacher(~~这是一个悲伤的故事~~)。那我们就考虑一个区间能够通过重新排列形成回文串的条件
2. 回文串：
  
  “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
  
  即镜像对称。那么他们每一个字符的出现次数只有两种情况：1.全部都是偶数次 2.一个是奇数次，其余全部是偶数次。考虑他们的次数对二取模，状态压缩每一个字符的出现次数。
  1. 对于情况一：因为全部是偶数次，设当前的状态为x，如果每一个数的出现次数为偶数(即0)，
    $图片说明$
    这就是一个前缀异或和的思想
  2. 对于情况二：肯定要枚举哪个数字出现的次数为奇数次，然后如情况一一般求出答案
3. 因为一共52个字符，直接压缩下来回MLE，那就只压缩23个字符的次数，利用链表的存储就可以减少一定的查询时间与空间，具体看代码
代码：

/*
    如果一个区间在rearrenged之后

出现次数为奇数的数只有1个或者没有

那么重构后就能形成一个回文串

    链表--->ac
*/
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=3e5+10,M=210;
const ll mod=8388607;//取余，不然要炸 

int n,tot;
char s[N];
ll p[M],h[mod+10],nex[N],ver[N],cnt[N];

inline int get(int x)
{
    if(x>='a'&&x<='z') return x-'a'+27;
    return x-'A'+1;
}//表示每一个字母

inline void ins(ll x)
{
    ll y=(x&mod);//只记录后几位
    for (int i=h[y];~i;i=nex[i])
        if(ver[i]==x)
        {
            cnt[i]++;
            return ;
        }

    nex[tot]=h[y];
    ver[tot]=x;
    cnt[tot]=1;
    h[y]=tot++;
}

inline ll find(ll x)
{
    for (int i=h[(x&mod)];~i;i=nex[i])
        if(ver[i]==x) return cnt[i];
    return 0;
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d%s",&n,s);ins(0);//初始化
    for (int i=1;i<=52;i++) p[i]=(1ll<<i);

    ll now=0,ans=0;
    for (int i=1;i<=n;i++)
    {
        int to=get(s[i-1]);now^=p[to];
        for (int j=0;j<=52;j++)
        {//j=0情况一;j!=0,情况二
            ll sum=find(now^p[j]);
            if(sum!=0) ans+=sum;
        }

        ins(now);
    }

    printf("%lld\n",ans);

    return 0;
}

C Great Deceiver

题意：给定一个n与k，求小于等于n的数中有多少个数，表示为k进制与-k进制后每一位对应相等。
分析：
1. 看个式子就明白了
  $图片说明$
  $图片说明$
  当幂次是偶数时，k为正负无所谓，但是如果是奇数次幂，那就会不同，很明显就是一个数位dp
2. 设 f [ i ] [ j ]:当前是第i层，上一个数字是j满足条件的方案数
代码：

//数位dp
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e2;

ll n,k;
ll a[N],f[N][N*12];

inline ll dfs(bool eq,ll dep,ll las)
{
/*
eq作用：判断边界。以为我们是从最高位填到最低位的，就假设n=555，如果百位上我已经
填了5，那么十位上要保证这个数不大于555，十位最高只能填到5
*/
    if(!eq&&f[dep][las]!=-1) return f[dep][las];
//数位dp的精髓：记忆化搜索
    if(!dep) return 1;

    ll ep=(eq ? a[dep]:k-1),ret=0;//判断这一位能填哪些数
    for (ll i=0;i<=ep;i++)
    {
        if(dep&1) ret+=dfs(eq&&(i==ep),dep-1,i);
        else
        {
            ret+=dfs(eq&&(a[dep]==0),dep-1,0);
            break;//因为这个时候的幂次是奇数，只能在这一位填0
        }
    }

    if(!eq) f[dep][las]=ret;
    return ret;
}


inline void Get(ll x)
{
    while(x)
    {
        a[++a[0]]=x%k;
        x/=k;
    }//求出每一位最高能填到哪里

    printf("%lld\n",dfs(1,a[0],0));//越位,层数,上一个数字
}

int main()
{
    memset(f,-1,sizeof(f));
    scanf("%lld%lld",&n,&k);

    Get(n);

    return 0;
}

D Exact Measurement

题意：给定一个整数x与n中不同类型的砝码。每一种砝码的质量都是10^k(k是自然数)，每一个箱子里面且都有一定个数的砝码。问如何通过开启最少的箱子凑够x
分析：
1. 考虑从低位到高位贪心，因为个位上的数只能通过质量为1的砝码凑出，当凑够个位时，就考虑十位，十位能够被质量为10和1的砝码凑出，以此类推
2. 当我们开启一个箱子，其实并不需要考虑如何才能恰好组成相对应的质量，考虑把他所有的砝码都拿光，并不是一定要刚好凑成x，即使最后有余数，那些其实都是进位后剩下的，相当于不取。
3. 记录一个优先队列存入砝码的序号以及能称量的最大质量，从个位开始，每做完一位，便将下一位的砝码加入到队列中
代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e5+10;

ll x,n;
ll cnt[N],p[22]={1};

bool vis[N];

vector<ll>g[22];

struct nkl
{
    ll tot,id;
    bool operator < (const nkl &b)const
    {
        return tot<b.tot;
    }//按照称量总量从大到小排序
    nkl (ll x,ll y):tot(x),id(y){}
};
priority_queue<nkl>q;

int main()
{
    scanf("%lld%lld",&x,&n);
    for (ll i=1,a;i<=n;i++)
    {
        scanf("%lld%lld",&a,&cnt[i]);
        g[a].push_back(i);//记录10^k的砝码有哪些
    }

    ll las=0;
    for (ll i=1;i<=20;i++) p[i]=p[i-1]*10ll;
    for (ll i=0;i<=18;i++)
    {
        ll len=g[i].size(),now=x%p[i+1];
        for (ll j=0;j<len;j++)
        {
            ll a=g[i][j];
            q.push(nkl(p[i]*cnt[a],a));
        }//解封

        while(las<now&&q.size())
        {
            nkl u=q.top();q.pop();
            las+=u.tot;vis[u.id]=1;
        }
        if(las<now) {las=-1;break;}
    }

    if(las==-1) puts("-1");
    else
    {
        ll ans=0;
        for (ll i=1;i<=n;i++) ans+=vis[i];
        printf("%lld\n",ans);
        for (ll i=1;i<=n;i++)
            if(vis[i]) printf("%lld ",i);
    }

    return 0;
}

E Caravan Robbers

题意：输入 n条线段，把每条线段变成原线段的一条子线段，使得改变之后所有线段等长且不相交（但是端点可以重合）。输出最大长度（用分数表示）。例如，有 3 条线段[ 2 , 6 ] ，[ 1 , 4 ] ，[ 8 , 12 ] ，则最优方案是分别变成 [ 3.5 , 6 ] ， [ 1 , 3.5 ] ， [8 , 10.5 ] ，输出 5/2 。
分析：
1. 首先解决第一个问题，求出答案。可以通过二分答案的方法，验证而二分出来的mid能否使原先的区间化为符合条件的子区间
2. 转化为分数——选择枚举分母，通过判断与答案的误差来选取与二分出来的结果误差最小的一个。
代码

#include<bits/stdc++.h>

#define dl double

using namespace std;

const int N=1e5+10;
const dl eps=1e-10;

int n;

struct nkl
{
    dl x,y;

    bool operator < (const nkl &b)const
    {
        if(x==b.x) return y<b.y;
        return x<b.x;
    }
}s[N];

inline bool check(dl mid)
{
    dl now=0.0;//右端点
    for (int i=1;i<=n;i++)
    {
        if(s[i].y-s[i].x<mid) return 0;
        now=max(s[i].x,now)+mid;
        if(now>s[i].y) return 0;
    }
    return 1;
}

inline int gcd(int x,int y)
{
    if(!y) return x;
    return gcd(y,x%y);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lf%lf",&s[i].x,&s[i].y);
    sort(s+1,s+n+1);

    dl l=0,r=1e6,ans=-1;
    while(r-l>eps)
    {
        dl mid=(l+r)/2.0;
        if(check(mid)) l=mid,ans=mid;
        else r=mid;
    }

    //逼近小数ans 
    int zi=0,mu=1;
    for (int i=1;i<=n;i++)
    {
        dl p=round(ans*i);
        if(fabs(p/i-ans)<fabs(zi*1.0/mu-ans))
        {
            zi=p;
            mu=i;
        }
    }

    int kp=gcd(zi,mu);
    printf("%d/%d\n",zi/kp,mu/kp);

    return 0;
}