当前位置：首页 > news >正文

2024zzuacm新生选拔赛第一场

news 2025/6/27 10:58:25

2024zzuacm新生选拔赛第一场https://ac.nowcoder.com/acm/contest/92409

python代码源自我有异议症QAQ

A - 降智视频

题意

起初有n个数都在丁丁手中，进行如下操作k次：

豆豆从丁丁手中拿走标号为奇数的数。
对丁丁的其他的数进行重新标号。

问进行k次之后，豆豆和丁丁各自有多少个不同的数

思路

思路一：每次豆豆都会从丁丁手中拿走第奇数个数，如第 1,3,5,7,..等。

之后对丁丁手中的数重新标号，可以发现新的标号恰好为原先标号的 $\frac{1}{2}$ 。如4 -> 2 , 8 -> 4, 2 -> 1 。

于是我们进行分析可以发现，对于第 $i$ 次操作，豆豆会从丁丁手中拿走除以 $2^{i-1}$ 是奇数的数。那么留下的数的下标 $x$ 都会满足 $\frac{x}{2^{i-1}} \ mod\ 2 = 0$ , 即所有的数的下标都是 $2^i$ 的倍数，那么进行k次操作后，丁丁会留下下标为 $2^k, 2 * 2^k,3 *2^k,...$ 的数。

我们便可以直接获取豆豆和丁丁最终的数，然后对其进行计数，就可以得出各自有多少种类的数。时间复杂度 $O (n)$

思路二：可以发现，最多 $log_2n$ 次操作豆豆就可以把丁丁的数全部拿完，那么我们可以直接模拟这个拿数的过程 , 时间复杂度为 $O (n l o g n)$

代码

C思路一

#include<stdio.h>
int vis1[1000005];
int vis2[1000005];
int main(){int n,k;scanf("%d %d",&n,&k);if(k > 20) k = 20;int mod = (1<<k);for(int i= 1;i<=n;i++){int x;scanf("%d",&x);if(i%mod==0){vis1[x] = 1;}else{vis2[x] = 1;}}int cnt1 = 0;int cnt2 = 0;for(int i = 1;i<=n;i++){if(vis1[i]) cnt1++;if(vis2[i]) cnt2++;}printf("%d %d",cnt2,cnt1);return 0;
}

C思路二

#include<stdio.h>
int A[1000005];
int cntA;
int B[1000005];
int cntT;
int cntB;
int vis1[1000005];
int vis2[1000005];
int main(){int n,k;scanf("%d %d",&n,&k);cntA = n;for(int i =1;i<=n;i++){scanf("%d",&A[i]);}while(k--){int new_cntA = 0;for(int i = 1;i<=cntA;i++){if(i%2 == 1) B[++cntB] = A[i];else A[++new_cntA] = A[i];}cntA = new_cntA;if(cntA == 0) break;}for(int i = 1;i<=cntA;i++){vis1[A[i]] = 1; }for(int i = 1;i<=cntB;i++){vis2[B[i]] = 1; }int cnt1=0,cnt2=0;for(int i = 1;i<=n;i++){if(vis1[i]) cnt1++;if(vis2[i]) cnt2++;}printf("%d %d",cnt2,cnt1);return 0;
}

python

n,k = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]if k>=20 :s = set()for i in range(n):s.add(c[i])print(len(s),0)
else :s1 = set()s2 = set()for i in range(n):if((i+1)%pow(2,k)==0):s1.add(c[i])else :s2.add(c[i])print(len(s2),len(s1))

B - 还在分糖果！

题意

对于所有的正整数，取走包含7的数之后，问第n个数是多少。

思路

如果大家没有头绪，不妨将取走7 替换为取走9 ，这样我们观察数据，发现变成了1,2,3,4,5,6,7,8,10 , 从原先的“十进制” 变为了“九进制” ，于是发现本题其实就是 十进制转换为九进制 的进制转换。只不过本题删去的不是9，而是7 ，我们把转换后的九进制中的7替换为8 , 8替换为9即可

代码

C

#include<stdio.h>
char ans[1000005];
int len = 0;
void solve(){long long n;scanf("%lld",&n);len = 0;while(n){int x = n%9;if(x >= 7) x ++;ans[++len] = char(x + '0');n /= 9;}for(int i = len;i>=1;i--){putchar(ans[i]);}puts("");
}
signed main(){int T;scanf("%d",&T);while(T--){solve();}return 0;
}

python

