Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing7 minutes read (About 1110 words)

hdu 5130 2014 ACM/ICPC Regional Guangzhou 计算几何

由高中平面解析几何得：平面某一点P与两点A、B满足|PA|=k|PB|，则点P的轨迹是一个圆。
所以应求多边形与圆的公共面积，可将多边形分解为三角形来求。

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
/** Sep 9, 2015 3:23:33 PM
 * PrjName:hdu5130
 * @author Semprathlon
 */
import java.util.*;
import java.io.*;
public class Main {

    /**
     * @param args
     */
    static double sqr(double x){
        return x*x;
    }
    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 cas=0;
        while(in.nextLine()!=null){
            int n=in.nextInt();
            double k=in.nextDouble();
            Polygon pl=new Polygon(n);
            for(int i=0;i<n;i++)
                pl.v[i]=new Point(in.nextInt(), in.nextInt());
            pl.v[n]=pl.v[0];
            Point A=new Point(in.nextDouble(),in.nextDouble());
            Point B=new Point(in.nextDouble(), in.nextDouble());
            Point O=new Point(-(B.x-k*k*A.x)/(k*k-1), -(B.y-k*k*A.y)/(k*k-1));
            double r=Math.sqrt(sqr((B.x-k*k*A.x)/(k*k-1))+sqr((B.y-k*k*A.y)/(k*k-1))-k*k*(sqr(A.x)+sqr(A.y))/(k*k-1)+(sqr(B.x)+sqr(B.y))/(k*k-1));
            Round R=new Round(r, O.x, O.y);
            double ans=0;
            for(int i=0;i<n;i++)
                ans+=Round.TriAngleCircleInsection(R, pl.v[i], pl.v[i+1]);
            out.println(String.format("Case %d: %.6f", ++cas,Math.abs(ans)));
            //out.println(r+" "+O.x+" "+O.y);
            //out.println(R.GetCirclePolyIntersectionArea(pl));
        }
        out.flush();
        out.close();
    }

}
class Point {
    double x, y;

    Point() {}
    Point(double _x, double _y) {}
    Point(Point p) {}
    Point add(Point r) {}
    Point sub(Point r) {}
    Point mul(double r) {}
    Point move(double dx, double dy) {}
    Point rotate(double a) {}
    Point rotate(double dx, double dy, double a) {}
    static Point mid(Point a, Point b) {}
    static double dist(Point a, Point b) {}
    public boolean equals(Point p) {}
    static void swap(Point a, Point b) {}
    static class Comp implements Comparator<Point> {}

    final static double eps = 1e-3;
    static int dcmp(double d) {
        if (Math.abs(d) < eps)
            return 0;
        return d > 0 ? 1 : -1;
    }

}
class Vector extends Point {
    Vector() {}
    Vector(double _x, double _y) {}
    Vector(Point a, Point b) {}
    Vector(Point p) {}
    static double angle(Vector a, Vector b) {}
    static double angle(Point a, Point b) {}
    static double angle(Point o, Point a, Point b) {}
    double dot(Vector r) {}
    double cross(Vector r) {}
    double length() {}
    Vector normal() {}
    static Point GetLineIntersection(Point p, Vector v, Point q, Vector w) {}
    static Point GetLineIntersection(Point p, Point v, Point q, Point w) {}
    static Vector add(Vector a, Vector b) {}
    static double dot(Vector a, Vector b) {}
    static double cross(Vector a, Vector b) {}
    static double cross(Point a, Point b) {}
    static double cross(Point o, Point a, Point b) {}
    static double cross(Point a, Point b, Point c, Point d) {}
    static double length(Vector r) {}
}
class Line extends Vector {
    Point s, e;

    Line() {}
    Line(Point _s, Point _e) {}
    Line(double x1, double y1, double x2, double y2) {}
    Vector vector(){}
    static boolean isLineInter(Line l1, Line l2) {}
    static boolean isSegInter(Point s1, Point e1, Point s2, Point e2) {}
    static boolean isSegInter2(Point p1, Point p2, Point p3, Point p4){}
    static boolean isSegInter(Line l1, Line l2) {}
    static boolean isSegInter2(Line l1, Line l2) {}
}
class Polygon extends Vector {
    int num;
    Point[] v;
    Polygon() {}
    Polygon(int n) {}

    boolean IsConvexBag() {
        int direction = 0;// 1:右手正螺旋，逆时针 -1:左手正螺旋，顺时针
        for (int i = 0; i < num; i++) {
            int tmp = dcmp(cross(v[i], v[i + 1], v[i + 1], v[i + 2]));

            if (direction == 0) // 避免最初的点出现共线的情况
                direction = tmp;

            if (direction * tmp < 0) // 只要Vec是凸包，那么无论Vec的旋转方向如何，direction*temp都会>=0
                return false;
        }
        return true;
    }

}
class Round extends Vector {
    double r;
    Point o;
    final static double pi = Math.acos(-1.0);

