【题解】CDTU宜宾校区第一届大学生程序设计竞赛题解(C/C++)

这次比赛题目还是具有一定思维性和技巧性也比较强,大家不要灰心,加油!

部分同学对于时间的规划以及做题决策有较大的提升空间。

第一题 入门修仙

#include <stdio.h>

int main(){
    printf("CDTU YYDS 1913~2022!");
    return 0;
}

第二题 进制转换

答案1042,具体计算方法不多说,也可以用计算器算

第三题 逃命

答案6 S->J->B->A,贪心策略,不多说

第四题 最长连续不下降的温度

题目很简单,有特殊点要处理而已

#include <iostream>
#include <cstring>
using namespace std;

int main(){
    long long n;
    cin>>n;
    if(n==1){
        cout<<1;
        return 0;
    }
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    int dp[n];
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    int max=-0x3f3f3f;
    for(long long i=1;i<n;i++){
        if(a[i]>=a[i-1]){
            dp[i]=dp[i-1]+1;
            if(dp[i]>max)max=dp[i];
        }
        else dp[i]=1;

    }
    cout<<max;
}

第五题 Ultraman

纯属找规律

#include<bits/stdc++.h>
using namespace std;
int main()
{
    unsigned long long n,p,k;
    cin>>n>>p>>k;
    cout<<(p*k)%n;
    return 0;
}

第六题 来自霍格沃兹的骰子

这个题有个坑,就是一次都不抽,拿就不变啊!

这里来说一下这道题的思想

假设初始值为a[i],我们要抽k次,每次一定要是最大值

那么我们可以想一想,如果k的值小于a[i]呢?那取k次最大后,最后的数会不会就是6-k,如果大于a[i]的话,那我们肯定也会抽k次,但是其中有一次肯定是a[i],所以这个数一定会是6-k+1,所以最后的结果智慧与 a[i]和k的大小差值有关,而和a[i]本身无关。

#include <iostream>
using namespace std;
int a[6],k;
int main(){
    for(int i=0;i<6;i++)cin>>a[i];
    cin>>k;
    if(k)
    for(int i=0;i<6;i++)cout<<6-k+(a[i]>6-k?0:1)<<(i==5?"":" ");
    else for(int i =0;i<6;i++)cout<<a[i]<<(i==5?"":" ");
    return 0;
}

第七题 原神出金

递归版

#include <iostream>
using namespace std;
int get(int k){
    if(k==1)return 1;
    return k*get(k-1)%328;
}
int main(){
    int k;
    cin>>k;
    cout<<get(k)%328;
}

循环版:

#include <iostream>
using namespace std;

int main()
{
    long long n;
    cin>>n;
    int sum=1;
    for (int i = 1; i <= n; ++i) {
        sum*=i;
        sum%=328;
    }
    cout<<sum;
}

第八题 自动收割机

用数组可以过70%的数据,全过得用哈希表

#include <iostream>
#include <map>
using namespace std;
map<string,long long> mp;
int main(){
        string a;
        while (cin >> a) {
            mp[a] += 1;
            if (getchar() == 10)break;
        }
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            string a;
            cin >> a;
            cout << mp[a] << endl;
        }
}

第九题 矩阵乘法

考察循环嵌套

#include <bits/stdc++.h>
#define mm(a) memset(a,0,sizeof(a))
using namespace std;

int main()
{
        int n, m, n1, m1;
        cin >> n >> m;
        int a[n+1][m+1];
        mm(a);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; ++j) {
                cin >> a[i][j];
            }
        cin >> n1 >> m1;
        int b[n1 + 10][m1 + 10];
        int c[n+10][m1+10];
        mm(b);
        mm(c);
        for (int i = 1; i <= n1; i++)
            for (int j = 1; j <= m1; ++j) {
                cin >> b[i][j];
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m1; ++j) {
                for (int k = 1; k <= m1; k++) {
                    c[j][i] += a[i][k] * b[k][j];
                }
            }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m1; ++j) {
                cout << c[i][j] << " ";
            }
            cout << endl;
        }
    
    return 0;
}

第十题 不定的斐波那契

算几组数据就能发现规律,奇数的值是-1,偶数的值是1,然后字符串处理即可,这里用的位运算判断奇偶性,位运算可以看我另外的文章

#include <iostream>
using namespace std;

int main(){
    string s;
    cin>>s;
    cout<<(((s[s.length()-1]-'0')&1)?-1:1);
    return 0;
}

第十一题 素数三元组

