题目目录：D C K F I
D题 Er Ba Game（2-8游戏）
题目大意：游戏规则：2-8对为最大牌，其次是牌面相同的两张牌，如果牌面都相同（如1-1,2-2）则数字大的赢；如果牌面不同（如1-2,3-5），则和%10数字大的一方赢。如果和%10数字一样，则有最大牌的一方赢。其他情况为平局。
思路：根据题目所给的规则枚举每一种可能的情况即可。
#include <bits/stdc++.h>
using namespace std;
void change(int &a,int &b){
int temp;
temp=a;
a=b;
b=temp;
}
int main(){
int t,a1,a2,b1,b2;
cin>>t;
while(t--){
cin>>a1>>b1>>a2>>b2;
if(a1>b1) change(a1,b1);
if(a2>b2) change(a2,b2);
if(a1==2&&b1==8&&!(a2==2&&b2==8)){
cout<<"first"<<endl;
continue;
}else if(a2==2&&b2==8&&!(a1==2&&b1==8)){
cout<<"second"<<endl;
continue;
}else if(a1==a2&&b1==b2){
cout<<"tie"<<endl;
continue;
}else if(a1==b1&&a2!=b2){
cout<<"first"<<endl;
continue;
}else if(a1!=b1&&a2==b2){
cout<<"second"<<endl;
continue;
}else{
if((a1+b1)%10==(a2+b2)%10){
if(b1>b2){
cout<<"first"<<endl;
continue;
}else if(b1==b2){
cout<<"tie"<<endl;
continue;
}else{
cout<<"second"<<endl;
continue;
}
}else if((a1+b1)%10>(a2+b2)%10){
cout<<"first"<<endl;
continue;
}else{
cout<<"second"<<endl;
continue;
}
}
}
return 0;
} C题 Draw Grids（绘制网格）
题目大意：给出一个n*m的点阵，可以在相邻两点之间连线，不可以连斜线。游戏开始时，ZYT为先手，游戏规定不能使线连接成任意一种多边形（不能形成闭合曲线），画出最后一笔的人获胜。输出ZYT是否能获胜。
思路：行和列只要有偶数，最后能绘制的总条数一定是奇数条，先手赢；否则为偶数条，后手赢。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
if(n%2==0||m%2==0) cout<<"YES";
else cout<<"NO";
}
K题 Stack（栈）
题目大意：给出一个序列a和记录部分a中的元素信息的序列b，题目中操作的意思是将a中的每个元素按照顺序放入一个空栈中，当栈顶元素大于要放入的元素，踢出栈顶元素（这样就保证了最后栈中留下来的元素组成的序列是a的最大升子序列），之后继续操作直到a中元素放完。b[i]表示序列a放到第i个时，栈中有b[i]个元素，即a的前i个元素能组成长度为b[i]的最大升子序列。现在给出序列a的长度和k个b[i]，要求构造出符合条件的序列a。
思路：利用st[]数组模拟入栈出栈操作，用top记录栈顶元素的序号（也等于栈中元素的个数），st[i]记录放入栈的元素的位置，栈顶元素出栈时则将被踢出的元素赋予最大值即可。最后再给栈内元素赋值，如果想不明白可以用纸笔模拟过程。最重要的是理解st[]在程序中记录当前放入第i个元素到栈顶的作用。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],b[N],st[N];//st[N]储存序列a中元素的序号，注意仔细体会
int main(){
int n,k,p,i;
cin>>n>>k;
for(i=1;i<=k;i++) cin>>p,cin>>b[p];
int top=0,t=n;//top记录栈中元素个数，t记录当前未被赋值的最大值
for(i=1;i<=n;i++){//i控制当前放第几个数
if(b[i]){//如果b[i]中储存了信息，查看当前序列a是否满足b中的条件
if(b[i]>top+1){//如果b中要求的元素个数比当前栈中元素+1还要多的话
cout<<-1;//说明即使再将元素放入栈也无法满足条件，不存在这样的a，直接结束程序
return 0;
}
while(b[i]<=top) a[st[top--]]=t--;
//给被踢出去的元素所在坐标的a赋值
//要让操作时栈中元素由栈顶开始踢出直到剩余b[i]-1个
//则在构造时要让这些元素是倒序
}
st[++top]=i;
}
while(top) a[st[top--]]=t--;//一个一个踢出栈直到栈空，使得所有元素均被赋值
for(i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}F题 Girlfriend（女朋友）
题目大意：ZYT和ZFeT分别有两个女朋友，他们都被自己的女朋友给诅咒了，咒语规则如下：
1）ZYT必须离他的女友A不少于k1倍的他离女友B之间的距离；
2）ZFeT必须离他的女友C不少于k2倍的他离女友D之间的距离。
用P1，P2表示ZYT和ZFeT，即|AP1|≥k1|BP1|，|CP2|≥k2|DP2|，也就是说他们可用的生活空间形成了两种集合状态，它们可能在内部有交集，现在要求交集的体积。
思路：这道题主要是运用了阿波罗尼斯圆模型，即给出定点A、B，所有满足PA/PB=k且不等于1 的点P的轨迹是一个以定比k内分和外分定线段AB的两个点连线为直径的圆，在三维空间中是一个球面。如果想知道证明过程的话，可以先了解一下角平分线定理和外角平分线定理。感性观察可以发现，使得PA/PB≥k的部分是一个实心球。也就是说现在给出两个球的大小（直径）和位置，求两球相交的体积。两球相交又包含两种情况：
1）大球包含小球，只需求出小球体积即可；
2）两球相交但无明显包含关系，可用如下公式：
//首先要解决的就是两个圆心的坐标问题
//要知道圆心坐标，只需要知道确定直径的两点坐标，然后求中点即可
//为了方便理解，编者选择了在过程中声明变量，而没有在程序开头将所有变量进行声明
//读者在整理代码时可以将声明的过程合并以减少代码长度
#include <bits/stdc++.h>
using namespace std;
typedef double db;//将double重命名为db
const db pi=3.1415926;
//虽然题目给的条件坐标都是int，但是建议用db储存
//这样运用除法时就不用考虑要不要乘1.0的问题
struct node{
db x,y,z;
}p[12];
db getpi(db a1,db a2,int k){//get position inside 求线段上的定比分点
db p=a2-(a2-a1)/(k+1);
return p;
}
db getpo(db a1,db a2,int k){//get position outside 求线段延长线上的定比分点
db p=a2+(a2-a1)/(k-1);
return p;
}
db dis(db x1,db y1,db z1,db x2,db y2,db z2){//distance
db len=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
return len;
}
db cos(db a,db b,db c){//c是对边
db cs=(a*a+b*b-c*c)/2/a/b;
return cs;
}
int main(){
int t;
cin>>t;
while(t--){
int k[3];
for(int i=1;i<=4;i++) cin>>p[i].x>>p[i].y>>p[i].z;
for(int i=1;i<=2;i++) cin>>k[i];
for(int i=1;i<=2;i++){
p[2*i+3].x=getpi(p[2*i-1].x,p[2*i].x,k[i]);
p[2*i+3].y=getpi(p[2*i-1].y,p[2*i].y,k[i]);
p[2*i+3].z=getpi(p[2*i-1].z,p[2*i].z,k[i]);
p[2*i+4].x=getpo(p[2*i-1].x,p[2*i].x,k[i]);
p[2*i+4].y=getpo(p[2*i-1].y,p[2*i].y,k[i]);
p[2*i+4].z=getpo(p[2*i-1].z,p[2*i].z,k[i]);
}//获得了四个定比分点的坐标p[5],p[6],p[7],p[8]
for(int i=1;i<=2;i++){
p[i+8].x=(p[2*i+3].x+p[2*i+4].x)/2;
p[i+8].y=(p[2*i+3].y+p[2*i+4].y)/2;
p[i+8].z=(p[2*i+3].z+p[2*i+4].z)/2;
} //获得了两个圆心坐标p[9],p[10]
db r,R;
r=dis(p[5].x,p[5].y,p[5].z,p[6].x,p[6].y,p[6].z)/2;
R=dis(p[7].x,p[7].y,p[7].z,p[8].x,p[8].y,p[8].z)/2;
//获得了两球的半径,其实无法保证r和R的相对大小
db dx=dis(p[9].x,p[9].y,p[9].z,p[10].x,p[10].y,p[10].z);
//得到圆心距，根据半径之比求到交平面的距离之比，从而求h1和h2
//用公式之前要先考虑两球是否相交，圆心距和半径的和与差作比较即可
db v;//相交的体积
if(r+R<=dx) v=0;
else if(R-r>=dx) v=4.0/3*pi*r*r*r;//r圆在R圆中
else if(r-R>=dx) v=4.0/3*pi*R*R*R;//R圆在r圆中
else{
db h1,h2;
h1=R*(1-cos(R,dx,r));
h2=r*(1-cos(r,dx,R));
v=pi*h1*h1*(R-1.0/3*h1)+pi*h2*h2*(r-1.0/3*h2);
}
printf("%.4lf\n",v);//题目要求精度小于0.001，在这里保留四位小数
}
return 0;
}I题 Penguins（企鹅）
题目大意：游戏给出两个20*20网格的地图，两个地图之间有一列墙隔开，地图上有一些网格是障碍。网格（x，y）表示它在地图的第x行第y列。企鹅可以上下左右移动，每次移动一格。如果企鹅遇到了障碍或者边界，不移动。玩家可以控制左企鹅上下左右移动，但是两只企鹅的移动是镜像的，如果有一只企鹅在指定方向遇到障碍，那么它不移动，另一只企鹅仍可以移动。游戏开始，左边的企鹅从左地图（20,20）出发，要移动到（1,20），右边的企鹅从（20,1）出发，要移动到（1,1）。只有两只企鹅能够到达终点，游戏才胜利。要找到最短的一条路使游戏胜利，如果有多条，按照下、左、右、上的有限顺序输出最短路径。（提示：当企鹅a到达终点而企鹅B没有时，B的挪动可能会使得A离开终点）
输入描述：输入游戏地图，‘.’代表可以走的网格，‘#’代表障碍，‘ ’是地图间的墙。
输出描述：输出22行，第一行是最短路径的步数。第二行输出每一步走的方向，接下来20行用‘A’记录企鹅在游戏过程中的足迹。
思路：在企鹅所处位置按照下左右上（题目要求的优先级顺序）搜索可以走的路，并且将它入列。结点记录当前两只企鹅所在坐标以及左企鹅的行进方向。只要行进方向可以让一只企鹅移动，就把下一步入列，直到两只企鹅都到终点为止。此时已经得到了左企鹅从起点到终点的行进方向字符串，只要按序将每一步赋值为A，输出地图即可。
#include <bits/stdc++.h>
using namespace std;
string od="DLRU";
int x[2][4]={1,0,0,-1,1,0,0,-1};
int y[2][4]={0,-1,1,0,0,1,-1,0};
char l[21][21],r[21][21];
int inq[21][21][21][21];//初值全为零
struct node{
int x1,y1,x2,y2;
string s;
};
int judge(int x,int y,char c[21][21]){
if(x>0&&y>0&&x<21&&y<21&&c[x][y]!='#') return 1;
//没有说走过的路就不能走，当c[x][y]=='.'||c[x][y]=='A'的时候都可以走
return 0;
}
int arrive(int x1,int y1,int x2,int y2){//判断是否到达终点
if(x1==1&&y1==20&&x2==1&&y2==1) return 1;
return 0;
}
void print(string s){
cout<<s.size()<<endl;
cout<<s<<endl;
int nx1=20,ny1=20,nx2=20,ny2=1;
l[nx1][ny1]='A';
r[nx2][ny2]='A';
for(int i=0;i<s.size();i++){
for(int j=0;j<4;j++){
if(s[i]==od[j]){
nx1+=x[0][j];
ny1+=y[0][j];
nx2+=x[1][j];
ny2+=y[1][j];
if(judge(nx1,ny1,l)) l[nx1][ny1]='A';
else{
nx1-=x[0][j];
ny1-=y[0][j];
}
if(judge(nx2,ny2,r)) r[nx2][ny2]='A';
else{
nx2-=x[1][j];
ny2-=y[1][j];
}
}
}
}
for(int i=1;i<21;i++){
cout<<l[i]+1<<" "<<r[i]+1<<endl;
}
}
void bfs(){//两个结点同时搜索
int nx1,ny1,nx2,ny2;
inq[20][20][20][1]=1;
queue<node> q;
q.push({20,20,20,1,""});
while(!q.empty()){
node top=q.front();
q.pop();
if(arrive(top.x1,top.y1,top.x2,top.y2)){
print(top.s);
return;
}
for(int i=0;i<4;i++){
nx1=top.x1+x[0][i];
ny1=top.y1+y[0][i];
nx2=top.x2+x[1][i];
ny2=top.y2+y[1][i];
//尝试对两只企鹅做下一步操作，判断左右企鹅分别是否能走
int f1=1,f2=1;//其实起到的是布尔类型的作用
if(!judge(nx1,ny1,l)) f1=0;//左企鹅不能走
if(!judge(nx2,ny2,r)) f2=0;//右企鹅不能走
if(f1==0&&f2==0){//都不能走
continue;
}else if(!f1){//左企鹅不能走
nx1=top.x1;
ny1=top.y1;
}else if(!f2){//右企鹅不能走
nx2=top.x2;
ny2=top.y2;
}
if(inq[nx1][ny1][nx2][ny2]==1) continue;
else inq[nx1][ny1][nx2][ny2]=1;
q.push({nx1,ny1,nx2,ny2,top.s+od[i]});
}
}
}
int main(){
for(int i=1;i<21;i++){
cin>>l[i]+1>>r[i]+1;
}
bfs();
return 0;
}
京公网安备 11010502036488号