    Round(double _r, double _x, double _y) {}
    static double Rad2Deg(double rad) {}
    static double Deg2Rad(double deg) {}
    double Area() {}

    static double CommonArea(Round A, Round B) {
        double area = 0.0;
        Round M = dcmp(A.r - B.r) > 0 ? A : B;
        Round N = dcmp(A.r - B.r) > 0 ? B : A;
        double D = dist(M.o, N.o);
        if (dcmp(M.r + N.r - D) > 0 && dcmp(M.r - N.r - D) < 0) {
            double cosM = (M.r * M.r + D * D - N.r * N.r) / (2.0 * M.r * D);
            double cosN = (N.r * N.r + D * D - M.r * M.r) / (2.0 * N.r * D);
            double alpha = 2.0 * Math.acos(cosM);
            double beta = 2.0 * Math.acos(cosN);

            double TM = 0.5 * M.r * M.r * Math.sin(alpha);
            double TN = 0.5 * N.r * N.r * Math.sin(beta);
            double FM = 0.5 * alpha / pi * M.Area();
            double FN = 0.5 * beta / pi * N.Area();
            area = FM + FN - TM - TN;
        } else if (dcmp(M.r - N.r - D) >= 0) {
            area = N.Area();
        }
        return area;
    }

    /* 判断圆与多边形的关系 */
    boolean IsFitPoly(Polygon pl) {
        for (int i = 0; i <= pl.num; i++) {
            int k = dcmp(Math.abs(cross(o, pl.v[i], o, pl.v[i + 1]) / dist(pl.v[i], pl.v[i + 1])) - r);
            if (k < 0)
                return false;
        }
        return true;
    }

    boolean IsInPoly(Polygon pl) {
        double CircleAngle = 0.0; // 环绕角
        for (int i = 1; i <= pl.num; i++) // 注意重复边不计算
            if (dcmp(cross(o, pl.v[i], o, pl.v[i + 1])) >= 0)
                CircleAngle += angle(o, pl.v[i], pl.v[i + 1]);
            else
                CircleAngle -= angle(o, pl.v[i], pl.v[i + 1]);

        if (dcmp(CircleAngle) == 0) // CircleAngle=0, Peg在多边形外部
            return false;
        else if (dcmp(CircleAngle - pi) == 0 || dcmp(CircleAngle + pi) == 0) // CircleAngle=180,
                                                                                // Peg在多边形边上(不包括顶点)
        {
            if (dcmp(r) == 0)
                return true;
        } else if (dcmp(CircleAngle - 2 * pi) == 0 || dcmp(CircleAngle + 2 * pi) == 0) // CircleAngle=360,
                                                                                        // Peg在多边形边内部
            return true;
        else // CircleAngle=(0,360)之间的任意角， Peg在多边形顶点上
        {
            if (dcmp(r) == 0)
                return true;
        }
        return false;
    }
    
