使用的是遞歸算法，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1564
 #include <stdio.h>
#include <stdlib.h>
int cmp ( const void *a, const void *b )
   {
return *( int * )b - *( int * )a;
 }
int n;
int num[15];
int stack[15];
int flag;
void print ( int len, int s, int last )
{
int fa = -1;
for ( int i=s; i<n; i++ )
  {
if ( last - num[i] == 0 && num[i] != fa )
{
stack[len] = num[i];
for ( int i=0; i<len; i++ )
{
printf ( "%d+", stack[i] );
 }
printf ( "%d\n", stack[i] );
flag = 1;
}
else
{
if ( last - num[i] > 0 && num[i] != fa )
{
stack[len] = num[i];
print ( len+1, i+1, last-num[i] );
}
}
fa = num[i];
}
}
int main ()
{
int t;
while ( scanf ( "%d%d", &t, &n ) != EOF && ( t || n ) )
{
for ( int i=0; i<n; i++ )
{
scanf ( "%d", &num[i] );
}
qsort ( num, n, sizeof ( int ), cmp );
flag = 0;
printf ( "Sums of %d:\n", t );
print ( 0, 0, t );
if ( ! flag )
{
printf ( "NONE\n" );
}
}
return 0;
}
入門的廣搜問題，地址： http://acm.pku.edu.cn/JudgeOnline/problem?id=1562
#include "stdio.h"
char fi[105][105];
int move[8][2]={0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1};
int qu[10005][2];
int head,tail;
void begin()
{
head=0;
tail=-1;
}
void inq(int l,int c)
{
++tail;
qu[tail][0]=l;
qu[tail][1]=c;
}
void outq()
{
head++;
}
int empty()
{
if(head>tail)return 1;
return 0;
}
void search(int l,int c,int n,int m)
{
int tl,tc,i;
begin();
inq(l,c);
fi[l][c]='*';
while(!empty())
{
tl=qu[head][0];
tc=qu[head][1];
outq();
for(i=0;i<8;i++)
{
tl+=move[i][0];
tc+=move[i][1];
if(tl>=0&&tl<n&&tc>=0&&tc<m)
{
if(fi[tl][tc]=='@')
{
inq(tl,tc);
fi[tl][tc]='*';
}
}
tl-=move[i][0];
tc-=move[i][1];
}
}
}
int main()
{
int n,m;
int i,j;
int count;
while(1)
{
scanf("%d%d",&m,&n);
if(m==0&&n==0)break;
for(i=0;i<m;i++)
{
scanf("%s",&fi[i][0]);
}
count=0;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(fi[i][j]=='@')
{
search(i,j,m,n);
count++;
}
}
}
printf("%d\n",count);
}
return 0;
}
二分匹配的問題，使用的是匈牙利算法，地址： http://acm.pku.edu.cn/JudgeOnline/problem?id=1469
#include "stdio.h"
#include<string.h>
const int M = 505;
bool canmatch[M][M];
int ser(int leftnum,int rightnum,int cur,int* link,bool *used)
{
int i;
for(i=1;i<=rightnum;i++)
{
if( canmatch[cur][i]==1 && !used[i] )
{
used[i]=true;
if(link[i]==0||ser(leftnum,rightnum,link[i],link,used))
{
link[i]=cur;
return true;
}
}
}
return false;
}
int Match( int leftnum ,int rightnum )
{
int ans=0 , i;
bool *used = new bool[(rightnum+1)] ;
int *link = new int [(rightnum+1)] ;
memset(link,0,sizeof(int)*(rightnum+1));
for(i=1;i<=leftnum;i++)
{
memset(used,0,sizeof(bool)*(rightnum+1));
if(ser(leftnum,rightnum,i,link,used))
ans++;
}
return ans;
}
void initm ( int n )
{
for ( int i=0; i<=n; i++ )
{
for ( int j=0; j<=n; j++ )
{
canmatch[i][j] = false;
}
}
}
int main ()
{
int t;
int p, n;
int i, j;
scanf ( "%d", &t );
while ( t -- )
{
scanf ( "%d%d", &p, &n );
int count;
initm ( p<n ? n:p );
for ( i=1; i<=p; i++ )
{
scanf ( "%d", &count );
int in;
for ( j=0; j<count; j++ )
{
scanf ( "%d", &in );
canmatch[ i ][ in ] = true;
}
}
if ( Match ( p, n ) == p )
{
printf ( "YES\n" );
}
else
{
printf ( "NO\n" );
}
}
return 0;
}
摘要: 最大流的應(yīng)用，最小路徑覆蓋，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1422
/**//*距離標(biāo)號的最大流*/#include <stdio.h>const int LEN = 500;const int MAX = 0x7fffffff;... 閱讀全文
摘要: 這個題目可以打表過，也可以尋找循環(huán)結(jié)的方法過。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1338
#include<stdio.h>__int64 data[]={0,1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,7... 閱讀全文
摘要: 最近公共祖先問題，求的是中兩個節(jié)點的最近公共祖先。使用了一個帶并查集的離線算法。
#include <stdio.h>const int LEN = 10005;int p[LEN];void make ( int n ){ &n... 閱讀全文
一個字符串處理的問題，做法是排序+二分查找。地址： http://acm.pku.edu.cn/JudgeOnline/problem?id=1318
#include < stdio.h >
#include < stdlib.h >
#include < string.h >
typedef struct
{
char unch[8];
char ch[8];
}type;
type word[101];
int cmp1 ( const void *a, const void *b )
{
return *( char * )a - *( char * )b;
}
int cmp2 ( const void *a, const void *b )
{
type *c = ( type * )a;
type *d = ( type * )b;
int ans;
ans = strcmp ( c->ch, d->ch );
if ( !ans )
{
return strcmp ( c->unch, d->unch );
}
return ans;
}
void sort ( int n )
{
for ( int i=0; i<n; i++ )
{
qsort ( word[i].ch, strlen( word[i].ch ), sizeof( char ), cmp1 );
}
qsort ( word, n, sizeof( type ), cmp2 );
}
int main ()
{
char input[8];
char end[] = "XXXXXX";
int n;
type in;
n = 0;
while ( scanf ( "%s", input ) != EOF && strcmp( input, end ) )
{
strcpy ( word[n].unch, input );
strcpy ( word[n].ch, input );
n ++;
}
sort ( n );
while ( scanf ( "%s", input ) != EOF && strcmp( input, end ) )
{
int left, right, middle;
left = 0; right = n-1;
strcpy ( in.unch, input );
strcpy ( in.ch, input );
qsort ( in.ch, strlen ( in.ch ), sizeof( char ), cmp1 );
while ( left <=right )
{
middle = ( left + right ) / 2;
if ( strcmp ( word[middle].ch, in.ch ) >=0 )
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
if ( left < n && ( ! strcmp ( word[left].ch, in.ch ) ) )
{
int low, high;
low = left; high = left;
while ( low > 0 && ( ! strcmp ( word[low - 1].ch, in.ch ) ) )
{
low --;
}
while ( high < n-1 && ( ! strcmp ( word[high+1].ch, in.ch ) ) )
{
high ++;
}
for ( ; low<=high; low ++ )
{
printf( "%s\n", word[low].unch );
}
}
else
{
printf ( "NOT A VALID WORD\n" );
}
printf ( "******\n" );
}
return 0;
}
摘要: 做法是使用并查集判環(huán)，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1308
#include <stdio.h>int point[14];void make ( int n ){ for ( in... 閱讀全文
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 25 | 26 | 27 | 28 | 29 | 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)
隨筆檔案
搜索
最新評論
閱讀排行榜
評論排行榜
|
|