排序的應用，地址： 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;
}
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 30 | 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 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
決定從線程開始!!
常用鏈接
留言簿(6)
隨筆檔案
搜索
最新評論
閱讀排行榜
評論排行榜
|
|