2025年南京大学计算机考研复试机试真题（解题思路 + AC 代码）

2025年南京大学计算机考研复试机试真题

2025年南京大学计算机考研复试上机真题

历年南京大学计算机考研复试上机真题

历年南京大学计算机考研复试机试真题

更多学校完整题目开源地址：https://gitcode.com/u014339447/pgcode

百度一下pgcode即可查看，输入 “学校名称” 即可筛选该校历年机试真题，包括真题、ac代码、解题思路、视频讲解。

字符串区间翻转-南京大学

题目描述

小诺有一个由 0 和 1 组成的字符串。现在小诺有一次机会，可以选择一个任意的区间 [L,R]，将该区间内的所有字符串进行翻转（即 0→1，1→0）。

请问小诺经过一次翻转之后字符串中最多会有多少个 1？

输入格式

第一行输入一个正整数n {n}n，表示字符串长度，n ≤ 10 7 {n \leq 10^7}n≤107。接下来一行输入一个 01 字符串。可能有多组测试数据输入。

输出格式

输出题目要求的答案。

输入样例

4 1001

输出样例

4

#include<stdio.h>intmain(){intn;scanf("%d",&n);chardata[n];scanf("%s",data);intmax=0;for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){intcount=0;for(intp=0;p<n;p++){if((p<i||p>j)&&data[p]=='1'){count++;}elseif(p>=i&&p<=j&&data[p]=='0'){count++;}}if(count>max){max=count;}}}printf("%d",max);}

完全背包问题-南京大学

题目描述

有n {n}n种（每一种有无数个）重量和价值分别为W i {W_i}Wi​,V i {V_i}Vi​的物品，现从这些物品中挑选出总量不超过W {W}W的物品，求所有方案中价值总和的最大值。

输入格式

输入包含多组测试用例，每一例的开头为两位整数n {n}n、W {W}W（1 ≤ n ≤ 10000 {1 \leq n \leq 10000}1≤n≤10000,1 ≤ W ≤ 1000 {1 \leq W \leq 1000}1≤W≤1000），接下来有n {n}n行，每一行有两位整数W i {W_i}Wi​、V i {V_i}Vi​（1 ≤ W i ≤ 10000 {1 \leq W_i \leq 10000}1≤Wi​≤10000,1 ≤ V i ≤ 100 {1 \leq V_i \leq 100}1≤Vi​≤100）。

输出格式

输出为一行，即所有方案中价值总和的最大值。

输入样例

3 4 1 2 2 5 3 7 3 5 2 3 3 4 4 5

输出样例

10 7

#include<stdio.h>intmain(){intn,w;while(scanf("%d %d",&n,&w)==2){intdata[n][2];intv[w];for(inti=0;i<n;i++){scanf("%d %d",&data[i][0],&data[i][1]);}for(inti=0;i<=w;i++){intmax=0;for(intj=0;j<n;j++){if(i>=data[j][0]){if(v[i-data[j][0]]+data[j][1]>max){max=v[i-data[j][0]]+data[j][1];}}}v[i]=max;}printf("%d\n",v[w]);}}

最长连续公共子序列-南京大学

题目描述

输入两个字符串s 1 {s1}s1,s 2 {s2}s2。输出最长连续公共子串长度和最长连续公共子串。

输入格式

多组数据输入。输入两个字符串s 1 {s1}s1,s 2 {s2}s2，长度不大于 100，以空格隔开。

输出格式

输出最长连续公共子串长度和最长连续公共子串。

输入样例

abcdefg qwercdefiok

输出样例

4 cdef

#include<stdio.h>#include<string.h>intmain(){chars1[101],s2[101];while(scanf("%s %s",s1,s2)==2){intmax=0,index1=0,index2=0;intlength[strlen(s1)][strlen(s2)];for(inti=0;i<strlen(s1);i++){for(intj=0;j<strlen(s2);j++){if(s1[i]==s2[j]){length[i][j]=i>0&&j>0?length[i-1][j-1]+1:1;}else{length[i][j]=0;}if(length[i][j]>max){max=length[i][j];index1=i;index2=j;}}}printf("%d\n",max);inti=index1,j=index2;while(index1>=0&&index2>=0&&s1[index1]==s2[index2]){index1--;index2--;}for(intk=index1+1;k<=i;k++){printf("%c",s1[k]);}printf("\n");}}

子序列-南京大学

题目描述

一个串的“子序列”是将这个串中的一些字符提取出来得到一个新串，并且不改变它们的相对位置关系。

我们说串t {t}t是串s 1 {s1}s1和s 2 {s2}s2的公共子序列，当且仅当t {t}t是s 1 {s1}s1的子序列且t {t}t是s 2 {s2}s2的子序列。定义串s 1 {s1}s1和s 2 {s2}s2的相似度为它们最长公共子序列的长度。

现在给定一个文本串S {S}S和一组模式串T [ 1 ] , T [ 2 ] , … , T [ n ] {T[1], T[2], \dots, T[n]}T[1],T[2],…,T[n]。求T [ i ] {T[i]}T[i]中和S {S}S具有最高相似度的那个，然后输出最高的相似度。

S {S}S和所有的T [ i ] {T[i]}T[i]都只含有小写字母。

输入规则：

先是一行字符串S {S}S。

第二行是n {n}n（1 ≤ n ≤ 100 {1 \leq n \leq 100}1≤n≤100）。

第三行以降的n {n}n行是n {n}n个模式串T [ 1 ] … T [ n ] {T[1] \dots T[n]}T[1]…T[n]。

S {S}S和所有的T [ i ] {T[i]}T[i]的长度都不超过 2000。

输入格式

如题

输出格式

如题

输入样例

abcdef 4 acfaff appont emmm bdxeuf

输出样例

bdxeuf 4

#include<stdio.h>#include<string.h>intmain(){chars[2001];scanf("%s",s);intn;scanf("%d",&n);chart[n][2001];intmax=0;intindex;for(inti=0;i<n;i++){scanf("%s",t[i]);intlength[strlen(t[i])][strlen(s)];if(s[0]==t[i][0]){length[0][0]=1;}else{length[0][0]=0;}for(intj=1;j<strlen(t[i]);j++){if(s[0]==t[i][j]){length[j][0]=1;}else{length[j][0]=length[j-1][0];}}for(intj=1;j<strlen(s);j++){if(s[j]==t[i][0]){length[0][j]=1;}else{length[0][j]=length[0][j-1];}}for(intj=1;j<strlen(t[i]);j++){for(intk=1;k<strlen(s);k++){if(s[k]==t[i][j]){length[j][k]=length[j-1][k-1]+1;}else{if(length[j-1][k]>length[j][k-1]){length[j][k]=length[j-1][k];}else{length[j][k]=length[j][k-1];}}}}if(length[strlen(t[i])-1][strlen(s)-1]>max){max=length[strlen(t[i])-1][strlen(s)-1];index=i;}}printf("%s\n",t[index]);printf("%d",max);}