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