Author Archives: boleyn.su

数学题，需要知道(a*k^n)mod(k-1)=a，即sum{a[i]*k^i}mod(k-1)=sum{a[i]}。 其实不知道也可以做。 继续练习Java。 CODE: /*PROGRAM: $PROGRAMAUTHOR: Su JiaoDATE: 2011-11-18DESCRIPTION:$DESCRIPTION*/import java.io.*;import java.util.*;public class Ural { public static void main(String args[]) { new Ural(); } public int c2i(char c) { if (‘A'<=c&&c<=’Z’) return (int)(c-‘A’)+10; else return (int)(c-‘0’); } public Ural() { Scanner cin=new Scanner(new BufferedInputStream(System.in)); String s=cin.nextLine(); int sum=0; int mink=2; for (int i=0;i<s.length();i++) { sum+=c2i(s.charAt(i)); if […]

数学题。 首先可以证明有解当且仅当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生涯的开始吧。 （附图，拿气球的是我。）