无锡网站设计网站,网站推广计划渠道,资讯网站排版,郑州全面恢复正常2024zzuacm新生选拔赛第一场https://ac.nowcoder.com/acm/contest/92409
python代码源自我有异议症QAQ
A - 降智视频
题意
起初有n个数都在丁丁手中#xff0c;进行如下操作k次#xff1a;
豆豆从丁丁手中拿走标号为奇数的数。对丁丁的其他的数进行重新标号。
问进行k次…2024zzuacm新生选拔赛第一场https://ac.nowcoder.com/acm/contest/92409
python代码源自我有异议症QAQ
A - 降智视频
题意
起初有n个数都在丁丁手中进行如下操作k次
豆豆从丁丁手中拿走标号为奇数的数。对丁丁的其他的数进行重新标号。
问进行k次之后豆豆和丁丁各自有多少个不同的数
思路
思路一每次豆豆都会从丁丁手中拿走第奇数个数如第 1,3,5,7,..等。
之后对丁丁手中的数重新标号可以发现新的标号恰好为原先标号的 1 2 \frac{1}{2} 21 。 如4 - 2 , 8 - 4, 2 - 1 。
于是我们进行分析可以发现 对于第 i i i次操作豆豆会从丁丁手中拿走除以 2 i − 1 2^{i-1} 2i−1 是奇数的数。那么留下的数的下标 x x x都会满足 x 2 i − 1 m o d 2 0 \frac{x}{2^{i-1}} \ mod\ 2 0 2i−1x mod 20 , 即所有的数的下标都是 2 i 2^i 2i的倍数那么进行k次操作后丁丁会留下下标为 2 k , 2 ∗ 2 k , 3 ∗ 2 k , . . . 2^k, 2 * 2^k,3 *2^k,... 2k,2∗2k,3∗2k,...的数。
我们便可以直接获取豆豆和丁丁最终的数然后对其进行计数就可以得出各自有多少种类的数。时间复杂度 O ( n ) O(n) O(n)
思路二可以发现最多 l o g 2 n log_2n log2n次操作豆豆就可以把丁丁的数全部拿完那么我们可以直接模拟这个拿数的过程 , 时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
代码
C思路一
#includestdio.h
int vis1[1000005];
int vis2[1000005];
int main(){int n,k;scanf(%d %d,n,k);if(k 20) k 20;int mod (1k);for(int i 1;in;i){int x;scanf(%d,x);if(i%mod0){vis1[x] 1;}else{vis2[x] 1;}}int cnt1 0;int cnt2 0;for(int i 1;in;i){if(vis1[i]) cnt1;if(vis2[i]) cnt2;}printf(%d %d,cnt2,cnt1);return 0;
}C思路二
#includestdio.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;in;i){scanf(%d,A[i]);}while(k--){int new_cntA 0;for(int i 1;icntA;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;icntA;i){vis1[A[i]] 1; }for(int i 1;icntB;i){vis2[B[i]] 1; }int cnt10,cnt20;for(int i 1;in;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 k20 :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((i1)%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
#includestdio.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;i1;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 n0:t n%9n // 9if t7:t 1ans chr(ord(0)t)print(ans[::-1])C - 数论难题
题意
给出一个数 N N N 找到一个数 x x x, 满足 0 ≤ x 998244353 0 \le x 998244353 0≤x998244353 , 并且 N − x N - x N−x 是 998244353 998244353 998244353的倍数。
思路
本题题意等价于 求 N m o d 998244353 N \ mod \ 998244353 N mod 998244353 的结果其中 m o d mod mod表示取余运算 直接输出即可。
注意负数取余会得到负数所以必须在取余数的结果上加上 998244353 998244353 998244353。
代码
C
#includestdio.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,y x,y , 使得 x × y x \times y x×y 最大
思路
本题中可能会出现两个负数取值的情况但如果想要得到最大值那么无非就是
两个正数相乘两个负数相乘
于是我们输出 a × c a \times c a×c 和 b × d b \times d b×d 两个答案中的最大值即可。
代码
C
#includestdio.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 x,y ,使得 x y xy xy 中的最大数位 尽可能大。
思路
首先可以得知对于一个数位他最大为9。那么我们从 L 1 L 2 L1L2 L1L2 开始枚举最多10个数就可以找到最适合的 x y xy xy 。
于是我们计算 f ( L 1 L 2 ) , f ( L 1 L 2 1 ) , . . . , f ( L 1 L 2 9 ) f(L1L2),f(L1L21),...,f(L1L29) f(L1L2),f(L1L21),...,f(L1L29) ,取其中的最大值即可。
代码
C
#includestdio.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 l1l2;int r r1r2;int ans 0;for(int i l;ir;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(x0):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-la9 or rb-lb9):print(9)else :ans 0for i in range(la,ra1):for j in range(lb,rb1):ans max(ans,check(ij))print(ans)
F - 个位数口算
题意
输出 3 n 3^n 3n 的个位数。
思路
找规律可以发现对于 3 1 , 3 2 , 3 3 , 3 4 , . . . 3 ^ 1, 3^2 ,3^3,3^4,... 31,32,33,34,... 他们的个位数为 3 , 9 , 7 , 1 , 3 , 9 , 7 , . . . 3,9,7,1,3,9,7,... 3,9,7,1,3,9,7,... 即[3,9,7,1] 循环
于是我们对 n n n取余 4 4 4就可以得到结果。
另如果你没有找到规律也可以用快速幂直接计算出 3 n 3^n 3n 对 10 10 10取余的结果
代码
C
#includestdio.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])快速幂
#includebits/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;ir;i)
#define per(i,r,l) for(int i r;il;i--)
const int INF 0x3f3f3f3f3f3f3f3f;
typedef pairint,int PII;
int qpow(int x,int n){int ans 1;while(n){if(n1) ans ans * x % 10;x x * x % 10;n1;}return ans;
}
void solve(){int n;cinn;coutqpow(3,n);
}
signed main(){int T 1;// cinT;while(T--){solve();}return 0;
}# G - ASCII大小写转换
题意
给一个字符串 s s s ,将其中的大写字母转换为小写字母 小写字母转换为大写字母
思路
对于一个小写字母我们这样转换为大写字母 s[i] s[i] - a A
大写字母转换为小写字母同理s[i] s[i] - A a
代码
C
#includestdio.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 a_1,a_2,...,a_n a1,a2,...,an, 请你找出一个最大的数 N N N , 满足a中 大于等于N的数至少为N个
思路
思路一我们使用一个数组cnt记录一下每个数出现的次数。即cnt[a[i]] 1 。
然后逆序查找从 1 0 6 10^6 106 到 1 1 1 的每个数查看是否满足条件 那么第一个满足条件的 i i i 即为答案。
条件为 ∑ j i n c n t [ j ] ≥ i \sum_{j i}^n cnt[j] \ge i ∑jincnt[j]≥i
思路二对数组a进行逆序排序这样就得出了以下规律 a a a数组中大于等于 a [ i ] a[i] a[i] 的数有 i i i个。
我们逆序遍历数组找到最后一个满足 a [ i ] ≥ i a[i] \ge i a[i]≥i 的 i i i即可 。
代码
C思路一
#includestdio.h
int cnt[1000006];
int main()
{int n;scanf(%d,n);for(int i 1;in;i){int x;scanf(%d,x);cnt[x];}int sum 0;for(int i 1000000;i0;i--){sum cnt[i];if(sum i) {printf(%d,i);return 0;}}return 0;
}C思路二
#includebits/stdc.h
using namespace std;
int a[1000006];
int main(){int n;cinn;for(int i 1;in;i){cina[i];}sort(a1,an1);reverse(a1,an1);for(int i 1;in;i){if(a[i] i){couti-1endl;break;}}return 0;
}python
n int(input())
a [int(i) for i in input().split()]
a.sort(reverseTrue)def check():for i in range(n):if(a[i]i1):return i;return nprint(check())I - 飞云鸽鸽的和式
题意
给你一个数组请你找出其中一段连续的区间 使得区间中的数的总和尽可能大。
思路
思路一本题给的 n n n很小我们直接暴力枚举即可。复杂度 O ( n 3 ) O(n^3) O(n3)
思路二如果我们加上一点前缀和的思想在确认左端点枚举右端点的时候可以借用上一次的答案。这样就省去了第三重循环复杂度 O ( n 2 ) O(n^2) O(n2)
思路三如果我们再加上动态规划的思想我们令 f i f_i fi 表示 以第i个数为结尾的 连续子数组的最大的和 那么我们的答案就是 m a x 1 ≤ i ≤ n f i max_{1 \le i \le n} f_i max1≤i≤nfi , 我们在枚举 i i i的时候考虑两种情况
加入 f i − 1 f_{i-1} fi−1对应的那一段单独成为一段
当然取其中较大值是更好的。
于是最终的递推式为 f i m a x ( f i − 1 a i , a i ) f_i max(f_{i-1} a_i,a_i) fimax(fi−1ai,ai)
时间复杂度为 O ( n ) O(n) O(n)
代码
C 思路一 O ( n 3 ) O(n^3) O(n3)
#includestdio.h
int a[105];
int main(){int n;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}int ans 0xcfcfcfcf;//足够小的数for(int i 1;in;i){for(int j i;jn;j){int sum 0;for(int k i;kj;k){sum a[k];}if(ans sum) ans sum;}}printf(%d,ans);
}C思路二 O ( n 2 ) O(n^2) O(n2)
#includestdio.h
int a[105];
int main(){int n;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}int ans 0xcfcfcfcf;//足够小的数for(int i 1;in;i){int sum 0;for(int j i;jn;j){sum a[j];if(ans sum) ans sum;}}printf(%d,ans);
}C思路三O(n)
#includestdio.h
int a[105];
int f[105];
int main(){int n;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}int ans 0xcfcfcfcf;//足够小的数f[0] 0xcfcfcfcf;for(int i 1;in;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 a , 对数组 a a a进行排序
思路
模板题写对排序代码即可
本题数据范围较小使用朴素的 O ( n 2 ) O(n^2) O(n2) 排序算法也可以通过本题。
同时也可以使用进阶的 O ( n l o g n ) O(nlogn) O(nlogn) 排序算法来更快的解决问题。
代码
C 冒泡排序 O ( n 2 ) O(n^2) O(n2)
#includestdio.h
int a[5005];
int main(){int n;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}for(int i 1;in;i){for(int j i;jn;j){if(a[i] a[j]){int t a[i];a[i] a[j];a[j] t;}}}for(int i 1;in;i){printf(%d ,a[i]);}return 0;
}C 排序函数 O ( n l o g n ) O(nlogn) O(nlogn)
#includebits/stdc.h
using namespace std;
int a[5005];
int main(){int n;cinn;for(int i 1;in;i){cina[i];}sort(a1,an1);for(int i 1;in;i){couta[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 n n的排列 p p p, 问满足 : 对于所有的 1 ≤ i ≤ n 1\le i \le n 1≤i≤n , 都有 p i ̸ i p_i \not i pii 的排列有多少。
排列指数组[1,2,3,...,n] 随机打乱后的数组 如长度为 3 3 3的排列有[1,2,3] 、[1,3,2] 、 [2,1,3] 、[2,3,1] 、[3,1,2]、[3,2,1] 长度为n的排列共有 A n n A_n^n Ann 个
思路
本题考察“错排数”为经典组合数学问题大家可以上网搜索相关内容。
本题给出的 n n n很小 暴力枚举所有的排列即可。
在C中可以调用排列函数来生成长度为 n n n的全排列。
使用全排列的复杂度是 O ( n ! ∗ n ) O(n!*n) O(n!∗n)
下面给出更好的解法时间复杂度 O ( n ) O(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 n n等于 1 1 1和 2 2 2递推式很明显成立 ,对于n大于2的情况我们考虑n的位置
如[2,1,4,3*5*] 前面的[2,1,4,3] 是一个长度为4的错排序那么这个5可以放在前面四个位置中的任意一个。 n − 1 n-1 n−1种可能
假设我们放在数字 1 1 1的位置, [2,*5*,4,3,*1*] 此时数字1和数字5一定是满足条件的。
此时我们可以选择5是否要和“下标为1的数”交换位置
如果交换位置[*5*,2,4,3,*1*]那么剩余n-2个数可以任意组合为错排序方案数为 f n − 2 f_{n-2} fn−2如果不交换位置[2,*5*,4,3,1]那么剩下的n-1个数都可以任意组合为错排序方案数为 f n − 1 f_{n-1} fn−1
代码
C全排列
#includestdio.h
int vis[15];
int a[15];
int t 0;
int n;
int ans 0;
void dfs(int step){if(step n1){for(int i 1;in;i){if(a[i] i) return;}ans ;return;}for(int i 1;in;i){if(vis[i]) continue;vis[i] 1;a[step] i;dfs(step1);vis[i] 0;}return ;
}
int main(){scanf(%d,n);dfs(1);printf(%d\n,ans);return 0;
}C 调用排列函数 O ( n ! ∗ n ) O(n!*n) O(n!∗n)
#includebits/stdc.h
using namespace std;
int a[15];
int main(){int n;cinn;for(int i 1;in;i){a[i] i;}int ans 0;do{bool ok 1;for(int i 1;in;i){if(a[i] i) ok 0;}if(ok) ans ;}while(next_permutation(a1,a1n));coutans;return 0;
}C递推 O ( n ) O(n) O(n)
#includestdio.h
int f[1000005];
int main(){int n;scanf(%d,n);f[1] 0;f[2] 1;for(int i 3;in;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 n1:return 0if n2:return 1return (n-1)*(cp(n-1)cp(n-2))print(cp(n))L - P19E99喜欢16进制
题意
给一个十六进制数输出他的十进制表示
思路
用字符串读取十六进制数然后枚举十六进制数然后不断累加到答案上即可。
代码
C
#includestdio.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))
