SRM 454 DIV 1 Level 2

就是说用火柴来表示数。。给你一个18位以下的10进制数。。
最多移动K根火柴。。求出能形成多少不同的数。。
dp啊。。
F[i][plus][minus]表示前i个中,移进plus根火柴,移开minus根火柴,有几种不同的数。。
然后预处理或者直接手打出火柴两两之间的移动关系( 有人就是手打的)。。
就可以方便的DP了。。
关键就是这个状态是3维的。。一开始我一直以为是2维的。。想了半天也没结果。。
答案就是Sum{F[n][i][i]|0<=i<=K}。。
感觉就是这道题如果从记忆化搜索的角度来想比较方便。。现在我发现记忆化搜索在很多时候比子问题重叠的思考方法要重要多了。。

TopCoder SRM 4XX DIV 2 Level 3

忘了是SRM几了。。不过是道好题啊。。
已知三个整数x,y,z。。给出它们的上下界。。求出x*y=z的三元组有几个。。
由于上下界是10^10次方的。。暴力枚举x和y的话是10^20。。只能去死。。
如果枚举z。。然后可以根据y的上下界得出满足条件的x的上下界。。再与真实的x上下界求交。。
是10^10。。还是太慢了。。。
想了N久。。最后灵机一动。。
核心就是要降低枚举的复杂度。。注意到下界可以通过减法原理消掉。。那么只需要考虑上界。。
问题就变成了:
 x,y,z>=1
x<=maxx
y<=maxy
x*y=z<=maxz
关键就是如果x*y<=maxz的话,那么x和y必然有一个小于根号z。。
首先枚举x小于根号z的情况,然后枚举y小于根号z求x大于跟号z的情况(防止重复)。10^5。。问题就解决了。。
忘了是SRM几了。。找不到代码了。。

悲剧了。。

这次USACO的月赛比的很悲剧。。第一题代码搞错了一行结果全WA。。
第二题少了几个判断结果N个点seg error了。。
第3个最简单的我全WA光。。结果发现是线段树写错了。。
啊啊啊。。BS我自己啊。。太ZB了。。

为什么会悲剧呢?题目我都会做啊,感觉跟NOIP的时候是一个道理,知道怎么做跟打出来让它做完全是两码事,脑子里面有算法一点用都没有,码不出来照样悲剧,就像NOIP的时候我全悲剧在那个强连通上了。。根本没写过几遍偏偏要去写。。绝对是ZB的表现。。这就是一个教训就是不熟的代码千万别打。。哪怕损点分也无所谓。。NOIP的时候如果不打强连通还可以DP出50分。。然后就有大把的时间去A第4题。。说不定就喜剧了。。总之也是一个抉择啦。。如果对自己不是非常有自信。。还是先做有把握的题目吧。。。像这次我第二题写的快疯掉。。我估计就肯定对不了。。果然悲剧的要死。。还不如把第一题再调试调试。。然后第三题也可以检查出错误。。然后就又喜剧了。。

总而言之言而总之呢。。我得记住永远不要相信自己能A完所有的题而太苛求一道题。。人要清醒。。能拿多少是多少。。

SRM 449 DIV 1 Level 1

 就是说一个三角形。。2条边长的平方分别为A和B。。都小于2*10^9 并且这个三角形三个顶点的坐标都是整数。。求最大可能的面积或者没有这样的三角形返回-1.。
