1 0pts

2 10pts

3 100pts

本想装个逼，从后面开始做，确实t3第一个AC，获得了紫色high light,BUT，第二题自己造的极端数据都过了，结果上讲台看，0分！！怎么可能？！检查了一下精度问题，没毛病啊，在最后两分钟发现我把题读错了……我以为必须要是升序的数列……被坑惨了，两分钟改了一下，得了10pts呵呵.t1没时间调了，死循环

t1迷宫

注意用dp做啊！dfs会爆，bfs懒得写……

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=30;
int mapp[N][N];
int f[N*N][N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n,ex,ey,sx,sy;

void readdata()
{
    char c;
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%c",&c);
            if(c!='X')mapp[i][j]=1;
            if(c=='X')mapp[i][j]=0;
            if(c=='S'){sx=i;sy=j;}
            if(c=='E'){ex=i;ey=j;}
        }
        scanf("\n");
    }
}

void work()
{
    f[0][sx][sy]=1;
    rep(t,1,n*n)
        rep(i,1,n)
            rep(j,1,n)
                if(mapp[i][j])
                {
                    for(int k=0;k<4;k++)
                    {
                        int nx=i+dx[k],ny=j+dy[k];
                        if(mapp[nx][ny] && nx>=1 && ny>=1 && nx<=n && ny<=n)
                        {
                            f[t][i][j]=f[t][i][j]+f[t-1][nx][ny];
                        }
                    }
                }

    rep(t,1,n*n)
        if(f[t][ex][ey])
        {
            printf("%d\n%d",t,f[t][ex][ey]);
            break;
        }
}

int main()
{
    readdata();
    work();
    return 0;
}

# t2 最大数列

前缀和这波操作是真的不懂……（这是wolf gang的代码）

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define inf 0x3f3f3f3f

int n,a[N],f[N],h[N],t[N];

int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int main()
{
    n=read();

    t[n+1]=h[0]=0;

    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        h[i]=h[i-1]+a[i];//前缀
    }

    for(int i=n;i>0;i--)
        t[i]=t[i+1]+a[i];//后缀

    int mi=0;f[0]=-inf;

    for(int i=1;i<=n;i++)//求左区间
    {
        f[i]=h[i]-mi;
        f[i]=max(f[i],f[i-1]);
        mi=min(mi,h[i]);
    }
    int ma=-inf,ans=-inf;mi=0;

    for(int i=n;i>=2;i--)
    {
        ma=max(ma,t[i]-mi);
        ans=max(ans,ma+f[i-1]);//加答案
        mi=min(t[i],mi);
    }
    printf("%d",ans);
    return 0;
}

T3 安装服务器

1.感觉这题比前两题简单啊

2.刘汝佳，蓝书，第六页，，有一个棒棒的证明

3.算法：带权中位数（模版提难度吧）

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 100010
using namespace std;

int T,quan,xx,yy,cnt=0;

int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

struct city{
    int x,y,v; //v:k*p
}C[N];

bool cmpx(city a,city b){return a.x<b.x;}
bool cmpy(city a,city b){return a.y<b.y;}

int main()
{
    //freopen("read.txt","r",stdin);
    T=read();

    rep(i,1,T)
    {
        int x,y,p,k;
        x=read(),y=read(),k=read(),p=read();
        C[i]=(city){x,y,k*p};
        quan+=k*p;
    }


    sort(C+1,C+T+1,cmpx);
    quan=(quan+1)>>1;

    rep(i,1,T)
    {
        cnt+=C[i].v;

        if(cnt>=quan)
        {
            xx=C[i].x;
            break;
        }
    }

    sort(C+1,C+T+1,cmpy);

    cnt=0;
    rep(i,1,T)
    {
        cnt+=C[i].v;

        if(cnt>=quan)
        {
            yy=C[i].y;
            break;
        }
    }

    printf("%d %d",xx,yy);
    return 0;
}