摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2394題目的大概意思就是，判斷關于x的二次同余方程 a x^2 + b x + c = 0 ( mod 2 ^32 ) 是否有解看到這道題目的時候剛好看了一些二次互反律之類的知識，思維被定向到了那邊，又在網上找了一些資料，但是都不能解決此題（起碼我沒有想出來怎么辦，大牛勿鄙視）。跟haozi討論了一下，也沒什么結... 閱讀全文
http://acm.hdu.edu.cn/showproblem.php?pid=3571比賽前一天晚上剛跟haozi研究了最小包圍球，其中要根據四個點求出球心坐標，然后我提出了這么拓展到N維的情況。今天比賽的時候居然就出了這么一題，雖然知道可以用高斯消元，但是這題的數據好大，有10 17那么大，而且要是整數解，用double精度根本不夠。我想利用大整數，要隊友寫了一個java的，每次消元的時候取最小公倍數，結果TLE了。。。比賽的時候只有haozi他們隊和電子科大的一個隊伍過了，Orz！！！ 賽后，問了一下haozi，因為最后的答案在[ -10 17 , 10 17] 的范圍內，可以取一個大于2×10 17的素數p，計算的過程中都 mod p，由于坐標有正有負，可以先將球心坐標都加上10 17 這么一個偏移量，最后求出答案之后在剪掉。 PS: 高斯消元改自浙大模板 1 #include <cstdio>
2 #include <iostream>
3 #include <map>
4 #include <queue>
5 #include <complex>
6 #include <algorithm>
7 #include <cmath>
8 #include <cstring>
9 using namespace std;
10 typedef __int64 ll;
11
12 const ll p = 1000000000000000003LL;
13 const int maxn = 60;
14 const ll inf = 100000000000000000LL;
15
16 ll mod( ll a, ll n ) { return ( a % n + n ) % n; }
17
18 ll mul_mod ( ll a, ll b )
19 {
20 ll ret = 0, tmp = a % p;
21 while( b )
22 {
23 if( b & 1 )
24 if( ( ret += tmp ) >= p )
25 ret -= p;
26 if( ( tmp <<= 1 ) >= p ) tmp -= p;
27 b >>= 1;
28 }
29 return ret;
30 }
31
32 void gcd( ll a, ll b, ll & d, ll & x, ll & y )
33 {
34 if( ! b ) { d = a; x = 1; y = 0; }
35 else
36 {
37 gcd( b, a % b, d, y, x );
38 y -= x * ( a / b );
39 }
40 }
41
42 ll inv( ll a, ll n )
43 {
44 ll d, x, y;
45 gcd( a, p, d, x, y );
46 return d == 1 ? mod( x, p ) : -1;
47 }
48
49 ll ABS( ll a ) { return ( a < 0 ? -a : a ); }
50
51 int Gauss( int n, ll a[][maxn], ll b[] )
52 {
53 int i, j, k, row;
54 ll maxp, t;
55 for( k = 0; k < n; k++ )
56 {
57 for( maxp = 0, i = k; i < n; i++ )
58 if( ABS( a[i][k] ) > ABS( maxp ) )
59 maxp = a[row=i][k];
60 if( maxp == 0 ) return 0;
61 if( row != k )
62 {
63 for( j = k; j < n; j++ )
64 t = a[k][j], a[k][j] = a[row][j], a[row][j] = t;
65 t = b[k], b[k] = b[row], b[row] = t;
66 }
67 ll INV = inv( maxp, p );
68 for( j = k + 1; j < n; j++ )
69 {
70 a[k][j] = mul_mod( a[k][j], INV );
71 for( i = k + 1; i < n; i++ )
72 a[i][j] = mod( a[i][j] - mul_mod( a[i][k], a[k][j] ), p );
73 }
74 b[k] = mul_mod( b[k], INV );
75 for( i = k + 1; i < n; i++ )
76 b[i] = mod( b[i] - mul_mod( b[k], a[i][k] ), p );
77 }
78 for( i = n - 1; i >= 0; i-- )
79 for( j = i + 1; j < n; j++ )
80 b[i] = mod( b[i] - mul_mod( a[i][j], b[j] ), p );
81 return 1;
82 }
83
84 int main(int argc, char *argv[])
85 {
86 int cas, n;
87 ll a[maxn][maxn], b[maxn], c[maxn][maxn], d[maxn];
88 scanf("%d",&cas);
89 for( int t = 1; t <= cas; t++ )
90 {
91 scanf("%d",&n);
92 for( int i = 0; i <= n; i++ )
93 {
94 b[i] = 0;
95 for( int j = 0; j < n ; j++ )
96 {
97 scanf("%I64d",&a[i][j]);
98 a[i][j] += inf;
99 b[i] = ( b[i] + mul_mod( a[i][j], a[i][j] ) ) % p;
100 a[i][j] = ( a[i][j] + a[i][j] ) % p;
101 }
102 }
103 for( int i = 0; i < n; i++ )
104 {
105 for( int j = 0; j < n; j++ )
106 c[i][j] = mod( a[i][j] - a[n][j], p );
107 d[i] = mod( b[i] - b[n], p );
108 }
109 Gauss( n, c, d );
110 //gauss_cpivot( n, c, d );
111 printf("Case %d:\n",t);
112 printf("%I64d",d[0]-inf);
113 for( int i = 1; i < n; i++ )
114 printf(" %I64d",d[i]-inf);
115 printf("\n");
116 }
117 return 0;
118 }
摘要: http://www.spoj.pl/problems/LCMSUM/ sigma lcm( i, n ) = sigma ( i * n / gcd( i, n ) ) = n * sigma ( i / gcd( i, n ) ) 設 gcd( i, n ) = k, i = k * j, n = k * m ( j <= m )... 閱讀全文
摘要: 很郁悶的一題，第一次碰到使用不同的編譯器，一個超時（C++），一個AC的情況（G++）。。。
首先題中的要求等價于：存在一條直線l和所有的線段都相交。
證明：若存在一條直線l和所有線段相交，作一條直線m和l垂直，則m就是題中要求的直線所有線段投影的一個公共點即為垂足。（l和每條線段的交點沿l投影到m上的垂足處）反過來，若存在m，所有線段在m上的投影有公共點，則過這點垂直于m作直線l， ... 閱讀全文
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2665以前只知道用歸并樹做，查詢時間復雜度要 m * ( log n)^3， 昨天學了一個劃分樹，查詢只要m * logn 。其實這題的正解就是使用劃分樹來做。劃分樹跟歸并樹剛好是相反的操作，劃分樹查詢用于查詢[ l , r ]內第k大的數， 歸并樹用于查詢某個數在[ l , r ]內排第幾。劃分樹的資料比較少，... 閱讀全文
摘要: http://124.205.79.250/JudgeOnline/problem?id=1418 最近跟著haozi大牛學習計算幾何，第一道圓的離散化的題目。 題目的大致意思是按照時間順序把許多圓放在平面上，后放的圓可能將先放的圓... 閱讀全文
http://acm.hdu.edu.cn/showproblem.php?pid=3474單調隊列，又是第一次使用，本人蒟蒻無比啊。。。
  hdu 3474
