cf 569B. Inventory （模拟？）

给出一个图书馆人员进出情况，问图书馆满足题意的最小容量是多少。 注意在初始之前图书馆里面可能就有人了，也就是说不是所有进入图书馆的人都会被给出。 我的做法是先统计出图书馆里面初始的人数，开一个布尔数组，初始全为false，如果一个人标记为 false 而且从 图书馆里出来了，就说明这个人初始是在图书馆里的。

简单模拟，n,m貌似给反了(两个地方给的不一致 ) 害我wa了两发 代码实现 1 2 /************************************************************************* 3 > File Name: code/2015summer/#5/K.cpp 4 > Author: 111qqz 5 > Email: rkz2013@126.com 6 > Created Time: 2015年07月30日 星期四 14时00分56秒 7 ************************************************************************/ 8 9 #include<iostream> 10 #include<iomanip> 11 #include<cstdio> 12 #include<algorithm> 13 #include<cmath> 14 #include<cstring> 15 #include<string> 16 #include<map> 17 #include<set> 18 #include<queue> 19 #include<vector> 20 #include<stack> 21 #define y0 abc111qqz 22 #define y1 hust111qqz 23 #define yn hez111qqz 24 #define j1 cute111qqz 25 #define tm crazy111qqz 26 #define lr dying111qqz 27 using namespace std; 28 #define REP(i, n) for (int i=0;i<int(n);++i) 29 typedef long long LL; 30 typedef unsigned long long ULL; 31 const int inf = 0x7fffffff; 32 const int N=1e2+5; 33 int b[N][N]; 34 int n,m; 35 char cmd[505]; 36 bool vis[N][N]; 37 int nx,ny; 38 int dx[4]={-1,0,1,0}; 39 int dy[4]={0,1,-0,-1}; 40 char ch[N][N]; 41 int main() 42 { 43 cin>>n>>m; 44 nx = 0; 45 ny = 0; 46 for ( int i = 0 ; i < n ; i++) 47 cin>>ch[i]; 48 for ( int i = 0 ; i <n ; i++ ) 49 { 50 for ( int j = 0 ; j < m ; j++ ) 51 { 52 b[i+1][j+1]=(int)(ch[i][j]-'0'); 53 } 54 } 55 int ans = 0; 56 memset(vis,false,sizeof(vis)); 57 int dir = 1; 58 cin>>cmd; 59 int len = strlen(cmd); 60 for ( int i = 0 ; i < len ; i ++ ) 61 { 62 // cout<<"ans:"<<ans<<endl; 63 // cout<<"nx:"<<nx<<" ny:"<<ny<<endl; 64 if (cmd[i]=='L') 65 { 66 dir = (dir+3)%4; 67 } 68 if (cmd[i]=='R') 69 { 70 dir = (dir+1)%4; 71 } 72 if (cmd[i]=='M') 73 { 74 if (dir==0) 75 { 76 if (vis[nx][ny]) 77 { 78 ans = ans + b[nx][ny]/2; 79 } 80 else 81 { 82 ans = ans + b[nx][ny]; 83 } 84 if (vis[nx][ny+1]) 85 { 86 ans = ans + b[nx][ny+1]/2; 87 } 88 else 89 { 90 ans = ans + b[nx][ny+1]; 91 } 92 vis[nx][ny]=true; 93 vis[nx][ny+1]=true; 94 nx = nx +dx[dir]; 95 ny = ny +dy[dir]; 96 } 97 if (dir==2) 98 { 99 nx = nx + dx[dir]; 100 ny = ny + dy[dir]; 101 if (vis[nx][ny]) 102 { 103 ans = ans + b[nx][ny]/2; 104 } 105 else 106 { 107 ans = ans + b[nx][ny]; 108 } 109 if (vis[nx][ny+1]) 110 { 111 ans = ans + b[nx][ny+1]/2; 112 } 113 else 114 { 115 ans = ans + b[nx][ny+1]; 116 } 117 vis[nx][ny]=true; 118 vis[nx][ny+1]=true; 119 } 120 if (dir==1) 121 { 122 nx = nx + dx[dir]; 123 ny = ny + dy[dir]; 124 if (vis[nx][ny]) 125 { 126 ans = ans + b[nx][ny]/2; 127 } 128 else 129 { 130 ans = ans + b[nx][ny]; 131 } 132 if (vis[nx+1][ny]) 133 { 134 ans = ans + b[nx+1][ny]/2; 135 } 136 else 137 { 138 ans = ans + b[nx+1][ny]; 139 } 140 vis[nx][ny]=true; 141 vis[nx+1][ny]=true; 142 143 } 144 if (dir==3) 145 { 146 147 if (vis[nx][ny]) 148 { 149 ans = ans + b[nx][ny]/2; 150 } 151 else 152 { 153 ans = ans + b[nx][ny]; 154 } 155 if (vis[nx+1][ny]) 156 { 157 ans = ans + b[nx+1][ny]/2; 158 } 159 else 160 { 161 ans = ans + b[nx+1][ny]; 162 } 163 vis[nx][ny]=true; 164 vis[nx+1][ny]=true; 165 nx = nx +dx[dir]; 166 ny = ny +dy[dir]; 167 } 168 } 169 170 } 171 cout<<ans<<endl; 172 173 return 0; 174 }

一开始算法想的有点问题。 坑点在于走廊两侧都有房间 也就是说room1和room2对应的位置是一样的 1 to 3 4to6 是没法同时完成的。 做法就是整个扫一遍，看哪个位置的重复次数最大，*10就是答案。

题意是说用 k 种颜色填充 nm 的方格，第 i 种颜色要用 c[i] 次，保证 c[i]（i 属于 1..k）的和为 nm，问是否有可行解，若有，输出任意一种。 第一感觉是 dfs，而且数据范围还那么小。但是鉴于我上次 dfs 写成汪的经历……嗯，不过群里有学长说似乎剪枝不太好想？ 我一开始分了四类：o 行 o 列、e 行 e 列、e 行 o 列、o 行 e 列（o 是 odd，e 是 even），然后将 c[i] 排序，先填大的 c[i]，感觉这样应该更容易找到解。交了一发，WA 掉了。发现当 k 较小的时候，也就是 c[i] 都相对较大的时候，先填大的 c[i] 的策略会出现错误。于是我换了下，按 c[i] 的大小从两边往中间填。然后我还发现其实 o 行 o 列和 e 行 e 列可以归为一类，同理，后两种也可以归为一类。又交，又 WA 2333333。然后想了好久，发现对于上面说的两类的处理顺序不同会得到不同的结果，只有一种是对的。于是加了个 judge 函数判断冲突，如果冲突就换个顺序。再交，A 了。