解题摘要-白红宇

解题摘要

阅读量：5022 次

发布时间：2019-06-12

本文共 10453 字，大约阅读时间需要 34 分钟。

HDU 1254 推箱子

题意：图中有一个箱子，和目标点，问最少推多少步可以把箱子推到目的地。

分析：广搜+深搜，对箱子的移动进行广搜处理，广搜的过程中用深搜判断人能否到达推箱子的位置。

HDU 1254

#include 
      
       #include 
       
        #define clr(x)memset(x,0,sizeof(x))int f[8] = {-1,1,0,0, 0,0,-1,1};struct node{    int step;    int x, y;    int tx, ty;}q[8000],tt,end,in,re;int v[8][8][8][8];int vis[8][8];int g[8][8];int n, m;bool ok(int x,int y){    if (x>=0 && x
        
         =0 && y

HDU 1428 漫步校园

题意：已知一个数字矩阵，例如

1 2 3

从左上角移动到右下角，有多少种路线，路线要求是：每走一步要距离终点更近。

分析：先用广搜预处理出每个点到终点的最短距离，然后进行记忆化搜索，r[x][y] 表示距离终点符合要求的路线数。

HDU 1428

#include 
      
       #include 
       
        #define INF 999999999#define clr(x)memset(x,0,sizeof(x))#define N 55int g[N][N];__int64 r[N][N];int d[N][N];int v[N][N];struct node{    int x, y;}q[10000],tt, in;int f[8] = {-1,1,0,0, 0,0,-1,1};int n;bool ok(int x,int y){    if (x>=0 && x
        
         =0 && y

HDU 1270 小希的数表

题意：Gardon昨天给小希布置了一道作业，即根据一张由不超过5000的N(3<=N<=100)个正整数组成的数表两两相加得到N*(N-1)/2个和，然后再将它们排序。例如，如果数表里含有四个数1，3，4，9，那么正确答案是4，5，7，10，12，13。小希做完作业以后出去玩了一阵，可是下午回家时发现原来的那张数表不见了，好在她做出的答案还在，你能帮助她根据她的答案计算出原来的数表么？

分析：先把前四个数确定了，然后维护一个堆即可。

优先队列实现

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int b[105];int a[5005];int top;struct node{    int x;    const bool operator <(const struct node&a)const    {        return x>a.x;    }}tt;int l,n;bool ok(){    priority_queue
          
           que;    tt.x = b[2]+b[4];    que.push(tt);    tt.x = b[3]+b[4];    que.push(tt);        int i;      int m = 4;     for (i=1; i<=4; i++)     {        tt.x = a[i];        que.push(tt);     }    int tot = 1;    while (tot < l)    {        if (!que.empty() &&  que.top().x==a[tot])        {                tot++;                que.pop();        }        else        {            b[++m] = a[tot]-b[1];            for (i=1; i
           
            n) return false; } } return true;}int main(){ int i, j, m; int flag; while (scanf("%d",&n),n) { l=n*(n-1)/2; for (i=1; i<=l; i++) { scanf("%d",&a[i]); } if (n==3) { b[1] = a[1]+a[2]-a[3]; b[1] = b[1]/2; b[2] = a[1]-b[1]; b[3] = a[2]-b[1]; b[4] = a[4]-b[1]; for (i=1; i<=n; i++) printf("%d%c",b[i],i==n?'\n':' '); continue; } flag = 0; b[1] = a[1]+a[2]-a[3]; if (b[1]%2==0) { b[1] = b[1]/2; b[2] = a[1]-b[1]; b[3] = a[2]-b[1]; b[4] = a[4]-b[1]; if (b[1]<=b[2] && b[2]<=b[3] && b[3]<=b[4]) { if (ok()) for (i=1; i<=n; i++) printf("%d%c",b[i],i==n?'\n':' '); } } if ((a[1]+a[2]-a[4])%2==0) { b[1] = (a[1]+a[2]-a[4])/2; b[2] = a[1]-b[1]; b[3] = a[2]-b[1]; b[4] = a[3]-b[1]; if (ok()) for (i=1; i<=n; i++) printf("%d%c",b[i],i==n?'\n':' '); } } return 0;}

HDU 1247 Hat’s Words

题意：给出一个字典，问字典里面哪些单词是由其他两个单词组成的。

分析：拆分每个字符串，分别在字典中找即可。

字典树

