CSP-201612

2018-03-15

201612-3-权限查询

题目链接

http://118.190.20.162/view.page?gpid=T50

题目大意

题目太蛋疼。。。直接看吧。。。

思路

没有任何思路。。考虑好数据结构怎么设计以后就可以直接大模拟了。。
纯粹为了记录我这伟大的200+行代码。。

代码

CSP-201612-3

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct Category{
    char cate_name[33];
    int cate_level;
}category[101];
int cate_num;
struct Role{
    char role_name[33];
    int pri_num;
    int pri_index[11];
    int pri_level[11];
}role[101];
int role_num;
struct User{
    char user_name[33];
    int role_num;
    int role_index[11];
}user[101];
int user_num;

int find_cate(char *pri)
{
    for (int i=1;i<=cate_num;i++)
    {
        if (strcmp(pri,category[i].cate_name) == 0) return i;
    }
    return -1;
}

int find_role(char *roname)
{
    for (int i=1;i<=role_num;i++)
    {
        if (strcmp(roname,role[i].role_name) == 0) return i;
    }
    return -1;
}

int find_user(char *username)
{
    for (int i=1;i<=user_num;i++)
    {
        if (strcmp(username,user[i].user_name) == 0) return i;
    }
    return -1;
}
int main()
{
    scanf("%d",&cate_num);
    for (int i=1;i<=cate_num;i++)
    {
        char cate[50];
        scanf("%s",cate);
        int cate_len=strlen(cate);
        int p=0;
        while (p<cate_len)
        {
            if (cate[p] == ':') break;
            p++;
        }
        if (p == cate_len)
        {
            category[i].cate_level=-1;
            for (p=0;p<cate_len;p++) category[i].cate_name[p]=cate[p];
            category[i].cate_name[strlen(category[i].cate_name)]='\0';
        }
        else
        {
            int x=0;
            for (int pp=p+1;pp<cate_len;pp++) x=x*10+(cate[pp]-'0');
            category[i].cate_level=x;
            for (int pp=0;pp<p;pp++) category[i].cate_name[pp]=cate[pp];
            category[i].cate_name[strlen(category[i].cate_name)]='\0';
        }
    }
 /*   printf("---------------------------\n");
    for (int i=1;i<=cate_num;i++)
    {
        printf("%s:%d\n",category[i].cate_name,category[i].cate_level);

    }
    printf("---------------------------\n");*/
    scanf("%d",&role_num);
    for (int i=1;i<=role_num;i++)
    {
        char rolename[50];
        int pri_num;
        scanf("%s%d",rolename,&pri_num);

        int len=strlen(rolename);
        for (int p=0;p<len;p++) role[i].role_name[p]=rolename[p];
        role[i].role_name[len]='\0';

        role[i].pri_num=pri_num;

        for (int j=1;j<=pri_num;j++)
        {
            char pri[50];
            scanf("%s",pri);
            len=strlen(pri);
            int p=0;
            while (p<len)
            {
                if (pri[p] == ':') break;
                p++;
            }
            if (p == len)
            {
                role[i].pri_level[j]=-1;
                role[i].pri_index[j]=find_cate(pri);
            }
            else
            {
                int x=0;
                for (int pp=p+1;pp<len;pp++) x=x*10+(pri[pp]-'0');
                role[i].pri_level[j]=x;
                pri[p]='\0';
                role[i].pri_index[j]=find_cate(pri);
            }
        }
    }
/*    printf("---------------------------\n");
    for (int i=1;i<=role_num;i++)
    {
        printf("%s %d ",role[i].role_name,role[i].pri_num);
        for (int j=1;j<=role[i].pri_num;j++)
            printf("%d:%d ",role[i].pri_index[j],role[i].pri_level[j]);
        printf("\n");

    }
    printf("---------------------------\n");*/
    scanf("%d",&user_num);
    for (int i=1;i<=user_num;i++)
    {
        char username[50];
        int ro_num;
        scanf("%s%d",username,&ro_num);
        int len=strlen(username);
        for (int p=0;p<len;p++) user[i].user_name[p]=username[p];
        user[i].user_name[len]='\0';
        user[i].role_num=ro_num;
        for (int j=1;j<=ro_num;j++)
        {
            char roname[50];
            scanf("%s",roname);
            user[i].role_index[j]=find_role(roname);
        }
    }
 /*   printf("---------------------------\n");
    for (int i=1;i<=user_num;i++)
    {
        printf("%s %d ",user[i].user_name,user[i].role_num);
        for (int j=1;j<=user[i].role_num;j++)
            printf("%d ",user[i].role_index[j]);
        printf("\n");
    }
    printf("---------------------------\n");*/

    int Q;
    scanf("%d",&Q);
    while (Q--)
    {
        int flag=0;
        char username[55],pri[55];
        scanf("%s%s",username,pri);
        int pri_level=-1;
        int p=0,len=strlen(pri);
        while (p<len)
        {
            if (pri[p] == ':') break;
            p++;
        }
        if (p != len)
        {
            pri_level=0;
            for (int pp=p+1;pp<len;pp++) pri_level=pri_level*10+(pri[pp]-'0');
            pri[p]='\0';
        }
        int user_index=find_user(username);
        int cate_index=find_cate(pri);
        int cate_level=-1;
        for (int i=1;i<=user[user_index].role_num && flag!=1;i++)
        {
            for (int j=1;j<=role[user[user_index].role_index[i]].pri_num && flag!=1;j++)
            {
                if (role[user[user_index].role_index[i]].pri_index[j] == cate_index)
                {
                    if (category[cate_index].cate_level == -1) {flag=1; break;}
                    if (pri_level == -1)
                    {
                        flag=-1;
                        cate_level=max(cate_level,role[user[user_index].role_index[i]].pri_level[j]);
                        continue;
                    }
                    if (pri_level <= role[user[user_index].role_index[i]].pri_level[j]) {flag=1; break;}
                }
            }
        }
        if (flag == 1) printf("true\n");
        else
            if (flag == 0) printf("false\n");
        else
            if (flag == -1) printf("%d\n",cate_level);
    }
    return 0;
}