    static double TriAngleCircleInsection(Round C, Point A, Point B)
    {
        Vector OA = new Vector(A.sub(C.o)), OB = new Vector(B.sub(C.o));
        Vector BA = new Vector(A.sub(B)), BC = new Vector(C.o.sub(B));
        Vector AB = new Vector(B.sub(A)), AC = new Vector(C.o.sub(A));
        double DOA = OA.length(), DOB = OB.length(),DAB = AB.length(), r = C.r;
        if(dcmp(cross(OA,OB)) == 0) return 0;
        if(dcmp(DOA-C.r) < 0 && dcmp(DOB-C.r) < 0) return cross(OA,OB)*0.5;
        else if(dcmp(DOB-r)<0 && dcmp(DOA-r) >= 0) {
            double x = (dot(BA,BC) + Math.sqrt(r*r*DAB*DAB-cross(BA,BC)*cross(BA,BC)))/DAB;
            double TS = cross(OA,OB)*0.5;
            return Math.asin(TS*(1-x/DAB)*2/r/DOA)*r*r*0.5+TS*x/DAB;
        }
        else if(dcmp(DOB-r) >=0 && dcmp(DOA-r) <0 ) {
            double y = (dot(AB,AC)+Math.sqrt(r*r*DAB*DAB-cross(AB,AC)*cross(AB,AC)))/DAB;
            double TS = cross(OA,OB)*0.5;
            return Math.asin(TS*(1-y/DAB)*2/r/DOB)*r*r*0.5+TS*y/DAB;
        }
        else if(dcmp(Math.abs(cross(OA,OB))-r*DAB)>=0 || dcmp(dot(AB,AC)) <= 0 || dcmp(dot(BA,BC)) <= 0) {
            if(dcmp(dot(OA,OB)) < 0) {
                if(dcmp(cross(OA,OB)) < 0) return (-Math.acos(-1.0)-Math.asin(cross(OA,OB)/DOA/DOB))*r*r*0.5;
                else                 return ( Math.acos(-1.0)-Math.asin(cross(OA,OB)/DOA/DOB))*r*r*0.5;
            }
            else                     return Math.asin(cross(OA,OB)/DOA/DOB)*r*r*0.5;
        }
        else {
            double x = (dot(BA,BC)+Math.sqrt(r*r*DAB*DAB-cross(BA,BC)*cross(BA,BC)))/DAB;
            double y = (dot(AB,AC)+Math.sqrt(r*r*DAB*DAB-cross(AB,AC)*cross(AB,AC)))/DAB;
            double TS = cross(OA,OB)*0.5;
            return (Math.asin(TS*(1-x/DAB)*2/r/DOA)+Math.asin(TS*(1-y/DAB)*2/r/DOB))*r*r*0.5 + TS*((x+y)/DAB-1);
        }
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 225 words)

hdu 2203 亲和串 KMP

亲和串

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
/** Sep 8, 2015 10:56:55 PM
 * PrjName:hdu2203
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    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);
        while(in.nextLine()!=null){
            String s=in.next();
            s=new String(s+s);
            String t=in.next();
            out.println(KMP.Index(s, t)>-1?"yes":"no");
        }
        out.flush();
        out.close();
    }

}
class KMP{
    static int next[];
    static void getNext(String T){
        next=new int[T.length()+1];
        int j = 0, k = -1; next[0] = -1;
        while(j < T.length())
            if(k == -1 || T.charAt(j) == T.charAt(k))
                next[++j] = ++k;
            else
                k = next[k];
    }
    static int Index(String S,String T)
    {
        int i = 0, j = 0;
        getNext(T);
        
        for(i = 0; i < S.length()&&j<T.length(); i++)
        {
            while(j > 0 && S.charAt(i) != T.charAt(j))
                j = next[j];
            if(S.charAt(i) == T.charAt(j))
                j++;
        }
        if(j == T.length())
            return i - T.length();
        else
            return -1;
    }
    static int Count(String S,String T)
    {
        int res = 0,j=0;
        if(S.length() == 1 && T.length() == 1)
        {
            if(S.charAt(0) == T.charAt(0))
                return 1;
            else
                return 0;
        }
        getNext(T);
        for(int i = 0; i < S.length(); i++)
        {
            while(j > 0 && S.charAt(i) != T.charAt(j))
                j = next[j];
            if(S.charAt(i) == T.charAt(j))
                j++;
            if(j == T.length())
            {
                res++;
                j = next[j];
            }
        }
        return res;
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 299 words)

hdu 2222 Keywords Search AC自动机

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
/** Sep 8, 2015 8:34:27 PM
 * PrjName:hdu2222
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {

    /**
     * @param args
     */
    static AC ac = new AC();

    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) {
            int n = in.nextInt();
            ac.clear();
            for (int i = 1; i <= n; i++)
                ac.insert(in.next());
            ac.build();
            out.println(ac.query(in.next()));
        }
        out.flush();
        out.close();
    }

}

class AC {
    final int maxl = 500010, maxc = 26;
    final char fstc = 'a';
    int root, L;
    int[][] next;
    int[] fail, end;
    Queue<Integer> que = new LinkedList<Integer>();

    AC() {
        next = new int[maxl][maxc];
        fail = new int[maxl];
        end = new int[maxl];
        L = 0;
        root = newnode();
    }

    void clear() {
        Arrays.fill(fail, 0);
        Arrays.fill(end, 0);
        L = 0;
        root = newnode();
    }

    int newnode() {
        Arrays.fill(next[L], -1);
        end[L++] = 0;
        return L - 1;
    }

    void insert(String str) {
        int now = root;
        for (int i=0;i<str.length();i++) {
            char ch=str.charAt(i);
            if (next[now][ch - fstc] == -1)
                next[now][ch - fstc] = newnode();
            now = next[now][ch - fstc];
        }
        end[now]++;
    }

    void build() {
        que.clear();
        fail[root] = root;
        for (int i = 0; i < maxc; i++)
            if (next[root][i] == -1)
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.add(next[root][i]);
            }
        while (!que.isEmpty()) {
            int now = que.poll();
            for (int i = 0; i < maxc; i++)
                if (next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.add(next[now][i]);
                }
        }
    }

    int query(String str) {
        int now = root, res = 0;
        for (int i=0;i<str.length();i++) {
            char ch=str.charAt(i);
            now = next[now][ch - fstc];
            int tmp = now;
            while (tmp != root) {
                res += end[tmp];
                 end[tmp] = 0;
                tmp = fail[tmp];
            }
        }
        return res;
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 220 words)

