题解 | CDTU宜宾校区第一届大学生程序设计竞赛题解
开启修仙之旅
https://ac.nowcoder.com/acm/contest/35455/A
这次比赛题目还是具有一定思维性和技巧性也比较强，大家不要灰心，加油！
部分同学对于时间的规划以及做题决策有较大的提升空间。
第一题 入门修仙
#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;
}
投递影石Insta360等公司7个岗位 >