SGU 417

。。。这是编程题么。。明明是BT纯高等数学题。。

就是说每个点的密度函数是ln(x^2+y^2)。。然后给你一个跟原点不想交的圆,然你求这个圆的重量。

ln(x^2+y^2)不就是2ln(圆点到该点的距离么)。。这个这个。。没想法。。

怎么办啊。。我暴力积分了半天。脑子都大了。。只好找规律。。我弄了一堆数据。。

然后我震精了。。答案就是圆心的密度的乘以圆的面积。。

我也不知道为什么

总结就是看到这种题算毛啊。。直接找规律。。AC就是硬道理!

Code:

#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cmath>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;int main(){ //freopen("in","r",stdin); double p=acos(0)*2;int x,y,r;cin>>x>>y>>r; double ans=log(x*x+y*y)*r*r*p; printf("%0.15lfn",ans);}本高亮代码使用codeHl生成,查看详情

SGU 441

就是把p个东西分成k个非空的部分,顺序不同的比如1234和4321视为一种。让你求出答案mod 2007
总所周知这是传说中的第二类Stirling数,它的公式是S(p,k)=S(p-1,k-1)+k*S(p-1,k)
那么似乎好像就可以直接上了,但是p的范围是1到10亿,k的范围是10以下。。
怎么办捏,我一开始想起来这个函数有一个公式,Wiki上有,但是我发现这个公式要除一个数的囧,就没办法mod了。。
我想啊想啊。。最后发现由于k比较小,直接矩阵乘法来计算就可以了额。。
是O(logp*k^3)。。
矩阵乘法是解决这类递推问题的良方啊!
Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const int mod=2007;
const int maxn=11;
typedef int data[maxn][maxn];
int p,c;
struct mat
{
data o;
mat(){memset(o,0,sizeof(o));}
int& operator() (int i,int j)
{return o[i][j];}
int operator() (int i,int j) const
{return o[i][j];}
void operator=(const mat&x)
{memmove(o,x.o,sizeof(o));}
void print()
{
rep(i,c)
{
rep(j,c)
cout<<o[i][j]<<" ";
cout<<endl;
}
}
}o;
mat operator*(const mat&a,const mat&b)
{
mat r;
rep(i,c) rep(j,c) rep(k,c)
r(i,j)+=a(i,k)*b(k,j),r(i,j)%=mod;
return r;
}
mat power(int p)
{
if(p==1) return o;
mat tmp=power(p/2);
tmp=tmp*tmp;
if(p&1) tmp=tmp*o;
return tmp;
}
int main()
{
//freopen("in","r",stdin);
cin>>p>>c;c++;
rep(i,c) o(i,i)=i;
for(int i=1;i<c;i++) o(i,i-1)=1;
mat now=power(p);
//now.print();
int ans=0;
cout<<now(c-1,0)<<endl;
}
本高亮代码使用codeHl生成,

SGU 415

Problem
就是说给你n个硬币,然后让你支付m的货物,让你求出那些硬币是必须的。。、
n<=200,m<=10000
这个数据范围,如果枚举每个硬币,然后计算的化,绝对会悲剧,
怎么办呢,我注意到要尽量利用计算的信息,
设L[x]表是1->x-1这些硬币能支付的钱的集合。
R[x]是x+1->n这些硬币能支付的钱的集合。
使用布尔数组或者bitset来表示,那么可以在O(nm)算出这些数。。
然后检查第x个是不是必须的就很方便了,可以在O(m)完成。。
Code:

#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxm=10000+1,maxn=200;int m,n;int A[maxn];struct Coins{ bool C[maxm]; int M; Coins(){memset(C,0,sizeof(C));M=0;C[0]=true;} void put(int x) { for(int i=M;i>=0;–i) if(C[i]&&i+x<=m) C[i+x]=true; M+=x;M=min(M,m); } void operator=(const Coins&o) { memmove(C,o.C,sizeof(C)); M=o.M; } bool& operator[](int v){return C[v];}};Coins L[maxn],R[maxn];void init(){ cin>>n>>m; rep(i,n) cin>>A[i];}void solve(){ Coins tmp; for(int i=0;i<n;i++) { L[i]=tmp; tmp.put(A[i]); } tmp=Coins(); for(int i=n-1;i>=0;–i) { R[i]=tmp; tmp.put(A[i]); } vector<int> ans; for(int i=0;i<n;i++) { bool ok=false; for(int x=0;x<=m;x++) if(L[i][x]&&R[i][m-x]) { ok=true;break; } if(!ok) ans.push_back(A[i]); } cout<<ans.size()<<endl; rep(i,ans.size()) cout<<ans[i]<<" ";}int main(){ //freopen("in","r",stdin); init(); solve();}

