Showing posts with label NOIP. Show all posts
Showing posts with label NOIP. Show all posts

Tuesday, November 6, 2012

NOIP 2005 等价表达式

题目大意:输入多个代数表达式(其中只有'+','-','*','^',0~10000的整数,以及一个未知数a),要求输出与第一行表达式等价的表达式的序号。

显然,要电脑做表达式展开是不太可能的。但是,我们可以指定a的值,代入表达式计算,若结果相等,就认为两个表达式是等价的。当然,这样做是有误判风险的,因此可以对a取不同的值,依次带入。两个表达式相等当且仅当对所有测试的a值它们的结果都相等。

最关键的部分就是表达式求值了,方法是先把表达式转换成后序表达式,然后带入a的值求结果,这两个操作都涉及到栈的使用。具体原理和方法,读者可以参考本人的这篇文章。

此外,输入表达式中没有除号,而直接计算结果可能会超出long的范围,因此可以利用同余的性质,避免高精度。

代码如下:

Monday, October 29, 2012

安排警卫题解

题目大意:有一个由N个节点构成的树,在每个节点安排警卫的花费都不同,只有在某个节点布置警卫,或者在其某个相邻节点布置警卫,才可以保证这个节点安全。求:要让所有节点都安全,最少的花费是多少。

容易看出问题的最优子结构性质,因此考虑树形动态规划。那么,要如何表示状态呢?本人用f[x][0]表示在x节点不放置警卫,使以x为根的子树安全的最小花费;f[x][1]表示在x放置警卫,使以x为根的子树安全的最小花费。不过,这个状态表示不能包括下面这个情形:
[1](10)------[2](20)------[3](30)------[4](5)
方括号内是节点编号,圆括号内是安排警卫的费用, 此时的最优解是15,而本人的解是25.

因此,增加一个状态,用f[x][2]表示不再x安排警卫,在x的父亲节点安排。

由于转移方程要考虑多种情况,较为复杂,读者请直接看代码。

Friday, October 26, 2012

包含指定元素的最长上升序列

题目要求:给出一个长度为N整数序列,请求出它的包含第K个元素的最长上升子序列。
很明显,可以求出1~(K-1)中小于v[K]的元素构成的LIS的长度l1,再求出(K+1)~N中大于v[K]的元素构成的LIS的长度l2,l1+l2+1即为包含第K个元素的LIS的长度。

求解LIS的nlogn算法可以参考本人的最长不上升子序列 。

需要注意的是,本题要求的是严格上升序列的长度,即序列中不能存在值相等的元素。
因此对于某个值v,只有在v严格大于S[top]才可以S[++top]=v.
若小于等于S[top],则要在S中找大于等于v的S[t],而不是大于v的。否则求出来的可能是最长不下降序列。

代码如下

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN (200000+10)

long N,K;
long v[MAXN];
long ans1,ans2;
long tmp[MAXN],len;

void init()
{
   scanf("%ld%ld\n",&N,&K);
   long i;
   for(i = 1;i <= N;i ++)
       scanf("%ld",&v[i]);
}

long lis()   //计算tmp中的LIS
{
   static long S[MAXN];
   long top = 1;
   S[top] = tmp[0];
   long l,r,mid,i;
   fprintf(stderr,"len %ld\n",len);
   for(i = 1;i < len;i ++)
   {
       if(tmp[i] > S[top])
           S[++top] = tmp[i];
       else
       {
           l = 1;
           r = top;
           while(l < r)
           {
               mid = (l + r) / 2;
               if(S[mid] >= tmp[i])
                   r = mid;
               else
                   l = mid + 1;
           }
           S[l] = tmp[i];
       }
   }
   return top;
}

void solve()
{
   long i;
   len = 0;
   for(i = 1;i < K;i ++)
       if(v[i] < v[K])    tmp[len ++] = v[i];
   if(len > 0)
       ans1 = lis();
   else
       ans1 = 0;
   len = 0;
   for(i = K + 1;i <= N;i ++)
       if(v[i] > v[K])    tmp[len ++] = v[i];
   if(len > 0)
       ans2 = lis();
   else
       ans2 = 0;
   printf("%ld\n",ans1 + 1 + ans2);
}

