THU2017spring 1-2 Company
描述
公司有n个员工，编号1 ~ n。员工数量众多，需要你为他们编写一个管理系统。
员工上班时都要登录管理系统登记一个code，离开要从管理系统上注销，员工也可以随时更新自己的code。到了下班时间，所有员工都会自动注销。公司管理人员随时都可能想要知道有多少员工上班，以及任一员工登记的code。
输入
第一行两个整数n、m。接下来m行，每行都是以下内容之一：
I a c //Log In：员工a登录，code为c。若a已登录，则将code更新为c
O a //Log Out：编号为a的员工注销。若a未登录，则注销无效
C //Close：到下班时间，所有员工注销
N //Number：询问有多少员工正在上班
Q a //Query：询问员工a的code（若未登录或已注销，视为-1）
输出
一个整数，是所有询问（N、Q）的答案之和（int表示，自动溢出，不用管溢出部分）
输入样例
10 8
I 1 2
I 1 4
Q 1
C
I 2 4
O 2
Q 2
N
输出样例
3
//“Q 1”答案是4，“Q 2”答案是-1，“N”答案是0，所有答案之和为3
限制
n <= 10,000,000
m <= 1,000,000
1<=a<=n
code为[0, 2^31)的整数
空间限制：256 MB
时间限制：2 sec
提示
一级提示
测试数据中，每种操作都可能频繁出现，或很少出现。因此，你的算法需要应对所有可能的情况。
● Bitmap / 常数时间初始化的数组
● Bitmap: 习题解析[2-34]，实例参考[2-35]，[2-36]
二级提示
● 避免频繁初始化整个数组。
● 可以借助Bitmap记录数组的各元素是否已被初始化。将一个（或所有）元素置为未初始化状态，实质上只需要打破“校验环”两个验证条件中的任何一个，考虑如何打破校验条件的复杂度最低。
● 还可以使用“懒删除”策略。
● 参考习题[2-34]。
用scanf(“%c”, …)或getchar()读入一个字符时，可能会读到空格、制表符、回车符或换行符，尽量避免使用这个方法。使用scanf(“%s”, …)会自动过滤空白字符。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include<iostream> #include<cstdio> #include<cstring> using namespace std; int main(){ setvbuf(stdin,new char[1<<24],_IOFBF,1<<24); setvbuf(stdout,new char[1<<24],_IOFBF,1<<24); int n,m; scanf("%d %d",&n,&m); int * staffs=new int[n+1]; int * version_arr=new int[n+1]; //使用版本号 memset(staffs,-1,sizeof(int)*(n+1)); memset(version_arr,-1,sizeof(int)*(n+1)); int sum=0; int staff_num=0,version=0; while(m--){ char c; do{ scanf("%c",&c); }while(c>'Z'||c<'A'); switch(c){ //登录 case 'I': int a,c; scanf("%d %d",&a,&c); if(version_arr[a]<version||staffs[a]==-1&&version_arr[a]==version)staff_num++; //版本号在过去或者当前版本号并且未登录 staffs[a]=c; version_arr[a]=version; //更新版本号 break; case 'O': //注销 int b; scanf("%d",&b); if(version_arr[b]==version&&staffs[b]!=-1)staff_num--; //原来版本号的不需要去减，当前版本号登陆过的才需要去减，在twd2的提醒下才加上staffs[b]!=-1 staffs[b]=-1; break; case 'C': version++; staff_num=0; break; case 'N': sum+=staff_num; break; case 'Q': int d; scanf("%d",&d); if(version_arr[d]<version||staffs[a]==-1&&version_arr[a]==version)sum-=1;//原来版本号，当前版本号未登录都是-1 else sum+=staffs[d]; break; } } printf("%d",sum); } |