T1、数列(number)

Solution

首先我们考虑形如\(\frac{n^2}{2}\)的数，显然n个这样的数会提供\(\frac{n(n-1)}{2}\)对。

把k看作是几个形如\(\frac{n(n-1)}{2}\)的和，从大到小贪心加。

要保证任意两个不同的数的和不是完全平方数，暴力构造一下就可以了。

#include
    
     #include
     
      #include
      
       typedef long long ll;ll K,num[100005],a[155];ll ans,print[155];ll l,r,res,pos=0;const ll nn[105]={0,1,3,5,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67};int main(){    freopen("number.in","r",stdin);    freopen("number.out","w",stdout);    scanf("%lld",&K);    if(K<100000){        if(K<=6){            printf("%lld\n",K+1);printf("1 ");            for(int i=1;i<=K;i++) printf("3 ");        }        else{            printf("%d\n",K-1);            printf("2 2 2 2 ");printf("1 ");            for(int i=1;i<=K-6;i++) printf("3 ");        }        return 0;    }    for(int i=1;i<=100000;i++) num[i]=1LL*i*(i-1)/2;    for(int i=1;i<=100;i++) a[i]=2LL*nn[i]*nn[i];    while(K!=0){        ++pos;        l=2;r=100000;        while(l<=r){            ll mid=(l+r)>>1;            if(num[mid]<=K) res=mid,l=mid+1;            else r=mid-1;        }        print[pos]=res;        K-=num[res];ans+=res;    }    printf("%lld\n",ans);    for(register int i=1;i<=pos;i++)    for(register int j=1;j<=print[i];j++) printf("%lld ",a[i]);    return 0;}
      
     
    

T2、散步(walk)

Solution

对于15分，直接用map来记录就可以直接判断了。

官方题解

/*15 points#include
    
     #include
     
      #include
      
       #include
       
      
     
    

T3、考古(archaeology)

Solution

把操作反过来，就可以看成是，每次会有一段地面下降，问最后每一段地面会降至那一层。

用树状数组/线段树来维护下降过程中每一段的(x,y)值，寻找下降的区间可以直接在树状数组/线段树上二分。

#include
    
     using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 200005#define ll long long#define lowbit(a) (a&-a)int n,q,x[MN],l[MN];ll xpos[MN],ypos[MN],pos,X,Y;bool d[MN];void Cx(int x,int val){for(;x<=n;x+=lowbit(x))xpos[x]+=val;}void Cy(int x,int val){for(;x<=n;x+=lowbit(x))ypos[x]+=val;}ll G(int x){ll res=0;for(;x;x-=lowbit(x)) res+=ypos[x];return res;}int main(){    freopen("archaeology.in","r",stdin);    freopen("archaeology.out","w",stdout);    n=read();q=read();    register int i,j;    for(i=1;i<=q;++i) x[i]=read(),d[i]=read()==1,l[i]=read();    for(i=2;i<=n;++i) Cx(i,1);    for(i=q;i;--i){        if(d[i]){            pos=X=Y=0;                      for(j=17;~j;--j)if((pos|1<
     
      <=n&&X+xpos[pos|1<
      
       <
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！!