摘要: 判断点q是否在多边形内的一种方法,过q作水平射线L, 如果L与多边形P的边界不相交,则q在P的外部。否则, L和P的边界相交,具体地说,交点个数为奇(偶)数时,点q在P的内(外)部。(参考 计算几何P19 )
/**//*判断点q是否在多边形内的一种方法,过q作水平射线L,如果L与多边形P的边界不相交,则q在P的外部。否则,L和P的边界相交,具体地说,...
阅读全文
posted @
2011-02-06 22:55 小阮 阅读(343) |
评论 (0) |
编辑 收藏
凸包入门题目, 我用的是O(nlgn)的graham算法, 该算法的原理可以参照算法导论相关章节
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: fc
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int STACKSIZE = 1000;
const int MAXN = 10001;
const int INF = 0x7FFFFFFF;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Point
{
double x,y;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin("fc.in");
ofstream fout("fc.out");
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Point p0, points[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
double cross(Point &p1s, Point &p1e, Point &p2s, Point &p2e)
{
double x1 = p1e.x - p1s.x;
double y1 = p1e.y - p1s.y;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
double x2 = p2e.x - p2s.x;
double y2 = p2e.y - p2s.y;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return x1*y2-x2*y1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
double dis(Point &p1, Point &p2)
{
return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int cmp(const void *A, const void *B)
{
Point *p1 = (Point*)A;
Point *p2 = (Point*)B;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
double res = cross(p0, *p1, p0, *p2);
if(res>0)
return -1;
else if(res==0 && dis(p0,*p1) > dis(p0, *p2))
return -1;
else
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void input()
{
int loc=0;
double minx = INF, miny = INF;
fin>>n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<n; ++i)
{
fin>>points[i].x >>points[i].y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(points[i].y < miny)
{
miny = points[i].y;
minx = points[i].x;
p0 = points[i];
loc = i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else if(points[i].y == miny)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(points[i].x < minx)
{
miny = points[i].y;
minx = points[i].x;
p0 = points[i];
loc = i;
}
}
}
points[loc] = points[--n];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort(points, n, sizeof(Point), cmp);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Point stack[STACKSIZE];
int top;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void graham()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
stack[++top] = p0;
stack[++top] = points[0];
stack[++top] = points[1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=2; i<n; ++i)
{
while(cross(stack[top], points[i], stack[top], stack[top-1])<0 )
top--;
stack[++top] = points[i];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double ans=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void output()
{
int tmp = top;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(tmp!=1)
{
ans += dis(stack[tmp], stack[tmp-1]);
tmp--;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ans += dis(p0, stack[top]);
fout.setf(ios::fixed);
fout.precision(2);
fout<<ans<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](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)
input();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
graham();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
output();
![](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 @
2011-02-05 22:16 小阮 阅读(177) |
评论 (0) |
编辑 收藏
摘要: 根据题意,每个矩形总能找到他的四个角的坐标,先找出各个矩形,再遍历每个矩形的四条边,例如:若在遍历矩形A的四条边时候,遇到B。则图中存在边A->B如此建立边的关系之后即刻拓扑排序。最后对结果进行排序。PS:结果数量比较大。
/**//*ID: lorelei3TASK: frameupLANG: C++*/#include <fstream&g...
阅读全文
posted @
2011-02-04 16:48 小阮 阅读(349) |
评论 (0) |
编辑 收藏
根据最大流最小割定理,最大流的值flow就等于最小割的流量。
求最小割的边集:枚举每条边,该边的值为t, 从图中去掉这条边,然后求最大流maxt。
如果 maxt + t = flow 则这条边属于最小割的边集,flow -= t 。继续枚举。
另外,为了构造解,我记录了输入的顺序并对边的大小和答案进行了排序。 我看到有些牛人的题解不需要排序,学习中。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: milk6
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <queue>
#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 MAXM = 1005;
const int MAXN = 33;
const int INF = 0x7FFFFFFF;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin("milk6.in");
ofstream fout("milk6.out");
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Edge
{
int index, s, t;
long cost ;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool operator < ( const Edge &e)const
{
return (cost>e.cost) || (cost==e.cost && index<e.index );
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n,m;
int cnt;
Edge edges[MAXM];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long c[MAXN][MAXN];
long tmp[MAXN][MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void input()
{
fin>>n>>m;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i<=m; ++i)
{
edges[i].index=i;
fin>>edges[i].s>>edges[i].t>>edges[i].cost;
c[edges[i].s][edges[i].t] += edges[i].cost;
}
memcpy(tmp, c, sizeof( long)*MAXN*MAXN);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long pre[MAXN], delta[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool bfs(int s, int t)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
queue<int> Q;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(pre, 0, sizeof(pre));
memset(delta, 0, sizeof(delta));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
delta[s]=INF;
Q.push(s);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(!Q.empty())
{
int cur = Q.front();
Q.pop();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i<=n; ++i)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(delta[i]==0 && c[cur][i]>0 )
{
delta[i] = delta[cur]<c[cur][i] ? delta[cur] : c[cur][i];
pre[i] = cur;
Q.push(i);
}
}
}
if(delta[t]==0)
return false;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
long edmonds_karp(int s, int t)
{
long ans=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(bfs(s,t))
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=t; i!=s; i=pre[i])
{
c[pre[i]][i] -= delta[t];
c[i][pre[i]] += delta[t];
}
ans += delta[t];
}
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int tot;
int ans[MAXM];
long maxflow, flow;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void solve()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sort(edges+1, edges+m+1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
flow = edmonds_karp(1, n);
maxflow = flow;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i<=m; ++i)
{
long t = edges[i].cost;
memcpy(c, tmp, sizeof( long)*MAXN*MAXN);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
c[edges[i].s][edges[i].t] -= edges[i].cost;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
long maxt = edmonds_karp(1, n);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(maxt+t == flow)
{
ans[tot++] = edges[i].index;
flow -= edges[i].cost;
tmp[edges[i].s][edges[i].t] -= edges[i].cost;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void output()
{
fout<<maxflow<<" "<<tot<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sort(ans, ans+tot);
for(int i=0; i<tot; ++i)
fout<<ans[i]<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](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)
input();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
solve();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
output();
![](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 @
2011-02-02 13:57 小阮 阅读(803) |
评论 (0) |
编辑 收藏
一开始想到暴搜,但是状态太多,肯定TLE。
了USACO上给出构造法求解:
3
3 5 6 4 2 1 3 5 7 6 4 2 3 5 4
2 1 -2 -2 -1 2 2 2 -1 -2 -2 1 2 -1
4
4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5
2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1
5
5 7 8 6 4 3 5 7 9 10 8 6 4 2 1 3 5 7 9 11 10 8 6 4 2 3 5 7 9 8 6 4 5 7 6
2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1
6
6 8 9 7 5 4 6 8 10 11 9 7 5 3 2 4 6 8 10 12 13 11 9 7 5 3 1 2 4 6 8 10 12 11 9 7 5 3 4 6 8 10 9 7 5 6 8 7
2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 1 -2 -2 -2 -2 -2 -2 1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1
规律很明显。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: shuttle
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 MAX = 500;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
int two=2, one=1;
int a[MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool flag = true;
![](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)
ifstream fin("shuttle.in");
ofstream fout("shuttle.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>n;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int loc=0, k=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(k!=0)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(k==n)
{
flag=false;
one = -one;
}
int t=k;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(t!=0)
{
a[loc++] = two;
t--;
}
a[loc++]=one;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
two = -two;
one = -one;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(k<n && flag)
k++;
else
k--;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int res=n;
fout<<n<<" ";
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0, cnt=2; i<loc-1; ++i,++cnt)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(cnt==20)
{
fout<<(res+=a[i])<<endl;
cnt=0;
}
else
fout<<(res+=a[i])<<" ";
}
res+=a[loc-1];
fout<<res<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2011-01-30 22:11 小阮 阅读(377) |
评论 (0) |
编辑 收藏
摘要: 对ditch里边的单词进行枚举, 需要预处理, 过滤掉不符合题意的单词.
/**//*ID: lorelei3TASK: lgameLANG: C++*/#include <fstream>#include <string>#include <memory.h>using namespace...
阅读全文
posted @
2011-01-30 11:23 小阮 阅读(193) |
评论 (0) |
编辑 收藏
第一问, 枚举地拿掉每个点u,看能否连通(dfs 到n),能连通的就是必需经过的点,对于点u 进行DFS,看会不会重复经过第一问中已经访问过的点,若都没有经过,则该u点符合第二问。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: race3
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 = 55;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin("race3.in");
ofstream fout("race3.out");
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int map[MAX][MAX];
int visited[MAX], ans1[MAX], ans2[MAX], cnt1, cnt2, n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void input()
{
int i=0, in=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(fin>>in && in!=-2)
{
int t=in;
int c = ++map[i][0];
map[i][c]=t;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(fin>>t && t!=-2)
{
int c = ++map[i][0];
map[i][c]=t;
}
i++;
}
fin>>in;
n=i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool dfs1(int u)
{
if(u==n)
return true;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i<=map[u][0]; ++i)
{
int v = map[u][i];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(visited[v]==0)
{
visited[v]=1;
if(dfs1(v))
return true;
}
}
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool rep;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dfs2(int u)
{
if(rep)
return;
if(visited[u]==2)
return;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
visited[u]=2;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i<=map[u][0]; ++i)
{
int v = map[u][i];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(visited[v]==1)
{
rep=true;
return;
}
dfs2(v);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void solve()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i<n; ++i)
{
memset(visited, 0, sizeof(visited));
visited[i]=1;
visited[0]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!dfs1(0))
{
ans1[cnt1++] = i;
rep = false;
dfs2(i);
if(rep == false)
ans2[cnt2++] = i;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void output()
{
int i;
fout<<cnt1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(cnt1!=0)
{
fout<<" ";
for(i=0; i<cnt1-1; ++i)
fout<<ans1[i]<<" ";
fout<<ans1[cnt1-1];
}
fout<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<cnt2;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(cnt2!=0)
{
fout<<" ";
for(i=0; i<cnt2-1; ++i)
fout<<ans2[i]<<" ";
fout<<ans2[cnt2-1];
}
fout<<endl;
}
![](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)
input();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
solve();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
output();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2011-01-29 20:01 小阮 阅读(343) |
评论 (0) |
编辑 收藏
摘要: 做了一天. AC的速度还可以, 时间最长的 0.16s.1. 开始做之前,要确定下搜索顺序, 这个很关键. &...
阅读全文
posted @
2011-01-29 00:07 小阮 阅读(676) |
评论 (0) |
编辑 收藏
第一问,求最长下降子序列长度。
设a表示数据,len(i)=前i个数中最长下降子序列长度,状态转移方程 len (i)=max{len(j)+1}(j<i,a[j]>a[i]), 初始化f[i]=1 (i=0...n-1);
第二问:
对于c[i]=前i个数中最长下降子序列的个数,状态转移方程 c[i]=sigma(c[j]) (j<i,a[j]>a[i], len[i]==len[j]+1)
对于重复情况, 每一个可能重复的下降的子序列,它一定是a , b, b (a>b)的情况,开一个数组visited记录b是否出现过,若出现了,就不再计算。
状态转移方程: c[i]=sigma(c[j]) (j<i,a[j]>a[i], len[i]==len[j]+1),visited[j]=false)。
最后是高精度加法,我的版本是每一位存一个数,有待改进。
PS:这次代码风格有点变化。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: buylow
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 MAXN = 5000;
const int MAXP = 50;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class HPNum
{
public:
int length;
int num[MAXP];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
HPNum()
{
length=1;
memset(num,0,sizeof(num));
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void plus(HPNum &p)
{
int len = length>p.length ? length : p.length;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<len; ++i)
{
num[i] = num[i]+p.num[i];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(num[i]>=10)
{
num[i]-=10;
num[i+1]++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
if(num[len]>0)
len++;
length=len;
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
long maxlen;
long a[MAXN], len[MAXN];
bool visited[20000];
HPNum c[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin("buylow.in");
ofstream fout("buylow.out");
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void input()
{
fin>>n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<n; ++i)
{
fin>>a[i];
len[i]=1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dp()
{
int i,j;
maxlen=1;
for(i=1; i<n; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=i-1; j>=0; --j)
{
if(a[i]<a[j] && len[i]<len[j]+1)
len[i] = len[j]+1;
if(maxlen<len[i])
maxlen = len[i];
}
for(i=0; i<n; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(len[i]==1)
{
c[i].length=1;
c[i].num[0]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
memset(visited, false, sizeof(visited));
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=i-1; j>=0; --j)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(len[i]==len[j]+1 && !visited[a[j]] && a[i]<a[j])
{
c[i].plus(c[j]);
visited[a[j]]=true;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void output()
{
int i;
HPNum sum;
sum.length=1;
sum.num[0]=0;
memset(visited, false, sizeof(visited));
for(i=n-1; i>=0; --i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(len[i]==maxlen && !visited[a[i]])
{
sum.plus(c[i]);
visited[a[i]]=true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<maxlen<<" ";
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=sum.length-1; i>=0; --i)
fout<<sum.num[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<endl;
}
![](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)
input();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dp();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
output();
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2011-01-27 00:59 小阮 阅读(444) |
评论 (0) |
编辑 收藏
参考了USACO上的提示:
1. 最大传动比率至少是最小的3倍。这个其实不用算出比率再判断,只要不满足s1[F]/s2[1]-s1[1]/s2[R]>=3的都剪掉 .
2. 用memcpy函数会更快.
3. 用插入排序对于规模较小的数据速度比较客观.
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: cowcycle
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 = 100;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int F, R, F1, F2, R1, R2;
int s1[MAX], s2[MAX];
int ans1[MAX], ans2[MAX];
double rate[MAX*MAX], diff[MAX*MAX];
double minf = 0x7FFFFFFF;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void count()
{
int i,j,k=0;
double sum1=0, sum2=0, t=0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=F; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=1; j<=R; ++j)
{
t = (double)s1[i]/s2[j];
int p=++k;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(rate[p-1]>=t)
{
rate[p] = rate[p-1];
p--;
}
rate[p] = t;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int cnt = F*R;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=cnt-1; ++i)
{
diff[i] = rate[i+1] - rate[i];
sum1 += diff[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
double mean = sum1/(cnt-1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=cnt-1; ++i)
sum2+=(diff[i]-mean)*(diff[i]-mean);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
double var = sum2/cnt-1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(var<minf)
{
minf = var;
memcpy(ans1+1, s1+1, sizeof(int)*F);
memcpy(ans2+1, s2+1, sizeof(int)*R);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dfs2(int k, int w)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(k==R+1)
{
if(s1[F]*s2[R]<3*(s1[1]*s2[1]) )
return;
count();
return;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=w; i<=R2-(R-k); ++i)
{
s2[k]=i;
dfs2(k+1, i+1);
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dfs1(int k, int w)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(k==F+1)
{
dfs2(1, R1);
return;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=w; i<=F2-(F-k); ++i)
{
s1[k]=i;
dfs1(k+1, i+1);
}
}
}
![](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)
ifstream fin("cowcycle.in");
ofstream fout("cowcycle.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>F>>R>>F1>>F2>>R1>>R2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dfs1(1,F1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
for(i=1; i<=F-1; ++i)
fout<<ans1[i]<<" ";
fout<<ans1[F]<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=R-1; ++i)
fout<<ans2[i]<<" ";
fout<<ans2[R]<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2011-01-26 12:03 小阮 阅读(237) |
评论 (0) |
编辑 收藏