本高亮代码使用codeHl生成,查看详情

SGU 488

悲剧了。我怎么就这么菜呢

这道题就是纯水题,不过两种东西实际上只要写一个就可以了。。

把所有数取反再算一遍就是第二个的答案了。。

Code:

#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=1000000+1;int A[maxn],L[maxn],R[maxn],n;void init(){ cin>>n; rep(i,n) scanf("%d",A+i);}int Cal(){ L[0]=0; for(int i=1;i<n;++i) if(A[i-1]<A[i]) L[i]=L[i-1]; else L[i]=i; R[n-1]=n-1; for(int i=n-2;i>=0;–i) if(A[i+1]<A[i]) R[i]=R[i+1]; else R[i]=i; int ans=0; rep(i,n) ans=max(min(i-L[i],R[i]-i),ans); return ans;}void solve(){ init(); int H=Cal(); rep(i,n) A[i]=-A[i]; int D=Cal(); printf("%d %dn",H,D);}int main(){ //freopen("in","r",stdin); int t;cin>>t; while(t–) solve();}

本高亮代码使用codeHl生成,查看详情

SGU题解索引

无聊了。。做个索引吧。。就当整理一下
加个推荐程度吧。。1到5。。越高越好
SGU:
103 最短路   3
111 高精度开平方  2
130 Catalan数或DP 1
134 树形DP 2
149 树形DP 3
165 构造 3
175 递归 2
187 动态数列维护,数据结构题 4
199 DP 2
200 高斯消元 3
242 网络流 2.5
247(算法) 很有意思的数学题,是以前IMO的题目 4
247(程序)
299 水题,排序之后扫描 1
302 模拟题,很水 1.5
318 并查集。 2.5
327 哈密顿路 4.5
339
暴力模拟,题目很唬人 2.5
347-357(1)
347-357(2)
362
375
377
395
415
417
高等数学+找规律 4.5
441 矩阵乘法 3.5
455
463
476 容斥原理外加一点优化 4
479
484
488 水题,DP 2
489 DP 3
491 很有技巧的枚举 4.5
499 正确估计复杂度,然后枚举答案判定 3.5
502 暴力dfs 2
507
用set维护答案,启发式合并,正确估计复杂度才敢写。。 4
PS。不知不觉居然写了这么多。。唉。。老了。。

SGU 455

就是说给你一个序列。第0项是1其余由上一项决定。。
如果第一个与前面的数重复的数的编号小于2000000。。就输出这个编号。。否则就输出-1.。
分析:一开始我当然想的是用hash,set之类的数据结构来搞定。。结果TLE的跟鬼一样。。
后来我在wiki上看到了寻找循环节的O(1)空间算法。。这才恍然大悟。。真的很神奇。
Link:Cycle Finding
简单的介绍一下吧。。设Fx是序列中的第x个数。。弄两个指针。。一个指向Fi。。一个指向F2*i。。
每次讲i加一,那么第一个指针前进1个。第二个前进两个。直到Fi=F2*i了。。i就是一个循环节了。。
然后从第0个数开始推起。。找出第一个x使Fx=Fx+i。。
然后再从x往后推。。找到第一个与其相等的。就是答案了。。
Code:

#include<iostream>
using namespace std;
typedef long long ll;
ll A,B,C;
const int maxn=2e6;
ll next(const ll&x)
{
return (A*x+x%B)%C;
}
void init()
{
cin>>A>>B>>C;
}
bool solve()
{
ll l=next(1),r=next(l);
for(int i=1;i<=maxn+1;i++)
{
if(l==r) break;
l=next(l);
r=next(r);r=next(r);
}
if(l!=r) return false;
l=1;int f=0;
while(l!=r)
{
l=next(l);
r=next(r);
f++;
}
r=next(l);
for(int n=f+1;n<=maxn;n++)
{
if(l==r){cout<<n<<endl;return true;}
r=next(r);
}
return false;
}
int main()
{
init();
if(!solve())cout<<-1<<endl;
}

本高亮代码使用codeHl生成,

PKU 3728 The merchant