#include 
      
       #include 
       
        struct node{    int count;    node *next[26];}tt[2500000];int tot;char ss[50000][50];void add(char *s,node *root){    node *p = root;    int i=0;    while (s[i])    {        int x = s[i]-'a';        if (p->next[x] == NULL)        {            p->next[x] = &tt[++tot];            memset(tt[tot].next,NULL,sizeof(tt[tot].next));            tt[tot].count = -1;        }        p = p->next[x];        i++;    }    p->count = 1;}bool find(char *a,node *root){    int x, i =0;    node *p = root;    while (a[i])    {        x = a[i]-'a';        if (p->next[x]==NULL)            return false;        p = p->next[x];        i++;    }    if (p->count==1)        return true;    return false;}int main(){    int n=0;    int i, j;    tot = 0;    node *root = &tt[0];    memset(tt[0].next,NULL,sizeof(tt[0].next));    tt[0].count = -1;    while (scanf("%s",ss[n])!=EOF)    {        add(ss[n],root);        n++;    }    for (i=0; i

HDU 1263 水果

题意：给水果排序，先按产地再按名称排，并且同种水果累加。

分析：模拟水题。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;struct node{    int  num;    char c[88];    char name[88];}q[10000]; bool cmp(node a,node b) {     if (strcmp(a.c,b.c)!=0)        return strcmp(a.c,b.c)<0;    return strcmp(a.name,b.name)<0; }int main(){    char s1[88];    char s2[88];    int p, m;    int t;    int i;    scanf("%d",&t);    while (t--)    {        scanf("%d",&m);        for (i=0; i

HLG 1618 词频统计

题意：统计一篇文章中每个词出现的次数，每个词仅包含大写和小写字母，每个词的长度至少为1，最长有可能整篇文章只有一个词。

分析：

①线性再探测+BKDR字符串哈希

BKDR_HASH

#include 
      
       #include 
       
        #include 
        
         const int maxn = 180000;//const int maxn = 21*1024*1024;//char s[maxn];//char *int BKDRHash(char *str){    int hash = 0;    while (*str)    {        hash = hash*31 + (*str++);    }    return (hash & 0x7FFFFFFF);}struct node{    int count;    char *s;}h[maxn];int num[maxn]={
    0};int tot = 0;void hashinsert(char *str){    int val = BKDRHash(str)%maxn;    while (h[val].count != 0)    {        if (strcmp(h[val].s,str)==0)        {            h[val].count++;            break;        }        val = (val+1)%maxn;    }    if (h[val].count == 0)    {        int len = strlen(str);        h[val].s = (char*)malloc(sizeof(char)*(len+1));  //多组数据时要注意释放缓存        strcpy(h[val].s,str);        h[val].count++;        num[++tot] = val;    }}char ss[3000000];int main(){    memset(h,0,sizeof(h));    while (scanf("%s",ss)!=EOF)    {        hashinsert(ss);    }    int i;    for (i=1; i<=tot; i++)        printf("%d\n",h[num[i]].count);    return 0;}

②链式+BKDR字符串哈希

链式

#include 
      
       #include 
       
        #include 
        
         const int maxn = 120000;const int maxc = 40000;//const int maxn = 21*1024*1024;//char s[maxn];//char *int BKDRHash(char *str){    int hash = 0;    while (*str)    {        hash = hash*31 + (*str++);    }    return (hash & 0x7FFFFFFF);}struct node{    int count;    char *s;    node *next;};node h[maxn+maxc]={
    0};int tt = maxn;int num[maxn];int tot = 0;void hashinsert(char *str){    //int val = str[0]%3;    //printf("%d\n",val);    int val = BKDRHash(str)%maxn;    if (h[val].count == 0)    {        int len = strlen(str);        h[val].s = (char*)malloc(sizeof(char)*(len+1));        strcpy(h[val].s,str);        h[val].count++;        num[++tot] = val;        return;    }    if (strcmp(str,h[val].s)==0)    {        h[val].count++;        return;    }    node *p = &h[val];    while (p->next != NULL)    {        if (strcmp(p->next->s,str)==0)        {            p->next->count++;            return;        }        p = p->next;    }    if (p->next == NULL)    {        p->next = &h[++tt];        int len = strlen(str);        p->next->s = (char*)malloc(sizeof(char)*(len+1));        strcpy(p->next->s,str);        p->next->count++;        num[++tot] = tt;    }}char ss[4000000];int main(){   //memset(h,0,sizeof(h));    while (scanf("%s",ss)!=EOF)    {        hashinsert(ss);    }    int i;    for (i=1; i<=tot; i++)        printf("%d\n",h[num[i]].count);    return 0;}

HLG 1441 Parking Ships

题意：有N个海盗，其中有一个是船长，他们都住在一个海岸线上，知道了每个海盗的房子的中心位置为x，每个海盗的船的长度是l,如果可以将他的船放在位置[a,a+l],并且满足

a<=x<=a+l这个海盗就会高兴，首先船长会把自己的船的中心位置和自己房子的中心位置对其，船长应该如何安排船只的泊位，可以使得尽可能多的海盗高兴呢？

分析：可以采用贪心的方法，把海盗分成在船长左边和右边两个部分，若右边的的某个海盗的船要摆放的话，应该尽可能的让他的船向左放置，即满足max(lastship+p[i].len,p[i].x)

可以将所有的长度变成2倍，这样就能避免船长的船只取一半的时候不用处理浮点数。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const long long INF = 10000000000;struct node{    long long  x;    long long len;}q[2][1001],c,tt;int num[2];bool cmp(const node a, const node b){    return a.x < b.x;}int main(){    int t;    int n;    scanf("%d",&t);    while (t--)    {        scanf("%d",&n);        scanf("%lld %lld",&c.x,&c.len);        num[0] = num[1] = 0;        for (int i=0; i
          
           = c.x)            {                tt.x = fabs(tt.x-c.x)*2;                if (tt.x >= c.len)                    q[1][num[1]++] = tt;            }            else if (tt.x <= c.x)            {                tt.x = fabs(tt.x-c.x)*2;                if (tt.x >= c.len)                    q[0][num[0]++] = tt;            }        }        sort(q[0],q[0]+num[0],cmp);        sort(q[1],q[1]+num[1],cmp);        int tot = 1;        for (int j=0; j<2; j++)        {            long long ls = c.len;            for (int i=0;i

HDU 1436 排列组合（二）

题意：有N个字母，每个字母的数量不定。用这N个字母组成一个长为M的串，并且规定这个串中每个字母能出现的次数。求这样的串的总数。

分析：之前处理好组合数c[][]，然后d[i]表示字符串长度为i的时候用所给字符串构成的满足条件的情况数，

递推式： d[s[i][k]+j] += d[j]*c[m-j][s[i][k]];

View Code

#include 
      
       #include 
       
        #include 
        
         using namespace std;#define clr(x)memset(x,0,sizeof(x))const int maxn = 1001;__int64 c[maxn][maxn],d[maxn],s[maxn][maxn];void cc(__int64 m){    int i,j;    for (i=1; i<=m; i++)    {        c[i][0] = 1;        for (j=1; j
         
           m)                continue;            d[s[0][i]] = c[m][s[0][i]];        }        for (i=1; i
          
           =0 ; j--)            {                if (d[j])                    for (k=1; k<=s[i][0] && j+s[i][k]<=m; k++)                    {                        if (s[i][k] > 0)                            d[s[i][k]+j] += d[j]*c[m-j][s[i][k]];                    }            }        }        printf("%I64d\n",d[m]);    }    return 0;}

HDU 4145 Cover The Enemy

题意：已知有两个防御塔，有N个敌人，知道了每个敌人的坐标和防御塔的坐标，现在要在两个防御塔上造大炮，要求能覆盖所有的敌人，并且造价之和为R1*R1+R2*R2

　　如何设置两个炮的覆盖半径能使得造价最小。，

分析：对所有炮塔先按照和第1个防御塔的距离从小到大排序，然后一次枚举每个距离，第2个防御塔的半径就是第一个防御塔不能覆盖到的最远距离。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const double eps = 1e-8;struct node{    int d1,d2;    int x,y;}t1,t2,q[100005];double dis(node a,node b){    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}int cmp(node a,node b){    return a.d2 > b.d2;}int main(){    int t;    int n;    int i;    int maxdis;    int res,tmp;    scanf("%d",&t);    while (t--)    {        scanf("%d %d %d %d",&t1.x,&t1.y,&t2.x,&t2.y);        scanf("%d",&n);        for (i=0; i
          
            maxdis)                maxdis = q[i-1].d1;            tmp = q[i].d2+maxdis;            if (tmp < res)                res = tmp;        }        if (q[n-1].d1 > maxdis)            maxdis = q[n-1].d1;        if (maxdis < res)            res = maxdis;        printf("%d\n",res);    }    return 0;}