hdu 1204 糖果大战 概率过程

hdu 1204

通过本题接触到了存在于《概率论与数理统计》教材，但是不在学校教学范围内的概率过程知识。
接受这种新的认知，才能避免落入高中局限的概率观的窠臼。 

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
/** Sep 5, 2015 9:45:04 PM
 * PrjName:hdu1204
 * @author Semprathlon
 */
import java.awt.Toolkit;
import java.io.*;
import java.util.*;
public class Main {
    /**
     * @param args
     */
    static double pow(double n,int m){
        double res=1;
        while(m>0){
            if ((m&1)>0) res=res*n;
            n=n*n;
            m>>=1;
        }
        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);
        while(in.nextLine()!=null){
            int n=in.nextInt();
            int m=in.nextInt();
            double p=in.nextDouble();
            double q=in.nextDouble();
            if (n==0)
                out.println("0.00");
            else if (m==0)
                out.println("1.00");
            else if (p==0||q==1)
                out.println("0.00");
            else if (p==1||q==0)
                out.println("1.00");
            else{
                double k=q*(1.0-p)/p/(1.0-q);
                double ans=p==q?n*1.0/(m+n):(1.0-pow(k, n))/(1.0-pow(k, n+m));
                out.println(String.format("%.2f", ans));
            }
        }
        out.flush();
        out.close();
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 640 words)

Bestcoder

1001 A problem of sorting

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
/** Sep 5, 2015 7:07:52 PM
 * PrjName:Bc54-01
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    final static int maxn=116;
    static String s;
    static Vector<String>[] vec=new Vector[maxn];
    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);
        for(int i=0;i<maxn;i++)
            vec[i]=new Vector<String>();
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        while(T-->0){
            for(int i=0;i<maxn;i++)
                vec[i].clear();
            int n=Integer.parseInt(br.readLine());
            for(int i=1;i<=n;i++){
                s=new String(br.readLine());
                int y=0,tmp=1,j;
                for(j=s.length()-1;j>0;j--)
                    if (s.charAt(j)>='0'&&s.charAt(j)<='9'){
                        y+=tmp*(s.charAt(j)-'0');
                        tmp*=10;
                    }
                    else 
                        break;
                s=s.substring(0, j);
                vec[y-1900].add(s);
            }
            for(int i=maxn-1;i>=0;i--)
                for(int j=0;j<vec[i].size();j++)
                    out.println(vec[i].get(j));
        }
        out.flush();
        out.close();
    }
}

1002 The Factor

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
/** Sep 5, 2015 7:30:23 PM
 * PrjName:Bc54-02
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    final static int maxn=109000;
    static int[] a;
    static int[] pri,phi,fstp;
    static void get_prime(){
        pri=new int[maxn];
        fstp=new int[maxn];
        phi=new int[maxn];
        phi[1]=1;
        for(int i=2;i<maxn;i++){
            if (fstp[i]==0){
                pri[++pri[0]]=i;
                phi[i]=i-1;
            }
            for(int j=1;j<=pri[0]&&i*pri[j]<maxn;j++){
                int k=i*pri[j];
                fstp[k]=pri[j];
                //if (fstp[i]==pri[j]){
                if (i%pri[j]==0){
                    phi[k]=phi[i]*pri[j];
                    break;
                }
                else
                    phi[k]=phi[i]*(pri[j]-1);
            }
        }
    }
    static int get_fstp(int n){
        if (n<maxn)
            return fstp[n]>0?fstp[n]:n;
        for(int i=2;i<maxn;i++)
            if (n%i==0)
                return fstp[i]>0?fstp[i]:i;
        return 0;
    }
    static Vector<Integer> get_prime_factor(int n){
        Vector<Integer> res=new Vector<Integer>();
        while(n>1&&fstp[n]>0){
            res.add(fstp[n]);
            n/=fstp[n];
        }
        if (n>1) res.add(n);
        return res;
    }
    static Vector<Integer> v=new Vector<Integer>();
    static Integer[] f;
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        get_prime();
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            v.clear();
            a=new int[n+1];
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                if (a[i]==1) continue;
                int tmp=get_fstp(a[i]);
                v.add(tmp);
                if (a[i]/tmp>1) v.add(get_fstp(a[i]/tmp));
            }
            /*v.sort(new Comparator<Integer>() {
                public int compare(Integer o1,Integer o2){
                    return Integer.compare(o1, o2);
                }
            });*/
            f=v.toArray(new Integer[0]);
            Arrays.sort(f);
            if (v.size()<2)
                out.println(-1);
            else 
                out.println(f[0]*f[1]);
        }
        out.flush();
        out.close();
    }
}