Link:题目
就是说上次我说的那个PKU月赛题。。Tarjan离线就是NB啊。。
那个保存2的乘方的既耗空间,又耗时间。。
而Tarjan是线性的。。
这道题目就是说给你一个颗边不代权,点代权的树,有个商人要旅行。每次从一个点到另一个点,点权表示商品的价格。。商人最多进货和卖出一次,求他的最大收入(可以不交易)。。
这道题就需要维护一个并查集中顶点到并查集中父亲的路径的4个值了,最大点权,最小点权,从它到并查集中父亲一路的最大收入,从并查集父亲到它一路的最大收入。。
这是可以合并的。。然后求的时候。。终点到lca的信息要反一下。。
Code:

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=1<<20;
const int maxn=50000;int n;
const int maxm=maxn;int m;
struct edge
{
int t;
edge(int _t):t(_t){}
};
struct queryLca
{
bool s;
int t,n;
queryLca(int _t,int _n,bool _s):t(_t),n(_n),s(_s){}
};
struct query
{
int a,b,n;
query(int _a,int _b,int _n):a(_a),b(_b),n(_n){}
};
struct info
{
int Min,Max,Pro,RPro;
info(int v=0):Min(v),Max(v),Pro(0),RPro(0){}
info R()
{
info ans=*this;
swap(ans.Pro,ans.RPro);
return ans;
}
void Merge(const info& o)
{
Pro=max(Pro,o.Pro);
Pro=max(Pro,o.Max-Min);
RPro=max(RPro,o.RPro);
RPro=max(RPro,Max-o.Min);
Min=min(Min,o.Min);
Max=max(Max,o.Max);
}
};
vector<edge> E[maxn];
vector<queryLca> Lca[maxn];
vector<query> Query[maxn];
typedef vector<edge>::iterator eit;
typedef vector<queryLca>::iterator lit;
typedef vector<query>::iterator qit;
info Ans[maxm];
void add_edge(int s,int t)
{
E[s].pb(edge(t));
E[t].pb(edge(s));
}
void add_lca(int s,int t,int n)
{
Lca[s].pb(queryLca(t,n,true));
Lca[t].pb(queryLca(s,n,false));
}
info P[maxn];
int F[maxn];
void set()
{
rep(i,n) F[i]=i;
}
int find(int x)
{
int tmp=F[x];
if(F[x]!=x)
F[x]=find(F[x]),P[x].Merge(P[tmp]);
return F[x];
}
void Union(int i,int j)
{
F[j]=i;
}
bool vis[maxn]={0};
void dfs(int x)
{
vis[x]=true;
for(eit i=E[x].begin();i!=E[x].end();i++)if(!vis[i->t])
dfs(i->t),Union(x,i->t);
for(lit i=Lca[x].begin();i!=Lca[x].end();i++)
{
if(vis[i->t])
{
if(i->s)
Query[find(i->t)].pb(query(x,i->t,i->n));
else
Query[find(i->t)].pb(query(i->t,x,i->n));
}
}
for(qit i=Query[x].begin();i!=Query[x].end();i++)
{
find(i->a);find(i->b);
info&t=Ans[i->n];
t=P[i->a];t.Merge(P[i->b].R());
}
}
void init()
{
scanf("%d",&n);int s,t,c;
set();
for(int i=0;i<n;i++)
scanf("%d",&c),P[i]=info(c);
for(int i=0;i<n-1;i++)
{
scanf("%d %d",&s,&t);
add_edge(s-1,t-1);
}
scanf("%d",&m);int a,b;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
add_lca(a-1,b-1,i);
}
}
void solve()
{
dfs(0);
for(int i=0;i<m;i++)
printf("%dn",Ans[i].Pro);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
solve();
}

本高亮代码使用codeHl生成,

SPOJ 3978 Distance Query

