D题
简单模拟，按照题目要求判断就行
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int main() {
int t;
cin >> t;
int a1, b1, a2, b2;
while (t--) {
cin >> a1 >> b1 >> a2 >> b2;
if (a1 > b1)swap(a1, b1);
if (a2 > b2)swap(a2, b2);
if (a1 == a2 && b1 == b2)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)cout << "first" << endl;
else if (a1 != b1 && a2 == b2)cout << "second" << endl;
else if (a1 == b1 && a2 == b2) {
if (a1 > a2)cout << "first" << endl;
else if (a1 < a2)cout << "second" << endl;
}
else if (a1 != b1 && a2 != b2) {
if ((a1 + b1) % 10 > (a2 + b2) % 10)cout << "first" << endl;
else if ((a1 + b1) % 10 < (a2 + b2) % 10)cout << "second" << endl;
else if ((a1 + b1) % 10 == (a2 + b2) % 10) {
if (b1 > b2)cout << "first" << endl;
else if (b1 < b2)cout << "second" << endl;
}
}
}
return 0;
}
C题
一开始一直没有看到题目呜呜呜呜呜呜呜
就是对点连线，不能重复也不能形成闭合图形，那么有k个点，就有k-1个可以连接的点，奇数先手赢，偶数后手。
#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 7;
int main() {
int n, m;
cin >> n >> m;
int ans = n * m;
ans -= 1;
if (ans % 2 == 1)cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}
题意，给了四个点，求满足题目不等式的p1,p2的活动范围的相交的区域的体积，推导过程如下，可得为两个球的相交的体积。无白色草稿纸了，将就着看
这时候只需要求两个球相交的体积
参考博客
按照公式写就行
(参考了牛客题解区)
#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N = 1e6 + 7;
//pai 3.1415.....
const double pi = acos(-1);
int t;
double x[5], y[5], z[5];
double k1, k2;
int main() {
cin >> t;
while (t--) {
for (int i = 1; i <= 4; i++) {
cin >> x[i] >> y[i] >> z[i];
}
cin >> k1 >> k2;
//球一
double xs1 = k1 * k1 - 1;
double a1, b1, c1, r1, d1;
a1 = (k1 * k1 * x[2] - x[1]) / xs1;
b1 = (k1 * k1 * y[2] - y[1]) / xs1;
c1 = (k1 * k1 * z[2] - z[1]) / xs1;
d1 = 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];
d1 /= xs1;
r1 = sqrt(a1 * a1 + b1 * b1 + c1 * c1 - d1);
//球二
double xs2 = k2 * k2 - 1;
double a2, b2, c2, r2, d2;
a2 = (k2 * k2 * x[4] - x[3]) / xs2;
b2 = (k2 * k2 * y[4] - y[3]) / xs2;
c2 = (k2 * k2 * z[4] - z[3]) / xs2;
d2 = 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];
d2 /= xs2;
r2 = sqrt(a2 * a2 + b2 * b2 + c2 * c2 - d2);
//计算两球相交的体积 球1球心(a1,b1,c1)半径r1 球2球心(a2,b2,c2)半径r2
double ans = 0;
//两个圆心的距离
double d3 = sqrt((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2) + (c1 - c2) * (c1 - c2));
//判断，1.相离相切，ans为0. 2.内切内含，ans为里面那个球的体积
//3.相交
if (d3 >= r1 + r2) {
ans = 0;
}
else if (d3 + r1 <= r2) {
ans = (4.0 / 3.0) * pi * r1 * r1 * r1;
}
else if (d3 + r2 <= r1) {
ans = (4.0 / 3.0) * pi * r2 * r2 * r2;
}
else {
double co1 = (r1 * r1 + d3 * d3 - r2 * r2) / (2 * r1 * d3);
double h1 = r1 * (1 - co1);
double co2 = (r2 * r2 + d3 * d3 - r1 * r1) / (2 * r2 * d3);
double h2 = r2 * (1 - co2);
ans = pi * (3 * r1 - h1) * h1 * h1 / 3.0 + pi * (3 * r2 - h2) * h2 * h2 / 3.0;
}
printf("%.3lf\n", ans);
}
return 0;
}
K题呜呜呜呜呜呜呜呜呜呜又又又无法理解题目
题意的话大概就是求ai数组的可能值，需要用1~n来填充
是一个单调栈，刚开始栈为零，将ai数组一个一个放入，如果栈里有比放入大的数，弹出，bi数组为每次操作栈里数的个数
由题目给出条件可求出bi数组的一种可满足的值（bi数组即ai数组中每一个位置的size） 刚开始一直没有看懂
如果b[i]!=b[j],就把较小的数放到较小的下标里
如果b[i]==b[j],将小的数放到较大的下标里还是参考了题解区大佬的代码
#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N = 1e6 + 10;
struct p
{
int num, w;
}po[N];
//进行排序
bool cmp(struct p a, struct p b)
{
if (a.w != b.w)return a.w < b.w;
else return a.num > b.num;
}
int b[N], book[N], ans[N];
int main()
{
int n, k, f = 1;
cin >> n >> k;
for (int i = 0; i < k; i++){
int t, w;
cin >> t >> w;
b[t] = w;
book[t] = 1;
if (w > t || t > n || w > n) f = 0;
}
//当下标小于需要长度或者两者大于n时输出-1
if (f == 0) {
puts("-1");
return 0;
}
for (int i = 1; i <= n; i++){
if (book[i]){
for (int j = i - 1; j >= 1 && !book[j]; j--){
b[j] = max(b[j + 1] - 1, 1);//构造一个满足条件的b数组
book[j] = 1;
}
}
}
for (int i = 1; i <= n; i++){
if (book[i] == 0)b[i] = b[i - 1];
po[i].num = i;
po[i].w = b[i];
}
sort(po + 1, po + 1 + n, cmp);
for (int i = 1; i <= n; i++){
ans[po[i].num] = i;
}
for (int i = 1; i <= n; i++){
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
I题
题意，两只小企鹅在两个地图镜像移动，求移动到终点的移动方向的字典序最小。
按照顺序“D，L，R，U”的移动顺序，用bfs求出他的最短路径，分别储存两边地图，可以移动并且没有到过这个点入队列，用q储存路径，然后递归求，具体的看代码注释代码实现真的好神奇，呜呜呜呜呜呜呜呜呜呜巨菜
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int N = 0x3f3f3f3f;
char a[25][25], b[25][25];
int dp[25][25][25][25];
int d[4][4] = { 1,0,1,0,0,-1,0,1,0,1,0,-1,-1,0,-1,0 };
struct node {
int x1, y1, x2, y2;
};
char dd[4] = { 'D','L','R','U' };
node q[25][25][25][25];
char f[25][25][25][25];
char z[1000];
queue <node> p;
void bfs() {
while (!p.empty()) {
node u = p.front();
p.pop();
int k = dp[u.x1][u.y1][u.x2][u.y2];
for (int i = 0; i < 4; i++) {
//控制的小企鹅为左边的
//i==0: D; i==1: L; i==2: R; i==3: U;
//镜像同步
int x1 = u.x1 + d[i][0];
int y1 = u.y1 + d[i][1];
int x2 = u.x2 + d[i][2];
int y2 = u.y2 + d[i][3];
if (a[x1][y1] != '.')
x1 = u.x1, y1 = u.y1;
if (b[x2][y2] != '.')
x2 = u.x2, y2 = u.y2;
//dp是走到每个点的最小步数
//q是路径，从一个点到下一个点
//求出最短路径
if (dp[x1][y1][x2][y2] > k + 1) {
dp[x1][y1][x2][y2] = k + 1;
q[x1][y1][x2][y2] = node{ u.x1,u.y1,u.x2,u.y2 };
f[x1][y1][x2][y2] = i;
p.push(node{ x1,y1,x2,y2 });
}
}
}
}
int ans = 0;
void aa(node u) {
int x1 = u.x1;
int y1 = u.y1;
int x2 = u.x2;
int y2 = u.y2;
//将经过的地方做标记
a[x1][y1] = 'A'; b[x2][y2] = 'A';
//如果到达起点就返回
if (x1 == 20 && y1 == 20 && x2 == 20 && y2 == 1)
return;
//继续遍历
aa(q[x1][y1][x2][y2]);
//递归，ans为步数，z储存的为移动方向
z[++ans] = dd[f[x1][y1][x2][y2]];
}
int main() {
/*for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << d[i][j] << ' ';
}
cout << endl;
}*/
for (int i = 1; i <= 20; i++) {
cin >> a[i] + 1 >> b[i] + 1;
}
//A从(20,20)开始搜B从(20,1)开始
p.push(node{ 20,20,20,1 });
memset(dp, N, sizeof(dp));
dp[20][20][20][1] = 0;
bfs();
//终点 A为(1,20) B为(1,1),从终点到起点
aa(node{ 1,20,1,1 });
cout << ans << endl << z + 1 << endl;
for (int i = 1; i <= 20; i++) {
cout << a[i] + 1 << " " << b[i] + 1 << endl;
}
return 0;
}