Olympiad in Informatics

首先考虑所有n>k的部分：k mod n=k，答案直接+k*(n-k)。

接下来考虑n属于区间[1,ceil(sqrt(k))]的情况。因为sqrt(k)只有5位数而已，可以按照题目要求朴素算一遍。

最后考虑n属于区间[ceil(sqrt(k)),k]的情况：因为k mod n=k-k div n*n，此时k div n最大为ceil(sqrt(k))，最小为1。如果我们知道某个k div n=a，那么我们就可以求出n的取值范围（因为n在这个范围内都满足k div n=a）：[k/n]=a等价于k>=an && k<(a+1)n。换句话来说k/(a+1) < n <= k/a。

得到n的取值区间[L,R]后，这部分k mod n的和就是Σ[i=L->R,(k-ai)]。

我们枚举所有的a，并累加各个部分的余数和，这就是答案。总的复杂度为O(sqrt(k))。 Read on →
Olympiad in Informatics

这题的n有点大，1000000的数据规模只能考虑O(n)解决（貌似跟O(nlogn)的算法扯不上关系）。

先假定1为根，这样能把这个有根图转成一棵以1为根的树。再用f[i],son[i]表示在这棵树中，以i为根节点下面最大的深度之和（深度是相对于整棵树，而不是i来说的），以及i节点下有多少个子节点（包括自己）。可以使用一个简单的广搜确定父节点后，用一个简单的动规累加，完成这步需要O(2n)的时间。

之后我们考虑换根。对于根从当前根节点的fa换到它的某个最近孩子u上的情况：u和它的所有孩子的深度都会-1，u另外一边的节点的深度都会+1，因此换完根之后的深度和就是f[fa]-son[u]+(n-son[u])。将根从1到n枚举一遍，看看哪个情况的深度之和最大，输出即可。

总复杂度O(n)。 Read on →
Olympiad in Informatics

显然如果n个矩形的高度如果都不相同，那么一定要n张海报才能覆盖。出现更优解的当且仅当出现了高度相同的矩形。可以考虑从左边第一个矩形开始，覆盖所有不比它矮的矩形部分，剩下的依次。如果这个矩形已经被完全覆盖了（也就是有一个可达该矩形，并且高度和相同的矩形），那么海报数量不用+1，否则都得+1。

考虑用单调栈维护，从栈底到栈顶单调递增。每次一个矩形的高度x进栈的时候，先维护单调栈的性质，如果发现维护后的栈顶和当前一样高，则不用多一张海报，否则入栈、海报+1。 Read on →
Olympiad in Informatics

这题是TSP的简化版：只能从左边单向走向右边，再从右边单项走回来源点，满足路径是一条哈密顿回路。

对于走两遍的要求，可以当作是两个人从左边选择两条不会有公共点的路径，单向走向右边。也就是双路DP。

一开始我的想法是f[i,j]表示A走到了i，B走到了j，那么转移的时候要么从f[i-1,j]要么从f[i,j-1]转移，为了不使两条路径相交，可以规定i>j，计算出f[i,j]后，f[j,i]=f[i,j]，方程十分简单。但是有一个问题，如果j=i-1呢？那么f[i-1,j]=f[i,i]显然就出事了！

因此要对j=i-1的情况特殊处理：寻找某个k(ki) Read on →
Olympiad in Informatics

据说这题是十分经典的动态规划，题目的意思就是求一种消除方块的方法，使得得分最高。

看到这题有种用区间动归的冲动，用f[l,r]记录从l个方块合并到r的最高得分。不过这题消除方块有个限制条件，就是一次必须消除连续的相同颜色的方块，直接操作容易违背这个条件，因此考虑要把方块缩点：用(color[i],len[i])记录有len[i]个color[i]色的方块。这样f[l,r]就表示从第l组色块到第r组色块合并的最有值。

不过有个问题，考虑如下序列：0001111000，把1111拿走后，前后的000 000合并时必须一次完成。但实际上，在程序中根本无法知道1111被拿走了（或者说，如果知道了1111被拿走了，那么要手动合并000 000，也就是要更改(color[i],len[i])，这样会破坏整个数据结构，有有后效性）。

