program fire;
const
        inf = 'fire.in';
        //     fire9.ans
        ouf = 'fire.out';
var
        n:longint;
        t,t0,t1:longint;
        p:array[1..50000,1..2] of longint;
        ne,ne2:array[1..50000] of longint;
        an:array[1..50000] of boolean;
        w:array[0..49999] of longint;
        max:longint;
begin
        assign(input,inf);reset(input);
        assign(output,ouf);rewrite(output);

        readln(n);
        for t:=1 to n do readln(p[t][1],p[t][2]);
        fillchar(an,sizeof(an),0);
        ne[1]:=1;ne2[n]:=1;max:=0;
        an[1]:=true;t0:=p[1][1];
        for t:=2 to n do begin
                if an[t0] then begin
                        writeln(-1);
                        close(input);
                        close(output);
                        halt;
                        end;
                ne[t]:=t0;
                ne2[n-t+1]:=t0;
                an[t0]:=true;
                if an[p[t0][1]] then t0:=p[t0][2] else t0:=p[t0][1];
                end;
        fillchar(w,sizeof(w),0);
        for t:=1 to n do begin
                inc(w[(ne[t] - t + n) mod n]);
                end;
        for t:=0 to n-1 do if max < w[t] then max:=w[t];
        fillchar(w,sizeof(w),0);
        for t:=1 to n do begin
                inc(w[(ne2[t] - t + n) mod n]);
                end;
        for t:=0 to n-1 do if max < w[t] then max:=w[t];

        writeln(n - max);

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



-------------------------------------------------------

program river;
const
        inf = 'river.in';
        //     river.ans
        ouf = 'river.out';
var
        t,t0,t1:longint;
        l,mi,ma:longint;
        m:longint;
        st:array[0..101] of longint;
        v:array[0..101,0..101] of boolean;
        f:array[0..101] of longint;
        subject:longint;
        min:longint;
procedure sort(l,r:longint);
        var
                i,j:longint;
                x,y:longint;
        begin
                i:=l;j:=r;
                x:=st[(l+r) shr 1];
                repeat
                        while st[i] < x do inc(i);
                        while x < st[j] do dec(j);
                        if i<=j then begin
                                y:=st[i];st[i]:=st[j];st[j]:=y;
                                inc(i);dec(j);
                                end;
                        until i>j;
                if l < j then sort(l,j);
                if i < r then sort(i,r);
                end;
function find(i:longint):longint;
        var
                l,r:longint;
        begin
                l:=1;r:=m;
                while l<>r do
                        if st[(l+r-1)shr 1] < i then l:=(l+r+1)shr 1 else r:=(l+r-1)shr 1;
                if st[l] < i then inc(l);
                exit(l);
                end;
procedure search(i,j:longint);
        var
                tt0,tt:longint;
        begin
                if j>=l then begin
                        v[subject][m+1]:=true;
                        //writeln(subject,'->',m+1);
                        j:=l-1;
                        end;
                if i>j then exit;
                tt:=find(i);
                if (tt = m+1)and(v[subject][m+1]) then exit;
                if st[tt] <= j then begin
                        repeat
                                if not v[subject][tt] then begin
                                        //writeln(subject,'->',tt);
                                        v[subject][tt]:=true;
                                        if (tt>0)and(st[tt-1]>i) then
                                                search(st[tt-1]+1,st[tt]-1) else
                                                search(i,st[tt]-1);
                                        end;
                                inc(tt);
                                until (st[tt] > j)or(tt > m);
                        if (tt>0) then search(st[tt-1]+1,j);
                        end else begin
                                repeat
                                        tt0:=(st[tt] - j - 1) div ma + 1;
                                        j:=j +  tt0 * ma;
                                        i:=i +  tt0 * mi;
                                        tt:=find(i);
                                        if i>l then break;
                                        until st[tt]>=i;
                                search(i,j);
                                end;
                end;
begin
        assign(input,inf);reset(input);
        assign(output,ouf);rewrite(output);

        readln(l);
        readln(mi,ma,m);
        for t:=1 to m do read(st[t]);readln;st[m+1]:=l;
        sort(1,m);
        fillchar(v,sizeof(v),0);
        for subject:=m downto 0 do
                search(st[subject] + mi,st[subject] + ma);
        f[m+1]:=-1;
        for t0:=m downto 0 do begin
                min:=200;
                for t:=t0+1 to m+1 do if v[t0][t] then if f[t] < min then min:=f[t];
                f[t0]:=min+1;
                end;
        writeln(f[0]);

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

都是AC了的程序,,, 哎考试的时候一些边界没考虑好 改正了就AC... 闷

谢谢

发重了

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int L,pos[102];
int s,t,m,end;
int n;
int dis;
int a[50000];

int cmp(const void *w1,const void *w2)
{
    if (*(int *)w1-*(int *)w2>0) return 1;
    if (*(int *)w1-*(int *)w2<0) return -1;
    return 0;
}
void work(int i)
{
    int j,k,d,tnum;
    if (pos[i+1]-pos[i]>=dis)
    {
        tnum=10000;
        for (k=1;k<=t;k++)
            if (tnum>a[end-k]) tnum=a[end-k];
        for (j=1;j<t;j++)
            a[end++]=tnum;
        a[end++]=tnum+1;
    }
    else
    {
        d=pos[i+1]-pos[i]-1;
        for (j=0;j<d;j++)
         {
            a[end]=10000;
            for (k=end-t;k<=end-s;k++)
                 if (a[end]>a[k]) a[end]=a[k];
            end++;
        }
        a[end]=10000;
        for (k=end-t;k<=end-s;k++)
             if (a[end]>a[k]+1) a[end]=a[k]+1;
        end++;
    }
}
int main(void)
{
    int i,num;
    freopen("river.in", "r", stdin);
    freopen("river.out", "w", stdout);
    cin >> L;
    cin >> s >> t >> m;
    pos[0]=0;pos[m+1]=L;
    for (i=1;i<=m;i++) cin >> pos[i];

    qsort(pos,m+1,sizeof(int),cmp);
    if (t!=s)
    {
        if ((s-1)%(t-s)==0) n=(t-1)/(t-s);
        else n=(t-1)/(t-s)+1;
        dis=n*t;
        for (end=0;end<t;end++) a[end]=0;
        
        for (i=m;i>=0;i--) work(i);
        cout<<a[end-1]-1;
    }
    else
     {
        num=0;
        for (i=1;i<=m;i++) if (pos[i]%t==0) num++;
        cout<<num;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

river 的

貌似不是最好的答案
river那道用挪威斯倒叙算法
fire算公式吧
都不难