2014 BUPT 新生排位賽04

A 大家一起點外賣

連結：http://code.bupt.edu.cn/problem/p/437/

思路：水題，注意負數的情況，注意long long 就能過了。

code：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#define INF 100000005
#define eps 1e-9
using namespace std;
 
const int MAX_N=500005;
const int MAX_M=2000005;
 
int a[MAX_N],n,m;
int ma,mb;
int used[MAX_M],flag;
 
int abc(int a)
{
    if(a<0) return -a;
    return a;
}
void solve()
{
    flag=false;
    ma=0;
    mb=INF;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        used[a[i]]++;
    }
    for(int i=0;i<n;i++){
        if(m-a[i]<0) continue;
        if(!used[m-a[i]]) continue;
        if(m-a[i]==a[i]&&used[a[i]]<2) continue;
        if((mb-ma)>(abc(m-a[i]-a[i]))){
            mb=max(m-a[i],a[i]);
            ma=min(m-a[i],a[i]);
            flag=true;
        }
    }
    if(flag==false){
        printf("Sad\n");
        return ;
    }
    printf("%d %d\n",ma,mb);
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(used,0,sizeof(used));
        solve();
    }
    return 0;
}

B 田田的公司

連結：http://code.bupt.edu.cn/problem/p/438/

思路：裸的并查集，比賽時候沒有注意到long long 到最後也沒過。

code：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#define INF 100000005
#define eps 1e-9
using namespace std;
 
const int MAX_N=100005;
const int MAX_M=2000005;
 
int par[MAX_N];
int high[MAX_N];
long long  value[MAX_N];
 
void init(int n)
{
    for(int i=0;i<=n;i++){
        par[i]=i;
        value[i]=0;
    }
}
int Find(int x)
{
    if(par[x]==x) return x;
    else return par[x]=Find(par[x]);
}
void unite(int x,int y)
{
    x=Find(x);
    y=Find(y);
    if(x==y) return ;
    if(value[x]<value[y]){
        par[x]=y;
        value[y]+=value[x];
    }
    else{
        par[y]=x;
        value[x]+=value[y];
    }
}
bool same(int x,int y)
{
    return Find(x)==Find(y);
}
 
int main()
{
    int T,n,m,tt,a,b;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init(n);
        for(int i=1;i<=n;i++) scanf("%lld",&value[i]);
        while(m--){
            scanf("%d",&tt);
            if(tt==1){
                scanf("%d%d",&a,&b);
                unite(a,b);
            }
            if(tt==2){
                scanf("%d",&a);
                printf("%lld\n",value[Find(a)]);
            }
        }
    }
    return 0;
}

C 崔逗逗的難題

連結：http://code.bupt.edu.cn/problem/p/439/

思路：公式都能推出來但是這道題題目卡精度，我的其他同學都能用double水過去，我無論換什麼姿勢用double都水不過去。

未ac code：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#define INF 100000005
#define eps 1e-9
//#define Pi 3.1415926536
using namespace std;
 
const int MAX_N=100005;
const int MAX_M=2000005;
const int p=90000;
const double Pi=acos(-1.0);
 
int main()
{
    double r;
    while(~scanf("%lf",&r)){
        double s1=(Pi/3.0+1-sqrt(3.0))*(r*r);
        double s2=4.0*((Pi/12.0-1+sqrt(3.0)/2.0)*(r*r));
        double s3=4.0*(r*r-(Pi/6.0)*(r*r)-(sqrt(3.0)/4.0)*(r*r));
        printf("%.6lf %.6lf %.6lf\n",(Pi/3.0+1.0-sqrt(3.0))*r*r,4.0*((Pi/12.0-1.0+sqrt(3.0)/2.0)*r*r),4.0*(1.0-Pi/6.0-sqrt(3.0)/4.0)*r*r);
    }
    return 0;
}

D 崔逗逗給你信心

連結：http://code.bupt.edu.cn/problem/p/435/

思路：我感覺這是一道比較好的題，多個步驟換換相扣。

（1）根據式子x^(2x)^(3x)可得，x^2x=3x => x^2x=x+2x。2乘以x相當于将x二進制表示的最高位上加1的位置上放一個1，是以想要使等式成立就必須，x的二進制表示不能有相鄰的1，因為如果有相鄰的1，則做加法的時候高位上會産生一個1，而異或的話原來是1的位置将全部變成零。

