2018 Multi-University Training Contest 1

Hetui 2018-07-24 原文

1001：

1002：

1003：

贪心排一下序就行，先按x坐标再按y坐标，每次选三个即可

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
struct point
{
    long long x,y;
    int id;
};
point po[4010];
int n;

void init()
{
    memset(po,0,sizeof(po));
}

bool cmp(const point &a,const point &b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

int main()
{
    int i;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d",&n);
        for(i=1;i<=3*n;i++)
        {
            cout<<i<<endl;
            scanf("%lld%lld",&po[i].x,&po[i].y);
            po[i].id=i;
        }
        sort(po+1,po+1+3*n,cmp);
        int pos=1;
        for(i=1;i<=n;i++)
        {
            printf("%d %d %d\n",po[pos++].id,po[pos++].id,po[pos++].id);
        }
    }
    return 0;
}

View Code

1004：

1005：

1007：

找规律，打表

首先把a[]序列打表出来：

将相同元素放到同一行发现这样的一个三角形

2 2

4 4 4

6 6

8 8 8 8

发现这个a[]中每个元素出现的次数刚好是因子中所含2的数量+1

然后就好做了，找一找这个三角形规律，注意打表，log*log的复杂度过不了

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
const long long mod=1e9+7;
const long long inv=500000004;
long long  num_2[100],mi[100],biao[100],biao_cnt[100];
long long n,num,sum;
long long ans;

void init()
{
    num=0;
    ans=0;
    sum=0;
}

long long fun(long long now,int i)
{
    long long pos=now;

    long long flag=(pos%mod)*((pos+1)%mod)%mod;
    flag=(flag*inv)%mod;
    long long tmp=flag;
    long long cnt=pos;
    long long t=flag;
    pos/=2;
    while(pos>0)
    {
        tmp=(tmp+((t+now/2)%mod)*inv)%mod;
        cnt+=pos;
        pos/=2;
        t=(((t+now/2)%mod)*inv)%mod;
    }
    tmp=(tmp+(sum%mod*cnt%mod)%mod)%mod;

    biao_cnt[i]=cnt;
    sum+=now;
    return (tmp%mod+mod)%mod;
}

int main()
{
    //freopen("123.in","r",stdin);
    //freopen("123.out","w",stdout);
    int i;
    num_2[0]=0;
    mi[0]=1;
    biao[0]=fun(mi[0],0);
    long long flag=1;
    for(i=1;i<=62;i++)
    {
        flag*=2;
        mi[i]=flag;
        num_2[i]=flag-1;
        sum=0;
        biao[i]=fun(mi[i],i);
   //     cout<<biao_cnt[i]<<endl;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%lld",&n);
        long long tmp=n-1;
        for(i=62;i>0;i--)
        {
            if(tmp==0) break;
            if(num_2[i]>tmp) continue;
            num+=(num_2[i]+1)/2;
            tmp-=num_2[i];
        }

        long long cnt=num;
        long long pos=0;
        int xx=62;
        sum=0;
        while(cnt>0)
        {

           for(i=xx;i>=0;i--)
            {
                if(mi[i]<=cnt)
                {
                    pos=mi[i];
                    break;
                }
            }
            long long flag=biao[i];

            flag=(flag+(sum%mod)*(biao_cnt[i]%mod))%mod;
            ans=(ans+flag)%mod;
            cnt-=pos;
            sum+=pos;
        }
        ans=(ans+((num+1)%mod)*(tmp%mod)+1)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}