int main()
{
   freopen("lis.in","r",stdin);
   freopen("lis.out","w",stdout);
   init();
   solve();
   fclose(stdout);
   return 0;
}

Thursday, October 25, 2012

最长不上升子序列

题目描述:
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:
虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入数据:
第一行为一个整数 N,表示飞来的导弹个数,N<=100000
第二行为 N 个整数,依次表示导弹飞来的高度,高度数据为不大于 3000000 的正整数。
输出数据:
第一行,输出计算一套系统最多能拦截多少导弹
第二行,输出要拦截所有导弹最少要配备多少套这种导弹拦截系统。

容易看出,第一问求的是这个序列的最长不上升子序列的长度。这个问题有一个N^2时间规模的DP算法,用于10^5的数据是显然超时的。本人就不讲解这个算法了,不了解的读者可以自行搜索。

=================================================================

下面介绍一个时间复杂度为NlogN的,基于贪心和二分查找的算法。(h表示飞来导弹的高度)
引入一个数组S[MAXN],它的长度记作top。S[i]表示长度为i的最长不上升序列的末尾的元素的最大值。容易知道,S是不递增的。
初始化S[1] = h[0],top = 1
从h[1]开始,依次处理每个导弹h[i]。如果h[i] < S[top],那么S[++top] = h[i]。否则用二分查找在S[1]~S[top]中寻找恰好小于h[i]的元素,并把它替换成h[i].
处理完所有h后,top的值即为最长不上升子序列的长度。

为什么可以这么做呢?本人认为有以下几个原因:
任何时刻均有i>=top;
对于一组数据,要获得较长的不上升子序列,则序列末尾的元素要尽量大。
把S中恰好大于h[i]的元素替换后,会给替换位置后的元素更大的上升空间,可能创造更长的序列。

一个问题:能否通过S和h两个数组,重构最长不上升序列呢?请读者思考。

=================================================================

题目的第二个问题是需要几套系统可以拦截所有导弹。对于这个问题,有一个贪心的解法。
用S[i]表示第i个系统目前的高度,初始化所有S[i]为LONG_MAX。
从h[0]~h[N-1],对每个h[i],都在S中找出恰好>=h[i]的S[k],令S[k] = h[i]。
最后,统计S中小于LONG_MAX的值的个数cnt即为答案。

可以发现,对任意t,S[t]的值是只减不增的,并且S是具有单调性的,因此可以用二分优化查找。总的复杂度也是NlogN.

//nlogn的类LIS,贪心
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100005

long h[MAXN];
long S[MAXN];
long N;

void init()
{
   scanf("%ld\n",&N);
   long i;
   for(i = 0;i < N;i ++)
       scanf("%ld\n",h + i);
}

void solve_1()
{
   long i,top,l,r,mid;
   S[1] = h[0];
   top = 1;
   for(i = 1;i < N;i ++)
   {
       if(h[i] <= S[top])
           S[++top] = h[i];
       else
       {
           l = 1;r = top;
           while(l < r)
           {
               mid = (l + r) / 2;
               if(S[mid] < h[i])
                   r = mid;
               else
                   l = mid + 1;
           }
           S[l] = h[i];
       }
   }
   printf("%ld\n",top);
}

long find(long *v,long l,long r,long ele)   //二分查找
{
   long mid;
   while(l < r)
   {
       mid = (l + r) / 2;
       if(v[mid] < ele)
           l = mid + 1;
       else
           r = mid;
   }
   return l;
}

void solve_2()   //贪心地安排导弹,每次都使用恰好大于h[i]的导弹
{
   long i,x;
   static long v[MAXN];
   for(i = 1;i <= N;i ++)
       v[i] = 100000000;
   for(i = 0;i < N;i ++)
   {
       x = find(v,1,N,h[i]);
       v[x] = h[i];
   }
   for(i = 1;i <= N;i ++)
       if(v[i] == 100000000)    break;
   printf("%ld\n",i - 1);
}

int main()
{
   freopen("missile.in","r",stdin);
   freopen("missile.out","w",stdout);
   init();
   solve_1();
   solve_2();
   return 0;
}