（2）根據第一步的結論，我們需要做的就是判斷小于n的數中有多少個相鄰位置上不含一的數。我們以a[n]表示1~n位的二進制數中有多少相鄰位上沒有一的數。可以得到一個斐波那契數列就是 a[n]=a[n-1]+a[n-2]。預處理出這個數列再将每個帶待求的n處理成二進制，從最高位向最低位掃，對于每個二進制位為1的位i，如果其後面的位也是一就可以則res+=a[i]跳出；如果後面的位是0則res+=a[i-1]，再繼續判斷其他位。

（3）其中還有很多的細節地方，賽後我也是改了好久才過了這道題。

code：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#define INF 999999999
#define eps 1e-9
using namespace std;
 
const int MAX_M=200;
const int MAX_N=100005;
const int p=1000000009;
 
int a[100];
int bit[100];
int convert(long long n,int tt[])
{
    long long d=1;
    int cnt=0;
    while(d<=n) d=d*2,cnt++;
    d/=2;
    for(int i=cnt;i>=1;i--){
        tt[i]=n/d;
        n%=d;
        d/=2;
    }
    return cnt;
}
int main()
{
    a[0]=1;
    a[1]=2;
    for(int i=2;i<=100;i++) a[i]=(a[i-1]+a[i-2])%p;
    long long  x;
    int l,res;
    bool flag=0;
    while(~scanf("%lld",&x)){
        bit[0]=res=flag=0;
        l=convert(x,bit);
        for(int i=l;i>=2;i--){
            if(bit[i]&&bit[i-1]){
                res=(res+a[i]-1)%p;
                flag=1;
                break;
            }
            if(bit[i]) res=(res+a[i-1])%p;
        }
        if(bit[1]&&!flag) res++;
        if(x==1) res++;
        else res++;
        printf("%d\n",res);
    }
}

E 焦級長搭積木

連結：http://code.bupt.edu.cn/problem/p/434/

思路：用dp的方法可以很快的求出來總步數，dp[i][j][k]=dp[i-k][j-1][k-1]+dp[i-k][j-1][k+1] 其中dp[i][j][k] 表示一個i個積木搭成j層最底層k個的總數量。

之後就是求第k個排序，在這個地方卡了一下一直想不到比較好的方法，去看了一下菊苣們的題解知道了，就是對于每個位置判斷k和dp[n][h][m]的關系，前dp[n-m][h-1][m-1] 種序列對應的操作室将上一次層的數量-1，第dp[n-m][h-1][m-1]+1到dp[n-m][h-1][m+1]種序列對應的操作是上一層的數量+1，這樣我們不斷的更新跟新就能更新出第k種序列了。

code：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#define INF -1000000000
#define eps 1e-9
using namespace std;
 
const int MAX_N=545;
const int MAX_H=65;
const int MAX_M=20;
 
long long dp[MAX_N][MAX_H][MAX_M];
int N,M,H;
long long nn;
 
void solve()
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=N;i++){
       if(i<=10) dp[i][1][i]=1;
        for(int j=2;j<=H;j++){
            for(int k=1;k<=10;k++)
                if(k<=i) dp[i][j][k]=dp[i-k][j-1][k-1]+dp[i-k][j-1][k+1];
        }
    }
    printf("%lld\n",dp[N][H][M]);
}
void output(int N,int H,int M,long long k)
{
    int a[H+1];
    int n=N,h=H,m=M;
    a[0]=m;
    for(int i=1;i<H;i++){
        if(k<=dp[n-m][h-1][m-1]){
            a[i]=m-1;
            n=n-m;
            h--;
            m--;
        }
        else{
            k-=dp[n-m][h-1][m-1];
            a[i]=m+1;
            n=n-m;
            h--;
            m++;
        }
    }
    for(int i=0;i<H;i++){
        printf("%d",a[i]);
        if(i!=H-1) printf(" ");
    }
    printf("\n");
}
int main()
{
    while(~scanf("%d%d%d",&N,&H,&M)){
        solve();
        cin>>nn;
        while(nn!=-1){
            output(N,H,M,nn);
            cin>>nn;
        }
    }
    return 0;
}

2014 BUPT 新生排位賽04

繼續閱讀

2020 GDUT Rating Contest Ⅰ G.Livestock Lineup

2014 BUPT 新生排位賽01

20.2.25排位賽H

20.2.25排位賽D

2014 BUPT 新生排位賽02

2014 BUPT 新生排位賽06

2014 BUPT 新生排位賽09

2014 BUPT 新生排位賽11

20.2.25排位賽E

C. Defining Labels

2020 GDUT Rating Contest I (3.08) C. 積木

2020 GDUT Rating Contest Ⅱ G. Bucket Brigade