codeforces round #499(div2) 做题记录

codeforces round #499(div2) 做题记录

A. Stages

题意：

给你n个字母，你要选k个，你选择的相邻两个字母在字母表中必须满足中间至少隔一个字母，每个字母的权值是c-‘a’+1，求最小权值和。

k<=n<=50

题解：贪心，从前向后扫，满足题意的就加进去就可以了

#include<bits/stdc++.h>
#define ll long long
#define maxn 55
using namespace std;
int n,k;
char s[maxn];
int w[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    for(int i=1;i<=n;++i)w[s[i]-'a'+1]++;
    int last=-1,tot=0,ans=0;
    for(int i=1;i<=26;++i)if(w[i]&&i-last>1)
    {
        tot++;ans+=i;last=i;
        if(tot==k)break;
    }
    if(tot<k)puts("-1");else printf("%d
",ans);
    return 0;
}

B. Planning The Expedition

题意：

你有n个人，m个食品，每个食品有一个种类a_i，你现在要用这些食品喂饱这些人，每个人第一天吃了哪个种类的食品以后每天都必须吃这个种类的食品，求让这n个人生存的最大天数

n,m,a_i<=100

题解：

枚举天数，然后check一遍

#include<bits/stdc++.h>
#define maxn 105
using namespace std;
int n,m;
int c[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int x,i=1;i<=m;++i)scanf("%d",&x),c[x]++;
    for(int T=1;T<=1000;++T)
    {
        int tot=0;
        for(int i=1;i<=100;++i)tot+=c[i]/T;
        if(tot<n)
        {
            printf("%d
",T-1);
            return 0;
        }
    }
    return 0;
}

C. Fly

题意：

有n个星球，你要从1->2->3->……->n->1，每次起飞降落都要消耗燃料，消耗的燃料*系数=(飞船重量m+燃料重量)，给定每次的系数a_i和b_i,求最少要带多少燃料

n,m<=1000

题解：

把起降的序列搞出来，然后从最后一次剩余燃料开始解方程即可，方程无解就是-1

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
const double eps=1e-7;
int n;
double m;
double a[maxn],b[maxn],c[maxn*2];
int main()
{
    scanf("%d",&n);
    scanf("%lf",&m);
    for(int i=1;i<=n;++i)scanf("%lf",&a[i]);
    for(int i=1;i<=n;++i)scanf("%lf",&b[i]);
    for(int i=1;i<=n;++i)c[i*2-2]=b[i],c[i*2-1]=a[i];
    c[0]=0;c[n*2]=b[1];n*=2;
    for(int i=1;i<=n;++i)
    {
        if(c[i]-1<=eps)
        {
            puts("-1");
            return 0;
        }
    }
    double t=0;
    for(int i=n;i;--i)
    {
        t=(m+c[i]*t)/(c[i]-1);
    }
    printf("%.10lf
",t);
    return 0;
}

D.Rocket

题意：

交互题

给你一个范围1~m，让你猜一个数x，每次系统会告诉你你猜的数y是y<x还是y=x还是y>x

但系统会说谎，具体来说，有一个长度为n的01序列，0表示说谎，1表示不说谎，系统按这个序列循环询问。

但你只知道n和m，并不知道序列，你要猜出这个数

n<=30,m<=1e9,询问次数<=60

题解：

首先我们可以询问1-n，如果猜中很好，如果没猜中那么答案肯定>i,所以这个序列就可以在n次询问被确定下来

然后二分就行了

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[35];
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;++i)
    {
        printf("%d
",i+1);
        fflush(stdout);
        int opt;
        scanf("%d",&opt);
        if(opt==0)
        {
            return 0;
        }
        if(opt==1)a[i]=1;
        if(opt==-1)a[i]=-1;
    }
    int l=1,r=m;
    for(int T=0;T<30;++T)
    {
        int x=T%n;
        int mid=(l+r)>>1;
        printf("%d
",mid);
        fflush(stdout);
        int opt;
        scanf("%d",&opt);
        if(opt==0)
        {
            return 0;
        }
        opt*=a[x];
        if(opt==-1)r=mid-1;
        if(opt==1)l=mid+1;
    }
    return 0;
}

E. Border

题意：

你有n个数，每个数可以用无限次，求在模k意义下你能表示出哪些数

n,k<=100000

题解：

有一个结论是能被这些数模k意义下线性表示的最小数是gcd(k,a_1,a_2,……，a_n)

然后是这个数的倍数都可以

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,k;
int a[maxn];
int gcd(int a,int b)
{
    if(!b)return a;
    return gcd(b,a%b);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    int t=k;
    for(int i=1;i<=n;++i)t=gcd(a[i],t);
    int tot=0;
    for(int i=1;i<=k;++i)
    {
        if(i%t==0)tot++;
    }
    printf("%d
",tot);
    if(k%t==0)printf("0 ");
    for(int i=1;i<k;++i)
    {
        if(i%t==0)printf("%d ",i%k);
    }
    return 0;
}

F. Mars rover

题意：

不好描述，直接英文看题面吧 http://codeforces.com/contest/1011/problem/F

题解：

考虑每次改动只影响一条链，所以我们可以预处理出来每个点状态为0/1，其他不变，朝上跳会变成什么数

倍增搞一搞就行了

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n;
int tp[maxn],fa[maxn],son[maxn][2],val[maxn];
void dfs(int u)
{
    if(tp[u]==1)return;
    if(son[u][0])dfs(son[u][0]);
    if(son[u][1])dfs(son[u][1]);
    if(tp[u]==2)val[u]=val[son[u][0]]^1;
    if(tp[u]==3)val[u]=val[son[u][0]]&val[son[u][1]];
    if(tp[u]==4)val[u]=val[son[u][0]]|val[son[u][1]];
    if(tp[u]==5)val[u]=val[son[u][0]]^val[son[u][1]];
}
int anc[maxn][22];
bool Ans[2][maxn][22];
inline int get(int u,int v,int x)
{
    if(tp[u]==2)return x^1;
    int ls=son[u][0],rs=son[u][1];
    if(rs==v)swap(ls,rs);
    if(tp[u]==3)return x&val[rs];
    if(tp[u]==4)return x|val[rs];
    if(tp[u]==5)return x^val[rs];
}
void init()
{
    for(int i=2;i<=n;++i)
    {
        anc[i][0]=fa[i];
        Ans[0][i][0]=get(fa[i],i,0);
        Ans[1][i][0]=get(fa[i],i,1);
    }
    for(int j=1;j<=20;++j)
    {
        for(int i=1;i<=n;++i)
        {
            anc[i][j]=anc[anc[i][j-1]][j-1];
            Ans[0][i][j]=Ans[Ans[0][i][j-1]][anc[i][j-1]][j-1];
            Ans[1][i][j]=Ans[Ans[1][i][j-1]][anc[i][j-1]][j-1];
        }
    }
}
int query(int u)
{
    int ans=val[u]^1;
    for(int i=20;i>=0;--i)if(anc[u][i])
    {
        ans=Ans[ans][u][i];
        u=anc[u][i];
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        char opt[5];
        scanf("%s",opt);
        int x,y;
        if(opt[0]=='I')
        {
            tp[i]=1;
            scanf("%d",&x);
            val[i]=x;
        }
        if(opt[0]=='N')
        {
            tp[i]=2;
            scanf("%d",&x);
            son[i][0]=x;fa[x]=i;
        }
        if(opt[0]=='A')
        {
            tp[i]=3;
            scanf("%d%d",&x,&y);
            son[i][0]=x;son[i][1]=y;fa[x]=fa[y]=i;
        }
        if(opt[0]=='O')
        {
            tp[i]=4;
            scanf("%d%d",&x,&y);
            son[i][0]=x;son[i][1]=y;fa[x]=fa[y]=i;
        }
        if(opt[0]=='X')
        {
            tp[i]=5;
            scanf("%d%d",&x,&y);
            son[i][0]=x;son[i][1]=y;fa[x]=fa[y]=i;
        }
    }
    dfs(1);
    init();
    for(int i=1;i<=n;++i)if(tp[i]==1)printf("%d",query(i));
    puts("");
    return 0;
}