【题目链接】点击打开链接 密码是: 960626
【写在前面】 例题，我就不写了，书上都有非常多的方法思路，下面我写的是第4章的习题，UVA220还未AC，以后有空再来补上。
【4-1 象棋】非常简单的题，单纯的模拟，代码量有点大，写成函数可以让自己的思路清晰起来。还要注意一些TRICK。我给出我的几个判断的代码就好。
struct node{
char s[3];
int x, y;
}a[10];
int g[20][20];
bool vis[20][20];
bool check1(int x, int y) //检查棋子在棋盘里面
{
if(x >= 1 && x <= 10 && y >= 1 && y <= 9) return 1;
else return 0;
}
bool check2(int x, int y)//检查帅的位置是否合法
{
if(x >= 1 && x <= 3 && y >= 4 && y <= 6) return 1;
else return 0;
}
void check_G(int x, int y)
{
for(int i = x - 1; i >= 1; i--){
if(g[i][y]){
vis[i][y] = 1;
break;
}
vis[i][y] = 1;
}
}
void check_R(int x, int y)
{
for(int i = y + 1; i <= 9; i++){
if(g[x][i]){
vis[x][i] = 1;
break;
}
vis[x][i] = 1;
}
for(int i = y - 1; i >= 1; i--){
if(g[x][i]){
vis[x][i] = 1;
break;
}
vis[x][i] = 1;
}
for(int i = x + 1; i <= 10; i++){
if(g[i][y]){
vis[i][y] = 1;
break;
}
vis[i][y] = 1;
}
for(int i = x - 1; i >= 1; i--){
if(g[i][y]){
vis[i][y] = 1;
break;
}
vis[i][y] = 1;
}
}
void check_H(int x, int y)
{
if(!g[x-1][y])
{
int tx = x - 2, ty = y - 1;
if(check1(tx, ty)) vis[tx][ty] = 1;
ty = y + 1;
if(check1(tx, ty)) vis[tx][ty] = 1;
}
if(!g[x+1][y])
{
int tx = x + 2, ty = y - 1;
if(check1(tx, ty)) vis[tx][ty] = 1;
ty = y + 1;
if(check1(tx, ty)) vis[tx][ty] = 1;
}
if(!g[x][y+1])
{
int tx = x + 1, ty = y + 2;
if(check1(tx, ty)) vis[tx][ty] = 1;
tx = x - 1;
if(check1(tx, ty)) vis[tx][ty] = 1;
}
if(!g[x][y-1])
{
int tx = x - 1, ty = y - 2;
if(check1(tx, ty)) vis[tx][ty] = 1;
tx = x + 1;
if(check1(tx, ty)) vis[tx][ty] = 1;
}
}
void check_C(int x, int y)
{
for(int i = x - 1; i >= 1; i--) //up
{
if(g[i][y]){
for(int j = i - 1; j >= 1; j--){
if(g[j][y])
{
vis[j][y] = 1;
break;
}
vis[j][y] = 1;
}
break;
}
}
for(int i = x + 1; i <= 10; i++) //down
{
if(g[i][y]){
for(int j = i + 1; j <= 10; j++){
if(g[j][y])
{
vis[j][y] = true;
break;
}
vis[j][y] = true;
}
break;
}
}
for(int i = y - 1; i >= 1; i--)//left
{
if(g[x][i]){
for(int j = i - 1; j >= 1; j--){
if(g[x][j]){
vis[x][j] = 1;
break;
}
vis[x][j] = 1;
}
break;
}
}
for(int i = y + 1; i <= 9; i++){
if(g[x][i]){
for(int j = i + 1; j <= 9; j++){
if(g[x][j]){
vis[x][j] = 1;
break;
}
vis[x][j] = 1;
}
break;
}
}
}
bool checkans(int x, int y)
{
int tx = x + 1, ty = y;
if(check2(tx, ty) && !vis[tx][ty]) return true;
tx = x - 1;
if(check2(tx, ty) && !vis[tx][ty]) return true;
tx = x; ty = y + 1;
if(check2(tx, ty) && !vis[tx][ty]) return true;
ty = y - 1;
if(check2(tx, ty) && !vis[tx][ty]) return true;
return false;
}【4-2 正方形】枚举，然后统计，自信1A。
int a[11][11], n, m;
int e[11][11][11][11];
int main()
{
int ks = 0;
while(scanf("%d%d", &n, &m) != EOF)
{
char op[3];
int x, y;
memset(e, 0, sizeof(e));
for(int i = 1; i <= m; i++){
scanf("%s%d%d",op,&x,&y);
if(op[0] == 'H'){
e[x][y][x][y+1] = 1;
e[x][y+1][x][y] = 1;
}
else{
e[y][x][y+1][x] = 1;
e[y+1][x][y][x] = 1;
}
}
if(ks++) printf("\n**********************************\n\n");
printf("Problem #%d\n\n", ks);
bool flag = 0;
for(int s = 1; s <= n; s++){
int ans = 0;
for(int i = 1; (i+s) <= n; i++){
for(int j = 1; (j+s) <= n; j++){
bool ok = 1;
for(int k = i + 1; k <= i + s; k++){
if(e[k-1][j][k][j] == 0){
ok = 0;
break;
}
}
for(int k = j + 1; k <= j + s; k++){
if(e[i][k-1][i][k] == 0){
ok = 0;
break;
}
}
for(int k = i + 1; k <= i + s; k++){
if(e[k-1][j+s][k][j+s] == 0){
ok = 0;
break;
}
}
for(int k = j + 1; k <= j + s; k++){
if(e[i+s][k-1][i+s][k] == 0){
ok = 0;
break;
}
}
if(ok) ans++;
}
}
if(ans){
flag = 1;
printf("%d square (s) of size %d\n",ans, s);
}
}
if(flag == 0)
{
printf("No completed squares can be found.\n");
}
}
return 0;
}【4-3 黑白棋】未AC，没怎么读懂题，留坑。
【4-4 骰子涂色】参加2016ICPC青岛站的选手，对这个问题应该非常有印象，这个和那个魔方都是同类问题，我们可以固定一个面，然后旋转相邻的四个面，那么两个模仿相同如何比较呢？注意到输入为字符串输入，所以我们直接strcmp这题就做完啦！
int dir[6][6] = { {0,1,2,3,4,5},{1,5,2,3,0,4},{2,1,5,0,4,3},{3,1,0,5,4,2},
{4,0,2,3,5,1},{5,4,2,3,1,0} };
char s[20], s1[20], s2[20];
bool f()
{
char t[6] = {0};
for(int i = 0; i < 6; i++){
for(int j = 0; j < 6; j++){
t[j] = s1[dir[i][j]];
}
for(int j = 0; j < 4; j++){
char xx;
xx = t[1];
t[1] = t[2];
t[2] = t[4];
t[4] = t[3];
t[3] = xx;
if(strcmp(t, s2) == 0)
{
return 1;
}
}
}
return 0;
}
int main()
{
while(scanf("%s", s)!=EOF)
{
for(int i = 0; i < 6; i++) s1[i] = s[i];
for(int i = 6; i < 12; i++) s2[i-6] = s[i];
if(f())
{
printf("TRUE\n");
}
else{
printf("FALSE\n");
}
}
return 0;
}【4-5 IP网络】那么这个题比较简单的办法就是我们先去算出子网掩码，不难发现最小网络就相当于子网掩码和任意一个网络地址想与之后的结果。那么子网掩码怎么算呢？
根据题意，我们找出每一个部分的最大值和最小值，然后看他们的二进制是最后几位不同，然后去子网掩码的表中查找答案就行啦。（首先要对子网掩码从低位到高位，依次替换成0之后，10进制是多少进行打表）
int zw[9] = {255, 254, 252, 248, 240, 224, 192, 128, 0};
int ip[4][1024];
int m;
int main()
{
while(scanf("%d", &m) != EOF)
{
memset(ip, 0, sizeof(ip));
int zwym[4], minip[4];
for(int i = 0; i < m; i++){
scanf("%d.%d.%d.%d", &ip[0][i], &ip[1][i], &ip[2][i], &ip[3][i]);
}
for(int i = 0; i < 4; i++){
int pos = 0;
int p, q;
sort(ip[i], ip[i] + m);
p = ip[i][0];
q = ip[i][m-1];
for(int j = 1; j <= 8; j++)
{
if(p%2 != q%2) pos = j;
p /= 2;
q /= 2;
}
zwym[i] = zw[pos];
minip[i] = ip[i][0] & zwym[i];
}
for(int i = 0; i < 4; i++){
if(zwym[i] != 255){
for(int j = i + 1; j < 4; j++){
zwym[j] = minip[j] = 0;
}
break;
}
}
printf("%d.%d.%d.%d\n", minip[0], minip[1], minip[2], minip[3]);
printf("%d.%d.%d.%d\n", zwym[0], zwym[1], zwym[2], zwym[3]);
}
return 0;
}【4-6 莫斯电码】这个题是真的恶心， 我自己尝试写了1份代码，愉快的炸了，我是用字符数组模拟的，很烦很复杂，然后在网上看到一位博主的代码非常好，很值得借鉴。就参考了他的思路，顺利AC了， 并且感受到了STL真强大。这题考察的就是如何映射字符串的关系和如何查找目标字符串，这里map当然是不二之选，然后细节也很多，方法选取不当很难AC，博客链接:点击打开链接
map <char, string> code1;
map <string, string> code2;
int dist(string a, string b)
{
if(a == b) return 0;
if(b.size() < a.size()) swap(a, b);
if(a != b.substr(0, a.size())) return inf;
else return b.size() - a.size();
}
string bianma(string &s)
{
string t;
for(int i = 0; i < s.size(); i++){
t += code1[s[i]];
}
return t;
}
string jiema(string s)
{
map<string, string>::iterator it = code2.begin();
string ans = it->first;
int dis = dist(it->second, s);
while(++it != code2.end()){
int dd = dist(it->second, s);
if(dd < dis)
{
ans = it->first;
dis= dd;
}
else if(dd == dis && dd == 0 && ans[ans.size()-1] != '!'){
ans = ans + "!";
}
}
if(dis) ans = ans + "?";
return ans;
}
int main()
{
string s1, s2;
while(cin>>s1, s1 != "*") cin>>s2, code1[s1[0]] = s2;
while(cin>>s1, s1 != "*") code2[s1] = bianma(s1);
while(cin>>s1&&s1 != "*") cout<<jiema(s1)<<endl;
return 0;
}【4-7 RAID技术】 这个题，可以说我见过最坑+难的题了，关键是题意，样例的输入是紫书的图的转置，这个地方坑了几个小时，后来看了别人说的才注意到。理解到题意之后，这就是纯模拟了，然后就是输出的时候可以用16进制来输出答案。
这题的做法主要分成两部，第一步是判断是否有解，这个比较简单，按照题意模拟即可：
bool f()
{
for(int i = 0; i < s*b; i++)
{
int sum = 0, cnt = 0, pos;
for(int j = 0; j < d; j++){
if(tab[j][i] == '1') ++sum;
if(tab[j][i] == 'x'){
cnt++, pos = j;
}
}
sum %= 2;
if(cnt >= 2) return false;
else if(cnt == 1){
if(sum){
if(cmd[0] == 'E') tab[pos][i] = '1';
else tab[pos][i] = '0';
}
else{
if(cmd[0] == 'E') tab[pos][i] = '0';
else tab[pos][i] = '1';
}
}
else if(cnt == 0){
if(cmd[0] == 'E' && sum == 1) return false;
if(cmd[0] == 'O' && sum == 0) return false;
}
}
return true;
}第二步，就是在已知这个表存在之后输出答案了，这个随便花点时间都可以搞出来的，关键点就是不能输出校验位，这个可以通过循环巧妙避免
void print()
{
int sum = 0, cnt = 0;
for(int i = 0; i < b; i++){
int pos = i % d;
for(int j = 0; j < d; j++){
if(j == pos) continue;
for(int k = i * s; k < i * s + s; k++){
cnt = (cnt + 1) % 4;
if(tab[j][k] == '0') sum *= 2;
else sum = sum * 2 + 1;
if(cnt == 0){
printf("%X", sum);
sum = 0;
}
}
}
}
if(cnt){
int over = 4 - cnt;
sum = sum * (1<<over);
printf("%X", sum);
}
printf("\n");
}特别提醒， 题上给的图是书上的转置。
【4-8 特别困的学生】 如果没看数据范围我们觉得这是个很困难得问题（我也不会），但是注意到n最大才10，A,B最大才5之后，我们猜这个时间并不会太长，我们可以枚举这个时间，然后暴力去模拟判断一下，我是模拟到了100000，果然可以过，感觉这个上限应该还可以小一点。
int a[12], b[12], c[12];
int main()
{
int ks = 0, n;
while(scanf("%d", &n) != EOF)
{
if(n == 0) break;
for(int i = 0; i < n; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]);
int clk, cnt;
for(clk = 1; clk < 100000; clk++){
cnt = 0; //清醒人数
for(int i = 0; i < n; i++){
if(c[i] <= a[i]){//c[i]代表周期内第c[i]分钟
cnt++;
}
}
if(cnt == n) break;
for(int i = 0; i < n; i++){
if(c[i] == a[i] + b[i] || (c[i] == a[i] && cnt >= n - cnt)){
c[i] = 0;
}
c[i]++;
}
}
if(clk == 100000) clk = -1;
printf("Case %d: %d\n", ++ks, clk);
}
return 0;
}【4-9 数据挖掘】这个题，套路好骚，题都读不懂，可以去看这个博客 点击打开链接 懂了题意之后，不妨学习一下博主对这题的思维认知，被套路深深折服，知道A,B的范围在32之内的时候，我们就可以直接暴力枚举了。
LL n, x, y, N, A, B, ansN, ansA, ansB;
int main()
{
while(cin>>n>>x>>y)
{
ansN = 0xfffffffffffffff;
for(A = 0; A < 32; A++){
for(B = 0; B < 32; B++){
N = ((n-1)*x + (((n-1)*x)<<A)>>B) + y; //仔细读题
if(N >= n*y && N < ansN){
ansA = A;
ansB = B;
ansN = N;
}
}
}
cout<<ansN<<" "<<ansA<<" "<<ansB<<endl;
}
return 0;
}【4-10 洪水】 淹没肯定是从高度最低的方格就开始的，所以先将n*m个方格从小到大排序。如果洪水要想淹没下一个方格，那么剩余洪水的体积必须>=已经淹没方格的面积*已经淹没方格的数量，这样水面才能整体拔高。如果满足不了这个条件，只能在原来的高度上均匀拔高了。
int a[1100];
int main()
{
int n, m, ks = 0;
while(scanf("%d%d",&n,&m) != EOF)
{
if(n == 0 && m == 0) break;
n *= m;
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
double V;
scanf("%lf", &V);
sort(a, a + n);
a[n] = 0x7fffffff;
int k;
double sum = V;
sum /= 100.0;
for(int i = 1; i <= n; i++){
sum += a[i-1];
if(sum / i <= a[i]){
k = i;
break;
}
}
printf("Region %d\n", ++ks);
printf("Water level is %.2lf meters.\n", sum / k);
printf("%.2lf percent of the region is under water.\n\n", k * 100.0 / n);
}
return 0;
}
京公网安备 11010502036488号