[Codeforces Round#417 Div.2]

来自FallDream的博客，未经允许，请勿转载，谢谢。

有毒的一场div2 找了个1300的小号，结果B题题目看错没交 D题题目剧毒 E题差了10秒钟没交上去。

233

-------

A.Sagheer and Crossroads

[Codeforces Round#417 Div.2]

有一个十字路口，分别给出每个方向左右转和直行以及行人的红绿灯的状态，求有没有可能有行人会被车撞

大判断。附上大佬@ACMLCZH的代码

#include <cstdio>
#include <cstring>
int a[5][5];

inline int read()
{
    int n=0,f=1; char c=getchar();
    while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
    while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
    return n*f;
}

int main()
{
    register int i,j,x,y;
    for (i=0;i<4;++i)
        for (j=0;j<4;++j) a[i][j]=read();
    for (i=0;i<4;++i)
        for (j=0;j<3;++j) if (a[i][j]&&a[i][3]) return 0*printf("YES");
    if (a[0][3]) if (a[1][0]||a[2][1]||a[3][2]) return 0*printf("YES");
    if (a[1][3]) if (a[2][0]||a[3][1]||a[0][2]) return 0*printf("YES");
    if (a[2][3]) if (a[3][0]||a[0][1]||a[1][2]) return 0*printf("YES");
    if (a[3][3]) if (a[0][0]||a[1][1]||a[2][2]) return 0*printf("YES");
    printf("NO");
}

B Sagheer, the Hausmeister

给定一个宿舍，两边是楼梯，中间是房间，有些房间有灯亮着，你要从1楼向上走，把一层的灯关完之后才能上楼，问把所有的灯关完至少要走多少步。

直接dp,f[i][0/1]表示关完前i层在左/右边的最小步数。

#include<iostream>
#include<cstdio>
using namespace std;
inline int read()
{
    int x = 0 , f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}

int n,m,r[17],l[17],f[17][2];
char st[17][105];

int main()
{
    n=read();m=read()+2;
    for(int i=1;i<=n;++i) scanf("%s",st[i]+1);
    for(int i=1;i<=n;++i)
    {
        for(int j=m;j;--j)
            if(st[i][j]=='1') {r[i]=j;break;}
        for(int j=1;j<=m;++j)
            if(st[i][j]=='1') {l[i]=j;break;}
    }
    int i=1;
    for(;i<=n&&!r[i];++i);
    if(i>n) return 0*puts("0");
    f[i][0]=r[i]-1,f[i][1]=m-l[i];
    for(++i;i<=n;++i)
    {
        if(!r[i]) f[i][0]=f[i-1][0]+1,f[i][1]=f[i-1][1]+1;
        else
        {
            f[i][0]=min(f[i-1][0]+2*(r[i]-1)+1,f[i-1][1]+m);
            f[i][1]=min(f[i-1][1]+2*(m-l[i])+1,f[i-1][0]+m);    
        }
    }
    printf("%d
",min(f[n][0],f[n][1]+m-1));
    return 0;
}

C. Sagheer and Nubian Market

有n个物品，基础价格是ci,买k个物品的话价格会变成ci+k*i,求最多能买几个

二分答案，然后排序一下就好了

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
    int x;char c;
    while((c=getchar())<'0'||c>'9');
    for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0';
    return x;
}
#define MN 100000
int a[MN+5];
long long v[MN+5];
int main()
{
    int n,m,i,j,l,r,mid,ans,c;
    n=read();m=read();
    for(i=1;i<=n;++i)a[i]=read();
    for(l=0,r=n;l<=r;)
    {
        mid=l+r>>1;
        for(i=1;i<=n;++i)v[i]=a[i]+1LL*i*mid;
        sort(v+1,v+n+1);
        for(i=1,j=m;i<=mid;++i)if(j>=v[i])j-=v[i];else break;
        if(i>mid)l=mid+1,ans=mid,c=m-j;else r=mid-1;
    }
    printf("%d %d",ans,c);
}

D.毒题

好好写题面不好吗？考验读题能力？？？？

E.Sagheer and Apple Tree

给你一棵树，每个点有一些苹果。两个人博弈。

每次选择一种操作

1)选择一个叶子节点，吃掉一些苹果。

2)选择一个非叶子节点，把一些苹果移到它的儿子处。

n<=10^5 满足叶子结点奇偶性相同。

求有多少种方法交换两个点的苹果数量，后手必胜？

发现当与叶子结同奇偶的苹果树塔起来等于0的时候后手必胜。

枚举换哪个，用个桶统计方案数。

然后如果一开始就是0，偶数深度之间随便换，奇数也是。

#include<iostream>
#include<cstdio>
#define MN 100000
using namespace std;
inline int read()
{
    int x = 0 , f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}

int n,head[MN+5],s[20000005],s2[20000005],cnt=0,a[MN+5];
struct edge{int to,next;}e[MN*2+5];

inline void ins(int f,int t)
{
    e[++cnt]=(edge){t,head[f]};head[f]=cnt;    
}
int dd,d[MN+5];
void Dfs(int x,int fa,int dep)
{
    d[x]=dep;
    if(dep&1) ++s[a[x]];else ++s2[a[x]];
    int son=0;
    for(int i=head[x];i;i=e[i].next)
        if(e[i].to!=fa)
            ++son,Dfs(e[i].to,x,dep+1);
    if(!son) dd=dep;
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=2;i<=n;++i) 
    {
        int fa=read();
        ins(fa,i);ins(i,fa);    
    }
    Dfs(1,0,1);int ans=0,num=0;
        for(int i=1;i<=n;++i)
            if((d[i]&1)==(dd&1))    
                ans^=a[i],++num;
    long long aa=0;
    for(int i=1;i<=n;++i)
            if((d[i]&1)==(dd&1))
                aa+=(dd&1)?s2[a[i]^ans]:s[a[i]^ans];
    if(ans==0) aa+=1LL*num*(num-1)/2+1LL*(n-num)*(n-num-1)/2;
    cout<<aa;
    return 0;
}

[Codeforces Round#417 Div.2]

相关推荐