2014 BUPT 新生排位賽01

A 學姐的桌面

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

思路：水題，有一個坑就是怎麼輸出“%”這個字元，當時沒注意到自己的程式沒打這個字元直接交了上去wa了一次。

code：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define INF 10000
using namespace std;
 
const int MAX_N=1000;
const int MAX_M=1000;
 
int main()
{
    int T,n,t,nn,mid;
    double ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&t);
        nn=0;
        for(int i=0;i<n;i++){
            scanf("%d",&mid);
            if(mid<t) nn++;
        }
        ans=(double)nn/n;
        printf("%.2lf",ans*100);
        printf("%c",'%');
        printf("\n");
    }
    return 0;
}

B 學姐去學車

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

思路：找規律的題，多寫幾項就能看出來，當時1A了，具體規律見代碼吧。

code:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define INF 10000
using namespace std;
 
const int MAX_N=1000;
const int MAX_M=1000;
 
int main()
{
    int T,n,m,q,tt;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        scanf("%d",&tt);
        while(tt--){
            scanf("%d",&q);
            if(q<=n) printf("1\n");
            else if(q%(n+1)<m) printf("2\n");
            else printf("1\n");
        }
    }
    return 0;
}

當時就做出來了這兩個題，太弱了~~

C 學姐的學弟

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

大緻題意：給多個圓每個圓的坐标都是整數，且半徑都是1，求這幾個圓的并。

思路：比賽時感覺這個題得用計算幾何做，計算幾何根本一竅不通就沒再想，後來聽學長講，這個題有幾個關鍵的地方（坐标為整數半徑為一）是以圖上每個小方格的情況一共隻有三種：全部覆寫，

2014 BUPT 新生排位賽01

，

2014 BUPT 新生排位賽01

。

這三種情況其面積分别為

2014 BUPT 新生排位賽01

再統計個數的時候以左上角為準，如果四個頂點中有一條對角線上的兩個頂點是圓心則為第一種，如果隻有一個頂點是圓心是第二種，有兩個頂點在一條邊上是第三種，然後周遊所有頂點統計個數即可。

code:

//2014 排位賽01 C（奇葩方法求面積）
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define INF 1000000000
 
using namespace std;
 
const int MAX_N=130;
const int MAX_E=500005;
 
const double Pi=acos(-1.0);
const double s1=Pi/4,s2=Pi/6+sqrt(3.0)/4,s3=1;
bool graph[MAX_N][MAX_N];
int n1,n2,n3;
int main()
{
    int T,n;
    double res;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        n1=n2=n3=0;
        for(int i=0;i<MAX_N;i++) for(int j=0;j<MAX_N;j++) graph[i][j]=0;
        for(int i=0;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            graph[x][y]=1;
        }
        for(int i=0;i<MAX_N-10;i++){
            for(int j=0;j<MAX_N-10;j++){
                //printf("i=%d j=%d..\n",i,j);
                if((graph[i][j]&&graph[i+1][j+1])||
                   (graph[i+1][j]&&graph[i][j+1])) n3++;
                else if((graph[i][j]&&graph[i][j+1])||
                        (graph[i][j]&&graph[i+1][j])||
                        (graph[i+1][j]&&graph[i+1][j+1])||
                        (graph[i][j+1]&&graph[i+1][j+1])) n2++;
                else if(graph[i][j]||graph[i][j+1]||graph[i+1][j]||graph[i+1][j+1]) n1++;
            }
        }
        //printf("n1=%d n2=%d n3=%d..\n",n1,n2,n3);
        res=n1*s1+n2*s2+n3*s3;
        printf("%.5lf\n",res);
    }
    return 0;
}

D BLOCKS

連結：http://code.bupt.edu.cn/problem/contest/104/problem/D/

思路：這個當時做了好久一直是re，比賽結束之後又改了幾次還是re（無語了），無奈。

當時的思路是判斷相關的‘#’圖中是否存在一個點四周的非‘#’是否等于三，如果等于三則不為矩形（這裡面有個特殊情況就是寬為1的條需要特殊判斷），否則就是矩形。

一直re呀，後來重寫改了一種更簡單的思路：周遊整個‘#’圖，記錄其中x，y的最大值和最小值，根據最大最小值可以計算一下矩形的面積，再搜尋的時候記錄一下‘#’的個數看二者是否相等如果相等就是矩形，否則就不是，并且将dfs改成bfs，用手寫隊列來代替stl，十分利索，一次就a掉了。

code：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define INF 10000
using namespace std;
 
const int MAX_N=1010;
const int MAX_M=1000002;
 
char graph[MAX_N][MAX_N];
 
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int N,M;
struct ppp{int x,y;} P[MAX_M];
int head,tail;
bool bfs(int x,int y)
{
    graph[x][y]='0';
    int minx=x,miny=y,maxx=x,maxy=y,nn=1;
    head=tail=0;
    P[tail].x=x;
    P[tail++].y=y;
    while(head!=tail){
        int xx=P[head].x,yy=P[head++].y;
        for(int i=0;i<4;i++){
            int midx=xx+dir[i][0],midy=yy+dir[i][1];
            if(midx<0||midy<0||midx>=N||midy>=M) continue;
            if(graph[midx][midy]=='#'){
                nn++;
                minx=min(minx,midx);
                miny=min(miny,midy);
                maxx=max(maxx,midx);
                maxy=max(maxy,midy);
                graph[midx][midy]='0';
                P[tail].x=midx;
                P[tail++].y=midy;
            }
        }
    }
    if((maxx-minx+1)*(maxy-miny+1)==nn) return true;
    return false;
}
 
