题目意思是给你n个数,其中选取一些数使他们的和sum大于给定数M,求满足此条件的Min{M-sum},此题可以装化为01背包问题,刚开始可以把所有的数都加起来这时的sum一定大于M的,但此时的sum-M不一定是最小的,怎么才能得到最小的呢。可以这样想,令B=sum-M,要尽量在这B中减去一些原来加进去数,这样会使sum-M的差逐渐减小,这不就是01背包的模型吗,背包的容量为B,物品的价值与体积相同。尽量使其价值最大,那最后的到的差当然就是最小的。
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int N,H;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cows[25];
int f[1000001];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int inline max(int a, int b)
{
return a>b?a:b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int sum=0, i,j;
cin>>N>>H;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=N; ++i)
{
cin>>cows[i];
sum+=cows[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int m = sum - H;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
//ZeroOnePack(w[i], c[i])
for(j=m; j>=cows[i]; --j)
f[j]=max(f[j], f[j-cows[i]]+cows[i]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
cout<<m-f[m]<<endl;
return 0;
}
参考:http://hi.baidu.com/zhouxc07/blog/item/898a103c35b886ce9e3d6262.html
posted @
2010-12-08 11:21 小阮 阅读(250) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: ttwo
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)
ifstream fin;
ofstream fout;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 10000000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dx[] =
{ -1, 0, 1, 0 };
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dy[] =
{ 0, 1, 0, -1 };
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cd=0, cx, cy;
int fd=0, fx, fy;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int map[10][10];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j;
char ch;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin.open("ttwo.in");
fout.open("ttwo.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<10; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0; j<10; j++)
{
fin>>ch;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(ch=='*')
{
map[i][j]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else if(ch=='C')
{
cx=i, cy=j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else if(ch=='F')
{
fx=i, fy=j;
}
}
int step=0;
int x,y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(step!=MAX)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
// for cows
x = cx+dx[cd];
y = cy+dy[cd];
if(map[x][y]==1 || x<0 || x>9 || y<0 || y>9)
cd = (cd+1)%4;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
cx = x;
cy = y;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
// for farmer
x = fx+dx[fd];
y = fy+dy[fd];
if(map[x][y]==1 || x<0 || x>9 || y<0 || y>9)
fd = (fd+1)%4;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
fx = x;
fy = y;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
step++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//compare
if(cx==fx && cy==fy)
break;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(step == MAX)
fout<<0<<endl;
else
fout<<step<<endl;
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-12-08 11:18 小阮 阅读(216) |
评论 (0) |
编辑 收藏
唉..做得烂洗了..
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: concom
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <memory.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 101;
const int NCON = 100;
int N,x;
int a[MAX][MAX];
int c[MAX];
bool f[MAX];
ifstream fin;
ofstream fout;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dfs(int k)
{
f[k]=true;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i<=NCON; ++i)
{
c[i] += a[k][i];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!f[i] && c[i]>50)
{
dfs(i);
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void show()
{
for(int i=1; i<=NCON; ++i)
if(i!=x && c[i]>50)
fout<<x<<" "<<i<<endl;
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,p,k;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin.open("concom.in");
fout.open("concom.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k=0; k<N; k++)
{
fin>>i>>j>>p;
a[i][j]=p;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k=1; k<=NCON; ++k)
{
memset(f, 0, sizeof(f));
memset(c, 0, sizeof(c));
x=k;
dfs(k);
show();
}
return 0;
}
posted @
2010-12-07 21:28 小阮 阅读(483) |
评论 (0) |
编辑 收藏
很标准的01 背包问题
for(i=1; i<=N; ++i)
//ZeroOnePack( w[i], c[i])
for(j = V; j>= weight; j--)
f[j] = max( f[j], f[j-cost[i]]+w[i])
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int w[3500], d[3500];
int f[13000];
int N,M;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline int max(int a, int b)
{
return a>b? a: b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j;
cin>>N>>M;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
cin>>w[i]>>d[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
// ZeroOnePack(w[i], d[i])
for(j=M; j>=w[i]; j--)
f[j] = max(f[j], f[j-w[i]]+d[i]);
cout<<f[M]<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-12-07 16:05 小阮 阅读(158) |
评论 (0) |
编辑 收藏
01 背包问题.
f[i][j] 表示将前i个物品放入力矩为j的可行方案
f[i][j] = sum{ f[i-1][j-w[i][k] }
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int mid = 6000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int w[25],v[25];
int f[25][mid+mid];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int C,G;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,k;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
cin>>C>>G;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=C; ++i) cin>>v[i];
for(i=1; i<=G; ++i) cin>>w[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=C; ++i)
f[1][mid+v[i]*w[1]] = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=2; i<=G; ++i)
for(j=1; j<=C; ++j)
for(k=0; k<=2*mid; ++k)
if(f[i-1][k]>0)
f[i][k+w[i]*v[j]] += f[i-1][k];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
cout<<f[G][mid]<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-12-07 12:18 小阮 阅读(113) |
评论 (0) |
编辑 收藏
完全背包问题.
只是将完全背包问题的max 改为 sum
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: money
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 V = 30;
const int MAX = 10005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long long f[MAX];
int c[V];
int N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,n;
ifstream fin;
ofstream fout;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin.open("money.in");
fout.open("money.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>n>>N;
for(i=1; i<=n; ++i)
fin>>c[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
f[0]=1;
for(i=1; i<=n; ++i)
for(j=c[i]; j<=N; ++j)
f[j] = f[j] + f[j-c[i]];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<f[N]<<endl;
return 0;
}
posted @
2010-12-06 13:14 小阮 阅读(115) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: lamps
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int C = 4;
const int MAXN = 6;
const int MASK = (1<<MAXN)-1;
int loc[1<<MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n,c,t;
int open_mask, tot_mask;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int op[4] =
{ MASK,
MASK & 0xAA,
MASK & 0x55,
MASK & ( (1<<(MAXN-1)) | (1<<(MAXN-4)) )
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
FILE *fin, *fout;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void wirte(int lights)
{
int i;
char s[105];
for(i=0; i<n; ++i)
s[i] = ( lights & (1<<(MAXN-1-(i%MAXN))) ) ? '1': '0';
s[i]='\0';
fprintf(fout, "%s\n", s);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dfs(int lights, int i, int n)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(n==c)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if( (lights&tot_mask)==open_mask)
{
loc[lights]=1;
return;
}
}else
for( ; i<4; ++i)
dfs( lights^op[i], i+1, n+1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin = fopen("lamps.in", "r");
fout = fopen("lamps.out", "w");
assert(fin!=NULL && fout!=NULL);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fscanf(fin, "%d %d", &n, &c);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(;;)
{
fscanf(fin, "%d", &t);
if(t==-1) break;
t = MAXN-1-(t-1)%MAXN;
open_mask |= (1<<t);
tot_mask |= (1<<t);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(;;)
{
fscanf(fin, "%d", &t);
if(t==-1) break;
t = MAXN-1-(t-1)%MAXN;
tot_mask |= (1<<t);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(c>4)
{
if(c%2==0)
c=4;
else
c=3;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<=c; i+=2)
dfs(MASK, 0, i);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
bool flag=false;
for(i=0; i< (1<<MAXN); ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(loc[i])
{
flag = true;
wirte(i);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(!flag)
fprintf(fout, "IMPOSSIBLE\n");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2010-11-21 00:49 小阮 阅读(140) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: runround
LANG: C++
*/
#include <iostream>
#include <string.h>
#include <fstream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int N = 15;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool num_check(int n)
{
char num[N];
bool used[10];
int i, len;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(used, 0, sizeof(used));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sprintf(num, "%d", n);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
len=strlen(num);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<len; ++i)
if(used[num[i]-'0'] == true || num[i]=='0')
return false;
else
used[num[i]-'0'] = true;
return true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool round_check(int n)
{
char num[N];
bool f[N];
int steps, i, len;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(f, 0, sizeof(f));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sprintf(num, "%d", n);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
len=strlen(num);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
steps=0, i=0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(steps<len)
{
if(f[i]==true)
return false;
else
f[i] = true;
i = (i+num[i]-'0') % len;
steps++;
}
if(i==0)
return true;
else
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n,num;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream in("runround.in");
ofstream out("runround.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in>>n;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(num=n+1; ;num++)
if(num_check(num) && round_check(num))
break;
out<<num<<endl;
return 0;
}
posted @
2010-11-21 00:49 小阮 阅读(178) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: subset
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include<stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int N = 40;
const int MAX = (1+N)*N/4;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long long ans[N][MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n, tot, sum;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
freopen("subset.in", "r", stdin);
freopen("subset.out", "w", stdout);
scanf("%d", &n);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tot = (1+n)*n/2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(tot&0x01)
{
printf("0\n");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sum = tot/2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ans[1][0] = 1; ans[1][1] = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(int i=2; i<=n; ++i)
for(int j=0; j<=sum; ++j)
if(j-i>=0)
ans[i][j]=ans[i-1][j]+ans[i-1][j-i];
else
ans[i][j]=ans[i-1][j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%lld\n", ans[n][sum]/2);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2010-11-21 00:48 小阮 阅读(173) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: preface
LANG: C
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
static char *encode[] =
{
"", "I", "II", "III", "IV",
"V", "VI", "VII", "VIII", "IX",
};
char*
romandigit(int d, char *ivx)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
char *s, *p;
static char str[10];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(s=encode[d%10], p=str; *s; s++, p++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
switch(*s)
{
case 'I':
*p = ivx[0];
break;
case 'V':
*p = ivx[1];
break;
case 'X':
*p = ivx[2];
break;
}
}
*p = '\0';
return str;
}
char*
roman(int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
static char buf[20];
strcpy(buf, "");
strcat(buf, romandigit(n/1000, "M"));
strcat(buf, romandigit(n/100, "CDM"));
strcat(buf, romandigit(n/10, "XLC"));
strcat(buf, romandigit(n, "IVX"));
return buf;
}
int
main(void)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
FILE *fin, *fout;
int i, n;
char *s;
int count[256];
fin = fopen("preface.in", "r");
fout = fopen("preface.out", "w");
assert(fin != NULL && fout != NULL);
fscanf(fin, "%d", &n);
for(s="IVXLCDM"; *s; s++)
count[*s] = 0;
for(i=1; i<=n; i++)
for(s=roman(i); *s; s++)
count[*s]++;
for(s="IVXLCDM"; *s; s++)
if(count[*s])
fprintf(fout, "%c %d\n", *s, count[*s]);
return 0;
}
posted @
2010-11-21 00:47 小阮 阅读(149) |
评论 (0) |
编辑 收藏