菜死了，被czn踩了8分暴力分
水分没水到/kk
整体第四，初二第一，竞赛班第二
主要是切了T4翻盘的
T1 祖先 ABC263B
一道简单的DP，随便做做跑路了
代码长这样
#include <stdio.h>
int n, x, f[55];
int main() {
scanf("%lld", &n);
for (int i = 2; i <= n; i++) {
scanf("%lld", &x);
f[i] = f[x] + 1;
}
printf("%lld", f[n]);
}
为了拿最快写了C语言
我不理解网上的代码为什么都是建树+DFS，又慢，又长，空间又大，又难想，数据一大可能还卡掉了
这里鞭尸Binbin的代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;
int n;
int f[maxn];
bool vis[maxn];
vector<int> sons[maxn];
void dfs(int x, int y) {
vis[x] = true;
if (x == n) {
printf("%d", y);
exit(0);
}
for (int i = 0; i < sons[x].size(); i++) {
if (!vis[sons[x][i]])
dfs(sons[x][i], y + 1);
}
}
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
scanf("%d", &f[i]);
sons[f[i]].push_back(i);
}
dfs(1, 0);
}
还有Vicky，这位更是重量级
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
ll z = 0, ju = 1;
char a = getchar();
while (a > '9' || a < '0') {
if (a == '-')
ju = -1;
a = getchar();
}
while (a >= '0' && a <= '9') {
z = (z << 1) + (z << 3) + a - '0';
a = getchar();
}
return z * ju;
}
inline void pr(ll a) {
if (a < 0) {
a *= -1;
putchar('-');
}
if (a > 9) {
pr(a / 10);
putchar(a % 10 + '0');
} else
putchar(a + '0');
}
ll fa[10004], z, ans;
int main() {
z = read();
for (int i = 2; i <= z; i++) {
ll aa = read();
fa[i] = aa;
}
fa[1] = 1;
ll i = z;
while (fa[i] != i) ++ans, i = fa[i];
pr(ans);
return 0;
}
deer也没能逃过一劫
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50;
int n;
int p[maxn + 5];
int work(int x) {
if (x == 1)
return 0;
else
return work(p[x]) + 1;
}
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) scanf("%d", &p[i]);
printf("%d", work(n));
return 0;
}
无语......
我寻思今天也不是反转日啊，平时不是我写粪代码吗......
没有嘲讽之意，只是在此提醒自己
- 在比赛中，代码能过就行
- 不要想复杂，正解通常是短而美的
- 我是蒟蒻，人家打暴力都打完了，我还在看题！
T2 严格上升子序列 ABC263C
正解怎么做？暴力对不对？暴力！暴力！暴力！
（加边！加边！加边！）
#include <stdio.h>
int n, m, a[15];
void dfs(int x, int y) {
if (x > n) {
for (int i = 1; i <= n; i++) printf("%lld ", a[i]);
printf("\n");
return;
}
if (y > m)
return;
for (int i = y; i <= m; i++) {
a[x] = i;
dfs(x + 1, i + 1);
}
}
int main() {
scanf("%lld%lld", &n, &m);
dfs(1, 1);
}
T3 头尾操作 ABC263D
反转了，今天不是反转日
我要写粪代码了
首先整三种情况 ：全部不动，全部 ,全部
接下来我们想一想，两个区间可能接触吗
答案是否，因为让占领全局比它好
所以中间是至少有一个空的
枚举空的位置，预处理两端最优解即可
#include <bits/stdc++.h>
using namespace std;
long long n, l, r, mn, a[200005], lm[200005], rm[200005], sum[200005];
long long minn(long long x, long long y) {
if (x > y)
return y;
return x;
}
int main() {
scanf("%lld%lld%lld", &n, &l, &r);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i];
}
mn = minn(sum[n], minn(l * n, r * n));
for (int i = 1; i <= n; i++) {
if (l * i <= (lm[i - 1]) * l + sum[i] - sum[lm[i - 1]]) {
lm[i] = i;
} else {
lm[i] = lm[i - 1];
}
// cout<<lm[i]<<' ';
}
// cout<<endl;
rm[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
if (r * (n - i + 1) <= (n - rm[i + 1] + 1) * r + sum[rm[i + 1] - 1] - sum[i - 1]) {
rm[i] = i;
} else {
rm[i] = rm[i + 1];
}
// cout<<rm[i]<<' ';
}
// cout<<endl;
for (int i = 1; i <= n; i++) {
mn = minn(mn, (lm[i - 1]) * l + (n - rm[i + 1] + 1) * r + sum[rm[i + 1] - 1] - sum[lm[i - 1]]);
// cout<<(lm[i-1])*l+(n-rm[i+1]+1)*r+sum[rm[i+1]-1]-sum[lm[i-1]]<<' ';
}
printf("%lld", mn);
}
T4 掷骰子 ABC263E
简单期望DP
其中可以变形
来个前缀和就可以了
总结
还行
