A .Drazil and Date
题目大意:问是否有一条路径，从(0,0)到(x,y)正好走s步的路线存在，每步可以上下左右移动一格
思路:显然先计算出(0,0)到(x,y)的最短距离后，看剩下的步数是否是偶数就可以了，注意x,y为负数的情况
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int mabs(int x) 5 { 6 if(x>0)return x;else return -x; 7 } 8 int main() 9 { 10 int n,m,step; 11 scanf("%d%d%d",&n,&m,&step); 12 int u=mabs(n)+mabs(m); 13 if(u>step)printf("No "); 14 else if((step-u)&1)printf("No "); 15 else printf("Yes "); 16 return 0; 17 }
B. Drazil and His Happy Friends
题目大意:n个男生从0编号到n-1，ｍ个女生编号从０到m-1,男女中有些快乐有些不快乐，每次邀请编号为i mod n的男生和i mod m编号的女生，只要有一个快乐，两个人就都快乐了，问是否有可能让所有人都快乐？
思路:感觉使劲想应该有数学公式可以推的，懒了那么一下下于是一个大模拟搞定
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #define maxn 1000 5 using namespace std; 6 int boy[maxn],girl[maxn],b,g,x; 7 int main() 8 { 9 int n,m; 10 scanf("%d%d",&n,&m); 11 scanf("%d",&b); 12 for(int i=1;i<=b;i++) 13 { 14 scanf("%d",&x); 15 boy[x]=1; 16 } 17 scanf("%d",&g); 18 for(int i=1;i<=g;i++) 19 { 20 scanf("%d",&x); 21 girl[x]=1; 22 } 23 int max_=max(n,m); 24 for(int i=0;i<max_*100;i++) 25 { 26 girl[i%m]=boy[i%n]=girl[i%m]|boy[i%n]; 27 } 28 for(int i=0;i<n;i++) 29 { 30 if(boy[i]==0){printf("No ");return 0;} 31 //printf("%d ",boy[i]); 32 } 33 for(int i=0;i<m;i++)if(girl[i]==0){printf("No ");return 0;} 34 printf("Yes "); 35 return 0; 36 }
C. Drazil and Factorial
题目大意:给出函数Ｆ(x)为ｘ的十进制下各位数阶乘的乘积，求最大的ｙ使得F(x)=F(y)并且ｙ中不含有０和１
思路：应该挺容易想的，首先素数显然只能放在那儿不能动，合数的话尽量拆成较多的数，比如９!可以拆成７!*3!*3!*2!一次类推，总共就２到９一共８个数，除去素数就只要手推几个数这题就出来了
1 #include<cstdio> 2 using namespace std; 3 char ch[1000]; 4 int cnt[100]; 5 int main() 6 { 7 int n; 8 scanf("%d",&n); 9 scanf("%s",ch+1); 10 for(int i=1;i<=n;i++) 11 { 12 int u=ch[i]-'0'; 13 if(u<=1)continue; 14 else if(u==4) 15 { 16 cnt[2]+=2; 17 cnt[3]++; 18 } 19 else if(u==6) 20 { 21 cnt[3]++; 22 cnt[5]++; 23 } 24 else if(u==8) 25 { 26 cnt[7]++; 27 cnt[2]+=3; 28 } 29 else if(u==9) 30 { 31 cnt[2]++; 32 cnt[3]+=2; 33 cnt[7]++; 34 } 35 else 36 { 37 cnt[u]++; 38 } 39 } 40 for(int i=9;i>=2;i--) 41 { 42 for(int j=1;j<=cnt[i];j++)printf("%d",i); 43 } 44 printf(" "); 45 return 0; 46 }
D. Drazil and Tiles
题目大意:给一个ｎ*m的棋盘，放１＊２的骨牌，棋盘上有些位置不能放骨牌，问能否覆盖满整个棋盘并且覆盖方案数唯一
思路:本质上是二分图最大匹配是否唯一的问题（黑白染色建图，每个匹配对应着唯一的放骨牌的数，最大匹配对应着放满的情况）
实际不用那么复杂，只要看是否存在一个点三头不能放，唯有一头能放的结构，然后每次在这种结构中放骨牌即可
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<queue> 5 #define maxn 4000 6 using namespace std; 7 const int dx[10]={0,1,-1,0,0};//down up rig,lef 8 const int dy[10]={0,0,0,1,-1}; 9 int map[maxn][maxn]; 10 queue<pair<int , int > > q; 11 char ch[maxn]; 12 //can 1 13 int check(int x,int y) 14 { 15 for(int i=1;i<=4;i++)if(map[x+dx[i]][y+dy[i]]==1) 16 { 17 int flag=0; 18 for(int j=1;j<=4;j++)if(j!=i) 19 { 20 if(map[x+dx[j]][y+dy[j]]==1){flag=1;break;} 21 } 22 if(flag==0)return i; 23 } 24 return 0; 25 } 26 int main() 27 { 28 int n,m; 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=n;i++) 31 { 32 scanf("%s",ch+1); 33 for(int j=1;j<=m;j++) 34 { 35 if(ch[j]=='.')map[i][j]=1;else map[i][j] = 0; 36 } 37 } 38 for(int i=1;i<=n;i++) 39 { 40 for(int j=1;j<=m;j++) 41 { 42 int u; 43 if(u=check(i,j) && map[i][j]==1)q.push(make_pair(i,j)); 44 } 45 } 46 while(!q.empty()) 47 { 48 pair<int,int> temp=q.front(); 49 q.pop(); 50 int x=temp.first,y=temp.second; 51 int u=check(x,y); 52 if(u==0)continue; 53 if(u==1) 54 { 55 map[x][y]='^'; 56 map[x+1][y]='v';x++; 57 } 58 if(u==2) 59 { 60 map[x][y]='v'; 61 map[x-1][y]='^';x--; 62 } 63 if(u==3) 64 { 65 map[x][y]='<'; 66 map[x][y+1]='>';y++; 67 } 68 if(u==4) 69 { 70 map[x][y]='>'; 71 map[x][y-1]='<';y--; 72 } 73 for(int i=1;i<=4;i++) 74 { 75 int xx=temp.first+dx[i],yy=temp.second+dy[i]; 76 if(map[xx][yy]==1 && check(xx,yy))q.push(make_pair(xx,yy)); 77 } 78 for(int i=1;i<=4;i++) 79 { 80 81 int xx=x+dx[i],yy=y+dy[i]; 82 if(map[xx][yy]==1 && check(xx,yy))q.push(make_pair(xx,yy)); 83 } 84 } 85 for(int i=1;i<=n;i++) 86 { 87 for(int j=1;j<=m;j++) 88 { 89 if(map[i][j]==1) 90 { 91 printf("Not unique "); 92 return 0; 93 } 94 } 95 } 96 for(int i=1;i<=n;i++) 97 { 98 for(int j=1;j<=m;j++) 99 { 100 if(map[i][j]==0) 101 { 102 printf("*"); 103 } 104 else printf("%c",map[i][j]); 105 } 106 printf(" "); 107 } 108 return 0; 109 }
E. Drazil and Park
题目大意:简单来说给你一个环形，上面有Ｎ棵树，每棵树间有个距离，每棵树有高度，每次一段连续的区间是不能走的，你要在剩下的环形中找出最大的一段使得dist(x,y)+２＊(h[x]+h[y])最大
思路:环形拆成两倍很容易处理，dist用前缀和很容易处理，至于h可以挂靠在前缀和中处理，也就是前缀和sum［ｉ］最后再加上两倍h[i]，当然还要记录负数的前缀和，也是同样处理，问题就是两棵树不能是同一颗．．．我的做法是一旦发现它们是同一颗，我把这个点改为负无穷，再求一遍最大值，貌似这样处理的确烦了
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define maxn 5000000 5 #define inf 9223372036854775807ll 6 using namespace std; 7 long long lx[maxn],rx[maxn],a[maxn]; 8 struct T 9 { 10 long long l;long long r; 11 long long posl;long long posr; 12 T () 13 { 14 l=-inf; 15 r=-inf; 16 } 17 }tree[maxn]; 18 T max(T a,T b) 19 { 20 T ans; 21 if(a.l>b.l)ans.l=a.l,ans.posl=a.posl; 22 else ans.l=b.l,ans.posl=b.posl; 23 if(a.r>b.r)ans.r=a.r,ans.posr=a.posr; 24 else ans.r=b.r,ans.posr=b.posr; 25 return ans; 26 } 27 void build(long long node,long long l,long long r) 28 { 29 if(l+1==r) 30 { 31 tree[node].l=lx[l]; 32 tree[node].r=rx[l]; 33 tree[node].posl=tree[node].posr=l; 34 return ; 35 } 36 long long mid=(l+r)>>1; 37 build(node*2,l,mid); 38 build(node*2+1,mid,r); 39 tree[node]=max(tree[node*2],tree[node*2+1]); 40 } 41 void update(long long node,long long l,long long r,long long pos,long long ll,long long rr) 42 { 43 if(l+1==r) 44 { 45 tree[node].l=ll;tree[node].r=rr; 46 return ; 47 } 48 long long mid=(l+r)>>1; 49 if(pos<mid)update(node*2,l,mid,pos,ll,rr); 50 else update(node*2+1,mid,r,pos,ll,rr); 51 tree[node]=max(tree[node*2],tree[node*2+1]); 52 } 53 T query(long long node,long long l,long long r,long long ql,long long qr) 54 { 55 if(ql<=l && r<=qr) 56 { 57 return tree[node]; 58 } 59 long long mid=(l+r)>>1; 60 T ans,temp; 61 if(mid>ql)temp=query(node*2,l,mid,ql,qr); 62 ans=max(ans,temp); 63 if(mid<qr)temp=query(node*2+1,mid,r,ql,qr); 64 ans=max(ans,temp); 65 return ans; 66 } 67 void debug(long long n) 68 { 69 for(long long i=1;i<=2*n;i++) 70 { 71 printf("%d ",lx[i]); 72 } 73 puts(""); 74 for(long long i=1;i<=2*n;i++) 75 { 76 printf("%d ",rx[i]); 77 } 78 puts(""); 79 } 80 int main() 81 { 82 long long n,m,x; 83 scanf("%I64d%I64d",&n,&m); 84 for(long long i=1;i<=n;i++) 85 { 86 scanf("%I64d",&a[i+1]); 87 a[i+n+1]=a[i+1]; 88 } 89 for(long long i=1;i<=2*n;i++) 90 { 91 lx[i]=a[i]+lx[i-1]; 92 rx[i]=-a[i]+rx[i-1]; 93 } 94 for(long long i=1;i<=n;i++) 95 { 96 scanf("%I64d",&x); 97 lx[i]+=2*x; 98 lx[i+n]+=2*x; 99 rx[i]+=2*x; 100 rx[i+n]+=2*x; 101 } 102 //debug(n); 103 build(1,1,2*n+1); 104 long long ll,rr; 105 for(int i=1;i<=m;i++) 106 { 107 scanf("%I64d%I64d",&ll,&rr); 108 if(ll<=rr) 109 { 110 ll+=n-1; 111 rr++; 112 swap(ll,rr); 113 } 114 else 115 { 116 swap(ll,rr); 117 ll++;rr--; 118 } 119 T ret=query(1,1,2*n+1,ll,rr+1); 120 if(ret.posl==ret.posr) 121 { 122 update(1,1,2*n+1,ret.posl,-inf,-inf); 123 T ret2=query(1,1,2*n+1,ll,rr+1); 124 printf("%I64d ",max(ret.l+ret2.r,ret2.l+ret.r)); 125 update(1,1,2*n+1,ret.posl,ret.l,ret.r); 126 }else 127 printf("%I64d ",ret.l+ret.r); 128 } 129 return 0; 130 }