[Sgu395][bzoj2363]Binary Cat Club
一道神题……
rzO 发现立杰在初三（http://hi.baidu.com/wjbzbmr/item/4a50c7d8a8114911d78ed0a9据此可以推断）就怒A了此题…… Orz
/*************************************************************
我这种大弱菜，看了题目后完全茫然。
看了剧透后往网络流方向想，结果还是不会T_T。
然后去看题解，还是不会T_T。
然后去看题解的题解，还是不会T_T。
然后想了一个晚上，第二天才有点明白T_T。
上述题解在这里
**************************************************************/
题解【sol】：
请先观摩观摩来自安徽省合肥一中的梅诗珂犇的题解。衷心感谢！
【
Binary Cat Club (SGU 395)解题报告
安徽省合肥一中梅诗珂
题目大意：有关于一场聚会的N条记录，每条记录的格式有 ， ， 三种，分别表示进来一个叫”name”的人，出去一个叫”name”的人，当前聚会厅有visitors个人。现在记录的一部分遗失，但剩下记录的顺序是原顺序。给出剩下的记录，请添加最少条数的记录，使之合理化。注意：可以有人进出会厅多次，可以有人聚会结束待在会厅。
约束条件： 1≤N≤200 , 每条 记录中的visitors不超过100。
分析：
首先要明确什么是”合理”,可以看出”合理”有两条要求：
1） 对同一个人，其对应的记录应以 开头，第2个(如果有)一定是 ，第3个(如果有)一定是,交错出现。
2） 任何时候 必须与当前在场人数相同。
显然，不同的人之间互不影响。为了做到第一个要求，我们设关于某人的记录出现的
位置为a1<a2<a3<…<am。分3种情况:
1) ai对应的记录是,ai+1对应的记录是 ，那么我们一定要在ai到ai+1之间插入(当ai+1不存在时可不插入)。
2) ai对应记录 ，ai+1对应的记录是 ，那么有两种可能，一种是中间不插入任何关于name的记录，另一种是插入依次插入 ，如果把 看成左括号， 看成右括号，则两种形式为()和()()。
3） ai对应记录 ，ai+1对应记录 ，那么我们要在ai到ai+1之间插
入 。
其实完全可能插入更多的操作，但这样必然会产生完全由新插入的操作组成的
“()”,我们完全可以把其中的name替换成一个从没有出现过的新名字(而逆向替换可
能是非法的)。因此这样考虑简化了问题。
为了达到第二个目标，我们考虑补充一些“新人”，我们可以让所有“新人”的名
字都不相同。
问题转化为：合理选择已有人的 ， 操作插入位置，并插入若干“新
人”,从而使任何时候记录真实。
要考虑的情况很多，但是由恰好与visitors相同，想到带上下界的网络流，问题就
不难解决。
设有N1个 记录，对第i(1≤i≤N1)，从i点向i+1点连一条上下界皆为
visitors的边，得到的链称为“主链”。
我们要对每一种情况，设计一种结构，“安装”到主链上。
第1种： 设ai在第v个 ，和第v+1个 之间，ai+1在u，（u+1）之间，新建一个点p，从p向v连边(1,1)表示已有的 记录，v到u之间的点向p连边(0,1)表示要插入一个 记录。如下图所示(括号中的第一个数表示下界，第二个表示上界，下同)：
第2种： 设ai在第v个 ，和第v+1个 之间，ai+1在u，（u+1）之间。新建点p,q，从p向v连边(1,1)表示已有的 记录，(v+1)到u之间的点向p连边(0,1)（注：应为p向(v+1)到u之间的点连边(0,1)），从u向q连边(1,1)表示已有的 记录，v到(u-1)之间的点向q连边(0,1)，从q向p连边(1,2)，表示中间可能还会插入一个“)(”。如下图所示：
第3种： 设ai在第u个 ，和第(u+1)个 之间，ai-1在v，
（v+1）之间。新建点q，从u向q连边(1,1) 表示已有的 记录，q向v到u之间的点连边(0,1)表示待插入的 。如下图所示:（缺了张图）
还要考虑“新人”的插入，我们对主链上的每个点v，新建一个点v’,表示新人的出现在第(v-1)个 ，与第v个 之间，从v’向v连边(0,∞)表示在此处可以插入任意多个新人,从(v+1)到(N1+1)向v’连边(0,∞)表示这些新人对应的 记录。如下图所示：
完成构图，我们只要对其求最小费用可行流即可，由上面论述正确性显然。我们来分析复杂度，主链上有N1个点，对剩下的每个点加上新人对应的点共有(N+ N1)个点，非主链的N个点向主链上每个点各连一条边，最多有 条边，因此我们要对 个点， 条边的图求最小费用流，是可以接受的。
总结：本题的难点是构造出的图并没有源汇，求的也不是最大流，与NOI2008的《志愿者招募》类似，这与大多数网络流问题不同，显示了网络流模型的灵活。在建模过程中有一些小知识：比如串联求最小值，并联求和，点提供一个流量平衡方程，边提供流量限制，想让一条边不出现在最小割中，只需让其容量为无穷大。建立的模型也有几类：如有源汇的最大流，最小费用最大流，带上下界最大(小)流，无源汇最小(大)费用流。提高建模水平，只能靠多练习，解决了问题多推广。】
//////////////////////////////////////////////////////////
然后我再补充几个细节：
- 对于上述的第2种，即+-的情况，似乎有一个bug，就是我们没法保证流出来的结果一定是+- or +-+-，可能会出现++--。不过没关系，我们可以把中间的+-看作是新人。
- 为了方便，可以在最前面加一个= 0
- 对于第一个为-的情况，可以当作是--来处理，也就是在每个名字操作序列的最前面加-。
- 对于最后一个为+的情况，可以当作是++来处理，也就是在每个名字操作序列的最后面加+。
- 对于新人和最后一个为+的情况，如果是散场的时候可以不用增加费用。
- 输出的处理：我们可以将整个操作序列合起来处理，对于某个人单独记录这个人的操作序列已经处理到的位置。对于原有操作就等到循环到了它的时候再输出，对于新增的操作则处理到的时候就输出，不用考虑顺序问题。
P.S 这题我只在sgu395上交过，没有在BZ上交（因为我不是高富帅……交不起）。
附上AC代码和对拍程序
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
void TLE(){while(1);}
using std::vector;
using std::string;
using std::map;
using std::cout;
using std::endl;
const int N = 800 + 9;
char name[100];
map<string,int>namelist;
struct Operation
{
bool type;
int idx;
string name;
}oper[201][201];
struct Edge{int link,next;}es[N*N*2];
int n,equals,Vc,src,sink,cap[N][N],low[N][N],cost[N][N],dis[N],ec,son[N],opers[N],pre[N],equal[N],new_people,stcap[N][N],delta[N],cnt,name_cnt,type[N],idx[201][201],ans;
vector<string> Out[N];
const string shenben[14]={"wjmzbmr","sevenkplus","acrush","fjxmlhx","lydrainbowcat","fotile","vfleaking","seter","cxjyxxme","hyn","mzn","acaeroligh","thcdusman","black"};
string now("a");
void getnext(string &s)
{
int len = s.size() - 1;
while (len >= 0 && s[len] == 'z') s[len--] = 'a';
if (len < 0) s = "a" + s;
else ++s[len];
}
string newname()
{
while (name_cnt < 14 && namelist[shenben[name_cnt]]) ++name_cnt;
if (name_cnt >= 14) {
while (namelist[now]) getnext(now);
namelist[now] = 1;
return now;
}
namelist[shenben[name_cnt]] = 1;
return shenben[name_cnt];
}
inline void addedge(const int x,const int y)
{
es[++ec].link = y;
es[ec].next = son[x];
son[x] = ec;
}
bool SPFA()
{
static bool inq[N];
static std::queue<int> q;
memset(dis,0x3f,sizeof dis);
inq[src] = 1; dis[src] = 0;
for (q.push(src); !q.empty(); q.pop()) {
const int u = q.front();
inq[u] = 0;
for (int i = son[u]; i; i = es[i].next) {
const int v = es[i].link;
if (cap[u][v] && dis[v] > dis[u] + cost[u][v]) {
pre[v] = u;
dis[v] = dis[u] + cost[u][v];
if (!inq[v]) inq[v] = 1, q.push(v);
}
}
}
return dis[sink] != 0x3f3f3f3f;
}
int Cost_Flow()
{
int ans = 0;
while (SPFA()) {
int Min = 0x7ffffff;
for (int i = sink; i != src; i = pre[i])
Min = std::min(Min,cap[pre[i]][i]);
for (int i = sink; i != src; i = pre[i])
cap[pre[i]][i] -= Min,cap[i][pre[i]] += Min;
ans += Min * dis[sink];
}
return ans;
}
void build_graph()
{
for (int i = 1; i <= equals; ++i)
low[i - 1][i] = cap[i - 1][i] = equal[i];
//会有重边
for (int k = 1; k <= cnt; ++k) {
//oper[j][0].type = 0; // 0 --> '-'
oper[k][opers[k] + 1].type = 1; // 1 --> '+'
oper[k][opers[k] + 1].idx = equals;
for (int i = 0; i <= opers[k]; ++i) {
const int t1 = oper[k][i].type,t2 = oper[k][i + 1].type;
/******************************** ++ *********************************/
if (t1 == 1 && t2 == 1) {
const int u = oper[k][i].idx, v = oper[k][i + 1].idx;
low[Vc][u] += 1; cap[Vc][u] += 1;
for (int j = u; j <= v; ++j) {
cap[j][Vc] += 1;
if (i != opers[k] || j != v) cost[j][Vc] += 1;
}
idx[k][i] = Vc++;
/******************************** -- *********************************/
}else if (t2 == 0 && t1 == 0) {
const int u = oper[k][i].idx, v = oper[k][i + 1].idx;
low[v][Vc] += 1; cap[v][Vc] += 1;
for (int j = u; j <= v; ++j)
cap[Vc][j] += 1,cost[Vc][j] += 1;
idx[k][i] = Vc++;
/******************************** +- *********************************/
}else if (t1 == 1 && t2 == 0) {
const int u = oper[k][i].idx, v = oper[k][i + 1].idx;
low[Vc + 1][Vc] += 1; cap[Vc + 1][Vc] += 2;
low[Vc][u] += 1; cap[Vc][u] += 1;
for (int j = u; j <= v; ++j)
cap[Vc][j] += 1,cost[Vc][j] += 1;
idx[k][i] = Vc++;
low[v][Vc] += 1; cap[v][Vc] += 1;
for (int j = u; j <= v; ++j)
cap[j][Vc] += 1,cost[j][Vc] += 1;
idx[k][i + 1] = Vc++;
}
}
}
new_people = Vc;
for (int i = 0; i < equals; ++i) {
cap[Vc][i] = 10000; //每次最多50人 200 * 50 = 10000
cost[Vc][i] = 1;
for (int j = i + 1; j <= equals; ++j) {
cap[j][Vc] = 10000;
if (j != equals) cost[j][Vc] = 1;//可以不出去
}
++Vc;
}
for (int i = 0; i < Vc; ++i)
for (int j = 0; j < Vc; ++j)
if (cap[i][j]) {
if (cost[i][j]) cost[j][i] = -cost[i][j];//cost只会一边有值(新图)
addedge(i,j);
if (!cap[j][i]) addedge(j,i);
}
memcpy(stcap,cap,sizeof cap);
/************************ rebuild_graph ************************/
for (int i = 0; i < Vc; ++i)
for (int j = 0; j < Vc; ++j)
if (low[i][j]) {
delta[i] -= low[i][j];
delta[j] += low[i][j];
cap[i][j] -= low[i][j];
}
src = Vc++; sink = Vc++;
for (int i = 0; i < Vc - 2; ++i)
if (delta[i] > 0) cap[src][i] = delta[i],addedge(src,i),addedge(i,src);
else cap[i][sink] = - delta[i],addedge(i,sink),addedge(sink,i);
/************************ rebuild_graph ************************/
}
void out_procedure()
{
static bool tag[201][201];
/************************ Get_Extra_Net ************************/
for (int i = 0; i < Vc; ++i)
for (int j = 0; j < Vc; ++j)
if (low[i][j]) cap[i][j] += low[i][j];
/************************ Get_Extra_Net ************************/
for (int ii = 1; ii <= type[0]; ++ii) {
const int j = type[ii]/201, k = type[ii]%201,i = idx[j][k];
if (tag[j][k]) Out[oper[j][k].idx].push_back("- " + oper[j][k].name);
/************************** ++ ***************************/
if (oper[j][k].type == 1 && oper[j][k + 1].type == 1) {
Out[oper[j][k].idx].push_back("+ " + oper[j][k].name);
for (int l = oper[j][k].idx; l <= oper[j][k + 1].idx; ++l)
if (cap[l][i] != stcap[l][i]) {
if (cost[l][i]) Out[l].push_back("- " + oper[j][k].name);
break;
}
}
/************************** -- ***************************/
else if (oper[j][k].type == 0 && oper[j][k + 1].type == 0) {
for (int l = oper[j][k].idx; l <= oper[j][k + 1].idx; ++l)
if (cap[i][l] != stcap[i][l]) {
Out[l].push_back("+ " + oper[j][k + 1].name);
break;
}
tag[j][k + 1] = 1;
//Out[oper[j][k + 1].idx].push_back("- " + oper[j][k + 1].name);//必须后加//出事了!!
}
/************************** +- ***************************/
else if (oper[j][k].type == 1 && oper[j][k + 1].type == 0) {
Out[oper[j][k].idx].push_back("+ " + oper[j][k].name);
int mem1 = -1,mem2 = -1;
for (int l = oper[j][k].idx; l <= oper[j][k + 1].idx; ++l)
if (cap[i][l] != stcap[i][l]) {mem2 = l;break;}//+
for (int l = oper[j][k].idx; l <= oper[j][k + 1].idx; ++l)
if (cap[l][i + 1] != stcap[l][i + 1]) {mem1 = l;break;}//-
if (mem1 != -1 || mem2 != -1) {
if (mem1 <= mem2) {
Out[mem1].push_back("- " + oper[j][k].name);
Out[mem2].push_back("+ " + oper[j][k].name);
}else {
string tmp = newname();
Out[mem2].push_back("+ " + tmp);
Out[mem1].push_back("- " + tmp);
}
}
//Out[oper[j][k + 1].idx].push_back("- " + oper[j][k].name);//出事了!!
tag[j][k + 1] = 1;
}
}
static string tmp[10001];int st;
for (int i = new_people; i < Vc; ++i) {
if (cap[i][i - new_people] != stcap[i][i - new_people]) {
st = 0;
for (int j = cap[i][i - new_people]; j < stcap[i][i - new_people]; ++j) {
tmp[++st] = newname();
Out[i - new_people].push_back("+ " + tmp[st]);
}
}else continue;
for (int j = i - new_people + 1; j < equals; ++j)
for (int k = cap[j][i]; k != stcap[j][i]; ++k) Out[j].push_back("- " + tmp[st--]);
}
int test = 0;
for (int i = 0; i <= equals; ++i) {
if (i) printf("= %d\n",equal[i]);
test += Out[i].size();
for (vector<string>::iterator iter = Out[i].begin(); iter != Out[i].end(); ++iter)
cout << *iter << endl;
}
//if (test + equals != ans) TLE();
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("395.in","r",stdin);
freopen("395.out","w",stdout);
#endif
scanf("%d",&n);
//equal[0] = 0;
for (int i = 1,x; i <= n; ++i) {
char opt;
scanf("\n%c",&opt);
if (opt == '=') {
scanf("%d",&x);
equal[++equals] = x;
}else {
scanf("%s",name);
int t,mem = cnt;
if (!namelist[string(name)])
namelist[string(name)] = ++cnt;
t = namelist[string(name)];
oper[t][++opers[t]].type = (opt == '+');
oper[t][opers[t]].name = name;
oper[t][opers[t]].idx = equals;
if (cnt != mem) type[++type[0]] = t * 201 + 0;
type[++type[0]] = t * 201 + opers[t]; // for output
}
}
Vc = equals + 1;
build_graph();
ans = Cost_Flow() + n;
printf("%d\n",ans);
out_procedure();
}
对拍程序：
使用说明：返回值为1则答案错误。0为正确。
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
FILE *f1;
FILE *f2;
FILE *f3;
using std::map;
using std::string;
map<string,int>Map;
char s2[201][30];
int n,m,ans;
int main()
{
f1 = fopen("395_std.out","r");
f2 = fopen("395.out","r");
f3 = fopen("395.in","r");
fscanf(f1,"%d",&ans);
fscanf(f2,"%d\n",&n);
fscanf(f3,"%d\n",&m);
for (int i = 1; i <= m; ++i) fgets(s2[i],100,f3);
if (ans != n) return 1;
char name[30],s1[30];
int cnt = 0,j = 1;
for (int i = 1; i <= n; ++i) {
fgets(s1,100,f2);
if (j <= m && strcmp(s1,s2[j]) == 0) ++j;
if (s1[0] == '=') {
int x;
sscanf(s1,"= %d",&x);
if (x != cnt) return 1;
}else if (s1[0] == '+') {
sscanf(s1,"+ %s",name);
if (++Map[string(name)] > 1) return 1;
++cnt;
}else if (s1[0] == '-') {
sscanf(s1,"- %s",name);
if (!Map[string(name)]--) return 1;
--cnt;
}
}
if (j != m + 1) return 1;
fclose(f1);fclose(f2);fclose(f3);
}
Checker.bat
@echo off
:loop
data.exe
395.exe
395_std.exe
checker.exe
if not errorlevel 1 (
ping -n 2 127.1>nul
echo correct
goto loop
)
pause
goto loop
最新文章
- ASP.NET MVC5+EF6+EasyUI 后台管理系统（58）-DAL层重构
- coreseek安装过程
- WinObjC？这是什么鬼？
- 打字机游戏Ⅱ之手速pk
- 与众不同 windows phone (43) - 8.0 相机和照片: 镜头的可扩展性, 图片的可扩展性, 图片的自动上传扩展
- js动态生成数据列表
- -----------------------------SpringMVC理解-----------------------------
- 软件测试 -- alpha测试和beta测试的区别
- Docker命令使用详解
- Protel 99SE PCB 打印技巧
- python笔记之字符串
- Andriod学习笔记 - 参考
- session锁问题
- 201521123100 《Java程序设计》第13周学习总结
- LINUX：alias命令详解
- [array] leetcode - 34. Search for a Range - Medium
- structure streaming笔记
- 10.21CRM项目(01)
- 安装ubuntu gnome桌面
- 吴裕雄 python 爬虫（2）