【题解】牛客NOIP暑期七天营-提高组3
T1 破碎的矩阵
部分分设置
：
暴力枚举，直接检验。
：暗示正解。
题目思路
考虑在时，对于每个格子可以填
。那么所有的格子对应的数都只有一个二进制位。当所有行异或和的异或和等于所有列异或和的异或和时，在前
行
列的格子随意的填数，第
行和第
列总有唯一合法的填数方案。
考虑在时，对于每个格子对应的数有
个二进制位，且
不受限制，此时相比于
，
个二进制位相互独立，所以在前
行
列的格子随意的填数，第
行和第
列也总有唯一合法的填数方案。
考虑当所有行异或和的异或和不等于所有列异或和的异或和时，矩阵填数一定不合法，此时答案为。否则，矩阵内前
行
列可以随意填数，每个位置有
种填数方案，此时答案为
。
时间复杂度。
考察知识点
位运算，快速幂。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int t,n,m,p,d;
long long x,a[N],b[N],suma,sumb,ans;
long long qpow(long long u,int v){
long long rep=1;
while(v>0){
if(v&1){
rep=(rep*u)%p;
}
u=(u*u)%p;
v>>=1;
}
return rep;
}
int main(){
scanf("%d",&t);
while(t--){
suma=0;sumb=0;
scanf("%d%d%lld%d",&n,&m,&x,&p);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
suma^=a[i];
}
for(int i=1;i<=m;i++){
scanf("%lld",&b[i]);
sumb^=b[i];
}
if(suma!=sumb){
printf("0\n");
continue;
}
++x;
x%=p;
ans=qpow(x,n-1);
ans=qpow(ans,m-1);
printf("%lld\n",ans);
}
return 0;
}
T2 点与面
部分分设置
纯暴力
提示正解
解题思路
对于前30%数据，我们可以暴力枚举五元组，在时间内解决这个问题。
我们考虑枚举W型最中间的点，既，我们考虑
的左边，要找一个比
，还要找一个
，那么实际上，对于
左侧，低于
的点
，对答案的贡献为
左侧比
大的点，我们这一步可以用BIT维护,得到左右两边的贡献之后，使用乘法原理将他们组合，就能计算出答案。
统计时，直接枚举是单次
的，总复杂度
可以得到40%的分数，考虑我们刚才维护的信息，和这个类似，我们也可以用类似的方式，再维护一颗BIT来完成统计。 得到左右两边的贡献之后，使用乘法原理将他们组合，就能计算出答案。
总时间复杂度可以做到，拿到全部分数。
考察知识点
BIT(树状数组)，乘法原理
代码实现
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
const int p = 998244353;
int inc(int a,int b) {
a+=b;
return a>=p?a-p:a;
}
int dec(int a,int b) {
a-=b;
return a<0?a+p:a;
}
int mul(int a,int b) {
return 1LL*a*b%p;
}
int a[5000100],b[5000100],h[5000100],sum1[5001000],sum2[5001000];
int n,ans=0,m=0;
int lowbit(int k)
{
return k&(-k);
}
void add_a(int k)
{
while(k<=m)
{
a[k]=inc(a[k],1);
k+=lowbit(k);
}
}
void add_b(int k,int sum)
{
while(k<=m)
{
b[k]=inc(b[k],sum);
k+=lowbit(k);
}
}
int ask_a(int k)
{
int res=0;
while(k)
{
res=inc(res,a[k]);
k-=lowbit(k);
}
return res;
}
int ask_b(int k)
{
int res=0;
while(k)
{
res=inc(res,b[k]);
k-=lowbit(k);
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;m=max(m,h[i]),i++)
scanf("%d",&h[i]);
for(int i=1;i<=n;i++)
{
add_a(h[i]);
add_b(h[i],dec(ask_a(m),ask_a(h[i])));
sum1[i]=ask_b(h[i]-1);
}
memset(a,false,sizeof(a));
memset(b,false,sizeof(b));
for(int i=n;i>=1;i--)
{
add_a(h[i]);
add_b(h[i],dec(ask_a(m),ask_a(h[i])));
sum2[i]=ask_b(h[i]-1);
}
for(int i=1;i<=n;i++)
ans=inc(ans,mul(sum1[i],sum2[i]));
printf("%d\n",ans);
}
T3 信息传递
部分分设置
：
暴力。
：留给有需要的
复杂度选手。
题目思路
首先，位置是环形的，可以考虑断环为链（长度倍），那么所有人都知道Venn被飞的消息等价于传播的左端点到右端点长度
。
考虑从每个位置开始，第
秒后最远可以将Venn被飞的消息传播到的最左位置
和最右位置
。设答案为
，则
时，
，
时，
。由于
，所以每经过
，边界位置总会扩大，考虑倍增。对于断环为链后的每个位置
，维护从当前位置开始传播
秒后的边界位置
和最右位置
，则有转移
，区间最大/最小值用线段树/ST表维护，然后对于个询问，倍增求出答案即可。
时间复杂度 。
考察知识点
倍增，线段树/ST表。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n, l[17][17][maxn], r[17][17][maxn];
pair<int, int> qry(int i, int l2, int r2) {
int b=31-__builtin_clz(r2-l2+1);
return {max(l[i][b][l2], l[i][b][(r2-(1<<b)+1)%n]-(r2-(1<<b)+1-l2)), max(r[i][b][(r2-(1<<b)+1)%n], r[i][b][l2]-(r2-(1<<b)+1-l2))};
}
int main() {
scanf("%d",&n);
if(n==1) {
puts("0");
return 0;
}
for(int i=0; i<n; ++i)
scanf("%d",&l[0][0][i]);
for(int i=0;i<n;++i)
scanf("%d",&r[0][0][i]);
for(int i=1; i<17; ++i) {
int a=1<<(i-1);
for(int j=0; j<n; ++j) {
l[0][i][j]=max(l[0][i-1][j], l[0][i-1][(j+a)%n]-a);
r[0][i][j]=max(r[0][i-1][(j+a)%n], r[0][i-1][j]-a);
}
}
for(int i=1; i<17; ++i) {
for(int j=0; j<17; ++j) {
int a=1<<j;
for(int k=0; k<n; ++k) {
int l2=k-l[i-1][j][k], r2=k+a-1+r[i-1][j][k];
if(r2-l2>=n-1) {
l[i][j][k]=r[i][j][k]=n;
continue;
}
if(l2<0) {
l2+=n;
r2+=n;
}
tie(l[i][j][k], r[i][j][k])=qry(i-1, l2, r2);
l[i][j][k]+=l[i-1][j][k];
r[i][j][k]+=r[i-1][j][k];
}
}
}
for(int i=0; i<n; ++i) {
int l2=i,r2=i,ans=1,l3,r3;
for(int j=16; j>=0; --j) {
tie(l3, r3)=qry(j, l2, r2);
l3=l2-l3;
r3+=r2;
if(r3-l3<n-1) {
ans+=1<<j;
l2=l3;
r2=r3;
if(l2<0) {
l2+=n;
r2+=n;
}
}
}
printf("%d ",ans);
}
return 0;
}