T = int(input())
for i in range(T):n = int(input())ans = ''while n>0:t = n%9n //= 9if t>=7:t += 1ans += chr(ord('0')+t)print(ans[::-1])

C - 数论难题

题意

给出一个数 $N$ ，找到一个数 $x$ , 满足 $\le x < 998244353$ , 并且 $N - x$ 是 $998244353$ 的倍数。

思路

本题题意等价于，求 $\ mod \ 998244353$ 的结果，（其中 $m o d$ 表示取余运算），直接输出即可。

注意负数取余会得到负数，所以必须在取余数的结果上加上 $998244353$ 。

代码

C

#include<stdio.h>
int main(){long long n;scanf("%lld",&n);int mod = 998244353;printf("%lld",(n%mod + mod)%mod);return 0;
}

python

n = int(input())
mod = 998244353
print(n%mod)

D - 数论简单题

题意

给你两个区间[a,b] ,[c,d] ，从中分别选择一个数 $x, y$ , 使得 $\times y$ 最大

思路

本题中可能会出现两个负数取值的情况，但如果想要得到最大值，那么无非就是

两个正数相乘
两个负数相乘

于是我们输出 $\times c$ 和 $\times d$ 两个答案中的最大值即可。

代码

C

#include<stdio.h>
int main(){long long a,b,c,d;scanf("%lld%lld%lld%lld",&a,&b,&c,&d);if(a * c < b * d){printf("%lld\n",b * d);}else{printf("%lld\n",a * c);}return 0;
}

python

a,b,c,d = [int(i) for i in input().split()]
print(max(max(a*c,a*d),max(b*d,b*c)))

E - 最大数

题意

给定两个区间[L1,R1] , [L2,R2] , 从中各自选择一个数 $x, y$ ,使得 $x + y$ 中的最大数位 尽可能大。

思路

首先可以得知，对于一个数位，他最大为9。那么我们从 $L 1 + L 2$ 开始枚举最多10个数就可以找到最适合的 $x + y$ 。

于是我们计算 $f (L 1 + L 2), f (L 1 + L 2 + 1), ..., f (L 1 + L 2 + 9)$ ,取其中的最大值即可。

代码

C

#include<stdio.h>
int f(int x){int ans = 0;while(x){int t = x % 10;ans = (ans > t) ? ans : t; x/=10;}return ans;
}
void solve(){int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);int l = l1+l2;int r = r1+r2;int ans = 0;for(int i = l;i<=r;i++){int fi = f(i);ans = ans > fi ? ans : fi;if(ans == 9) break;}printf("%d\n",ans);
}
int main(){int T = 1;scanf("%d",&T);while(T--){solve();}return 0;
}

python

T = int(input())def check(x):ans = 0while(x>0):ans = max(ans,x%10)x //= 10return ansfor i in range(T):la,ra,lb,rb = [int(i) for i in input().split()]if(ra-la>9 or rb-lb>9):print(9)else :ans = 0for i in range(la,ra+1):for j in range(lb,rb+1):ans = max(ans,check(i+j))print(ans)

F - 个位数口算

题意

输出 $3^n$ 的个位数。

思路

找规律可以发现，对于 $3 ^ 1, 3^2 ,3^3,3^4,...$ 他们的个位数为 $3, 9, 7, 1, 3, 9, 7, ...$ 即[3,9,7,1] 循环

于是我们对 $n$ 取余 $4$ 就可以得到结果。

另：如果你没有找到规律，也可以用快速幂直接计算出 $3^n$ 对 $10$ 取余的结果

代码

C

#include<stdio.h>
int main(){long long n;scanf("%lld",&n);putchar("3971"[(n-1)%4])return 0;
}

python

n = int(input())
print('3971'[(n-1)%4])

快速幂

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int qpow(int x,int n){int ans = 1;while(n){if(n&1) ans = ans * x % 10;x = x * x % 10;n>>=1;}return ans;
}
void solve(){int n;cin>>n;cout<<qpow(3,n);
}
signed main(){int T = 1;// cin>>T;while(T--){solve();}return 0;
}

# G - ASCII大小写转换

题意

给一个字符串 $s$ ,将其中的大写字母转换为小写字母，小写字母转换为大写字母

思路

对于一个小写字母，我们这样转换为大写字母： s[i] = s[i] - 'a' + 'A'

大写字母转换为小写字母同理s[i] = s[i] - 'A' + 'a'

代码

C

#include<stdio.h>
int main(){char ch;while(~scanf("%c",&ch)){if(ch == '\n') break;if('a' <= ch && ch <= 'z') putchar(char(ch - 'a' + 'A'));else putchar(char(ch - 'A' + 'a'));}return 0;
}

