题意：有n个人，要分成k支队，问你最多能够进行多少场比赛。。贪心，尽量平均分，就能够进行最多场的比赛。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-812 #define inf 0x3f3f3f3f13 #define lson l, m, rt<<114 #define rson m+1, r, rt<<1|115 #define mnx 1010016 #define mod 100000000717 18 int a[mnx];19 int main(){20 int n, m, cas;21 scanf( "%d", &cas );22 while( cas-- ){23 scanf( "%d%d", &n, &m );24 int tmp = n / m;25 for( int i = 1; i <= m; ++i ){26 a[i] = tmp;27 }28 tmp = n % m;29 for( int i = 1; i <= tmp; ++i ){30 a[i]++;31 }32 for( int i = 1; i <= m; ++i ){33 a[i] = a[i-1] + a[i];34 }35 LL ans = 0;36 for( int i = 1; i <= m; ++i ){37 ans += (LL)( a[m] - a[i] ) * ( a[i] - a[i-1] );38 }39 cout << ans << endl;40 }41 return 0;42 }
题意：给你一个既不能被2又不能被5整除的数n，问你长度为多少的只含1的数能够整除 n。。
做法：数据比较小，暴力找就好了，肯定能够找到。前几天做过问 长度为多少的只含8的数能够整除n，那道题的数据比较大，用欧拉函数搞。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 11 #define LL long long12 #define eps 1e-613 #define inf 0x3f3f3f3f14 #define mod 100015 #define MP make_pair16 #define mnx 1005017 18 int main(){19 int n;20 while( scanf( "%d", &n ) != EOF ){21 int tmp = 1, ans = 1;22 while( tmp % n ){23 ans++;24 tmp = ( tmp % n ) * 10 + 1;25 }26 printf( "%d\n", ans );27 }28 return 0;29 }
题意：给你一条弦还有圆弧的长度，问你 弦的中心到圆弧中心的距离。
做法：二分答案就好了。最开始做的时候二分角度没跑出来，以为不是单调的，后来爬山又跪了，心好塞。没想到是单调的，二分答案就好了。还有poj交G++的时候浮点数要用.3f
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 11 #define LL long long12 #define eps 1e-813 #define inf 0x3f3f3f3f14 #define mod 100015 #define MP make_pair16 #define mnx 2517 18 int main(){19 double seg, c, n, len;20 while( scanf( "%lf%lf%lf", &seg, &n, &c ) != EOF && seg >= 0 ){21 len = seg + seg * c * n;22 double l = 0, r = seg/2;23 while( r - l > eps ){24 double m = ( r + l ) / 2;25 double R = ( m*m + (seg/2)*(seg/2) ) / (2*m);26 double a = asin( seg / 2 / R );27 double len2 = 2 * a * R;28 if( len2 > len )29 r = m;30 else l = m;31 }32 printf( "%.3lf\n", l );33 }34 return 0;35 }
看别人的题解吧，。不会做。现在好像有点明白了，树形dp + 背包。。C++能过，但G++不知道为什么TLE了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 11 #define LL long long12 #define eps 1e-613 #define inf 0x3f3f3f3f14 #define mod 100015 #define MP make_pair16 #define mnx 2005017 18 int n, s, k, dp[mnx][20];19 int vv[mnx], fst[mnx], cost[mnx], nxt[mnx], e;20 void add( int u, int v, int c ){21 vv[e] = v, nxt[e] = fst[u], cost[e] = c, fst[u] = e++;22 }23 void dfs( int u, int fa ){24 for( int i = fst[u]; i != -1; i = nxt[i] ){25 int v = vv[i], c = cost[i];26 if( v == fa ) continue;27 dfs( v, u );28 for( int j = k; j >= 0; --j ){29 dp[u][j] += dp[v][0] + 2 * c;30 for( int jj = 1; jj <= j; ++jj ){31 dp[u][j] = min( dp[u][j], dp[u][j-jj] + dp[v][jj] + jj * c );32 }33 }34 }35 }36 int main(){37 while( scanf( "%d%d%d", &n, &s, &k ) != EOF ){38 memset( fst, -1, sizeof fst );39 memset( dp, 0, sizeof dp );40 e = 0;41 int u, v, c;42 for( int i = 0; i < n-1; ++i ){43 scanf( "%d%d%d", &u, &v, &c );44 add( u, v, c );45 add( v, u, c );46 }47 dfs( s, -1 );48 printf( "%d\n", dp[s][k] );49 }50 return 0;51 }
题意：给你一个图，让你把图联通，同时使权值最大的边尽量小。
做法：最小生成树的kruskal算法，题目有spj的。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-812 #define lson l, m, rt<<113 #define rson m+1, r, rt<<1|114 #define mnx 10010015 16 struct edge{17 int u, v, c;18 bool operator < ( const edge &b ) const {19 return c < b.c;20 }21 void input(){22 scanf( "%d%d%d", &u, &v, &c );23 }24 }e[mnx];25 int fa[mnx];26 int find( int x ){27 if( fa[x] != x )28 fa[x] = find( fa[x] );29 return fa[x];30 }31 int uu[mnx], vv[mnx];32 int main(){33 int n, m;34 while( scanf( "%d%d", &n, &m ) != EOF ){35 for( int i = 0; i <= n; ++i )36 fa[i] = i;37 for( int i = 0; i < m; ++i ){38 e[i].input();39 }40 sort( e, e + m );41 int ans = 0, cnt = 0;42 for( int i = 0; i < m; ++i ){43 int u = e[i].u, v = e[i].v, c = e[i].c;44 if( find(u) != find(v) ){45 fa[find(v)] = find(u);46 ans = c;47 uu[cnt] = u, vv[cnt++] = v;48 }49 }50 printf( "%d\n%d\n", ans, cnt );51 for( int i = 0; i < cnt; ++i )52 printf( "%d %d\n", uu[i], vv[i] );53 }54 return 0;55 }
题意：自己看吧。
做法：模拟题，细心一点就可以过了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 11 #define LL long long12 #define eps 1e-613 #define inf 0x3f3f3f3f14 #define mod 100015 #define MP make_pair16 #define mnx 10517 18 int n, m, tot, cnt, a[mnx*1000], cur, L[30], step;19 char ch[mnx][mnx];20 int dx[5] = { -1, 0, 1, 0 }, dy[5] = { 0, 1, 0, -1 }, D;21 bool out( int x, int y ){22 if( x < 0 || y < 0 || x >= n || y >= m ) return 1;23 return 0;24 }25 int gao( int x, int y ){26 if( out( x, y ) ) return 1;27 char c = ch[x][y];28 if( c == '?' ){29 cur = a[cnt++];30 if( cnt >= tot ) cnt = tot - 1;31 }32 else if( c >= 'A' && c <= 'Z' )33 swap( cur, L[c-'A'] );34 else if( c == '!' ){35 printf( "%d\n", cur );36 cur = 0;37 }38 else if( c == '^' )39 D = 0;40 else if( c == '>' )41 D = 1;42 else if( c == 'v' )43 D = 2;44 else if( c == '<' )45 D = 3;46 else if( c == '+' )47 cur++;48 else if( c == '-' )49 cur--;50 else if( c == '@' ){51 if( cur == 0 )52 D = ( D + 4 - 1 ) % 4;53 else D = ( D + 1 ) % 4;54 }55 else if( c == '#' )56 return -1;57 return 0;58 }59 int main(){60 scanf( "%d%d", &n, &m );61 for( int i = 0; i < n; ++i )62 scanf( "%s", ch[i] );63 scanf( "%d", &tot);64 for( int i = 0; i < tot; ++i )65 scanf( "%d", &a[i] );66 int x = 0, y = 0;67 D = 1, step = 0;68 while( 1 ){69 int ok = gao( x, y );70 if( ok == 1 ){71 puts( "RUNTIME ERROR" ); break;72 }73 if( ok == -1 ){74 break;75 }76 if( abs(cur) > 100000 ){77 puts( "OVERFLOW ERROR" ); break;78 }79 step++;80 if( step >= 1000000 ){81 puts( "TIME LIMIT EXCEEDED" ); break;82 }83 x = x + dx[D], y = y + dy[D];84 }85 return 0;86 }
题意：有一个robot要清除地图上所有不干净的地方，问你最短路要多少。
做法：bfs + TSP问题。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 11 #define LL long long12 #define eps 1e-813 #define inf 0x3f3f3f3f14 #define mod 100015 #define MP make_pair16 #define mnx 2517 18 char ch[mnx][mnx];19 int dx[5] = { 0, 1, -1, 0 }, dy[5] = { 1, 0, 0, -1 };20 bool vis[mnx][mnx];21 struct node{22 int u, v, dis;23 node( int u = 0, int v = 0, int dis = 0 ) : u(u), v(v), dis(dis) {}24 };25 queue q;26 int x[mnx], y[mnx], g[mnx][mnx], dis[mnx][mnx], cnt, n, m;27 bool in( int ax, int ay ){28 if( ax < 0 || ay < 0 || ax >= n || ay >= m || ch[ax][ay] == 'x' )29 return 0;30 return 1;31 }32 void bfs( int k, int cx, int cy ){33 memset( vis, 0, sizeof(vis) );34 vis[cx][cy] = 1;35 dis[k][k] = 0;36 q.push( node(cx, cy, 0) );37 while( !q.empty() ){38 node vv = q.front();39 int gx = vv.u, gy = vv.v, d = vv.dis;40 q.pop();41 for( int i = 0; i < 4; ++i ){42 int ax = gx + dx[i], ay = gy + dy[i];43 if( in( ax, ay ) && !vis[ax][ay] ){44 if( g[ax][ay] != -1 )45 dis[k][g[ax][ay]] = d + 1;46 vis[ax][ay] = 1;47 q.push( node(ax, ay, d+1) );48 }49 }50 }51 }52 int dp[15000][15];53 void solve(){54 for( int i = 0; i < cnt; ++i )55 bfs( i, x[i], y[i] );56 cnt--;57 for( int v = 0; v < (1<
题意：有w个mice和b个mice，公主 和 龙 轮流摸，谁先摸到白的谁就赢，问你公主获胜的概率。龙每次摸完之后，如果没有赢的话，就会有一只mice会逃走（白色的或者黑色的）
做法：dp[i][j]表示有i个白mice和j个黑mice，公主赢的概率。根据题意，公主赢的概率有3种情况。
dp[i][j] = i*1.0 / sum; （当前公主赢的概率）
dp[i][j] += ( dp[i-1][j-2] * (j/sum * (j-1.0)/(sum-1.0) * (i/(sum-2.0)) ) ); （龙没有赢，逃走的是白mice）dp[i][j] += ( dp[i][j-3] * (j/sum * (j-1.0)/(sum-1.0) * (j-2.0)/(sum-2.0) ) ); （龙没有赢，逃走的是黑mice） 1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-1212 #define lson l, m, rt<<113 #define rson m+1, r, rt<<1|114 #define mnx 110015 #define Pi acos( -1.0 )16 17 double dp[mnx][mnx];18 int main(){19 for( int i = 1; i < mnx; ++i ){20 dp[i][0] = 1.0;21 }22 dp[1][1];23 int w, b;24 while( scanf( "%d%d", &w, &b ) != EOF ){25 for( int i = 1; i <= w; ++i ){26 for( int j = 1; j <= b; ++j ){27 double sum = i + 0.0 + j;28 dp[i][j] = i*1.0 / sum;29 if( j >= 2 ){30 dp[i][j] += ( dp[i-1][j-2] * (j/sum * (j-1.0)/(sum-1.0) * (i/(sum-2.0)) ) );31 }32 if( j >= 3 ){33 dp[i][j] += ( dp[i][j-3] * (j/sum * (j-1.0)/(sum-1.0) * (j-2.0)/(sum-2.0) ) );34 }35 }36 }37 printf( "%.10lf\n", dp[w][b] );38 }39 return 0;40 }
题意：给你n个单词，问你这n个单词里面有哪些个是可以由两个单词组成的。
做法：trie树 or 哈希。还以为单词很长，一个个分割会超时，没想到单词并不长。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-812 #define inf 0x3f3f3f3f13 #define mod 100014 #define mnx 20010015 16 char ch[mnx][50];17 int son[mnx][26], cnt, val[mnx], all;18 void insert( char *s ){19 int m = strlen( s ), t = 0;20 for( int i = 0; i < m; ++i ){21 int c = s[i] - 'a';22 if( son[t][c] == 0 ){23 son[t][c] = ++cnt;24 memset( son[cnt], 0, sizeof(son[cnt]) );25 val[cnt] = 0;26 }27 t = son[t][c];28 }29 val[t] = 1;30 }31 bool find( char *s ){32 int m = strlen( s ), t = 0;33 for( int i = 0; i < m; ++i ){34 int c = s[i] - 'a';35 if( son[t][c] == 0 )36 return false;37 t = son[t][c];38 }39 return val[t];40 }41 char s[mnx];42 bool gao( int c, int u, int v ){43 int tot = 0;44 for( int i = u; i <= v; ++i ){45 s[tot++] = ch[c][i];46 }47 s[tot] = '\0';48 //cout << s << endl;49 if( find( s ) ) return 1;50 return 0;51 }52 int main(){53 cnt = all = 0;54 while( scanf( "%s", ch[all] ) != EOF ){55 insert( ch[all] );56 all++;57 }58 for( int i = 0; i < all; ++i ){59 int n = strlen( ch[i] );60 for( int j = 0; j < n-1; ++j ){61 if( gao( i, 0, j ) && gao( i, j + 1, n-1 ) ){62 printf( "%s\n", ch[i] ); break;63 }64 }65 }66 return 0;67 }