Author Archives: boleyn.su

数学题。 首先可以证明有解当且仅当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 […]

水动规。 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; } […]

表达式求值+简单模拟。 继续练习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() […]

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)); } […]

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; […]

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; […]

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++) […]

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; […]

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

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