ACM周练-10.30

发表于   |   分类于

第一题

原题:hdoj 5971

算法思想

dfs二分染色,先将已知身份的人涂色,再从剩下的人中开始染色,最后如果还有剩下的人未被染色,那就是NO,否则是YES

程序代码

//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <memory.h>
#define  mem(a,b)    memset(a,b,sizeof(a))
using namespace std;
const int MAX=1010;
vector<int> G[MAX];
int color[MAX];
int n,m,x,y;
bool dfs(int v,int c)
{
    color[v]=c;
    for(int i=0;i<G[v].size();i++)
    {
        if(color[G[v][i]]==c) return false;
        if(color[G[v][i]]==0&&!dfs(G[v][i],-c)) return false;
    }
    return true;
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(color[i]==1)
        {
            if(!dfs(i,1))
            {
                puts("NO");
                return ;
            }
        }
        else if(color[i]==-1)
        {
            if(!dfs(i,-1))
            {
                puts("NO");
                return ;
            }    
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(color[i]==0)
            if(!dfs(i,1))
            {
                puts("NO");
                return ;
            }    
    }
    for(int i=1;i<=n;i++)
    {
        if(color[i]==-5)
            {
                puts("NO");
                return ;
            }
    }
    puts("YES");
}
int main()
{
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif

    while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF)
    {
        int a,b;

        for(int i=0;i<=n;i++)
        {
            G[i].clear();
            color[i]=-5;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
            color[a]=color[b]=0;
        }
        for(int i=1;i<=x;i++)
        {
            scanf("%d",&a);
            color[a]=1;
        }
        for(int i=1;i<=y;i++)
        {
            scanf("%d",&a);
            color[a]=-1;
        }
        solve();
    }
    return 0;
}

第二题

原题:hdoj 5978

算法思想

奇偶判断题,先算前几项的概率,就会发现规律

程序代码

#include <cstdio>
#define  ll long long
using namespace std;
int main()
{
    long t;
    while(scanf("%ld",&t)!=EOF)
    {
         if(t%2==0) printf("1\n");
         else printf("0\n");
    }
    return 0;
}

第三题

原题:hdoj 5969

算法思想

位运算,最大位或考虑二进制数位全为1.

程序代码

#include <cstdio>
#define  ll long long
using namespace std;
int main()
{
    int T;
    ll l,r;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&l,&r);
        ll i;
        for(i=1;(l|i)<=r;i<<=1)
            l|=i;
        if(l+1<=r)
        {
            printf("%lld\n",l|i);
        }
        else
            printf("%lld\n",l);
    }
    return 0;
}

第四题

原题:hdoj 5979

算法思想

水题,用三角函数即可

程序代码

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

const float pi=3.1415926;

int main()
{
    int len,point;
    int angle[1000];
    double t=0.0;
    while(scanf("%d",&point)!=EOF)
    {
        t=0.0;

        scanf("%d",&len);

        for(int i=1;i<=point;i++)
            scanf("%d",&angle[i]);



        for(int i=1;i<=point;i++)
            t+=len*len*sin(angle[i]/180.0*pi)*0.5;

        printf("%.3lf\n",t);
    }
    return 0;
}

第五题

原题:hdoj 5410

算法思想

0/1背包问题+无限背包.
推荐背包问题的博客

http://www.cppblog.com/tanky-woo/archive/2010/07/31/121803.html

程序代码

//#define LOCAL
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
#define Maxsize 0x1fffffff
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
int main()
{
#ifdef LOCAL
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
#endif

    int dp[2002];
    int T,value[2002],volume[2002],extra[2002],M,N;
    scanf("%d",&T);
    while(T--)
    {
        mem(dp,0);
        scanf("%d%d",&M,&N);
        for(int i=0;i<N;i++)
            scanf("%d%d%d",&volume[i],&value[i],&extra[i]);
        for(int i=0;i<N;i++)
        {
            for(int j=M;j>=volume[i];j--)
                dp[j]=max(dp[j],dp[j-volume[i]]+value[i]+extra[i]);
            for(int j=volume[i];j<=M;j++)
                dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
        }
        printf("%d\n",dp[M]);
    }
    return 0;
}

第六题

原题:hdoj 5952

算法思想

dfs暴力搜索,如何防止重复走是关键.
详见博客

http://blog.csdn.net/yuanjunlai141/article/details/52972715