排序的应用,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1828
#include "stdio.h" int num[50005][2]; int qu[50005]; int judge(int a,int b) { int ans=0; int i; for(i=0;i<2;i++) { if(num[qu[a]][i]>num[qu[b]][i]){ans=1;break;} if(num[qu[a]][i]<num[qu[b]][i]){ans=-1;break;} } return ans; } void swap(int a,int b) { int t; t=qu[a]; qu[a]=qu[b]; qu[b]=t; } int partion(int low,int high,int p) { while(low<=high) { if(low<p) { if(judge(low,p)>0){swap(low,p);p=low;} low++; } else { if(high>p) { if(judge(high,p)<0){swap(high,p);p=high;} } high--; } } return p; } void qsort(int left,int right) { int middle; if(left<right) { middle=(left+right)/2; middle=partion(left,right,middle); qsort(left,middle-1); qsort(middle+1,right); } } int main() { int n,i; int count,last; while(1) { scanf("%d",&n); if(n==0)break; for(i=0;i<n;i++){scanf("%d%d",&num[i][0],&num[i][1]);qu[i]=i;} qsort(0,n-1); count=1;last=n-1; for(i=n-2;i>=0;i--) { if(num[qu[i]][0]!=num[qu[i+1]][0]) { if(num[qu[i]][1]>num[qu[last]][1]) { count++; last=i; } } } printf("%d\n",count); } return 0; }
摘要: 大素数的判定,用拉宾-米勒素数测试,但是我竟然也加上了RHO,地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1811
/** *//*******************************************************************************************这里包含了rabinmi... 阅读全文
用了迭代法,但是有人说用DJ可以过的。
#include <stdio.h>
const int LEN = 1005;
const int MAX = 0x7fffffff;
int map[LEN][LEN];
void init ( int n ) {
for ( int i=0; i<n; i++ ) { for ( int j=0; j<n; j++ ) { if ( i == j ) { map[i][j] = 0; } else { map[i][j] = MAX; } } } }
int minest ( int a, int b ) {
return a < b ? a : b; }
int cost[LEN];
int bellman_ford ( int s, int t, int n ) { int v, u; int flag = 1; for ( v=0; v<n; v++ ) { cost[v] = map[s][v]; } while ( flag ) { flag = 0; for ( v=0; v<n; v++ ) { for ( u=0; u<n; u++ ) { if ( map[u][v] < MAX && cost[u] < MAX ) { int min = minest ( map[u][v], cost[u] ); if ( cost[v] < min || cost[v] == MAX ) { cost[v] = min; flag = 1; } } } } }
return cost[t]; }
int main () {
int t; int n, m; int b, e, len;
while ( scanf ( "%d", &t ) != EOF ) { for ( int i=1; i<=t; i++ ) { scanf ( "%d%d", &n, &m );
init ( n ); for ( int j=0; j<m; j++ ) { scanf ( "%d%d%d", &b, &e, &len ); map[b-1][e-1] = len; map[e-1][b-1] = len; }
printf ( "Scenario #%d:\n%d\n\n", i, bellman_ford ( 0, n-1, n ) ); } } return 0; }
地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
题目就是要我们将一个数表示成阶乘和的形式,用的好像是打表的方法吧。地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1775
#include <stdio.h>
const int MAXLEN = 1000001;
int num[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
char dp[MAXLEN][10];
void cup () { int i; for ( i=0; i<10; i++ ) { dp[0][i] = 0; } for ( i=1; i<MAXLEN; i++ ) { for ( int j=0; j<10; j++ ) { dp[i][j] = 0; int next = i - num[j]; if ( next == 0 ) { dp[i][j] = 1; } else { if ( next > 0 ) { for ( int z=0; z<j; z++ ) { if ( dp[next][z] ) { dp[i][j] = dp[next][z]; break; } } } } } } }
int main () { int n; cup (); while ( scanf ( "%d", &n ) != EOF && (n >= 0) ) { int i; for ( i=0; i<10; i++ ) { if ( dp[n][i] ) { printf ( "YES\n" ); break; } } if ( i >= 10 ) { printf ( "NO\n" ); } } return 0; }
摘要: 一个很无聊的题目,要注意负数的存在和溢出的问题。地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1730
#include <stdio.h>#include <math.h>const int MAX = 50000;int prime[MAX];int... 阅读全文
NOI的题目,其实就是中位数的一个应用吧。地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1723
#include <stdio.h> #include <stdlib.h> #include <math.h>
typedef struct { int x; int y; }type; type p[10001];
int cmpx ( const void *a, const void *b ) {
return ( ( type * )a )->x - ( ( type * )b )->x; }
int cmpy ( const void *a, const void *b ) {
return ( ( type * )a )->y - ( ( type * )b )->y; }
int main () {
int n;
while ( scanf ( "%d", &n ) != EOF ) { for ( int i=0; i<n; i++ ) { scanf ( "%d%d", &p[i].x, &p[i].y ); } if ( n == 1 ) { printf ( "0\n" ); continue; }
int mid; int ans = 0;
qsort ( p, n, sizeof ( type ), cmpy ); if ( ! n & 1 ) { mid = ( p[n/2].y + p[n/2-1].y ) / 2; } else { mid = p[n/2].y; } for ( i=0; i<n; i++ ) { ans += abs ( p[i].y - mid ); } qsort ( p, n, sizeof ( type ), cmpx ); for ( i=0; i<n; i++ ) { p[i].x -= i; } qsort ( p, n, sizeof ( type ), cmpx ); if ( ! n & 1 ) { mid = ( p[n/2].x + p[n/2-1].x ) / 2; } else { mid = p[n/2].x; } for ( i=0; i<n; i++ ) { ans += abs ( p[i].x - mid ); }
printf ( "%d\n", ans ); } return 0; }
一个简单的并查集的题目,要注意的是内部权值的修改。
#include <stdio.h>
int num[100001]; int dis[100001];
void init(int p) {
int i; for (i=0; i<p; i++) { num[i] = -1; dis[i] = 0; } }
int find(int a) {
int i = a; int count = 0; int temp;
while (num[i]>=0) { count += dis[i]; i = num[i]; } while (a!=i) { count -= dis[a]; dis[a] += count; temp = a; a = num[a]; num[temp] = i; }
return i; }
void un(int a, int b) { int ra = find(a); int rb = find(b);
if(num[ra]<=num[rb]) { num[ra] += num[rb]; num[rb] = ra; dis[rb] = dis[a] -dis[b] +1; } else { num[rb] += num[ra]; num[ra] =rb; dis[ra] = dis[b] - dis[a] -1; } }
int main() {
int t, n, m; int l, rl, r, rr; char ch[3]; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); init(n); while (m--) { scanf("%s%d%d", &ch, &l, &r);
rl = find(l-1); rr = find(r-1); if (ch[0]=='D') { if(rl!=rr) { un(l-1, r-1); } } else { if (rl!=rr) { printf("Not sure yet.\n"); } else { if (dis[l-1]%2==dis[r-1]%2 || dis[l-1]%2==-dis[r-1]%2) { printf("In the same gang.\n"); } else { printf("In different gangs.\n"); } } } } } return 0; }
地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1703
摘要: 一个最小生成树的题目,用并查集判连通。地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1679
#include <stdio.h>#include <stdlib.h>const int LEN = 105;struct{ &nb... 阅读全文
模拟题目,地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1573
#include <stdio.h>
struct { char done;//动作 int depth;//深度 }map[11][11];
int hash[26][2];
int ans; int last;
int dfs ( int s, int r, int c ) { int now[2] = {0, s}; ans = 0; while ( now[0]>=0 && now[0]<r && now[1]>=0 && now[1]<c ) { if ( map[ now[0] ][ now[1] ].done == 0 ) { last = ans; ans = map[ now[0] ][ now[1] ].depth; return 0; } map[ now[0] ][ now[1] ].depth = ans++; int temp[2]; temp[0] = hash[ map[now[0]][now[1]].done-'A' ][0]; temp[1] = hash[ map[now[0]][now[1]].done-'A' ][1]; map[ now[0] ][ now[1] ].done = 0; now[0] += temp[0]; now[1] += temp[1]; } return 1; }
int main () { int n, m, s; hash[ 'E'-'A' ][0] = 0, hash[ 'E'-'A' ][1] = 1; hash[ 'S'-'A' ][0] = 1, hash[ 'S'-'A' ][1] = 0; hash[ 'W'-'A' ][0] = 0, hash[ 'W'-'A' ][1] = -1; hash[ 'N'-'A' ][0] = -1, hash[ 'N'-'A' ][1] = 0; while ( scanf ( "%d%d%d", &n, &m, &s ) != EOF && ( n || m || s ) ) { getchar (); for ( int i=0; i<n; i++ ) { for ( int j=0; j<m; j++ ) { scanf ( "%c", &map[i][j].done ); } getchar (); }
if ( dfs ( s-1, n, m ) ) { printf ( "%d step(s) to exit\n", ans ); } else { printf ( "%d step(s) before a loop of %d step(s)\n", ans, last-ans ); } } return 0; }
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
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 | 8 | 9 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|