首页 / 算法 / 2021牛客寒假算法基础集训营3
2021牛客寒假算法基础集训营3
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了2021牛客寒假算法基础集训营3，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5162字，纯文字阅读大概需要8分钟。
内容图文
C重力坠击
思路：dfs枚举k次攻击的位置，然后求一下最大值即可
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int x[15],y[15],r[15],n,k,R,atkx[5],atky[5],ans,vis[15];
int get_dist(int i,int j)
{
int d1=atkx[i]-x[j];
int d2=atky[i]-y[j];
return d1*d1+d2*d2;
}
void dfs(int cur)
{
if(cur==k+1){
int temp=0;
memset(vis,0,sizeof vis);
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
if(!vis[j]){
int d1=(r[j]+R)*(r[j]+R);
int d2=get_dist(i,j);
if(d1>=d2)vis[j]=1;
}
}
}
for(int i=1;i<=n;i++)
if(vis[i])temp++;
ans=max(ans,temp);
return ;
}
for(int i=-7;i<=7;i++){
for(int j=-7;j<=7;j++){
atkx[cur]=i;
atky[cur]=j;
dfs(cur+1);
}
}
}
int main()
{
cin>>n>>k>>R;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i]>>r[i];
dfs(1);
cout<<ans<<'\n';
return 0;
}
D-Happy New Year！
签到题
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int getlen(int n)
{
int res=0;
while(n){
int t=n%10;
res+=t;
n/=10;
}
return res;
}
int main()
{
int n;
cin>>n;
int len=getlen(n);
for(int i=n+1;i;i++){
if(len==getlen(i)){
cout<<i<<'\n';break;
}
}
return 0;
}
H数字串
思路：模拟题。坑点还是挺多的，一开始细节没处理到。其实>10以后的字母可以拆分成个位的，而个位的同样也可以合并成两位数的。然后注意一下10,20这种特殊情况即可
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int main()
{
string s,t;
cin>>s;
bool flag=false;
int n=s.size();
for(int i=0;i<s.size();i++){
int tt=s[i]-'a'+1;
if(tt>10&&tt!=20&&!flag){
int a=tt/10%10;
int b=tt%10;
t+=(char)('a'+a-1);
t+=(char)('a'+b-1);
flag=true;continue;
}else if(tt<10&&!flag&&i+1<n){
int t1=tt;
int t2=s[i+1]-'a'+1;
int t3=t1*10+t2;
if(t3>10&&t3!=20&&t3<=26){
t+=(char)('a'+t3-1);
flag=true;i++;continue;
}
}
t+=s[i];
}
if(flag){
cout<<t;
}else cout<<"-1";
cout<<'\n';
return 0;
}
G-糖果
思路：这道题把我卡住了，用并查集写的，不知道为什么假了
假代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
typedef long long ll;
ll pre[N],a[N];
void init(int n)
{
for(int i=1;i<=n;i++)pre[i]=i;
}
int find(ll x)
{
if(x==pre[x])return x;
else {
a[pre[x]]=max(a[pre[x]],a[x]);
return pre[x]=find(pre[x]);
}
}
int main()
{
ll n,m,u,v;
scanf("%lld%lld",&n,&m);
init(n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=m;i++){
scanf("%lld%lld",&u,&v);
int fu=find(u);
int fv=find(v);
if(fu!=fv)pre[fu]=fv;
}
ll ans=0;
for(int i=1;i<=n;i++){
ans+=a[find(i)];
}
printf("%lld\n",ans);
return 0;
}
/*
3 2
1 2 3
1 2
2 3
*/
ac
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
typedef long long ll;
ll pre[N],a[N];
void init(int n)
{
for(int i=1;i<=n;i++)pre[i]=i;
}
int find(ll x)
{
if(x==pre[x])return x;
else {
//a[pre[x]]=max(a[pre[x]],a[x]);
return pre[x]=find(pre[x]);
}
}
int main()
{
ll n,m,u,v;
scanf("%lld%lld",&n,&m);
init(n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=m;i++){
scanf("%lld%lld",&u,&v);
int fu=find(u);
int fv=find(v);
if(fu!=fv)pre[fu]=fv;
a[fu]=a[fv]=max(a[fu],a[fv]);
}
ll ans=0;
for(int i=1;i<=n;i++){
ans+=a[find(i)];
}
printf("%lld\n",ans);
return 0;
}
/*
3 2
1 2 3
1 2
2 3
*/
I序列的美观度
题意：给你一个序列，求所有子序列的美观度（假设一个长度为m的序列满足1=<i<=m-1,且a[i]=a[i+1],则美观度=m-1）最大是多少。子序列是指去除某些元素不改变元素相对位置而形成的新序列。
思路：dp。设f[i]表示以i结尾的序列美观度最大值
则有转移方程：
- f[i]=max(f[j]+1)，j<i且a[i]=a[j]
- f[i]=max(f[j]),j<i且a[i]!=a[j]
分析：一开始分析以为f[i]只和f[i-1]有关，（当时考虑的太少）,这个时间复杂度是O（n^2）,主要是pos的寻找
实际上对于第一种情况：对于第i个数字，假设前i-1个中有与a[i]相等的，那么他的最大值会从最后一个与a[i]相等的位置那里转移过来，（比如 1 1 2 1，其中的第四个1肯定从第二个1转移过来是最优的）也就是f[i]=f[pox]+1（pos是指与a[i]相等的最靠近的位置），这里的pos怎么寻找？其实用一个vis数组标记每个元素最后的位置即可。
第二种情况：这个更好解决，我们用一个maxx标记前i-1个的最大值即可。
这样就把时间复杂度降到了O(n)
注意：需要特别注意一下pos可能不存在
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
typedef long long ll;
int f[N],vis[N],a[N];//vis[i]-i出现的最后一个位置
int main()
{
int n,maxx=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
f[1]=0;vis[a[1]]=1;//初始化一下
for(int i=2;i<=n;i++){
if(vis[a[i]]){//pos存在
f[i]=max(maxx,f[vis[a[i]]]+1);//考虑两个方程的最大值
maxx=max(maxx,f[i]);//一直更新前第二个方程的最大值
vis[a[i]]=i;//更新pos最后的位置
}
else{//pos不存在 ，最大值只可能是第二个方程
f[i]=maxx;vis[a[i]]=i;
}
}
cout<<f[n]<<'\n';
return 0;
}
J加法和乘法
思路：首先考虑两张牌的各种情况：
偶+偶=偶 偶*偶=偶 奇+奇=偶 奇*奇=奇 奇+偶=奇 奇*偶=偶
可以发现n奇数时，最后一次操作是牛妹，那么就算出现两个奇数或者一奇一偶牛妹也能把它们变成偶数，那么牛妹赢。接下来看n偶数的情况。
如果序列中全是奇数，那么牛牛肯定是希望出现奇数的，牛妹肯定是希望操作成偶数，那牛妹操作出现一个偶数牛牛就把他变成奇数，到最后牛牛操作肯定是两奇或者一奇一偶，显然牛牛赢。
那序列中出现一个偶数的情况，不难发现牛牛还是可以赢的。
两个偶数及以上的情况：不管牛牛怎么变成奇数，在牛妹最后一次操作都可以把他变成两个偶数。因此牛妹获胜
注意：n=1特判
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
int main() {
int n,cnt=0,x;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]%2==0)cnt++;
}
if(n==1){
if(a[0]&1)cout<<"NiuNiu";
else cout<<"NiuMei";
}else{
if(n&1)cout<<"NiuMei";
else {
if(cnt<=1)cout<<"NiuNiu";
else cout<<"NiuMei";
}
}
cout<<'\n';
return 0;
}
内容总结
以上是互联网集市为您收集整理的2021牛客寒假算法基础集训营3全部内容，希望文章能够帮你解决2021牛客寒假算法基础集训营3所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。