位运算,
输入一位, 先用B 位的掩码mask之, 得到str , 对str从A位到B位mask之, 再最前头加个1, 以免忽略前导0, 然后hash..
sort一下, 再输出..
输出很ws...小心...写得很烂...
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: contact
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <algorithm>
#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 = 200005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
typedef struct Sequence
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Sequence():cnt(0),value(0)
{}
int cnt, value;
}Seq;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Seq hash[MAX];
char str[MAX];
int A,B,p,N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin;
ofstream fout;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int cmp(const Seq &a , const Seq &b)
{
return a.cnt>b.cnt || (a.cnt==b.cnt&&a.value<b.value);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void my_print_bin(int value)
{
int tmp[100], cnt=0;
memset(tmp, 0 , sizeof(tmp));
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
do
{
tmp[cnt++] = value & 1;
value>>=1;
}while(value);
for(int i=cnt-2; i>=0; i--)
fout<<tmp[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i, j;
unsigned mask, mask1, mask2;
unsigned int str=0, c;
char ch;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin.open("contact.in");
fout.open("contact.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>A>>B>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin.get(ch);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
mask = (1<<B)-1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(fin.get(ch))
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(ch=='0' || ch=='1')
{
p++;
c = ch-'0';
str = ((str<<1)+c)&mask;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=A; i<=B&&i<=p; ++i)
{
mask1 = (1<<i)-1;
mask2 = mask1+1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
unsigned int t = (str&mask1)|mask2;
hash[t].cnt++;
hash[t].value= t;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sort(hash, hash+MAX, cmp);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int tc=-1;
char* seq=" ";
bool flag = false;
i=0,j=0;
int count=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(true)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(hash[j].cnt == tc)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(count==6)
{
seq="\n";
count=0;
}
fout<<seq;
my_print_bin(hash[j].value);
seq=" ";
count++;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
if(flag)
fout<<endl;
if(hash[j].cnt==0 || ++i>N)
break;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<hash[j].cnt<<endl;
my_print_bin(hash[j].value);
count = 1;
tc=hash[j].cnt;
flag =true;
}
j++;
};
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-12-18 15:52 小阮 阅读(268) |
评论 (0) |
编辑 收藏
上浮法 + 矩阵分割
以逆序来进行放置,即n to 1。逆序的好处在于放置一个矩形后,俯视看到的就是最终俯视该矩形应该看到的。因为挡着它的矩形在之前已经放置好了,所以可直接统计,为递归创造了条件。每放一个矩形,可以想象成将其扔入一密度很大的海水底部,海分成了n层,然后矩形开始向上浮。在上浮过程中若碰撞到其他的矩形则断裂成几个小矩形,继续上浮,直到浮出水面。于是想到用个递归来模拟上浮过程。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: rect1
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 10010;
const int MAXC = 2510;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int N;
int x1[MAX], y1[MAX], x2[MAX], y2[MAX], color[MAXC], area[MAXC];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void cover(int lx, int ly, int rx, int ry, int c, int k)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(k<=N &&( lx >= x2[k] ||
rx <= x1[k] ||
ly >= y2[k] ||
ry <= y1[k] ))
k++;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(k>N)
{ area[c] += (ry-ly) * (rx-lx); return; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(lx<x1[k])
{ cover(lx, ly, x1[k], ry, c, k+1); lx=x1[k]; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(rx>x2[k])
{ cover(x2[k], ly, rx, ry, c, k+1); rx=x2[k]; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(ly<y1[k])
{ cover(lx, ly, rx, y1[k], c, k+1); ly=y1[k]; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(ry>y2[k])
{ cover(lx, y2[k], rx, ry, c, k+1); ry=y2[k]; }
}
![](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 i;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("rect1.in");
ofstream fout("rect1.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>x2[0]>>y2[0]>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
x1[0]=0;
y1[0]=0;
color[0]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
fin>>x1[i]>>y1[i]>>x2[i]>>y2[i]>>color[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=N; i>=0; i--)
cover(x1[i], y1[i], x2[i], y2[i], color[i], i+1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<MAXC; ++i)
if(area[i])
fout<<i<<" "<<area[i]<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2010-12-16 15:41 小阮 阅读(211) |
评论 (0) |
编辑 收藏
看了官方题解才略懂....囧..
我们在数组hum中计算出前n个丑数。为了实现起来更简单,我们把1也作为一个丑数,算法也要因此略微调整一下。
当我们已知前k个丑数,想得到第k+1个,我们可以这样做:
对于每个质数p 寻找最小的丑数h 使得 h * p 比上一个丑数大
取我们找到的 h * p 中最小的一个:它就是下一个丑数为了使搜索更快,我们可以为每个质数维护一个索引“pindex”表示每个质数已经乘到了哪个丑数,每次都从那里开始,而不是再从头再来。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: humble
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 100000;
const int INF = 0x7FFFFFFF;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int prim[MAX], pindex[MAX];
long hum[MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int K,N,n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,min,minp;
ifstream fin("humble.in");
ofstream fout("humble.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>K>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<K; ++i)
fin>>prim[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
hum[n++]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(n<N+1)
{
min = INF; minp=-1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; i<K; ++i)
{
while((double)prim[i]*hum[pindex[i]] <= hum[n-1])
pindex[i]++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if((double)prim[i]*hum[pindex[i]] < min)
{
min = prim[i]*hum[pindex[i]];
minp = i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
hum[n++] = min;
pindex[minp]++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<hum[N]<<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-15 11:23 小阮 阅读(447) |
评论 (0) |
编辑 收藏
标准的完全背包问题。练练手吧。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: inflate
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)
int f[10005], mark[10005], cost[10005];
int N,V;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("inflate.in");
ofstream fout("inflate.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>V>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
fin>>mark[i]>>cost[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
//complete pack
for(j=cost[i]; j<=V; ++j)
if(f[j]<f[j-cost[i]]+mark[i])
f[j] = f[j-cost[i]]+mark[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<f[V]<<endl;
return 0;
}
posted @
2010-12-14 20:41 小阮 阅读(197) |
评论 (0) |
编辑 收藏
标准的最小生成树问题. Prim, kruskal 均可.
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: agrinet
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 105;
const int INF = 100000000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int g[MAX][MAX];
int lowcost[MAX], s[MAX];
int ans, n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void prim(int n)
{
int i,j,k,min;
ans = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<n; ++i)
lowcost[i] = g[0][i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
s[0]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; i<n-1; ++i)
{
min = INF;
j=0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(k=1; k<n; ++k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!s[k]&&lowcost[k]<min)
{
min=lowcost[k];
j=k;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ans+=min;
s[j]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(k=1; k<n; ++k)
if(!s[k] && j!=k && g[j][k]<lowcost[k])
lowcost[k]= g[j][k];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("agrinet.in");
ofstream fout("agrinet.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(i=0; i<n; ++i)
{
lowcost[i] = INF;
s[i]=0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<n; ++i)
for(j=0; j<n; ++j)
fin>>g[i][j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
prim(n);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<ans<<endl;
return 0;
}
posted @
2010-12-14 16:49 小阮 阅读(392) |
评论 (0) |
编辑 收藏
长除法, 当发现余数一样时候, 出现循环.
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: fracdec
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <iostream>
#include <string.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 100000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char ans[MAX],ch[MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
typedef struct Num
{
bool flag;
int index;
}Num;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Num f[MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int a,b,c,i,j,k, start, stop;
bool p=false;;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k=0; k<MAX;++k)
{
f[k].flag = false;
f[k].index = -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("fracdec.in");
ofstream fout("fracdec.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>a>>b;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
c = a/b;
a = a%b;
sprintf(ans, "%d.", c);
f[a].flag=true;
f[a].index=0;
int len = strlen(ans);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
k=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(true)
{
a*=10;
c=a/b;
a=a%b;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ch[k] = (char)('0'+c);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(a==0)
{
p=true;
break;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(f[a].flag==true)
{
start = f[a].index;
stop = k;
break;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
f[a].flag = true;
f[a].index = k+1;
k++;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(p)
{
strcat(ans, ch);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
for(i=0, j=len; i<start; ++i, ++j)
ans[j] = ch[i];
ans[j++]='(';
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=start; i<=stop; ++i, ++j)
ans[j] = ch[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ans[j++]=')';
ans[j]='\0';
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
bool con = true;
i=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(con)
{
k=76;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(k--)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(ans[i]=='\0')
{
con=false;
break;
}
else
fout<<ans[i++];
}
fout<<endl;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2010-12-14 14:43 小阮 阅读(205) |
评论 (0) |
编辑 收藏
SPFA, Dijkstra, Floyd 都可以.
注意两点之间有重边, 所以要选择最小的.
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: comehome
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <queue>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 256;
const int INF = 999999999;
int map[MAX][MAX];
int dist[MAX];
bool isInQ[MAX],f[MAX];
int N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline bool relax(int u, int v)
{
int len = dist[u]+map[u][v];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(len<dist[v])
{
dist[v] = len;
return true;
}
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void spfa()
{
queue<int> Q;
int be = 'Z',t=0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dist[be]=0;
map[be][be]=0;
Q.push(be);
isInQ[be]=true;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(!Q.empty())
{
int u = Q.front();
Q.pop();
isInQ[u]=false;
for(int v=0; v<MAX; ++v)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(relax(u, v) && !isInQ[v])
{
Q.push(v);
isInQ[v]=true;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,v,ans=INF, loc=0;
char ch1,ch2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("comehome.in");
ofstream fout("comehome.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; i<MAX; ++i)
{
for(j=0; j<MAX; ++j)
map[i][j]=INF;
dist[i] = INF;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](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(i=0; i<N; ++i)
{
fin>>ch1>>ch2>>v;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(v<map[ch1][ch2])
{
map[ch1][ch2]=v;
map[ch2][ch1]=v;
}
if(ch1>='A' && ch1<'Z')
f[ch1]=true;
if(ch2>='A' && ch2<'Z')
f[ch2]=true;
}
spfa();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<MAX; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(dist[i]<ans && f[i] )
{
ans = dist[i];
loc= i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<(char)loc<<' '<<ans<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2010-12-10 21:23 小阮 阅读(317) |
评论 (0) |
编辑 收藏
先用floyd 求两点之间的最短距离map[i][j] ,再求各点与牧区内其他结点距离的最大值d[i]。
枚举分别在两个牧区的两个点i,j,
tmp = d[i] + d[j] + ( i, j 之前的距离)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei
TASK: cowtour
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <memory.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const double INF = 999999.0;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef pair<int, int> PAIR;
PAIR loc[200];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double map[200][200];
double d[200];
int N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline double dist(int x1, int y1, int x2, int y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,k;
double ans= INF;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("cowtour.in");
ofstream fout("cowtour.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<N; ++i)
fin>>loc[i].first>>loc[i].second;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
char ch;
for(i=0; i<N; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0; j<N; ++j)
{
fin>>ch;
if(ch=='1')
map[i][j] = map[j][i] = dist(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
else if(ch=='0')
map[i][j] = map[i][j] = INF;
if(i==j)
map[i][j] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(k=0; k<N; ++k)
for(i=0; i<N; ++i)
for(j=0; j<N; ++j)
if(map[i][j] > map[i][k]+map[k][j])
map[i][j] = map[i][k]+map[k][j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(d, 0, sizeof(d));
for(i=0; i<N; ++i)
for(j=0; j<N; j++)
if(map[i][j]>d[i] && map[i][j]!=INF)
d[i] = map[i][j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<N; ++i)
for(j=0; j<N; ++j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[i][j]==INF)
{
double tmp = d[i]+d[j]+dist(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
if(tmp<ans)
ans = tmp;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<N; ++i)
if(d[i]>ans)
ans = d[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<setprecision(6)<<setiosflags(ios::fixed | ios::showpoint)<<ans<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2010-12-10 19:49 小阮 阅读(183) |
评论 (0) |
编辑 收藏
摘要: floodfill
/**//*ID: lorelei3TASK: maze1LANG: C++*/#include<stdio.h> const int dx1[4] = {1, -1, 0, 0}; const int dy1[4] ...
阅读全文
posted @
2010-12-09 22:42 小阮 阅读(402) |
评论 (0) |
编辑 收藏
1. 在三角形的周长l一定时,最长边c的取值范围是l/3≤c<l/2
2. 用01背包枚举两条边.
#include <iostream>
#include <cmath>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool f[1000][1000];
int len[50];
int N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
double area(int a, int b, int c)
{
double p = (a+b+c)/2.0;
return sqrt(p*(p-a)*(p-b)*(p-c));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,k,sum=0;
double ans = 0.0 ;//,tmp=0.0;
cin>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=N; ++i)
{
cin>>len[i];
sum+=len[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int max = sum/2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
f[0][0]=true;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
for(j=max; j>=0; j--)
for(k=max; k>=0; k--)
f[j][k] = f[j][k] | (j>=len[i]&&f[j-len[i]][k]) |(k>=len[i]&&f[j][k-len[i]]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=max; ++i)
for(j=1; j<=max; ++j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(f[i][j])
{
k = sum-i-j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if( (i+j>k) && (i+k>j) && (k+j>i) )
{
double tmp = area(i,j,k);
if(tmp>ans)
ans = tmp;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(ans == 0.0)
cout<<-1<<endl;
else
cout<<(int)(ans*100)<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//system("pause");
return 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
posted @
2010-12-09 11:07 小阮 阅读(345) |
评论 (1) |
编辑 收藏