牛客练习赛 26

Love The Way You Lie 2022-05-14 13:29 205阅读 0赞

比赛链接：[传送门][Link 1]  
链接：https://www.nowcoder.com/acm/contest/180/A  
A

题目描述  
小a的平面上有n个X型不明物体，但是他不确定他们的位置。现在请你来确定他们的位置，使得划分形成的平面尽量多  
输入描述:  
一个整数n，如题所示  
输出描述:  
一个整数，表示最多把平面分成多少份  
示例1  
输入

2  
输出

平面分割问题，直线划分平面，有个公式就是  
Cn 0+Cn 1+Cn 2  
推导大致是这样的：详见[传送门][Link 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

异或有一个性质就是 x^y=z,然后 x^z=y;  
找出这个集合能不能异或出y  
那么就是线性基经典操作了

#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");
        }
    }

其他的题目日后再记录呜呜呜

[Link 1]: https://www.nowcoder.com/acm/contest/180#question
[Link 2]: https://blog.csdn.net/fandoudou123/article/details/50974806