python

s = input()
ans = ''
for ch in s:ans += chr(ord(ch)^32)
print(ans)

H-index

题意

给出n个数， $a_1,a_2,...,a_n$ , 请你找出一个最大的数 $N$ , 满足a中大于等于N的数至少为N个

思路

思路一：我们使用一个数组cnt记录一下每个数出现的次数。即cnt[a[i]]+= 1 。

然后逆序查找从 $10^6$ 到 $1$ 的每个数，查看是否满足条件，那么第一个满足条件的 $i$ 即为答案。

条件为 $\sum_{j = i}^n cnt[j] \ge i$

思路二：对数组a进行逆序排序，这样就得出了以下规律： $a$ 数组中大于等于 $a [i]$ 的数有 $i$ 个。

我们逆序遍历数组，找到最后一个满足 $\ge i$ 的 $i$ 即可。

代码

C思路一

#include<stdio.h>
int cnt[1000006];
int main()
{int n;scanf("%d",&n);for(int i =1;i<=n;i++){int x;scanf("%d",&x);cnt[x]++;}int sum = 0;for(int i = 1000000;i>=0;i--){sum += cnt[i];if(sum >= i) {printf("%d",i);return 0;}}return 0;
}

C++思路二

#include<bits/stdc++.h>
using namespace std;
int a[1000006];
int main(){int n;cin>>n;for(int i = 1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);reverse(a+1,a+n+1);for(int i = 1;i<=n;i++){if(a[i] < i){cout<<i-1<<endl;break;}}return 0;
}

python

n = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse=True)def check():for i in range(n):if(a[i]<i+1):return i;return nprint(check())

I - 飞云鸽鸽的和式

题意

给你一个数组，请你找出其中一段连续的区间，使得区间中的数的总和尽可能大。

思路

思路一：本题给的 $n$ 很小，我们直接暴力枚举即可。复杂度 $O(n^3)$

思路二：如果我们加上一点前缀和的思想，在确认左端点，枚举右端点的时候，可以借用上一次的答案。这样就省去了第三重循环，复杂度 $O(n^2)$

思路三：如果我们再加上动态规划的思想，我们令 $f_i$ 表示 以第i个数为结尾的连续子数组的最大的和 ，那么我们的答案就是 $max_{1 \le i \le n} f_i$ , 我们在枚举 $i$ 的时候，考虑两种情况

加入 $f_{i-1}$ 对应的那一段
单独成为一段

当然取其中较大值是更好的。

于是最终的递推式为 $f_i = max(f_{i-1} + a_i,a_i)$

时间复杂度为 $O (n)$

代码

C 思路一 $O(n^3)$

#include<stdio.h>
int a[105];
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int ans = 0xcfcfcfcf;//足够小的数for(int i = 1;i<=n;i++){for(int j = i;j<=n;j++){int sum = 0;for(int k = i;k<=j;k++){sum += a[k];}if(ans < sum) ans = sum;}}printf("%d",ans);
}

C思路二 $O(n^2)$

#include<stdio.h>
int a[105];
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int ans = 0xcfcfcfcf;//足够小的数for(int i = 1;i<=n;i++){int sum = 0;for(int j = i;j<=n;j++){sum += a[j];if(ans < sum) ans = sum;}}printf("%d",ans);
}

C思路三O(n)

#include<stdio.h>
int a[105];
int f[105];
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int ans = 0xcfcfcfcf;//足够小的数f[0] = 0xcfcfcfcf;for(int i = 1;i<=n;i++){if(f[i-1] < 0) f[i] = a[i];else f[i] = f[i-1] + a[i];if(ans < f[i]) ans = f[i];}printf("%d",ans);
}

python

n = int(input())
a = list(map(int, input().split()))
mi = 0
pre = 0
ans = -1000000000
for i in range(n):pre += a[i]ans = max(ans,pre-mi)mi = min(mi,pre)
print(ans)

J - 排队

题意

给一个数组 $a$ , 对数组 $a$ 进行排序

思路

模板题，写对排序代码即可，

本题数据范围较小，使用朴素的 $O(n^2)$ 排序算法也可以通过本题。

同时也可以使用进阶的 $O (n l o g n)$ 排序算法来更快的解决问题。

代码

C 冒泡排序 $O(n^2)$

