题目链接:http://www.cspoi.net/problem/4003
题意xy 平面上有一个边平行于 x 轴和 y 轴的矩形。已知其中三个顶点,求出另外一个顶点 (x4,y4)。
题解矩形的边平行于坐标轴,问题转化为 x1,x2,x3 中出现次数为 1 次的数为多少, y1,y2,y3 中出现次数为 1 次的数为多少。把 x,y 分别异或起来输出即可。时间复杂度 O(1)。
Code:
#include <iostream>
#include <cstdio>
int x, y, ansx, ansy;
int main()
{
for (int i = 0; i < 3; i ++ )
{
scanf("%d%d", &x, &y);
ansx ^= x, ansy ^= y;
}
printf("%d %d\n", ansx, ansy);
return 0;
}
题目链接:http://www.cspoi.net/problem/4004
题意给出 A 和 B,求出 (0, 0) 向 (A, B) 前进 1 个单位后的坐标。
题解设 (0, 0) 到 (A, B) 的距离是 d,那么答案就是 (\frac{A}{d}, \frac{B}{d});根据两点坐标距离公式,得 d = \sqrt{A^2 + B^2},输出求出的数字即可。
Code:
#include <iostream>
#include <cmath>
#include <algorithm>
int main()
{
double x, y;
scanf("%lf%lf", &x, &y);
double t = std::sqrt(x * x + y * y);
printf("%.12lf %.12lf\n", x / t, y / t);
return 0;
}
题目链接:http://www.cspoi.net/problem/4005
题意有 n 个商品,每个商品的价格为 a_i。有 k 张优惠券,每张优惠券可以让某个商品的价格降低 x。即商品原价为 a,使用 k 张优惠券后,商品的现价为 \max\{a−kx,0\}。求使用优惠券买下所有商品所需要的价格。
题解考虑贪心,先对所有物品尽可能多的使用代金券,让这些优惠券能抵扣的价格等于其面值。如果还剩余一些代金券,将剩余的面额从大到小排序,依次使用,这样的贪心策略可以使代金券降低的价格最大。时间复杂度为 O(n \log n)。
Code:
#include <iostream>
#include <cmath>
#include <algorithm>
const int N = 2e5 + 10;
int a[N];
int main()
{
int n, k, x;
scanf("%d%d%d", &n, &k, &x);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
int t = std::min(a[i] / x, k);
k -= t;
a[i] -= t * x;
}
std::sort(a + 1, a + 1 + n, std::greater<int> ());
long long ans = 0;
for (int i = k + 1; i <= n; i ++ )
ans += a[i];
printf("%lld", ans);
return 0;
}
题目链接:http://www.cspoi.net/problem/4006
题意设 f(a,b) = a^3 + a^2*b + a*b^2 + b^3。给出一个正整数 N,找到最小的 X,满足 X \geq N 且 X = f(a,b)。
题解考虑从小到大枚举 a,在 f(a,b) \geq n 的条件下,最小的 b 一定有单调不升的特性,满足双指针的条件,所以可用双指针解决本题,时间复杂度 O(可过)。
Code:
#include <iostream>
#include <cmath>
#include <algorithm>
long long n, ans = 0x3f3f3f3f3f3f3f3f;
long long f(long long a, long long b)
{
return (a * a * a + b * b * b + a * a * b + b * b * a);
}
int main()
{
scanf("%lld", &n);
for (long long i = 0, j = 1e6; i <= 1e6; i ++ )
while (f(i, j) >= n && j >= 0)
{
ans = std::min(ans, f(i, j));
j -- ;
}
printf("%lld\n", ans);
return 0;
}
题目链接:http://www.cspoi.net/problem/4007
题意有一个 n \times n 的棋盘,能走的地方为 . 不能走的地方为 #,从 (i, j) 出发可一步到达对角线上的任意一个之间无 # 的点。求从 (A_x, A_y) 到达 (B_x, B_y) 的最少步数。
题解
时限 6s,直接 BFS
,每次更新四个方向,能走多远走多远,如果遇到不能更新的地方就直接 break 掉。