void solve()
{
    int nn=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(graph[i][j]=='#'){
                if(!bfs(i,j)){
                  printf("So Sad\n");
                  return ;
                }
                else nn++;
            }
        }
    }
    printf("There are %d ships.\n",nn);
    return ;
}
int main()
{
    while(scanf("%d%d",&N,&M)!=EOF){
        for(int i=0;i<N;i++) scanf("%s",graph[i]);
        solve();
    }
    return 0;
}

E 數的關系

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

思路：遞推的方法dp[i][j]=（j+1）*(dp[i-1][j]+dp[i-1][j-1]) dp[i][j] 表示i個數，用j個<号來連結，可以構成的個數。可以讨論第i個數是以什麼

方式更前面i-1個數連結的，如果是‘=’有j+1種，如果是‘<’号也有j+1種，可得遞推式，這題的一個麻煩之處就是資料規模太大得用高精度，直接

套用了一個高精度類水過了。

code：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define INF 10000
using namespace std;
 
const int MAX_N=105;
const int MAX_M=100;
const int maxn = 200;
struct bign{
  int len, s[maxn];
 
  bign() {
    memset(s, 0, sizeof(s));
    len = 1;
  }
 
  bign(int num) {
    *this = num;
  }
 
  bign(const char* num) {
    *this = num;
  }
 
  bign operator = (int num) {
    char s[maxn];
    sprintf(s, "%d", num);
    *this = s;
    return *this;
  }
 
  bign operator = (const char* num) {
    len = strlen(num);
    for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
    return *this;
  }
 
  string str() const {
    string res = "";
    for(int i = 0; i < len; i++) res = (char)(s[i] + '0') + res;
    if(res == "") res = "0";
    return res;
  }
 
  bign operator + (const bign& b) const{
    bign c;
    c.len = 0;
    for(int i = 0, g = 0; g || i < max(len, b.len); i++) {
      int x = g;
      if(i < len) x += s[i];
      if(i < b.len) x += b.s[i];
      c.s[c.len++] = x % 10;
      g = x / 10;
    }
    return c;
  }
 
  void clean() {
    while(len > 1 && !s[len-1]) len--;
  }
 
  bign operator * (const bign& b) {
    bign c; c.len = len + b.len;
    for(int i = 0; i < len; i++)
      for(int j = 0; j < b.len; j++)
        c.s[i+j] += s[i] * b.s[j];
    for(int i = 0; i < c.len-1; i++){
      c.s[i+1] += c.s[i] / 10;
      c.s[i] %= 10;
    }
    c.clean();
    return c;
  }
 
  bign operator - (const bign& b) {
    bign c; c.len = 0;
    for(int i = 0, g = 0; i < len; i++) {
      int x = s[i] - g;
      if(i < b.len) x -= b.s[i];
      if(x >= 0) g = 0;
      else {
        g = 1;
        x += 10;
      }
      c.s[c.len++] = x;
    }
    c.clean();
    return c;
  }
 
  bool operator < (const bign& b) const{
    if(len != b.len) return len < b.len;
    for(int i = len-1; i >= 0; i--)
      if(s[i] != b.s[i]) return s[i] < b.s[i];
    return false;
  }
 
  bool operator > (const bign& b) const{
    return b < *this;
  }
 
  bool operator <= (const bign& b) {
    return !(b > *this);
  }
 
  bool operator == (const bign& b) {
    return !(b < *this) && !(*this < b);
  }
 
  bign operator += (const bign& b) {
    *this = *this + b;
    return *this;
  }
};
istream& operator >> (istream &in, bign& x) {
  string s;
  in >> s;
  x = s.c_str();
  return in;
}
 
ostream& operator << (ostream &out, const bign& x) {
  out << x.str();
  return out;
}
bign dp[MAX_N][MAX_N];
bign ans[MAX_N];
int main()
{
    int n;
    for(int i=1;i<=100;i++){
        ans[i]="0";
        dp[i][0]="1";
        for(int j=1;j<i;j++)    dp[i][j]="0";
    }
    for(int i=2;i<=100;i++){
        for(int j=1;j<=i-1;j++){
            for(int k=0;k<j+1;k++) dp[i][j]+=(dp[i-1][j]+dp[i-1][j-1]);
        }
    }
    for(int i=1;i<=100;i++){
        for(int j=0;j<i;j++){
            ans[i]+=dp[i][j];
        }
    }
    while(scanf("%d",&n)!=EOF){
        cout<<ans[n]<<endl;
    }
  return 0;
}

到此為止就是這樣，加油！！

2014 BUPT 新生排位賽01

繼續閱讀

2020 GDUT Rating Contest Ⅰ G.Livestock Lineup

20.2.25排位賽H

20.2.25排位賽D

2014 BUPT 新生排位賽02

2014 BUPT 新生排位賽06

2014 BUPT 新生排位賽09

2014 BUPT 新生排位賽11

2014 BUPT 新生排位賽04

20.2.25排位賽E

C. Defining Labels

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

2020 GDUT Rating Contest Ⅱ G. Bucket Brigade