牛客練習賽 26

比賽連結：​​傳送門​​​ 連結：https://www.nowcoder.com/acm/contest/180/A

A

題目描述

小a的平面上有n個X型不明物體，但是他不确定他們的位置。現在請你來确定他們的位置，使得劃分形成的平面盡量多

輸入描述:

一個整數n，如題所示

輸出描述:

一個整數，表示最多把平面分成多少份

示例1

輸入

2

輸出

11

平面分割問題，直線劃分平面，有個公式就是

Cn 0+Cn 1+Cn 2

推導大緻是這樣的：詳見​​傳送門​​ 當有n-1條直線時，平面最多被分成了f（n-1）個區域。則第n條直線要是切成的區域數最多，就必須與每條直線相交且不能有同一交點。這樣就會得到n-1個交點。這些交點将第n條直線分為2條射線和n-2條線斷。而每條射線和線斷将以有的區域一分為二。這樣就多出了2+（n-2）個區域。

f(n)=f(n-1)+n

=f(n-2)+(n-1)+n

=……

=f(1)+1+2+……+n

=n(n+1)/2+1

#include<stdio.h>
int main()
{ 
   long long n,L1;
   scanf("%lld",&n);
    n=n*2;
      L1=(n*n+n+2)/2;      //直線劃分平面 
       
      printf("%lld\n",L1);
   
   return 0;
}      

連結：https://www.nowcoder.com/acm/contest/180/B

B

題目描述

小a有個煙花，每個煙花代表着互不相同的顔色，對于第個煙花，它有的機率點燃，現在小a要去點燃它們，他想知道産生顔色的期望個數 及 産生恰好産生種顔色的機率

輸入描述:

第一行兩個整數

接下來一行個數，第個數表示第個煙花被點燃的機率

輸出描述:

輸出有兩行

第一行表示産生不同顔色的期望個數

第二行表示産生恰好種顔色的機率

以換行符分割

每種顔色的個數是1。期望的線性性質

，積分 ans就等于xi*pi的積分了，等于機率之和

第二問，dp[i][j]表示目前有i個煙花恰好有j個煙花被點燃。

#include<cstdio>
#include<algorithm>
using namespace std;
double p[1000005],dp[100005][105];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    double ans=0;
    for (int i=1; i<=n; i++){
        scanf("%lf",&p[i]);
        ans+=p[i];
    }
    printf("%0.4lf\n",ans);
    dp[0][0]=1;
    for (int i=1; i<=n; i++){
    
        for (int j=0; j<=min(i,k); j++){
            dp[i][j+1]+=dp[i-1][j]*p[i];
            
            dp[i][j]+=dp[i-1][j]*((double)1-p[i]);
          
        }
    } 
    printf("%0.4lf\n",dp[n][k]);
   
}      

如果題目卡空間的話，就需要用到滾動數組優化，放标程了

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 100001;
int N, K;
double p[MAXN], f[2][MAXN];
int main() {
    scanf("%d %d", &N, &K);
    double sum = 0;
    for(int i = 1; i <= N; i++) scanf("%lf", &p[i]), sum += p[i];
    printf("%.4lf\n", sum);
    int o = 0;
    f[o][1] = p[1]; f[o][0] = 1 - p[1];
    for(int i = 2; i <= N; i++) {
        o ^= 1;
        for(int j = 0; j <= min(i, K); j++)
            f[o][j] = f[o ^ 1][j - 1] * p[i] + f[o ^ 1][j] * (1 - p[i]);
    }
    printf("%.4lf", f[o][K]);
    return 0;
}      

連結：https://www.nowcoder.com/acm/contest/180/C

C

題目描述

小a的國家裡有n個城市，其中第i和第i - 1個城市之間有無向道路連接配接，特殊的，第1個城市僅與第2個城市相連

為了減輕道路維護負擔，城市規劃局局長MXT給出了m個要求，他想讓小a斷開一些道路，使得任意1 ≤ i ≤ m ，城市xi不能到達城市yi

同時最小化斷開道路的數量。

輸入描述:

第一行兩個整數n, m，分别表示城市的數量和請求的數量

接下來m行，每行兩個整數x,y，表示需要使得x不能到達y

輸出描述:

輸出一個整數，表示最小斷開橋的數量

示例1

輸入

4 2

1 3

2 4

輸出

1

說明

可以斷開(2, 3)城市之間的道路

貪心

考慮一個很顯然的 O(mlog(m))的做法 首先對所有線段按照右端點排序，然後每次在右端點處切 但是m達到了 10^7級别

題目保證所有線段的值域為1-n ，我們可以對所有左端點，直接記錄出右端點最靠左的 位置 同樣每次切右端點，掃一遍即可 時間複雜度: O(m)

#include<cstdio>
const int MAXN = 1e6 + 10;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
#define min(a, b) (a < b ? a : b)
char buf[(1 << 22)], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
int r[MAXN];
int main() {
    N = read(); M = read();
    for(int i = 1; i <= N; i++) r[i] = N + 1;
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read();
        r[x] = min(y, r[x]);
    }
    int cur = N + 1, ans = 0;
    for(int i = 1; i <= N; i++) {
        cur = min(cur, r[i]);
        if(i == cur) cur = r[i], ans++;
    }
    printf("%d", ans);
    return 0;
}      

連結：https://www.nowcoder.com/acm/contest/180/D

D

題目描述

小a有n個數，他提出了一個很有意思的問題：他想知道對于任意的x, y，能否将x與這n個數中的任意多個數異或任意多次後變為y

輸入描述:

第一行為一個整數n，表示元素個數

第二行一行包含n個整數，分别代表序列中的元素

第三行為一個整數Q，表示詢問次數

接下來Q行，每行兩個數x,y，含義如題所示

輸出描述:

輸出Q行，若x可以變換為y，輸出“YES”，否則輸出“NO”

示例1

輸入

5

1 2 3 4 5

3

6 7

2 1

3 8

輸出

YES

YES

NO

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 32, B = 31;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N;
int P[MAXN];
void Insert(int x) {
    for(int i = B; i >= 0; i--) {
        if((x >> i) & 1) {
            if(!P[i]) {P[i] = x; break;}
            x ^= P[i];
        }
    }
}

int Query(int x) {
    for(int i = B; i >= 0; i--) {
        if((x >> i) & 1) {
            if(!P[i]) return 0;
            x ^= P[i];
        }
    }
    if(x == 0) return 1;
    else return 0;
}

int main(){ 
    N = read();
    for(int i = 1; i <= N; i++) {
        int val = read(); Insert(val);
    }
    int Q = read();
    while(Q--) {
        int x = read(), y = read();
        if(Query(x ^ y)) puts("YES");
        else puts("NO");
    }
}