AtCoder Beginner Contest 246（A ~ E）

A - Four Points

题意：

$xyxy$ 平面上有个矩形，该矩形的每条边都平行于 $xx$ 轴或 $yy$ 轴，并且面积不为零。给定矩形的三个点的坐标，求第四个点的坐标

分析：

由于矩形的每条边都平行于 $xx$ 轴或 $yy$ 轴，所以如果 $x_1=x_{2}x\_1\; =\; x\_2$ ，则说明这两点在同一条平行于 $xx$ 轴的矩形边上，其余两点则在另一条平行于 $xx$ 轴的矩形边上，故有 $x_{ans}=x_{3}x\_\{ans\}\; =\; x\_3$ 。 $yy$ 轴同理

代码：

#include<bits/stdc++.h>
using namespace std; 
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int x1, x2, x3, y1, y2, y3;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
	
	if (x1 == x2) cout << x3 << ' ';
	if (x1 == x3) cout << x2 << ' ';
	if (x2 == x3) cout << x1 << ' ';
	
	if (y1 == y2) cout << y3;
	if (y1 == y3) cout << y2;
	if (y2 == y3) cout << y1;
	
	return 0;
}

另外我们可以用异或的方式找到那个“独特的值”，两个相同的数异或结果为 $00$ ，而 $00$ 异或任何数结果都为那个数本身，所以我们有：

#include<bits/stdc++.h>
using namespace std; 
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int x1, x2, x3, y1, y2, y3;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
	
	cout << (x1 ^ x2 ^ x3) << ' ' << (y1 ^ y2 ^ y3);
	
	return 0;
}

B - Get Closer

题意：

在二维平面中给定一个坐标 $(A,B)(A,\; B)$ ，从 $(0,0)(0,0)$ 出发，向 $(A,B)(A,\; B)$ 的位置移动距离 $11$ ，输出移动后的坐标。数据保证 $(A,B)(A,\; B)$ 离 $(0,0)(0,\; 0)$ 距离大于 $11$

分析：

用勾股定理求 $(0,0)(0,\; 0)$ 到 $(A,B)(A,\; B)$ 的距离 $dd$ ，设移动后坐标为 $(x,y)(x,\; y)$ ，则有： $\frac{1}{d}=\frac{x}{A}=\frac{y}{B}\backslash frac\{1\}\{d\}\; =\; \backslash frac\{x\}\{A\}\; =\; \backslash frac\{y\}\{B\}$ 即： $x=\frac{A}{d}y=\frac{B}{d}x\; =\; \backslash frac\{A\}\{d\}\; \backslash quad\; y\; =\; \backslash frac\{B\}\{d\}$

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    double a, b;
    cin >> a >> b;
    double d = pow(a * a + b * b, 0.5);
    
    printf("%.12lf %.12lf", a / d, b / d);
	
	return 0;
}

C - Coupon

题意：

一家商店有 $NN$ 件商品。第 个商品的价格为 $A_{i}A\_i$ 元。高桥有 $KK$ 张券，每张券价值为 $XX$ 。每张优惠券可用于一件商品。可以在同一商品上使用任意数量的优惠券，也可以不使用优惠卷。在价格为 $aa$ 元的商品上使用 $kk$ 个优惠券可以以 $max(a\mathrm{-}kX,0)max(a\; -\; kX,\; 0)$ 元的价格购买它。输出购买所有物品所需的最低金额

分析：

先把每个商品价格存到数组中，并把总价格 $ansans$ 存下来，再遍历数组，在优惠卷数量不为 $00$ 的情况下，把所有价格大于等于 $XX$ 的商品用优惠卷减到小于 $XX$ 的价格，并记录使用优惠卷的数量 $sumsum$ ，遍历后答案 $res=ans-X\times sumres\; =\; ans\; -\; X\; \backslash times\; sum$ 。若优惠卷数量仍有剩余，则排序后从后向前遍历数组（因为排序后每个商品剩余价格大的在数组后面），直到 $k=0k\; =\; 0$ 或遍历完数组时停止，更新 $resres$ 输出结果

代码：

#include<bits/stdc++.h>
using namespace std;
 
const int N = 200010;
 
