2020牛客多校第六场

B Binary Vector

链接：https://ac.nowcoder.com/acm/contest/5671/B
题意：
给定一串数列f，可以找出他们的规律f[i]=f[i-1](2^i-1)/2^i.求f[1]^....f[n]异或和
题解：
由小费马引理可知：a/b%mod=ab^(mod-2)%mod;令初值1/2%mod=q;每次只需要再原来的f[i-1]之上q(2^i-1)；打表把所有的f[i]求出来
注意：
%mod
代码：

#include<bits/stdc++.h>
const int mod=1e9+7;
const int maxn=2e7+10;
using namespace std;
typedef long long ll;

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans % mod;
}
ll ans[maxn];
int main()
{
    //费马小定理：a/b%p=a*b^(p-2)     第一次操作时，p=1,q=2^(mod-2) ,之后q=4^(mod-2)  8^(mod-2),
    ll p=1,q=quick_pow(2,mod-2),now=2,inv=q,ori=q;
    //printf("%lld",q);

    for(int i=1;i<=2e7;i++)
    {
        ans[i]=(p*q)%mod;//直接放进去一起计算了
        now=(now*2)%mod;//now-1   ->1 3      2, 4
        p=(p*(now-1))%mod;
        inv=(inv*ori)%mod;
        q=(q*inv)%mod;//有直接乘以之前的ans[i-1];
    }//求得就是每一个f[i]
    for(int i=2;i<=2e7;i++)ans[i]^=ans[i-1];
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);

        printf("%lld\n",ans[n]);
    }
    return 0;
}

C Combination of Physics and Maths

链接：https://ac.nowcoder.com/acm/contest/5671/C
题意：
给定一个矩阵，框中一个区域，可以删去行或者列，构成一个新的矩阵，求这样的矩阵的和加起来x，除以最下面一行的所有和y,x/y的值最大为多少
题解：
a/b c/d max(a/b,c/d)>a+b/c+d即求出某一列列里面的前缀和/最后一行的数最大的值
注意：
不仅可以删除列，还可以删除行，当然是从后往前删
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
double matr[210][210];
double line[210][210];
double cha[210][210];

int main() {
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        double maxn = 0.0;
        memset(matr, 0.0, sizeof(matr));
        memset(line, 0.0, sizeof(line));
        memset(cha, 0.0, sizeof(cha));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%lf", &matr[i][j]);
                line[i][j] = line[i - 1][j] + matr[i][j];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cha[i][j] = line[i][j] * 1.0 / matr[i][j];
            }

            sort(cha[i] + 1, cha[i] + m+1);
            if (maxn < cha[i][m])maxn = cha[i][m];
        }
        /*for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                printf("%.2lf ", cha[i][j]);
            }
            printf("\n");
        }*/
        printf("%.8lf\n", maxn);
    }
    return 0;
}

K K-Bag

链接：https://ac.nowcoder.com/acm/contest/5671/K
题意：
定义k-bag:1~ k不重复的随机排列，这样有无数个排列连在一起构成一个合理的排列，给定一个一定的字符串，问是否是这个排列的子序列
题解：
先离散化一下，把字符串中所有出现的数字，整合一下，重新表示。再遍历每一个对应的编号，在每两个相同的相邻编号之间，用数组d[k]的形式来表示i%k,和之前编号c[a[i]]%k在他们的区间内，用前缀和表示，左加右减，若出现后面的编号%k>前面编号%k,那么就是在前面编号%k~ k,0~ 后面编号%k，表示连续。这些的前缀和==进入这个循环的个数，则他们都好好的待在自己的序列里头
注意：
左加右减，在相同的编号上，这样后面那个编号不计入这次的循环中，而是在下一个循环中大显身手。详情看看代码吧，我太low了。
代码：

2020牛客多校第六场

B Binary Vector

C Combination of Physics and Maths

K K-Bag

全站热榜