本次训练共7题,本文附题目链接和AC代码(非本人所写的代码将标明出处)。

nefu 1528 数字游戏

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,sum,tmp,ans1,ans2,a[15];
int main()
{
    tmp=1;
    for(int i=1;i<=12;i++)//先打表9~999999999999(12个9)
    {
        a[i]=10*tmp-1;
        tmp=tmp*10;
    }
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        for(ll i=1;i<=12;i++)
        {
            if(a[i]>n)
            {k=i-1;break;}
        }
        ans1=a[k];
        ans2=n-a[k];
        sum=0;
        while(ans1)
        {
            sum=sum+ans1%10;
            ans1=ans1/10;
        }
        while(ans2)
        {
            sum=sum+ans2%10;
            ans2=ans2/10;
        }
        printf("%lld\n",sum);
    }
    return 0;
}

nefu 1523 校门外的树-林大版-广搜

#include <bits/stdc++.h>
using namespace std;
int n,a,b;
struct node
{
    int x,cnt;
};
node tmp;
queue<node>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    if(a>=b){printf("%d\n",a-b);return 0;}
    q.push({a,0});
    while(!q.empty())
    {
        tmp=q.front();q.pop();
        if(tmp.x==b)
            {printf("%d\n",tmp.cnt);break;}
        if(tmp.x*2<=n)
            q.push({tmp.x*2,tmp.cnt+1});
        if(tmp.x-1>=0&&(tmp.x-1)*2>=b)//此处的if判断很关键,写成if(tmp.x-1>=b)实际上是错的
            q.push({tmp.x-1,tmp.cnt+1});
        if(tmp.x+1<=b)
            q.push({tmp.x+1,tmp.cnt+1});
    }
    return 0;
}

nefu 1517 林大实验林场--尺取法

以下代码来自wyz

#include <iostream>
#include <algorithm>
#include  <stdio.h>
#include <map>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N];
map <LL,int>flag;
int main()
{  ios::sync_with_stdio(0);
    LL n,ans=0;cin>>n;
    for(LL i=1;i<=n;i++)
    {
         cin>>a[i];
         if(!flag[a[i]]) ans++;
          flag[a[i]]++;
    }
    if(n==1)
        cout<<1<<endl;
    else
    {
        LL l=1,r=n;
    while(flag[a[l]]!=1)
        flag[a[l]]--,l++;
    while(flag[a[r]]!=1)
        flag[a[r]]--,r--;
    cout<<r-l+1<<endl;
    }
    return 0;
}

nefu 1519 林大超市买水果

以下代码来自cbw

#include <bits/stdc++.h>
using namespace std;
int m,n,k;
int a[32];
bool flag;
void dfs(int x,int ans,int money)
{
if(money==m&&ans==k)
{flag=1;return;}
if(money>m||ans>k)return;
for(int i=x+1;i<=n;i++)
dfs(i,ans+1,money+a[i]);
}
int main()
{
    scanf("%d %d %d",&m,&n,&k);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
    dfs(i,1,a[i]);
    if(flag)
    {
    puts("Yes");
    break;
    }
    }
    if(!flag)
    puts("No");
    return 0;
}

nefu 1525 一道图论一

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e5+10;
struct node
{
    int x,y,z;
}p[M];
int n,m,k,x,y,z,a,b,cnt,mx,flag,pre[N];
int find(int x)
{
    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
void join(int a,int b)
{pre[find(a)]=find(b);}
bool cmp(node s1,node s2)
{return s1.z<s2.z;}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
        cin>>p[i].x>>p[i].y>>p[i].z;
    sort(p+1,p+m+1,cmp);
    while(k--)
    {
        cin>>a>>b;
        for(int i=1;i<=n;i++)
            pre[i]=i;
        cnt=0;mx=0;flag=0;
        for(int i=1;i<=m;i++)
        {

            if(find(p[i].x)!=find(p[i].y))
            {
                join(p[i].x,p[i].y);
                mx=max(mx,p[i].z);
                cnt++;
                if(find(a)==find(b)){flag=1;break;}
                if(cnt==n-1)break;
            }
        }
        if(cnt<n-1&&flag==0)printf("-1\n");
        else printf("%d\n",mx);
    }
    return 0;
}

nefu 1520 一道数学题

以下代码来自cbw

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n;
int num;
int su[MAXN];
bool is_prime[MAXN];
int a[MAXN];
int cnt;
void prime()
{
cnt=1;
memset(is_prime,1,sizeof(is_prime));
is_prime[0]=is_prime[1]=0;
for(int i=2;i<=MAXN;i++)
{
if(is_prime[i])
su[cnt++]=i;
for(int j=1;j<cnt&&su[j]*i<=MAXN;j++)
is_prime[su[j]*i]=0;
}
}
int main()
{
    scanf("%d",&n);
    prime();
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&num);
    for(int j=1;j<=cnt&&su[j]*su[j]<=num;j++)
    {
    if(num%su[j]==0)
    {
    sum+=(i-a[su[j]])*(long long)(n-i+1);
    a[su[j]]=i;
    while(num%su[j]==0)
    num/=su[j];
    }
    }
    if(num>2)
    {
    sum+=(i-a[num])*(long long)(n-i+1);
    a[num]=i;
    }
    }
    printf("%lld\n",sum);
    return 0;
}

nefu 1529 打扑克

以下代码来自admin题解

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000000,maxk=1000000;
int n,K,col[maxk+5];
LL sum[maxn+5],f[maxn+5],MAX[maxk+5];
int main()
{
    int x;
    cin>>n>>K;
    for (int i=1;i<=n;i++) cin>>col[i]; 
    for (int i=1;i<=n;i++) {cin>>x;sum[i]=sum[i-1]+x;}
    memset(MAX,192,sizeof(MAX));
    for (int i=1;i<=n;i++)
    {
        f[i]=max(f[i-1],MAX[col[i]]+sum[i]);
        MAX[col[i]]=max(MAX[col[i]],f[i-1]-sum[i-1]);
    }
   printf("%lld\n",f[n]);
   return 0;
}