不能在(color[i],len[i])上作修改，那就只能对动归的状态进行修改了：用f[i,j,k]表示合并色块[i,j]，连同色块j之后k个与j同色的方块得到的最高得分。

实际上这个表示方法不需要考虑色块j之后的色块是否合并、颜色是否相同，只需要考虑色块j后有k个和它颜色相同的方块。因为我们可以假设j之后的、夹在色块j和后面的和j同色的方块之间的色块已经被消除。因此就有如下的转移方法：
  1. 如果色块j连同后面的k个方块一起合并掉，那么f[i,j,k]=f[i,j-1]+(len[j]+k)2。
  2. 如果色块j被前面的合并掉了（也就是被前面的某个j’当作是k个方块之一），那么就要找到前面的所有和j一样颜色的x，先把[i,x]连同j合并了，然后再把x和j中间的方块处理掉，f[i,j,k]=min{f[i,x,len[x]+k]+f[x+1,j-1,0]}

答案就是f[1,n,0]。直接写DP可能不好写，因此可以考虑记忆化搜索。 Read on →

Olympiad in Informatics

这题其实是动规+状态压缩。

最基本的压缩想法是：二进制压缩，若第i个地方放了大炮，那么该位就为1。

题目中的列数m很少，m<=10，可以在不考虑地形的情况下计算出一行的所有可能情况，也就是一行的标准情况。那么其余行的状态必定为这些标准状态之一。这些标准状态可以用O(2^m)的时间枚举出来，经实践证明，当m=10时标准状态只有60种，这样一来，每行的状态数不超过60种。

另外一方面，因为一个炮兵会影响到它下面的两行，因此我们在转移的时候需要记下当前行和上一行的状态。用f[i,j,k]表示第i行的状态为标准状态j，第i-1行的状态为标准状态k，那么f[i,j,k]=max{f[i-1,k,u]}+o[j] （其中o[j]表示标准状态j中有多少个炮兵）

最后的答案就是max{f[n,j,k]}

因为这题用到了许多的位运算小技巧，所以在这里顺便提下（其实这些小技巧可以直接看程序）： Read on →
Olympiad in Informatics

少说多做- -||

1.能量项链

典型的合并类动规。对于一条链来说，f[i,j]表示合并i到j的最大能量，易得f[i,j]=max{f[i,k]+f[k+1,j]+a[i]a[k+1]a[j+1]}，复杂度O(n3)。由于项链是一个环，要拆成链，有一个办法就是做n次，每次都把项链移动一位。但是这样复杂度就变成了O(n4)，对于n<=100难以承受。

由于有许多的公共部分，可以考虑拆成2n个点，动规时合并区间[1,n],[2,n+1]…[n,2n-1]，最后从这几个区间中选出一个最大的作为答案。公共部分没有被重复计算，因此效率大大提高，整体的复杂度仍然保持在O(n^3)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var tmp,n,i,j,k,len:longint;
    a:array[0..200]of longint;
    f:array[0..200,0..200]of longint;
begin
  fillchar(f,sizeof(f),193);
  readln(n);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do a[n+i]:=a[i];
  for i:=1 to 2*n-1 do f[i,i]:=0;

  for len:=1 to n-1 do
    for i:=1 to n*2-1-len do begin
      j:=i+len;
      for k:=i to j-1 do begin
        tmp:=f[i,k]+f[k+1,j]+a[i]*a[k+1]*a[j+1];
        if tmp>f[i,j] then f[i,j]:=tmp;
      end;
    end;
  tmp:=0;
  for i:=0 to n-1 do
    if f[i+1,i+n]>tmp then tmp:=f[i+1,i+n];
  writeln(tmp);
end.

2.金明的预算方案

经典的01背包。因为有附件，并且一个主件最多只有2个附件，且附件没有附件，因此转移的方法只有如下四种：1.只买主件；2.买主件和附件1；3.买主件和附件2；4.买主件和两个附件。带入01背包DP方程f[j]=max{f[j-a[i]]+b[i]}，轻松解决。

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

{$inline on}
var n,m,i,j:longint;
    a:array[0..60,1..2]of longint;
    f:array[0..32000]of longint;
    q,v,w,count:array[0..60]of longint;
