hgoi#20190515

muronglin
muronglin 2019年05月15日
  • 在其它设备中阅读本文章

T1-Pie or die

Volodya 和 Vlad 在玩下面的这个游戏。这里有 k 个派,分布在 n×m 的板子上。每一回合 Volodya 移动一个派到这个派边界的格子,如果这个派在板子的边界,Volodya 就可以把它移出板,得到这个派并且获胜。在 Volodya 移动之后,Vlad 在板的边界放一个长度为 1 的挡板,然后 Volodya 就不能把派从挡住的边移出。 请问,Volodya 会赢得这次比赛吗?(我们假设两个玩家都无比聪明)

解法

明显的贪心,如果已经在边界上有派了,能赢 如果没有的话,显然只能走到边角获胜 看离边界最近的距离是否超过 4,如果不超过 4,对手无法封锁全部边角,能赢 如果超过 4,对手能封锁所有边角,输了

ac 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,flg=1;
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&x,&y);
        if(x==1||x==n||y==1||y==m)flg=0;
        if(x-1<=4||n-x<=4||y-1<=4||m-y<=4)flg=0;
    }
    if(flg)puts("NO");else puts("YES");
    return 0;
}

T2-Beautiful numbers

Volodya 是一个很皮的男♂孩。他认为一个能被它自己的每一位数上的数整除的数是很妙的。我们先忽略他的想法的正确性(如需证明请百度“神奇海螺”),只回答在 l 到 r 之间有多少个很妙的数字。

解法

数位 dp,和记忆化搜索很相似 我们设 dp[i][j][k]表示当前的数为 i 位,mod 2520 为 j,当前数的每一位数的 lcm 为 k 的答案种类 发现要存 18×2520×2520,可能会爆,就预处理出所有可能的 lcm,就可以简化为 50 左右了 至于数位 dp,主要处理上限,如果前面几位不是上限的前几位,后面没有限制,可以记忆化搜索 如果前面几位和上限一样,这一位就不能都取,不能记忆化,相当于多扫一层 复杂度不太清楚,大概是 O(能过),(大雾

ac 代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll T,l,r,cnt=0,w[20],mp[3000],dp20[50];
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll dfs(int len,int pre,int mod,int lim)
{
    if(!len)return pre%mod==0;
    if(!lim&&dplen[mp[mod]]!=-1)return dplen[mp[mod]];
    ll res=0,maxx=lim?w[len]:9;
    for(int i=0;i<=maxx;i++)
        res+=dfs(len-1,(pre10+i)%2520,i==0?mod:modi/gcd(mod,i),lim&&i==maxx);
    if(!lim)dplen[mp[mod]]=res;
    return res;
}
ll calc(ll n,ll len)
{
    while(n){w[++len]=n%10,n/=10;}
    return dfs(len,0,1,1);
}
int main()
{
    for(int i=1;i<=2520;i++)if(2520%i==0)mp[i]=++cnt;
    memset(dp,-1,sizeof(dp)),scanf("%lld",&T);
    while(T--){scanf("%lld%lld",&l,&r),printf("%lldn",calc(r,0)-calc(l-1,0));}
    return 0;
}

T3-Geometry Horse

给定 n 种物品,每种物品有 Ki 个,价值为 Ci,摧毁一个物品的贡献为 Ci×f f 为贡献因子,有一个长度为 t 的单调递增序列 p,当前摧毁的物品若超过 p[i],则贡献因子 f =i+1 求最大贡献

解法

主要题意好难读懂啊 emm 读懂之后,是一个比 T1 还显然的贪心,让价值小的先摧毁,价值大的后摧毁,模拟一遍 =-=

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define inf 2333333333333333333
using namespace std;
struct node{int k,c;}a[110];
int n,m,nw=1;
ll ans=0,p[110];
int cmp(node x,node y){return x.c<y.c;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].k,&a[i].c);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%lld",&p[i]);
    for(int i=m;i>1;i--)p[i]-=p[i-1];
    p[m+1]=inf;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        while(a[i].k>p[nw])ans+=1llnwa[i].c*p[nw],a[i].k-=p[nw],nw++;
        ans+=1llnwa[i].c*a[i].k,p[nw]-=a[i].k;
    }
    printf("%lldn",ans);
    return 0;
}

T4-Plane of Tanks: Duel

坦克的属性:血量,攻击间隔,攻击下限与上限,攻击不命中的概率
现有 2 个坦克,求第一个坦克获胜的概率(当 2 个坦克同时死亡时,算第一个坦克获胜)

