URAL1104[Don’t Ask Woman about Her Age]

数学题,需要知道(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 […]

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生涯的开始吧。 (附图,拿气球的是我。)