CSP认证-现值计算、训练计划、JPEG 解码、聚集方差
T1现值计算
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n;
double rate;
cin >> n >> rate;
double t = 1.0, x, res = 0;
for (int i = 1; i <= n + 1; ++i) {
scanf("%lf", &x);
res += t * x;
t *= 1.0 / (1 + rate);
}
printf("%lf\n", res);
return 0;
}
T2训练计划
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int p[N], t[N], level[N], idx[N], res1[N], res2[N];
bool is_leaf[N];
int main()
{
freopen("a.in", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) scanf("%d", &p[i]), idx[i] = i, is_leaf[i] = true;
for (int i = 1; i <= m; ++i) scanf("%d", &t[i]);
// m^2
for (int i = 1; i <= m; ++i) {
int j = p[i];
while (j) level[i]++, j = p[j];
}
// 拓扑 + 时间大到小
sort(idx + 1, idx + 1 + m, [&](int i, int j) {
return level[i] < level[j];
});
// 计算最早开始的时间,只需满足拓扑
for (int i = 1; i <= m; ++i) {
int j = idx[i];
if (p[j]) res1[j] += (t[p[j]] + res1[p[j]]);
else res1[j] = 1;
}
int ft = 0;
for (int i = 1; i <= m; ++i) {
printf("%d ", res1[i]);
ft = max(ft, res1[i] + t[i] - 1);
}
printf("\n");
if (ft > n) return 0;
// 计算最晚开始时间
else {
memset(res2, 0x3f, sizeof res2);
for (int i = m; i >= 1; --i) {
int id = idx[i], pid = p[id];
if (is_leaf[id]) res2[id] = n - t[id] + 1;
if (pid) {
is_leaf[pid] = false;
res2[pid] = min(res2[id] - t[pid], res2[pid]);
}
}
for (int i = 1; i <= m; ++i) {
printf("%d ", res2[i]);
}
return 0;
}
}
T3JPEG 解码
#include <bits/stdc++.h>
using namespace std;
#define PI acos(-1)
#define qrt sqrt(1.0 / 2.0)
int Q[10][10], mat[10][10];
double Q_2[10][10];
int n, T, row = 1, col = 1, cur = 0, nxt = 1;
void in_mat()
{
for (int i = 1; i <= 8; ++i) {
for (int j = 1; j <= 8; ++j) {
scanf("%d", &Q[i][j]);
}
}
scanf("%d%d", &n, &T);
for (int i = 1; i <= n; ++i) {
if (i < 36) {
if (nxt % 2) scanf("%d", &mat[row--][col++]);
else scanf("%d", &mat[row++][col--]);
++cur;
if (cur == nxt) {
cur = 0;
nxt++;
if (nxt % 2) row = nxt, col = 1;
else row = 1, col = nxt;
}
}
else if (i == 36) {
scanf("%d", &mat[row][col]);
cur = 0;
nxt = 7;
row = 8, col = 2;
}
else {
if (nxt % 2) scanf("%d", &mat[row--][col++]);
else scanf("%d", &mat[row++][col--]);
++cur;
if (cur == nxt) {
cur = 0;
nxt--;
if (nxt % 2) row = 8, col = 8 - nxt + 1;
else row = 8 - nxt + 1, col = 8;
}
}
}
}
void plus_mat()
{
for (int i = 1; i <= 8; ++i) {
for (int j = 1; j <= 8; ++j) {
mat[i][j] *= Q[i][j];
}
}
}
void DCT(int m[10][10], double res[10][10])
{
double au, av;
for (int i = 1; i <= 8; ++i) {
for (int j = 1; j <= 8; ++j) {
double t = 0;
for (int u = 0; u <= 7; ++u) {
if (u == 0) au = qrt;
else au = 1;
for (int v = 0; v <= 7; ++v) {
if (v == 0) av = qrt;
else av = 1;
t += 1.0 / 4.0 * au * av * m[u + 1][v + 1] * cos(PI / 8 * (i - 1 + 1.0 / 2) * u)
* cos(PI / 8 * (j - 1 + 1.0 / 2) * v);
}
}
res[i][j] = t;
}
}
for (int i = 1; i <= 8; ++i) {
for (int j = 1; j <= 8; ++j) {
int t = round(res[i][j] + 128);
if (t > 255) t = 255;
else if (t < 0) t = 0;
printf("%d ", t);
}
printf("\n");
}
}
void out_mat()
{
for (int i = 1; i <= 8; ++i) {
for (int j = 1; j <= 8; ++j) {
printf("%d ", mat[i][j]);
}
printf("\n");
}
}
int main()
{
freopen("a.in", "r", stdin);
in_mat();
if (T == 0) {
out_mat();
}
else if (T == 1) {
plus_mat();
out_mat();
}
else {
plus_mat();
DCT(mat, Q_2);
}
return 0;
}
T4聚集方差
65分解法如下:文章来源地址https://www.toymoban.com/news/detail-518501.html
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300100;
int h[N], e[N], ne[N], a[N], idx;
LL ans[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 合并两个有序数组O(n)
void merge(vector<int>& dest, vector<int>& v)
{
vector<int> v3(dest.size() + v.size());
if (dest.empty()) dest = v;
else {
int p1 = 0, p2 = 0, i = 0;
while (p1 != dest.size() && p2 != v.size()) {
if (dest[p1] < v[p2]) v3[i++] = dest[p1++];
else v3[i++] = v[p2++];
}
if (p1 == dest.size()) {
while(p2 != v.size())
v3[i++] = v[p2++];
}
else{
while (p1 != dest.size())
v3[i++] = dest[p1++];
}
}
dest = v3;
}
LL calc(vector<int>& v)
{
int n = v.size();
if (n == 1) return LL(0);
LL res = 0;
for (int i = 0; i < n; ++i) {
int min_dis = 2e9;
if (i - 1 >= 0)
min_dis = abs(v[i - 1] - v[i]);
if (i + 1 < n)
min_dis = min(min_dis, abs(v[i + 1]) - v[i]);
res += (LL)min_dis * min_dis;
}
return res;
}
vector<int> dfs(int u)
{
vector<int> res;
res.push_back(a[u]);
for (int i = h[u]; ~i; i = ne[i]) {
vector<int> t = dfs(e[i]);
merge(res, t);
}
ans[u] = calc(res);
return res;
}
int main()
{
int n, pp;
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 2; i <= n; ++i) {
scanf("%d", &pp);
add(pp, i);
}
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
dfs(1);
for (int i = 1; i <= n; ++i) {
printf("%lld\n", ans[i]);
}
return 0;
}
博主原创,转载注明出处
文章来源:https://www.toymoban.com/news/detail-518501.html
到了这里,关于CSP认证-现值计算、训练计划、JPEG 解码、聚集方差的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!