很遗憾，本次比赛只有 dingmohan 一人参加 (有些人估计是英文看不懂)，得分为200。本来打算Rated的，但由于人数过少就不计算积分了。这场比赛我觉得难度不算很大，除T1外其他题比去年的CSP略简单（2019年CSP第一题估计是历年来最水的一次），只要编程能力还可以，得到200分还是很容易的。为了起到提升同学们编程能力的效果，良心的出题人将每题的数据设成多组，防止无意义骗分。
T1: Contest Ranking (contest)
题目描述
John老师喜欢让学生考试，一共有 名学生，考试前每个人有一个分数 。John认为每个学生的排名值应该是 =1+比他(她)分数高的学生数。由于学生较多，现在帮助John老师计算一下，考试后所有学生的排名值。
输入格式
第一行为正整数 ，表示数据组数；每组数据中，第一行为正整数 ，
第二行为以空格隔开的 个分数 。
输出格式
对于每组数据，输出这场考试之后的排名分值，仍然按照输入顺序。
分析
这题其实就一个模拟+结构体排序，需要注意的是这题 的数据范围 ，所以 会超时。
考虑到这是第一题，所以我给的数据 还是可以得到70pts的。
下面是 的代码 (70pts)：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[10005],b[10005];
int main() {
freopen("contest.in","r",stdin);
freopen("contest.out","w",stdout);
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
for(int i=1; i<=n; i++) {
int score_up=0;
for(int j=1; j<=n; j++) {
if(a[j]>a[i]) {
score_up++;
}
}
b[i]=score_up+1;
}
for(int i=1; i<=n; i++) {
cout<<b[i]<<" ";
}
cout<<endl;
}
return 0;
}
这是AC的代码 (100pts) :
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10005;
struct Node {
int v, id, rk;
} a[N];
bool cmpv(Node x, Node y) {
return x.v > y.v;
} //按分值降序排列
bool cmpid(Node x, Node y) {
return x.id < y.id;
} //再按id升序排列
void in(int &x) {
char c=getchar();
while (c<'0' || c>'9') c=getchar();
for (x=0; c>='0' && c<='9'; c=getchar())
x=x*10+c-'0';
}
int main() {
freopen("contest.in", "r", stdin);
freopen("contest.out", "w", stdout);
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i=0; i<n; i++) {
in(a[i].v);//scanf("%d", &a[i].v);
a[i].id=i;
}
sort(a, a+n, cmpv);
int cnt=2;
a[0].rk=1;
for (int i=1; i<n; ++i) {
if (a[i].v < a[i-1].v)
a[i].rk=cnt++;
else {
a[i].rk=a[i-1].rk;
cnt++;
}
}
sort(a, a+n, cmpid);
for (int i=0; i<n; ++i)
printf("%d ", a[i].rk);
printf("\n");
}
return 0;
}
T2: Lost number (wild)
题目描述
小强写了一个十进制数 ，但有些字迹已经模糊不清（我们以 ? 代替），现在给定另一个相同位数的十进制数 ，他想知道有多少种可能使得 。
输入格式
第一行为正整数 ，表示数据组数；每组数据中，第一行为一个16位以内的十进制数 ，当中有若干个 ?；
第二行为一个相同位数的十进制数。
输出格式
输出 的可能数。
分析
这是一道模拟题，首先统计 中 ? 的格式，之后对于 (十进制数字 的第 位) 和 (十进制数字 的第 位)，我们分4种情况讨论，分别是：?,<,>,=。
?: 加上之前种数<: 直接退出>: 加上当前种数，退出=: 继续
这是AC的代码 (100pts) :
#include <cstdio>
#include <cstring>
typedef long long ll;
ll p10[18]= {1};
int main() {
freopen("wild.in","r",stdin);
freopen("wild.out","w",stdout);
for (int i=1; i<18; i++)
p10[i]=p10[i-1]*10;
int t;
scanf("%d", &t);
while (t--) {
char s[20], v[20];
scanf("%s", s);
scanf("%s", v);
int n=strlen(s), w=0;
for (int i=0; i<n; i++)
if (s[i]=='?') w++;//统计?个数
ll ans=0ll;
for (int i=0; i<n; i++)//分四种情况：
if (s[i]=='?') //1、？
ans+=('9'-v[i])*p10[--w];
else if (s[i]<v[i])//2、<
break;
else if (s[i]>v[i]) { //3、>
ans+=p10[w];
break;
} //4、相等，继续
printf("%lld\n", ans);
}
return 0;
}
T3: Number of common subintervals (common)
题目描述
在 中给出区间集合 和 ，分别包含 个区间和 个区间，求出它们长度为 的公共子区间个数。注意，这里符合条件的公共子区间有 个点（包含起点和终点），其长度实际上是 ，且允许重叠，具体参看样例。
输入格式
第一行为正整数，表示数据组数；
每组数据中，第一行为正整数 ,,,；
接下来 行，每行两个正整数 ,，表示 个子区间的起点和终点；
接下来 行，每行两个正整数 , 表示 个子区间的起点和终点。其中，,,,。
数据保证 个子区间互相不交叉， 个子区间互相不交叉。
输出格式
对于每组数据，输出符合条件的公共子区间个数。
分析
先看样例解释：在样例1中，3个子区间为 ，2个子区间为；它们长度为3的公共子区间分别是，所以答案是3。
这是模拟题，先求出公共子区间，求长度为 的子区间个数即可。
像求公共子区间这类模板代码可以自行到OJ题库或Internet去找，这里不再阐述做法。
这是AC的代码 (100pts) :
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10005;
struct Node {
int st, ed;
} a[N], b[N];
bool cmp(Node p, Node q) {
return p.st < q.st;
}
void in(int &x) {
char c=getchar();
while (c<'0' || c>'9') c=getchar();
for (x=0; c>='0' && c<='9'; c=getchar())
x=x*10+c-'0';
}
int main() {
freopen("common.in", "r", stdin);
freopen("common.out", "w", stdout);
int t;
scanf("%d", &t);
while (t--) {
int n, m, x, y;
scanf("%d %d %d %d", &n, &m, &x, &y);
m--;
for (int i=0; i<x; i++)
in(a[i].st), in(a[i].ed);
for (int i=0; i<y; i++)
in(b[i].st), in(b[i].ed);
sort(a, a+x, cmp);
sort(b, b+y, cmp);
int ans=0, i=0, j=0;
while (i<x && j<y) {
if (b[j].st > a[i].ed) {
i++;
continue;
}
if (a[i].st > b[j].ed) {
j++;
continue;
}
int st=max(b[j].st, a[i].st);
int ed=min(b[j].ed, a[i].ed); //求出公共子区间
if (ed-st+1>m) ans+=ed-st+1-m;//再求长度为m的子区间个数
if (a[i].ed < b[j].ed) i++;
else if (a[i].ed == b[j].ed) i++, j++;
else j++;
}
printf("%d\n", ans);
}
return 0;
}
T4: Maximum profit (profit)
题目描述
有 个火车站，某连锁饭店要在火车站开饭店，但政府不允许它同时开在两个相连接的火车站，任意两个火车站有且只有一条路径。现在已知在每个火车站开饭店的利润，求这个连锁饭店的最大利润。
输入格式
第一行为正整数 ，表示数据组数；
每组数据中，第一行为正整数 ，表示火车站个数，编号从1到 ，
接下来 行，每行两个正整数 ,()，分别表示 和 火车站之间有一条直达路径，最后一行是 个正整数 ()，分别表示在每个火车站开饭店的利润。
输出格式
输出最大利润。
分析
算法树形DP，参考做法：深度优先搜索+链式前向星，详细见代码。
知识点回顾：图论之链式前向星
struct Edge {
int from,to,dis;//next下一条边的编号，to这条边到达的点，dis这条边的长度
} edge[maxm];
int head[maxm],num_edge,n,m,u,v,d;
void add_edge(int from,int to ,int dis) { //添加一条从from到to的距离为dis的单向边
edge[++num_edge].from=head[from];
edge[num_edge].to=to;
edge[num_edge].dis=dis;
head[from]=num_edge;
}
int main() {
num_edge=0;
cin>>n>>m;
for(i=1--m) {
cin>>u>>v>>d;
add_edge(u,v,d);
}
for(int i=head[1]; i; i=edge[i].from) {
u=edge[i].to;
}
}
其他图论模板代码可参考我的这篇博客或自行上网搜索。
下面是本题的AC代码 (100pts) :
#include <cstdio>
#include <cstring>
const int N=100010;
struct Edge {
int v, next;
} edge[2*N]; //边集数组
struct Head {
int first, w;
} head[N];
int pos, ans, n, f[N], g[N];
bool vis[N];
inline int mx(int a, int b) {
return a>b ? a : b;
}
void in(int &s) {
char c=getchar();
while (c<'0' || c>'9') c=getchar();
for (s=0; c>='0' && c<='9'; c=getchar())
s=s*10+c-'0';
}
void ins(int x, int y) {
pos++;
edge[pos].v=y;
edge[pos].next=head[x].first;
head[x].first=pos;
}
void dfs(int r) {
vis[r]=1;
f[r]=head[r].w, g[r]=0;
for (int k=head[r].first; k; k=edge[k].next) {
int v=edge[k].v;
if (!vis[v]) {
dfs(v);
f[r]+=g[v];
g[r]+=mx(f[v], g[v]);
}
}
ans=mx(ans, mx(f[r], g[r]));
}
int main() {
freopen("profit.in", "r", stdin);
freopen("profit.out", "w", stdout);
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
memset(vis, 0, sizeof(vis));
memset(head, 0, sizeof(head));
pos=0;
ans=-1;
int x, y;
for (int i=1; i<n; i++) {
in(x), in(y); //scanf("%d %d", &x, &y);
ins(x, y);
ins(y, x);
}
for (int i=1; i<=n; i++)
scanf("%d", &head[i].w);
dfs(1);
printf("%d\n", ans);
}
return 0;
}
- Solution Created By: wen
- Created Date：2020-10-24
共 3 条回复
+1
前排支持
前排支持