也不知道是什么题目了，贴上去再说
 #include < stdio.h >
#include < stdlib.h >
#define MIN -100000000
int num1[100005];
int num2[100005];
int dp1[100005];
int dp2[100005];
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 n;
int i;
int max;
int left, right;
while ( scanf ( "%d", &n ) != EOF && 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>const int LEN = 10005;int flag; //强连通分支标号struct HEAD //结点头{ int state; //搜索处在的状态 ... 阅读全文
摘要: 想计算几何，但是事快排题目
#include <stdio.h>#include <stdlib.h>const int LEN = 10005;struct{ int x; int y;}p[LEN]... 阅读全文
并差集
#include <stdio.h>
int stu[50005];
void make ( int n )
{
for ( int i=0; i<n; i++ )
{
stu[i] = -1;
}
}
int find ( int a )
{
if ( stu[a] < 0 )
{
return a;
}
int root = find ( stu[a] );
stu[a] = root;
return root;
}
void un ( int a, int b )
{
int ra = find ( a );
int rb = find ( b );
stu[rb] = ra;
}
int main ()
{
int n, m;
int c = 0;
while ( scanf ( "%d%d", &n, &m ) != EOF )
{
if ( n == 0 && m == 0 )
{
break;
}
make ( n );
for ( int i=0; i<m; i++ )
{
int l, r;
scanf ( "%d%d", &l, &r );
if ( find ( l-1 ) != find ( r-1 ) )
{
un ( l-1, r-1 );
}
}
int count = 0;
for ( i=0; i<n; i++ )
{
if ( stu[i] < 0 )
{
count ++;
}
}
printf ( "Case %d: %d\n", ++c, count );
}
return 0;
}
并差集的应用
#include <stdio.h>
const int LEN = 2005;
struct
{
int fa;
int dis;
}p[LEN];
void make ( int n )
{
for ( int i=0; i<n; i++ )
{
p[i].fa = -1;
p[i].dis = 0;
}
}
int find ( int a )
{
if ( p[a].fa < 0 )
{
return a;
}
int r = find ( p[a].fa );
p[a].dis += p[ p[a].fa ].dis;
p[a].fa = r;
return r;
}
void un ( int a, int b )
{
int ra = find ( a );
int rb = find ( b );
p[rb].fa = ra;
p[rb].dis = p[a].dis + 1 - p[b].dis;
}
int main ()
{
int t;
int m, n;
int a, b;
scanf ( "%d", &t );
for ( int count = 1; count <= t; count ++ )
{
scanf ( "%d%d", &n, &m );
make ( n );
int flag = 1;
for ( int i=0; i<m; i++ )
{
scanf ( "%d%d", &a, &b );
if ( flag )
{
a --;
b --;
int ra = find ( a );
int rb = find ( b );
if ( ra != rb )
{
un ( a, b );
}
else
{
if ( !( ( p[a].dis + p[b].dis ) & 1 ) )
{
printf ( "Scenario #%d:\nSuspicious bugs found!\n\n", count );
flag = 0;
}
}
}
}
if ( flag )
{
printf ( "Scenario #%d:\nNo suspicious bugs found!\n\n", count );
}
}
return 0;
}
生成树，发现自己写了好多生
#include <stdio.h>
#include <stdlib.h>
int city[505];
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;
}
}
void init ( int n )
{
for ( int i=0; i<n; i++ )
{
city[i] = 0;
}
}
typedef struct
{
int b;
int e;
int len;
}type;
type seg[200000];
int cmp ( const void *a, const void *b )
{
return ( ( type * )a )->len - ( ( type * )b )->len;
}
int main ()
{
int t;
int n;
int m;
int l;
while ( scanf ( "%d", &t ) != EOF )
{
while ( t -- )
{
scanf ( "%d", &n );
m = 0;
for ( int i=0; i<n; i++ )
{
for ( int j=0; j<n; j++ )
{
scanf ( "%d", &l );
if ( j > i )
{
seg[m].b = i;
seg[m].e = j;
seg[m].len = l;
m ++;
}
}
}
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 <math.h>const __int64 MAX = 47000;__int64 prime[MAX];__int64 number[MAX];__int64 find ( __int64&n... 阅读全文
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 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)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|