当前位置:首页 > 资讯 > info5 > 正文

Codeforces Round #287 (Div. 2) 解题报告 A.B.C.D.E

发表于: 2015-01-26   作者:u013013910   来源:转载   浏览:
摘要: 这次的CF挺水的,当时B题犯了一个很SB的错误,浪费了好多时间,所以D和E也没来得及看。sad,。。A-AmrandMusic水题,从小的开始选。代码如下:#include #include #include #include #include #include #include #include #include usingnamespacestd; #defineLL__int64 #defi

这次的CF挺水的,当时B题犯了一个很SB的错误,浪费了好多时间,所以D和E也没来得及看。sad,。。

A - Amr and Music

水题,从小的开始选。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
struct node {
        int x, n;
} fei[400];
int cmp(node f1, node f2)
{
        return f1.x<f2.x;
}
int main()
{
        int n, m, i, sum=0, j, pos;
        scanf("%d%d",&n,&m);
        for(i=0; i<n; i++) {
                scanf("%d",&fei[i].x);
                fei[i].n=i+1;
        }
        sort(fei,fei+n,cmp);
        pos=n-1;
        for(i=0; i<n; i++) {
                if(sum+fei[i].x>m) {
                        pos=i-1;
                        break;
                } else {
                        sum+=fei[i].x;
                }
        }
        printf("%d\n",pos+1);
        for(j=0; j<=pos; j++) {
                printf("%d ",fei[j].n);
        }
        return 0;
}
B - Amr and Pins

只要距离小于2*r,那么肯定能找到一个点可以正好将圆心移到目标点。所以只要看距离是2*r的多少倍就可以了。该死的精度。。取10^-9就挂了。。换成别的都过了。。无语。。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-11;
int main()
{
        LL r, x1, y1, x2, y2;
        LL a;
        double d, c;
        while(scanf("%I64d%I64d%I64d%I64d%I64d",&r,&x1,&y1,&x2,&y2)!=EOF){
                        r*=2;
                d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
                c=d/r;
                a=(LL)c;
                if(c==a){
                        printf("%I64d\n",a);
                }
                else
                        printf("%I64d\n",a+1);
        }
        return 0;
}

C - Guess Your Way Out!

我的做法是先建树,记录到目标点的最短路径,然后再从根节点出发开始走,如果下一步偏离了路径,那么就加上下一步的所有子树节点的个数。(因为它肯定会遍历完所有子树然后返回)

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
LL ans, c, num[100], cnt, p[100], H;
void update(LL n, LL l, LL r, LL rt)
{
        num[cnt++]=rt;
        if(l==r) return ;
        LL mid=l+r>>1;
        if(n<=mid) update(n,lson);
        else update(n,rson);
}
void dfs(int f, int h, LL l, LL r, LL rt)
{
        if(l==r) return ;
        LL next;
        if(f==-1) next=rt<<1;
        else next=rt<<1|1;
        if(next!=num[h+1]) {
                ans+=p[H-h-1];
                f=-f;
        }
        c>>=1;
        LL mid=l+r>>1;
        if(f==-1) {
                dfs(-f,h+1,lson);
        } else {
                dfs(-f,h+1,rson);
        }
}
void init()
{
        p[0]=1;
        for(int i=1; i<=60; i++) {
                p[i]=p[i-1]+((LL)1<<i);
                //printf("%I64d\n",p[i]);
        }
}
int main()
{
        LL n, i;
        while(scanf("%I64d%I64d",&H,&n)!=EOF) {
                ans=0;
                c=(LL)1<<H;
                cnt=0;
                init();
                update(n-1,0,c-1,1);
                /*for(i=0;i<cnt;i++){
                        printf("%I64d\n",num[i]);
                }*/
                dfs(-1,0,0,c-1,1);
                printf("%I64d\n",ans+H);
        }
        return 0;
}

D - The Maths Lecture

水题啊。。。普通的数位DP而已,用dp[i][j][k]记录第i位(从低位开始数),模为j时,k记录是否已经存在模为0的后缀的状态时的个数。因为要算后缀,所以应该从低位向高位开始搜。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
int mod, k, n;
const int INF=0x3f3f3f3f;
const double eqs=1e-6;
LL dp[1002][101][3], mo[1002];
LL dfs(int cnt, int mods, int in, int zero)
{
        if(cnt==-1) return in;
        if(zero&&dp[cnt][mods][in]!=-1) return dp[cnt][mods][in];
        int l=(cnt==0), i, m, z;
        LL ans=0;
        for(i=l;i<=9;i++){
                m=(mods+i*mo[n-cnt])%k;
                if(i||zero) z=1;
                else z=0;
                ans+=dfs(cnt-1,m,in||(m==0&&z),z);
        }
        ans%=mod;
        if(zero)    {
                        dp[cnt][mods][in]=ans;
        }
        return ans;
}
void init()
{
        int i;
        mo[1]=1%k;
        for(i=2;i<=1000;i++){
                mo[i]=(mo[i-1]*10)%k;
        }
}
int main()
{
        memset(dp,-1,sizeof(dp));
        scanf("%d%d%d",&n,&k,&mod);
        init();
        printf("%I64d\n",dfs(n-1,0,0,0));
        return 0;
}

