2024zzuacm新生选拔赛第一场

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}}mod2=0$ , 即所有的数的下标都是$2^i$的倍数，那么进行k次操作后，丁丁会留下下标为$2^k,2\ast 2^k,3\ast 2^k,...$的数。

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

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

代码

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$, 满足$0\le x<998244353$ , 并且$N-x$ 是$998244353$的倍数。

思路

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

注意负数取余会得到负数，所以必须在取余数的结果上加上$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$ , 使得$x\times y$ 最大

思路

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

1. 两个正数相乘
2. 两个负数相乘

于是我们输出$a\times c$ 和$b\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。那么我们从$L1+L2$ 开始枚举最多10个数就可以找到最适合的$x+y$ 。

于是我们计算$f(L1+L2),f(L1+L2+1),...,f(L1+L2+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$个。

我们逆序遍历数组，找到最后一个满足$a[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个数为结尾的 连续子数组的最大的和 ， 那么我们的答案就是$ma{x}_{1\le i\le n}{f}_i$ , 我们在枚举$i$的时候，考虑两种情况

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

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

于是最终的递推式为$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(nlogn)$ 排序算法来更快的解决问题。

代码

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(nlogn)$

#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\ne 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!\ast 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!\ast 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))