HNU - nazgul's Blog
旅行
小王最近刚买了新车，非常兴奋，于是决定开车出去旅游。但是从他家到旅游目的地没有直接连接的道路，他中间必须经过其他的城市才能到达目的地。
一开始时，他的汽车每单位时间走单位路程，但是当经过一个城市后，他需要增加一个单位时间才能走单位路程，请编程计算他如何开车才能最快到达目的地。
输入：第一行是测试用例个数。对每一个测试用例，第一行是两个数n and m (0 < n ≤ 200, 0 < m < n×(n-1)/2 )，n是城市的编号，编号1是他的出发点，n是目的地，m是城市之间存在的路的条数，道路可双向行驶。
接来的m行，每行包含3个数x, y, z，表示从城市x到城市y有一条道路，距离是z，（假设从家到目的地总至少有一条通路）。
输出： 从家到目的地最少的时间。
样例输入：
5 6
1 2 1
1 4 5
2 3 2
3 5 1
4 5 1
2 4 2
样例输出：
7
本题不能用一般的最短路来求，因为并不一定是每次都走最短的边就能得出最小值。
我们可以认为每条边的权值为k*x，k为边的初始权值，x为该走法经过的点的个数，最开始x为1，如果我们按x逐步增大来递推，那么可以知道，如果一个节点第x(x>1)
次经过时，只有当走这条路到达这个点的花费小于之前到达该点的最小值，这样走才可能使这次更新有意义。
因此我们可以定义一个3重循环，第一重为步数x，第2重为该步数有被更新的点i，如果i有在第x步被更新则进入第3重循环让他们去更新他们能到达的其他点，当所有点无法被更新时结束。最坏的情况下时间复杂度为n3。
#include <stdio.h>
#include <string.h>
#define MAX 0x7f7f7f7f
int d[501][501],dis[501][501],mx[501],pre[501];
int main()
{
int tt, bb;
int n, m, i, j, x, y, z, flag;
scanf( "%d", &tt );
for ( bb=0; bb<tt; bb++)
{
scanf( "%d%d", &n, &m );
memset( d, 0, sizeof( d ) );
for ( i=1; i<=m; i++ )
{
scanf( "%d%d%d", &x, &y, &z );
d[x][y] = d[y][x] = z;
}
memset( mx, 127, sizeof( mx ) );
memset( dis, 127, sizeof( dis ) );
dis[0][1] = 0; mx[1] = 0;
for ( x=0; ; x++ )
{
for ( flag=0, i=1; i<=n; i++ )
{
if ( dis[x][i] != MAX )
{
flag = 1;
for ( j=1; j<=n; j++ )
{
if ( d[i][j] != 0 && mx[j] > dis[x][i] + d[i][j]*( x+1 ) )
{
mx[j] = dis[x][i] + d[i][j]*(x+1);
dis[x+1][j] = mx[j];
}
}
}
}
if ( flag == 0 ) break;
}
printf("%d\n",mx[n]);
}
return 0;
}
The QianJin Teaching Building
http://acm.hnu.cn/online/?action=problem&type=show&id=11444
二维树状数组支持两种操作,一种修改二维数组中任意元素的值,另一种是查询任意范围的元素和.
题目中的4种操作都可以用以上两种操作完成.
#include <stdio.h>
#include <string.h>
#define maxn 1002
int c[maxn][maxn];
int lowbit( int x )
{
return x & ( -x );
}
int sum( int x, int y )
{
int i, j, t=0;
for ( i=x; i>0; i-=lowbit(i) )
for ( j=y; j>0; j-=lowbit(j) )
t += c[i][j];
return t;
}
void Insert( int x, int y, int a )
{
int i, j;
for ( i=x; i<maxn; i+=lowbit(i) )
for ( j=y; j<maxn; j+=lowbit(j) )
c[i][j] += a;
}
int Query( int x1, int y1, int x2, int y2 )
{
return sum( x2, y2 )-sum( x1-1, y2 )-sum( x2, y1-1 )+sum( x1-1, y1-1 );
}
int main()
{
int cases, T, m, x1, y1, x2, y2, v, t;
char s[2];
//freopen( "//home//administrator//32.in", "r", stdin );
//freopen( "//home//administrator//test.out", "w", stdout );
scanf( "%d", &cases );
for ( T=1; T<=cases; ++T )
{
printf( "Case %d:\n", T );
memset( c, 0, sizeof( c ) );
scanf( "%d", &m );
while ( m-- )
{
scanf( "%s", s );
if ( s[0] == 'A' )
{
scanf( "%d%d%d", &x1, &y1, &v );
x1++; y1++;
Insert( x1, y1, v );
}
else
if ( s[0] == 'D' )
{
scanf( "%d%d%d", &x1, &y1, &v );
x1++; y1++;
t = Query( x1, y1, x1, y1 )+1;
if ( v > t ) v = t;
Insert( x1, y1, -v );
}
else
if ( s[0] == 'M' )
{
scanf( "%d%d%d%d%d", &x1, &y1, &x2, &y2, &v );
x1++; y1++; x2++; y2++;
t = Query( x1, y1, x1, y1 )+1;
if ( v > t ) v = t;
Insert( x1, y1, -v );
Insert( x2, y2, v );
}
else
if ( s[0] == 'S' )
{
scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 );
x1++; y1++; x2++; y2++;
if ( x1 > x2 )
{
v = x1; x1 = x2; x2 = v;
}
if ( y1 > y2 )
{
v = y1; y1 = y2; y2 = v;
}
v = Query( x1, y1, x2, y2 )+( x2-x1+1 )*( y2-y1+1 );
printf( "%d\n", v );
}
}
}
return 0;
}
The nearest taller cow
http://acm.hnu.cn/online/?action=problem&type=show&id=11449
用一个栈进行扫描，维护栈内元素的单调性
分别求出每个元素左边和右边的最近的更高元素，再取最大值，最后再求和取均值。
以求左边的为例，先从左往右扫描，遇到小于等于栈顶元素的数就将这个数入栈，继续向后扫；如果大于则弹出栈顶元素，并设置其左边最近元素为此新元素。
#include <stdio.h>
#include <string.h>
#define NIL 0x01010101
int a[1000001], f[1000001];
int q[1000001], l;
int main()
{
int n, t, i, j, imax ;
double tt;
//freopen( "//home//administrator//2.in", "r", stdin );
scanf( "%d", &t );
while ( scanf( "%d", &n ) != EOF )
{
memset( f, 1, sizeof( f ) );
for ( imax=i=0; i<n; i++ )
{
scanf( "%d", &a[i] );
if ( imax < a[i] ) imax = a[i];
}
l = -1;
for ( i=0; i<n; ++i )
{
while ( l >= 0 && a[i] >= a[q[l]] )
{
/×如果当前值等于栈中元素，则它最近距离为它到与它相等的距离+那个相等的数的最近距离×/
if ( a[i] == a[q[l]] )
{
f[i] = f[q[l]]+i-q[l];
break;
}
/×如果最短距离可以更新*/
if ( f[q[l]] > i-q[l] )
f[q[l]] = i-q[l];
l--;
}
/*找到栈中比a[i]大的数，记录距离*/
if ( l != -1 && a[i] != a[q[l]] ) f[i] = i-q[l];
/*入栈*/
q[++l] = i;
}
tt = 0;
for ( i=0; i<n; ++i )
{
if ( a[i] == imax || f[i] == NIL ) f[i] = n;
tt += f[i];
}
/*注意进位*/
printf( "%.2f\n", ( tt*100+0.5 )/100/n );
}
return 0;
}
hnu 11450
http://acm.hnu.cn/online/?action=problem&type=show&id=11450
用trie树记录所有可能的基因，然后用背包。对第i个背包时计算出从i开始可以扩展的所有j的值。
即f[i+len(gene)] = max{ f[i+len(gene)], f[i]+v[gene] )，gene是从i开始可以找到的基因。
#include <stdio.h>
#include <string.h>
struct node
{
int value;
int nt[4];
}trie[289000];
int now;
int f[10110];
char s[10001];
int CharToInt( char c )
{
switch ( c )
{
case 'A': return 0;
case 'T': return 1;
case 'C': return 2;
case 'G': return 3;
}
}
void Trie_Insert( char *s, int p )
{
int k = 0, t;
while ( *s )
{
t = CharToInt( *s );
if ( trie[k].nt[t] == 0 )
{
trie[k].nt[t] = now++;
}
k = trie[k].nt[t];
s++;
}
trie[k].value = p;
}
void Trie_Search( char *s, int l )
{
int k = 0, i = l, t;
while ( *s )
{
k = trie[k].nt[CharToInt( *s )];
if ( k == 0 ) break;
t = trie[k].value;
if ( t )
{
if ( l == 0 )
{
if ( t > f[i] ) f[i] = t;
}
else
if ( f[i] < t+f[l-1] )
f[i] = f[l-1] + t;
}
i++; s++;
}
}
int DynamicProg( char *s )
{
int len = strlen( s ), i, Max = 0;
for ( i=0; i<len; ++i )
{
Trie_Search( s+i, i );
if ( i && f[i] < f[i-1] ) f[i] = f[i-1];
if ( Max < f[i] ) Max = f[i];
}
return Max;
}
int main()
{
int T = 1, p, n;
while ( scanf( "%d", &n ) != EOF )
{
printf( "Case %d: ", T++ );
memset( trie, 0, sizeof( trie ) );
memset( f, 0, sizeof( f ) );
now = 1;
while ( n-- )
{
scanf( "%s%d", s, &p );
Trie_Insert( s, p );
}
scanf( "%s", s );
printf( "%d\n", DynamicProg( s ) );
}
return 0;
}