看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生成,查看详情

SGU 491

全世界第46个A掉这道题的唉。。激动死了。。
激动完了。。讲讲算法吧。
题目是说给一个N。让你求有多少对A和B,让方程Ax+By=N有自然数解。。
N<=100000。。
这个N卡的太紧了。。我花了3个小时加速程序。。
一开始我的想法是首先算出所有小于N的数的因子,一个数的因子个数是logn级别的。
总共就是NlogN这不是问题。。
关键是后面的,时限卡得太紧了,4s,我一开始暴力枚举Ax的值,然后By=N-Ax。
那么Ax的任何因子配上By的任何因子都是解。。然后去重就可以了。。
看一下我的优化之路吧。。下面的时间表示最大数据。。
使用set加上pair<int,int>来去重。。23s
讲pair<int,int>压缩成一个long long。。21s
先讲这些long long存下来。再排序之后去重。。8s
一些细节上的小优化,比如vector使用由索引改成iterator之类的。。7s
大叫了一声TMD,人品爆发     6.2s
晕了。。写了个hash。。    MLE
使劲改Hash。。。    还是MLE
总算改好了Hash    23.3s
震精了。用了Hash+set 15s
撞死。。吃饭去了。。
吃饭好了继续想。。我把最快的那个算法的用时分析了一下。。
发现读入0s输出0s预处理1.6s,枚举0.7s,排序+去重5s。。
于是我发现预处理可以该进。。一开始我是暴力枚举平方根以下的因子并用set去重的,发现更本没必要。只要用vector就可以了。。于是预处理变成0.8s。。
还是超时。。
最后我快绝望了。。于是我想可能是因为排序的东西太多了。。一股脑排序可能慢了点。。
于是我先枚举a再枚举x。。然后算出所有可能的b。。然后对于每个a去一次重。。
实际上这两个算法是一摸一样的。。但是这个就AC了。。
累啊。。。。。
Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<ctime>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100000+1;int n;
vector<int> A[maxn];
typedef vector<int>::iterator it;
typedef vector<int>::reverse_iterator rit;
typedef long long ll;
void Cal(int x)
{
static int tmp[10000];
int cnt=0;
for(int i=1;i*i<=x;i++)if(x%i==0)
tmp[cnt++]=i,tmp[cnt++]=x/i;
sort(tmp,tmp+cnt);A[x].push_back(tmp[0]);
for(int j=1;j<cnt;j++)
if(tmp[j]!=tmp[j-1])
A[x].push_back(tmp[j]);
}
int Ans[maxn*50];
int main()
{
//freopen("in","r",stdin);
int o=clock();
cin>>n;
for(int i=1;i<n;i++) Cal(i);
int ans=0;
for(int a=1;a<n;a++)
{
int*end=Ans;
for(int l=a;l<n;l+=a)
{
int r=n-l;
for(rit i=A[r].rbegin();i!=A[r].rend();i++)
if(*i>a) *(end++)=*i;
else break;
}
if(Ans==end) continue;
sort(Ans,end);
ans++;
for(int*i=Ans+1;i!=end;i++)
if(*i!=*(i-1)) ans++;
}
cout<<ans<<endl;
}
本高亮代码使用codeHl生成,
loading… loading…

Page 1 of 712345...Last »