ccf-csp201909题解
标签： ccf题解
1. 201909-1 小明种苹果
题目描述
试题编号： 201909-1
试题名称： 小明种苹果
时间限制： 2.0s
内存限制： 512.0MB
解析
简单模拟题。
题中要求三个值，苹果的总数T，疏果最大值所在树的序号k，疏果最大值P。
维护T只要将输入从第二行开始所有数都相加即可，维护k和P只需维护输入每行第二个数开始加和的最小值即可。
通过代码
//1592771 <13100928923> <王恪楠> 小明种苹果 11-05 20:11 603B C0X 正确 100 796ms 540.0KB
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
int sum = 0, maxx = 0, id = 1; //sum就是T记录苹果的总数。maxx是f记录疏果最多的个数。id是P记录对应maxx的序号。
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++){
int t, sum0 = 0;
scanf("%d", &t);
sum += t;
for(int j = 1; j <= m; j ++){
scanf("%d", &t);
sum += t;
sum0 -= t;
}
if(sum0 > maxx){ //当发现有更大的疏果数时，不只更新maxx，还要更新序号id.
maxx = sum0;
id = i;
}
}
printf("%d %d %d", sum, id, maxx);
return 0;
}
2. 201909-2 小明种苹果（续）
题目描述
试题编号： 201909-2
试题名称： 小明种苹果（续）
时间限制： 1.0s
内存限制： 512.0MB
解析
比上一题的难度稍有增加。
- 加入了掉落的概念。
掉落：输入每行的值，第一个值为果树原有果子个数，之后的值为正数则为现在果树上的果子个数，非正数则为疏果掉落的个数。我们需要藉此来判断是否出现掉落情况（不包括疏果使其掉落）。则用变量now记录每行到每个位置的这棵果树的果子树。如果是非正数数，那么就now加上这个值(负数)，如果是正数，那么就用now和这个正数比一下大小，如果now比这个正数小，那么就说明这棵树出现了掉落情况，反之则无。用(vis[1 dots n])记录每棵树是否出现了掉落情况。
- 果树按圆种植。
一棵树的序号为(i)，则它左边的树序号为((i - 2 + n) \% n + 1)，右边的树序号为(\,i \,\% \, n + 1)。
题中要求的三个值，苹果的总数T，有掉落的果树个数D，连续三个果树都有掉落的情况个数E。
T可以通过每行最后变量now相加得到，每行如果出现了掉落情况则D++, E可以通过已经记录好的(vis[1 cdots n])数组循环一遍求得。
通过代码
//1586427 <13100928923> <王恪楠> 小明种苹果（续） 11-05 21:18 1.174KB C0X 正确 100 93ms 528.0KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 50;
int vis[MAXN];
inline int read() //快读，输入数据量较多，可以增加读入速度.
{
int res = 0, f = 1;
char ch;
ch = getchar();
while(!isdigit(ch)){
if(ch == '-')
f = -1;
ch = getchar();
}
while(isdigit(ch)){
res = (res << 3) + (res << 1) + ch - 48;
ch = getchar();
}
return f * res;
}
int main()
{
int n, sum = 0, cnt1 = 0, cnt2 = 0; //sum就是所求的T，cnt1就是所求的D，cnt2就是所求的E.
n = read();
for(int i = 1; i <= n; i ++){
int m, now = 0, flag = 0;
m = read();
for(int j = 1; j <= m;j ++){
int t;
t = read();
if(t > 0){
if(now > t){ //当now大于所出现的正数时，说明有果子掉落了.
vis[i] = 1;
flag = 1;
}
now = t;
}
else
now += t;
}
if(flag)
cnt1 ++;
sum += now; //维护sum的值.
}
for(int i = 1; i <= n; i ++){
if(vis[(i - 2 + n) % n + 1] && vis[i] && vis[i % n + 1]) //遍历所有的果树，如果它的左边果树，自己和右边果树都有下落情况，则cnt2++.
cnt2 ++;
}
printf("%d %d %d", sum, cnt1, cnt2);
return 0;
}
3. 201909-3 字符画
本题于这篇CSDN题解（CCF CSP 201909-3 字符画 100分 2250ms by best335）有所借鉴。
题目描述
试题编号： 201909-3
试题名称： 字符画
时间限制： 5.0s
内存限制： 512.0MB
解析
这道题没用的话实在太多，题面描述还涉及计算机操作系统等的相关知识，让人很难懂。
当我们把一些无关紧要的话过滤掉之后，会发现其实这道题并没有特别复杂。本题难就难在读题。
要对一个 (m imes n)的矩阵像素块进行压缩，压缩后的矩阵的每个像素块大小是(p imes q)。压缩后的矩阵各个像素块颜色对应值为其原矩阵(p imes q)个像素块颜色加和后对应的平均值。我们要对压缩后的这个矩阵像素块进行背景色的处理。
输入：
第一行输入(m,n,p,q)。
之后的(n imes m)行输入#a 或 #abc 或 #abcdef代表原矩阵第n行第m列的颜色。
a 代表像素块颜色为(aa, aa, aa)
abc 代表像素块颜色为（aa, bb, cc）
abcdef 代表像素块颜色为 (ab, cd, ef)
输出：
默认背景色为(0, 0, 0)。压缩后的矩阵，如果每行的像素块的颜色和本行上一个（如果是第一个，那么它的上一个就是默认值）像素块的颜色值完全相等则继续循环，否则我们进行判断，如果这个像素块的颜色为(0, 0, 0)，那么就输出"ESC[0m"，否则输出"ESC[48;2;R;G;Bm"(R,G,B分别对应的为这个像素块的颜色的三个值)。然后再输出一个空格。每行结束之后，背景色的默认值要恢复为(0, 0, 0)。如果上一个像素块的颜色不是默认值则输出"ESC[0m"。行末换行都要照常输出。
注：输出中的ESC不是三个字符，而是对应ASCII码中值为27的一个标准字符。
本题中所有的输出都是将字符转换成整型(对应的ASCII码值)，然后再将整型以十六进制输出。输出的R,G,B将十进制的数转换成字符串，然后再将字符串中的每个字符以其ASCII码值得十六进制输出。输入的R,G,B也是以十六进制输入。输出无需换行。
通过代码
//1590851 <13100928923> <王恪楠> 字符画 11-09 17:04 2.106KB C0X 正确 100 2.265s 46.37MB
#include <bits/stdc++.h>
using namespace std;
int c[2000][2000][3];
int getPixel(const char &ch1, const char &ch2) //将输入的十六进制转换成十进制.
{
return (isalpha(ch1)? 10 + ch1 - 'a': ch1 - '0') * 16 + (isalpha(ch2)? 10 + ch2 - 'a': ch2 - '0');
}
void outChar(const char &ch) //将每个字符以其ASCII码值的十六进制输出.
{
cout << "\x" << hex << uppercase << setw(2) << int(ch); //hex是按十六进制输出的意思，uppercase是将所有字母转换成大写字母输出的意思，setw（2）域宽是2.
return;
}
void outPixel(int x) //输出R,G,B十进制整数.
{
vector<int> v;
if(!x) v.push_back(0);
while(x){
v.push_back(x % 10);
x /= 10;
}
for(int i = v.size() - 1; i >= 0; i --)
outChar('0' + v[i]);
return ;
}
void outStr(const string &ss) //输出字符串.
{
for(int i = 0; i < ss.size(); i ++)
outChar(ss[i]);
return;
}
int main()
{
int n, m, p, q;
string s;
scanf("%d%d%d%d", &m, &n, &p, &q);
int area = p * q;
cout.fill('0'); //域宽中遇到空的地方都以字符'0'占位.
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> s;
if(s.size() == 2){
s += string(5, s[1]);
}
else if(s.size() == 4)
s = "#" + string(2, s[1]) + string(2, s[2]) + string(2, s[3]);
for(int k = 0; k < 3; k ++)
c[i][j][k] = getPixel(tolower(s[k + k + 1]), tolower(s[k + k + 2])); //tolower()转换成小写字母的函数.将每个像素块的颜色R,G,B以十进制记录下来.
}
}
int R, G, B, r = 0, g = 0, b = 0;
for(int i = 1; i <= n; i += q){
for(int j = 1; j <= m; j += p){
R = G = B = 0;
for(int ii = i; ii < i + q; ii ++)
for(int jj = j; jj < j + p; jj ++){
R += c[ii][jj][0];
G += c[ii][jj][1];
B += c[ii][jj][2];
}
R /= area, G /= area, B /= area; //求出压缩后的像素块的颜色.
//以下为根据题意的具体输出情况.
if(!(R == r && G == g && B == b)){
if(!R && !G && !B)
outStr(string(1, char(27)) + "[0m");
else
outStr(string(1, char(27)) + "[48;2;"), outPixel(R), outChar(';'), outPixel(G), outChar(';'), outPixel(B), outChar('m');
}
r = R, g = G, b = B;
outChar(' ');
}
if(r || g || b) outStr(string(1, char(27)) + "[0m");
outChar('
');
r = g = b = 0;
}
return 0;
}
4. 201909-4 推荐系统
题目描述
试题编号： 201909-4
试题名称： 推荐系统
时间限制： 5.0s
内存限制： 512.0MB
解析
模拟题。
需要使用stl中的set进行插入，删除，查找操作。要注意stl中set的一系列用法，包括结构体重载小于号、删除、遍历等。
通过代码
//1587530 <13100928923> <王恪楠> 推荐系统 11-06 19:43 2.912KB C0X 正确 100 3.593s 161.6MB
#include <bits/stdc++.h>
using namespace std;
struct Node{
int type, id, score;
bool operator < (const Node &i) const{ //因为要把结构体塞进set，所以要重载小于号.
if(score != i.score) //优先级为大score、小type、小id.
return score > i.score;
if(type != i.type)
return type < i.type;
if(id != i.id)
return id < i.id;
return 0;
}
};
vector<Node> v;
unordered_map<int, int> p[55]; // 记录下种类type，编号id，所对应的size的值.
set<Node> st;
inline int read() //快读，加快输入.当输入量较大时，可以使程序明显加速.
{
int res = 0, f = 1;
char ch;
ch = getchar();
while(!isdigit(ch)){
if(ch == '-')
f = -1;
ch = getchar();
}
while(isdigit(ch)){
res = (res << 3) + (res << 1) + ch - 48;
ch = getchar();
}
return f * res;
}
int main()
{
int n, m, opn;
int zz = 0;
m = read(), n = read();
for(int i = 1; i <= n; i ++){
int t1, t2;
t1 = read(), t2 = read();
for(int j = 0; j < m; j ++){
st.insert(Node{j, t1, t2});
p[j][t1] = t2; //记录下每种每型号商品的价值方便删除.
}
}
opn = read();
for(int i = 1; i <= opn; i ++){ //共opn次操作.
int t1, t2, t3, t4;
t1 = read();
//插入操作.
if(t1 == 1){
t2 = read(), t3 = read(), t4 = read();
st.insert(Node{t2, t3, t4});
p[t2][t3] = t4;
}
//删除操作.
else if(t1 == 2){
t2 = read(), t3 = read();
st.erase(Node{t2, t3, p[t2][t3]});
p[t2].erase(t3);
}
//查找操作.
else{
vector<int> ans[55]; //将每种选中的商品放进ans中.
int kn, k[55], cnt[55]; //共需要查找kn个.第j种不超过k[j]个.
kn = read();
for(int j = 0; j < m; j ++)
k[j] = read();
for(set<Node> :: iterator it = st.begin(); it != st.end() && kn; it ++){ //遍历set直到从中找出kn个商品为止.
//因为set中自带顺序，所以可以直接遍历.
if(k[(*it).type]){ //当第j种商品被选中的个数不超过k[j]种的时候，可以选择这个商品.
ans[(*it).type].push_back((*it).id);
k[(*it).type] --;
kn --;
}
}
for(int j = 0; j < m; j ++){
if(!ans[j].size()) //这个种类没有商品被选中则输出-1.
printf("-1
");
else{
sort(v.begin(), v.end()); //每种按照id的从小到大输出.
printf("%d", ans[j][0]);
for(int jj = 1; jj < ans[j].size(); jj ++)
printf(" %d", ans[j][jj]);
printf("
");
}
}
}
}
return 0;
}