C/C++教程
2021中国大学生程序设计竞赛部分题解（CCPC）- 网络选拔赛（重赛）
本文主要是介绍2021中国大学生程序设计竞赛部分题解（CCPC）- 网络选拔赛（重赛），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
文章目录
- 一、1002 Kanade Doesn't Want to Learn CG
- 二、1004 Primality Test
- 三、1005 Monopoly
- 四、1006 Nun Heh Heh Aaaaaaaaaaa
- 五、1010 Bigraph Extension
- 六、1011 Jumping Monkey
一、1002 Kanade Doesn’t Want to Learn CG
简单数学问题：判断位置即可
#include <bits/stdc++.h>
#define MaxN 0x3f3f3f3f
#define MinN 0xc0c0c0c0
#define bug(x) cout << #x"=" << x << endl;
#define BUG(a,b) cout << #a"=" << a << " " << #b"=" << b << endl;
#define ALL(a) a.begin(), a.end()
#define rep1(i,a,b) for(int i=(a);i<=(b);i++)
#define per1(i,a,b) for(int i=(a);i>=(b);i--)
#define rep2(i,a,b) for(int i=(a);i<(b);i++)
#define per2(i,a,b) for(int i=(a);i>(b);i--)
#define mset(a,b) memset(a,b,sizeof(a))
#define sz(a) (int)a.size()
#define EPS 1e-9
#define MAX(a,b) (((a)>(b)? (a):(b)))
#define MIN(a,b) (((a)>(b)? (b):(a)))
#define buff ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pf(x) printf("%d\n",x);
#define sf(x) scanf("%d",&x);
using namespace std;
void solve(){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
double x0,x1,y0,y1,y2;
scanf("%lf%lf%lf%lf%lf",&x0,&x1,&y0,&y1,&y2);
double x = 0.0;
x = (-sqrt(b*b-4*a*(c-y0))-b)/(2*a);
// 这里注意a是负数：取哪个根的时候要抉择一下.
// cout << "x=" << x << " x0=" << x0 << " x1=" << x1 << endl;
if(x>x0 && x1>x) puts("YES");
else if(x<=x0) puts("NO");
else{
double yy = a*x1*x1+b*x1+c;
if(yy<=y2){
if(2*x1-x>x0 && 2*x1-x<x1){
puts("YES");
}else{
puts("NO");
}
}else{
puts("NO");
}
}
}
int main()
{
//buff;
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
二、1004 Primality Test
签到题。
通过水几组样例可以发现规律：当 x>1 时输出NO，当x=1时输出YES.
正经分析：通过观察发现，f(x)和f(f(x))是连续的质数，质数一定是奇数，故g(x)一定是整数.（从这里就可以看出2比较特殊（因为2是偶数））。假设g(x)是个质数，则g(x)一定在f(x)和f(f(x))之间，与观察矛盾，故g(x)不可能是质数。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
long long x;
while(t--){
scanf("%lld",&x);
if(x==1) puts("NO");
else puts("YES");
}
return 0;
}
三、1005 Monopoly
维护一种数据结构…(kungeyyds)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 998244353;
ll a[100010];
struct node {
ll u, x, pos;
friend bool operator<(node s1, node s2) {
if(s1.u == s2.u) return s1.x < s2.x;
return s1.u < s2.u;
}
} q[100010];
#define sangkun
int main() {
#ifdef sangkun
freopen("in.txt", "r", stdin);
#endif
int t;
cin >> t;
while(t--) {
int n, m;
cin >> n >> m;
ll sum = 0;
int op = 0;
map<ll, map<ll, bool>>vis;
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
sum += a[i];
}
if(sum == 0) {
map<ll, int>ans;
for(int i = 1; i <= n; i++) {
a[i] += a[i - 1];
if(!ans[a[i]]) ans[a[i]] = i;
}
while(m--) {
ll x;
cin >> x;
if(x == 0) {
printf("0\n");
} else if(ans[x]) {
printf("%d\n", ans[x]);
} else printf("-1\n");
}
continue;
}
int ok=0;
if(sum < 0) {
for(int i = 1; i <= n; i++) {
a[i] = -a[i];
}
sum = -sum;
ok=1;
}
q[++op] = {0, 0, 0};
vis[0][0] = 1;
for(int i = 1; i <= n; i++) {
a[i] += a[i - 1];
ll u = abs(a[i]) % sum;
ll x = a[i] / sum;
if(a[i] < 0) u = sum - u, x--;
if(vis[u][x]) continue;
vis[u][x] = 1;
q[++op] = {u, x, i};
}
sort(q + 1, q + 1 + op);
// for(int i=1;i<=op;i++) cout<<q[i].u<<" "<<q[i].x<<" "<<q[i].pos<<endl;
while(m--) {
ll x;
cin >> x;
if(ok) x=-x;
ll u = abs(x) % sum, y = x / sum;
if(x < 0) u = sum - u, y--;
ll l = 1, r = op, ansl = op + 1, ansr = 0, ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(q[mid].u < u) l = mid + 1;
else r = mid - 1, ansl = mid;
}
l = 1, r = op;
while(l <= r) {
int mid = (l + r) >> 1;
if(q[mid].u <= u) l = mid + 1, ansr = mid;
else r = mid - 1;
}
if(q[ansl].u != u) {
printf("-1\n");
continue;
}
l = ansl, r = ansr;
while(l <= r) {
int mid = (l + r) >> 1;
if(q[mid].x <= y) l = mid + 1, ans = mid;
else r = mid - 1;
}
if(ans == 0) {
printf("-1\n");
continue;
}
ans = (y - q[ans].x) * n + q[ans].pos;
cout << ans << endl;
}
}
return 0;
}
四、1006 Nun Heh Heh Aaaaaaaaaaa
DP问题：定义dp(i,j) 表示前i个数中匹配到第j位的方案数.
dp(i,j) = dp(i-1,j) + (if(匹配) +1);
dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]*(s[i]==str[j])) % MOD;
dp(i,9)*后缀a的贡献数即为答案.
后缀a的方案数：2的n次方-1（由二项式定理推出）
处理2的n次方：使用快速幂或者使用左移运算符(1<<i);
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#define bug(x) cout << #x"=" << x << endl;
#define BUG(a,b) cout << #a"=" << a << " " << #b"=" << b << endl;
using namespace std;
typedef long long ll;
const int N = 100010;
const int MOD = 998244353;
ll mod_power(ll a,ll n,ll mod){ll res = 1;while(n){if(n&1) res = res*a%mod;n >>= 1;a = a*a%mod;}return (res-1);}
ll dp[N][10];
char s[N];
void solve(){
char str[] = " nunhehheh";
ll a[N];
scanf("%s",s+1);
int len = strlen(s+1);
// cout << len << endl;
a[len+1] = 0;
for(int i=len;i>=1;i--){
a[i] = a[i+1] + (s[i]=='a');
}
ll ans = 0;
for(int i=1;i<=len;i++){
for(int j=1;j<=9;j++){
if(j==1) dp[i][j] = dp[i-1][j] + (s[i]==str[j]);
else if(j==9) dp[i][j] = dp[i][j-1]*(s[i]==str[j]); // 这里出现问题.
else dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*(s[i]==str[j]);
}
if(dp[i][9]){
ans = (ans + (dp[i][9]*mod_power(2,a[i+1],MOD))%MOD)%MOD;
// ans = (ans + (dp[i][9]%MOD*((1<<a[i+1])-1)%MOD)%MOD)%MOD; 使用左移运算符计算.
}
}
printf("%lld\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
五、1010 Bigraph Extension
(kungeyyds)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 998244353;
int f[1010][2];
int pre[2010];
int tmp(int x) {
if(x == pre[x]) return x;
return pre[x] = tmp(pre[x]);
}
int n, m;
bool add(int x, int y) {
y += n;
int A = tmp(x);
int B = tmp(y);
if(A == B) return false;
pre[A] = B;
return true;
}
int main() {
int t;
cin >> t;
while(t--) {
cin >> n >> m;
map<int, map<int, int>>vis;
vector<pair<int, int>>ans;
set<int>s;
for(int i = 1; i <= n; i++) {
pre[i] = i;
pre[i + n] = i+n;
f[i][0] = 0;
f[i][1] = 0;
s.insert(i);
}
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
f[u][0]++;
f[v][1]++;
if(f[v][1] == 2) s.erase(v);
}
if(m == 0) {
f[1][0]++;
f[1][1]++;
add(1, 1);
ans.push_back({1, 1});
}
for(int i = 1; i <= n; i++) {
while(f[i][0] != 2 && ans.size() + m != 2 * n - 1) {
f[i][0]++;
for(auto j : s) {
// cout << tmp(i) << ":" << tmp(j) << endl;
if(!add(i, j)) continue;
f[j][1]++;
ans.push_back({i, j});
// cout << i << "==" << j << endl;
if(f[j][1] == 2)s.erase(j);
break;
}
}
}
std::cout << q0 << ' '
int q1 = 0, q2 = 0;
for(int i = 1; i <= n; i++) {
if(f[i][0] == 1) q1 = i;
if(f[i][1] == 1) q2 = i;
}
ans.push_back({q1, q2});
cout << ans.size() << endl;
for(auto i : ans) printf("%d %d\n", i.first, i.second);
}
return 0;
}
六、1011 Jumping Monkey
先排序然后从小到大枚举;每次把当前点作为并查集的根;然后遍历它的儿子 ;只考虑权值比它小的;那么儿子所在的集的根能到的第一个点就是当前点;这样去求每个点能到的第一个比它大的点;然后倒序去求答案;答案就是能到的第一个点的答案+1.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 998244353;
int u[100100], v[100100];
int a[100100], b[100100];
vector<int>g[100100];
int ans[100010];
int pre[100010];
int tmp(int x) {
if(x == pre[x]) return x;
return pre[x] = tmp(pre[x]);
}
int main() {
int t;
cin >> t;
while(t--) {
int n;
scanf("%d", &n);
for(int i = 1; i < n; i++) {
scanf("%d%d", &u[i], &v[i]);
}
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
g[i].clear();
ans[i] = 0;
pre[i] = i;
}
sort(b + 1, b + 1 + n);
for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
for(int i = 1; i <= n; i++) {
u[i] = a[u[i]];
v[i] = a[v[i]];
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
for(int i = 1; i <= n; i++) {
for(auto j : g[i]) {
if(j < i) {
int A = tmp(j);
if(A == i) continue;
pre[A] = i;
ans[A] = i;
}
}
}
for(int i = n; i >= 1; i--) {
ans[i] = ans[ans[i]];
ans[i]++;
}
for(int i = 1; i <= n; i++) printf("%d\n", ans[a[i]]);
}
}
这篇关于2021中国大学生程序设计竞赛部分题解（CCPC）- 网络选拔赛（重赛）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
-
在Mac系统上将图片中的文字提取出来有哪些方法？-icode9专业技术文章分享11-22
-
excel 表格中怎么固定一行显示不滚动？-icode9专业技术文章分享11-22
-
怎么将 -rwxr-xr-x 修改为 drwxr-xr-x？-icode9专业技术文章分享11-22
-
在Excel中怎么将小数向上取整到最接近的整数？-icode9专业技术文章分享11-22
-
Excel中常见的取整函数有哪些？-icode9专业技术文章分享11-22
-
错误信息：does not match the actual quantity supplied 提示是什么意思？-icode9专业技术文章分享11-22
-
WebSocket学习：初学者的简单指南11-21
-
获取apk的md5值有哪些方法？-icode9专业技术文章分享11-20
-
xml报文没有传 IdentCode ，为什么正常解析没报错呢？-icode9专业技术文章分享11-20
栏目导航
