额。。最为VIJOS回归之后做的第一题。还是蛮有意思的。。
传送门
首先可以看出答案是1到n的倒数和。。
有两个办法。。一个是我开始想到的就是设F(x)为1到x的排列的答案。
那么若这个排列第一个是1。那么就是F(x-1)+1否则在中间的1可以忽略掉，就是F(x-1)。。
那么F(x)=( F(x-1)+1 )/x +F(x-1)*(x-1)/x。。
就是F(x)=F(x-1)+1/x。。。
这个方法只有我这样菜的人才想的出来囧。。
一般来说第i个数为Local Maxima的概率就是他为前i个中最大的概率，就是1/i。。
然后+起来。。
不过数据范围太TMD大了。。
我一开始想是不是要用矩阵加速，感觉不是齐次的搞不出来。。。
最后wiki了一下调和数列，发现原来是有公式的。。
zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89-%E9%A9%AC%E6%AD%87%E7%BD%97%E5%B0%BC%E5%B8%B8%E6%95%B0
因为精度的问题，对于n<=10^6次方的时候。。暴力计算，
否则使用公式。
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;
const int inf=~0U>>1;
const int limit=1e6;
int main()
{
int n;cin>>n;double ans=0;
if(n<=limit)
for(double i=1;i<=n;i++)
ans+=1/i;
else
ans=log((double)n)+0.57721566490153286060651209;
printf("%0.8lfn",ans);
}P.S我的vijos号由于注册的比较早。不叫WJMZBMR。。好像是453844077囧。。我在想是不是为了统一风格就不要原来的号了又舍不得100多道题目囧。。
Category Archives: DefaultCategory
看Saw有感
寒假的作业，由于上个学期一直搞OI随笔一篇都没写，作文差了N篇，才补好一篇囧。
这个实际上很早就写了。。但当时太激动，我怕老师觉得我是BT所以改了改囧。
看Saw有感
someone lives without thanksgiving,
but not you ，any more .
Saw的中文名就是电锯惊魂，说白了就是一部血腥+恐怖片，但我看了之后却觉得，这部片子的导演很伟大，这的的确确是一部反映当前时代精神的片子。
血腥、暴力？嗯，可这在失去灵魂的人面前又算什么？Saw的海报都是一个个失去灵魂的人戴着刑具，脸上除了痛苦什么都没有。实际上这个时代的人的神经已经彻底麻木了，Saw的主角约翰明白还有一种办法可以拯救人，就是痛苦。信仰，宗教，都是虚的，尽管曾经是对的，但是在现在的时代精神面前早已土崩瓦解了，每个人都不再能从他人的脸上看到上帝（哎，我以前是多么相信这个。。），自我的存在意识都逐渐模糊了，人发明了那么多机器，到头来反而被成为机器的机器。
痛苦？看到他人的痛苦，也感觉到痛苦，内心才能不再麻木？感觉到痛苦，才能感觉到自己原来是存在的？原来不仅仅是视觉+听觉+触觉？不是在看三维电影？还是这个世界中的？
活了几十年的人反而要让别人教他体验到自己的存在，很可笑？很可悲？一点也不，这就是事实。
Saw里面约翰得了绝症，快死了，他去自杀，没成功，于是决定将余生用来救赎他人的灵魂。折磨他人，让他人对生命感恩。第一部结束的时候，导演还是忍不住插播了画外音，someone lives without thanksgiving, but not you any more..也许是说给经过考验的医生说的，也许是说给观众听的。
我开始明白为什么有那么多人喜欢自残，那么多人执着于血腥片了，跟爱情和死亡一个道理，想感受到自己存在。
you’re wrong.
No one will change
但这真的是拯救么，第一部中被约翰救赎的阿凡达在第三部中说you’re wrong , No one will change，也许这本来就是骗人的，约翰只是在报复，报复他没有生命了。约翰之所以是对的是因为他头上有上帝的时钟，一个即将死亡的人？一种宿命感？对他人生命的妒忌？我也不知道是什么。也许就是这样。
TopCoder HigSchool 2010 Round 1
这是第一次比赛。。本来是海选出500个人的。。结果总共都没有500个人囧。。
由于明天就要上学了。。本来不想参加的。。但是根本没有睡意。。于是就上了。。
第一题这个太水了。。怎么做都可以。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class TheSequencesLevelOne
{
public:
vector <int> find(vector <int>);
};
vector <int> TheSequencesLevelOne::find(vector <int> s)
{
vector<int> ans;
for(int i=0; i<s.size(); i++)
{
int a;
for(int t=0; t<=7; t++)
{
int x=s[i];
x-=t;
if(x%4==0||x%7==0)
{
a=x;
break;
}
x+=2*t;
if(x%4==0||x%7==0)
{
a=x;
break;
}
}
ans.push_back(a);
}
return ans;
}
//Powered by [KawigiEdit] 2.0!
第二题找规律啊。。奇数位放当前最小的，放了后删掉，偶数位放当前第二小的，放了后删掉，
最后一位特判一下就可以了。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class TheSequencesLevelTwo
{
public:
vector <int> find(vector <int>);
};
vector <int> TheSequencesLevelTwo::find(vector <int> s)
{
set<int> S(s.begin(),s.end());
vector<int> Ans;
for(int i=0; i<s.size()-1; i++)
{
if(i%2==0)
{
Ans.push_back(*S.begin());
S.erase(S.begin());
}
else
{
Ans.push_back(*(++S.begin()));
S.erase(++S.begin());
}
}
Ans.push_back(*S.begin());
return Ans;
}
//Powered by [KawigiEdit] 2.0!
第三题的题目可以转化成分成有序的两堆不包括最大数，两堆中相邻元素差不超过K。那么从小到大一个个考虑元素，每个堆有意义的只有大小和最上面的数。。同时一定有一个堆最上面是当前最大的数，所以只要记录3个值就可以了。。然后递推。。算出所有的结果。。然后判断一下最大数就可以了。。
我也不知道为什么我非常WS的用了动态申请。。
dp[i][j][k]当前左边堆有i个，右边堆有j最大的那个在左边堆的最上面，k是右边堆最上面数的编号
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class TheSequencesLevelThree
{
public:
int find(vector <int>, int);
};
const int mod=1234567891;
int TheSequencesLevelThree::find(vector <int> s, int K)
{
sort(s.begin(),s.end());
long long***dp;
int n=s.size();
if(n<3) return 0;
dp=new long long**[n+1];
for(int i=0; i<=n; i++)
{
dp[i]=new long long*[n+1];
for(int j=0; j<=n; j++)
{
dp[i][j]=new long long[n+1];
for(int k=0; k<=n; k++)
dp[i][j][k]=0;
}
}
dp[0][0][0]=1;
int t;
for(int l=0; l<n; l++)
for(int i=0; i<=l; i++)
{
int j=l-i;
for(int k=0; k<n; k++)
if(t=dp[i][j][k])
{
int now=i+j;
if(i==0||s[now]-s[now-1]<=K)
dp[i+1][j][k]+=t,dp[i+1][j][k]%=mod;
if(j==0||s[now]-s[k]<=K)
dp[j+1][i][now-1]+=t,dp[j+1][i][now-1]%=mod;
}
}
long long ans=0;
for(int l=1; l<n-1; l++)
{
int r=n-l-1;
for(int k=0; k<n; k++)
{
int x=dp[l][r][k];
if(s[n-1]-s[k]<=K&&s[n-1]-s[n-2]<=K)
ans+=x,ans%=mod;
}
}
ans*=2;
ans%=mod;
return ans;
}
//Powered by [KawigiEdit] 2.0!
我还Cha掉了一个人的程序。。算法不知道对不对。一看他的特判就知道他判错了。。处女Cha啊。。
我的Coding的速度真是慢死了。。分低的要命。。囧
PS.那个人算法真是对的。。
这么大的随机数据都过了。。反而被我这个Cha掉囧。。
发现一个语法高亮的网站非常NB
我找了N多地方都没有发现什么网站可以高亮scala的。。
后来我看到了一篇文章。找到了这个网站：
www.andre-simon.de/doku/highlight/en/highlight_demo.html
自己看啦，太NB了。。基本可以高清任何代码。。发个效果图
C++：
#include <stdio.h>
int main(void)
{
char msg[13] =
{ 0110, 0145, 0154, 0154, 0157, 054, 040,
0127, 0157, 0162, 0154, 0144, 012 };
int i;
for ( i=0; i<13; i++ )
putchar(msg[i]);
return 0;
}
Java：
public class Fibonacci {
public static long fib(int n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
for (int i = 1; i <= N; i++)
System.out.println(i + ": " + fib(i));
}
}
[HNOI2008]越狱
倒。。这么水的题目都有的。。
Link：61.187.179.132:8080/JudgeOnline/showproblem
正着想有点麻烦。。倒过来想。。
一共有m^n种情况，其中不能越狱的情况中，如果从左往右考虑的话，第一个是m种，其余都是m-1种
所以就是(m-1)^(n-1)*m。。用一个二分计算乘方就可以了。。
减一下就可以了囧。。
Code：
#include<iostream>
using namespace std;
typedef long long ll;
const int mod=100003;
ll m,n;
inline void mul(ll&a,int b){a*=b;a%=mod;}
int power(ll x,int base)
{
if(x==0) return 1;
ll tmp=power(x/2,base);
mul(tmp,tmp);
if(x&1) mul(tmp,base);
return tmp;
}
int main()
{
cin>>m>>n;
int all=power(n,m);
ll sub=power(n-1,m-1);
mul(sub,m);
int ans=all-sub;if(ans<0) ans+=mod;
cout<<ans<<endl;
}
本高亮代码使用codeHl生成，
[ZJOI2007]报表统计
[ZJOI2007]报表统计
Time Limit:15000MS Memory Limit:165536K
Total Submit:154 Accepted:37
Case Time Limit:10000MS
Description
小Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。经过仔细观察，小Q发 现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。
在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作：
INSERT i k 在原数列的第i个元素后面添加一个新元素k；
如果原数列的第i个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子）
MIN_GAP 查询相邻两个元素的之间差值（绝对值）的最小值
MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值（绝对值）
例如一开始的序列为
5 3 1
执行操作INSERT 2 9将得到：
5 3 9 1
此时MIN_GAP为2，MIN_SORT_GAP为2。
再执行操作INSERT 2 6将得到：
5 3 9 6 1
注意这个时候原序列的第2个元素后面已经添加了一个9，此时添加的6应加在9的后面。这个时候MIN_GAP为2，MIN_SORT_GAP为 1。
于是小Q写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
Input
第一行包含两个整数N，M，分别表示原数列的长度以及操作的次数。
第二行为N个整数，为初始序列。
接下来的M行每行一个操作，即“INSERT i k”，“MIN_GAP”，“MIN_SORT_GAP”中的一种（无多余空格或者空行）。
Output
对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令，输出一行答案即可。
Sample Input
3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
Sample Output
2
2
1
Hint
对于30%的数据，N ≤ 1000 , M ≤ 5000
对于100%的数据，N , M ≤500000
对于所有的数据，序列内的整数不超过5*108。
Source
61.187.179.132:8080/JudgeOnline/showproblem
由于是中文的，题目大意就不用讲了
那么这道题怎么办呢？我是全用stl的，Code Length最短，速度就悲剧了。。
首先第一个操作的话用个vector数组模拟就可以了。。
由题目的特性，把第i个元素后面的数成为第i个列表。。
那么第二个操作，MIN_GAP呢？
有三个办法，一个是自己写一个heap。然后需要有删除操作，所以还要弄一个索引。。
麻烦额。。第二个是用一个multiset，然后删除就删除，最小就是begin()。。
我一开始就是这样。。TLE了。。
第三就是用stl里面priority_queue，那么删除的话可以用懒删除，
因为一个节点只要不是最小的就没有立马删除的必要，
那么可以发现如果造成这个差值的两个数在同一个列表里。。
那么这个值永远不会被删除，
只有是一个列表的最后一个和其后一个列表的第一个造成的差值，
才有可能在插了一个数后被删除，那么只需要对后一种记录当时的前一个列表的大小，
那么如果这个大小小于当前的大小，就说明在那之后有值插进来过，这个值就失效了。。
第二个就搞定了。。
第三个呢？首先注意到这个值只可能是在排序之后的相邻对，
那么只需要用一个set来维护当前所有数，并且在插入之后更新一下就可以了。。
按这个思路写成的Code差点就超时了。。
于是我又想了一会儿。。发现根本没必要用vector，
因为当前有效的项根本就只有第一项和最后一项！
所以只要弄个2维数组就可以了！
然后就快多了：
代码也短了。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<utility>
#include<set>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define For(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int inf=~0U>>2;
const int maxn=500000;int n;
int L[maxn][2];
int N[maxn];
inline int abs(int x){return x>0?x:-x;}
struct qset
{
multiset<int> S;
typedef set<int>::iterator it;
int Min;
qset(){Min=inf;}
void ins(int x)
{
it j=S.insert(x);
if(j!=S.begin())
Min=min(Min,x-*(–j)),++j;
++j;
if(j!=S.end())
Min=min(Min,*(j)-x);
}
}All;
struct state
{
bool in;
int i,x,val;
state(bool _in,int _val,int _i=0,int _x=0):
in(_in),i(_i),x(_x),val(_val){}
bool legal() const{return in||x==N[i];}
bool operator<(const state&o) const{return val>o.val;}
};
priority_queue<state> Q;
void ins(int i,int x)
{
All.ins(x);
Q.push(state(true,abs(x-L[i][1])));
L[i][1]=x;N[i]++;
if(i!=n-1) Q.push(state(false,abs(L[i+1][0]-x),i,N[i]));
}
int get()
{
while(!Q.top().legal()) Q.pop();
return Q.top().val;
}
int main()
{
char cmd[100];
int n,m,x,i;
scanf("%d %d",&n,&m);
rep(i,n) scanf("%d",&L[i][0]),L[i][1]=L[i][0],All.ins(L[i][0]),N[i]=1;
For(i,0,n-1)
{
Q.push(state(false,abs(L[i+1][0]-L[i][0]),i,1));
}
while(m–)
{
scanf("n");
scanf("%s",cmd);
if(cmd[0]==’I’)
scanf("%d %d",&i,&x),ins(i-1,x);
else if(cmd[4]==’G’) printf("%dn",get());
else printf("%dn",All.Min);
}
}
本高亮代码使用codeHl生成，查看详情
[JSOI2008]最大数maxnumber
Link：61.187.179.132:8080/JudgeOnline/showproblem
就是说让你维护一个数据结构。
支持两个操作，A 在末尾插入一个数，
Q L，最后L个数中最大的是哪个？
很明显要用单调队列。。用了单调队列后。。
整个数列被分成几段每段的答案都是一样的。。
那么弄一个并查集维护答案。。然后插入一个数可能导致几段的合并，
就正好是并查集的Union，然后每段的根就是这段的答案。。
那么用并查集就可以搞定了。。
这个算法实际上就是离线RMQ的一种应用，我以前发过这样那个算法，见：传送门
Code：
#include<cstdio>
using namespace std;
const int maxn=200000;
int stack[maxn],top=0;
int F[maxn],A[maxn];
int find(int x){if(F[x]==x) return x; return F[x]=find(F[x]);}
void Union(int x,int y){F[y]=x;}
int main()
{
//freopen("in","r",stdin);
int last=0,m,d,x,n=0;char c;
scanf("%d %dn",&m,&d);
while(m–)
{
scanf("%c %dn",&c,&x);
if(c==’Q’)
x=(n-x),printf("%dn",last=A[find(x)]);
else
{
F[n]=n;A[n]=(last+x)%d;
while(top&&A[stack[top-1]]<=A[n])
Union(n,stack[top-1]),top–;
stack[top++]=n++;
}
}
}
本高亮代码使用codeHl生成，查看详情
SGU 489
就是说一个1到n的排列如果是一上一下的。。那么就叫local extreme。。
然后告诉你n让你求1到n的排列里local extream的数量。。
我太无耻了。。首先暴力搜出1到8的结果。。
1,2,4,10,32,122,544,2770
然后上www.research.att.com/~njas/sequences/index.html
搜索这个数列。。然后找到了这个数列的介绍mathworld.wolfram.com/AlternatingPermutation.html
然后用http://mathworld.wolfram.com/EulerZigzagNumber.html上面的办法来做的。。
说实话我根本没有搞懂这个是什么意思！但是我还是写了程序。。A掉了这道题。。
以后遇到数列题就这么干了。。话说我发现SGU上过了100题了。。高兴一下
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=10000+10;int dp[2][maxn]={0};int main(){ //freopen("in","r",stdin); int n,m;cin>>n>>m;–n;if(!n){cout<<1%m<<endl;return 0;} int now=0,old=1; dp[now][1]=1; for(int i=2;i<=n;i++) { swap(now,old); dp[now][0]=0; for(int j=1;j<=n;j++) { dp[now][j]=dp[now][j-1]; if(i>j) { dp[now][j]+=dp[old][i-j]; if(dp[now][j]>=m) dp[now][j]-=m; } } } int ans=0; for(int i=1;i<=n;i++) ans+=dp[now][i],ans%=m; cout<<(ans*2)%m<<endl;}
本高亮代码使用codeHl生成，查看详情
PS。。我总算搞明白这个公式了
E(n,k)是1到n的排列中第一个是k且一开始下降的数量。。
由于是下降，那么下一个要小于k。。
那么如果下一个是k-1的话。。
那么就是剩下的数列第一个是k-1并且上升的方法数了。。
由于k已经选了。。那么k-1在这个数列中是倒数第n-k个。。
上升跟下降是11对应的。。于是这方面的是E（n-1，n-k）。。
然后如果下一个不是k。。那么就是E（n，k-1）了。。
加起来就是上面的公式
这个里面第一个是下降。。最后答案乘以2。。。。
因此要特判n=1的情况。。
SPOJ 1 in scala
。。。最近我在把玩scala真是很有意思啊。。为了更好的使用。我装了个eclipse的scala控件。。
于是我前去A掉了SPOJ的第一题。。(*^__^*) 。。还用scala写了个我最喜欢的算法spfa（。。
不过在SPOJ上TLE了囧。。
还好把TEXT过了。。
SGU 476
这两天我在拼命刷SGU。。本来想弄哥country hero爽一下的。。结果没成功
这道题是说一个教练，有3*N个学生，要把他们3个3个分成N组，同时有k个3元组的学生不能成为一组，有多少种方法。
由于N<=1000，k<=20。。我的办法是利用冗斥原理来做，枚举每移一种k个3元组的子集，然后分别计算各种方法数。。就可以了。。
但是这样是要TLE的。。我发现不用每一个算出来都加一下。。由于实际上+的值只有k+1种，弄一个add数组表示每种情况被+的次数。。到最后乘一下就可以了。。
Code：因为是高精度，所有我用了Java
import java.math.*;import java.util.*;import static java.math.BigInteger.*;public class Solution { static Scanner in=new Scanner(System.in); static BigInteger[] P; static int[] Add; static int[][] L; static int n,k; static void CalP() { BigInteger now=ONE; if(n<=k) P[n]=ONE; for(int i=1;i<=n;i++) { now=now.multiply(valueOf(i*3-2)); now=now.multiply(valueOf(i*3-1)); now=now.multiply(valueOf(i*3)); now=now.divide(valueOf(6)); now=now.divide(valueOf(i)); if(n-i<=k) P[n-i]=now; } } static boolean[] In; static void dfs(int pos,int ch) { if(pos==k) { if(ch%2==0) Add[ch]++; else Add[ch]–; return; } boolean check=true; for(int i=0;i<3;i++) if(In[L[pos][i]]) { check=false; break; } if(check) { for(int i=0;i<3;i++) In[L[pos][i]]=true; dfs(pos+1,ch+1); for(int i=0;i<3;i++) In[L[pos][i]]=false; } dfs(pos+1,ch); } public static void main(String[] args) { n=in.nextInt();k=in.nextInt(); L=new int[k][3]; for(int i=0;i<k;++i) { for(int j=0;j<3;j++) L[i][j]=in.nextInt()-1; } P=new BigInteger[k+1]; Add=new int[k+1]; In=new boolean[n*3]; CalP(); dfs(0,0); BigInteger Ans=ZERO; for(int i=0;i<=k;i++) if(P[i]!=null) Ans=Ans.add(P[i].multiply(valueOf(Add[i]))); System.out.println(Ans); }}
本高亮代码使用codeHl生成，查看详情