2017 济南综合班 Day 4

T1 外星人

二维前缀和

#include<cstdio>

#define N 1001

using namespace std;

bool v[N][N];

int sum[N][N];

int main()

{

    freopen("alien.in","r",stdin);

    freopen("alien.out","w",stdout);

    int r,c,p,q;

    scanf("%d%d%d%d",&r,&c,&p,&q);

    int x,y;

    for(int i=;i<=p;i++)

    {

        scanf("%d%d",&x,&y);

        v[x][y]=true;

    }

    for(int i=;i<=r;i++)

     for(int j=;j<=c;j++)

      sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+v[i][j];

    int ans=;

    while(q--)

    {

        scanf("%d%d",&x,&y);

        for(int i=;i<=r;i++)

         for(int j=;j<=c;j++)

         {

             if(i-x>= && j-y>= && sum[i][j]-sum[i-x][j]-sum[i][j-y]+sum[i-x][j-y]==) ans++;

             if(x==y) continue;

             if(i-y>= && j-x>= && sum[i][j]-sum[i-y][j]-sum[i][j-x]+sum[i-y][j-x]==) ans++;

         }

        printf("%d\n",ans);   ans=;

    }

}

T2 游戏

点权*2

边权分别加到两个点上

排序、贪心、两人轮流选当前最大

点权乘了2，边权是自己的乘了2，不是自己的减了去

最后除2就是答案

#include<cstdio>

#include<algorithm>

#include<iostream>

#define N 10001

using namespace std;

int a[N];

int main()

{

    freopen("game.in","r",stdin);

    freopen("game.out","w",stdout);

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%d",&a[i]),a[i]<<=;

    int u,v,w;

    while(m--)

    {

        scanf("%d%d%d",&u,&v,&w);

        a[u]+=w; a[v]+=w;

    }

    sort(a+,a+n+,greater<int>());

    int ans=;

    for(int i=;i<=n;i+=)

    {

        ans+=a[i];

        ans-=a[i+];

    }

    printf("%d",ans>>);

}

T3 堡垒

当时改了最后一行的输出，忘了改成啥了

所以就忽略最后一行输出吧

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

char move;

int m,n,xx,yy;

int sum,tmp,maxn,big;

int E[][][][],N[][][][];

bool v[][];

void dfs(int x,int y)

{

    v[x][y]=true;  tmp++;

    if(x!= && !N[x][y][x-][y] && !v[x-][y]) dfs(x-,y);

    if(y!=m && !E[x][y][x][y+] && !v[x][y+]) dfs(x,y+);

    if(x!=n && !N[x+][y][x][y] && !v[x+][y]) dfs(x+,y);

    if(y!= && !E[x][y-][x][y] && !v[x][y-]) dfs(x,y-);

}

int main()

{

    freopen("fortress.in","r",stdin);

    freopen("fortress.out","w",stdout);

    int x;

    scanf("%d%d",&m,&n);

    for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      {

           scanf("%d",&x);

           if(x&(<<))

            N[i][j][i-][j]=true;

           if(x&(<<))

            E[i][j][i][j+]=true;

      }

    for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      if(!v[i][j])

      {

           sum++; tmp=;

         dfs(i,j);

         maxn=max(maxn,tmp);

      }

    printf("%d\n%d\n",sum,maxn);

    for(int i=n;i>=;i--)

     for(int j=;j<=m;j++)

     {

         if(i!= && N[i][j][i-][j])

         {

             memset(v,,sizeof(v));

            N[i][j][i-][j]=false;

             tmp=;

             dfs(i,j);

             if(tmp>maxn) maxn=tmp,xx=i,yy=j,move='N';

             N[i][j][i-][j]=true;

        }

        if(j!=m && E[i][j][i][j+])

        {

            memset(v,,sizeof(v));

            E[i][j][i][j+]=false;

            tmp=;

            dfs(i,j);

            if(tmp>maxn) maxn=tmp,xx=i,yy=j,move='E';

            E[i][j][i][j+]=true;

        }

     }

    printf("%d\n",maxn);

    printf("%d %d %c",xx,yy,move);

}