PAT (Advanced Level) Practice 代码
分类:
IT文章
•
2024-01-05 13:40:30
1,A+B Format
先用取余的方法将和逆序存在数组a中,并在该过程中每隔三位数就将-10086存在数组a中,以用来标记逗号应该出现的位置,最后逆序输出就可以了。需要注意0的特判就可以了。
#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<stdio.h>
#define N 10
int a[N], b[N];
int abs(int a)
{
return a > 0 ? a : -a;
}
int main(void)
{
int x, y; scanf("%d%d", &x, &y);
int sum = x + y;
int t = abs(sum);
int j = 0, jj = 0;
while (t)
{
if (jj % 3 == 0 && jj != 0)
a[j++] = -10086;
a[j] = t % 10;
j++, jj++;
t /= 10;
}
if (sum == 0)
printf("0
");
else
{
if (sum < 0)
printf("-");
for (int i = j - 1; i >= 0; i--)
{
if (a[i] == -10086)
{
printf(",");
continue;
}
printf("%d", a[i]);
}puts("");
}
system("pause");
return 0;
}
View Code
2,A+B for Polynomials
每一行代表一个多项式,其中第一个数k代表多项式的项数,该行接下来有k对数,每一对有两个数,分别是该项指数a和系数b。
设数组 coe[i] 为系数为 i 的项的系数。所以,只需让 coe[a]+=b 即可求得答案。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define N 1005
double coe[N];
int main(void)
{
int n, max = 0;
for (int i = 0; i < 2; i++)
{
scanf("%d", &n);
for (int j = 0; j < n; j++)
{
int x; double y;
scanf("%d%lf", &x, &y);
coe[x] += y;
max = max > x ? max : x;
}
}
int cnt = 0;
for (int i = 0; i <= max; i++)
if (coe[i])
cnt++;
printf("%d", cnt);
for (int i = max; i >= 0; i--)
if (coe[i])
printf(" %d %.1lf", i, coe[i]);
puts("");
system("pause");
return 0;
}
View Code
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 505
#define inf 0x3f3f3f3f
struct Chain_forward_star
{
int tot, last[N];
struct Edge {
int pre, to, w;
}e[N*N];
void init()
{
tot = 0;
memset(last, -1, sizeof(last));
}
void add(int from, int to, int w)
{
tot++;
e[tot].to = to;
e[tot].w = w;
e[tot].pre = last[from];
last[from] = tot;
}
}star;
int dis[N], vis[N];
int num[N]; // 每个点的救援队数量
int cnt1[N]; // 源点到点i 的最短路径条数
int cnt2[N]; // 源点到点i 的最大救援队数量
void dij(int s, int n)
{
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
memset(cnt1, 0, sizeof(cnt1));
memset(cnt2, 0, sizeof(cnt2));
dis[s] = 0; vis[s] = 1;
cnt1[s] = 1;
cnt2[s] = num[s];
int m = n - 1;
while (m--)
{
for (int i = star.last[s]; ~i; i = star.e[i].pre)
{
int to = star.e[i].to;
int w = star.e[i].w;
if (!vis[to])
{
if (dis[s] + w < dis[to])
{
dis[to] = dis[s] + w;
cnt1[to] = cnt1[s];
cnt2[to] = cnt2[s] + num[to];
}
else if (dis[s] + w == dis[to])
{
cnt1[to] += cnt1[s];
if (cnt2[s] + num[to] > cnt2[to])
cnt2[to] = cnt2[s] + num[to];
}
}
}
int min = inf;
for (int i = 0; i < n; i++)
{
if (!vis[i] && dis[i] < min)
{
min = dis[i];
s = i;
}
}
vis[s] = 1;
}
}
int main(void)
{
int n, m, s, e;
while (scanf("%d%d%d%d", &n, &m, &s, &e) != EOF)
{
star.init();
for (int i = 0; i < n; i++)
scanf("%d", &num[i]);
for (int i = 0; i < m; i++)
{
int u, v, w; scanf("%d%d%d", &u, &v, &w);
star.add(u, v, w);
if (u != v)
star.add(v, u, w);
}
dij(s, n);
printf("%d %d
", cnt1[e], cnt2[e]);
}
return 0;
}