IT评测·应用市场-qidao123.com技术社区

标题: 【补题/atccoder】Toyota Programming Contest 2024#7（AtCoder Beginner C [打印本页]

作者: 兜兜零元 时间: 2024-11-4 10:34
标题: 【补题/atccoder】Toyota Programming Contest 2024#7（AtCoder Beginner C
A、买笔

思路：
  输入红绿蓝三只笔价格，再输入不喜欢颜色，
  输出除不喜欢颜色笔以外最低价格
  代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int r, g, b;
cin >> r >> g >> b;
string s;
cin >> s;
if (s == "Red")
{
if (g < b) cout << g;
else cout << b;
}
else if (s == "Green")
{
if (r < b)cout << r;
else cout << b;
}
else if (s == "Blue")
{
if (r < g)cout << r;
else cout << g;
}
return 0;
}

复制代码

B、判断是否为直角三角形

题目本质：
给定不共线的三点，判断他们是否可以形成直角三角形。
注意：必要用long long范例。

#include<iostream>
#include <cmath>
using namespace std;
int main() {
int a1, a2, b1, b2, c1, c2;
cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2;
int ab = abs(a1 - b1) * abs(a1 - b1) + abs(a2 - b2) * abs(a2 - b2);
int ac = abs(a1 - c1) * abs(a1 - c1) + abs(a2 - c2) * abs(a2 - c2);
int bc = abs(c1 - b1) * abs(c1 - b1) + abs(c2 - b2) * abs(c2 - b2);
if (ab + ac == bc || ab + bc == ac || ac + bc == ab) cout << "Yes";
else cout << "No";
return 0;
}

复制代码

C、和值为0

数据输入/输出
样例1：
  输入：
  3
3 5
-4 1
-2 3
输出：
  Yes
4 -3 -1 （结果不唯一）

  样例2：
  输入：
  3
1 2
1 2
1 2
输出：
  No
题目本质：
  给定L，X，R三个数组，已知L，R的数据，而且L <= X <= R。
  思路：
  设s_min为L的和，s_max为R的总和，当s_min大于0大概s_max小于0，不大概存在
  然后我们给X初始化为L，此时X的和为s（等于s_min），然后用dif 存下（R - L，-s）的较小值。
  当s<0时，则dif则增长X，间接增长s的值
  当 s >0，则dif则减少X，间接减少s的值

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
LL s_min, s_max;
int main()
{
int n;
cin >> n;
vector<int> L(n), R(n), X(n);
for (int i = 0; i < n; i++)
{
cin >> L[i] >> R[i];
s_min += L[i];
s_max += R[i];
}

if (s_min > 0 || s_max < 0) cout << "No" << "\n";
else
{
cout << "Yes" << "\n";
for (int i = 0; i < n; i++) X[i] = L[i]; //给x先赋初值
LL s = s_min; //s一定为负数
for (int i = 0; i < n; i++) {
if (s == 0) break;
//由于R[i] - L[i] >=0
//s为负数，X[i]增加，那么s也增加
LL dif = min((LL)R[i] - L[i], -s);
X[i] += dif;
s += dif;
}
for (int i = 0; i < n; i++)cout << X[i] << " ";
}
return 0;
}
复制代码
D、最短路径

样例1输入：
  3 3
1 2 3
1 2 1
1 3 6
2 3 2
输出：4 9

  样例2输入：
  2 1
0 1
1 2 3
输出：4

  样例3输入：
  5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403
输出：2832044198 2824130042 4696218483 2805069468
题目本质就是给定n个点，m条边，
  先输入每个点的自身权值，然后再输入m条边的权值。输入时不大概输入同一边的不同权值
  如样例一中，1到2的最小权值为 1 + 1 + 2 = 4；
  1到3的最小权值为 4 + 3 + 2 = 9；
  ’思路：
  可以用better_dijkstra()来写，

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
typedef pair<ll, int> PII; //权值和终点
ll dist[N], a[N];// 存储1号点到每个点的最短距离,每个点自身权值
int n, m;
struct Node {
int y, val; //终点和权值
};
vector<Node> f[N];
void  better_dijkatra(int st)
{
memset(dist, 0x3f3f, sizeof dist);
priority_queue<PII, vector<PII>, greater<PII>> q;
dist[st] = a[st];
q.push({ dist[st],st });
while (!q.empty())
{
ll d = q.top().first, u = q.top().second; //终点和权值
q.pop();
if (d > dist[u]) continue;
for (auto edge : f[u]) //遍历当前终点所连接的边
{
ll v = edge.y, val = edge.val;
if (dist[u] + val + a[v] < dist[v])
{
         //当前两点的权值等于边权+之前最短点权值，加终点自身权值
dist[v] = dist[u] + val + a[v];
q.push({ dist[v], v });
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)  cin >> a[i];
while (m--)
{
int u, v, b;
cin >> u >> v >> b;
f[u].push_back({ v,b });
f[v].push_back({ u,b });
}
better_dijkatra(1); //从1号点开始
for (int i = 2; i <= n; i++) cout << dist[i] << " ";
return 0;
}
复制代码
E、盘算算术子序列的数量

样例1输入：
  5
1 2 3 2 3
  输出：5 10 3 0 0

  样例2输入：
  4
1 2 3 4
  输出：4 6 2 1

  样例3输入：
  1
100
  输出：1
题目本质：
  相称于对于n个数字，输出长度为i（1<=i<=n）的子序列个数，对于子序列要求其相应次序不变，好比样例1中
  长度为1的子序列：（1）、（2）、（3）、（4）、（5）
  长度为2的子序列：长度为2的子序列都是算术子序列
  长度为3的子序列：（1，2，3）、（1，2，5）、（1，4，5）
  长度为4的子序列：0
  长度为5的子序列：0
  注意：
  子序列：是通过从原序列删除零个或多个元素并在不改变次序的情况下分列其余元素而获得的序列
  算术序列：是一个数字列表，其中的一连项相差一个常数，即共同的差（也就是雷同于等差数列）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 85, M = 998244353;
ll n, a[N], f[N][N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++)
f[i][j][2] = 1; //初始化
}
cout << n << ' ';
ll ans = 0;
for (int l = 2; l <= n; l++) {
ll as = 0;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
for (int k = 1; k < j; k++) {
if (a[i] - a[j] == a[j] - a[k]) {
f[i][j][l] += f[j][k][l - 1];
f[i][j][l] %= M;
}
}
as += f[i][j][l], as %= M;
}
}
cout << as << ' ';
//ans += as;
}
//cout << ans << "\n";
return 0;
}
复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4