这次拿的暴力分，让我觉得是考的最好的一次 QAQ
考试
直角三角形
考试的时候想了 20 分钟，想不出来，打了个暴力交了，60 分（用 cin 40分 哈哈哈哈哈哈）
这题其实可以卡常，加上读入优化，输出优化，register ，可以跑到 70 分。估计加个 $O2$ 还可以更快，不过这在考试中当然是不可取的。
这题某位 $dalao$ 不加优化满分，太强了！
正解有三种：
- 固定直角顶点，固定另外一个顶点，然后算这两点所连直线的解析式，然后算出垂直于该直线的解析式，然后看看有多少个点在这一条直线上，用数据结构维护进行优化，否则时间复杂度很高。
- 极角排序，不知道是什么东西 qwq
- 固定一个点，然后平移整个坐标系，枚举象限中的每一个点，旋转 $k \times 90°$ 角到第一象限，然后计算该点到原点的斜率，然后对于其他每一个点，计算斜率后排序。斜率相同且象限符合情况时，算入答案。
三个正解复杂度都是 $O(n^2 \log n)$ ，难怪 $O(n^3)$ 吸氧气可以跑满分 qwq
感谢 @znh 的翻译！
$Test's$ $Code$：60%
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 1505;
struct Node {
int x, y;
};
Node p[MAXN];
int n, ans;
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d%d", &p[i].x, &p[i].y);
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = j + 1; k <= n; k++) {
int a = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
int b = (p[j].x - p[k].x) * (p[j].x - p[k].x) + (p[j].y - p[k].y) * (p[j].y - p[k].y);
int c = (p[i].x - p[k].x) * (p[i].x - p[k].x) + (p[i].y - p[k].y) * (p[i].y - p[k].y);
if (a + b == c || a + c == b || b + c == a) {
ans++;
}
}
}
}
printf ("%d\n", ans);
return 0;
}
排序
这题好像跟逆序对有关，应该可以用 $dp$ ，不过我就直接模拟求逆序对了，70 分 QAQ
正解不是 $dp$ ，在求答案的过程中其实可以使用数据结构维护，最简单的树状数组就可以了。只要在读取数据的时候用一下插入，每次把一个数归位以后就删掉这个数，然后再查询在需要移动的方向上，有几个数挡在路上。
时间复杂度 $O(n \log n)$
$Test's$ $Code$：70%
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1e5+5;
const int INF = 2e9;
int f[MAXN], n, a[MAXN], num[MAXN];
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d", &a[i]);
num[i] = a[i];
}
sort (num + 1, num + n + 1);
num[n + 1] = INF;
for (int i = 1; i <= n; i++) {
if (n % 2 == 1 && i == n / 2 + 1) {
f[i] = 0;
continue;
}
if (i <= n / 2) {
for (int j = 1; j <= n; j++) {
if (a[j] == num[i]) break;
if (a[j] > num[i] && a[j] < num[n - i + 2]) {
f[i]++;
}
}
}
else {
for (int j = n; j >= 1; j--) {
if (a[j] == num[i]) break;
if (a[j] < num[i] && a[j] > num[n - i + 1]) {
f[i]++;
}
}
}
}
for (int i = 1; i <= n / 2; i++) {
printf ("%d\n", f[i]);
printf ("%d\n", f[n - i + 1]);
}
if (n % 2 == 1) {
printf ("%d\n", f[n / 2 + 1]);
}
return 0;
}$Fixed$ $Code$：100%
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e5 + 5;
int n, a[MAXN], num[MAXN];
int c[MAXN];
inline int lowbit (int x) {
return x & (-x);
}
inline void Add (int i, int num) {
while (i <= n) {
c[i] += num;
i += lowbit (i);
}
return;
}
inline int Sum (int i) {
int ans = 0;
while (i > 0) {
ans += c[i];
i -= lowbit (i);
}
return ans;
}
inline int Query (int l, int r) {
return Sum (r) - Sum (l - 1);
}
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d",&a[i]);
Add(i, 1);
num[a[i]] = i;
}
int Min = 1, Max = n;
for (int i = 1; i <= n; i++) {
if (i % 2 == 1) {
Add (num[Min], -1);
printf ("%d\n", Query (1, num[Min]));
Min++;
}
else {
Add (num[Max], -1);
printf ("%d\n", Query (num[Max], n));
Max--;
}
}
return 0;
}自行车比赛
考试的时候直接跳过了，最后输出样例，不知道多少分 QAQ。现在知道了，当然没有分啦~
小 L 的数列
直接模拟 30 分，后面加了个快速幂，不知道多少分 QAQ。有 50 分，非常感动，嘤嘤嘤~
正解使用矩阵快速幂，首先先把矩阵推出来。对于原始 $k = 5$ 的矩阵，有：
$$ f[1] = f[1]^1 \quad f[2] = f[2]^1 \quad f[3] = f[3]^1 \quad f[4] = f[4]^1 \quad f[5] = f[5]^1 $$
所以 $f[1..k]$ 的原始 指数 矩阵为：
$$ \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$
然后就可以推出 $f[2.. k+1]$ 的矩阵：
$$ \begin{bmatrix} 0 & 0 & 0 & 0 & b[5] \\ 1 & 0 & 0 & 0 & b[4] \\ 0 & 1 & 0 & 0 & b[3] \\ 0 & 0 & 1 & 0 & b[2] \\ 0 & 0 & 0 & 1 & b[1] \end{bmatrix} $$
$Test's$ $Code$：50%
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 4e7 + 5;
const int MAXK = 2e2 + 5;
const int Mod = 998244353;
long long f[MAXN];
int b[MAXK], n, k;
long long Pow (long long a, int x) {
if (x == 1) return a;
long long ans = 1;
long long temp = Pow (a, x>>1) % Mod;
ans = (temp * temp) % Mod;
if (x % 2 == 1) {
ans = (ans * a) % Mod;
}
return ans;
}
int main() {
freopen ("seq.in", "r", stdin);
freopen ("seq.out", "w", stdout);
scanf ("%d%d", &n, &k);
for (int i = 1; i <= k; i++) {
scanf ("%d", &b[i]);
}
for (int i = 1; i <= k; i++) {
scanf ("%lld", &f[i]);
}
int i = k + 1;
while (i <= n) {
int cnt = 0;
f[i] = 1;
for (int j = i - 1; j >= i - k; j--) {
long long s = 1;
cnt++;
s = Pow (f[j], b[cnt]);
f[i] = (f[i] * s) % Mod;
}
i++;
}
printf ("%lld\n", f[n]);
fclose (stdin);
fclose (stdout);
return 0;
}本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/75/
最后修改时间：2020-04-13 11:41:52
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！