int a[N];
 
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
    int n, k, x;
    cin >> n >> k >> x;
    
    for (int i = 1;i <= n;i ++) cin >> a[i];
    
    long long ans = 0;
    for (int i = 1;i <= n;i ++) ans += a[i];
    
    long long sum = 0;
    for (int i = 1;i <= n;i ++)
    {
        while (k != 0 && a[i] >= x)
        {
            a[i] -= x;
            k --;
            sum ++;
        }
    }
    
    long long res = ans - x * sum;
    
    sort (a + 1,a + n + 1);
    
    while (k)
    {
        if (n == 0) break;
        res -= a[n --];
        k --;
    }
    
    cout << res;
	
	return 0;
}

D - 2-variable Function

题意：

给定一个整数 $NN$ ，求满足以下条件的最小的 $XX$ :

• $XX$ 大于等于 $NN$
• 有一对非负整数 $(a,b)(a,\; b)$ 满足 $X=a^3+a^{2}b+a{b}^2+b^{3}X\; =\; a^3\; +\; a^2b\; +\; ab^2\; +\; b^3$

$NN$ 满足

分析：

因为 $NN$ 的最大取值为 $10^{18}10^\{18\}$ ，所以 $aa$ 或 $bb$ 的最大取值为 $10^{6}10^6$ ，可知当 $aa$ 固定时， $bb$ 增大， $XX$ 也增大（ $bb$ 亦同理），即 $XX$ 单调递增，所以我们固定 $aa$ ，二分求满足 $XX$ 大于 $NN$ 的最小的 $bb$ 即可，答案为最小的 $XX$

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1000000;

LL f(LL a, LL b)
{
    return a * a * a + a * a * b + a * b * b + b * b * b;
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
    LL n;
    cin >> n;
    
    LL x = 1e18;
    for (int a = 0;a <= N;a ++)
    {
        int l = 0, r = N;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (f(a, mid) >= n) r = mid;
            else l = mid + 1;
        }
        x = min(x, f(a, l));
    }
    
    cout << x;
	
	return 0;
}

E - Bishop 2

题意：

$N\times NN\; \backslash times\; N$ 的棋盘上有若干障碍物，求棋子从 $(A_x,A_y)(A\_x,\; A\_y)$ 到 $(B_x,B_y)(B\_x,\; B\_y)$ 的最短步数。已知棋子只能斜着走，每步距离不限，但路径和终点上不能有障碍物

分析：

首先可知若起点和终点坐标相加为奇数，则一定不可能成功，靠这个特判相当于能剪一下枝，而且相加为偶数的也不全能成功。我们用 $bfsbfs$ 搜索全图的所有位置，先从起点开始，起点的左上、左下、右上、右下的点在遇到障碍物之前全为 $11$ ，搜索完起点后，再从队列里继续搜索，重复的点不必再搜，直到搜索到终点的值为之，若最后都没有搜索到终点，则输出 $-1-1$

代码：

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1510;

char s[N][N];
int d[N][N];
bool v[N][N];
queue<PII> q;

int dx[4] = {1, -1, 1, -1}, dy[4] = {1, 1, -1, -1};

int main()
{
    memset(d, -1, sizeof d);
    
    int n, sx, sy, ex, ey;
    scanf("%d%d%d%d%d", &n, &sx, &sy, &ex, &ey);
    
    if (sx + sy + ex + ey & 1)
    {
        cout << -1;
        return 0;
    }
    
    for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    
    d[sx][sy] = 0;
    q.push({sx, sy});
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        if (t.x == ex && t.y == ey)
        {
            printf("%d", d[ex][ey]);
            return 0;
        }
        v[t.x][t.y] = 1;
        for(int u = 0; u < 4; u++)
        {
            PII st = {t.x + dx[u], t.y + dy[u]};
            while (true)
            {
                if (st.x <= 0 || st.x > n || st.y <= 0 || st.y > n || s[st.x][st.y] == '#' || v[st.x][st.y]) 
                    break;
                if (d[st.x][st.y] != -1) 
                {
                    st.x += dx[u];
                    st.y += dy[u];    
                    continue;
                }
                d[st.x][st.y] = d[t.x][t.y] + 1;
                q.push(st);
                st.x += dx[u];
                st.y += dy[u];
            }
        }
    }
    printf("%d", -1);
    
    return 0;
}