20181015队内ACM赛 Part.1

发表于 by TaK-Vin in C++、笔记、线段树、递推、队测、题解、高精度、动态规划、暴力、模拟
T1题意
给你一个n∗m的网格图，问能在这个网格图上最多放几个互不冲突的中国象棋的马
(撇角影响该马吃与在它范围的马冲突)
Solution

可以想到本题分三种情况：

  • n或m的值为1，这样是可以全部放满的
  • n或m的值为2，这样可以考虑在(1,1)放棋子，可以想到若在第一列(假设n行m列n为2)放满那么对应的第三列是一个都不能放的然后再把第二列填满，可以发现每2∗2的矩形这样放是最优的。
  • n及m均不等于1或2，继续考虑在(1,1)放棋子，则(2,3)和(3,2)是放不了的，而这两个点恰好不在(1,1)到(n,n)的斜线上，可以试着交叉放，发现刚好是最优方案

Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
ll n,m,t;
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(t);
    while(t--){
        read(n),read(m);
        if (n==2){wt((m%4==0)?m:(m%4==1||m%4==3)?m+1:m+2,'\n');continue;}
        if (m==2){wt((n%4==0)?n:(n%4==1||n%4==3)?n+1:n+2,'\n');continue;}
        if (n==1||m==1){wt(n*m,'\n');continue;}
        wt((n*m+1)>>1,'\n');
    }
    return 0;
}
T2题意
在一个平面直角坐标系上给你若干条线段(与x轴或y轴平行)
求最大的一个交叉的(十字)
Solution
将线段的长度从大到小排序
若ans>len/2 则后面的线段都不会符合条件，直接break。

Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 100100
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int n,totA,totB,Ans;
struct S1{
    int l,r,T,len;
    inline void ins(int _l,int _r,int _T,int _len){l=_l,r=_r,T=_T,len=_len;}
    inline bool operator <(const S1 &x)const{return len>x.len;}
}A[maxn+10],B[maxn+10];
inline int get(int a,int b,int c,int d){return min(a,min(b,min(c,d)));}
int main(){
    read(n);
    for (int x1,y1,x2,y2,i=1;i<=n;i++){
        read(x1),read(y1),read(x2),read(y2);
        if (x1-x2==0){
            if (y1>y2) swap(y1,y2);
            A[++totA].ins(y1,y2,x1,y2-y1);
        }
        if (y1-y2==0){
            if (x1>x2) swap(x1,x2);
            B[++totB].ins(x1,x2,y1,x2-x1);
        }
    }
    sort(A+1,A+1+totA);
    sort(B+1,B+1+totB);
    for (int i=1;i<=totA;i++){
        if (A[i].len>>1<Ans) break;
        for (int j=1;j<=totB;j++){
            if (B[j].len>>1<Ans) break;
            if (A[i].l<=B[j].T&&B[j].T<=A[i].r&&B[j].l<=A[i].T&&A[i].T<=B[j].r)
                ckmax(Ans,get(B[j].T-A[i].l,A[i].r-B[j].T,A[i].T-B[j].l,B[j].r-A[i].T));
        }
    }
    printf(!Ans?"Human intelligence is really terrible\n":"%d\n",Ans);
    return 0;
}
T3题意
给你一个网格图，判断把一条边删掉后两端点是否联通
Solution
每删一条边就在边两边新建一个两个点并连边，若冲突则不连通。

Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 510
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int n,m,f[maxn*maxn],p;
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline int num(int x,int y){
    if(x<1||y<1||x==n||y==n)return 0;
    else return (x-1)*n+y;
}
inline void get(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy)puts("DAJIA"),p=1;
    else f[fy]=fx,p=0,puts("HAHA");
}
int main(){
    read(n),read(m);
    for(int i=0;i<=n*n;i++)f[i]=i;
    for(int x1,y1,x2,y2,i=1;i<=m;i++){
        read(x1),read(y1),read(x2),read(y2);
        if(i>1){
            if(p)read(x1),read(y1),read(x2),read(y2);
            else for(int t,i=1;i<5;i++)read(t);
        }
        if(x1>x2)swap(x1,x2);if(y1>y2)swap(y1,y2);
        if(x1<x2)get(num(x1,y1-1),num(x1,y1));
        else get(num(x1-1,y1),num(x1,y1));
    }
}

点我回到主页

发布者：TaK-Vin

发表评论

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 ( 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 ( 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 ( 注销 /  更改 )

取消

Connecting to %s