Friday, October 19, 2012

压缩字符串题解

输入一个仅由大写字母组成的字符串(长度不超过100),可以用如下规则压缩:

  1. 如果遇到连续的重复字串,可以只保留一个,在其两边用"n(",")"标记,n表示重复的次数。
  2. 括号的使用可以嵌套。

使用以上规则,尽可能压缩字符串(即使压缩后的串尽量短),输出压缩结果。

比如:
AAAAAAAAA           ->    9(A)
AAAAAABBBBBB    ->     6(A)6(B)
AA                          ->     AA
ICICICICICI              ->     4(IC)I
AAAAABBBBBAAAAABBBBB   ->     2(5(A)5(B))

这是一题的最优子结构性质非常明显,是典型的区间动态规划题。
用f[i][j]表示i~j这个字符串最小的长度。
显然,
f[i][j] = min{j - i + 1,f[i][k] + f[k + 1][j],compress(f[i][j])}
i<=k由于需要输出字符,因此增加一个s[i][j][MAXLEN]记录str[i]~str[j]压缩后的情况。

s[0][len - 1]就是最终结果。

需要注意,动态规划的特性决定了它会对所有可能的情况作出转移并选择最优的。因此在写动规方程的时候要注意避免没有必要的转移(或者重复的转移)。


?
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 101
char str[MAXLEN];
int len;
char s[MAXLEN][MAXLEN][MAXLEN] = {};
int f[MAXLEN][MAXLEN];
int numlen(int x)
{
    if(x >= 100)   return 3;
    if(x >= 10)    return 2;
    return 1;
}
void output()
{
    int i;
    for(i = 0;i < f[0][len - 1];i ++)
        printf("%c",s[0][len - 1][i]);
    printf("\n");
}
int find(int b,int l,int e)
{
    int i,r = 1;
    for(i = b + l;i <= e - l + 1;i += l)
    {
        if(strncmp(str + b,str + i,l) != 0)   return 0;
        r ++;
    }
    return r;
}
void solve()
{
    int l,j,k,i,seg;
    int r,newlen;
    char tmp[MAXLEN];
    for(i = 0;i < len;i ++)
        for(j = i;j < len;j ++)
        {
            f[i][j] = j - i + 1;
            memcpy(s[i][j],str + i,j - i + 1);
        }
    for(l = 2;l <= len;l ++)
        for(i = 0;i < len;i ++)
        {
            j = l + i - 1;
            if(j >= len)   break;
            for(seg = 1;seg < l;seg ++)
                if(l % seg == 0)
                {
                    r = find(i,seg,j);
                    if(r == 0)    continue;
                    newlen = numlen(r) + 2 + f[i][i + seg - 1];   //寻找重复串
                    if(newlen < f[i][j])
                    {
                        f[i][j] = newlen;
                        sprintf(s[i][j],"%d(",r);
                        strcat(s[i][j],s[i][i + seg - 1]);
                        strcat(s[i][j],")");
                    }
                }
            for(k = i;k < j;k ++)
            {
                if(f[i][k] + f[k + 1][j] < f[i][j])
                {
                    f[i][j] = f[i][k] + f[k + 1][j];
                    strcpy(s[i][j],s[i][k]);
                    strcat(s[i][j],s[k+1][j]);
                }
            }
            //fprintf(stderr,"(%d,%d):%s\n",i,j,s[i][j]);
        }
}
int main()
{
    freopen("cipher.out","w",stdout);
    freopen("cipher.in","r",stdin);
    scanf("%s\n",str);
    len = strlen(str);
    solve();
    output();
    fclose(stdout);
    return 0;
}

Wednesday, October 17, 2012

甲虫喝水题解

题目来源:NOI导刊,NOIP模拟试题八
题目描述:有一只甲虫位于x轴的原点,在任何时刻,它可以选择左右两个方向移动,并且移动一个单位长度需要耗时1s。x轴上的N个点上有露珠。起始时刻,每个露珠的含水量都是正整数M,每经过1s,每个露珠的含水量减少1单位。当甲虫遇到露珠时,它可以在瞬间喝光露珠的水。
输入N,M和每个露珠的位置(露珠位置为整数),输出甲虫能喝到的最多的水量。