首先变长知道了。。那么这个三角形的夹角越接近90越好。。那么只要算出所有可能的角度然后扫描过去就可以了。。。
好烦啊。。程序很长很猥琐。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack> a
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long ll;
const int maxn=2000000000;
vector<ll> S;
void predo()
{
for(ll i=0;i*i<maxn;i++)
S.push_back(i*i);
}
int inS(int x)
{
int i=lower_bound(S.begin(),S.end(),x)-S.begin();
if(S[i]==x) return i;
return -1;
}
class MaxTriangle
{
vector<double> put(int A)
{
vector<double>res;
double p=acos(0);
for(int i=0;i<S.size()&&S[i]<=A;i++)
{
int B=A-S[i];
int t=inS(B);if(t==-1) continue;
double a=atan2(i,t);
res.push_back(a);
res.push_back(a+p);
}
return res;
}
public:
double calculateArea(int A, int B)
{
predo();double p=acos(0);
vector<double> a=put(A),b=put(B);
sort(a.begin(),a.end());sort(b.begin(),b.end());
if(a.size()==0||b.size()==0) return -1;
double best=0;
for(int j=0,i=0;i<a.size()&&a[i]<=p;i++)
{
while(b[j]-a[i]<p&&j!=b.size()-1)j++;
double q=b[j]-a[i];
if(abs(q-p)<abs(best-p)) best=q;
if(j)j–;
if(abs(q-p)<abs(best-p)) best=q;
}
return sin(best)*sqrt(A)*sqrt(B)/2;
}
};

MIPT 105 一种O(n)的RMQ离线算法

我在GYH神牛的论文里看到对于RMQ问题有一种很方便的离线算法。。于是写了个程序去AMIPT105这道标准的RMQ题。。
论文在这里:cid-47648079f9d741d1.skydrive.live.com/self.aspx/OI/RMQ%e9%97%ae%e9%a2%98%e7%9a%84%e7%a6%bb%e7%ba%bf%e8%bf%91%e7%ba%bf%e6%80%a7%e7%ae%97%e6%b3%95.doc
Code:
#include<cstdio>
#include<utility>
using namespace std;
typedef pair<int,int> pi;
const int maxn=250000,maxm=2*maxn;
int stack[maxn],top=0,n,cnt=0,m;
int F[maxn];
float A[maxn],Ans[maxm];
inline void makeset(int x){F[x]=x;}
int find(int x){if(F[x]==F[F[x]])return F[x];return F[x]=find(F[x]);}
inline void Union(int x,int y){F[y]=x;}
int first[maxn],next[maxm],qnt=0;
pi data[maxm];
void add_query(int l,int r)
{
data[qnt]=pi(l,cnt++);
next[qnt]=first[r];
first[r]=qnt++;
}
void init()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%f",A+i),first[i]=-1;
scanf("%d",&m);int l,r;
for(int i=0;i<m;i++) scanf("%d %d",&l,&r),add_query(l,r-1);
}
void solve()
{
for(int i=0;i<n;i++)
{
makeset(i);
while(top&&A[stack[top-1]]>=A[i])
{Union(i,stack[–top]);}
stack[top++]=i;pi*tmp;
for(int j=first[i];j!=-1;j=next[j])
{
tmp=data+j;
Ans[tmp->second]=A[find(tmp->first)];
}
}
for(int i=0;i<m;i++)
printf("%fn",Ans[i]);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
solve();
}

MIPT 026

就是说一个数。。把它+1或-1或者如果是偶数除以2。。求最少次数把它变成0.。。
这个数小于200000。。。
很显然从0开始倒着宽搜就可以了。。不过我为了体现出我的个性。。用了IDFS。。
。。还加了个剪枝,就是+1和-1不能连续两次出现。。然后就0.01sAC了。。
我倒。。。暴力IDFS居然也能过。。4.29s。。晕死了。。大概是因为操作数肯定是logn量级的吧。。
Code:

TopCoder SRM 452 DIV 2 Level 3 HamiltonPath

给定一个完全图和一些必须包含在哈密顿路中的边。。求这样的哈密顿路有几条。。
很显然如果一个点连接了3条或以上的必须边的话。。就无解了。。所以必须边一定是成链出现的。。
一个有2个或以上节点组成的必须链有一个方向,就是因子2
同时如果有n条链的话(单个节点也算链。。)。。那么排列也有n!的因子。。
全部乘起来就OK了。。
Code:
#include<string>
#include<vector>
#include<cstring>
using namespace std;
const int mod=1000000007;
class HamiltonPath
{
bool vis[50];
vector<string> map;
int num;
void dfs(int x)
{
vis[x]=true;num++;
for(int i=0;i<map.size();i++)
if(map[x][i]==’Y’&&!vis[i]) dfs(i);
}
public:
int countPaths(vector <string> m)
{
vector<int> d(m.size(),0);int cnt=0;map=m;long long ans=1;
for(int i=0;i<m.size();i++)
for(int j=0;j<m.size();j++)
{
if(m[i][j]==’Y’) d[i]++;
if(d[i]>2) return 0;
}
memset(vis,0,sizeof(vis));
for(int i=0;i<m.size();i++)if(!vis[i]){num=0;dfs(i);cnt++;if(num>1)ans*=2,ans%=mod;}
for(int i=1;i<=cnt;i++)ans*=i,ans%=mod;
return ans;
}
};