1 #include <cstdio>
2#include <iostream>
3#include <cmath>
4#include <complex>
5#include <algorithm>
6#include <cstring>
7#include <queue>
8using namespace std;
9
10const int maxn = 1000000 + 10;
11int Q[maxn<<1], sum[maxn<<1];
12char neck[maxn<<1];
13int vis[2][maxn];
14
15void solve( int n, int m, int v )
16 {
17 sum[0] = 0;
18 for( int i = 1; i < m; i++ )
19 sum[i] = sum[i-1] + ( neck[i] == 'C' ? 1 : -1 );
20 int head = 0, tail = 0;
21 for( int i = 0; i < m; i++ )
22  {
23 while( head < tail && sum[Q[tail-1]] >= sum[i] ) tail--;
24 Q[tail++] = i;
25 if( i >= n )
26 {
27 while( i - Q[head] >= n ) head++;
28 vis[v][i-n] = ( sum[i-n] <= sum[Q[head]] );
29 }
30 }
31 }
32
33int main(int argc, char *argv[])
34{
35 int t;
36 scanf("%d",&t);
37 for( int p = 1; p <= t; p++ )
38 {
39 scanf("%s",neck+1);
40 int n = strlen( neck + 1 );
41 int m = n * 2 + 1;
42 for( int i = 1; i <= n; i++ )
43 neck[i+n] = neck[i];
44 neck[m] = 0;
45 memset( vis, 0, sizeof( vis ) );
46 solve( n, m, 0 );
47 reverse( neck + 1, neck + m );
48 solve( n, m, 1 );
49 int ans = 0;
50 for( int i = 1; i <= n; i++ )
51 if( vis[0][i] || vis[1][n-i] ) ans ++;
52 printf("Case %d: %d\n",p,ans);
53 }
54 return 0;
55}
56
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3471此題主要有兩個問題：直線與面的交點，點是否在多邊形內
對于速度V的方向有三種情況，可用V與ABCD面法向量的點積判斷：1 V指向ABCD面外側，不可能進球；2 V與ABCD面平行，不可能進球；3 V指向ABCD面內側，可能進球，分三種情況: 3.1 P在ABCD面內側，不可能進球；... 閱讀全文
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3465太弱了，第一次聽說逆序對數，這題判斷線段相交的對數，可以轉換到逆序對數來做。而逆序對數可以修改一下歸并排序來實現，只要n logn的時間復雜度。大致的意思見下圖：
右邊有多少對逆序對數，就是有多少個交點！
hdu_3465Code highlighting produced by Actipro C... 閱讀全文
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3437AC牛的題目，精度比較惡心，最后一組數據一個誤差是0.00006 我精度用了1e-8，而標程是1e-4，卡死在最后一組數據上了。。。這題看起來是三維的幾何，其實完全可以壓縮到二維來做。
1// Author : AmazingCaddy &n... 閱讀全文
摘要: 【題目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1951【題目大意】PS.此題的題目描述是亮點，膜拜ipig~“在那山的那邊海的那邊有一群小肥豬。他們活潑又聰明，他們調皮又靈敏。他們自由自在生活在那綠色的大草坪，他們善良勇敢相互都關心……”——選自豬王國民歌 給出... 閱讀全文
http://124.205.79.250/JudgeOnline/problem?id=3608旋轉卡殼的經典題目，看著網上某篇論文寫的，寫了一個下午還是WA，最后參考了了haozi的代碼，還是WA，原來haozi的代碼中將平行跟其中一種情況合并在一起寫了，精度調得很高，但是我的精度太低了，調整精度之后過了。但是我覺得這題的精度是不用那么高的，原因應該是出在了，兩種情況的合并上面，后來我改成三種情況，精度就1e-8過了，看來是那哥問題。代碼如下：   pku 3608
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<vector>
5 #include<cstring>
6 #include<complex>
7 using namespace std;
8 typedef complex<double> point;
9 const double eps = 1e-8;
10 const double pi = acos( -1.0 );
11 const double inf = 1e100;
12 vector<point> P, Q;
13
14 double operator ^( const point p1, const point p2 ) { return imag( conj( p1 ) * p2 ); }
15 double operator &( const point p1, const point p2 ) { return real( conj( p1 ) * p2 ); }
16 int dblcmp( double x ) { return ( x < -eps ? -1 : x > eps ); }
17 double min( double x, double y ) { return ( x < y ? x : y ); }
18
19 double DisPointToSeg( const point & p, const point & p1, const point & p2 )
20 {
21 if( dblcmp( p - p1 & p2 - p1 ) < 0 || dblcmp( p - p2 & p1 - p2 ) < 0 )
22 return min( abs( p1 - p ), abs( p2 - p ) );
23 return fabs( p1 - p ^ p2 - p ) / abs( p1 - p2 );
24 }
25
26 double DisPallSeg( point p1, point p2, point p3, point p4 )
27 {
28 return min( min( DisPointToSeg( p1, p3, p4 ), DisPointToSeg( p2, p3, p4 ) ),
29 min( DisPointToSeg( p3, p1, p2 ), DisPointToSeg( p4, p1, p2 ) ) );
30 }
31
32 void changeclockwise( vector<point> & g )
33 {
34 int n = g.size( );
35 if( ( g[1] - g[0] ^ g[2] - g[0] ) < 0 )
36 for( int i = 0; i < n / 2; i++ )
37 swap( g[i], g[n-1-i] );
38 }
39
40 double RC( )
41 {
42 point f0( 1.0, 0 ), f1( -1.0, 0 );
43 point p0, p1, p2, p3;
44 int pn = P.size( ), qn = Q.size( ), k1 = -1, k2 = -1;
45 double ymin = inf, ymax = -inf, angle, ang, ans;
46
47 changeclockwise( P );
48 changeclockwise( Q );
49
50 for( int i = 0; i < pn; i++ )
51 if( ymin > imag( P[i] ) ) ymin = imag( P[i] ), k1 = i;
52 for( int i = 0; i < qn; i++ )
53 if( ymax < imag( Q[i] ) ) ymax = imag( Q[i] ), k2 = i;
54
55 angle = 0.0;
56 ans = inf;
57
58 while( angle <= 140 )
59 {
60 p0 = P[k1]; p1 = P[(k1+1)%pn];
61 p2 = Q[k2]; p3 = Q[(k2+1)%qn];
62 int t = dblcmp( p1 - p0 ^ p3 - p2 );
63 if( t > 0 ) // 旋轉 p2p3
64 {
65 ang = arg( ( p3 - p2 ) / f1 );
66 f1 = p3 - p2;
67 f0 = -f1;
68 k2 = ( k2 + 1 ) % qn;
69 ans = min( ans, DisPointToSeg( p0, p2, p3 ) );
70 }
71 else if( t == 0 )
72 {
73 ang = arg( ( p1 - p0 ) / f0 );
74 f0 = p1 - p0;
75 f1 = -f0;
76 k1 = ( k1 + 1 ) % pn;
77 k2 = ( k2 + 1 ) % qn;
78 ans = min( ans, DisPallSeg( p0, p1, p2, p3 ) );
79 }
80 else // 平行 && 旋轉 p0p1， 兩種情況可以合并
81 {
82 ang = arg( ( p1 - p0 ) / f0 );
83 f0 = p1 - p0;
84 f1 = -f0;
85 k1 = ( k1 + 1 ) % pn;
86 ans = min( ans, DisPointToSeg( p2, p0, p1 ) );
87 }
88 angle += ( ang < 0 ? ang + 2 * pi : ang );
89 }
90 return ans;
91 }
92
93 int main( )
94 {
95 int n, m;
96 double x, y, ans;
97 while( scanf("%d%d",&n,&m) && ( n + m ) )
98 {
99 P.clear( );
100 Q.clear( );
101 for( int i = 0; i < n; i++ )
102 {
103 scanf("%lf%lf",&x,&y);
104 P.push_back( point( x, y ) );
105 }
106 for( int i = 0; i < m; i++ )
107 {
108 scanf("%lf%lf",&x,&y);
109 Q.push_back( point( x, y ) );
110 }
111 ans = RC( );
112 printf("%.5lf\n",ans);
113 }
114 }
摘要: 一、在姿態上要低調
在低調中修煉自己：低調做人無論在官場、商場還是政治軍事斗爭中都是一種進可攻、退可守，看似平淡，實則高深的處世謀略。
謙卑處世人常在：謙卑是一種智慧，是為人處世的黃金法則，懂得謙卑的人，必將得到人們的尊重，受到世人的敬仰。
&nbs... 閱讀全文
http://acmicpc-live-archive.uva.es/nuevoportal/先預處理所有凸包，然后dp。
1#include<iostream>
2#include<cmath>
3#include<algorithm>
4#include<complex>
5#include<vector>
6#include<stdio.h>
7using namespace std;
8typedef complex<double> point;
9const int maxn = 530;
10const double eps = 1e-8;
11const double inf = 1e10;
12const double pi = acos( -1.0 );
13double dp[maxn];
14int c[10];
15bool cmp( point p1, point p2 ){ return real(p1) < real(p2) || real(p1) == real(p2) && imag(p1) < imag(p2); }
16double operator^( point p1, point p2 ){ return imag( conj( p1 ) * p2 ); }
17int dblcmp( double x ){ return x < -eps ? -1 : x > eps ; }
18double minn( double x, double y ){ return x < y ? x : y; }
19void convex_hull( vector<point> &p, vector<point> &poly )
20{
21 int sz = 0, i, k;
22 poly.clear( );
23 sort( p.begin( ), p.end( ), cmp );
24 for( i = 0; i < p.size( ); ++i )
25 {
26 while( sz >= 2 && dblcmp( poly[sz-2] - p[i] ^ poly[sz-1] - p[i] ) <= 0 )
27 poly.pop_back( ), sz--;
28 poly.push_back( p[i] );
29 sz++;
30 }
31 k = sz;
32 for( i = p.size( ) - 2; i >= 0; i-- )
33 {
34 while( sz > k && dblcmp( poly[sz-2] - p[i] ^ poly[sz-1] - p[i] ) <= 0 )
35 poly.pop_back( ), sz--;
36 poly.push_back( p[i] );
37 sz++;
38 }
39 poly.pop_back( );
40}
41
42int main( )
43{
44 double a[maxn], x, y;
45 int i, j, q, n, m, len, k = 1, sz;
46 vector<point> p, poly, poly1;
47 while( 1 )
48 {
49 p.clear( );
50 scanf("%d%d",&n,&m);
51 if( n == 0 && m == 0 )break;
52 for( i = 0; i < n; i++ )
53 {
54 scanf("%lf%lf",&x,&y);
55 p.push_back( point( x, y ) );
56 }
57 len = 1 << n;
58 for( i = 1; i < len; i++ )
59 {
60 poly.clear( );
61 poly1.clear( );
62 j = i; q = 0;
63 while( j )
64 {
65 if( j & 1 ) poly.push_back( p[q] );
66 q++;
67 j >>= 1;
68 }
69 convex_hull( poly, poly1 );
70 sz = poly1.size( );
71 for( a[i] = 2 * pi * m, j = 0; j < sz; j++ )
72 a[i] += abs( poly1[j] - poly1[(j+1)%sz] );
73 }
74 for( dp[0] = 0.0, i = 1; i < len; i++ )
75 dp[i] = inf;
76 for( i = 0; i < len; i++ )
77 for( j = 1; j < len; j++ )
78 if( ( j & i ) == 0 )
79 dp[i|j] = minn( dp[i] + a[j], dp[i|j] );
80 printf("Case %d: length = %.2lf\n",k++,dp[len-1]);
81 }
82 return 0;
83}
84
http://162.105.81.212/JudgeOnline/problem?id=1286本人第一道polya的題目，polya的入門題，看過polya的應該都沒什么問題的。
1#include<iostream>
2using namespace std;
3typedef __int64 ll;
4int gcd( int a, int b ){ return b ? gcd( b, a % b ) : a; }
5ll pow( ll a, ll n )
6{
7 ll ans = 1, d = a;
8 while( n )
9 {
10 if( n & 1 ) ans = ans * d;
11 d *= d;
12 n >>= 1;
13 }
14 return ans;
15}
16
17ll solve( int n )
18{
19 int i;
20 ll sum = 0;
21 if( n == 0 )return 0;
22 for( i = 1; i <= n; i++ )
23 sum += pow( 3, gcd( i, n ) );
24 if( n % 2 == 0 )
25 {
26 sum += pow( 3, n / 2 ) * n / 2;
27 sum += pow( 3, n / 2 + 1 ) * n / 2;
28 }
29 else sum += pow( 3, n / 2 + 1 ) * n;
30 return sum / n / 2;
31}
32
33int main( )
34{
35 int n;
36 while( scanf("%d",&n) && n != -1 )
37 {
38 printf("%I64d\n",solve( n ));
39 }
40 return 0;
41}
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 27 | 28 | 29 | 30 | 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 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
常用鏈接
留言簿
隨筆分類
隨筆檔案
傳送門
搜索
最新評論
閱讀排行榜
評論排行榜
|
|