首页 > ACM题库 > HDU-杭电 > hdu 2723 Electronic Document Security[解题报告]C++
2014
02-14

hdu 2723 Electronic Document Security[解题报告]C++

Electronic Document Security

问题描述 :

The Tyrell corporation uses a state-of-the-art electronic document system that controls all aspects of document creation, viewing, editing, and distribution. Document security is handled via access control lists (ACLs). An ACL defines a set of entities that have access to the document, and for each entity defines the set of rights that it has. Entities are denoted by uppercase letters; an entity might be a single individual or an entire division. Rights are denoted by lowercase letters; examples of rights are a for append, d for delete, e for edit, and r for read.

The ACL for a document is stored along with that document, but there is also a separate ACL log stored on a separate log server. All documents start with an empty ACL, which grants no rights to anyone. Every time the ACL for a document is changed, a new entry is written to the log. An entry is of the form ExR, where E is a nonempty set of entities, R is a nonempty set of rights, and x is either "+", "�", or "=". Entry E+R says to grant all the rights in R to all the entities in E, entry E�R says to remove all the rights in R from all the entities in E, and entry E=R says that all the entities in E have exactly the rights in R and no others. An entry might be redundant in the sense that it grants an entity a right it already has and/or denies an entity a right that it doesn’t have. A log is simply a list of entries separated by commas, ordered chronologically from oldest to most recent. Entries are cumulative, with newer entries taking precedence over older entries if there is a conflict.

Periodically the Tyrell corporation will run a security check by using the logs to compute the current ACL for each document and then comparing it with the ACL actually stored with the document. A mismatch indicates a security breach. Your job is to write a program that, given an ACL log, computes the current ACL.

输入:

The input consists of one or more ACL logs, each 3�79 characters long and on a line by itself, followed by a line containing only "#" that signals the end of the input. Logs will be in the format defined above and will not contain any whitespace.

输出:

The input consists of one or more ACL logs, each 3�79 characters long and on a line by itself, followed by a line containing only "#" that signals the end of the input. Logs will be in the format defined above and will not contain any whitespace.

样例输入:

MC-p,SC+c
YB=rde,B-dq,AYM+e
GQ+tju,GH-ju,AQ-z,Q=t,QG-t
JBL=fwa,H+wf,LD-fz,BJ-a,P=aw
#

样例输出:

1:CSc
2:AeBerMeYder
3:
4:BHJfwLPaw

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2723

题意:为了对一个文件进行访问控制,会给每个文件建立一个访问控制列表(ACL),每个列表里有若干个entity(类似于用户组),每个entity有若干个right(权限)。给出一个文件的权限更改日志,日志是ExR形式的短语构成,E是这次操作影响的entity(多个),R是right,x是一个操作符,可以为+、-、=。为+的时候表示把权限加到entity上,为-的时候表示从entity减去相应权限,为=的时候表示把entity设为相应权限。最后输出每个entity对应的权限,没有权限的不输出,2个相邻的entity如果有相同的权限,合并输出。

mark:这其实就是个阅读题。数据量很小,读懂了几乎就是实现的问题,因为只有26个字母所以用位运算写爽爆了。很2b地wa了2次,一次是sscanf没处理好,一次是数组开小了,而且第三次提交的时候虽然A了,但是看错行以为wa,瞪了1小时不知道错哪儿直到小朋友提醒才发现。。。

代码:

# include <stdio.h>
# include <string.h>


int ACL[30], out[30][2] ;
char str[100] ;
char entity[100], right[100] ;


void gao(char s[])
{
    char *p = s, op ;
    int ent, rit, i, j ;
    memset (ACL, 0, sizeof(ACL)) ;
    while (*p)
    {
        sscanf (p, "%[A-Z]%c%[a-z]%*c", entity, &op, right) ;
        p += strlen(entity) + strlen(right) + 2 ;
        for (i = 0 ; entity[i] ; i++)
        {
            ent = entity[i]-'A' ;
            for (rit = 0, j = 0 ; right[j] ; j++) rit |= (1<<(right[j]-'a')) ;
            
            if (op == '+') ACL[ent] |= rit ;
            else if (op == '-') ACL[ent] &= ~rit ;
            else //op == '='
                ACL[ent] = rit ;
        }
    }
}


int main ()
{
    int nCase = 1 ;
    int i, j, cnt ;
    while (~scanf ("%s", str) && strcmp(str, "#"))
    {
        gao(str) ;
        memset (str, 0, sizeof(str)) ;
        printf ("%d:", nCase++) ;
        for (i = 0, cnt = 0 ; i < 26 ; i++) if (ACL[i])
            out[cnt][0] = i, out[cnt++][1] = ACL[i] ;
        for (i = 0 ; i < cnt ; i++)
        {
            printf ("%c", out[i][0]+'A') ;
            if (i==cnt-1 || (i<cnt-1 && out[i][1] != out[i+1][1]))
                for (j = 0 ; j < 26 ; j++) if (out[i][1] & (1<<j))
                    printf ("%c", j+'a') ;
        }
        printf ("\n") ;
    }
    return 0 ;
}

 

解题转自:http://www.cnblogs.com/lzsz1212/archive/2013/09/13/3318691.html


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.