E - Breaking Good

还是水题。。求一次最短路,将距离标记成一个比较大的数,然后将花费标记成1,这样就能找到了最短而且花费最短的路径了。然后再根据状态标记找到需要改动的路径即可。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
int mod, k, n;
const int INF=0x3f3f3f3f;
const double eqs=1e-6;
int head[110000], cnt, vis[110000], dd[110000], pre[110000], c[110000];
struct node
{
        int u, v, w, next, f, s;
}edge[210000];
void add(int u, int v, int w, int f)
{
        edge[cnt].v=v;
        edge[cnt].w=w;
        edge[cnt].f=f;
        edge[cnt].next=head[u];
        head[u]=cnt++;
}
void spfa()
{
        queue<int>q;
        memset(vis,0,sizeof(vis));
        q.push(1);
        dd[1]=0;
        while(!q.empty()){
                int u=q.front();
                q.pop();
                vis[u]=0;
                for(int i=head[u];i!=-1;i=edge[i].next){
                        int v=edge[i].v;
                        if(dd[v]>dd[u]+edge[i].w){
                                dd[v]=dd[u]+edge[i].w;
                                pre[v]=u;
                                if(!vis[v]){
                                        vis[v]=1;
                                        q.push(v);
                                }
                        }
                }
        }
}
void init()
{
        memset(head,-1,sizeof(head));
        cnt=0;
        memset(dd,INF,sizeof(dd));
        memset(pre,-1,sizeof(pre));
}
int main()
{
        int n, m, i, u, v, w, j, sum=0, cnt1=0;
        scanf("%d%d",&n,&m);
        init();
        while(m--){
                scanf("%d%d%d",&u,&v,&w);
                add(u,v,10000+1-w, w);
                add(v,u,10000+1-w, w);
        }
        spfa();
        for(i=n;i!=-1;i=pre[i]){
                c[cnt1++]=i;
        }
        for(i=1;i<=n;i++){
                for(j=head[i];j!=-1;j=edge[j].next){
                        edge[j].s=0;
                }
        }
        for(i=cnt1-1;i>=1;i--){
                u=c[i];
                for(j=head[u];j!=-1;j=edge[j].next){
                        int v=edge[j].v;
                        if(v==c[i-1]){
                                edge[j].s=1;
                                edge[j^1].s=1;
                                //printf("%d %d %d\n",u,v,edge[j].w);
                        }
                }
        }
        for(i=1;i<=n;i++){
                for(j=head[i];j!=-1;j=edge[j].next){
                        if(edge[j].s+edge[j].f==1){
                                edge[j^1].f=1-edge[j^1].f;
                                //printf("%d %d %d %d\n",i,edge[j].v,edge[j].s,edge[j].w);
                                sum++;
                        }
                }
        }
        printf("%d\n",sum);
        for(i=1;i<=n;i++){
                for(j=head[i];j!=-1;j=edge[j].next){
                        if(edge[j].s+edge[j].f==1){
                                printf("%d %d %d\n",i,edge[j].v,edge[j].s);
                        }
                }
        }
        return 0;
}


Codeforces Round #287 (Div. 2) 解题报告 A.B.C.D.E

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
------------ A. Flipping Game 有n个整数a1, a2, ..., an,每个整数只可能为0或1。 选择一个区
---------------- A. Magic Numbers 一个神奇的数字是由1、14、144连接而成的,判断一个数字是不是
所以苟蒻万年不做E。。。 A: A. Bulbs time limit per test 1 second memory limit per test 256 m
A. Patrick and Shopping time limit per test 1 second <div class="memory-limit" style="marg
A. Currency System in Geraldion: 题意:有n中不同面额的纸币,问用这些纸币所不能加和到的值的最
621A-Wet Shark and Odd and Even time limit per test2 seconds memory limit per test256 megabyt
A. Amr and Music time limit per test 1 second memory limit per test 256 megabytes input stand
B. Amr and Pins time limit per test 1 second memory limit per test 256 megabytes input standa
B. Amr and Pins time limit per test 1 second memory limit per test 256 megabytes input standa
A. Amr and Music (贪心) 水题,没能秒切,略尴尬。 1 #include <cstdio> 2 #include <alg
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号