⬆️当时想太多了啊，何必把找到的因子全存进vector啊，白白吃了个RE……
（测试还发现HDU尚不支持Vector的sort方法，还未支持到Java7？）

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
/** Sep 8, 2015 16:02:23 PM
 * PrjName:Bc54-02
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    final static int maxn=45000;
    static int[] a;
    static int[] pri,fstp;
    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 int get_fstp(int n){
        if (n<maxn)
            return fstp[n]>0?fstp[n]:n;
        for(int i=2;i<maxn;i++)
            if (n%i==0)
                return fstp[i]>0?fstp[i]:i;
        return n;
    }
    static int max1,max2,sum;
    static void init(){
        max1=max2=0x3fffffff;sum=0;
    }
    static void update(int s){
        if (s<max1){
            max2=max1;max1=s;
        }
        else 
            max2=Math.min(max2, s);
        sum++;
    }
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        get_prime();
        int T=in.nextInt();
        while(T-->0){
            init();
            int n=in.nextInt();
            a=new int[n+1];
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                if (a[i]==1) continue;
                int tmp=get_fstp(a[i]);
                update(tmp);
                if (a[i]/tmp>1) update(get_fstp(a[i]/tmp));
            }
            if (sum<2)
                out.println(-1);
            else 
                out.println(max1*(long)max2);
        }
        out.flush();
        out.close();
    }
}

1003 Geometric Progression

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
/** Sep 5, 2015 8:05:33 PM
 * PrjName:Bc54-03
 * @author Semprathlon
 */
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
    final static int maxn=101;
    static BigInteger a[]=new BigInteger[maxn];
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            boolean zero=false,nonzero=false;
            for(int i=1;i<=n;i++){
                a[i]=new BigInteger(in.next());
                if (a[i].equals(BigInteger.ZERO))
                    zero|=true;
                else
                    nonzero|=true;
            }
            boolean ans=(zero&&nonzero)?false:true;
            if (ans)
            for(int i=2;i<n;i++)
                if (!a[i].pow(2).equals(a[i-1].multiply(a[i+1]))){
                    ans=false;
                    break;
                }
            out.println(ans?"Yes":"No");
        }
        out.flush();
        out.close();
    }
}

不明不白地送了个WA，没有考虑好数列中值为0的项。
这题不是暑假多校才做过的么？

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing7 minutes read (About 1018 words)

2014 ACM/ICPC Asia Regional Anshan Online