#include <iostream>
using namespace std;

const int N = 1010;
int f[N],cnt,res;

int is_prime(int n)
{
    if(n < 2) return 0;
    for(int i=2;i<=n/i;i++)
        if(n % i == 0) return 0;
    return 1;
}

int main()
{
    int m,n;
    cin >> m >> n;
    if(n<m){
        cout<<-1;
        return 0;
    }
    for(int i=m;i<=n;i++)
    {
        if(is_prime(i)) f[cnt ++ ] = i;
    }
    for(int i=0;i<cnt;i++)
    {
        for(int j=i + 1;j<cnt;j++)
        {
            for(int k=j + 1;k<cnt;k++)
            {
                if(is_prime(f[i] * f[j] + f[k])
                   &&is_prime(f[j] * f[k] + f[i])
                   &&is_prime(f[k] * f[i] + f[j]))
                    res ++;
            }
        }
    }
    cout << res;
    return 0;
}

第十二题 Three Bei

中等题的第一题,二维前缀和,本来打算卡时间,但想想算了

#include <iostream>
using namespace std;
int arr[1000];
int main(){
    string s;
    cin>>s;
    for(int i=1;i<=s.length();i++){
        if(isdigit(s[i-1]))
        arr[i]=arr[i-1]+s[i-1]-'0';
        else{
            cout<<"F";
            return 0;
        }

    }
    int ans=0;
    for(int i=1;i<=s.length();i++){
        for (int j = i; j <= s.length(); ++j) {
            if((arr[j]-arr[i-1])%3)continue;
            ans++;
        }
    }
    cout<<"T\n"<<ans;
    return 0;
}

如果最优解的话可以参考 蓝桥杯原题 - k倍区间,题目虽然不同,但大意相同

第十三题 重复数字

循环嵌套绝对爆

用循环嵌套绝对会爆,由于位运算:异或 的一些性质

0^A=A

A^A=0

所以,我们可以构造一个1~n的连续数组,和原数组相异或,最后留下来的那个就是重复的数字

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long T;
    cin>>T;
    while(T--){
        long long x;
        long long p=0;
        long long len=0;
        while(true){
            scanf("%d",&x);
            char c= getchar();
            p^=x^=len++;
            if(c==10)break;

        }
        printf("%03lld\n",p);
    }
    return 0;
}

第十四题 子串和

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
string s;
long long int i,j,w[100001],ennu[100001],ans=0,ls;

int main()
{
	int indexx[27];
	cin>>s;
	ls=s.length();
	for(i=0;i<=27;i++)
	{
		indexx[i]=0;
	}
	for(i=ls;i>0;i--)
	{
		//s[i+1]=s[i];
		ennu[i]=s[i-1]-'`';
	}
	for(i=1;i<=ls;i++)
	{
		w[i]=i*(ls-i+1);
	}
	for(i=1;i<=ls;i++)
	{
		if(!indexx[ennu[i]])
		{
			ans+=w[i];
		}
		else
		{
			ans+=w[i]-((w[i]/i)*indexx[ennu[i]]);
		}
		indexx[ennu[i]]=i;
	}
	cout<<ans;
	return 0;
}

第十五题 找到所有小辈

可以用深搜,本题有GPLT L2题目改编,深搜广搜的方法可以百度,这里给出Dj算法题解

#include <iostream>
#include <set>
#include <cstring>
#include <vector>
#define INF 0x3f3f3f
using namespace std;
set<pair<int,int>,less<pair<int,int> > >s;
typedef struct edge{
    int to,w,next;
}E[1000000];
E e;
int head[1000000];
long long _size=0;
void add(int u,int v,int w){
    e[_size]={v,w,head[u]};
    head[u]=_size++;
}
bool book[1000000];
int dist[1000000];

void init(){
    memset(head,-1,sizeof(head));
    memset(dist,INF,sizeof(dist));
}
int main(){
    int max=-0x3f3f3f;
    init();
    int n;
    cin>>n;
    int u=1;
    int pk=0;
    while(u<=n){
        int v;
        cin>>v;
        if(v==-1)v=0,pk++;
        add(v,u,1);
        u++;
    }
    dist[0]=0;
    s.insert({0,0});
    for(int i=0;i<n;i++){
        int u=s.begin()->second;
        book[u]=true;
        s.erase(*s.begin());
        for(int j=head[u];j+1;j=e[j].next){
            int v=e[j].to;
            if(!book[v]&&dist[v]>dist[u]+e[j].w){
                s.erase({dist[v],v});
                dist[v]=dist[u]+e[j].w;
                s.insert({dist[v],v});
                if(max<dist[v]) max=dist[v];
            }
        }
    }
    vector<int> q;
    for(int i=0;i<=n;i++){
        if(dist[i]==max)q.push_back(i);
    }
    if (pk>1)max--;
    cout<<max<<endl;
    for(int i=0;i<q.size()-1;i++) cout<<q[i]<<" ";
    cout<<q[q.size()-1];
}

