比赛来源：第十四届重庆大学程序设计大赛暨西南地区高校邀请赛现场初赛
比赛地址：http://qscoj.cn/contest/24/
A. Comb 自述
分析：统计ACM在题目描述中出现的次数，认真数一遍就好了，答案就是比赛标题中的14.
官方标程：
#include <cstdio>
int main() {
puts("");
return ;
}
我的AC代码：
#include<stdio.h>
int main()
{
printf("14\n");
return ;
}
B. Comb 数学
分析：超级水题，我们知道5的任何正数次方都是5，唯一的坑就是5的0次方是1，只要加一个判断就行。
官方标程：
#include <cstdio>
int main() {
int t; scanf("%d", &t);
while(t--) {
int x; scanf("%d", &x);
printf("%d\n", x ? : );
}
return ;
}
我的AC代码：
#include<stdio.h>
int main()
{
int T,x;
scanf("%d",&T);
while(T--)
{
scanf("%d",&x);
if (x) printf("5\n");
else printf("1\n");
}
return ;
}
C. Comb 找零
分析：题目里说Comb里的每个钱袋子都是2的x次幂，所以要正好凑成n数量的钱，就得将n转化为二进制统计其中1的数量，就是最少的钱袋数。当然，一个装2的x次幂的钱袋也可以拆成2个装2的x-1次幂的钱袋，但那样的话会让钱袋的数量更多。所以统计n转化成二进制其中1的数量就是最佳答案。注意n的数据范围为10^19，就比long long大了一点，我想用double发现精度会有问题，然后写了个高精度过了这个题，看了官方标程才想起还有unsigned long long这种东西。官方标程中的__builtin_popcountll(x)这个函数就是返回x转化成二进制后其中1的个数。
官方标程：
#include <cstdio>
int main() {
int t; scanf("%d", &t);
while(t--) {
unsigned long long x; scanf("%llu", &x);
printf("%d\n", __builtin_popcountll(x));
}
return ;
}
我的AC代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T,i,cnt,len;
int a[];
long long n,j;
string s,s0;
cin>>T;
s0="";
while(T--)
{
cin>>s;len=s.length();cnt=;
memset(a,,sizeof(a));
for(i=;i<len;i++)
a[len--i]=s[i]-;
if (len== || (len== && s>=s0))
{
cnt++;
for(i=;i<=;i++)
a[i]-=s0[-i]-;
for(i=;i<=;i++)
{
if (a[i]<) {a[i]+=;a[i+]--;}
}
}
j=1e18;n=;
for(i=;i>=;i--)
{
n+=j*a[i];
j/=;
}
for(i=;i>=;i--)
{
j=(1ll<<i);
cnt+=n/j;n%=j;
}
printf("%d\n",cnt);
}
return ;
}
D. Comb 寻路
分析：棋盘的大小不大，只有100*100，所以可以采用BFS的方法，用dp[i][j]记录点从起点到点(i,j)的最短时间，一开始将怪物及怪物周边的空地标为-1；将其他点标为inf,将起点标为0,从起点开始BFS.注意从空地到空地需要花费时间1，从空地到墙或从墙到空地需要花费时间2，从墙到墙需要花费时间3.搜索完毕后判断终点的dp[i][j]值，如果为-1或inf则输出“Oh, Comb can't go out”，否则就输出该答案。
官方标程：
//
// Created by TaoSama on 2017-05-01
// Copyright (c) 2017 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h> using namespace std;
#define pr(x) cerr << #x << " = " << x << " "
#define prln(x) cerr << #x << " = " << x << endl
const int N = 1e2 + , INF = 0x3f3f3f3f, MOD = 1e9 + ; int n, m;
char s[N][N];
int f[N][N], in[N][N]; int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(); int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i) scanf("%s", s[i] + ); int sx, sy, tx, ty;
static const int d[][] = { -, , , -, , , , };
auto inBound = [&](int x, int y) {
return x >= && x <= n && y >= && y <= m;
};
for(int i = ; i <= n; ++i) {
for(int j = ; j <= m; ++j) {
if(s[i][j] == 'C') sx = i, sy = j;
else if(s[i][j] == 'E') tx = i, ty = j;
else if(s[i][j] == 'M') {
for(int k = ; k < ; ++k) {
int x = i + d[k][], y = j + d[k][];
if(inBound(x, y) && s[x][y] == '*') s[x][y] = 'X';
}
}
}
} bool can = true;
for(int k = ; k < ; ++k) {
int x = sx + d[k][], y = sy + d[k][];
if(inBound(x, y) && s[x][y] == 'M') can = false;
}
for(int k = ; k < ; ++k) {
int x = tx + d[k][], y = ty + d[k][];
if(inBound(x, y) && s[x][y] == 'M') can = false;
}
if(!can) {puts("Oh, Comb can't go out"); continue;} queue<pair<int, int>> q; q.push({sx, sy});
memset(f, 0x3f, sizeof f);
memset(in, false, sizeof in);
f[sx][sy] = ; in[sx][sy] = true;
while(q.size()) {
int x, y; tie(x, y) = q.front(); q.pop();
in[x][y] = false;
for(int k = ; k < ; ++k) {
int nx = x + d[k][], ny = y + d[k][];
if(!inBound(nx, ny) || s[nx][ny] == 'X') continue;
int c = s[nx][ny] == '#' ? : ;
if(f[nx][ny] > f[x][y] + c) {
f[nx][ny] = f[x][y] + c;
if(!in[nx][ny]) in[nx][ny] = true, q.push({nx, ny});
}
}
}
if(f[tx][ty] == INF) puts("Oh, Comb can't go out");
else printf("%d\n", f[tx][ty]);
} return ;
}
我的AC代码：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
vector< pair<int,int> > v[];
int fx[]={-,,,};
int fy[]={,,-,};
int main()
{
int T,n,m,xc,yc,xe,ye,i,j,k,s;
int x,y,xx,yy,cnt;
int dp[][];
char c[][];
cin>>T;
while(T--)
{
cin>>n>>m;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
dp[i][j]=inf;
for(i=;i<=;i++)
v[i].clear();
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
cin>>c[i][j];
if (c[i][j]=='C') {xc=i;yc=j;}
if (c[i][j]=='E') {xe=i;ye=j;}
}
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
if (c[i][j]=='M')
{
dp[i][j]=-;
for(k=;k<;k++)
{
xx=i+fx[k];
yy=j+fy[k];
if (xx< || xx>n || yy< || yy>m) continue;
if (c[xx][yy]=='#') continue;
dp[xx][yy]=-;
}
}
}
if (dp[xc][yc]==- || dp[xe][ye]==-)
{
printf("Oh, Comb can't go out\n");
continue;
}
v[].push_back(make_pair(xc,yc));dp[xc][yc]=;cnt=;
while()
{
for(i=;i<v[cnt].size();i++)
{
s=;x=v[cnt][i].first;y=v[cnt][i].second;
if (dp[x][y]<cnt) continue;
if (c[x][y]=='#') s++;
for(j=;j<;j++)
{
xx=x+fx[j];yy=y+fy[j];
if (xx< || xx>n || yy< || yy>m) continue;
if (dp[xx][yy]==-) continue;
if (c[xx][yy]=='#') s++;
if (dp[xx][yy]>cnt+s)
{
dp[xx][yy]=cnt+s;
v[cnt+s].push_back(make_pair(xx,yy));
}
if (c[xx][yy]=='#') s--;
}
}
if (cnt>= && !v[cnt].size() && !v[cnt-].size() && !v[cnt-].size()) break;
cnt++;
}
if (dp[i][j]==-) printf("Oh, Comb can't go out\n");
else printf("%d\n",dp[xe][ye]);
}
return ;
}