Link:Problem
大意是给一颗代权树。Q个询问。每个询问是两个节点。
让你回答这两个节点之间路径上的最长边和最短边。
跟PKU月赛的某题有点像。
使用离线算法类tarjan算法。
在并查集中对每个节点维护一个到父亲(并查集中的父亲)的路径上最长和最短的边。。
那么在路径压缩的时候也可以顺便合并。。
在求出两个节点之间的lca之后。。等dfs回到了这个lca。。就有充分的信息了。。
可以很方便的计算答案
PS我太依赖stl了。。这样下去怎么行
Code:

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1;
const int maxn=100000;int n;
const int maxm=maxn;int m;
struct edge
{
int t,c;
edge(int _t,int _c):t(_t),c(_c){}
};
struct queryLca
{
int t,n;
queryLca(int _t,int _n):t(_t),n(_n){}
};
struct query
{
int a,b,n;
query(int _a,int _b,int _n):a(_a),b(_b),n(_n){}
};
struct info
{
int Min,Max;
info():Min(inf),Max(-inf){}
info(int v):Min(v),Max(v){}
void print() const{cout<<"{"<<Min<<","<<Max<<"}";}
void Merge(const info& o)
{
//print();cout<<" + ";o.print();cout<<endl;
Min=min(Min,o.Min);
Max=max(Max,o.Max);
}
};
vector<edge> E[maxn];
vector<queryLca> Lca[maxn];
vector<query> Query[maxn];
typedef vector<edge>::iterator eit;
typedef vector<queryLca>::iterator lit;
typedef vector<query>::iterator qit;
info Ans[maxm];
void add_edge(int s,int t,int c)
{
E[s].pb(edge(t,c));
E[t].pb(edge(s,c));
}
void add_lca(int s,int t,int n)
{
Lca[s].pb(queryLca(t,n));
Lca[t].pb(queryLca(s,n));
}
info P[maxn];
int F[maxn];
void set()
{
rep(i,n) F[i]=i;
}
int find(int x)
{
int tmp=F[x];
if(F[x]!=x)
F[x]=find(F[x]),P[x].Merge(P[tmp]);
return F[x];
}
void Union(int i,int j,int c)
{
F[j]=i;
P[j]=info(c);
}
bool vis[maxn]={0};
void dfs(int x)
{
vis[x]=true;//cout<<x<<endl;
for(eit i=E[x].begin();i!=E[x].end();i++)if(!vis[i->t])
dfs(i->t),Union(x,i->t,i->c);
for(lit i=Lca[x].begin();i!=Lca[x].end();i++)
{
if(vis[i->t])
{
Query[find(i->t)].pb(query(x,i->t,i->n));
//cout<<find(i->t)<<" "<<x<<" "<<i->t<<endl;
}
}
for(qit i=Query[x].begin();i!=Query[x].end();i++)
{
find(i->a);find(i->b);
info&x=Ans[i->n];
x=P[i->a];x.Merge(P[i->b]);
}
}
void init()
{
scanf("%d",&n);int s,t,c;
set();
for(int i=0;i<n-1;i++)
{
scanf("%d %d %d",&s,&t,&c);
add_edge(s-1,t-1,c);
}
scanf("%d",&m);int a,b;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
add_lca(a-1,b-1,i);
}
}
void solve()
{
dfs(0);
for(int i=0;i<m;i++)
printf("%d %dn",Ans[i].Min,Ans[i].Max);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
solve();
}
本高亮代码使用codeHl生成,
话说我3点半了闲着无聊居然开始刷题了。。

scala

昨天十分无聊。。看了看一个最近比较流行的新语言scala。。真是太强了。。
scala=Java+函数语言。。
我花了些时间学习了一下。。
scala有一些十分强悍的语言特性。。

1.
函数可以做参数。。这个java是不可以的。。C++和C是可以的。但没有scala这么漂亮。。
比如一个函数 是从Int到Int的(比如乘方啊。。*2啊之类的)。。
就是 (Int) => Int。。
如果是二元的。。就是
(Int,Int) => Int。。
用=>符号十分的形象。。
2.
a.method(b) <=> a method b
就是说一切这样的函数都是操作符。。比如对象a有个方法叫insert。。
那么 a.insert(x) <=> a insert x
3.
跟Java接轨。。可以使用一切java的库。。并且编出来的东西可以在JVM上运行。。
比Java更强大并且代码远远简单于Java。。效率差不多(一样的恶心。。)
4.
在面向对象方面也比java纯粹。。java中基本类型不是对象。。
scala中基本类型也是对象。是Any的子类。。
发一个scala的快速排序的代码:
5.
继承了Java的优良传统。。速度慢的跟鬼一样
函数式:
def sort(xs: Array[Int]): Array[Int] = {
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}
过程式。。感觉跟pascal有点像
def sort(xs: Array[Int]) {
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
}
def sort1(l: Int, r: Int) {
val pivot = xs((l + r) / 2)
var i = l; var j = r
while (i <= j) {
while (xs(i) < pivot) i += 1
while (xs(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (j < r) sort1(i, r)
}
sort1(0, xs.length 1)
}
还有HelloWorld的程序。。
object HelloWorld {
def main(args: Array[String]) {
println("Hello, world!")
}
}还有一些就看scala的官网
http://www.scala-lang.org/ 上面有很多学习资料
还有wiki上的页面。。

Page 2 of 712345...Last »