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