第十七次CCF计算机软件能力认证

第一题：小明种苹果

n , m = map(int , input().split())
t , k , p = 0 , 0 , -1
for _ in range(n):l = list(map(int , input().split()))t += sum(l)x = -sum(l[i] for i in range(1 , len(l)))if x > p:p = xk = _ + 1
print(t , k , p)

第二题：小明种苹果（续）

#include<iostream>
#include<vector>
#include<cstring>using namespace std;typedef long long ll;
const int N = 1010;
int n;
ll t;
int d , e;
bool diao[N];int main()
{memset(diao , 0 , sizeof diao);cin >> n;for(int i = 0;i < n;i ++){int m;cin >> m;vector<ll>v;for(int j = 0;j < m;j ++){ll x;cin >> x;v.push_back(x);}ll temp = v[0];// 前缀和的思想for(int j = 1;j < m;j ++){if(v[j] <= 0) temp += v[j];else {if(temp != v[j]) diao[i] = true; }}for(int j = m - 1;j >= 0;j --){t += v[j];if(v[j] > 0) break;}}for(int i = 0;i < n;i ++)if(diao[i]) d ++;for(int i = 0;i < n;i ++)if(diao[i] && diao[(i + 1) % n] && diao[(i + 2) % n]) e ++;cout << t << " " << d << " " << e << endl;
}

第三题：字符画

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef unsigned char UC;
const int N = 1080, M = 1920;int m, n, p, q;
UC g[N][M][3];inline int get(char c)
{if (c <= '9') return c - '0';return c - 'a' + 10;
}inline char get(int x)
{if (x <= 9) return x + '0';return x - 10 + 'A';
}inline void print(char* str)
{for (int i = 0; str[i]; i ++ )printf("\\x%c%c", get(str[i] / 16), get(str[i] % 16));
}int main()
{scanf("%d%d%d%d", &m, &n, &p, &q);char str[100];for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ ){scanf("%s", str);int len = strlen(str);if (len == 2){int t = get(str[1]);for (int k = 0; k < 3; k ++ )g[i][j][k] = t * 16 + t;}else if (len == 4){for (int k = 0; k < 3; k ++ ){int t = get(str[1 + k]);g[i][j][k] = t * 16 + t;}}else{for (int k = 0; k < 3; k ++ )g[i][j][k] = get(str[1 + k * 2]) * 16 + get(str[2 + k * 2]);}}int bg[3] = {0};for (int i = 0; i < n / q; i ++ ){for (int j = 0; j < m / p; j ++ ){int cur[3] = {0};for (int x = 0; x < q; x ++ )for (int y = 0; y < p; y ++ )for (int z = 0; z < 3; z ++ )cur[z] += g[i * q + x][j * p + y][z];for (int k = 0; k < 3; k ++ ) cur[k] /= p * q;if (cur[0] == bg[0] && cur[1] == bg[1] && cur[2] == bg[2]) ;  // passelse if (!cur[0] && !cur[1] && !cur[2]) print("\033[0m");else{sprintf(str, "\033[48;2;%d;%d;%dm", cur[0], cur[1], cur[2]);print(str);}for (int k = 0; k < 3; k ++ ) bg[k] = cur[k];print(" ");}if (bg[0] || bg[1] || bg[2]){print("\033[0m");for (int k = 0; k < 3; k ++ ) bg[k] = 0;}print("\n");}return 0;
}

第四题：推荐系统

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>using namespace std;const int N = 110;
typedef pair<int , int>PII;
int n , m;struct node
{int id , idx , sc;  //商品种类id，第idx个商品，该商品得分scbool operator < (const node &p) const{if(sc != p.sc) return sc < p.sc;if(id != p.id) return id > p.id;return idx > p.idx;}
};priority_queue<node>q;
map<PII , int>mp;int main()
{cin >> m >> n;for(int i = 0;i < n;i ++){int a , b;cin >> a >> b;for(int j = 0;j < m;j ++)q.push({j , a , b}); // m类商品的第j个商品的编号和得分}int t;cin >> t;while(t --){int op;cin >> op;if(op == 1){int a , b , c;cin >> a >> b >> c;q.push({a , b , c});}else if(op == 2){int a , b;cin >> a >> b;mp[{a , b}] = 1;}else{int k;cin >> k;int many_k[N];priority_queue<node>temp;for(int i = 0;i < m;i ++)cin >> many_k[i];map<int , vector<int>>res;while(!q.empty() && k){auto t = q.top();q.pop();temp.push(t);if(!mp[{t.id , t.idx}]){if(many_k[t.id]){many_k[t.id] --;k --;res[t.id].push_back(t.idx);}}}while(!temp.empty()){q.push(temp.top());temp.pop();}for(int i = 0;i < m;i ++){if(!res[i].size()) puts("-1");else {for(auto j : res[i])cout << j << " ";cout << endl;}}}}return 0;
}

第五题：城市规划

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;
const int N = 50010, M = N * 2;int n, m, K;
int h[N], e[M], w[M], ne[M], idx;
LL f[N][110];
bool st[N];
int sz[N];
LL ans = 1e18;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}void dfs(int u, int fa)
{f[u][0] = 0;if (st[u]) f[u][1] = 0;sz[u] = 1;for (int i = h[u]; ~i; i = ne[i])  // 枚举物品组{int ver = e[i];if (ver == fa) continue;dfs(ver, u);sz[u] += sz[ver];for (int j = min(sz[u], K); j >= 0; j -- )  // 枚举体积for (int k = 0; k <= min(j, sz[ver]); k ++ )  // 枚举决策f[u][j] = min(f[u][j], f[u][j - k] + f[ver][k] + (LL)w[i] * k * (K - k));}ans = min(ans, f[u][K]);
}int main()
{scanf("%d%d%d", &n, &m, &K);memset(h, -1, sizeof h);while (m -- ){int x;scanf("%d", &x);st[x] = true;}for (int i = 0; i < n - 1; i ++ ){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}memset(f, 0x3f, sizeof f);dfs(1, -1);printf("%lld\n", ans);return 0;
}