Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 394 words)

hdu 3388 Coprime 容斥原理 二分查找

Coprime

刚开始不知道用二分，因为没有发现序列单调不下降的性质；
留意二分查找需找到下界。
二分查找起点的右边界取m*n是不够的，实际查找到的结果可能远大于该值。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/** Aug 27, 2015 9:25:32 PM
 * PrjName:hdu3388
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static Vector<Integer> v1=new Vector<Integer>();
    static Vector<Integer> v2=new Vector<Integer>();
    static HashSet<Integer> st=new HashSet<Integer>();
    static Integer[] fac=new Integer[0];
    static Vector<Integer> get_prime_factor(int n){
        Vector<Integer> res=new Vector<Integer>();
        res.clear();
        for(int i=2;i*i<=n;i++)
            if (n%i==0){
                res.add(i);
                while(n%i==0)
                    n/=i;
            }
        if (n>1) res.add(n);
        return res;
    }
    static long check(long n){
        long res=0L;
        int m=fac.length;
        for(int i=1;i<(1L<<m);i++){
            long tmp=1L;
            boolean tag=false;
            for(int j=0;j<m;j++)
                if (((1L<<j)&i)>0L){
                    tmp*=fac[j].longValue();
                    tag^=true;
                }
            res+=tag?n/tmp:-n/tmp;
        }
        return n-res;
    }
    static long bisearch(long low,long high,long key){
        long l=low,r=high,mid;
        while(l<r){
            mid=(l+r)>>1;
            if (check(mid)>=key)
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int m=in.nextInt();
            int n=in.nextInt();
            int k=in.nextInt();
            v1=get_prime_factor(m);
            v2=get_prime_factor(n);
            st.clear();
            for(Integer e:v1.toArray(new Integer[0]))
                st.add(e);
            for(Integer e:v2.toArray(new Integer[0]))
                st.add(e);
            fac=st.toArray(new Integer[0]);
            out.println("Case "+(++cas)+": "+bisearch(1, 0x3f3f3f3f3f3f3f3fL, k));
        }
        out.flush();
        out.close();
    }

}

较为神奇的是，把以上代码的check()函数（实现容斥原理的计算）替换为以下实现后，效率大有提升。

1
2
3
4
5
6
static long check(long n,int low){
        long sum=0L;
        for(int i=low;i<fac.length;i++)
            sum+=n/fac[i].longValue()-check(n/fac[i].longValue(),i+1);
        return sum;
    }
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 530 words)

hdu 4059 The Boss on Mars 容斥原理 数列通项公式

The Boss on Mars

为了高效求出数列的项 $ a_i=\sum\limits^n_{i=1} i^4 $，不使用通项公式是无法实现的。
另外实际分解所得的质因数的种类并不多，无需浪费大量时间、空间筛选大质数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/** Aug 27, 2015 2:45:37 PM
 * PrjName:hdu4059
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static PrintWriter out=new PrintWriter(System.out);
    static int maxn=105;
    static Vector<Integer> vec=new Vector<Integer>();
    static Vector<Integer> get_prime_factor(int n){
        Vector<Integer> res=new Vector<Integer>();
        for(int i=2;i*i<=n;i++)
            if (n%i==0){
                res.add(i);
                while(n%i==0)
                    n/=i;
            }
        if (n>1) res.add(n);
        return res;
    }
    final static long mod=1000000007L;
    static long pow(long n,long m,long mod){
        long res=1L;
        while(m>0L){
            if ((m&1L)>0L) res=res*n%mod;
            n=n*n%mod;
            m>>=1;
        }
        return res;
    }
    static long div(long a,long b,long mod){
        return a*pow(b,mod-2,mod)%mod;
    }
    static long sum(int n,long mod){
        long res=n;
        res*=2*n+1;res%=mod;
        res*=n+1;res%=mod;
        res*=(3L*n*n+3*n-1)%mod;res%=mod;
        return div(res,30,mod);
    }
    static long solve(Vector<Integer> vec,int n){
        long res=0L;
        int m=vec.size();
        for(int i=1;i<(1L<<m);i++){
            boolean tag=false;
            int tmp=1;
            for(int j=0;j<m;j++)
                if (((1L<<j)&i)>0){
                    tmp*=vec.get(j);
                    tmp%=mod;
                    tag^=true;
                }
            res=res+(tag?1:-1)*(pow(tmp,4,mod)*sum(n/tmp,mod)%mod);
            res%=mod;
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            Vector<Integer> v=get_prime_factor(n);
            out.println((sum(n,mod)-solve(v,n)+mod)%mod);
        }
        out.flush();
        out.close();
    }

}

另有一个未知的通过矩阵快速幂计算该数列项的方法（求以下矩阵的n次方）。
1 1 4 6 4 1
0 1 4 6 4 1
0 0 1 3 3 1
0 0 0 1 2 1
0 0 0 0 1 1
0 0 0 0 0 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void init()  
{  
    int i,j;  
    //构造矩阵  
    ONE.mat[1][1]=1;ONE.mat[1][2]=1;ONE.mat[1][3]=4;  
    ONE.mat[1][4]=6;ONE.mat[1][5]=4;ONE.mat[1][6]=1;  
    ONE.mat[2][1]=0;ONE.mat[2][2]=1;ONE.mat[2][3]=4;  
    ONE.mat[2][4]=6;ONE.mat[2][5]=4;ONE.mat[2][6]=1;  
    ONE.mat[3][1]=0;ONE.mat[3][2]=0;ONE.mat[3][3]=1;  
    ONE.mat[3][4]=3;ONE.mat[3][5]=3;ONE.mat[3][6]=1;  
    ONE.mat[4][4]=1;ONE.mat[4][5]=2;ONE.mat[4][6]=1;  
    ONE.mat[5][4]=0;ONE.mat[5][5]=1;ONE.mat[5][6]=1;  
    ONE.mat[6][6]=1;  
    yu[0]=0;  
    yu[1]=1;  
    LL x;  
    for(i=2;i<maxn;i++)//预处理1~200W的sum[x]  
    {  
        x=i%MOD;  
        x=x*i;  
        x=x%MOD;  
        x=x*i;  
        x=x%MOD;  
        x=x*i;  
        x=x%MOD;  
        yu[i]=yu[i-1]+x;  
        yu[i]=yu[i]%MOD;  
    }  
    AA[1]=ONE;  
    for(i=2;i<30;i++)AA[i]=AA[i-1]*AA[i-1];  
}

最后以这种方式取得计算结果(再乘上以下矩阵)：
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0 
1
2
3
4
5
6
7
8
9
10
matrix A;  
LL kan(LL x)//求sum[x]  
{  
    if(x<maxn)return yu[x];  
    matrix OP;  
    for(int i=1;i<=6;i++)OP.mat[i][1]=1;  
    A=powmul(ONE,x-1);  
    OP=A*OP;  
    return OP.mat[1][1];  
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 240 words)

hdu 4135 Co-prime 容斥原理

hdu 4135

具有教科书性质的容斥原理应用实例。
能不重复、不遗漏地选出所有合数，也就能得到质数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/** Aug 26, 2015 9:40:09 PM
 * PrjName:hdu4135
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static int maxn=1001;
    static int[] pri,fstp;
    static Vector<Integer> vec=new Vector<Integer>();
    static void get_prime(){
        pri=new int[maxn];
        fstp=new int[maxn];
        for(int i=2;i<maxn;i++){
            if (fstp[i]==0){
                pri[++pri[0]]=i;
            }
            for(int j=1;j<=pri[0]&&i*pri[j]<maxn;j++){
                int k=i*pri[j];
                fstp[k]=pri[j];
                if (i%pri[j]==0)
                    break;
            }
        }
    }
    static Vector<Integer> get_prime_factor(int n){
        Vector<Integer> res=new Vector<Integer>();
        res.clear();
        for(int i=1;i<=pri[0]&&pri[i]*pri[i]<=n;i++)
            if (n%pri[i]==0){
                res.add(pri[i]);
                while(n%pri[i]==0)
                    n/=pri[i];
            }
        if (n>1) res.add(n);
        return res;
    }
    static long solve(long n,Vector<Integer> vec){
        long res=0L;
        final int m=vec.size();
        for(long i=1L;i<(1L<<m);i++){
            boolean tag=false;
            long tmp=1L;
            for(int j=0;j<m;j++)
                if (((1L<<j)&i)>0){
                    tag^=true;
                    tmp*=vec.get(j).longValue();
                }
            res+=tag?n/tmp:-n/tmp;
        }
        return n-res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        get_prime();
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            long a=in.nextLong();
            long b=in.nextLong();
            int n=in.nextInt();
            vec=get_prime_factor(n);
            out.println("Case #"+(++cas)+": "+(solve(b,vec)-solve(a-1,vec)));
        }
        out.flush();
        out.close();
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 531 words)

2013 ACM/ICPC Asia Regional Chengdu Online

1007 F(x)数位DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/** Aug 22, 2015 5:23:42 PM
 * PrjName:hdu4734
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static int[][] f;
    static int[] digit;
    final static int maxm=4600;
    static int fun(int n){
        int res=0,tmp=1;
        while(n>0){
            res+=n%10*tmp;
            tmp<<=1;
            n/=10;
        }
        return res;
    }
    static void init(){
        int tmp=1;
        f=new int[10][maxm+1];
        f[0][0]=1;
        for(int i=1;i<10;i++){
            for(int j=0;j<=maxm;j++)
                for(int k=0;k<=9;k++)
                    if (j+tmp*k<=maxm)
                        f[i][j+tmp*k]+=f[i-1][j];
            tmp<<=1;
        }
        for(int i=0;i<10;i++)
            for(int j=1;j<=maxm;j++) f[i][j]+=f[i][j-1];
    }
    static int[] getdg(int n){
        int[] res=new int[10];
        while(n>0){
            res[++res[0]]=n%10;
            n/=10;
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        init();
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int A=in.nextInt();
            int B=in.nextInt();
            int m=fun(A);
            digit=getdg(B);
            int ans=0,tmp=1<<digit[0];
            for(int i=digit[0];i>=1;i--){
                tmp>>=1;
                for(int k=0;k<digit[i];k++){
                    
                    if (m-k*tmp>=0){
                        ans+=f[i-1][m-k*tmp];
                    }
                }
                m-=digit[i]*tmp;
                if (m<0) break;
                
            }
            if (m>=0) ans++;
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

磕磕绊绊的，到底有几大难？
期初是有过转化为背包问题的尝试，但是忽视了数位DP的处理手段；可先扩大枚举范围，再从中筛选。
预处理的两套循环不能杂糅在一起，因为先通过递推求了第i位、限制F(x)==j的解，然后才相加得到第i位、限制F(x)≤j的解。
筛选时注意“小于”的枚举方式。
最后还应留意B为可行解的条件。

1010 A Bit Fun

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/** Aug 22, 2015 4:28:18 PM
 * PrjName:hdu4737
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static int[] a;
    static Queue<Integer> que=new LinkedList<Integer>();
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int n=in.nextInt();
            int m=in.nextInt();
            a=new int[n+1];
            que.clear();
            int ans=0;
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                int k=que.size();
                for(int j=0;j<k;j++){
                    int tmp=que.poll()|a[i];
                    if (tmp<m) que.add(tmp);
                }
                if (a[i]<m) que.add(a[i]);
                ans+=que.size();
            }
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

并没有实现有些题解中所说的O(nlogn)或O(30n)的算法，但总的运行时间还是较短的？

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 338 words)

BestCoder

1001 Victor and Machine

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

  • Problem Description
    Victor has a machine. When the machine starts up, it will pop out a ball immediately. After that, the machine will pop out a ball every w seconds. However, the machine has some flaws, every time after x seconds of process the machine has to turn off for y seconds for maintenance work. At the second the machine will be shut down, it may pop out a ball. And while it’s off, the machine will pop out no ball before the machine restart.
    Now, at the 0 second, the machine opens for the first time. Victor wants to know when the n-th ball will be popped out. Could you tell him?

  • Input
    The input contains several test cases, at most 100 cases.
    Each line has four integers x, y, w and n. Their meanings are shown above。
    $ 1\leq x,y,w,n\leq 100 $ .

  • Output
    For each test case, you should output a line contains a number indicates the time when the n-th ball will be popped out.

  • Sample Input
    2 3 3 3
    98 76 54 32
    10 9 8 100

  • Sample Output
    10
    2664
    939

n-1的问题，自己刚开始出了点差错：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/** Aug 22, 2015 7:03:37 PM
 * PrjName:Bc52-01
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
        PrintWriter out=new PrintWriter(System.out);
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int x=(int)in.nval;
            in.nextToken();
            int y=(int)in.nval;
            in.nextToken();
            int w=(int)in.nval;
            in.nextToken();
            int n=(int)in.nval;
            if (n==1){
                out.println(0);continue;
            }
            if (w>x){
                out.println((n-1)*(x+y));continue;
            }
            else if (w==x){
                out.println((n-1)/2*(x+y)+(n-1)%2*x);continue;
            }
            else{
                int tmp=(x+w)/w;
                out.println((n-1)/tmp*(x+y)+(n-1)%tmp*w);continue;
            }
        }
        out.flush();
        out.close();
    }

}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga few seconds read (About 73 words)

Solving LCM【C0n,C1n, ,Cnn】

摘自《具体数学·计算机科学基础（英文版·第二版）》第5章习题及其解答：
0FF23C24-69C5-417E-BFA3-04CE6D477E87

BBACCBCF-BE37-40B5-8416-DD3FB5C6061A

$ \epsilon_p(n)$denotes the exponent of the prime p in the standard factorization of positive integer n.

$ \epsilon_p(n)$表示正整数n的因式分解中，质数p的指数。

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 466 words)

BestCoder

1001 Distribution money

WA过一发，因为忽视了金额的分布范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 2015年8月8日 下午7:02:20
 * PrjName:Bc50-01
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static int[] a;
    static int maxn=10001;
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
        PrintWriter out=new PrintWriter(System.out);
        a=new int[maxn];
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int n=(int)in.nval;
            Arrays.fill(a, 0);
            for(int i=1;i<=n;i++){
                in.nextToken();
                int k=(int)in.nval;
                a[k]++;
            }
            int ans=-1;
            for(int i=0;i<maxn;i++)
                if ((a[i]<<1)>n)
                    ans=i;
            //if (n>1)
                out.println(ans);
            //else 
                //out.println(-1);
        }
        out.flush();
        out.close();
    }
}

1002 Run

明显搞复杂了，做了一回出题人眼中的“火星人”T_T
平面上的整点就是无法构成正三角形、正五边形、正六边形，没这点见识就只有瞎弄。。。
简化到这个地步，正方形的判断就应该仔细点了吧？四条边及两对角线的长度比较都写上， 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Nov 19, 2015 7:32:18 PM
 * PrjName: hdu5365
 * @semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static Point[] pt;
    static boolean check(Point p1,Point p2,Point p3,Point p4){
        double[] v=new double[6];
        v[0]=Point.dist(p1, p2);
        v[1]=Point.dist(p2, p3);
        v[2]=Point.dist(p3, p4);
        v[3]=Point.dist(p1, p4);
        v[4]=Point.dist(p1, p3);
        v[5]=Point.dist(p2, p4);
        Arrays.sort(v);
        return v[0]==v[1]&&v[1]==v[2]&&v[2]==v[3]&&v[4]==v[5];
    }
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        while(in.nextLine()!=null){
            int n=in.nextInt();
            pt=new Point[n];
            for(int i=0;i<n;i++)
                pt[i]=new Point(in.nextInt(), in.nextInt());
            int ans=0;
            for(int i=0;i<n;i++)
                for(int j=i+1;j<n;j++)
                    for(int k=j+1;k<n;k++)
                        for(int l=k+1;l<n;l++){
                            Point p1=pt[i],p2=pt[j],p3=pt[k],p4=pt[l];
                            if (check(p1, p2, p3, p4))
                                ans++;
                        }
            out.println(ans);
        }
        out.flush();
        out.close();
    }
}

1003 The mook jong

多么有教育意义的猜公式，猜不出就别偏执了。。。
f[i]=s[i-3]+1,s[i]=s[i-1]+f[i],…

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 467 words)

Bestcoder

1001 Untitled

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 2015年8月1日 下午7:15:14
 * PrjName:Bc49-01
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static ArrayList<Integer> v=new ArrayList<Integer>();
    static int[] a,f;
    static int lowbit(int x){
        return x&(-x);
    }
    static int get(int x){
        int res=0;
        while(x>0){
            res++;
            x-=lowbit(x);
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            v.clear();
            int n=in.nextInt();
            int m=in.nextInt();
            for(int i=1;i<=n;i++)
                v.add(in.nextInt());
            Collections.sort(v);
            f=new int[1<<n];
            Arrays.fill(f, -1);
            f[0]=m;
            //out.println(n);
            int ans=Integer.MAX_VALUE;
            for(int i=0;i<(1<<n);i++)
                if (f[i]>0)
                    for(int j=0;j<n;j++)
                        if (((1<<j)&i)==0){
                            int k=i|(1<<j);
                            f[k]=f[i]%v.get(j);
                            if (f[k]==0)
                                ans=Math.min(ans, get(k));
                        }
            if (ans==Integer.MAX_VALUE) out.println(-1);
            else out.println(ans);
        }
        out.flush();
        out.close();
    }
}

1002 Three Palindromes

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

  • Problem Description
    Can we divided a given string S into three nonempty palindromes?

  • Input
    First line contains a single integer $ T \leq 20 $ which denotes the number of test cases.
    For each test case , there is an single line contains a string S which only consist of lowercase English letters. $ 1\leq |s| \leq 20000 $

  • Output
    For each case, output the “Yes” or “No” in a single line.

  • Sample Input
    2
    abc
    abaadada

  • Sample Output
    Yes
    No

赛时的Hash做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * 2015年8月1日 下午7:47:15
 * PrjName:Bc49-02
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static long pri=29L;
    static long lh(String s,long res,int p){
        return res*pri+(long)(s.charAt(p)-'a');
    }
    static long rh(String s,long res,int p,long m){
        return res+(long)(s.charAt(p)-'a')*m;
    }
    static BitSet v=new BitSet(20010);
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            String s=new String(in.next());
            int len=s.length();
            //s=s+"#"+(new StringBuffer(s).reverse().toString());
            //out.println(s);
            boolean ans=false;
            long l1=0L,r1=0L,tmp=1L;
            for(int i=0;i<len;i++){
                if (ans) break;
                l1=lh(s, l1, i);
                r1=rh(s, r1, i, tmp);
                //out.println(i+" "+l1+" "+r1);
                tmp*=pri;
                //if ((i&1)>0) continue;
                if (l1==r1){
                    //out.println("f"+i);
                    long l2=0L,r2=0L,tmp2=1L;
                    v.clear();
                    for(int j=i+1;j<len;j++){
                        l2=lh(s,l2,j);
                        r2=rh(s,r2,j,tmp2);
                        tmp2*=pri;
                        //if (((j-i+1)&1)>0) continue;
                        if (l2==r2) v.set(j);
                    }
                    
                    l2=0L;r2=0L;tmp2=1L;
                    for(int j=len-1;j>i;j--){
                        l2=lh(s,l2,j);
                        r2=rh(s,r2,j,tmp2);
                        tmp2*=pri;
                        //if (((len-j+1)&1)>0) continue;
                        if (l2==r2&&v.get(j-1)){
                            ans=true;break;
                        }
                    }
                }
            }
            out.println(ans?"Yes":"No");
        }
        out.flush();
        out.close();
    }
}

首次尝试去hack别人不成，还被人黑了，立马TLE

题解介绍的多种方法中，个人认为二分+hash代码量较少，如何实现？

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 156 words)

2015 Multi-University Training Contest 5

1009 MZL’s Border

字符串是可递归形式构造的，求解也是递归的；
但是递归时划分的三种情况，最终并没有做好化归 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
    static BigInteger f[] = new BigInteger[1005];
    public static void main(String[] args){
        f[1] = new BigInteger("1");
        f[2] = new BigInteger("2");
        for(int i = 3; i <= 1001; i++)
            f[i] = f[i - 1].add(f[i - 2]);
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        int n;
        BigInteger m;
        for(int cas = 1; cas <= T; cas++){
            n = cin.nextInt();
            m = cin.nextBigInteger();
            BigInteger mm = m.add(new BigInteger("1"));
            int p = 0;
            for(int i = 1; i <= 1001; i++){
                if(f[i].compareTo(mm) > 0){
                    p = i;
                    break;
                }
            }
            BigInteger ans = m.subtract(f[p - 2]);
            System.out.println(ans.mod(new BigInteger("258280327")));
        }
        
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 436 words)

2015 Multi-University Training Contest 4

1009 Walk Out

状态压缩方面，虽然想到了用一维的x+y替代二维的x,y，但并没有做到位。
既然可以转化成二维DP，还有何搜索必要
寻找合适的出发点时，不要陷入“极近点”而丢失了“最近点”！ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<cctype>

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int inf=0x7fffffff;
const double eps=1e-3;

typedef pair<int,int> pr;
const int dir[4][2]={ {0,-1},{0,1},{-1,0},{1,0}};
const int maxn=1010;
const int maxm=1010;
int n,m,X0,Y0;
bool g[maxn][maxm],f[maxn][maxm],vis[maxn][maxm];
char str[maxn];

bool can(int x,int y){
    if (x<1||x>n||y<1||y>m) return 0;
    return 1;
}
bool can(pr p){
    return can(p.first,p.second);
}
int mdis(int x,int y){
    return abs(x-n)+abs(y-m);
}
int mdis(pr p){
    return mdis(p.first,p.second);
}
int geth(pr p){
    return p.first+p.second;
}

void find0(int x,int y){
        if (vis[x][y]||!can(x,y)) return;
        vis[x][y]=1;
        if (g[x][y]) return;
        f[x][y]=1;
        if (x+y>X0+Y0)
        {
            X0=x;Y0=y;
        }
        for(int i=0;i<4;i++) find0(x+dir[i][0],y+dir[i][1]);
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {

        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            for(int j=1;j<=m;j++)
            {
                if (str[j]=='1') g[i][j]=1;
                else g[i][j]=0;
            }
        }

        X0=0;Y0=0;
        memset(vis[0],0,maxn*maxm*sizeof(vis[0][0]));
        memset(f[0],0,maxn*maxm*sizeof(f[0][0]));
        find0(1,1);
        //cout<<X0<<' '<<Y0<<endl;
        if (X0+Y0==n+m){
            printf("%d\n",0);
            continue;
        }
        if (X0+Y0<2)
        {
            X0=1;Y0=1;
            f[1][1]=1;
            printf("1");
        }
        for(int i=X0+Y0;i<n+m;i++)
        {
            int k=1;
            for(int j=max(1,i-m);j<=min(n,i-1);j++)
                if (f[j][i-j])
            {
                int k1=j<n?g[j+1][i-j]:1;
                int k2=i-j<m?g[j][i-j+1]:1;
                k=min(k,min(k1,k2));
            }
            for(int j=max(1,i-m);j<=min(n,i-1);j++)
                if (f[j][i-j])
            {
                int k1=j<n?g[j+1][i-j]:1;
                int k2=i-j<m?g[j][i-j+1]:1;
                if (k1==k) f[j+1][i-j]=1;
                if (k2==k) f[j][i-j+1]=1;
            }
            printf("%d",k);
        }
        puts("");
    }
    return 0;
}
Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview1
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python10
RMQ1
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×