over 6 years ago
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
GooseInZooDivOne
关键词：并查集、图论
算法简述
这个题一看就是一个比较套路的题目，先把两之间距离小于dist的用并查集缩起来，然后数一下奇数集合的数量和偶数集合的数量，然后判一下就可以了。
一点点小代码
const int N = 51;
int id[N][N];
int f[N * N], cnt[N * N];
int get(int u) { //并查集
if (u == f[u]) return u;
return f[u] = get(f[u]);
}
void join(int u, int v) {
f[get(u)] = get(v);
}
class GooseInZooDivOne {
public:
int count(vector<string> field, int dist) {
int n = field.size(), m = field[0].size();
int tot = 0;
REP(i, 0, n - 1) REP(j, 0, m - 1) id[i][j] = ++tot;
REP(i, 1, tot) f[i] = i, cnt[i] = 0;
REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v')
REP(k1, 0, n - 1 ) REP(k2, 0, m - 1) if (k1 != i || k2 != j)
if (field[k1][k2] == 'v') if (abs(i - k1) + abs(j - k2) <= dist) join(id[i][j], id[k1][k2]);
//把两两之间距离小于dist的那些给放到一个集合中去
REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v') cnt[get(id[i][j])]++;
int ans1 = 0, ans2 = 0;
REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v' && f[id[i][j]] == id[i][j]) {
if (cnt[id[i][j]] & 1) ++ans1; //集合大小为奇数的集合个数
else ++ans2; //集合大小为偶数的集合个数
}
int ans = pow(2, ans1 + ans2 - (ans1 > 0)); //因为要满足goose的数目为偶数，所以奇数的那些集合只能选偶数个
return (ans - 1 + mo) % mo;//至少要有一个goose
}
};
WolfInZooDivOne
关键词：动态规划
算法简述
这个题目还是比较有意思的。首先考虑如果限制不是最多放两个而是最多放一个。那么就可以写一个这样的dp. 代表现在dp到第i个位置，这个区间里不放东西的方案数。具体的转移可以根据区间的左右端点来确定。那么受到这个思路的启发,可以写出一个这样的dp,, 其中k表示这个区间最多放一个东西。
一点点小代码
const int N = 310;
int f[2][N][N];// f[i][j][k]代表目前放了前i个位置，i到j位置都不能放wolf了， (j + 1)到k位置可以放一个wolf的方案数
PII a[N]; //所有的区间
int n, m, tmp;
stringstream fin;
class WolfInZooDivOne {
public:
int count(int N, vector<string> L, vector<string> R) {
fin.clear();
n = N;
REP(i, 1, L.size() - 1) L[0] += L[i];
REP(i, 1, R.size() - 1) R[0] += R[i];
fin << L[0];
m = 0;
while (fin >> tmp) a[++m].FR = tmp + 1;
fin.clear();
fin << R[0];
m = 0;
while (fin >> tmp) a[++m].SC = tmp + 1; //处理一下格式
sort(a + 1, a + m + 1);
CL(f, 0);
f[0][0][0] = 1;
int j = 1, c = 0, ans = 0, l = 0;
REP(i, 0, n - 1) {
c ^= 1; CL(f[c], 0); //滚动数组
while (j <= m && a[j].FR <= i + 1) getmax(&l, a[j].SC), ++j;//目前包含i + 1这个位置的最远的区间
REP(k1, 0, n)
REP(k2, k1, n) {
f[c][k1][k2] = (f[c][k1][k2] + f[c ^ 1][k1][k2]) % mo; //这个位置不放wolf
if (k1 < i + 1) f[c][k2][l] = (f[c][k2][l] + f[c ^ 1][k1][k2]) % mo; //这个位置放wolf
}
}
REP(i, 0, n)
REP(j, i, n) ans = (ans + f[c][i][j]) % mo;
return ans;
}
};
DeerInZooDivOne
关键词：动态规划，费用流，KM
题目简述
给出一个个点的树，让你从中选出两个连通子图，使得这两个子图同构。
算法简述
这个题看起来挺熟悉的，不知道哪里见到过。感觉这种题也没啥好做法，就是暴力搞，复杂度反正就是玄学。
首先要先枚举一条断边，把整个树分成两部分，然后枚举这两部分中选择的点（也就是枚举两个根）。然后开始搞dp，这个dp的过程中由于需要对儿子进行配对，所以还要搞一个KM，或者费用流也可以。在dp的过程中可以瞎jb记忆化来加速。大致就是代表两个点为根的最大值。
一点小代码
class ZKW { //ZKW费用流板子
public:
#define INF 1000000000
#define MAXN 100000
#define MAXM 100000
struct edge_node
{
int p,next;
int w,c;
}edge[MAXM];
int vis[MAXN],instack[MAXN];
int head[MAXN],slk[MAXN];
int d[MAXN];
int cur[MAXM];
int cnt,S,T,index,tot;
LL ans,flow;
void ae(int a,int b,int weight,int cost)
{
edge[++cnt].p=b; edge[cnt].w=weight;
edge[cnt].c=cost; edge[cnt].next=head[a]; head[a]=cnt;
edge[++cnt].p=a; edge[cnt].w=0;
edge[cnt].c=-cost; edge[cnt].next=head[b]; head[b]=cnt;
}
int aug(int u,int now)
{
if (u==T)
{
ans+=(LL)now*d[T];
flow+=now;
return now;
}
int res=0,tmp;
vis[u]=instack[u]=index;
for (int &k=cur[u];k;k=edge[k].next)
{
int v=edge[k].p;
int t=d[u]+edge[k].c-d[v];
if (edge[k].w)
{
slk[v]=min(slk[v],t);
if (!t&&instack[v]!=index)
{
tmp=aug(v,min(now,edge[k].w));
res+=tmp;
edge[k].w-=tmp;
edge[k^1].w+=tmp;
if ((now-=tmp)==0) break;
}
}
}
instack[u]=false;
return res;
}
bool modlabel()
{
int del=INF;
for (int i=1;i<=T;++i) if (vis[i]!=index)
del=min(del,slk[i]);
if (del==INF) return false;
for (int i=1;i<=T;++i) if (vis[i]!=index)
d[i]+=del;
return true;
}
LL MCMF(int _S, int _T, int returnflow = 0)
{
S = _S, T = _T;
flow=ans=0;
for (int i=1;i<=T;++i) d[i]=0;
do
do{
for (int i=1;i<=T;++i) slk[i]=INF,cur[i]=head[i];
++index;
}
while (aug(S,INF));while (modlabel());
if (returnflow) return flow;
return ans;
}
void init(int n) {
index = cnt = 1;
REP(i, 1, n + 2) head[i] = 0, vis[i] = -1;
}
}solver;
const int N = 53;
int n;
struct node {
int p, next;
bool flag;
}edge[N * 2];
int head[N], cnt;
void ae(int a, int b) {
edge[++cnt].p = b;
edge[cnt].next = head[a];
head[a] = cnt;
edge[cnt].flag = 1;
}
int f[N][N][N][N];
vector<int> X, Y;
void dfs(vector<int> &V, int u, int fa) {
V.PB(u);
RED(k, u) if (edge[k].flag){
int v = edge[k].p;
if (v != fa) dfs(V, v, u);
}
}
int dp(int a, int fa, int b, int fb) { //记忆化搜索
if (f[a][fa][b][fb] != -1) return f[a][fa][b][fb];
vector<int> X, Y;
RED(k, a) if (edge[k].flag && edge[k].p != fa)
X.PB(edge[k].p);
RED(k, b) if (edge[k].flag && edge[k].p != fb)
Y.PB(edge[k].p);
for (int i = 0; i < X.size(); ++ i)
for (int j = 0; j < Y.size(); ++j) dp(X[i], a, Y[j], b);
solver.init(X.size() + Y.size()); //费用流初始化
int S = X.size() + Y.size() + 1, T = S + 1;
for (int i = 0; i < X.size(); ++ i) solver.ae(S, i + 1, 1, 0); //最大权匹配
for (int i = 0; i < Y.size(); ++ i) solver.ae(i + 1 + X.size(), T, 1, 0);
for (int i = 0; i < X.size(); ++ i)
for (int j = 0; j < Y.size(); ++j) {
solver.ae(i + 1, j + X.size() + 1, 1, -f[X[i]][a][Y[j]][b]);
}
f[a][fa][b][fb] = -solver.MCMF(S, T) + 1; //最大费用流
return f[a][fa][b][fb];
}
int solve(int a, int b) {
CL(f, 0xff);
X.clear(); Y.clear();
dfs(X, a, 0);
dfs(Y, b, 0);
int ans = 0;
REP(i, 0, X.size() - 1)
REP(j, 0, Y.size() - 1) { //枚举两边树的根
getmax(&ans, dp(X[i], 0, Y[j], 0));
}
return ans;
}
class DeerInZooDivOne {
public:
int getmax(vector<int> a, vector<int> b) {
n = a.size() + 1;
cnt = 1;
CL(head, 0);
REP(i, 0, a.size() - 1) ae(a[i] + 1, b[i] + 1), ae(b[i] + 1, a[i] + 1); //连边
int ans = 0;
REP(i, 1, n) RED(k, i) { //枚举断掉的边
int j = edge[k].p;
if (i > j) continue;
edge[k].flag = 0;
edge[k ^ 1].flag = 0;
ans = max(ans, solve(i, j));
edge[k].flag = 1;
edge[k ^ 1].flag = 1;
}
return ans;
}
};