hdu 5001 Walk 概率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
/** Sep 2, 2015 8:29:38 PM
 * PrjName:hdu5001
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	static int n, m, d;
	static int[] deg;
	static int[][] u;
	static double[][] f;

	static double solve(int x) {
		f = new double[d + 1][n + 1];
		for (int i = 1; i <= n; i++)
			f[0][i] = 1.0 / n;
		for (int i = 1; i <= d; i++)
			for (int j = 1; j <= n; j++) {
				if (j == x)
					continue;
				for (int k = 1; k <= u[j][0]; k++)
					f[i][u[j][k]] += f[i - 1][j] / u[j][0];
			}
		double ans = 0;
		for (int i = 1; i <= n; i++)
			if (i != x)
				ans += f[d][i];
		return ans;
	}

	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) {
			n = in.nextInt();
			m = in.nextInt();
			d = in.nextInt();
			u = new int[n + 1][m + 1];
			deg = new int[n + 1];
			for (int i = 1; i <= m; i++) {
				int x = in.nextInt();
				deg[x]++;
				int y = in.nextInt();
				deg[y]++;
				u[x][++u[x][0]] = y;
				u[y][++u[y][0]] = x;
			}

			for (int i = 1; i <= n; i++)
				out.println(String.format("%.6f", solve(i)));
		}
		out.flush();
		out.close();
	}

}

不知为何，printf+格式字符串会出现莫名的PE

hdu 4998 Rotate

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
/** Sep 2, 2015 5:58:24 PM
 * PrjName:hdu4998
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	final static double eps = 1e-5;
	final static double pi = Math.acos(-1.0);

	static int dcmp(double d) {
		if (Math.abs(d) < eps)
			return 0;
		return d > 0 ? 1 : -1;
	}

	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) {
			int n = in.nextInt();
			Point p1 = new Point(0, 0), q1 = new Point(p1);
			Point p2 = new Point(0, 1), q2 = new Point(p2);
			for (int i = 1; i <= n; i++) {
				double x = in.nextDouble();
				double y = in.nextDouble();
				double a = in.nextDouble();
				q1 = q1.rotate(x, y, a);
				q2 = q2.rotate(x, y, a);
			}
			Vector v1 = new Vector(p1, q1).normal();
			Vector v2 = new Vector(p2, q2).normal();
			Point o = Vector.GetLineIntersection(Point.mid(p1, q1), v1, Point.mid(p2, q2), v2);
			double ans = Vector.angle(o, p1, q1);
			if (Vector.cross(new Vector(o, p1), new Vector(o, q1)) < 0)
				ans = 2 * pi - ans;
			out.printf("%.5f %.5f %.5f\n", o.x, o.y, ans);
		}
		out.flush();
		out.close();
	}

	static class Point {
		double x, y;

		Point() {
		}

		Point(double _x, double _y) {
			x = _x;
			y = _y;
		}

		Point(Point p) {
			this(p.x, p.y);
		}

		boolean equals(Point p) {
			return dcmp(x - p.x) == 0 && dcmp(y - p.y) == 0;
		}

		Point add(Point r) {
			return new Point(x + r.x, y + r.y);
		}

		Point sub(Point r) {
			return new Point(x - r.x, y - r.y);
		}

		Point mul(double r) {
			return new Point(x * r, y * r);
		}

		Point move(double dx, double dy) {
			return new Point(x + dx, y + dy);
		}

		Point rotate(double a) {
			return new Point(x * Math.cos(a) - y * Math.sin(a), x * Math.sin(a) + y * Math.cos(a));
		}

		Point rotate(double dx, double dy, double a) {
			return this.move(-dx, -dy).rotate(a).move(dx, dy);
		}

		static Point mid(Point a, Point b) {
			return new Point((a.x + b.x) / 2.0, (a.y + b.y) / 2.0);
		}
	}

	static class Vector extends Point {
		Vector(double _x, double _y) {
			x = _x;
			y = _y;
		}

		Vector(Point a, Point b) {
			this(b.x - a.x, b.y - a.y);
		}

		Vector(Point p) {
			this(p.x, p.y);
		}

		static double angle(Vector a, Vector b) {
			return Math.acos(dot(a, b) / a.length() / b.length());
		}

		static double angle(Point o, Point a, Point b) {
			return angle(new Vector(o, a), new Vector(o, b));
		}

		double dot(Vector r) {
			return x * r.x + y * r.y;
		}

		double cross(Vector r) {
			return x * r.y - y * r.x;
		}

		double length() {
			return Math.sqrt(this.dot(this));
		}

		Vector normal() {
			double len = this.length();
			return new Vector(-y / len, x / len);
		}

		static Point GetLineIntersection(Point p, Vector v, Point q, Vector w) {// 求直线交点
			Vector u = new Vector(p.sub(q));
			double t = cross(w, u) / cross(v, w);
			return p.add(v.mul(t));
		}

		static Point GetLineIntersection(Point p, Point v, Point q, Point w) {
			return GetLineIntersection(p, new Vector(v), q, new Vector(w));
		}

		static Vector add(Vector a, Vector b) {
			return new Vector(a.add(b));
		}

		static double dot(Vector a, Vector b) {
			return a.dot(b);
		}

		static double cross(Vector a, Vector b) {
			return a.cross(b);
		}

		static double cross(Point o, Point a, Point b) {
			return cross(new Vector(o, a), new Vector(o, b));
		}

		static double length(Vector r) {
			return r.length();
		}
	}
}

说得好像很繁的样子

hdu 5000

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
/** Sep 3, 2015 9:43:43 PM
 * PrjName:hdu5000
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    final static int mod=1000000007;
    static int[] a,f;
    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){
            int n=in.nextInt();
            int sum=0;
            a=new int[n+1];
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                sum+=a[i];
            }
            sum>>=1;
            f=new int[sum+1];
            f[0]=1;
            for(int i=1;i<=n;i++)
                for(int j=sum;j>=0;j--)
                    for(int k=1;k<=j&&k<=a[i];k++){
                        f[j]+=f[j-k];
                        f[j]%=mod;
                    }
            out.println(f[sum]);
        }
        out.flush();
        out.close();
    }

}
class InputReader{
    public BufferedReader reader;
    public StringTokenizer tokenizer;
 
    public InputReader(InputStream stream){
           reader = new BufferedReader(
                   new InputStreamReader(stream), 32768);
           tokenizer = null;
    }
 
    public String next(){
        while(tokenizer == null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(
                           reader.readLine());
            }catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
 
    public int nextInt() {
        return Integer.parseInt(next());
    }
     
    public long nextLong() {
        return Long.parseLong(next());
    }
 
}

非常奇怪，找到sum/2可得最优解这个规律就算是成功了一半了

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

hdu 2089 数位dp

不要62

具有教科书性质的数位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
/** Aug 31, 2015 9:57:30 PM
 * PrjName:hdu2089
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    /**
     * @param args
     */
    final static int maxl=7;
    static int[][] f;
    static int[] digit;
    static void init(){
        f=new int[maxl+1][10];
        f[0][0]=1;
        for(int i=1;i<=maxl;i++)//从低位到高位！
            for(int j=0;j<10;j++)
                for(int k=0;k<10;k++)
                    if (k!=4&&!(j==6&&k==2))
                        f[i][j]+=f[i-1][k];
    }
    static int solve(int n){
        //if (n==0) return 1;
        digit=new int[maxl+1];
        while(n>0){
            digit[++digit[0]]=n%10;
            n/=10;
        }
        int res=0;
        for(int i=digit[0];i>0;i--){//从高位到低位！
            for(int j=0;j<digit[i];j++)
                if(j!=4&&!(j==2&&digit[i+1]==6))//限制前j位，枚举后digit[0]-j位
                    res+=f[i][j];
            if(digit[i]==4||digit[i]==2&&digit[i+1]==6) break;
        }
        return res;
    }
    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);
        init();
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int n=(int)in.nval;
            in.nextToken();
            int m=(int)in.nval;
            if (n==0&&m==0) break;
            //out.println(solve(n)+" "+solve(m+1));
            out.println(solve(m+1)-solve(n));
        }
        out.flush();
        out.close();
    }
}
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
/** Sep 1, 2015 8:57:53 PM
 * PrjName:hdu2089-2
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
	/**
	 * @param args
	 */
	final static int maxl = 8;
	static int[][] f, g;
	static int[] digit;
	static void init() {
		f = new int[maxl + 1][10];
		f[0][0] = 1;
		g = new int[maxl + 1][10];
		g[0][0] = 1;
	}
	static void getd(int n) {
		digit = new int[maxl + 1];
		while (n > 0) {
			digit[++digit[0]] = n % 10;
			n /= 10;
		}
	}
	static int dfs(int d, int r, boolean c) {
		if (d == 0) {
			if (c)
				f[d + 1][r]++;
			return 0;
		}
		if (!(f[d + 1][r] > 0)) {
			int add = 0;
			int up = c ? 9 : digit[d];
			for (int i = 0; i <= up; i++)
				if (!(r == 6 && i == 2)) {
					if (!(f[d][i] > 0))
						dfs(d - 1, i, c || i != up);
					if (i != 4)
						add += f[d][i];
				}
			f[d + 1][r] += add;
		}
		int res = digit[d] == 4 || digit[d] == 2 && digit[d + 1] == 6 ? 0 : dfs(d - 1, 0, false);
		for (int i = 0; i < digit[d]; i++)
			if (i != 4 && !(i == 2 && digit[d + 1] == 6))
				res += f[d][i];
		return res;
	}
	static int solve(int n) {
		int res = 0;
		getd(n);
		return dfs(digit[0], 0, true);
	}
	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);
		init();

		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			int n = (int) in.nval;
			in.nextToken();
			int m = (int) in.nval;
			if (n == 0 && m == 0)
				break;
			out.println(solve(m + 1) - solve(n));
		}
		out.flush();
		out.close();
	}
}
  • 为何生成与统计分两步走？
    因为前i+1位的各种情况以前i位为依据生成，不能打断这个递推的连续性。
    待统计时再筛选所需。
  • 为何solve(m+1)?
    便捷化处理，搜集<m+1的答案即≤m的答案。
  • 为何这个记忆化搜索极易写挂？
    许多人根据数字的可选或不可选来划分状态，而此处为了清晰的体现数位的筛选辄以数字为状态。
    状态的更新与统计仍是分离的。
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing5 minutes read (About 742 words)

