URAL1103[Pencils and Circles]

数学题。 首先可以证明有解当且仅当N不小于3且为奇数。 证明: 若N为偶数或N小于3,显然无解。 若N为不小于3的奇数,那么可以用下面的方法构造一个可行解。 首先选则两点(记为A,B),使得除这两点以外的所有点都在直线AB一侧。 那么若再选一点C,则对A,B,C以外的点(记为D)来说,它在过三角形ABC的外接园内当且仅当角ADB>角ACB。 由此,若把除A,B以外的所有点(记为P[i])排个序,使得对所有可取得的i,角AP[i]B>角AP[i+1]B。 又记排序后的P[i]中的中间那个一个点P[mid]为C。 则对所有i<mid,P[i]在三角形ABC内;对所有i>mid,P[i]在三角形ABC外。 所以三角形ABC即为所求三角形。 然后继续练习Java,这次刚好还用上了大数。 CODE: import java.io.*;import java.util.*;import java.math.*;public class Ural { public static void main(String args[]) throws IOException { new Ural(); } public int N; public BigInteger x[],y[],ax,ay,bx,by,cx,cy; public BigInteger cross(BigInteger ax,BigInteger ay,BigInteger bx,BigInteger by,BigInteger cx,BigInteger cy) { return bx.subtract(ax).multiply(cy.subtract(ay)).subtract(by.subtract(ay).multiply(cx.subtract(ax))); } public BigInteger dot(BigInteger ax,BigInteger ay,BigInteger […]

URAL1102[Strange Dialog]

水动规。 CODE: /*PROGRAM: $PROGRAMAUTHOR: Su JiaoDATE: 2011-11-17DESCRIPTION:$DESCRIPTION*/#include <cstdio>#include <cstring>using namespace std;const int MAXS=10000000+1;const int MAXM=6;int N;bool f[MAXS];int sl;char s[MAXS];char match[MAXM][7]={“out”,”output”,”puton”,”in”,”input”,”one”};int matchl[MAXM]={3,6,5,2,5,3};int main(){ gets(s); sscanf(s,”%d”,&N); for (int n=0;n<N;n++) { gets(s); sl=strlen(s); memset(f,0,sizeof(f)); f[0]=true; for (int i=0;i<sl;i++) if (f[i]) for (int j=0;j<MAXM;j++) if (i+matchl[j]<=sl) { bool matched=true; for (int k=0;k<matchl[j];k++) if (s[i+k]!=match[j][k]) matched=false; if (matched) f[i+matchl[j]]=true; } […]

URAL1101[Robot in the Field]

表达式求值+简单模拟。 继续练习Java。 CODE: /*PROGRAM: $PROGRAMAUTHOR: Su JiaoDATE: 2011-11-17DESCRIPTION:$DESCRIPTION*/import java.io.*;import java.util.*;public class Ural { public static void main(String args[]) { new Ural(); } public String exp; public int N,M,K; public int mx[],my[],kx[],ky[],iv[]; public boolean vars[]; public final int DIRS=4; public int dir,x,y; public int dx[],dy[]; public int getid(char ch) { return (int)(ch-‘A’); } public boolean calc() […]

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]I.Isabella's Message

2011年成都赛区I题的题解。 水题不解释。主要是练练Java,刚学Java,需要多练练。 CODE: /*PROGRAM: $PROGRAMAUTHOR: Su JiaoDATE: 2011-11-11DESCRIPTION:$DESCRIPTION*/import java.io.*;import java.util.*;public class Main { public static void main(String args[]) { new Main(); } public int N,M; public String message[],mask[],words[]; public String get_answer() { StringBuffer masks[][]=new StringBuffer[4][N]; for (int i=0;i<N;i++) masks[0][i]=new StringBuffer(mask[i]); for (int i=1;i<4;i++) for (int x=0;x<N;x++) { masks[i][x]=new StringBuffer(); masks[i][x].setLength(N); for (int y=0;y<N;y++) masks[i][x].setCharAt(y,masks[i-1][N-1-y].charAt(x)); } […]

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]H.Holiday's Accommodation

2011年成都赛区H题的题解。 对于每一条边,设它左边有X个点,右边有Y个点,则显然有min(X,Y)*2个点会经过这条边,所以答案=sum{每条边的长度乘以会经过这条边的点数}。然后需要动态规划一下。据现场经验,不能直接DFS来动规(会爆栈),需要BFS。 然后,我现在正在学习Java所以代码是用Java写的,呵呵。这是我用Java写的第一个AC的程序哦。 CODE: /*PROGRAM: $PROGRAMAUTHOR: Su JiaoDATE: 2011-11-11DESCRIPTION:$DESCRIPTION*/import java.io.*;import java.util.*;public class Main { public static void main(String args[]) { new Main(); } public class Graph { public class edge { public int v,d,n; } public int top; public edge edges[]; public int adj[]; public int N; public Graph(int N_) { N=N_; edges=new edge[(N-1)*2]; top=0; […]

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]G.GRE Words

2011年成都赛区G题的题解。 很容易想到一个朴素的,O(n^2)的动态规划(把做KMP的时间当做常数)。 显然,这样做太慢了,要想想应该怎么优化。 关于字符串的匹配,很容易想到用后缀数组来优化。 但是只用后缀数组的话,还是没有用的。 要优化转移使每次转移的代价由O(n)变成O(logn)甚至O(1)。那么时间复杂度就自然降低了。 于是很容易就想到了线段树。 接着,把它们组合起来。 首先把输入的所有字符串连接起来,中间用’#’分割(这样可以减少用倍增法做后缀数组的时间复杂度的,不添加的话会超时,不过如果你是用其他一些O(n)的算法来构造后缀数组或者后缀树的话就可以不用分割)。 再做后缀数组。 然后开始动规。 用f[i]表示第一个单词为word[i]的最优解。 那么f[i]=max{f[j]|j>i and word[i] is a substring of word[j]}+W[i],可以用线段树来优化max操作。 设suffix(i)表示从第i位到最后所构成的后缀,rank[i]表示suffix(i)的排名,p[i]表示word[i]在拼接后的字符串中的位置,用len[i]表示word[i]的长度。 线段树记录排名在某个区间的所有串的开头部分(即’#’前部分)所在单词的f值。 求f[i]时,用二分法(需要利用高度数组,并需要用到RMQ)求得L=min{i|LCP(suffix(SA[j]),suffix(p[i]))=len[i]},R=max{i|LCP(suffix(SA[j]),suffix(p[i]))=len[i]}。 然后f[i]=排名在L到R之间的所有f的最大值+W[i],这一步用线段树来求。  最后更新线段树,将排名为rank[p[i]+j](0<=j<len[i])的f值更新为f[i]。 这道题就做出来了。 CODE: /* PROGRAM: $PROGRAM AUTHOR: Su Jiao DATE: 2011-11-10 DESCRIPTION: $DESCRIPTION */ #include <cstdio> #include <cstring> using namespace std;   namespace sujiaos_lab { const int LOG2_MAXLENGTH=19; const int MAXLENGTH=320003; […]

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]B.Break the Chocolate

2011年成都赛区B题的题解。 水题不解释。 CODE: /* PROGRAM: $PROGRAM AUTHOR: Su Jiao DATE: 2011-11-09 DESCRIPTION: $DESCRIPTION */ #include <iostream> using namespace std;   int cut(long long int x) {     for (int i=0;;i++)     {         if (x<=0) return i;         x-=1ll<<i;     } }   int main() {     int TC;     cin>>TC;     for (int tc=1;tc<=TC;tc++) […]

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]A.Alice and Bob

2011年成都赛区A题的题解。 这是一道博弈动规题目。 首先,我们把数字分成4类,1,,2,大于1的奇数,大于2的偶数。 一个大于3的奇数是等价于3的,因为,总可以对手减一个,你也减一个,就又变成了一个大于3的奇数或者3,总可以让它变成3。因此所有大于1的奇数都等价于3。同理,所有大于2的偶数等价于4。 所以我们用f[a][b][c][d]表示有a个1,b个2,c个3,d个4是不是一个必胜态,然后动规求解就好了。 CODE: /* PROGRAM: $PROGRAM AUTHOR: Su Jiao DATE: 2011-11-09 DESCRIPTION: $DESCRIPTION */ #include <iostream> using namespace std;   bool calced[51][51][51][51]; bool f[51][51][51][51]; int F(int a,int b,int c,int d) {     if (!calced[a][b][c][d])     {        if (a>=1&&!F(a-1,b,c,d)) f[a][b][c][d]=true;        if (b>=1&&!F(a+1,b-1,c,d)) f[a][b][c][d]=true;        if (c>=1&&!F(a,b+1,c-1,d)) f[a][b][c][d]=true;        if (d>=1&&!F(a,b,c+1,d-1)) f[a][b][c][d]=true; […]

OI的结束,ACM的开始[2011年10月26日]

去年的八月份,参加了NOI2010,以一枚银牌结束了自己的OI生涯,然后又回去参加了高考,可惜没考好啊,还不如当时现场保送走。(所以,能现场保送的同学们,最好还是直接走吧。) 然后,来到了人大,一个ACM弱校。不过也好,要是到清华北大复旦上交之类的学校就不那么容易进ACM队了。 在这个月,我有幸参加了2011 ACM/ICPC 上海赛区现场赛,和队友zx及wyw一起得到了一个银奖。也算我的ACM生涯的开始吧。 (附图,拿气球的是我。)  

我如何看待宗教

一个月前,我去见了我的一个老师,她告诉我她成基督徒了。当然我听到后的第一反应是吃惊,这是因为她是我认识的第一个基督徒,以前最多见到过信佛的。然后她送了两本书给我,一本是《圣经》,一本是里程写的《游子吟》,并让我去解放碑的圣爱堂听了一次证道。再加上最近看的很多美国的电影与基督教有关系,以及和同学的一次聊天,我觉得我差不多可以写这篇文章了。 1.我的信仰 在和同学的聊天中,她问我信什么,基督?科学?我的回答是,最理想的状况是都不信,是质疑一切。 为什么要质疑一切呢?因为不论是基督教的观点,科学的观点,都不过是为了解释那些终极问题(世界从何而来?我是谁?之类)而存在的学说,它们都可以差不多自圆其说,也都可以漏洞百出。 本质来说它们是相同的,盲目的相信任何一个都是迷信。而唯有质疑,我们才能接近“上帝”(请参考什么是“上帝”,以后文中加引号的上帝均指此意,以区别宗教意义上的上帝)。可能很多人都会把信教的人说成迷信的人,认为自己是无有神论者就怎样怎样。首先,你不能说明别人信的教是骗人的,虽然很多科学证据证明圣经中的很多历史事件根本是虚构的,但是那些证据是很容易被推翻的,比如有科学家用技术手段测出地球的年龄与《圣经》写的完全不同,但是很快就有人说如果上帝可以创造世界,他难道就不能在造地球时让它看起来比实际老些吗? 而我,可以说我是一个没有信仰的人,或者说我信“上帝”。 2.什么是“上帝” 其实上帝不只是宗教所说的那样,其实我们可以这样理解上帝,“上帝”是绝对真理,是宇宙发展的规律。 所以才说“上帝”创造了万物,“上帝”主宰这世界。并且如果有人违背“上帝”的旨意,就会受到惩罚。 3.为什么现在的人们更相信科学 就我看来,其原因应该是科学看起来更接近“上帝”,即科学看起来更接近绝对真理。 科学在乎一点,就是一个理论不光能解释过去,还能预言未来。而后者正是宗教的软肋,宗教的许多预言是经不起考验的。 然而能预言未来是很重要的,人类物质生活上的进步很大程度上依赖于此。 所以更相信科学的人越来越多。 4. 我眼中的宗教关于宗教中最受人质疑的问题,到底有没有神或者上帝。对于这个问题,正确的态度是我不知道。任何人都不能证明神或者上帝的存在与不存在,因为他们即使存在也是无法感知的,即他们的存在与不存在对我们来说看起来是没有区别的。当然,这里有一个例外,就是有些人讲他遇见过神或者上帝,如果他没说谎,他就知道神或者上帝是存在的,但是如果他来告诉你他遇见上帝了,你就需要质疑了。而还有一些更极端的哲学家提出了连人的感官都要质疑,如果到了这个程度,即使你真的见到神或者上帝也同样要质疑(比如,这可能是你的一个朋友玩的恶作剧)。也就是说如果你质疑一切,就不可能知道神或者上帝的存在与否。如果质疑宗教中关于神的那部分,那么通常就谈不上信教了,那宗教还有什么意义呢?并且虽然宗教在现在已然没有以前的地位了,但是为什么还有这么多人信教呢?我认为,其原因一部分是人们还有对科学的质疑,人们发现还有一些问题是科学无法解释的(比如宇宙起源,现在只有假说),还有一些科学所给出的结论是无法被接受的(比如进化论,有些人无法接受人是猴子的近亲这个结论,准确的说它还不能叫结论,而是假说);一部分是因为科学更多的满足了人的物质需求,而有点忽视人的精神需求;还有一部分就是迷信了。而我对宗教的态度更侧重于第二点,就是宗教可以丰富人的精神生活。在圣爱堂听证道时,看到了许多虔诚的基督教徒,融入其中听牧师讲,教徒应和,只是这样就会让我有一些内心的震撼。而牧师所讲的内容多是一些故事,或取自《圣经》,或取材于现实,都在传播着如何做一个好人。而这不就是在丰富人们的精神生活吗?它让人们觉得做一个普通好人的意义大于一个黑心富商或腐败贪官。当然宗教活动不只是讲这一点,这是我听的那次我得到的感悟。 而这些正是我认为的宗教在现在最大的意义。 对于《圣经》,我认为,读《圣经》时,应该质疑其内容的真实性(否则就是迷信了),不可否认的是它的确宣扬着一些正确的价值观,也不能否认其中落后的思想,要学会有自己的判断。如果能做到这点,就能够真正得到《圣经》所传达的一直都适用的道理(也就是说,忽略掉了那些只适用于旧时代的道理),才能够从中得到上帝的正确的启示。