procedure up(var tmp:longint;i,need,j,w:longint);inline;
  begin
    if (count[i]>=need)and(j>=0)and(tmp<f[j]+w) then tmp:=f[j]+w;
  end;
begin
  readln(n,m);
  for i:=1 to m do begin
    readln(v[i],w[i],q[i]);
    if q[i]<>0 then begin
      inc(count[q[i]]);
      a[q[i],count[q[i]]]:=i;
    end;
  end;
  for i:=1 to m do if q[i]=0 then
    for j:=n downto 0 do begin
      up(f[j],i,0,j-v[i],v[i]*w[i]);
      up(f[j],i,1,j-v[i]-v[a[i,1]],v[i]*w[i]+v[a[i,1]]*w[a[i,1]]);
      up(f[j],i,2,j-v[i]-v[a[i,2]],v[i]*w[i]+v[a[i,2]]*w[a[i,2]]);
      up(f[j],i,2,j-v[i]-v[a[i,1]]-v[a[i,2]],v[i]*w[i]+v[a[i,1]]*w[a[i,1]]+v[a[i,2]]*w[a[i,2]]);
    end;
  writeln(f[n]);
end.
Read on →
Olympiad in Informatics

少说多做- -||

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

var count,i,j,k,n:longint;
    s:string;
    a:array[0..100]of record name:string[20];no,finalScore,classScore,article,money:longint;staff,western:char; end;