Bestcoder

迟到了半小时开打，不然rank还可以更好看点……

1001 Rikka with Graph

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
/** Aug 29, 2015 7:39:29 PM
 * PrjName:Bc53-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 n=(int)in.nval;
            in.nextToken();
            int m=(int)in.nval;
            boolean has=false;
            //out.println(n+"-"+m);
            for(int i=1;i<=m;i++){
                in.nextToken();
                int u=(int)in.nval;
                in.nextToken();
                int v=(int)in.nval;
                if (u==1&&v==n||u==n&&v==1)
                    has=true;
            }
            if (has)
                out.println(1+" "+n*(n-1)/2);
            else
                out.println(1+" "+1);
        }
        out.flush();
        out.close();
    }
}

如果点1与点n直接相连，那么就是距离最短了。

1002 Rikka with Tree

要同时满足不同与相似，就是要求结点数相等，各结点到树根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
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
/** Aug 29, 2015 7:59:14 PM
 * PrjName:Bc53-02
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    final static int maxn=2010;
    static Graph G=new Graph(maxn);
    static int[] dep;
    static HashSet<Integer> st=new HashSet<Integer>();
    static void bfs(int st){
        Queue<Integer> que=new LinkedList<Integer>();
        que.add(st);
        while(!que.isEmpty()){
            int u=que.poll();
            for(int i=G.h[u];i>-1;i=G.edge[i].next){
                int v=G.edge[i].to;
                if (dep[v]>0) continue;
                dep[v]=dep[u]+1;
                que.add(v);
            }
        }
    }
    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 n=(int)in.nval;
            G.clear();
            dep=new int[n+1];
            dep[1]=1;
            for(int i=1;i<n;i++){
                in.nextToken();
                int u=(int)in.nval;
                in.nextToken();
                int v=(int)in.nval;
                G.add(u, v);
                G.add(v, u);
            }
            bfs(1);
            boolean ans=true;
            st.clear();
            for(int i=1;i<=n;i++)
                if (st.contains(dep[i])){
                    ans=false;
                    break;
                }
                else
                    st.add(dep[i]);
            out.println(ans?"YES":"NO");
        }
        out.flush();
        out.close();
    }

}
class Edge{
    int to,next;
    Edge(int _u,int _v){
        to=_u;next=_v;
    }
}
class Graph{
    int[] h;
    int sz;
    Edge[] edge;
    Graph(int size){
        sz=size;
        h=new int[sz+1];
        edge=new Edge[sz+1];
        Arrays.fill(h, -1);
        h[0]=0;
    }
    void clear(){
        h=new int[sz+1];
        edge=new Edge[sz+1];
        Arrays.fill(h, -1);
        h[0]=0;
    }
    void add(int u,int v){
        edge[h[0]]=new Edge(v,h[u]);
        h[u]=h[0]++;
    }
}

然而错了。
适当地列举一些情况，发现若树的深度仅有2，那么它始终是特殊的。
可是加上这一判断仍不够。
进一步的举例发现，若树上非最底层有某一层结点多于一个，就能变换形成新结构

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
/** Aug 29, 2015 7:59:14 PM
 * PrjName:Bc53-02
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    final static int maxn=2010;
    static Graph G=new Graph(maxn);
    static int[] dep;
    static HashSet<Integer> st=new HashSet<Integer>();
    static void bfs(int st){
        Queue<Integer> que=new LinkedList<Integer>();
        que.add(st);
        while(!que.isEmpty()){
            int u=que.poll();
            for(int i=G.h[u];i>-1;i=G.edge[i].next){
                int v=G.edge[i].to;
                if (dep[v]>0) continue;
                dep[v]=dep[u]+1;
                que.add(v);
            }
        }
    }
    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 n=(int)in.nval;
            G.clear();
            dep=new int[n+1];
            dep[1]=1;
            for(int i=1;i<n;i++){
                in.nextToken();
                int u=(int)in.nval;
                in.nextToken();
                int v=(int)in.nval;
                G.add(u, v);
                G.add(v, u);
            }
            bfs(1);
            boolean ans=true;
            st.clear();
            int maxd=0;
            for(int i=1;i<=n;i++)
                maxd=Math.max(dep[i], maxd);
            for(int i=1;i<=n;i++)
                if (st.contains(dep[i])){
                    if (dep[i]<maxd){
                        ans=false;
                        break;
                    }
                }
                else
                    st.add(dep[i]);
            if (maxd<3)
                ans=true;
            out.println(ans?"YES":"NO");
        }
        out.flush();
        out.close();
    }

}
class Edge{
    int to,next;
    Edge(int _u,int _v){
        to=_u;next=_v;
    }
}
class Graph{
    int[] h;
    int sz;
    Edge[] edge;
    Graph(int size){
        sz=size;
        h=new int[sz+1];
        edge=new Edge[sz+1];
        Arrays.fill(h, -1);
        h[0]=0;
    }
    void clear(){
        h=new int[sz+1];
        edge=new Edge[sz+1];
        Arrays.fill(h, -1);
        h[0]=0;
    }
    void add(int u,int v){
        edge[h[0]]=new Edge(v,h[u]);
        h[u]=h[0]++;
    }
}

这与题解中所说的“一棵树是独特的当且仅当任意处于每一个深度的点数是1 1 1 1 … 1 1 x”相符（我个人将这种形态称作“呈扫帚状”）

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;
    }
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

×