练习 7.11
写一个error函数,它取一个printf风格的包含%s、%c和%d指示符的格式串, 以及任意多个其他参数。请不要使用printf()。
解:
对于变动长度参数表的处理通过一些很像对待器的设施完成,这类设施的类型为va_list。宏va_start对这类设施进行初始化,还必须用宏va_end指明这种设施不会再用。要取得当前参数的值并将该设施移到下一个参数, 需要用va_arg。参数表的结束必须能从至今已经看到的实际参数确定(典型情况下,函数从没有省略号表示的某个常规参数哪里获得有关信息。)
#include <cassert>
#include <cstdarg>
#include <iostream>
#include <stdexcept>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
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
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
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 小阮 阅读(326) |
评论 (0) |
编辑 收藏
模拟
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei
TASK: spiral
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXN = 800;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
const int dx[]=
{0,1,0,-1};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
const int dy[]=
{1,0,-1,0};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin("spiral.in");
ofstream fout("spiral.out");
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int m[MAXN][MAXN];
int N,M;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i, j, x=1, y=1, dir=0;
fin>>N;
M = N*N;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=M; ++i)
{
m[x][y]=i;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int tx = x + dx[dir];
int ty = y + dy[dir];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(m[tx][ty] || tx>N || ty>N || tx<1 || ty<1)
{
dir++;
if(dir==4)dir=0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
x += dx[dir];
y += dy[dir];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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 小阮 阅读(384) |
评论 (0) |
编辑 收藏
最长递增子序列问题。
O(n^2)
DP。 练练手
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 1005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int A[MAX],F[MAX];
int N, ans=-1;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j;
scanf("%d", &N);
for(i=1; i<=N; ++i)
scanf("%d", &A[i]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d\n", ans);
return 0;
}
O(nlgn)
开一个栈,每次取栈顶元素top和读到的元素temp做比较,如果temp > top 则将temp入栈;如果temp < top则二分查找栈中的比temp大的第1个数,并用temp替换它。 最长序列长度即为栈的大小top。
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 1005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int stack[MAX];
int N, ans=-1;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i, tmp, top;
scanf("%d", &N);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
stack[top=0]=-1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=N; ++i)
{
scanf("%d", &tmp);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(tmp>stack[top])
{
stack[++top] = tmp;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
int low=1, high=top;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(low<=high)
{
int mid=(low+high)/2;
if(tmp>stack[mid])
low = mid+1;
else
high = mid-1;
}
stack[low]=tmp;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d\n", top);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2011-03-10 11:21 小阮 阅读(235) |
评论 (0) |
编辑 收藏
题意:
Q1:LIS,最长长度为s
Q2:有多少个长度为s的子序列
Q3:若A[1]和A[n]可多次使用,问可以取多少个s长度的子序列
建模:
Q1:LIS,DP, F[i]表示以第i位为开头的最长上升序列的长度,求出最长上升序列长度K
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
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 小阮 阅读(608) |
评论 (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 小阮 阅读(444) |
评论 (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 小阮 阅读(582) |
评论 (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 小阮 阅读(1693) |
评论 (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 小阮 阅读(473) |
评论 (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 小阮 阅读(747) |
评论 (0) |
编辑 收藏