比如:N=3 M=15 露珠位置分别为6、-3、1时,甲虫可以依次喝1、-3、6处的露水,获得最大水量25

可以明确一下几点:
  1. 甲虫只会在有露珠的位置掉转方向。
  2. 一旦遇到露珠,甲虫一定会喝掉。
  3. 每个时刻所有未喝掉的露珠水量都会均匀减少。
故甲虫喝掉的水一定是一个连续的区间。

因此,这个题目就是一道区间动规题。
首先,先对露珠的位置排序。
用fi[i][j][k]表示一共要吃掉k颗露水,目前吃光了i到j之间的露水并停留在i端的情况。fj[i][j][k]表示停留在j端的情况。增加k这一维,预先扣除剩余(k-i+j)颗露水的减少量,就可以解决露珠水量减少的问题。

具体的转移方程可以参考下面的代码。数组中k这一维可以压缩掉。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 303

long x[MAXN];
long N,M;
long ans;
long fi[MAXN][MAXN];
long fj[MAXN][MAXN];

int cmp(const void *a,const void *b)
{
   if(*(long *)a > *(long *)b)    return 1;
   return -1;
}

void init()
{
   scanf("%ld%ld",&N,&M);
   long i;
   for(i = 0;i < N;i ++)
       scanf("%ld",&x[i]);
   qsort(x,N,sizeof(long),cmp);
}

inline long getmax(long a,long b)
{
   if(a > b)    return a;
   return b;
}

void solve()
{
   ans = 0;
   int i,j,k,l;
   for(k = 1;k <= N;k ++)
   {
       for(i = 0;i < N;i ++)
       {
           fi[i][i] = fj[i][i] = M - labs(x[i]) * k;
           ans = getmax(ans,fi[i][i]);
       }
       for(l = 2;l <= k;l ++)
           for(i = 0;i <= N - l;i ++)
           {
               j = i + l - 1;
               fi[i][j] = M + getmax(fi[i + 1][j] - (x[i + 1] - x[i]) * (k - j + i),fj[i + 1][j] - (x[j] - x[i]) * (k - j + i));
               fj[i][j] = M + getmax(fi[i][j - 1] - (x[j] - x[i]) * (k - j + i),fj[i][j - 1] - (x[j] - x[j - 1]) * (k - j + i));
               ans = getmax(fi[i][j],ans);
               ans = getmax(fj[i][j],ans);
           }
   }
   printf("%ld\n",ans);
}

int main()
{
   freopen("beetle.in","r",stdin);
   freopen("beetle.out","w",stdout);
   init();
   solve();
   return 0;
}

一个有关最小生成树的问题

题目来源:NOI导刊,NOIP模拟试题九

题目描述:输入一个联通的无向图,对于每条边,判断这条边是属于这张图的任意一个MST、至少一个MST还是不属于任何一个MST。对应输出"any","at least one","none"。

这个问题看上去有些复杂,不过,可以确定这一点:无向图中的桥一定在每个MST中。

接着,让我们从Kruskal算法的角度分析一下。Kruskal先把边按照边权递增排序,使用并查集记录每个点属于的联通分量,如果扫描到一条边的两个点不属于同一个联通分量,那么就把这条边加入MST中,并合并两个顶点所在的联通分量。

可见,对于同一个无向图,Kruskal给出的MST的结果很大程度上取决于排序的结果,如果使用稳定的排序算法对边表排序,那么Kruskal输出的结果是唯一的。如果使用随机化快排,当存在权值相等的边时,Kruskal给出的MST就不是一成不变的了。

我们就从这里下手。

新建一张空图G。在边表中找出所有边权为w的边,保存在list中,用Kruskal合并所有边权小于w的安全边。然后,依次扫描list中的所有边(i,j),如果i和j在同一个联通分量中,那么,显然这条边一定不属于任何一MST。否则,这条边就属于某个MST,并把这条边(两端点要改成原端点所属的联通分量)加入G中。

接着,用Tarjan算法求出G中所有的桥,这些桥必然存在任意一个MST。

按照上面的方法对所有w都运行一遍,就可以获得结果了。

