首页 > 代码库 > 2014百度之星程序设计竞赛

2014百度之星程序设计竞赛

2024-07-06 06:15:27   224人阅读

资格赛

Energy Conversion

水题。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll n,m,v,k;
        scanf("%I64d%I64d%I64d%I64d",&n,&m,&v,&k);
        if(m<n&&(m<v||(m*(1-k)+v*k>=0)))
            printf("-1\n");
        else
        {
            int cnt=0;
            while(m<n)
            {
                m=(m-v)*k;
                cnt++;
            }
            printf("%d\n",cnt);
        }
    }
    return 0;
}
View Code

 

Disk Schedule

双调欧几里得旅行商算法（DP）。

明显最优解是从0轨道再到最后轨道，再从最后轨道回到0轨道，并在此过程中读取所有数据。这很明显就是双调欧几里得旅行商问题。

下面是双调欧几里得旅行商问题的状态转移方程。

dp[i][j]（i>=j)表示从i到1再从1到j经历1到i所有点的最短距离,d[i][j]表示i点到j点的距离。

当i=j时，即A和B处于同一点，dp[i, j]=dp[i, i]=dp[i-1, i]+d[i-1, i]
当i=j-1时，即A在B紧邻的靠后一点，dp[i, j]=dp[j-1, j]=min(1<=k<=j-1){dp[k, j-1]+d[k, j]}
当i<j-1时，即A在B后且相隔多个点，dp[i, j]=dp[i, j-1]+d[j-1, j]

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int short_path(int st,int ed)
{
    return min(abs(st-ed),360-max(st,ed)+min(st,ed));
}
int dp[1005][1005];
int p[1005];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int lmax=0;
        p[0]=0;
        for(int i=1; i<=n; ++i)
        {
            int t;
            scanf("%d%d",&t,&p[i]);
            lmax=max(lmax,t);
        }
        n++;
        memset(dp,0x7f,sizeof(dp));
        dp[0][0]=0;
        for(int j=0; j<n; ++j)
            for(int i=j; i<n; ++i)
            {
                if(i==0&&j==0) continue;
                if(i==j)
                {
                     dp[i][j]=dp[i][j-1]+short_path(p[i],p[i-1]);
                }
                else if(i-1==j)
                {
                    for(int k=0; k<j; ++k)
                        dp[i][j]=min(dp[i][j],dp[j][k]+short_path(p[i],p[k]));
                }
                else if(j<i-1)
                    dp[i][j]=dp[i-1][j]+short_path(p[i],p[i-1]);
            }
        printf("%d\n",lmax*800+dp[n-1][n-1]+(n-1)*10);
    }
    return 0;
}
View Code

 

Xor Sum

字典树。

求异或结果最大即使得两个数字在二进制下的高位尽量不同。将数组中的所有数字转化成长度为32的二进制字符串插入到字典树中。对于每次查询，将数字转成长度为32的二进制字符串在字典树里面查找。如果某位置的0和1两个子节点都存在，那么转移到与原串该位置不同的子结点，否则转移的存在的那个子节点。

注意最后返回的是原数组里的数字，不是异或的最大值。要用unsigned int。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
unsigned int arr[100001];
struct Tire
{
    int ch[100001*32][2],val[100001*32];
    int sz;
    int idx(char c)
    {
        return c-‘0‘;
    }
    void init()
    {
        sz=1;
        memset(ch[0],0,sizeof(ch[0]));
        val[0]=0;
    }
    void insert(char *str,int v)
    {
        int u=0;
        for(int i=0; str[i]; ++i)
        {
            int c=idx(str[i]);
            if(!ch[u][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz]=0;
                ch[u][c]=sz++;
            }
            u=ch[u][c];
        }
        val[u]=v;
    }
    unsigned int solve(char *str,unsigned int v)
    {
        int u=0;
        for(int i=0; str[i]; ++i)
        {
            if(ch[u][0]&&ch[u][1])
            {
                if(str[i]==‘0‘) u=ch[u][1];
                else u=ch[u][0];
            }
            else if(ch[u][0])u=ch[u][0];
            else u=ch[u][1];
            if(val[u])  return arr[val[u]];
        }
    }
};
Tire tree;
void convers(char *str,unsigned v)
{
    for(int i=31; i>=0; --i)
    {
        str[i]=v%2+‘0‘;
        v=v/2;
    }
    str[32]=0;
}
int main()
{
    int T,kase=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        tree.init();
        for(int i=1; i<=n; ++i)
        {
            scanf("%u",&arr[i]);
            char str[40];
            convers(str,arr[i]);
            tree.insert(str,i);
        }
        printf("Case #%d:\n",++kase);
        while(m--)
        {
            unsigned int t;
            scanf("%u",&t);
            char str[40];
            convers(str,t);
            printf("%u\n",tree.solve(str,t));
        }
    }
    return 0;
}
View Code

 

Labyrinth

动态规划。

dp[0][i][j]表示向下方向移动可得最大金币数，dp[1][i][j]表示向上方向移动可得最大金币数。

这样

dp[0][i][j]=max(dp[0][i-1][j],max(dp[0][i][j-1],dp[1][i][j-1]))+money[i][j]

dp[1][i][j]=max(dp[1][i+1][j],max(dp[0][i][j-1],dp[1][i][j-1]))+money[i][j]

最后答案max(dp[1][1][m],dp[0][1][m])。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
int dp[2][105][105];
int val[105][105];
int main()
{
    int T,kase=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                scanf("%d",&val[i][j]);
        memset(dp,0x80,sizeof(dp));
        dp[0][0][1]=0;
        for(int j=1; j<=m; ++j)
        {
            for(int i=1; i<=n; ++i)
                dp[0][i][j]=max(dp[1][i][j-1],max(dp[0][i-1][j],dp[0][i][j-1]))+val[i][j];
            for(int i=n; i>=1; --i)
                dp[1][i][j]=max(dp[0][i][j-1],max(dp[1][i+1][j],dp[1][i][j-1]))+val[i][j];
        }
        printf("Case #%d:\n%d\n",++kase,max(dp[0][1][m],dp[1][1][m]));
    }
    return 0;
}
View Code

 

 


联系
我们