“卓见杯”第五届CCPC中国大学生程序设计竞赛河南省赛
发布时间
阅读量：
阅读量
文章目录
- "卓见杯"第五届CCPC中国大学生程序设计竞赛河南省赛
- A. Maximum Descent Matrix
- C. Point Pairs with Close Sizes
- D. Text Correction
- E. Guguge's Recursive Machine
- F. Guguge's Counting Problem II
- H. Guguge's Search Sequence
- I.Antique Dream
“卓见杯”第五届CCPC中国大学生程序设计竞赛河南省赛
A.最大下降矩阵
题意： 签到
题解：
代码：
#include <bits/stdc++.h>
using namespace std;
int const N = 310 + 10;
typedef long long LL;
typedef pair<int, int> PII;
int n, m, T;
int a[N][N];
int f[N];
bool check(int line1, int line2) {
int flg = 1;
for (int i = 1; i <= m; ++i) {
if (a[line1][i] >= a[line2][i]) flg = 0;
}
return flg == 1;
}
int main() {
// freopen("in.txt", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
int res = 0;
for (int i = 1; i <= n; ++i) {
f[i] = 1;
for (int j = 1; j <= i - 1; ++j) {
if (check(i, j) == 1) // < 0 -> 1
{
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
cout << n - res;
return 0;
}C.大小接近的点对
题意即为：当 u 是 v 的祖先节点且满足 |a[u] - a[v]| ≤ K 时，则称 (u, v) 为「大小相近的一对节点」。对于树中的每一个节点 i 来说，请计算其子树中「大小相近的一对节点」的数量。
题解：
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int const N = 3e5 + 10, M = N * 2;
int n, m, T, k, w[N];
int e[M], ne[M], h[N], idx, c[N];
LL res[N];
vector<int> v;
int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int lowbit(int x) {
return x & -x;
}
void add2(int x, int y) {
for (int i = x; i <= v.size(); i += lowbit(i)) c[i] += y;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += c[i];
return res;
}
void dfs(int u, int fa) {
res[u] = 0;
int l = getid(w[u] - k), r = getid(w[u] + k);
int first = query(r) - query(l - 1);
add2(getid(w[u]), 1);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs(j, u);
res[u] += res[j];
}
int second = query(r) - query(l - 1);
//cout << u << " " << second << " " << first << endl;
res[u] += second - 0ll - first;
return;
}
int main() {
//freopen("in.txt", "r", stdin);
cin >> n >> k;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; ++i) {
int t;
scanf("%d", &w[i]);
v.push_back(w[i]);
v.push_back(w[i] - k);
v.push_back(w[i] + k);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 2; i<= n; ++i) {
int fa;
scanf("%d", &fa);
add(i, fa), add(fa, i);
}
dfs(1, -1);
for (int i = 1; i <= n; ++i) printf("%lld\n", res[i]);
return 0;
}D.文本修正
题意： 签到
题解：
代码：
#include <bits/stdc++.h>
using namespace std;
char s[1000];
int main() {
while(scanf("%s", s) != EOF) {
if (strcmp(s, "henan") == 0) {
printf("Henan ");
}
else printf("%s ",s);
}
return 0;
}E.咕咕的的复复读读机机
题意： 签到
题解：
代码：
#include <bits/stdc++.h>
using namespace std;
int const N = 2e5 + 10;
typedef long long LL;
typedef pair<int, int> PII;
int n, m, T, a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int t;
cin >> t;
a[t]++;
}
int maxv = -1, max_val = -1;
for (int i = 1; i <= 100; ++i) {
if (a[i] > maxv) {
maxv = a[i];
max_val = i;
}
}
cout << max_val;
return 0;
}F.咕咕的计数题 II
题意： 签到
题解：
代码：
#include <bits/stdc++.h>
using namespace std;
int const N = 2e5 + 10;
typedef long long LL;
typedef pair<int, int> PII;
int T;
LL presum(LL x, LL a) {
LL sum = 0;
if (x / a <= a) {
LL pre = x / a - 1;
if (pre & 1) sum = (pre + 1) / 2 * pre;
else sum = pre / 2 * (pre + 1);
LL head = x / a * a;
x = min(x, head + pre);
sum += x - head + 1;
}
else {
LL pre = presum(a * a, a);
sum = pre + x - a * a;
}
return sum;
}
int main() {
cin >> T;
while(T--) {
LL a, l, r;
scanf("%lld%lld%lld", &a, &l, &r);
printf("%lld\n", presum(r, a) - presum(l - 1, a));
}
return 0;
}H.咕咕的搜索序列
题意： 定义在进行一次点回溯操作后才将该点加入序列。现提供一棵特定的树及其一种特殊形式的DFS序列，在此序列中某些元素已被删除，请判断该DFS序列是否满足条件。
题解：
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int const N = 1e6 + 10, M = N * 2;
int n, m, T, fa[N], a[N], st[N], ans[N], tot;
vector<int> G[N];
void solve(int x) { // 处理访问的优先级
while(1) {
if (st[x] || x == 1 || x == 0) break;
st[x] = 1;
G[fa[x]].push_back(x);
x = fa[x];
}
}
void dfs(int u ,int father) {
int len = G[u].size();
for (int i = 0; i < len; ++i) {
int j = G[u][i];
dfs(j, u);
}
ans[++tot] = u;
}
int main() {
cin >> T;
while(T--) {
tot = 0;
int n, m;
scanf("%d%d", &n, &m);
for (int i = 2, node; i <= n; ++i) {
scanf("%d", &node);
G[i].clear();
fa[i] = node;
st[i] = 0;
}
G[1].clear(), st[1] = 0, fa[1] = 0;
for (int i = 1; i <= m; ++i) scanf("%d", a + i);
for (int i = 1; i <= m; ++i) solve(a[i]);
dfs(1, -1);
int i = 1, j = 1;
while(1) {
if (a[i] == ans[j]) i++, j++;
else j++;
if (j > tot || i > m) break;
}
if (i <= m) puts("BAD GUGU");
else puts("NOT BAD");
}
return 0;
}I.Childhood dream
问题描述：考虑以下m次操作。每一次操作将提供一个长度为n的字符串以及两个参数a和b。其中参数a代表当前处理的字符串与目标答案在相同位置且大小一致的字符数量；而参数b则表示当前处理的字符串与目标答案在相同大小但不同位置上的字符数量。经过这m次操作后，请确定并输出最终的答案。
题解部分指出，在面对一个字符串问题时, 如果要求字符不重复且数据量不大, 则可以直接采用暴力搜索的方法解决这个问题; 对于本题而言, 在这种情况下无需进行任何剪枝优化就能轻松通过测试.
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int const N = 100 + 10;
int n, m, T;
struct Node {
string s;
int first, second;
}node[N];
int st[11];
int flg = 0;
PII get(int a[], string s) {
int backupa[11] = {0};
int backupb[11] = {0};
int tot = 0, cnt = 0;
for (int i = 0; i < m; ++i) {
if (a[i] != s[i] - '0') backupa[tot] = a[i], backupb[tot++] = s[i] - '0';
else cnt++;
}
int res = 0;
for (int i = 0; i < tot; ++i)
for (int j = 0; j < tot; ++j)
if (backupa[i] == backupb[j]) res ++;
return {cnt, res};
}
bool check(int a[]) {
for (int i = 1; i <= n; ++i) {
auto res = get(a, node[i].s);
int first = res.first, second = res.second;
if (first != node[i].first || second != node[i].second) return false;
}
return true;
}
void dfs(int u, int a[]) {
if (flg ) return;
if (u == m) {
if (check(a)) {
for (int i = 0; i < m; ++i) printf("%d", a[i]);
flg = 1;
}
return;
}
for (int i = 0; i <= 9; ++i) {
if (!st[i]) {
a[u] = i;
st[i] = 1;
dfs(u + 1, a);
st[i] = 0;
}
}
return;
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1, b, c; i <= n; ++i) {
string a;
cin >> a;
scanf("%d%d", &b, &c);
node[i] = {a, b, c};
}
int cur[11] = {0};
dfs(0, cur);
return 0;
}全部评论 (0)
还没有任何评论哟~