练习 7.11
写一个error函数，它取一个printf风格的包含%s、%c和%d指示符的格式串， 以及任意多个其他参数。请不要使用printf()。
解：
对于变动长度参数表的处理通过一些很像对待器的设施完成，这类设施的类型为va_list。宏va_start对这类设施进行初始化，还必须用宏va_end指明这种设施不会再用。要取得当前参数的值并将该设施移到下一个参数， 需要用va_arg。参数表的结束必须能从至今已经看到的实际参数确定（典型情况下，函数从没有省略号表示的某个常规参数哪里获得有关信息。）
#include <cassert>
#include <cstdarg>
#include <iostream>
#include <stdexcept>
using namespace std;
void error(char const * fmt, 
){
assert(fmt);
va_list p;
va_start(p, fmt);
for(char const *s=fmt; *s; ++s)
if(*s!='%')
cerr.put(*s);
else
switch(*(++s)){
case '%': cerr.put('%'); break;
case 's': cerr<<va_arg(p, char const *); break;
case 'c': cerr<<(char)va_arg(p, int); break;
case 'd': cerr<<va_arg(p, int); break;
default:
throw domain_error("error");
}
va_end(p);
}
int main(){
error("A string \"%s\", a single character \'%c\', an integer %d\n","Hello World", '$', 12345);
return 0;
}
posted @
2011-03-12 22:25 小阮 阅读(327) |
评论 (0) |
编辑 收藏
模拟
/**//*
ID: lorelei
TASK: spiral
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAXN = 800;
const int dx[]= {0,1,0,-1};
const int dy[]= {1,0,-1,0};
ifstream fin("spiral.in");
ofstream fout("spiral.out");
int m[MAXN][MAXN];
int N,M;
int main(){
int i, j, x=1, y=1, dir=0;
fin>>N;
M = N*N;
for(i=1; i<=M; ++i){
m[x][y]=i;
int tx = x + dx[dir];
int ty = y + dy[dir];
if(m[tx][ty] || tx>N || ty>N || tx<1 || ty<1){
dir++;
if(dir==4)dir=0;
}
x += dx[dir];
y += dy[dir];
}
for(i=1; i<=N; ++i){
for(j=1; j<N; ++j)
fout<<m[i][j]<<" ";
fout<<m[i][N]<<endl;
}
return 0;
}
posted @
2011-03-11 23:21 小阮 阅读(389) |
评论 (0) |
编辑 收藏
最长递增子序列问题。
O(n^2)
DP。 练练手
#include <iostream>
using namespace std;
const int MAX = 1005;
int A[MAX],F[MAX];
int N, ans=-1;
int main(){
int i,j;
scanf("%d", &N);
for(i=1; i<=N; ++i)
scanf("%d", &A[i]);
for(i=N; i>=1; --i){
F[i]=1;
for(j=i+1; j<=N; ++j)
if(A[j]>A[i] && F[j]+1>F[i])
F[i]=F[j]+1;
if(F[i]>ans)
ans = F[i];
}
printf("%d\n", ans);
return 0;
}
O(nlgn)
开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。 最长序列长度即为栈的大小top。
#include <iostream>
using namespace std;
const int MAX = 1005;
int stack[MAX];
int N, ans=-1;
int main(){
int i, tmp, top;
scanf("%d", &N);
stack[top=0]=-1;
for(i=1; i<=N; ++i){
scanf("%d", &tmp);
if(tmp>stack[top]){
stack[++top] = tmp;
}else{
int low=1, high=top;
while(low<=high){
int mid=(low+high)/2;
if(tmp>stack[mid])
low = mid+1;
else
high = mid-1;
}
stack[low]=tmp;
}
}
printf("%d\n", top);
return 0;
}
posted @
2011-03-10 11:21 小阮 阅读(236) |
评论 (0) |
编辑 收藏
题意：
Q1：LIS，最长长度为s
Q2：有多少个长度为s的子序列
Q3：若A[1]和A[n]可多次使用，问可以取多少个s长度的子序列
建模：
Q1：LIS，DP， F[i]表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K
for (int i=N;i>=1;i--){
F[i] = 1;
for (int j=i+1;j<=N;j++)
if (A[j] > A[i] && F[j]+1 > F[i])
F[i] = F[j]+1;
if (F[i] > Ans)
Ans = F[i];
}
Q2：
1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到<i.b>连接一条容量为1的有向边。
2、建立附加源S和汇T，如果序列第i位有F[i]=K，从S到<i.a>连接一条容量为1的有向边。
3、如果F[i]=1，从<i.b>到T连接一条容量为1的有向边。
4、如果j>i且A[i] < A[j]且F[j]+1=F[i]，从<i.b>到<j.a>连接一条容量为1的有向边。
求最大流，为第二问的解。
Q3：令(<1.a>,<1.b>)(<N.a>,<N.b>)(S,<1.a>)(<N.b>,T)这四条边的容量修改为无穷大，再求一次网络最大流，就是第三问结果。
posted @
2011-03-10 11:10 小阮 阅读(611) |
评论 (0) |
编辑 收藏
题意：
n个不同单位，每个单位ri 人；m个桌子，每个桌子坐ci人； 同一个单位的人不坐在一个桌子上，给出所有可能的方案。
建模：
建立二分图，每个单位为X集合中的结点，每个桌子为Y集合的结点，增加源点S和汇点T。
1. 添加 S->Xi，且权值为第i个单位的人数。
2. 添加 Yi->T，且权值为第i个桌子可容纳的人数。
3.添加 Xi ->Yi，且权值为1。
求网络最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。对于每个单位，从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况（一个可行解）。
分析：
对于二分图， 每个定点可以有多个匹配，称这类问题为二分图多重匹配。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次（一个餐桌上只能有一个单位的一个人），源汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。
posted @
2011-03-09 12:50 小阮 阅读(447) |
评论 (0) |
编辑 收藏【问题分析】
枚举答案转化为判定性问题，然后最小路径覆盖，可以转化成二分图最大匹配，从而用最大流解决。
【建模方法】
枚举答案A，在图中建立节点1..A。如果对于i<j有i+j为一个完全平方数，连接一条有向边(i,j)。该图是有向无环图，求最小路径覆盖。如果刚好满足最小路径覆盖数等于N，那么A是一个可行解，在所有可行解中找到最大的A，即为最优解。
具体方法可以顺序枚举A的值，当最小路径覆盖数刚好大于N时终止，A-1就是最优解。
【建模分析】
由于是顺序放球，每根柱子上的球满足这样的特征，即下面的球编号小于上面球的编号。抽象成图论，把每个球看作一个顶点，就是编号较小的顶点向编号较大的顶点连接边，条件是两个球可以相邻，即编号之和为完全平方数。每根柱子看做一条路径，N根柱子要覆盖掉所有点，一个解就是一个路径覆盖。
最小路径覆盖数随球的数量递增不递减，满足单调性，所以可以枚举答案（或二分答案），对于特定的答案求出最小路径覆盖数，一个可行解就是最小路径覆盖数等于N的答案，求出最大的可行解就是最优解。本问题更适合枚举答案而不是二分答案，因为如果顺序枚举答案，每次只需要在残量网络上增加新的节点和边，再增广一次即可。如果二分答案，就需要每次重新建图，大大增加了时间复杂度。
posted @
2011-03-08 21:42 小阮 阅读(585) |
评论 (0) |
编辑 收藏【1】质疑那些非const的引用参数；如果你想要的一个函数去修改其参数，请使用指针或者返回值；
【2】当你需要尽可能减少参数复制时，应用使用const引用参数；
【3】广泛而一致地使用const；
【4】避免宏
【5】避免不确定数目的参数；
【6】不要返回局部变量的指针或者引用；
【7】当一些函数对不同的类型执行概念上相同的工作时，请使用重载；
【8】在各种整数上重载时，通过提供函数去消除常见的歧义性；
【9】在考虑使用指向函数的指针时，请考虑虚函数或模板是不是更好的选择；
【10】如果你必须使用宏，请使用带有许多大写字幕的丑陋的名字。
posted @
2011-03-06 16:53 小阮 阅读(256) |
评论 (0) |
编辑 收藏
摘要: 题意：有向无环图中，需要多少条简单路可以覆盖整个图。建模：构造二分图。把原图的每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图的边(i, i)，连接(Xi, Yj)，值为1，然后把二分图最大匹配模型转化为网络留模型，求最大流。分析：
对于一个路径覆盖，有如下性质：
1、每个顶点属于且只属于一个路径。2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。
所以我们可...
阅读全文
posted @
2011-03-05 23:29 小阮 阅读(1750) |
评论 (0) |
编辑 收藏
摘要: 把每个实验看作二分图X集合中的顶点，每个设备看作二分图Y集合中的顶点，增加源S和汇T。1、从S向每个Xi连接一条容量为该点收入的有向边。2、从Yi向T连接一条容量为该点支出的有向边。3、如果一个实验i需要设备j，连接一条从Xi到Yj容量为无穷大的有向边。
统计出所有实验的收入只和Total，求网络最大流Maxflow，最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点...
阅读全文
posted @
2011-03-02 12:32 小阮 阅读(474) |
评论 (0) |
编辑 收藏
摘要: 题意：二分图最大匹配问题。解法1：匈牙利算法。解法2：最大流。添加原点s和汇点t。设二分图左边的点集为X，添加从s 到X（1,2,....,m ）的边，权值为1；右边的点集为Y，添加从Y（n-m+1, n-m+1, .... , n）到t 的边，权值为1；田间X和Y之间的边。求最大流。我用Dinic。最大流就是最大匹配。 配对保存在flow[i][j]中。
#include <f...
阅读全文
posted @
2011-02-24 12:35 小阮 阅读(750) |
评论 (0) |
编辑 收藏