第十六题 对峙

GPLT L2题目改编,考察知识点:并查集

#include <bits/stdc++.h>
using namespace std;
int a[101],mp[101][101];
void init(){
    for (int i = 0; i < 101; ++i) {
        a[i]=i;
    }
}
int find(int x){
    if(a[x]==x) return x;
    return a[x]=find(a[x]);
}

void merrge(int x,int y){
    if(find(x)==find(y))return ;
    a[find(x)]= find(y);
}

int main(){
    init();
    int n,m,k;
    cin>>n>>m>>k;
    for (int i = 0; i < m; ++i) {
        int u,v,w;
        cin>>u>>v>>w;
        if(w==1)merrge(u,v);
        else mp[u][v]=mp[v][u]=-1;
    }
    for (int i = 0; i < k; ++i) {
        int u,v;
        cin>>u>>v;
        bool f1= find(u)== find(v);
        bool f2= mp[u][v];
        if(f1&&f2) cout<<"OK but..."<<endl;
        else if(f1) cout<<"No problem"<<endl;
        else if(f2) cout<<"No way"<<endl;
        else cout<<"OK"<<endl;
    }
}

第十七题 CBT的层序遍历

#include <iostream>
using namespace std;
int N;//树中结点个数

int tree[35];
void hfind(int i=1){
    if(i>N) return;
    hfind(i<<1);
    hfind((i<<1)+1);
    cin>>tree[i];
}
int main(){
    cin>>N;
    hfind();
    for(int i=1;i<N;i++)
        cout<<tree[i]<<" ";
    cout<<tree[N];
    return 0;
}

第十八题 拔网线

图的最小生成树模板题,这里是Kruskal算法解析

#include <iostream>
#include <algorithm>
#include <vector>
#define v(p) vector<p>
#define add(u,v,w) e[e_size++]={u,v,w}//加边
using namespace std;
/*
边集数组存图
*/
typedef struct edge{
    int u,v,w;
    bool operator<(const edge &a)const {
        return w<a.w;
    }
}E[10001];
E e;
int e_size;//当前已存储边长
//加边的话直接用define,一句话没必要写函数,节省空间
bool cmp(struct edge a,struct edge b){
    return a.w<b.w;
}

/*
	并查集代码
*/
int a[10001];//并查集数组
//找祖宗,并把祖上几代都变成和自己同样的祖一代
int find(int x){
    if(a[x]==x)return x;
    return a[x]=find(a[x]);
}
//集合的合并,让x认y为爹,如果两个集合在同一个集合内,返回false,否则返回true
bool merrge(int x,int y){
    int in_x=find(x);
    int in_y=find(y);
    if(in_x==in_y)return false;
    a[in_x]=in_y;
    return true;
}
//初始化函数
void init(){
    //初始化代码
    //初始化并查集
    for(int i=0;i<10001;i++)a[i]=i;
    return;
}

int main(){
    init();//根据要求初始化
    int n,m,sum=0;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        sum+=w;
    }
    int cnt=0;//记边数
    sort(e,e+m);
    for(int i=0;i<m;i++){
        if(merrge(e[i].u,e[i].v)){
            sum-=e[i].w;
            if(++cnt==n-1)break;
        }
    }
    cout<<sum;
    return 0;
}

第十九题 超人小E

考察知识点:Dj算法 扩展欧几里得求逆元

#include <iostream>
#include <cstring>
#include <set>
#define INF 0x3f3f3f3f
using namespace std;
int cs=10;
/**
 *扩展欧几里得算法
 * @param a 数a
 * @param b 数b
 * @param x 代入方程中的x
 * @param y 代入方程中的y
 * @return a和b的最大公因数以及 x和y的解
 */
long long exgcd(int a,int b,int &x,int &y){
    if (b==0)   return x=1,y=0,a;
    long long t=x;
    x=y;
    y=t-a/b*y;
    return exgcd(b,a%b,x,y);
}
/**
 * 快速幂算法
 * @param x 底数
 * @param y 质数
 * @param mod 取余数
 * @return 返回x的y次方与mod模运算的值
 */
