传智杯往届补题
补题链接
1-5届
https://www.nowcoder.com/exam/company
第六届
- 初赛第一场的补题链接：https://ac.nowcoder.com/acm/contest/71300
- 初赛第一场题解：https://ac.nowcoder.com/discuss/1241427
- 初赛第二场，12月10日题解：https://www.nowcoder.com/discuss/563702942105190400
- 复赛第一场的题解+补题：https://ac.nowcoder.com/discuss/1246063
- 复赛第二场（2023年12月23日）补题+题解链接：https://ac.nowcoder.com/discuss/1247214
- 全国总决赛（2024年3月23日）AB组题解+补题链接：https://ac.nowcoder.com/discuss/1272107
第六届初赛第一场：kotori和素因子
题意：
给 n 个数，从每个数里面选它的一个质因子，要求每个数选的质因子都不一样，求这些质因子的最大累加和。
思路：
n <= 10 并且 a[i] <= 1000，数据范围很小，可以 dfs 搜索
- 先求出每个数的质因子
- 对每个数的质因子 dfs，如果每个数都取了一个质因子，取最大累加和
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int T, n, m;
int ans=MOD;
void dfs(vector<vector<int>>& v,int x,int sum,set<int>& se)
{
if(x==n)
{
ans=min(ans,sum);
return;
}
for(int i:v[x])
{
if(se.find(i)==se.end())
{
se.insert(i);
dfs(v,x+1,sum+i,se);
se.erase(i);
}
}
}
void solve()
{
cin>>n;
vector<vector<int>> v(n);
for(int i=0,temp;i<n;i++)
{
cin>>temp;
for(int j=2;j*j<=temp;j++)
{
if(temp%j==0)
{
v[i].push_back(j);
while(temp%j==0)temp/=j;
}
}
if(temp>1)v[i].push_back(temp);
}
set<int> se;
dfs(v,0,0,se);
cout<<(ans==MOD?-1:ans);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
第六届初赛第二场：小红取数
题意：
从 n 个数里取数，在满足所取数之和为 K 的倍数条件下，最大和是多少？
思路：
dp，每个数要么取，要么不取
dp[i][j] 表示取前 i 个数中，模 K 为 j 的最大和
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
int T,n,m;
void solve(){
cin>>n>>m;
vector<vector<int>> dp(n+1,vector<int>(m));
for(int j=1;j<m;j++)dp[0][j]=-1e18-7;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
for(int j=0;j<m;j++)dp[i][j]=dp[i-1][j];//不取 x
for(int j=0;j<m;j++)
dp[i][(j+x)%m]=max(dp[i][(j+x)%m],dp[i-1][j]+x);//取 x
}
cout<<(dp[n][0]>0?dp[n][0]:-1);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
第六届初赛第二场：加减
题意：
给定 n 个数，一次操作可以对每个数加 1 或减 1，可以操作 k 次，问最后出现次数最多的数的出现次数最大可以是多少？
思路：
假设有 cnt 个数，最开始不一定都相等，但是可以通过 <= k 次操作使得这些数全都相等，那么目标数就是这些数的中位数，就可以使得操作次数最少；
操作数对应的下标对答案没有影响，那么就可以排序，使得每个数之间的差值尽量小，对于加或减到目标值的次数来说会更优；
如果存在长度为 len 的区间可以满足题意，那么一定就存在长度为 len-1 的区间满足题意，满足单调性，可以二分；
check 的时候可以用前缀和在 O(1) 时间内求出区间和。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int t, n, k, m;
int a[100005];
int sum[100005];
bool check(int limit)
{
for(int i=1;i<=n-limit+1;i++)
{
int l=i,r=i+limit-1,mid=(l+r)/2,cnt=0;
cnt+=(mid-l)*a[mid]-(sum[mid-1]-sum[l-1]);
cnt+=(sum[r]-sum[mid])-(r-mid)*a[mid];
if(cnt<=k)return 1;
}
return 0;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
int l=0,r=n,ans=0;
while(l<=r)
{
int mid=(r-l)/2+l;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
第六届复赛第二场：小红的回文子串
题意：
给定一个字符串，可以修改其中一个字符为任意字符，问字符串的长度为 3 的回文子串的数量最大是多少？
思路：
只能修改一个字符，那么就有两种情况了
- s[i-2] = s[i+2], 但是 s[i] != s[i-2]，这种情况可以多加 2 个
- 在不影响原本数量的回文子串数量的情况下，最多可以再加 1 个，就是 s[i] != s[i+2] 的情况
- 修改 s[i]，看 s[i-2] 是否等于 s[i]，或者 i-2 越界了
- 修改 s[i+2]，看 s[i+2] 是否等于 s[i+4]，或者 i+4 越界了
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
int T,n,m;
void solve(){
string s;
cin>>s;
int ans=0,sign=1;
n=s.size();
for(int i=0;i<n-2;i++)
if(s[i]==s[i+2])ans++;
for(int i=2;i<n-2;i++)
{
if(s[i-2]==s[i+2] && s[i]!=s[i-2]){
cout<<ans+2;
return ;
}
}
for(int i=0;i<n-2;i++)
{
if(s[i]!=s[i+2] && (i+4>=n || s[i+2]!=s[i+4]))
{
ans++;
break;
}
if(s[i]!=s[i+2] && (i-2<0 || s[i-2]!=s[i]))
{
ans++;
break;
}
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
投递华顺信安等公司7个岗位
腾讯云智研发二面148人在聊
查看20道真题和解析