TopCoder SRM 459 DIV2

经神牛指点。。注册了topcoder。。今天有比赛的样子。。所以先做个上次的比赛找找感觉。。
1:
直接计算。。很easy啊。。
#include<cstdio>
#include<cmath>
using namespace std;
class RecursiveFigures
{
public:
double getArea(int len,int k)
{
double ans=0;double d2=len*len,p=acos(0);
for(int i=0;i<k;i++)
{
d2/=2;
ans+=d2*p-d2;
}
ans+=d2;
return ans;
}
};
2:
扫描线。。把每个方程看成一个线段。。那么就变成了在平面上找一个点在最多的线段中了。。
然后从左往右扫描就OK了。。注意可能那个点不是整数。。转换的时候+/-个0.5就OK了。。
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
#include<sstream>
using namespace std;
typedef vector<string>::iterator it;
class Inequalities
{
struct event
{
double x;int a;
event(double _x,int _a):x(_x),a(_a){}
bool operator<(const event&o) const
{return x<o.x;}
};
vector<event> list;
typedef vector<event>::iterator lit;
void add(double l,double r)
{
list.push_back(event(l,1));
list.push_back(event(r,-1));
}
void deal(const string&a)
{
istringstream in(a,istringstream::in);string tmp;
in>>tmp;int x;in>>tmp;in>>x;
if(tmp=="<") add(-1,x);
if(tmp=="<=") add(-1,x+0.5);
if(tmp=="=") add(x,x+0.5);
if(tmp==">") add(x+0.5,1001);
if(tmp==">=") add(x,1001);
}
public:
int maximumSubset(vector<string> Is)
{
for(it i=Is.begin();i!=Is.end();i++)
{
deal(*i);
}
sort(list.begin(),list.end());int ans=0,now=0;double last=-1;
for(lit i=list.begin();i!=list.end();i++)
{
if(i->x!=last){ans=max(ans,now);last=i->x;}
now+=i->a;
}
ans=max(ans,now);
return ans;
}
};
3:还是水题。。设dp(i,k)使从i点经过k条边出去的概率。。。然后直接dp就可以了。。
这个图是无环的。。我还以为是有环的准备解方程的说。。水啊。。
那么根据条件概率公式,答案就是dp (start,k)/sum{dp(all i,k)}。。
#include<vector>
#include<cstring>
#include<string>
using namespace std;
const int maxn=50;
class ParkAmusement
{
vector<string> map;
int n;
bool e(int x){return map[x][x]==’E';}
bool p(int x){return map[x][x]==’P';}
bool c(int x,int y){return map[x][y]==’1′;}
double dp[maxn][maxn];
bool save[maxn][maxn];
double pro(int pos,int len)
{
double&ans=dp[pos][len];
if(save[pos][len]) return ans;
save[pos][len]=true;
if(p(pos)) return ans=0;
if(e(pos)) return ans=(len==0?1:0);
if(len==0) return ans=0;
double sum=0;int num=0;
for(int i=0;i<n;i++)
if(c(pos,i))
{
sum+=pro(i,len-1);
num++;
}
if(num==0) return ans=0;
return ans=sum/num;
}
public:
double getProbability(vector<string> land,int start,int k)
{
map=land;n=map.size();
memset(save,0,sizeof(save));double p=pro(start,k);double sum=0;
for(int i=0;i<n;i++) sum+=pro(i,k);
return p/sum;
}
};
DIV2的题目好水的说。。但是DIV的题目第一题还好说。。第二题我就吴宇森了。。。

Page 5 of 7« First...34567