#include<stdio.h>
int a[5005];
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i = 1;i<=n;i++){for(int j = i;j<=n;j++){if(a[i] > a[j]){int t = a[i];a[i] = a[j];a[j] = t;}}}for(int i = 1;i<=n;i++){printf("%d ",a[i]);}return 0;
}

C++ 排序函数 $O (n l o g n)$

#include<bits/stdc++.h>
using namespace std;
int a[5005];
int main(){int n;cin>>n;for(int i = 1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);for(int i = 1;i<=n;i++){cout<<a[i]<<" ";}
}

python

n = int(input())
a = [int(i) for i in input().split()]a.sort()
for i in range(n):print(a[i],end=' ')

K - 飞云鸽鸽在送信

题意

对于所有长度为 $n$ 的排列 $p$ , 问满足 : 对于所有的 $1\le i \le n$ , 都有 $p_i \not= i$ 的排列有多少。

（排列指数组[1,2,3,...,n] 随机打乱后的数组，如长度为 $3$ 的排列有：[1,2,3] 、[1,3,2] 、 [2,1,3] 、[2,3,1] 、[3,1,2]、[3,2,1] ，长度为n的排列共有 $A_n^n$ 个）

思路

本题考察“错排数”，为经典组合数学问题，大家可以上网搜索相关内容。

本题给出的 $n$ 很小，暴力枚举所有的排列即可。

在C++中可以调用排列函数来生成长度为 $n$ 的全排列。

使用全排列的复杂度是 $O (n! * n)$

下面给出更好的解法（时间复杂度 $O (n)$ )

错排数的递推式为$ f_n = \left{
\begin{array}{lr}
0 & n = 1 \
1& n = 2\
(f_{n-1} + f_{n-2}) * (n-1) &, n \ge 3
\end{array}
\right. $

对于 $n$ 等于 $1$ 和 $2$ ，递推式很明显成立 ,对于n大于2的情况，我们考虑n的位置，

如[2,1,4,3，*5*] ，前面的[2,1,4,3] 是一个长度为4的错排序，那么这个5可以放在前面四个位置中的任意一个。（ $n - 1$ 种可能）

假设我们放在数字 $1$ 的位置, [2,*5*,4,3,*1*] 此时数字1和数字5一定是满足条件的。

此时我们可以选择5是否要和“下标为1的数”交换位置

如果交换位置[*5*,2,4,3,*1*]，那么剩余n-2个数可以任意组合为错排序，方案数为 $f_{n-2}$
如果不交换位置[2,*5*,4,3,1]，那么剩下的n-1个数都可以任意组合为错排序，方案数为 $f_{n-1}$

代码

C全排列

#include<stdio.h>
int vis[15];
int a[15];
int t = 0;
int n;
int ans = 0;
void dfs(int step){if(step == n+1){for(int i = 1;i<=n;i++){if(a[i] == i) return;}ans ++;return;}for(int i = 1;i<=n;i++){if(vis[i]) continue;vis[i] = 1;a[step] = i;dfs(step+1);vis[i] = 0;}return ;
}
int main(){scanf("%d",&n);dfs(1);printf("%d\n",ans);return 0;
}

C++ 调用排列函数 $O (n! * n)$

#include<bits/stdc++.h>
using namespace std;
int a[15];
int main(){int n;cin>>n;for(int i = 1;i<=n;i++){a[i] = i;}int ans = 0;do{bool ok = 1;for(int i = 1;i<=n;i++){if(a[i] == i) ok = 0;}if(ok) ans ++;}while(next_permutation(a+1,a+1+n));cout<<ans;return 0;
}

C递推 $O (n)$

#include<stdio.h>
int f[1000005];
int main(){int n;scanf("%d",&n);f[1] = 0;f[2] = 1;for(int i =3;i<=n;i++){f[i] = (i-1) *(f[i-1] + f[i-2]);}printf("%d",f[n]);return 0;
}

python

n = int(input())def cp(n):if n==1:return 0if n==2:return 1return (n-1)*(cp(n-1)+cp(n-2))print(cp(n))

L - P19E99喜欢16进制

题意

给一个十六进制数，输出他的十进制表示

思路

用字符串读取十六进制数，然后枚举十六进制数，然后不断累加到答案上即可。

代码

C

#include<stdio.h>
int main(){char ch;long long ans = 0;while(~scanf("%c",&ch)){if(ch == '\n') break;int x;if('0' <= ch && ch <= '9'){x = ch - '0';}else{x = ch - 'a' + 10;}ans = ans * 16 + x;}printf("%lld",ans);return 0;
}

python

s = input()
print(int(s,16))