C
给你n*m的网格，每一次可以横的或者竖的连接两个相邻的两个格点，轮流操作，连接的过程中不能有封闭图形，问最后先手赢还是后手赢
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;cin>>n>>m;
if(n>m){int x=n;n=m;m=x;}
int ans=m*n-1;
if(ans%2)puts("YES");
else puts("NO");
}
数据其实可以出的大一点。
D
比牌的大小，(2,8)最大，a=b仅次，两个人的两张牌都相等，比较(a+b)%10的大小，
如果还是相等，比较b的大小，a,b可以交换，即a为小的那个牌，b为更大的牌。问第一个赢还是第二个。
if,else语句。
#include <bits/stdc++.h>
using namespace std;
int main(){
int a1,b1,a2,b2;
int t;
cin>>t;
while(t--){
cin>>a1>>b1>>a2>>b2;
if(a1>b1) swap(a1,b1);
if(a2>b2) swap(a2,b2);
if(a1==2&&b1==8&&a2==2&&b2==8) cout<<"tie"<<endl;
else{
if(a1==2&&b1==8) cout<<"first"<<endl;
else if(a2==2&&b2==8) cout<<"second"<<endl;
else{
if(a1==b1&&a2==b2){
if(a1==a2) cout<<"tie"<<endl;
if(a1>a2) cout<<"first"<<endl;
if(a1<a2) cout<<"second"<<endl;
}
else if(a1==b1) cout<<"first"<<endl;
else if(a2==b2) cout<<"second"<<endl;
else {
int a=(a1+b1)%10;
int b=(a2+b2)%10;
if(a>b) cout<<"first"<<endl;
else if(a<b) cout<<"second"<<endl;
else {
if(b1>b2) cout<<"first"<<endl;
else if(b1<b2) cout<<"second"<<endl;
else cout<<"tie"<<endl;
}
}
}
}
}
return 0;
}E
求两个球相交的部分的体积
题解参考大佬 大哥
推一波式子：
对于第一个圆，设P的坐标为;
A,B,C,D坐标分别为;
那么就有：
移项，合并，之后：
球的一般方程：
球的标准方程：
圆心
半径:
那有了这些之后我们又该如何求相交部分的体积呢?
来源于：https://blog.csdn.net/ouyangcheese/article/details/115421270
当然也可以自己推，（懒）
公式：
比赛时候以为是二重积分啥的，想了半天高数公式，发现不会，坐牢一下午，还不如百度一下公式。（bushi）
啥也不是
代码：
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);//圆周率
double x[10],y[10],z[10];
double k1,k2;
int main(){
//freopen("in.txt", "r", stdin);
//freopen("test.txt", "w", stdout);
int T;
cin>>T;
while(T--){
for(int i=1;i<=4;i++){
cin>>x[i]>>y[i]>>z[i];
}
cin>>k1>>k2;
//计算第一个圆
double xx1=k1*k1-1;
double c1x,c1y,c1z,c1r,d;
c1x=(k1*k1*x[2]-x[1])/xx1;//求圆心
c1y=(k1*k1*y[2]-y[1])/xx1;
c1z=(k1*k1*z[2]-z[1])/xx1;
d=k1*k1*(x[2]*x[2]+y[2]*y[2]+z[2]*z[2])-x[1]*x[1]-y[1]*y[1]-z[1]*z[1];
d/=xx1;
c1r=sqrt(c1x*c1x+c1y*c1y+c1z*c1z-d);//求半径
//cout<<c1x<<" "<<c1y<<" "<<c1z<<" "<<d<<" "<<c1r<<endl;
//计算第二个圆
double xx2=k2*k2-1;
double c2x,c2y,c2z,c2r,dd;
c2x=(k2*k2*x[4]-x[3])/xx2;
c2y=(k2*k2*y[4]-y[3])/xx2;
c2z=(k2*k2*z[4]-z[3])/xx2;
dd=k2*k2*(x[4]*x[4]+y[4]*y[4]+z[4]*z[4])-x[3]*x[3]-y[3]*y[3]-z[3]*z[3];
dd/=xx2;
c2r=sqrt(c2x*c2x+c2y*c2y+c2z*c2z-dd);
//cout<<c2x<<" "<<c2y<<" "<<c2z<<" "<<dd<<" "<<c2r<<endl;
//求答案
double ans=0;
double dis=sqrt((c1x-c2x)*(c1x-c2x)+(c1y-c2y)*(c1y-c2y)+(c1z-c2z)*(c1z-c2z));
if(dis>=c1r+c2r){//外切或者相离，0
ans=0;
}
else if(c1r+dis<=c2r){//内含，两种情况，答案为体积小的那个球
ans=(4.00/3.00)*pi*c1r*c1r*c1r;
}
else if(c2r+dis<=c1r){
ans=(4.00/3.00)*pi*c2r*c2r*c2r;
}
else{//相交
double cal=(c1r*c1r+dis*dis-c2r*c2r)/(2.00*dis*c1r);
double h=c1r*(1-cal);
ans+=(1.00/3.00)*pi*(3.00*c1r-h)*h*h;
cal=(c2r*c2r+dis*dis-c1r*c1r)/(2.00*dis*c2r);
h=c2r*(1.00-cal);
ans+=(1.00/3.00)*pi*(3.00*c2r-h)*h*h;
}
printf("%.3f\n",ans);
}
}K
给定一段伪代码，
Stk is an empty stack
for i = 1 to n :
while ( Stk is not empty ) and ( Stk's top > a[i] ) :
pop Stk
push a[i]
b[i]=Stk's size当栈顶的元素大于,则弹出栈顶元素，
等于当前栈的大小。
现在给你若干个b数组的几个数，构造一个数组a，数组a只能是中的数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
#define debug(x) cout << #x << ": " << x << endl;
int a[N],b[N];
stack<int> st;
int main(){
int n,k;
cin>>n>>k;
int x;
for(int i=0;i<k;i++){
cin>>x>>b[x];
}//先构造b数组，
for(int i=1;i<=n;i++){
if(!b[i]) b[i]=b[i-1]+1;
if(b[i]>b[i-1]+1){//一次只能push进去一个元素，所以最多，b[i]<=b[i-1]+1;
puts("-1");
return 0;
}
}
int cnt=1;
//通过B数组，反过来模拟构造a数组。
//从后面开始填
for(int i=n;i>=1;i--){
while(b[i]>st.size()) st.push(cnt++);//构造没有pop之前的数组，有pop停止，最后的数就是数组a后面的数
a[i]=st.top();
st.pop();
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}I
两个企鹅，一个在左边的地图，一个在右边的图，两只企鹅同时走，左边的企鹅往左，右边的企鹅往右，左往右，右往左，但是上下移动时，两边都一样。一只企鹅不能走，另一只能走，则一只停下，另一只继续往前。一只到了终点，如果另一个动了，到了终点的一样还是会走。问两个企鹅都到达终点时，求最短路径步数，并输出路径。
模拟，把两个企鹅看成一个状态点，用一个结构体表示
struct node{
int ax,ay,bx,by;//a企鹅，b企鹅
string s;//记录答案
};代码：
参考江大佬的代码，自己写了一遍。
debug了好久，落泪
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30;
#define debug(x) cout << #x << ": " << x << endl;
char a[N][N],b[N][N];
struct node{
int ax,ay,bx,by;
string s;
};
//DLRU,保证字典序最大
int dx[]={1,0,0,-1};
int dy[]={0,-1,1,0};
bool vis[N][N][N][N];//因为是把两个企鹅看成一个状态，走过了这个状态就标记，跟一般BFS模板题一样，比赛时候觉得代码太长了，没敢下手，落泪。太菜了。
bool chk(int x,int y,char a[][N]){
if(x>20||x<=0||y<=0||y>20||a[x][y]=='#') return true;
return false;
}
//上下左右，四个方向都判断一遍，能走就加入队列。
node getD(node t){
t.ax+=dx[0],t.ay+=dy[0];
if(chk(t.ax,t.ay,a)) t.ax-=dx[0],t.ay-=dy[0];
t.bx+=dx[0],t.by+=dy[0];
if(chk(t.bx,t.by,b)) t.bx-=dx[0],t.by-=dy[0];
t.s+='D';
return t;
}
node getL(node t){
t.ax+=dx[1],t.ay+=dy[1];
if(chk(t.ax,t.ay,a)) t.ax-=dx[1],t.ay-=dy[1];
t.bx+=dx[2],t.by+=dy[2];
if(chk(t.bx,t.by,b)) t.bx-=dx[2],t.by-=dy[2];
t.s+='L';
return t;
}
node getR(node t){
t.ax+=dx[2],t.ay+=dy[2];
if(chk(t.ax,t.ay,a)) t.ax-=dx[2],t.ay-=dy[2];
t.bx+=dx[1],t.by+=dy[1];
if(chk(t.bx,t.by,b)) t.bx-=dx[1],t.by-=dy[1];
t.s+='R';
return t;
}
node getU(node t){
t.ax+=dx[3],t.ay+=dy[3];
if(chk(t.ax,t.ay,a)) t.ax-=dx[3],t.ay-=dy[3];
t.bx+=dx[3],t.by+=dy[3];
if(chk(t.bx,t.by,b)) t.bx-=dx[3],t.by-=dy[3];
t.s+='U';
return t;
}
string bfs(){
queue<node>q;
node start,next;
start={20,20,20,1,""};
q.push(start);
vis[20][20][20][1]=1;
while(!q.empty()){
start=q.front();
q.pop();
if(start.ax==1&&start.ay==20&&start.bx==1&&start.by==1) return start.s;
// debug(start.ax);
// debug(start.ay);
// debug(start.bx);
// debug(start.by);
// debug(start.s);
next=getD(start);
if(!vis[next.ax][next.ay][next.bx][next.by]){
vis[next.ax][next.ay][next.bx][next.by]=1;
q.push(next);
}
next=getL(start);
if(!vis[next.ax][next.ay][next.bx][next.by]){
vis[next.ax][next.ay][next.bx][next.by]=1;
q.push(next);
}
next=getR(start);
if(!vis[next.ax][next.ay][next.bx][next.by]){
vis[next.ax][next.ay][next.bx][next.by]=1;
q.push(next);
}
next=getU(start);
if(!vis[next.ax][next.ay][next.bx][next.by]){
vis[next.ax][next.ay][next.bx][next.by]=1;
q.push(next);
}
}
return "";
}
int main(){;
for(int i=1;i<=20;i++) scanf("%s", a[i] + 1), scanf("%s", b[i] + 1);
//for(int i=1;i<=20;i++) printf("%s ", a[i] + 1), printf("%s\n", b[i] + 1);
string ans=bfs();
cout<<ans.size()<<endl;
cout<<ans<<endl;
node t={20,20,20,1,""};
for(auto c:ans){//重新进入再走一遍，把路径覆盖成“A”
a[t.ax][t.ay]='A';
b[t.bx][t.by]='A';
if(c=='D')
t=getD(t);
else if(c=='L'){
t=getL(t);
}
else if(c=='R'){
t=getR(t);
}
else t=getU(t);
}
a[1][20]='A',b[1][1]='A';
for(int i=1;i<=20;i++) printf("%s ", a[i] + 1), printf("%s\n", b[i] + 1);//输出
}
京公网安备 11010502036488号