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

NOIP2010

最后一次NOIP了,390(最后一个程序dfs改快一点就可以400最后一个题有更好的算法,O(n^2)的)。 代码贴在这里,题解网上已经有了,就不必写了。 CODE: /* AUTHOR: Su Jiao DATE: 2010-11-20 DESCRIPTION: $DESCRIPTION */ #include <stdio.h>   #define PROBLEM “translate” FILE* file;   const int QUEUE_SIZE=1<<20; int M,N; int queue[QUEUE_SIZE]; bool in_queue[QUEUE_SIZE]; int head,tail; int answer;   int main() {     file=fopen(PROBLEM“.in”,“r”);     fscanf(file,“%d%d”,&M,&N);     for (int i=0;i<N;i++)     {         int word;         fscanf(file,“%d”,&word);         if […]

NOIP2009[Hankson的趣味题/son]

NOIP2010即将到来,这道题用来练练手感。 这道题的思路就是分解质因数。 首先,不难得到gcd(x/a1,a0/a1)=1以及gcd(b1/x,b1/b0)=1。 假设对于一个质因数y,a0含有a0c个y,a1含有a1c个y,b0含有b0c个y,b1含有b1c个y。 那么不难得到,如果a0c<a1c,那么就无解;如果a0c=a1c,那么x至少含有a1c个y;如果a0c>a1c,那么x只可能含有a1c个y。 同理,如果b1c<b0c,那么就无解;如果b1c=b0c,那么x至多含有b1c个y;如果b1c>b0c,那么x只可能含有b1c个y。 由此,可以求出对于每一个质数,x可能含有几个它,并求出一共有多少种选择方式。然后根据乘法原理,将每一个质数的选择方案数乘起来,就得到了答案。 CODE: /* AUTHOR: Su Jiao DATE: 2010-10-14 DESCRIPTION: $DESCRIPTION */ #include <stdio.h>   const int MAXSIZE=5000; int prime_table[MAXSIZE]; int prime_table_size; void initialize_prime_table() {     prime_table_size=0;     prime_table[prime_table_size++]=2;     for (int i=3;prime_table_size<MAXSIZE;i++)     {         bool is_prime=true;         for (int j=0;j<prime_table_size;j++)             if (i%prime_table[j]==0)             {                is_prime=false;              […]

SGU107[987654321 problem]

先离线处理出在[0,10^9)内中所有平方末尾数为987654321的数,然后显然应该写成下面那样。 CODE: /* AUTHOR: Su Jiao DATE: 2010-9-11 DESCRIPTION: $DESCRIPTION */ #include <stdio.h>   int main() {     /*     for (long long int i=0;i<1000000000;i++)         if (i*i%1000000000==987654321) printf(“%d\n”,int(i));     output:     111111111     119357639     380642361     388888889     611111111     619357639     880642361     888888889     */     int n;     scanf(“%d”,&n);     […]

SGU106[The equation]

数学题。扩展欧几里得解模同余方程。 CODE: /* AUTHOR: Su Jiao DATE: 2010-8-26 DESCRIPTION: $DESCRIPTION */ #include <iostream> #include <math.h> using namespace std;   #define lli long long int #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define ceil_div(a,b) ceil(double(a)/double(b)) #define floor_div(a,b) floor(double(a)/double(b))   lli gcd(lli a,lli b,lli& x,lli& y) {     //ax+by=gcd(a,b)     if (b==0)     {        x=1,y=0;        return […]