比赛12 总结

• T1
• T2
• T3
• T4
• T5

T1

题面

题意

输入n和k以及n个数,这几个数依次并循环减k,问最后一个大于0的数是多少

代码

#include<bits/stdc++.h>
using namespace std;

int n,mx=0,ans,a,k;

int main()
{
    int i,j;
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a);
        if((a+k-1)/k>=mx)
        {
            mx=(a+k-1)/k;
            ans=i;
        }
    }
    cout<<ans;
}

T2

题面

题意

一串数,x,y等,从第二个数起,每一个数等于它的下一项加上上一项,问第n个数是多少.输出结果对1e9+7取模.

方法

找规律

代码

#include<bits/stdc++.h>
#define ll long long
#define M 1000000007
using namespace std;

ll x,y,n,ans;

ll mod(ll m)
{
    while(m<0)
    {
        m+=M;
    }
    if(m>=M)
    {
        m=m%M;
    }
    return m;
}

int main()
{
    ll i,j;
    cin>>x>>y>>n;
    n=n%6;
    if(n==1) ans=x;
    if(n==2) ans=y;
    if(n==3) ans=y-x;
    if(n==4) ans=-x;
    if(n==5) ans=-y;
    if(n==0) ans=x-y;
    cout<<mod(ans);
}

T3

题面

题意

有一个长为m,宽为n的巧克力,只能沿着整数边长切割,切k刀,求这样切了之后最小的那一块的最大值.

方法

分类讨论,当刀数小于较长边时,将到集中在一边(这样切没有交叉,块数较少)
大于等于时,将刀先切满较长边(同理,块数较少),剩余的再均匀切在较短边上.

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll m,n,k,s,s1,s2,u,v;

int main()
{
    ll i,j;
    cin>>m>>n>>k;
    if(m+n-2<k)
    {
        cout<<-1;
        return 0;
    }
    if(m+n-2==k)
    {
        cout<<1;
        return 0;
    }
    if(k<=m-1||k<=n-1)
    {
        s=(m*n)/(k+1);
        s1=s/m*m;
        s2=s/n*n;
        cout<<max(s1,s2);
        return 0;
    }
    else
    {
        if(m>n) swap(m,n);//m<n
        u=k-(n-1);
        cout<<m/(u+1);
    }
}

T4

题面

题意

输入城市数,公路数和铁路数,以及它们的起点和终点和距离(火车起点均为首都1).问至多去掉几条铁路时到最短路的距离不变.

方法

首先用堆优化最短路,然后加入铁路并进行比较,判断铁路是否必要

代码

#include<bits/stdc++.h>
#define ll long long
#define M 1000000000000000000
#define N 100005
using namespace std;

ll n,m,K,p[N],d[N];
bool vis[N];
vector<pair<int,int> > g[N];
queue<int>que;

int main()
{
    int u,v,x,i,j;
    cin>>n>>m>>K;
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&u,&v,&x);
        g[u].push_back(make_pair(v,x));
        g[v].push_back(make_pair(u,x));
    }
    for(i=0;i<=n;i++)
    {
        d[i]=M;
    }
    d[1]=0;

    memset(p,0,sizeof(p));
    vis[1]=true;
    que.push(1);

    for(i=1;i<=K;i++)
    {
        scanf("%d%d",&u,&x);
        if(d[u]>x)
        {
            d[u]=x;
            p[u]=1;
            if(vis[u]==false)
            {
                vis[u]=true;
                que.push(u);
            }
        }
    }

    while(que.empty()==false)//找出最短路并与铁路进行比较,通过标记来确定是否删去 
    {
        u=que.front();
        que.pop();
        vis[u]=false;

        for(i=0;i<g[u].size();i++)
        {
            v=g[u][i].first;
            x=g[u][i].second;

            if(d[v]>=d[u]+x&&p[v]!=0)
                p[v]=0;

            if(d[v]>d[u]+x)
            {
                d[v]=d[u]+x;
                if(vis[v]==false)
                {
                    vis[v]=true;
                    que.push(v);
                }
            }
        }
    }

    for(i=1;i<=n;i++)
        K-=p[i];
    cout<<K;
}

T5

题面

题意

输入n,将1-n分成至多k组,使每组的最大公因数均大于1.
输出k和k组答案

方法

首先筛出质数,然后让质数从大到小进行分组,若恰好有偶数个倍数,则两两配对,反之,将2*该质数的值留下(为2提供更多的倍数以达到回收的作用,而且这个数肯定),其余的两两配对.

代码

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;

ll n,m,k,ans,an1[N],an2[N];
bool zhi[N],ap[N];

bool fj(ll m)
{
    ll i,j;
    bool a=false;
    for(i=m;i<=n;i+=m)
    {
        if(ap[i]==false) a=1-a;
    }
    return a;
}

void getzhi()
{
    ll i,j;
    for(i=2;i<=n/2;i++)
    {
        if(zhi[i]==false)
        {
            for(j=i*2;j<=n;j+=i)
            {
                zhi[j]=true;
            }
        }
    }
}

void ss(ll u)
{
    ll i,j,a[5],aa=0;
    for(j=u;j<=n;j+=u)
    {
        if(ap[j]==false)
        {
            a[aa]=j;
            aa++;
            if(aa==2)
            {
                ans++;
                aa=0;
                ap[a[0]]=ap[a[1]]=true;
                an1[ans]=a[0];
                an2[ans]=a[1];
            }
        }
    }
}

int main()
{
    ll i,j;
    cin>>n;
    getzhi();
    for(i=n/2;i>=3;i--)
    {
        if(zhi[i]==false)
        {
            if(fj(i)==false)
            {
                ss(i);
            }
            else
            {
                ap[i*2]=true;
                ss(i);
                ap[i*2]=false;
            }
        }
    }
    ss(2);
    cout<<ans;
    //*
    for(i=1;i<=ans;i++)
    {
        printf("\n%lld %lld",an1[i],an2[i]);
    }
    //*/
}