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 字符画

本题于这篇题解（CCF CSP 201909-3 字符画 100分 2250ms by best335）有所借鉴。

题目描述

试题编号： 201909-3
试题名称： 字符画
时间限制： 5.0s
内存限制： 512.0MB

解析

这道题没用的话实在太多，题面描述还涉及计算机操作系统等的相关知识，让人很难懂。
当我们把一些无关紧要的话过滤掉之后，会发现其实这道题并没有特别复杂。本题难就难在读题。

要对一个 $m \times n$的矩阵像素块进行压缩，压缩后的矩阵的每个像素块大小是$p \times q$。压缩后的矩阵各个像素块颜色对应值为其原矩阵$p \times q$个像素块颜色加和后对应的平均值。我们要对压缩后的这个矩阵像素块进行背景色的处理。

输入：
第一行输入$m,n,p,q$。
之后的$n \times 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('\n');
        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\n");
                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("\n");
                }
            }
        }
    }
    return 0;
}