压缩编码

题目链接

http://118.190.20.162/view.page?gpid=T49

题目大意

求最短的满足字典序的编码比特数。

思路

收到题目的干扰。本以为是哈夫曼编码的变形，但是看了网上的题解以后，原来是一个DP。
因为需要保证字典序，所以ABCD……是不能颠倒顺序的。所以类似于石子合并，相邻的合并，求最小代价。其中的内在原因是这样的，首先保证字典序，然后在这个场景下，每合并一次就是相当于增加一层，所以代价是类计算的，所以和石子合并的移动一样。
dp[i][j]表示合并第i堆到第j堆的最小代价。
状态转移方程:dp[i][j]=min{dp[i][k],dp[k+1][j]}+sum[j]-sum[i-1]
sum[i]表示前i堆的总代价。
不得不说。。这个dp的代码不太好写。。。

代码

CSP-201612-4

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1005][1005];
int main()
{
    int pinshu[1005];
    int sum[1005];
    memset(sum,0,sizeof(sum));
    int N;
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
    {
        scanf("%d",&pinshu[i]);
        sum[i]=sum[i-1]+pinshu[i];
    }
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            if (i == j) dp[i][j]=0;
            else dp[i][j]=1<<20;
    for (int v=2;v<=N;v++)
    {
        for (int i=1;i<=N-v+1;i++)
        {
            int j=i+v-1;
            dp[i][j]=1<<30;
            for (int k=i;k<=j-1;k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            dp[i][j]+=sum[j]-sum[i-1];
        }
    }
    printf("%d\n",dp[1][N]);
    return 0;
}

后记

这几天没有每天都做算法练习。。作业有点多，近世代数有点凉。。
CSP加油~