摘要: 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}
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 31 | 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 | 8 | 9 | 10 |
|
常用链接
留言簿
随笔分类
随笔档案
传送门
搜索
最新评论
阅读排行榜
评论排行榜
|
|