1. BearPair之bigDistance
1.1 题目概述
在 <= 50的字符串中找位置i，j 满足
(1) s[i] != s[j];
(2) abs(i-j)尽可能大。
若不存在返回-1， 否则返回最大值。
1.2 基本思路
没什么好说的，串长这么短 O(n^2)直接A了。
1.3 代码
class BearPair {
public:
int pos[];
int bigDistance(string s) {
int len = s.length();
int mx = -;
rep(i, , len) {
rep(j, , len) {
if (s[j]==s[i])
continue;
mx = max(mx, abs(j-i));
}
}
return mx;
}
};
2. BearChairs之findPositions
2.1 题目描述
一家餐馆，椅子排成一行从1开始，足够长，有N个元素的数组atLeast表示第i个顾客希望他的椅子编号大于等于atLeast[i]。
同时，需要保证任意两个顾客的椅子间相隔至少为d，并且顾客最终得到的椅子编号越小越好。这里，顾客的请求是有序的。
求最终的椅子编号。
2.2 基本思路
基本想法是贪心，第k个顾客最好的可能性是得到atLeast[k]编号的椅子。
如果此时该顾客与前k-1个顾客的间隔都大于等于d，那么答案就是atLeast[k]。
假设不满足，如果我们可以使前k-1个顾客的椅子编号按升序排列，那么当answer[j]-d<answer[k] && answer[k]<answer[j]+d
时，下一个最优的候选项即为answer[j]+d，而该候选项一定满足answer[1..j]。仅需判断其是否满足answer[j+1..k-1]即可。
因此，使用set维护已经确定的最优位置，即可解。
2.3 代码
class BearChairs {
public:
static const int maxn = ;
vi findPositions(vi vc, int d) {
int sz = SZ(vc), tmp;
vi ret;
sti st;
sti::iterator iter;
rep(i, , sz) {
int pos = vc[i];
for (iter=st.begin(); iter!=st.end(); ++iter) {
tmp = *iter;
if (tmp-d<pos && pos<tmp+d) {
pos = tmp + d;
}
}
ret.pb(pos);
st.insert(pos);
}
return ret;
}
};
2.4 数据发生器
import sys
import string
from random import randint def GenData(fileName):
with open(fileName, "w") as fout:
t = 1
bound = 10**6
# fout.write("%d\n" % (t))
for tt in xrange(t):
n = randint(1, 1000)
atLeast = []
for i in xrange(n):
x = randint(1, bound)
atLeast.append(x)
fout.write(" ".join(map(str, atLeast)) + "\n")
d = randint(1, 10**6)
fout.write("%d\n" % (d)) def MovData(srcFileName, desFileName):
with open(srcFileName, "r") as fin:
lines = fin.readlines()
with open(desFileName, "w") as fout:
fout.write("".join(lines)) def CompData():
print "comp"
srcFileName = "F:\Qt_prj\hdoj\data.out"
desFileName = "F:\workspace\cpp_hdoj\data.out"
srcLines = []
desLines = []
with open(srcFileName, "r") as fin:
srcLines = fin.readlines()
with open(desFileName, "r") as fin:
desLines = fin.readlines()
n = min(len(srcLines), len(desLines))-1
for i in xrange(n):
ans2 = int(desLines[i])
ans1 = int(srcLines[i])
if ans1 > ans2:
print "%d: wrong" % i if __name__ == "__main__":
srcFileName = "F:\Qt_prj\hdoj\data.in"
desFileName = "F:\workspace\cpp_hdoj\data.in"
GenData(srcFileName)
MovData(srcFileName, desFileName)
3. BearFair2之isFair
3.1 题目描述
有一个包含n(n%3 == 0)个元素的集合，其中的元素都在[1,b]区间，其中mod3等于0、1、2的元素个数均为n/3。
现有两个长度均为q数组upTo, quantity表示集合中的元素在区间[1, upTo[i]]的数目为quantity[i]。
判定是否存在这样一个集合满足upTo和quantity。
其中upTo的元素在[1,b]区间内，quantity的元素在[1,n]区间内，b在区间[1,1000]内。
3.2 基本思路
这是一个判定问题，首先以upTo作为first, quantity作为second重新构建pair数组，排序后，可以做初步的剪枝。
但仍需进一步判定是否存在这样的集合。基本思路是网络流，难点是如何构建图。
对pair树组的每个结点编号1001...1001+q-1
对1..b编号为1...b
对%3==0作结点mod0
对%3==1作结点mod1
对%3==2作结点mod2
可以这样建图：
1）st对pair结点建边，容量为对应的quantity[i]-quantity[i-1]；
2）pair结点对它包含的区间中的每个结点建边，容量为1；
3）编号1..b对其对应的modx建边，容量为1；
4）modx对ed建边，容量为n/3。
需要注意pair数组可能没有覆盖[1，b]，对余下的区间仍需要建边，与上述类似。
然后，判定最大流是否为n即可。
使用Dinic解该网络流。
3.3 代码
class BearFair2 {
typedef struct {
int v, f, nxt;
} edge_t;
public:
static const int INF = 0x3f3f3f3f;
static const int maxv = ;
static const int maxe = 1e5+;
static const int st = maxv - ;
static const int ed = maxv - ;
static const int mod0 = maxv - ;
static const int mod1 = maxv - ;
static const int mod2 = maxv - ;
int head_[maxv];
int head[maxv], l;
int Q[maxv];
int dis[maxv];
edge_t E[maxe];
int n, b;
void init() {
memset(head, -, sizeof(head));
l = ;
}
void addEdge(int u, int v, int c) {
E[l].v = v;
E[l].f = c;
E[l].nxt = head[u];
head[u] = l++;
E[l].v = u;
E[l].f = ;
E[l].nxt = head[v];
head[v] = l++;
}
bool bfs() {
int l = , r = ;
int u, v, k;
memset(dis, , sizeof(dis));
Q[r++] = st;
dis[st] = ;
while (l < r) {
u = Q[l++];
for (k=head[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (E[k].f && !dis[v]) {
dis[v] = dis[u] + ;
if (v == ed)
return false;
Q[r++] = v;
}
}
}
return true;
}
int dfs(int u, int val) {
if (val== || u==ed)
return val;
int ret = , tmp;
int v;
for (int& k=head_[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (E[k].f && dis[v]==dis[u]+ && (tmp=dfs(v, min(val, E[k].f)))>) {
ret += tmp;
val -= tmp;
E[k].f -= tmp;
E[k^].f += tmp;
if (val == )
break;
}
}
return ret;
}
int Dinic() {
int ret = , tmp;
while () {
if (bfs())
break;
memcpy(head_, head, sizeof(head));
while () {
tmp = dfs(st, INF);
if (tmp == )
break;
ret += tmp;
}
}
return ret;
}
string isFair(int n, int b, vector <int> upTo, vector <int> quan) {
this->n = n;
this->b = b;
init();
vpii vp;
int sz = SZ(upTo);
rep(i, , sz) {
vp.pb(mp(upTo[i], quan[i]));
}
sort(all(vp));
rep(i, , sz) {
if (vp[i].sec > vp[i].sec)
return "unfair";
if (i && vp[i].sec<vp[i-].sec)
return "unfair";
if (i && vp[i].fir==vp[i-].fir && vp[i].sec!=vp[i-].sec)
return "unfair";
}
int fr = , pm = ;
rep(i, , sz) {
addEdge(st, +i, vp[i].sec-pm);
while (fr <= vp[i].fir) {
addEdge(+i, fr, );
++fr;
}
pm = vp[i].sec;
}
if (fr <= b) {
addEdge(st, +sz, n-pm);
while (fr <= b) {
addEdge(+sz, fr, );
++fr;
}
}
for (int i=; i<=b; i+=)
addEdge(i, mod1, );
for (int i=; i<=b; i+=)
addEdge(i, mod2, );
for (int i=; i<=b; i+=)
addEdge(i, mod0, );
addEdge(mod0, ed, n/);
addEdge(mod1, ed, n/);
addEdge(mod2, ed, n/);
int flow = ;
flow = Dinic();
if (flow == n)
return "fair";
else
return "unfair";
}
};
3.4 数据发生器
import sys
import string
from random import randint def GenData(fileName):
with open(fileName, "w") as fout:
t = 1
bound = 10**6
# fout.write("%d\n" % (t))
for tt in xrange(t):
n = randint(1, 16) * 3
b = randint(1, n)
fout.write("%d %d\n" % (n, b))
q = randint(1, 50)
upTo = []
for i in xrange(q):
x = randint(1, b)
upTo.append(x)
fout.write(" ".join(map(str, upTo)) + "\n")
quantity = []
for i in xrange(q):
x = randint(0, n)
quantity.append(x)
fout.write(" ".join(map(str, quantity)) + "\n") def MovData(srcFileName, desFileName):
with open(srcFileName, "r") as fin:
lines = fin.readlines()
with open(desFileName, "w") as fout:
fout.write("".join(lines)) def CompData():
print "comp"
srcFileName = "F:\Qt_prj\hdoj\data.out"
desFileName = "F:\workspace\cpp_hdoj\data.out"
srcLines = []
desLines = []
with open(srcFileName, "r") as fin:
srcLines = fin.readlines()
with open(desFileName, "r") as fin:
desLines = fin.readlines()
n = min(len(srcLines), len(desLines))-1
for i in xrange(n):
ans2 = int(desLines[i])
ans1 = int(srcLines[i])
if ans1 > ans2:
print "%d: wrong" % i if __name__ == "__main__":
srcFileName = "F:\Qt_prj\hdoj\data.in"
desFileName = "F:\workspace\cpp_hdoj\data.in"
GenData(srcFileName)
MovData(srcFileName, desFileName)