牛客NOIP暑期七天营-提高组3
目录
A-破碎的矩阵
题目描述 link
题解
标签：推结论+快速幂
挺妙的一道题？？比赛的时候想到了但不敢确定正确性。
首先很容易想到，对于一个二进制数它的每一位都是独立的。那么下面的结论对于\(x=1\)和\(x=2^{30}-1\)和\(2^{60}-1\)这三组都同样适用。
大致思路就是对于一个\(n*m\)的矩阵，它左上角的子矩阵\((n-1)*(m-1)\)先随便怎么填，剩下的第\(n\)行，第\(m\)列根据剩余的异或值来进行调整，那么对于子矩阵中的任意一组填法，剩下的一列一行都有且仅有一组相应的填法。那么最终答案就为\(ans=(x+1)^{(n-1)*(m-1)}\)，底是\(x+1\)是因为对于子矩阵来说，每个元素的取值范围为\([0，x]\)，共\(x+1\)个数。
当然大前提是该组数据有解。如何判呢，只要把每行的值异或起来，把每列的值异或起来，若两者不相等则无解，输出0。
则总的时间复杂度为\(O(case*log(nm))\)。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll x,mod;
ll ksm(ll r,ll d){
ll res=1;
while(d){
if(d&1)res=res*r%mod;
r=r*r%mod;d>>=1;
}
return res;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d%lld%lld",&n,&m,&x,&mod);
ll sx=0,sy=0;
for(int i=1;i<=n;i++){
ll w;scanf("%lld",&w);
sx^=w;
}
for(int i=1;i<=m;i++){
ll w;scanf("%lld",&w);
sy^=w;
}
if(sx!=sy){puts("0");continue;}
ll ans=ksm((x+1)%mod,1ll*(n-1)*(m-1));
printf("%lld\n",ans);
}
}
B-点与面
题目描述 link
题解
标签：树状数组裸题
就是计个数的事，感觉难度比第一题简单很多。。
维护4个树状数组，然后循环一遍边计数边往上加就完事了，注意顺序应该是从\(5->4->3->2->1\)不然可能会出现重复计数。
时间复杂度为\(O(NlogN)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"### "<<x<<endl;
#define For(a,b,c) for(int a=b;a<=c;++a)
#define Dor(a,b,c) for(int a=b;a>=c;--a)
typedef long long ll;
const int N=1e5+10;
const ll mod=998244353;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
int n,num,a[N],b[N];
ll c[5][N];
inline ll askA(int x,int id){
ll res=0;
while(x){
res+=c[id][x],res%=mod;
x-=x&(-x);
}
return res;
}
inline ll askB(int x,int id){
ll res=0;
while(x<=num){
res+=c[id][x],res%=mod;
x+=x&(-x);
}
return res;
}
inline void addA(int x,ll d,int id){
while(x<=num){
c[id][x]+=d,c[id][x]%=mod;
x+=x&(-x);
}
}
inline void addB(int x,ll d,int id){
while(x){
c[id][x]+=d,c[id][x]%=mod;
x-=x&(-x);
}
}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i];
sort(b+1,b+n+1);
num=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+num+1,a[i])-b+1;
num++;
ll ans=0;
for(int i=1;i<=n;i++){
//5
ll tmp=askA(a[i]-1,4)%mod;
ans+=tmp,ans%=mod;
//4
tmp=askB(a[i]+1,3)%mod;
addA(a[i],tmp,4);
//3
tmp=askA(a[i]-1,2)%mod;
addB(a[i],tmp,3);
//2
tmp=askB(a[i]+1,1)%mod;
addA(a[i],tmp,2);
//1
addB(a[i],1,1);
}
printf("%lld\n",ans%mod);
}
C-信息传递
题目描述 link
题解
标签：断环为链+线段树区间维护最值+倍增
算法一：
适用于：60%数据，\(li,ri<=n<=10^3\)。
构图：很容易想到将问题转化为图上的最短路。对于某个人\(i\)，它的传播范围为\([li,ri]\)，我们由\(i\)向这个区间的所有点连一条边；
计算：对于每个点\(i\)，我们以其为源点跑一遍Dijkstra求出单源最短路，然后再枚举n个点，找出其中最远的距离\(dis_j\)，这个值就是答案。
时间复杂度为\(O(N^2logN)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
bool nc1;
inline int read(){}
int id[2*N],n;
namespace p60{
bool f[1010][1010];
int dis[1010],vis[1010];
vector<int>e[1010];
struct node{
int w,now;
inline bool operator <(const node &x)const{
return w>x.w;
}
};
priority_queue<node>q;
void dijkstra(int s){
for(register int i=1;i<=n;i++)dis[i]=n,vis[i]=0;
dis[s]=0;
q.push((node){0,s});
while(!q.empty()){
node x=q.top();
q.pop();
int u=x.now;
if(vis[u])continue;
vis[u]=1;
for(register int i=0;i<e[u].size();i++){
int v=e[u][i];
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
q.push((node){dis[v],v});
}
}
}
}
void solve(){
for(register int i=1;i<=n;i++){
int l=read();
for(register int j=i+n-1;j>=i+n-l;j--)if(!f[id[i]][id[j]]){
f[id[i]][id[j]]=1;
e[id[i]].push_back(id[j]);
}
}
for(register int i=1;i<=n;i++){
int r=read();
for(register int j=i+1;j<=i+r;j++)if(!f[id[i]][id[j]]){
f[id[i]][id[j]]=1;
e[id[i]].push_back(id[j]);
}
}
for(register int i=1;i<=n;i++){
int ans=0;
dijkstra(i);
for(register int j=1;j<=n;j++)if(dis[j]>ans)ans=dis[j];
printf("%d ",ans);
}
}
}
int li[N],ri[N];
bool nc2;
int main(){
n=read();
for(int i=1;i<=n;i++)id[i]=id[i+n]=i;
if(n<=1000){
p60::solve();
return 0;
}
}
算法二：
适用于：100%数据，\(li,ri<=n<=10^5\)。
首先断环为链，开三倍数组。
我们发现对于每一秒的传递，\(i\)能传到的最左边的人要么不变要么更左，\(i\)能传到的最右边的人要么不变要么更右。并且，[最左的人，最右的人]这一段区间里的所有人在此时都已经收到消息了。
根据这个单调性，我们可以维护两个数组\(li[x][i]，ri[x][i]\)，表示在\(2^i\)秒时，\(x\)能传递到的最左最右的人，看出用了倍增吧，那么询问时也可以利用倍增跳来快速找出答案。
接下来的任务就是如何维护呢——官方题解中给出了ST表维护最值，下面的代码中用的是线段树。
对于树上的节点\(o\)我们维护两个数组\(b[o][t][0/1]\)，表示在\(2^t\)秒内节点\(o\)包括的范围\([l,r]\)中，能跳的最左，能跳的最右。
接下来一个时间一个时间的转移维护，查询时也是在树上进行的。
总的时间复杂度为\(O(Nlog^2N)\)
详见代码8：
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
const int N=3e5+10;
int n,li[N][18],ri[N][18];
int b[N<<2][18][2];
int limL,limR,k,len;
void build(int o,int l,int r){
if(l==r){
b[o][k][0]=li[l][k];
b[o][k][1]=ri[l][k];
return;
}
int mid=l+r>>1;
build(o<<1,l,mid),build(o<<1|1,mid+1,r);
b[o][k][0]=min(b[o<<1][k][0],b[o<<1|1][k][0]);
b[o][k][1]=max(b[o<<1][k][1],b[o<<1|1][k][1]);
}
void query(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
limL=min(limL,b[o][k][0]);
limR=max(limR,b[o][k][1]);
return;
}
int mid=l+r>>1;
if(ql<=mid)query(o<<1,l,mid,ql,qr);
if(qr>mid)query(o<<1|1,mid+1,r,ql,qr);
}
int main(){
n=read();len=3*n;
for(register int i=1;i<=n;i++){
int x=read();
for(register int j=i;j<=len;j+=n)li[j][0]=max(1,j-x);
}
for(register int i=1;i<=n;i++){
int x=read();
for(register int j=i;j<=len;j+=n)ri[j][0]=min(3*n,j+x);
}
if(n==1){puts("0");return 0;}
build(1,1,len); for(k=1;k<=17;k++){
for(register int i=1;i<=len;i++){
limL=1e9,limR=0;
k--;
query(1,1,len,li[i][k],ri[i][k]);
k++;
li[i][k]=limL,ri[i][k]=limR;
}
build(1,1,len);
} for(register int i=n+1;i<=n+n;i++){
int l=i,r=i,ans=0;
for(k=17;k>=0;k--){
limL=1e9,limR=0;
query(1,1,len,l,r);
if(limR-limL+1>=n)continue;
l=limL,r=limR,ans+=1<<k;
}
printf("%d ",ans+1);
}
}
