CCST校赛题解
第一题
签到题，按照题目要求输出即可。
//c++
#include <iostream>
#include <string>
using namespace std;
int main()
{
cout << "欢迎各位参赛者参加本次校内选拔赛！" << endl;
return 0;
}
第二题
统计AC出现的次数，输出 AC/n*100%即可，注意不要对AC/n进行int计算。 比如3/5 * 100 = 0
//c++
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<limits>
#include<unordered_map>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<numeric>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
double cnt = 0;
cin >> n;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
if (s == "AC")
cnt++;
}
cout << (int)(cnt / n * 100) << "%";
return 0;
}
第三题
模拟题，按照题目输入，给出每个点的得分，累加得分输出即可。
//c++
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int ans = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
char c;
std::cin >> c;
if (c == 'X') {
ans += std::min({i + 1, 10 - i, j + 1, 10 - j});//(i,j)的得分
}
}
}
std::cout << ans << "\n";
}
int main() {
int t = 1;
//std::cin >> t;
while (t--) {
solve();
}
return 0;
}
第四题
由题易得中间数为(n * n+1)/2，幻和为中间数 * n
#include <bits/stdc++.h>
using namespace std;
void solve()
{
long long n;
cin >> n;
long long t = n;
n = n*n;
long long sum = (n+1)/2;
cout << sum*t << " " << sum << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
第五题
（位运算）顾客需要n大小的蛋糕，那么我们要烤的蛋糕一定是大于等于n的
我们看n是否为2的负整数次幂，如果是那就直接输出，且切割次数为0,否则，输出n最高二进制位数的上一位。那最小切割次数就是最低位和最高位的差。
#include <bits/stdc++.h>
using namespace std;
int lowbit(int x)
{
return x & -x;
}
void solve()
{
// 1000 - 0110 = 001
// 1000 >> 1 ans += 2;
// 1000 - 0101
int k;
cin >> k;
int tmp = k;
bool flag = true;
int minp;
int maxp = 0;
while(k != 0)
{
maxp ++;
if(k & 1 && flag)
{
flag = false;
minp = maxp;
}
k >>= 1;
}
if(tmp == lowbit(tmp)) cout << lowbit(tmp) << " " << 0 << endl;
else cout << (1 << maxp) << " " << maxp + 1 - minp << endl;
}
int main()
{
int t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}
第六题
题目大意就是找到一个质数，使与题目给出的质数相加后不是质数。
答案有很多种，其实输出自身就是一种答案，另外7与任何质数相加都为非质数，其他的也可以枚举质数出结果。
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
cout << n << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//cout.precision(10); cout.setf(ios::fixed);
int t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}
第七题
我们可以得出答案一定具有单调性，因此考虑二分。
check一下高度是否能把题目给出的水都装下，通过二分就能找到最大h
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL n,m;
vector<LL> v;
void solve()
{
cin >> n >> m;
v.clear();
v.resize(n);
for(int i = 0 ; i < n ; i ++) cin >> v[i];
LL l = 0 , r = 1e10;//r要高一些，考虑珊瑚柱全为1e9的平铺情况
LL total = 0;
while(l < r)
{
LL mid = (l + r + 1)/2;
total = 0;
for(int i = 0 ; i < n ; i ++)
{
if(mid > v[i]) total += mid - v[i];
}
if(total <= m) l = mid;
else r = mid - 1;
}
cout << r << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//cout.precision(10); cout.setf(ios::fixed);
int t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}
第八题
题目数据范围很小，爆搜就好，用全局ans记录最大值。
#include <bits/stdc++.h>
using namespace std;
const int N=100;
struct st
{
int x,y,z,w;
}k[N];
int n,a,b,c;
int sum;
void dfs(int id,int x1,int y1,int z1,int w1)
{
if(id>n)return;
if(x1>a||y1>b||z1>c) return;
if(x1<=a&&y1<=b&&z1<=c)
{
sum=max(sum,w1);
}
dfs(id+1,x1+k[id].x,y1+k[id].y,z1+k[id].z,w1+k[id].w);
dfs(id+1,x1,y1,z1,w1);
}
int main()
{
cin>>n>>a>>b>>c;
for(int i=0;i<n;i++)
cin>>k[i].x>>k[i].y>>k[i].z>>k[i].w;
dfs(0,0,0,0,0);
cout<<sum<<endl;
return 0;
}
第九题
根据题意，有两种情况：
1，以H-2r为圆柱的周长，W为圆柱的高，条件：
H-2r>=2πr
=> H>=2πr+2r => r <= H/2(π+1)
体积：V=πr²W；
2，以W为圆柱的周长，H-2r为圆柱的高，条件：
W>=2πr => r <=W/2π
体积：V = πr²(H-2r)
取max即可
#include <bits/stdc++.h>
using namespace std;
long double PI = acos(-1);//快速获取最精确的PI值
void solve()
{
double w, h, r, result1, result2;
while(scanf("%lf%lf", &w, &h) == 2 && w != 0)
{
r = w / (2 * PI);//第一种情况
result1 = PI * r * r * (h - 2 * r);
r = h / (2 * PI + 2);
r = r * 2 > w ? w / 2 : r;//第二种情况
result2 = PI * r * r * w;
printf("%.3f\n", result1>result2 ? result1:result2);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//cout.precision(10); cout.setf(ios::fixed);
int t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}
第十题
状态机DP
如果不考虑限制的话，其实每一个位置都有26种选择。
考虑f[i,4]
f[i,0]表示以i字符结尾，最后一个字符是除"Q"，"A"外任意一个字符；
f[i,1]表示以i字符结尾，最后一个字符以"Q"结尾；
f[i,2]表示以i字符结尾，最后两个字符是"QA"结尾；
f[i,3]表示以i字符结尾，最后一个字符任意且出现过"QAQ"的情况。
那么状态转移就是这样：
f[i][0] += f[i-1][0]*25 + f[i-1][1]*24 + f[i-1][2]*25;
f[i][1] += f[i-1][0] + f[i-1][1];
f[i][2] += f[i-1][1];
f[i][3] += f[i-1][2] + f[i-1][3]*26;
对于每个长度就是f[n,3]
void solve()//这里只放个solve函数，自行取模
{
int t;
cin >> t;
f[0][0] = 1;
for(int i = 1 ; i < N ; i ++)
{
f[i][0] += f[i-1][0]*25 + f[i-1][1]*24 + f[i-1][2]*25;
f[i][1] += f[i-1][0] + f[i-1][1];
f[i][2] += f[i-1][1];
f[i][3] += f[i-1][2] + f[i-1][3]*26;
}
while(t--)
{
int n;
cin >> n;
cout << f[n][3] << endl;
}
}
第十一题：
数据结构区间最小值，线段树，ST表，滑动窗口都可以做。
//线段树
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int N = 1e6 + 10 ;
int n, k ;
int w[N] ;
struct Node
{
int l, r, mn ;
}tr[4 * N] ;
void pushup(int u)
{
tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn) ;
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r]} ;
else
{
tr[u] = {l, r} ;
int mid = l + r >> 1 ;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r) ;
pushup(u) ;
}
}
int query(int u, int l, int r)
{
if (l <= tr[u].l && r >= tr[u].r) return tr[u].mn ;
int mid = tr[u].l + tr[u].r >> 1 ;
int res = 0x3f3f3f3f ;
if (l <= mid) res = min(res, query(u << 1, l, r)) ;
if (r > mid) res = min(res, query(u << 1 | 1, l, r)) ;
return res ;
}
int main()
{
ios::sync_with_stdio(false) ;
cin >> n ;
for (int i = 0 ; i < n ; i ++ )
cin >> w[i] ;
build(1, 0, n - 1) ;
cin >> k ;
for (int i = 0 ; i < n ; i ++ )
cout << query(1, max(0, i - k), min(n - 1, i + k)) << " " ;
return 0 ;
}
//ST表
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 20;
int n, k, t;
int q[N];
int f[N][M];
int query(int l, int r) {
int len = log(r - l + 1) / log(2);
int x = f[l][len], y = f[r - (1 << len) + 1][len];
return q[x] > q[y] ? y : x;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &q[i]);
cin >> k;
t = log(n) / log(2);
for (int j = 0; j <= t; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if (!j) f[i][j] = i;
else {
int l = f[i][j - 1], r = f[i + (1 << (j - 1))][j - 1];
if (q[l] > q[r]) f[i][j] = r;
else f[i][j] = l;
}
}
}
int l, r;
for (int i = 1; i <= n; i++) {
l = max(1, i - k), r = min(n, i + k);
cout << q[query(l, r)] << " ";
}
cout << endl;
return 0;
}
//双向滑动窗口
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N],ans1[N],ans2[N]; //ans1[]存储每个元素前k个（包含自己）元素中的最小值，ans2[]存储每个元素后k个元素（包含自己）元素中的最小值
int q1[N],q2[N];
int n,k;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>k;
int hh=0,tt=-1;
//窗口从前往后滑动，每次窗口中的最小值代表的是窗口中末元素前k个（包含自己）的最小值
for(int i=1;i<=n;i++){
while(hh<=tt&&q1[hh]<i-k) hh++;
while(hh<=tt&&a[q1[tt]]>=a[i]) tt--;
q1[++tt]=i;
ans1[i]=a[q1[hh]];
}
hh=0,tt=-1;
reverse(a+1,a+n+1); //我们为了方便可以复用上面的代码，将数组反转
//窗口也是从前往后滑动，因为已将数组反转，所以每次窗口中的最小值代表的是窗口中末元素前k个（包含自己）的最小值 ，也就是原序列中该元素后k个（包含自己）的最小值
for(int i=1;i<=n;i++){
while(hh<=tt&&q2[hh]<i-k) hh++;
while(hh<=tt&&a[q2[tt]]>=a[i]) tt--;
q2[++tt]=i;
ans2[n-i+1]=a[q2[hh]];
}
for(int i=1;i<=n;i++) cout<<min(ans1[i],ans2[i])<<' '; //该元素前k个元素和后k个元素（包含自己）中的最小值，即[i-k,i+k]中的最小值
return 0;
}
第十二题
对唐三用bfs跑一个最短路，对比比东跑一个附近环，看唐三能不能比比比东先到附近环。
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define LL long long
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl "\n"
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int mod = 1e9 + 7;
const int P = 998244353;
const int INF = 0x3f3f3f3f;
const int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 2e5 + 10 , M = 2e6;
int ne[M],e[M],h[N],idx;
int n,a,b;
int root;
void add(int a , int b)
{
e[idx] = b, ne[idx] = h[a] ; h[a] = idx++;
}
vector<int> bfs(int x)
{
vector<int> dis(n,-1);
queue<int>q;
q.push(x);
dis[x] = 0;
while(q.size())
{
auto u = q.front();
q.pop();
for(int i = h[u] ; ~i ; i = ne[i])
{
int v = e[i];
if(dis[v] == -1)
{
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis;
}
void dfs(vector<int> &dis,vector<bool> &st,vector<int> &par,vector<int> &dfn,int x)
{
st[x] = true;
for(int i = h[x] ; ~i ; i = ne[i])
{
int j = e[i];
if(!st[j])
{
par[j] = x;
dfn[j] = dfn[x] + 1;
dfs(dis,st,par,dfn,j);
}else if(dfn[j] < dfn[x] - 1) {
for(int k = x ; ; k = par[k])
{
if(root == -1 || dis[root] > dis[k])
root = k;
if(k == j) break;
}
}
}
}
void solve()
{
memset(h,-1,sizeof h);
idx = 0;
cin >> n >> a >> b;
a--,b--;
for(int i = 0 ; i < n ; i ++)
{
int u,v;
cin >> u >> v;
u--,v--;
add(u,v),add(v,u);
}
root = -1;
auto dis = bfs(b);
vector<bool> st(n);
vector<int>par(n),dfn(n);
dfs(dis,st,par,dfn,0);
if(bfs(root)[a] > dis[root]) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//cout.precision(10); cout.setf(ios::fixed);
int t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}
第十三题
一个有 n 个选项的类似于石头剪刀布游戏，胜负关系为一个环，问每局玩 m 轮的情况下，双方绝顶聪明下获胜的概率。可以发现，在第一轮赢了的情况下，只需要保证后面每一轮都是平局就可以赢。因为不能连续出一样的，所以上一轮如果没有输，就存在必定不会输的选项。所以第一轮赢了一定能赢。如果第一轮是平局的情况，一种比较显然的想法是两人的选项都存在一个只能输或平，一个只能赢或平，只能输或平的选项不严格的劣于只能平或赢的选项，所以不选这个。然后考虑到对方也有可以排除的选项，所以自己的一个选项因为对方的排除变为只能输或平，继续进行排除，多轮后只剩下最初的只能平或赢的选项。所以在第一轮平局的情况下，双方只能继续平局。可以注意到这样的排除选项是不严格的，例如有四个选项，都不能选第四个，这时采取 1/2 的概率选第一个，1/2 的概率选第三个，也可以做到最优的期望，但因为输或平的选项和赢或平的选项只有在平局的情况下才相等，所以类似的决策之间仍然是平局。所以第一轮的获胜概率就是整一局的获胜概率，为 1/n，直接输出即可。
#include"stdio.h"
main()
{
int n,m;
scanf("%d%d",&n,&m);
printf("1");
printf("/%d",n);
}
京公网安备 11010502036488号