2013多校第三场

hdu 4629

题意：给你n个三角形，问覆盖1~n次的面积各是多少，n < 50;

分析：取出所有端点和交点的x坐标，排序，然后对于每一段xi~xi+1的范围的线段都是不相交的，所以组成的

面积要么是三角形，要么是梯形，可以直接用公式算面积，然后对于每一个三角形的线段都标记该段对于

从下往上的扫描线来说是入边还是出边，然后就可以直接计算出这块面积被覆盖了几次；如入边加1，出边减一

下图，黄色表示覆盖次数；

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 #include<cstdlib>
  8 #define pbk push_back
  9 using namespace std;
 10 const int N = 25050+10;
 11 const double eps = 1e-10;
 12 inline double sqr(double x){
 13     return x * x;
 14 }
 15 inline int dcmp(double x){
 16     return x < -eps ? -1 : x > eps;
 17 }
 18 struct Point{
 19     double x,y;
 20     int kind;
 21     Point(){}
 22     Point(double x,double y,int kind = 0):x(x),y(y),kind(kind){}
 23     bool operator < (const Point &p)const{
 24         return dcmp(x - p.x) < 0 || ( dcmp(x - p.x) == 0 && dcmp(y - p.y) < 0 );
 25     }
 26     Point operator - (const Point &p)const{
 27         return Point(x - p.x, y - p.y);
 28     }
 29     Point operator + (const Point &p)const{
 30         return Point(x + p.x, y + p.y);
 31     }
 32     Point operator * (const double &k)const{
 33         return Point (x*k , y*k);
 34     }
 35     Point operator / (const double &k)const{
 36         return Point (x/k, y/k);
 37     }
 38     double operator * (const Point &p)const{
 39         return x * p.y - y * p.x;
 40     }
 41     double operator / (const Point &p)const{
 42         return x * p.x + y * p.y;
 43     }
 44     void input(){
 45         scanf("%lf%lf",&x,&y);
 46     }
 47     void ot(){
 48         printf("%lf %lf
",x,y);
 49     }
 50 };
 51 struct Line{
 52     Point a,b;
 53     int kind;
 54     Line (){}
 55     Line (Point a,Point b,int kind = 0):a(a),b(b),kind(kind){}
 56     double operator * (const Point &p)const{
 57         return ( b - a ) * ( p - a );
 58     }
 59     double operator / (const Point &p)const{
 60         return ( p - a) / ( p - b);
 61     }
 62     bool parallel(const Line &v){
 63         return !dcmp( ( b - a ) * ( v.b - v.a ) ); 
 64     }
 65     int LineCrossLine(const Line &v){
 66         if ( (*this).parallel(v) ){
 67             return ( dcmp( v * a ) == 0);
 68         }return 2;
 69     }
 70     int SegCrossSeg(const Line &v){
 71         int d1 = dcmp( (*this) * v.a);
 72         int d2 = dcmp( (*this) * v.b);
 73         int d3 = dcmp( v * a);
 74         int d4 = dcmp( v * b);
 75         if ( ( d1 ^ d2 ) == -2 && ( d3 ^ d4 ) == -2 ) return 2;
 76         return ( ( d1 == 0 && dcmp( (*this) / v.a ) <= 0 )
 77             ||   ( d2 == 0 && dcmp( (*this) / v.b ) <= 0 )
 78             ||   ( d3 == 0 && dcmp( v / a ) <= 0 )
 79             ||   ( d4 == 0 && dcmp( v / b ) <= 0 )
 80             );
 81     }
 82     Point CrossPoint(const Line &v){
 83         double s1 = v * a, s2 = v * b;
 84         return ( a * s2 - b * s1) / (s2 - s1);
 85     }
 86     void input(){
 87         a.input(); b.input();
 88     }
 89     void ot(){
 90         a.ot(); b.ot();
 91     }
 92 
 93 };
 94 
 95 int n,poly_n,xn;
 96 vector<double> lx;
 97 vector<Line> line;
 98 double ans[N];
 99 void init(){
100     int sz = line.size();
101     for (int i = 0; i < sz; i++){
102         for (int j = i+1; j < sz; j++){
103             if (line[i].SegCrossSeg(line[j]) == 2){
104                 Point p = line[i].CrossPoint(line[j]);
105                 lx.pbk(p.x);
106             }
107         }
108     }
109     
110     sort(lx.begin(),lx.end());
111     xn = unique(lx.begin(),lx.end()) - lx.begin();
112 }
113 vector<Point> qu[N];
114 void work(){
115     for (int i = 0; i <= n; i++) ans[i] = 0;
116     for (int i = 0; i < xn-1; i++){
117         int k = 0;
118         for (int j = 0; j+1 < qu[i].size(); j++){
119             k += qu[i][j].kind;
120             ans[ k ] += (lx[i+1] - lx[i]) * (qu[i][j+1].x+qu[i][j+1].y - qu[i][j].x - qu[i][j].y) / 2;        
121         }
122     }
123     for (int i = 1; i <= n; i++) printf("%.10lf
",ans[i]);
124 }
125 void check(){
126     for (int i = 0; i < xn - 1; i++){
127         cout<<qu[i].size()<<" >.<"<<endl;
128         for (int j = 0; j < qu[i].size(); j++){
129             qu[i][j].ot(); cout<<qu[i][j].kind<<endl;
130         }
131     }
132 }
133 void solve(){
134     for (int i = 0; i < xn; i++) qu[i].clear();
135     for (int i = 0; i < line.size(); i++){
136         int j = lower_bound(lx.begin(),lx.begin()+xn,line[i].a.x) - lx.begin();
137         for (; j+1 < xn; j++ ){
138             double l = lx[j], r = lx[j+1];
139             if (dcmp(r - line[i].b.x) > 0) break;
140             Point p1 = line[i].CrossPoint(Line(Point(l,0), Point(l,1)));
141             Point p2 = line[i].CrossPoint(Line(Point(r,0), Point(r,1)));
142             qu[j].pbk(Point(p1.y, p2.y,line[i].kind));
143         }
144     }
145     for (int i = 0; i < xn - 1; i++) sort(qu[i].begin(), qu[i].end());
146 //    check();
147     work();
148 }
149 int main(){
150     int T; scanf("%d",&T);
151     while (T--){
152         scanf("%d",&n);
153         lx.clear(); line.clear();;
154         for (int i = 0; i < n ;i++){
155             Point t[4];
156             for (int j = 0; j < 3; j++ ){
157                 t[j].input(); 
158             }
159             t[3] = t[0];
160             int flag = 1;
161             if (dcmp( (t[1] - t[0])*(t[2] - t[0]) ) == 0) flag = 0;
162         
163             for (int i = 0; i < 3 && flag; i++ ){
164                 lx.pbk(t[i].x);
165                 for (int j = i+1; j < 3; j++){
166                     Line tmp; tmp.a = t[i]; tmp.b = t[j];
167                     if (dcmp( tmp.a.x - tmp.b.x ) > 0) swap(tmp.a, tmp.b);
168                     
169                     Line tmp2 = Line(t[3-i-j], Point(t[3-i-j].x, t[3-i-j].y - 1));
170                     if (tmp.LineCrossLine(tmp2) != 2) continue;
171                     Point tp = tmp.CrossPoint(tmp2);
172                     if (dcmp(tp.y - t[3-i-j].y) < 0) tmp.kind = 1;
173                         else tmp.kind = -1;    
174                     line.pbk(tmp);
175                 }
176             }
177         }
178         init();
179         solve();    
180     }
181     return 0;
182 }

View Code

hdu 4622

题意：给你一个长n的串，Q次询问其子串s[l,r]中不同的串的个数；

分析：正解后缀自动机，或者HASH，比赛的时候用后缀数组水过了，时间复杂度是O(Qn+nlogn)；

先对整个串跑一遍后缀数组，然后对于每一次的询问，直接从SA数组里取出来，然后按照统计串中不同字串的论文题来做，需要注意一下不同之处，

当前字串要统计的个数不一定是减去前一个字串统计的数目，也许还要减去更前一个字串的个数；

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<vector>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<iostream>
  8 using namespace std;
  9 const int N = 2000+10;
 10 struct Suffix_Array{
 11     int a1[N],a2[N],c[N],sa[N],SA[N],*x,*y,n,m;
 12     int height[N],*rank;
 13     void sort(){
 14         for (int i = 0; i < m ; i++) c[i] = 0;
 15         for (int i = 0; i < n; i++) c[x[i]] ++;
 16         for (int i = 0; i < m; i++) c[i+1] += c[i];
 17         for (int i = n-1; i>=0; i-- ) SA[--c[x[sa[i]]]] = sa[i];
 18     }
 19     void build_SA(char *s){
 20         n = strlen(s); m = 256;
 21         x = a1; y = a2; x[n] = y[n] = -1;
 22         for (int i = 0; i < n; i++) x[i] = s[i], sa[i] = i;
 23         sort();
 24         for (int k = 1; k <= n; k <<= 1){
 25             int p = 0;
 26             for (int i = n-k; i < n; i++) sa[p++] = i;
 27             for (int i = 0; i < n; i++) if (SA[i] >= k) sa[p++] = SA[i] - k;
 28             sort();
 29             
 30             p = 0; y[ SA[0] ] = 0;
 31             for (int i = 1; i < n; i++){
 32                 if ( x[SA[i-1]] != x[SA[i]] || x[SA[i-1]+k]!= x[SA[i]+k] ) p++;
 33                 y[SA[i]] = p;
 34             }
 35             swap(x,y);
 36             if (p+1 == n) break;
 37             m = p+1;
 38         }
 39         rank = x; getHeight(s);
 40     }
 41     void getHeight(char *s){
 42         int k = 0;
 43         for (int i = 0; i < n; i++){
 44             if (k) k--;
 45             if (rank[i] == 0) continue;
 46             int j = SA[rank[i] - 1];
 47             while (s[j+k] && s[i+k] == s[j+k]) k++;
 48             height[rank[i]] = k;
 49         }
 50         height[n] = 0;
 51     }
 52     
 53 }H;
 54 int f[12][N];
 55 void initRMQ(int n,int height[]){
 56     n--;
 57     for  (int i = 1; i <= n; i++) f[0][i] = height[i];
 58     for (int j = 1; (1<<j) <= n; j++)
 59         for (int i = 1; i+(1<<(j-1)) <= n; i++){
 60             f[j][i] = min(f[j-1][i] ,f[j-1][i+(1<<(j-1))]);
 61         }
 62 };
 63 int lcp(int a,int b){
 64     if (a > b) swap(a,b);
 65     a++;
 66     int k = 0;
 67     while (1<<(1+k) <= b - a +1) k++;
 68     return min(f[k][a],f[k][b-(1<<k)+1]);    
 69 }
 70 char s[N];
 71 int Q;
 72 vector<int> q;
 73 void solve(int l,int r){
 74     int n = strlen(s);
 75     q.clear();
 76     int cnt = r - l + 1;
 77     for (int i = 0; i <n; i++){
 78         if (H.SA[i]>=l && H.SA[i]<=r){
 79             q.push_back(i);
 80             cnt -- ;
 81         }
 82         if (cnt == 0) break;
 83     }
 84     int ret = r - H.SA[ q[0] ] + 1;
 85     int tmp = ret;
 86     for (int i = 1; i < q.size(); i++){
 87         int t1 = r - H.SA[ q[i-1] ] + 1;
 88         int t2 = r - H.SA[ q[i] ] + 1;
 89         int lc = lcp(q[i-1],q[i]);
 90         if (lc<tmp) tmp = lc;
 91         if (t2 - tmp > 0) ret += t2 - tmp;
 92         if (t2 > tmp) tmp = t2;
 93     }
 94     printf("%d
",ret);
 95 }
 96 int main(){
 97     //freopen("D:\in.txt","r",stdin);
 98     //freopen("D:\out.txt","w",stdout);
 99     int T; scanf("%d",&T);        
100     while (T--){
101         scanf("%s",s);
102         scanf("%d",&Q);
103         H.build_SA(s);
104         //check();
105         initRMQ(H.n,H.height);
106         while (Q--){
107             int l,r;
108             scanf("%d%d",&l,&r);
109             solve(l-1,r-1);
110         }    
111     }
112     return 0;
113 }

View Code

hdu 4627

题意：给你一个数n,求a+b = n,lcm(a,b)最大;

分析：n为奇数，答案(n/2)*(n/2+1);

n为偶数，k = n/2;k是奇数，答案为k-2,k+2;否则k-1,k+1;比赛的时候直接暴力找了。

 1 #include<cstring>
 2 #include<cstdlib>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<vector>
 6 #include<algorithm>
 7 #include<cstdio>
 8 using namespace std;
 9 typedef long long LL;
10 const int N = 1000;
11 LL n;
12 void solve(){
13     LL l ,r;
14     if (n%2 == 0){
15         l = r =n/2;
16     }else {
17         l = n/2; r = n/2+1;
18     }
19     LL ans = 0;
20     while (1){
21         LL t = __gcd(l,r);
22         if (t==1){
23             if (l*r>ans) ans = l*r;
24             break;
25         }else {
26             if (l*r/t > ans) ans = l*r/t;
27         }
28         l--; r++;
29         if (l == 0) break;
30     }
31     printf("%I64d
",ans);
32 
33 }
34 int main(){
35     int T; scanf("%d",&T);
36     while (T--){
37         scanf("%I64d",&n);
38         solve();
39     }
40     return 0;
41 }

View Code

hdu 4628

题意：给你一个串，每次只能删除一个回文序列，求最少多少次能把这个串删完；

分析:n = 16，状压，预处理出所有是回文序列的情况，然后DP也过了，题解是一个3^n的方法，就是每次用位运算每次枚举I的子集；

这个是枚举i的子集的位运算写法：for (int j = i; j ; j = i & (j-1));

然后为什么是3^n次，首先从0~1<<n里面含有一个1的个数是c(n,1),2个1的有c(n,2),...n个1的c(n,n);

含有一个1的数的子集有2^1,2个1的数的子集有2^2,k个1的数2^k,...然后加起来就是(2+1)^n == 3^n;

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<cmath>
 8 using namespace std;
 9 const int N = 1<<16;
10 char s[20];
11 int n;
12 vector <int > q;
13 int check(int x){
14     char ts[20];
15     int c = 0;
16     for (int i = 0; i < n; i++ ){
17         if (x&(1<<i)) ts[c++] = s[i];  
18         ts[c] = 0;
19     }
20     
21     int k = 0,l , r;
22     if (c%2){
23         l = r = c/2;
24     }else {
25         l = c/2-1; r = c/2;
26     }
27     while (ts[l-k] == ts[r+k] && l-k>=0 && r+k<c){
28         k++;
29     }
30     if (r+k == c) {
31         return 1;
32     }
33     return 0;
34 }
35 int dp[N],can[N];
36 void init(){
37     memset(can,0,sizeof(can));
38     for (int i = 1; i < (1<<n); i++){
39         if (check(i)){
40             can[i] = 1;
41         }
42     }
43 
44 }
45 void solve(){
46     for (int i = 0; i < (1<<n); i++)  dp[i] = n;
47     dp[0] = 0;
48     for (int i = 1; i < (1<<n); i++){
49         for (int j = i; j ; j = i&(j-1)){
50             if (can[j])
51             dp[i] = min(dp[i] , dp[i^j]+1); 
52         }
53     }
54     printf("%d
",dp[(1<<n)-1]);
55 }
56 int main(){
57     int T; scanf("%d",&T);
58     while (T--){
59         scanf("%s",s);
60         n = strlen(s);
61         init();
62         solve();
63     }
64     return 0;
65 }

View Code

hdu 4630

题意：给你一个1~n的排序a1~an，Q次询问在区间[l,r]中的最大gcd(a,b).a,b属于[l,r];

分析：离线，从左到右扫一遍，idx[x]记录的是扫到当前位置时，含有x因子的最右的数的位置；

这样对于当前位置的ai,找出ai的所有约数，对于约数bi，在线段树中更新在前面出现的含有bi的最右边的数的那个位置的值，也就是idx[bi]处更新出现的最大约数；

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<vector>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<cstdlib>
  8 #define lson l,m,rt<<1
  9 #define rson m+1,r,rt<<1|1
 10 using namespace std;
 11 const int N = 50000+10;
 12 int mx[N<<2];
 13 int idx[N];
 14 int a[N];
 15 int n,Q;
 16 struct Line{
 17     int x,y;
 18     int id,ans;
 19     Line(){}
 20     Line (int x,int y):x(x),y(y){}
 21     bool operator < (const Line &p)const{
 22         return y<p.y || (y == p.y && x < p.x);
 23     }
 24 }L[N];
 25 bool cmp(Line a,Line b){
 26     return a.id<b.id;
 27 }
 28 void pushup(int rt){
 29     mx[rt] = max(mx[rt<<1] , mx[rt<<1|1]);
 30 }
 31 
 32 void update(int L,int c,int l,int r,int rt){
 33     if (l == r){
 34         if (c > mx[rt]) mx[rt] = c;
 35         return;
 36     }
 37     int m = (l+r)>>1;
 38     if (L <= m) update(L,c,lson);
 39     if (m <  L) update(L,c,rson);
 40     pushup(rt);
 41 }
 42 int query(int L,int R,int l,int r,int rt){
 43     if (L<=l && r<=R){
 44         return mx[rt];
 45     }
 46     int m = (l+r)>>1;
 47     int t1 = 0, t2 = 0;
 48     if (L <= m) t1 = query(L,R,lson);
 49     if (m <  R) t2 = query(L,R,rson);
 50     return max(t1,t2);
 51 }
 52 void insert(int now){
 53     int m = (int)sqrt((double)a[now]);
 54     
 55     for (int  j = 1; j <= m ; j++){        
 56         if (a[now]%j == 0){
 57             update(idx[j], j, 0, n, 1);
 58             idx[j] = now;
 59             if (a[now]/j !=j){
 60                 int c = a[now] / j;
 61                 update(idx[c], c, 0, n, 1);
 62                 idx[c] = now;
 63             }
 64         }
 65     }    
 66 }
 67 void solve(){
 68     memset(mx,0,sizeof(mx));
 69     memset(idx,0,sizeof(idx));
 70     int now = 1,flag = 1;
 71     for (int i = 0; i < Q; ){
 72         
 73         if ( flag ){
 74             flag = 0; insert(now);
 75         }
 76         if (L[i].y == now){
 77             L[i].ans = query(L[i].x, L[i].y, 0, n, 1);
 78             i++;
 79         }
 80         if (now < L[i].y ){
 81             flag = 1; now++;
 82         }
 83     }
 84     sort(L,L+Q,cmp);
 85 
 86     for (int i = 0; i < Q; i++){
 87         printf("%d
",L[i].ans);
 88     }
 89 }
 90 int main(){
 91     int T; scanf("%d",&T);
 92     while (T--){
 93         scanf("%d",&n);
 94         for (int i = 1; i <= n; i++){
 95             scanf("%d",&a[i]);
 96         }
 97         scanf("%d",&Q);
 98         for (int i = 0; i < Q; i++){
 99             scanf("%d%d",&L[i].x,&L[i].y);
100             L[i].id = i;
101         }
102         sort(L,L+Q);
103         solve();
104     }
105     return 0;
106 }

View Code

hdu 4631

题意：依次给你n个点，每次求出当前点中的最近点对，输出所有最近点对的和；

分析：按照x排序，然后用set维护，每次插入只更新当前点和插入点前后几个位置，如果最近距离变为0就break；

因为点的坐标的构造方法，所以是可以过的，（其实我也不太懂）；

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<vector>
 6 #include<cstdio>
 7 #include<cstdlib>
 8 #include<set>
 9 using namespace std;
10 typedef long long LL;
11 const int N = 110000;
12 int n;
13 LL ax,bx,cx,ay,by,cy;
14 struct Point{
15     LL x,y;
16     Point(){}
17     Point(LL x,LL y):x(x),y(y){};
18     bool operator < (const Point &p)const{
19         return x < p.x || (x == p.x && y < p.y);
20     }
21     void ot(){
22         cout<<x<<" "<<y<<endl;
23     }
24 };
25 LL sqr(LL x){
26     return x*x;
27 }
28 LL Distance(Point a,Point b){
29     return sqr((LL)a.x - b.x) + sqr((LL)a.y - b.y);
30 }
31 Point p[100];
32 multiset<Point> st;
33 multiset<Point> :: iterator it1,it2,it3;
34 
35 void solve(){
36     st.clear();
37     LL ans = 0;
38     LL nx = 0, ny = 0;
39     nx = ( bx ) % cx;
40     ny = ( by ) % cy;
41     st.insert(Point(nx,ny));    
42     LL mi = -1;
43     for (int i = 1; i < n; i++){
44         nx = ((LL)nx * ax + bx ) % cx;
45         ny = ((LL)ny * ay + by ) % cy;
46         Point t = Point(nx,ny);
47         st.insert(t);
48         it1 = it2 = it3 = st.lower_bound(t);
49         int k = 10;
50         while (k--){
51             if (it1 != st.begin()) it1--;
52             if (it3 != it1){
53                 LL d1 = Distance(t,*it1);
54                 if (mi == -1 || d1<mi){
55                     mi = d1;
56                 }
57             }
58             if (it2 != st.end()) it2++;
59             if (it2 != st.end() && it2!= it3){
60                 LL d2 = Distance(t,*it2);
61                 if (mi == -1 || d2 < mi){
62                     mi = d2;
63                 }
64             }
65         }
66         ans += mi;
67         if (mi == 0) break;
68     }
69     printf("%I64d
",ans);
70 }
71 int main(){
72     int T; scanf("%d",&T);
73     while (T--){
74         scanf("%d",&n);
75         scanf("%d%d%d%d%d%d",&ax,&bx,&cx,&ay,&by,&cy);
76         solve();
77     }
78     return 0;
79 }

View Code