long long qpow(long long x,long long y,long long mod){
    long long res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
/**存边结构体*/
typedef struct edge{
    int to,w,next;
}Edge[100001];
/**存边结构体数组*/
Edge e;
int _size;
/**结点存储数组*/
int head[100001];
/**
 * 加边函数
 * @param u 起点
 * @param v 终点
 * @param w 权值
 */
void add(int u,int v,int w){
    e[_size]={v,w,head[u]};
    head[u]=_size++;
}
/**
 * 迪杰斯特拉算法,单源最短路径
 * @param s 源点
 * @param dist 存储最短权值的数组
 * @param book 存储记事本(记录是否通过某个点松驰过)
 * @param dist_size 最短权值数组长度 请使用sizeof
 * @param len 数组大小
 */
void dj(int s,int dist[],bool book[],int dist_size,int len){
    memset(dist,INF,dist_size);
    memset(book,false,dist_size/4);
    dist[s]=0;
    book[s]=true;
    /**用min_heap存储离源点最近的点,first为权值,second为点的编号 */
    set<pair<int,int> >min_heap;
    min_heap.insert({0,s});
    for (int i = 0; i < len-1; ++i) {
        int u=min_heap.begin()->second;
        book[u]=true;
        min_heap.erase(*min_heap.begin());
        for (int j = head[u]; j+1 ; j=e[j].next) {
            int v=e[j].to;
            if (!book[v]&&dist[v]>dist[u]+e[j].w){
                min_heap.erase({dist[v],v});
                dist[v]=dist[u]+e[j].w;
                min_heap.insert({dist[v],v});
            }
        }
    }
}
/**计算距离*/
long long getInstence(int u,int v){
    int x,y;
    exgcd(u,v,x,y);
    return qpow(x,y,109110);
}
int main(){
    int n,m,cdtu,k;
    cin>>n>>m>>cdtu>>k;
    memset(head,-1,sizeof head);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        long long w=getInstence(u,v);
        add(u,v, w);
        add(v,u,w);
    }
    int dist[100001];
    bool book[100001];
    dj(cdtu,dist,book,sizeof(dist),n);
    for(int i=0;i<k;i++){
        int u,v;
        cin>>u>>v;
        int du=dist[u];
        int dv=dist[v];
        if (du>=INF) {
            du=0;
            if (cs)cs--;
            else{
                cout<<-1<<endl;
                continue;
            }
        }
        if (dv>=INF) {
            dv=0;
            if (cs)cs--;
            else{
                cout<<-1<<endl;
                continue;
            }
        }
        cout<<du+dv<<endl;
    }
}

第二十题 树的连通块

知识点:树形DP

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1005;
int n,m,k,x,y,l,o,r;
int nxt[maxn*2],last[maxn],to[maxn*2],Size[maxn],f[maxn][maxn],tmp[maxn],a[maxn];
vector <int> son[maxn];
void add(int x,int y)
{
    nxt[++l]=last[x];
    last[x]=l;
    to[l]=y;
}
bool cmp(int x,int y)
{
    return Size[x]<Size[y];
}
void dp(int u,int fa)
{
    vector<int>().swap(son[u]);
    for (int x=last[u];x;x=nxt[x])
    {
        int v=to[x];
        if (v==fa)  continue;
        dp(v,u);
        son[u].push_back(v);
    }
    sort(son[u].begin(),son[u].end(),cmp);
    if (a[u]>=o)    f[u][1]=1;
    Size[u]=1;
    for (int i=0,N=son[u].size();i<N;++i)
    {
        int v=son[u][i];
        memset(tmp,0,sizeof(tmp));
        for (int x=1;x<=Size[u];++x)
            for (int y=1;y<=Size[v];++y)
                tmp[x+y]=max(tmp[x+y],f[u][x]+f[v][y]);
        Size[u]+=Size[v];
        for (int x=1;x<=Size[u];++x)
            f[u][x]=max(f[u][x],tmp[x]);
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        r=max(r,a[i]);
    }
    for (int i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    l=0;
    while (l<r)
    {
        o=l+r+1>>1;
        memset(f,0,sizeof(f));
        dp(1,0);
        if (f[1][m]>=k) l=o;
        else    r=o-1;
    }
    printf("%d\n",l);
    return 0;
}
  • 微信或QQ扫一扫

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

目录