代码实现:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 100005
#define MAXE 100005

typedef struct node
{
   long v,ord;
   struct node *next;
}node;

typedef struct edge
{
   long u,v,w,ord;
}edge;

long N,M;
edge e[MAXE];

node *first[MAXN];
node space[MAXE * 3];
long empty;

long fa[MAXN];   //disjoint set
long dfsn[MAXN],low[MAXN];
long T;   //DFS time
int type[MAXE];

int ecmp(const void *a,const void *b)
{
   if(((edge *)a)->w > ((edge *)b)->w)    return 1;
   return -1;
}

inline void init_fa()
{
   long i;
   for(i = 1;i <= N;i ++)
       fa[i] = i;
}

long getfa(long x)
{
   if(fa[x] != x)
       fa[x] = getfa(fa[x]);
   return fa[x];
}

inline long getmin(long a,long b)
{
   if(a < b)    return a;
   return b;
}

void init()
{
   long i;
   scanf("%ld%ld",&N,&M);
   for(i = 0;i < M;i ++)
   {
       scanf("%ld%ld%ld",&e[i].u,&e[i].v,&e[i].w);
       e[i].ord = i;
   }
}

inline void addedge(long a,long b,long ord)
{
   space[empty].next = first[a];
   space[empty].v = b;
   space[empty].ord = ord;
   first[a] = space + empty;
   empty ++;
}

void tarjan(long x,long f)   //find bridges
{
   node *p;
   T ++;
   dfsn[x] = low[x] = T;
   for(p = first[x];p != NULL;p = p->next)
       if(p->ord != f)
       {
           if(dfsn[p->v] == 0)   //not visited yet
           {
               tarjan(p->v,p->ord);
               low[x] = getmin(low[x],low[p->v]);
               if(dfsn[x] < low[p->v])
                   type[p->ord] = 2;
           }
           else
               low[x] = getmin(low[x],dfsn[p->v]);
       }
}

void solve()
{
   long i,j,k,a,b;
   long addcnt = 0;
   qsort(e,M,sizeof(edge),ecmp);
   init_fa();
   for(i = 0;i < M && addcnt < N - 1;)
   {
       for(j = i;e[j].w == e[i].w;j ++);
       //e[i to j].w are the same
       for(k = i;k < j;k ++)
       {
           a = getfa(e[k].u);
           b = getfa(e[k].v);
           if(a != b)    //it's a safe edge
           {
               type[e[k].ord] = 1;   //in at least one MST
               first[a] = first[b] = NULL;   //make space for new graph
               dfsn[a] = dfsn[b] = low[a] = low[b] = 0;  //init for tarjan
           }
       }
       T = empty = 0;
       for(k = i;k < j;k ++)   //build new graph for tarjan to find bridges
       {
           if(type[e[k].ord] == 0)    continue;
           a = getfa(e[k].v);
           b = getfa(e[k].u);
           addedge(a,b,e[k].ord);
           addedge(b,a,e[k].ord);
       }
       for(k = i;k < j;k ++)
           if(dfsn[getfa(e[k].u)] == 0)  //not visited yet
               tarjan(getfa(e[k].u),-1);
       for(k = i;k < j;k ++)   //kruskal merge
       {
           a = getfa(e[k].u);
           b = getfa(e[k].v);
           if(a != b)
           {
               fa[a] = b;
               addcnt ++;
           }
       }
       i = j;
   }
}

void output()
{
   long i;
   for(i = 0;i < M;i ++)
   {
       switch(type[i])
       {
           case 1:printf("at least one\n");break;
           case 0:printf("none\n");break;
           case 2:printf("any\n");
       }
   }
}

int main()
{
   freopen("mst.in","r",stdin);
   freopen("mst.out","w",stdout);
   init();
   solve();
   output();
   fclose(stdout);
   return 0;
}

实际代码为了提高效率,重复利用了结果,并没有完全按照前面的方法设计程序。
起初本人图方便,建空图时直接memset整个first数组,导致最后三个数据超时,改成first[a] = first[b] = NULL就全部通过了。可见虽然memset速度很快,但如果只要重置某几个数值,还是直接赋值更好。