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);
}