2024zzuacm新生选拔赛第一场

🕗 发布于 2024-10-14 15:36 算法 数据结构 zzuacm新生选拔赛

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%9
        n //= 9
        if t>=7:
            t += 1
        ans += 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 = 0
    while(x>0):
        ans = max(ans,x%10)
        x //= 10
    return ans

for 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 = 0
        for 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 n

print(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 0
    if n==2:
        return 1
    return (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))

原文地址：https://blog.csdn.net/qq_66608435/article/details/142904905

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Qml 分组动画（二）动画嵌套（自学笔记）
下一篇：探索高效的 PDF 拆分工具及其独特功能

通过OpenCV实现 Lucas-Kanade 算法
在计算机视觉领域，光流估计是一种追踪物体运动的技术。它通过比较连续帧之间的像素强度变化来估计图像中每个像素的移动。本文将通过一个实际例子，使用Python和OpenCV库来展示光流估计的概念，特别是L
阅读更多2024-10-15
Linux系统：sudo systemctl reload apache2命令作用
Linux系统：sudo systemctl reload apache2命令作用
阅读更多2024-10-15
Tars RPC源码--C++客户端
客户端最重要的一个类，一个客户端只能生成一个Communicator类的实例，CommunicatorPtr& Application::getCommunicator(),获取线程安全的单例
阅读更多2024-10-15
you-get 使用出错 [error] oops, something went wrong.
you-get, 更新
阅读更多2024-10-15
算法笔记day03
这道题与上一道题类似，只不过换成了链表，只需要注意第一步一定要先将链表逆置，其他的步骤与上一题相同。同样也是一道模拟题，使用无进位相乘相加进行优化。使用数组将每一位都存储起来，最后统一处理进位。这就是
阅读更多2024-10-15
NVIDIA Bluefield DPU上的启动流程4个阶段分别是什么？作用是什么？
可以看到RSHIM实际上是Boot相关的集合。也能看到eMMC上的2个分区。Bluefield硬件单元图：（尤其可以看到RSHIM在硬件形态上是一个单独的硬件）ATF是主要的bootloader，用来
阅读更多2024-10-15
SQL语句规范及建议
主要针对mysql数据库的语句的规范及建议，可用于sql语句的审核规则 Summary: "不建议给列通配符'*'设置别名", Content: `例: "SELECT
阅读更多2024-10-15
Mysql(七) --- 索引
前面我们学习了，数据库的增删改查等操作，在数据库中，用的最多的业务就是查找，在现实生活中，我们会发现有很多的关键字会被经常查到，为了可以更加高效地进行查询，我们为此引出索引MySQL的索引是一种数据结
阅读更多2024-10-15
【Linux】【命令】查找(grep/find)与统计(wc)
Linux 下的查找命令：grep 和 find
阅读更多2024-10-15
Cesium 实战 - 自定义纹理材质 - 立体墙（旋转材质）
Cesium 实战 - 自定义纹理材质 - 立体墙（旋转材质）。
阅读更多2024-10-15

2024zzuacm新生选拔赛第一场

A - 降智视频

题意

思路

代码

C思路一

C思路二

python

B - 还在分糖果！

题意

思路

代码

C

python

C - 数论难题

题意

思路

代码

C

python

D - 数论简单题

题意

思路

代码

C

python

E - 最大数

题意

思路

代码

C

python

F - 个位数口算

题意

思路

代码

C

python

快速幂

# G - ASCII大小写转换

题意

思路

代码

C

python

H-index

题意

思路

代码

C思路一

C++思路二

python

I - 飞云鸽鸽的和式

题意

思路

代码

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

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

C思路三O(n)

python

J - 排队

题意

思路

代码

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

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

python

K - 飞云鸽鸽在送信

题意

思路

代码

C全排列

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

C递推 O ( n ) O(n) O(n)

python

L - P19E99喜欢16进制

题意

思路

代码

C

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

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

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

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

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

C递推 $O (n)$