@w616561153
2019-11-11T08:53:42.000000Z
字数 6129
阅读 515
ccf题解
试题编号: 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;
}
试题编号: 201909-2
试题名称: 小明种苹果(续)
时间限制: 1.0s
内存限制: 512.0MB
比上一题的难度稍有增加。
加入了掉落的概念。
掉落:输入每行的值,第一个值为果树原有果子个数,之后的值为正数则为现在果树上的果子个数,非正数则为疏果掉落的个数。我们需要藉此来判断是否出现掉落情况(不包括疏果使其掉落)。则用变量now记录每行到每个位置的这棵果树的果子树。如果是非正数数,那么就now加上这个值(负数),如果是正数,那么就用now和这个正数比一下大小,如果now比这个正数小,那么就说明这棵树出现了掉落情况,反之则无。用记录每棵树是否出现了掉落情况。
果树按圆种植。
一棵树的序号为,则它左边的树序号为,右边的树序号为。
题中要求的三个值,苹果的总数T,有掉落的果树个数D,连续三个果树都有掉落的情况个数E。
T可以通过每行最后变量now相加得到,每行如果出现了掉落情况则D++, E可以通过已经记录好的数组循环一遍求得。
//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;
}
本题于这篇题解(CCF CSP 201909-3 字符画 100分 2250ms by best335)有所借鉴。
试题编号: 201909-3
试题名称: 字符画
时间限制: 5.0s
内存限制: 512.0MB
这道题没用的话实在太多,题面描述还涉及计算机操作系统等的相关知识,让人很难懂。
当我们把一些无关紧要的话过滤掉之后,会发现其实这道题并没有特别复杂。本题难就难在读题。
要对一个 的矩阵像素块进行压缩,压缩后的矩阵的每个像素块大小是。压缩后的矩阵各个像素块颜色对应值为其原矩阵个像素块颜色加和后对应的平均值。我们要对压缩后的这个矩阵像素块进行背景色的处理。
输入:
第一行输入。
之后的行输入#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;
}
试题编号: 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;
}