2013 ACM/ICPC Asia Regional Hangzhou Onsite

http://acmicpc.info/archives/1636

Problem A. Lights Against Dudely

Brief description:

There are at most fifteen vulnerable rooms in the bank.

Analysis:

```//}/* .................................................................................................................................. */

const int dx[] = {-1, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

const int NN = 15, N = 209;
char Map[N][N]; int id[N][N]; int dp[1<<NN];
int n, m, nn;

bool inGrid(int x, int y){
return x >= 0 && y >= 0 && x < n && y < m;
}

struct rec{
int x, y, s;
rec(int x = 0, int y = 0):x(x),y(y){
}
void init(int o = 0){
s = _1(id[x][y]);
REP(d, 2){
int xx = x + dx[o+d], yy = y + dy[o+d];
if (!inGrid(xx, yy)) continue;
if (Map[xx][yy] == '.') s |= _1(id[xx][yy]);
else{
s = 0;
return;
}
}
}
} A[NN];

int f(int id, int off){

REP(i, nn){
if (i == id) A[i].init(off);
else A[i].init();
}

FLC(dp, 0x3f); dp[0] = 0;
REP(s, _1(nn)){
REP(i, nn) if (!_1(s, i)){
int ss = s | A[i].s;
checkMin(dp[ss], dp[s] + 1);
}
}
return dp[_U(nn)];
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

while (RD(n, m)){
REP(i, n) RS(Map[i]);
nn = 0; REP_2(i, j, n, m) if (Map[i][j] == '.'){
id[i][j] = nn;
A[nn++] = rec(i, j);
}

if (!nn){
OT(0);
continue;
}

int res = INF; REP(i, nn) REP(d, 4){
checkMin(res, f(i, d));
}
if (res == INF) res = -1;
OT(res);
}
}
```

Problem F. Infinite Go

Analysis:

（先出基本装、Gank 一波，再和队友抱团。。）。。。

```
//}/* .................................................................................................................................. */

const int N = int(1e4) + 9;
map<PII, int> B; // Board
int x[N], y[N], f[N], p[N];
int n, n1, n2;

int Find(int x){
return p[x] == x ? x : p[x] = Find(p[x]);
}

void Union(int x, int y){
x = Find(x), y = Find(y); if (x == y) return;
p[x] = y; f[y] += f[x];
}

void del(int n){
if (n&1) --n2; else --n1; B.erase(MP(x[n], y[n]));
REP(d, 4){
int xx = x[n] + dx[d], yy = y[n] + dy[d];
if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;
int m = B[MP(xx, yy)];
if ((n^m)&1) ++f[Find(m)]; else del(m);
}
}

void print(){
FOR_1(a, 1, 10){
FOR_1(b, 1, 10){
if (!CTN(B, MP(a, b))) putchar('.');
else putchar(B[MP(a, b)]&1 ? '&' : '*');
}
puts("");
}
puts("");
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

Rush{
CLR(B), n = n1 = n2 = 0; Rush{
RD(x[n], y[n]); p[n] = B[MP(x[n], y[n])] = n; f[n] = 0;
if (n&1) ++n2; else ++n1;

REP(d, 4){
int xx = x[n] + dx[d], yy = y[n] + dy[d];
if (!xx || !yy || CTN(B, MP(xx, yy))) continue;
++f[n];
}
REP(d, 4){
int xx = x[n] + dx[d], yy = y[n] + dy[d];
if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;
int m = Find(B[MP(xx, yy)]);
--f[m]; if ((m^n)&1 && !f[m]) del(m);
}
REP(d, 4){
int xx = x[n] + dx[d], yy = y[n] + dy[d];
if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;
int m = Find(B[MP(xx, yy)]);
if (!((m^n)&1)) Union(m, n);
}

if (!f[Find(n)]) del(n);

++n;
}
printf("%d %d\n", n1, n2);
}
}

```

Problem G. Ants

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2818548

Problem H. Rabbit Kingdom

Analysis:

```
//}/* .................................................................................................................................. */

const int N = int(2e5) + 9;
int n;

namespace BIT{
typedef int intt;
intt C[N], S;
if (!x) return;
for (;x<=n;x+=low_bit(x)) C[x] += d;
S += d;
}
intt Sum(int x){
intt res = 0; for (;x;x^=low_bit(x)) res += C[x];
return res;
}
intt Sum(int l, int r){
return Sum(r) - Sum(l-1);
}
} using namespace BIT;

//最小素因子。。
const int PMAX = N;
VI P; bitset<PMAX> isC; int p[PMAX];
#define ii (i*P[j])
void sieve(){
FOR(i, 2, PMAX){
if (!isC[i]) P.PB(i),p[i]=i;
for (int j=0;j<SZ(P)&&ii<PMAX;++j){
isC[ii]=1; p[ii]=P[j]; if (!(i%P[j])) break;
}
}
}
#undef ii

int A[N], suc[N], prd[N], last[N];
VII qry[N], rls[N]; int res[N];

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

sieve();

int q; while (RD(n, q)){

RST(C); S = 0; REP_1(i, n) RD(A[i]), CLR(qry[i], rls[i]);

REP(i, q){
int l, r; RD(l, r);
qry[r].PB(MP(l, i));
}

RST(last); REP_1(i, n){
int x = A[i]; prd[i] = 0;
while (x != 1){
int px = p[x]; checkMax(prd[i], last[px]); last[px] = i;
do x /= px; while (p[x] == px);
}
}

FLC(last, 0x3f); DWN_1(i, n, 1){
int x = A[i]; suc[i] = INF;
while (x != 1){
int px = p[x]; checkMin(suc[i], last[px]);
last[px] = i;
do x /= px; while (p[x] == px);
}
}

REP_1(i, n) if (suc[i] == INF) suc[i] = 0;

REP_1(i, n){

Add(i, 1); A[i] = 1; int l = prd[i], r = suc[i];

rls[r].PB(MP(i, -1));
rls[r].PB(MP(l, 1));

ECH(it, rls[i]){
}

ECH(it, qry[i]){
int l = it->fi, id = it->se;
res[id] = S - BIT::Sum(l-1);
}

//REP_1(i, n) cout << Sum(i, i) << " "; puts("");
}
//puts("");
REP(i, q) OT(res[i]);
}
}

```

Problem I. Gems Fight!

Analysis:

（主要是 The Gems collected are stored in a shared cooker.

```
//}/* .................................................................................................................................. */

const int N = 21, M = 9;
int F[1<<N], S[1<<N], n, m, s0;

void init(){

VVI I; REP(i, n){
VI t; Rush t.PB(RD()-1);
I.PB(t);
}

static int cnt[M]; REP(s, _1(n)){
RST(cnt); REP(i, n) if (_1(s, i)) ECH(it, I[i]) ++cnt[*it];
S[s] = 0; REP(i, m) S[s] += cnt[i] / s0;
}

FLC(F, -1);
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

while (RD(m,n,s0)){

init(); FLC(F, 0x8f); F[_U(n)] = 0; DWN(s, _1(n), 1){
REP(i, n) if (_1(s, i)){
int ss = s ^ _1(i), d = S[s]-S[ss];
if (d) checkMax(F[ss], F[s] + d);
else checkMax(F[ss], -F[s]);
}
}

OT(F[0]);
}
}

```

Problem K. Candy Factory

Analysis:

`S -> M -> C0 <-> C1 -> T`
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2823256

`S -> M -> C0 -> C1 -> T`
`S ------> C2 -> C1 -> T`
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2822981