动态规划
 #include < stdio.h >
#include < stdlib.h >
#define MIN -100000
int num1[50005];
int num2[50005];
int dp1[50005];
int dp2[50005];
int cmp ( const void *a, const void *b )
   {
return *( int * )a - *( int * )b;
 }
void find ( int n, int s[], int dp[] )
{
int sum = 0;
int ans = MIN;
for ( int i=0; i<n; i++ )
  {
if ( sum > 0 )
{
sum += s[i];
 }
else
{
sum = s[i];
}
if ( sum > ans )
{
ans = sum;
}
dp[i] = ans;
}
}
int check ( int n )
{
int count = 0;
for ( int i=0; i<n; i++ )
{
if ( num1[i] > 0 )
{
count ++;
}
}
return count;
}
int main ()
{
int t, n;
int i;
int max;
int left, right;
scanf ( "%d", &t );
getchar ();
getchar ();
while ( t -- )
{
scanf ( "%d", &n );
for ( i=0; i<n; i++ )
{
scanf ( "%d", &num1[i] );
num2[n-i-1] = num1[i];
}
if ( check ( n ) < 2 )
{
qsort ( num1, n, sizeof ( int ), cmp );
printf ( "%d\n", num1[n-2]+num1[n-1] );
}
else
{
find ( n, num1, dp1 );
find ( n, num2, dp2 );
max = MIN;
for ( i=0; i<=2*n; i++ )
{
if ( i&1 )
{
left = i / 2;
right = n - ( i / 2 + 1 ) - 1;
}
else
{
left = i / 2 - 1;
right = n - ( i / 2 + 1 ) - 1;
}
if ( left >= 0 && left < n && right >= 0 && right < n )
{
if ( dp1[left] + dp2[right] > max )
{
max = dp1[left] + dp2[right];
}
}
}
printf ( "%d\n", max );
}
}
return 0;
}
摘要: 生成树算法
#include "stdio.h"int table[105][105];int e[5005][3];int qu[5005];int node[105];int judge(int a,int b){ if(e[qu[a]][2]>e[qu[b]]... 阅读全文
传说中的字典树
#include <stdio.h>
#include <string.h>
#include "stdlib.h"
char in[35];
typedef struct
{
int next[53];
int count;
}node;
node trie[150005];
int now;
char st[10005][35];
int snow;
void init()
{
memset(&trie[0],0,sizeof(trie));
now = 1;
snow = -1;
}
int cmp(const void *a, const void *b)
{
return strcmp((char *)a, (char *)b);
}
int insert(char *str, int len)
{
int i;
int p = 0;
int hash;
for (i=0; i<len; i++)
{
hash = str[i]-20;
if (!trie[p].next[hash])
{
memset(&trie[now], 0, sizeof(node));
trie[p].next[hash] = now++;
}
p = trie[p].next[hash];
}
trie[p].count++;
return p;
}
int search(char *str, int len)
{
int i;
int p = 0;
int hash;
for (i=0; i<len; i++)
{
hash = str[i]-20;
if (!trie[p].next[hash])
{
return 0;
}
p = trie[p].next[hash];
}
if(!trie[p].count)
{
return 0;
}
return p;
}
int main()
{
int p, i;
int count = 0;
int len;
init();
while (gets(in))
{
len = strlen(in);
p = search(in, len);
if (!p)
{
insert(in, len);
strcpy(st[++snow], in);
}
else
{
trie[p].count ++;
}
count ++;
}
qsort(st, snow+1, sizeof(st[0]), cmp);
for (i=0; i<snow+1; i++)
{
printf("%s", &st[i]);
len = strlen(st[i]);
printf(" %.4lf\n", (double)trie[search(st[i], len)].count/(double)count*100);
}
return 0;
}
摘要: 欧拉函数的应用
#include <stdio.h>#include <math.h>const int MAX = 32000;int prime[MAX];int number[MAX];int find ( int n ){ &... 阅读全文
生成树算法的一个应用
#include <stdio.h>
#include <stdlib.h>
int city[2005];
void make ( int n )
{
for ( int i=0; i<n; i++ )
{
city[i] = -1;
}
}
int find ( int a )
{
if ( city[a] < 0 )
{
return a;
}
int root = find ( city[a] );
city[a] = root;
return root;
}
void un ( int a, int b )
{
int ra = find ( a );
int rb = find ( b );
if ( city[ra] < city[rb] )
{
city[ra] += city[rb];
city[rb] = ra;
}
else
{
city[rb] += city[ra];
city[ra] = rb;
}
}
typedef struct
{
int b;
int e;
int len;
}type;
type seg[10005];
int cmp ( const void *a, const void *b )
{
return ( ( type * )a )->len - ( ( type * )b )->len;
}
int main ()
{
int n, m;
int a, b, l;
while ( scanf ( "%d%d", &n, &m ) != EOF )
{
for ( int i=0; i<m; i++ )
{
scanf ( "%d%d%d", &a, &b, &l );
seg[i].b = a - 1;
seg[i].e = b - 1;
seg[i].len = l;
}
qsort ( seg, m, sizeof ( type ), cmp );
int max = -1;
make ( n );
for ( i=0; i<m; i++ )
{
if ( find ( seg[i].b ) != find ( seg[i].e ) )
{
if ( max < seg[i].len )
{
max = seg[i].len;
}
un ( seg[i].b, seg[i].e );
}
}
printf ( "%d\n", max );
}
return 0;
}
大数
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int OneNode = 1000000; //一位里不能超过OneNode
const int NodeLen = 6; //一位储存NodeLen位，和OneNode必须同时更改,输出部分格式必须跟随这里!!!
const int NumMax = 50; //储存位数限制，真实位数为NumMax*6
struct BigNum
{
unsigned num[NumMax] ;//高位 对 下标大位
unsigned numlen ;
void set(unsigned sm=0){ num[0] = sm ; numlen = 1; }//sm<OneNode
void set(char *string , int strlen)
{
numlen = (strlen-1) / NodeLen + 1 ;
memset (num , 0 , sizeof(unsigned)*numlen );
int temp , i ;
for( i=strlen-1 ; i>=0 ; i-- )
{
temp = i / NodeLen ;
num[temp] = num[temp]*10 + string[strlen-1-i]-'0' ;
}
}
void print()
{
printf("%d",num[numlen-1]);
int i = numlen-1;
while( i )
{
i--;
printf("%06d",num[i]);
}
printf("\n");
}
};
void Mul(BigNum &a,BigNum &b,BigNum &c) // a*b ->c
{
unsigned carry = 0 , lenmax = a.numlen+b.numlen-1 ,i,j ;
unsigned __int64 temp ;
c.numlen = lenmax;
for ( i=0 ; i<lenmax ; i++ )
{
temp = carry ;
for ( j=0 ; j<a.numlen ; j++ )
{
if ( i<j )
break;
if ( i-j >= b.numlen )
{
j = i-b.numlen ;
continue;
}
temp += (unsigned __int64)a.num[j] * b.num[i-j] ;
}
carry = temp / OneNode ;
c.num[i] = temp % OneNode ;
}
if(carry)
{
c.num[i] = carry ;
c.numlen ++;
}
}
BigNum a, b, c;
char ta[41], tb[41];
int main()
{
while(scanf("%s%s", ta, tb) != EOF)
{
a.set(ta, strlen(ta));
b.set(tb, strlen(tb));
Mul(a, b, c);
c.print();
}
return 0;
}
运算
最短路径算法
//面向邻接链表的DJ
#include <stdio.h>
const int MAX = 0x7fffffff;
struct
{
int next;
int last;
}head[1001];
typedef struct
{
int next;
int valu;
int dis;
}type;
type p[40001];
int now;
void initm ( int n )
{
for ( int i=0; i<n; i++ )
{
head[i].next = head[i].last = -1;
}
}
void add ( int b, int e, int d )
{
p[now].next = -1;
p[now].valu = e;
p[now].dis = d;
if ( head[b].next == -1 )
{
head[b].next = now;
}
else
{
p[ head[b].last ].next = now;
}
head[b].last = now ++;
}
int used[1001];
int dis[1001];
void initdj ( int s, int n, int *di )
{
for ( int i=0; i<n; i++ )
{
used[i] = 0;
di[i] = MAX;
}
di[s] = 0;
}
int dj ( int s, int t, int n, int *di )
{
initdj ( s, n, di );
int i, j;
int now;
for ( i=0; i<n; i++ )
{
type min;
min.dis = MAX;
for ( j=0; j<n; j++ )
{
if ( min.dis > di[j] && ! used[j] )
{
min.dis = di[j];
min.valu = j;
}
}
if ( min.valu == t )
{
break;
}
now = min.valu;
used[ min.valu ] = 1;
for ( j=head[now].next; j!=-1; j=p[j].next )
{
if ( ! used[ p[j].valu ] && di[ p[j].valu ] > di[now] + p[j].dis )
{
di[ p[j].valu ] = di[now] + p[j].dis;
}
}
}
return di[t];
}
int main ()
{
int t, n;
int b, e, r;
while ( scanf ( "%d%d", &t, &n ) != EOF )
{
initm ( n );
for ( int i=0; i<t; i++ )
{
scanf ( "%d%d%d", &b, &e, &r );
add ( b-1, e-1, r );
add ( e-1, b-1, r );
}
printf ( "%d\n", dj ( n-1, 0, n, dis ) );
}
return 0;
}
BFS或者DFS的入门题目
#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]=='W')
{
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(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%s",&fi[i][0]);
}
count=0;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(fi[i][j]=='W')
{
search(i,j,n,m);
count++;
}
}
}
printf("%d\n",count);
}
return 0;
}
摘要: 复杂的排序
int acm[1005][3];int num[1005][4];int qu[1005];int judge(int a,int b,int type){ int i; int ans=0; ... 阅读全文
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 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 | 10 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|