begin
  assign(input,'scholar.in');reset(input);
  assign(output,'scholar.out');rewrite(output);

  readln(n);
  for i:=1 to n do with a[i] do begin
    no:=i;
    readln(s);
    k:=pos(' ',s);
    name:=copy(s,1,k-1);
    delete(s,1,k);
    k:=pos(' ',s);
    val(copy(s,1,k-1),finalScore);
    delete(s,1,k);
    k:=pos(' ',s);
    val(copy(s,1,k-1),classScore);
    staff:=s[k+1];
    western:=s[k+3];
    delete(s,1,k+4);
    val(s,article);

    if (finalScore>80)and(article>=1) then inc(money,8000);
    if (finalScore>85)and(classScore>80) then inc(money,4000);
    if (finalScore>90) then inc(money,2000);
    if (finalScore>85)and(western='Y') then inc(money,1000);
    if (classScore>80)and(staff='Y') then inc(money,850);
    inc(count,money);
  end;
  for i:=1 to n-1 do
    for j:=i+1 to n do if a[i].money      a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
    end;
  k:=1;
  for i:=2 to n do if (a[i].money=a[1].money)and(a[i].no  writeln(a[k].name);
  writeln(a[1].money);
  writeln(count);

  close(input);close(output);
end.

2.过河

可以考虑动归。f[i]表示跳到第i个位置需要踩到多少石子，f[i]=min{f[k]}+rock[i]  (s<=k<=t，当i处有石子的时候rock[i]=1，否则为0)。显然L<=10^9，O(n)会时间空间双爆，考虑压缩。

因为石子数量比较少<=100，所以中间一定会产生许多的空长条，如果我们能够压缩这些空长条，那么总的长度就会小得多了。可以证明，如果相邻两个石头的距离Q>=s*(s+1)，那么一定可以使用s,s+1两种步长跳过。可以参考noip2005 过河 解题报告 @ N_C_Derek

因此，对于所有相邻的两个石头距离b[i]-b[i-1]>=s(s+1)，则从第i个点开始，后面的每个点都向左移动b[i]-b[i-1]-s(s+1)个单位。这样一来，L被压缩到10010，m<=100，对于O(m^2)的预处理和O(n)的DP毫无压力。

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

var ans,l,i,j,s,t,n,tmp,p,k:longint;
    a:array[0..101]of longint;
    f:array[0..10010]of longint;
begin
  assign(input,'river.in');reset(input);
  assign(output,'river.out');rewrite(output);

  readln(l);
  readln(s,t,n);
  for i:=1 to n do read(a[i]);
  inc(n);a[n]:=l;
  for i:=1 to n-1 do
    for j:=i+1 to n do if a[i]>a[j] then begin
      tmp:=a[i];a[i]:=a[j];a[j]:=tmp;
    end;
  if s=t then begin
    ans:=0;
    for i:=1 to n-1 do if a[i] mod s=0 then inc(ans);
  end else begin
    p:=s*(s+1);
    for i:=1 to n do begin
      if a[i]-a[i-1]>=p then begin
        k:=a[i]-a[i-1]-p;
        for j:=i to n do dec(a[j],k);
      end;
      f[a[i]]:=1;
    end;
    f[a[n]]:=0;

    for i:=1 to a[n]+t-1 do begin
      k:=maxlongint;
      for j:=s to t do if (i-j>=0)and(k>f[i-j]) then k:=f[i-j];
      if k=maxlongint then f[i]:=maxlongint else inc(f[i],k);
    end;

    ans:=maxlongint;
    for i:=a[n] to a[n]+t-1 do if f[i]  end;
  writeln(ans);

  close(input);close(output);
end.
Read on →
Olympiad in Informatics

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。——百度百科

求出数组中任意区间[l,r]的最值，朴素的算法需要O(n)的时间。当询问特别多时，效率十分低。 st算法可以在O(nlogn)的时间内做完预处理，然后用O(1)的时间回答每一个问题。具体实现方法如下：（其实是一个动规^_^） 以求最大值为例。 用f[i,j]表示区间[i,i+2j-1]中的最大值。那么： f[i,j]=max(F[i,j-1],F[i+2j-1,j-1]) 预处理完后，对于询问求[a,b]的最大值。我们首先需要求出一个最大的整数x满足2x <=r-l+1那么，答案就是max(f[a,x],f[b+1-2x,x])。

由于pascal中，log2函数在math库中，使用还需uses math; 而ln则不需要使用任何的库，所以可以考虑换底公式： log a(b)=log c(b)/log c(a) 也就是log2(a)=ln(a)/ln(2)

例题如：Balanced Lineup,USACO 2007 January Silver（即PKU3264）。求区间的最大值-最小值。程序如下： Read on →

Olympiad in Informatics

少说多做- -||

1.统计数字

nlogn排序+n统计，水过 
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

var i,n,count:longint;
    a:array[1..200000]of longint;
procedure qsort(l,r:longint);
  var i,j,x,t:longint;
  begin
    i:=l;j:=r;x:=a[(l+r)shr 1];
    repeat
      while a[i]<x do inc(i);
      while a[j]>x do dec(j);
      if i<=j then begin
        t:=a[i];a[i]:=a[j];a[j]:=t;
        inc(i);dec(j);
      end;
    until i>=j;
    if i<r then qsort(i,r);
    if l<j then qsort(l,j);
  end;
begin
  readln(n);
  for i:=1 to n do readln(a[i]);
  qsort(1,n);
  count:=1;
  for i:=2 to n do if a[i]<>a[i-1] then begin
    writeln(a[i-1],' ',count);
    count:=1;
  end else inc(count);
  writeln(a[n],' ',count);
end.

2.字符串的展开

模拟题，没什么好说的，跟着题目做就是了。不一定越长的代码一次AC的几率越高，简短一点的说不定更容易一次AC，比如我这次就一次AC了。初中的时候每次做都交了n次才过。 
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

var q1,q2,q3,k,i,j,last:longint;
    c:char;
    s:string;
begin
  assign(input,'expand.in');reset(input);
  assign(output,'expand.out');rewrite(output);

  readln(q1,q2,q3);
  readln(s);
  s:=s+' ';
  last:=0;

  while last<>length(s) do begin
    k:=pos('-',s);
    for i:=last+1 to k-1 do write(s[i]);
    if (k>1)and((s[k-1]in['a'..'z'])and(s[k+1]in['a'..'z']) or (s[k-1]in['0'..'9'])and(s[k+1]in['0'..'9'])and(s[k-1]<s[k+1]) then begin
      if p3=1 then
        for c:=succ(s[k-1]) to pred(s[k+1]) do writech(p3)
      else
        for c:=pred(s[k+1]) to succ(s[k-1]) do writech(p3);
    end else begin
      write(s[k],s[k+1]);
      last:=k+1;
    end;
  end;

  close(input);close(output);
end.
Read on →