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。
若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)); } }