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了。
代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
int a[maxn],b[maxn],c[maxn],d[maxn],ans,sum,cnt,n,t,k;
int main()
{
    for(scanf("%d",&t);t--;)
    {
        memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(d,0,sizeof(d));
        bool flag=1;cnt=0;d[0]=0;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>k)flag=0;
            b[i]=a[i];
            c[i]=d[i]=0;//初始化
        }
        if(!flag){
            printf("NO\n");continue;
        }
        sort(b+1,b+n+1);
        sum=unique(b+1,b+n+1)-b-1;// 这个unique函数在sort排序后，进行一个去重，会把不重复的都放在前面给替换掉，而剩下的数不进行改变
        // 实际上这个sum就相当于不重复的数的个数
        for(int i=1;i<=n;i++)
        {
            a[i]=lower_bound(b+1,b+1+sum,a[i])-b;//位置，第一个等于a[i]的位置
            //这个步骤就是把一些可能断着的数字放在一起来统计了
        }
        for(int i=1;i<=n;i++)
        {
            if(c[a[i]]&&i-c[a[i]]<k)//表示之前的那个相同的数和它距离小于k,如果大于k就不用进行判定了，直接成立然后末尾更新
            {
                d[c[a[i]]%k]++;//左端点+1
                cnt++;//统计所有进入这个循环的个数
                if(c[a[i]]%k<i%k)d[i%k]--;//右端点-1
                else d[min(k,n-1)]--,d[0]++,d[i%k]--;//以两个数之间为一个区间加上去。
            }
            c[a[i]]=i;//i表示的是这个数真正的顺序

        }
        if(d[0]==cnt){printf("YES\n");continue;}
        else
        {
            for(int i=1;i<=n;i++)
            {
                d[i]+=d[i-1];
                if(d[i]==cnt){printf("YES\n");flag=0;break;}
            }
        }
        if(flag)printf("NO\n");

    }
    return 0;

}