解法

可以模拟,但是发现如果 2 个坦克一直没打中,会停不下来 =-= 看到题目的精度要求,可以这样做,一直模拟直到 1 个坦克的存活率低于 eps,然后停止 稍微调一调精度就能过,主要是 dp 模拟坦克的行动,并且分开处理

ac 代码

#include<bits/stdc++.h>
#define eps (1e-8)
using namespace std;
double dp2[210],p[2],ans;
int n,x,y,a[2],t[2],l[2],r[2];
int main()
{
    for(int i=0;i<2;i++)scanf("%d%d%d%d%lf",&a[i],&t[i],&l[i],&r[i],&p[i]);
    if(abs(p[0]-100.0)<eps){puts("0.000000");return 0;}
    if(abs(p[1]-100.0)<eps){puts("1.000000");return 0;}
    dp0[a[0]]=dp1[a[1]]=1,p[0]/=100.0,p[1]/=100.0;
    for(x=1;x<=10000;x++)
    {
        for(int i=0;i<2;i++)for(int j=1;j<=a[i];j++)
        {
            if(dpi[j]<=eps)continue;
            for(int k=l[i^1];k<=r[i^1];k++)
                dpi[max(0,j-k)]+=dpi[j]*(1-p[i^1])/(r[i^1]-l[i^1]+1);
            dpi[j]+=dpi[j]*p[i^1];
        }
        dp0[0]+=dp0[0];
    }
    for(int i=1;i<=x;i++)
    {
        y=((i-1)*t[0]+t[1]-1)/t[1];
        if(y>x)break;
        ans+=(1-dp0[0])*dp1[0];
    }
    printf("%.6lfn",ans);
    return 0;
}

T5-Alphabet Permutations

给定一个长度为 n(n<200000)的字符串 s, 有两种指令: 1. 将区间 [L,R] 内的字符变为 ch 2. 给定长度为 k(1<=k<=10)的字符串排列 t,向 s 串中添加字符,使得 s 以 t 为模式循环,求最少的循环次数 最多 20000 条指令

解法

建一棵线段树,在每个节点里放一个 k^2 的数组,记录两个 ch 直接相连的情况,操作 1 就是区间修改 至于询问,记录一下每个字母在模式串中的出现位置,即 rk,当 rk[i]>rk[j]时 ans+=[1][i][j] 即当一个字母在另一个字母的后面时,与它相连的另一个字母一定会跳转到下一个模式串,即 1 的贡献

ac 代码

#include<bits/stdc++.h>
#define mem(a) memset(a,0,sizeof(a))
#define mid ((l+r)>>1)
using namespace std;
char ch;
int n,m,k,c,l,r,ans,rk[10],a800010[10],tg[800010],lc[800010],rc[800010];
void f(int x,int c,int len){mem(a[x]),ax[c]=len-1,lc[x]=rc[x]=tg[x]=c;}
void down(int x,int l,int r){if(tg[x]>-1)f(x<<1,tg[x],mid-l+1),f(x<<1|1,tg[x],r-mid);}
void upd(int x)
{
    int l=x<<1,r=x<<1|1;
    for(int i=0;i<k;i++)for(int j=0;j<k;j++)ax[j]=al[j]+ar[j];
    ax][lc[r]]++,lc[x]=lc[l],rc[x]=rc[r];
}
void build(int x,int l,int r)
{
    if(l==r){scanf(" %c",&ch),lc[x]=rc[x]=ch-'a';return;}
    build(x<<1,l,mid),build(x<<1|1,mid+1,r),upd(x);
}
void modify(int x,int l,int r,int p,int q,int d)
{
    if(l>=p&&r<=q){f(x,d,r-l+1);return;}else if(l>q||r<p)return;
    down(x,l,r),tg[x]=-1,modify(x<<1,l,mid,p,q,d),modify(x<<1|1,mid+1,r,p,q,d),upd(x);
}
int main()
{
    memset(tg,-1,sizeof(tg)),scanf("%d%d%d",&n,&m,&k),build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&c),ans=0;
        if(c==1)scanf("%d%d %c",&l,&r,&ch),modify(1,1,n,l,r,ch-'a');
        else
        {
            for(int i=0;i<k;i++)scanf(" %c",&ch),rk[ch-'a']=i;
            for(int i=0;i<k;i++)for(int j=0;j<k;j++)if(rk[i]>=rk[j])ans+=a1[j];
            printf("%dn",ans+1);
        }
    }
    return 0;
}