20230304模拟赛（jnxxhzz）-JZTXT

T1.海盗游戏

暴力：每一轮枚举可以有效攻击的人用链表记录（80分）

优化：如何过后面的20分？

可以模拟每一次进攻，发现每一轮有重复的攻击

第一轮：A->B->C->D->E->A，其中B把C干掉了

第二轮：A->B->D->E->A，其中只有C的左右两个攻击是之前没有的

那么第二轮有效攻击的人一定是上一轮成功攻击的人

用队列维护每一轮出局的人

每一次就用队列中的l[i]去攻击r[i]

GCD小优化：

预处理 G[1000][1000]，这样复杂度可以大约除以8

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+10;
int n,m,k,l[maxn],r[maxn],a[maxn],b[maxn],x,y,cnt=0,ans=0,g[1005][1005];
bool flag,vis[maxn];

int get_number(){
  k=k*214013+2531011;
  return (abs(k))%n+1;
}

int gcd(int x,int y){
  if(y==0) return x;
  return gcd(y,x%y);
}

queue<int>q[3],qq;

int main(){
  scanf("%d%d%d",&n,&m,&k);
  for(int i=1;i<=n;i++) b[i]=i;
  for(int i=1;i<=m;i++){
      x=get_number();y=get_number();
      swap(b[x],b[y]);
  }
  for(int i=1;i<=n;i++){
      if(b[i]==1){
        for(int j=i;j<=n;j++) a[j-i+1]=b[j];
      for(int j=1;j<i;j++) a[n-i+1+j]=b[j];    
      break;
    }//把1挪到最前面 
  }
  for(int i=1;i<=n;i++){
      if(i!=1) l[i]=i-1;
      else l[i]=n;
      if(i!=n) r[i]=i+1;
      else r[i]=1;
  }
  memset(vis,false,sizeof(vis));
  for(int i=2;i<=n;i++)//1不用判断 
      if(gcd(a[l[i]],a[i])!=1){
        q[1].push(i);vis[i]=true;
      //r[l[i]]=r[i];l[r[i]]=l[i];如果在这里更新会影响后面的gcd，有可能错过一些有效攻击 
      ans++;    
    }
  flag=true;cnt=1;
  while(flag){
    flag=false;
    while(!q[cnt].empty()){
      flag=true;
      int now=q[cnt].front();q[cnt].pop();
      r[l[now]]=r[now],l[r[now]]=l[now];
      if(!vis[r[now]]&&gcd(a[l[now]],a[r[now]])!=1){
      //如果现在的r[now]被删了，就不用比较了，在后面的某一个位置会补上 
          ans++;
          q[cnt^1].push(r[now]);vis[r[now]]=true;
      }
    }
    cnt^=1;
  }
  printf("%d\n",n-ans);
  return 0;
}

生成函数不要改动，有些时候要的就是爆int的效果

T2.粮食放大器

转乘为加: $2^{k_i}=p_1*p_2*\dots*p_x$ 编辑

$2^{k_i}=2^{\log p_1}*2^{\log p_2}*\dots *2^{\log p_x}$ 编辑

$k_i=\log p_1+\log p_2+\log p_3+ \dots +log p_x$ 编辑

n<=100?-->网络流（但是很明显不行）

二分？

二分粮食放大次数，那么如何check？

dp[i][j]表示走了i步后可以转化出j类粮食最大值

dp[i][j]=max(dp[i-1][k]+a[k][j]) 复杂度 O(qnk log k)

考虑如何优化check

n是点数，是不能优化的

那么只有优化k

我们想要快速跳到k步之后-->倍增

预处理dp[i][j][k]表示i号粮食在花了 $2^k$ 编辑步后变成j的最大值

复杂度O(qn log k log k)

代码：

#include <bits/stdc++.h>
using namespace std;

int n,q,x,ans=0;
double dp[105][105][21],a[105][105];
bool flag;

void init(){
  for(int t=1;t<=20;t++)
    for(int k=1;k<=n;k++)
      for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
          dp[i][j][t]=max(dp[i][j][t],dp[i][k][t-1]+dp[k][j][t-1]);
          dp[i][j][t]=max(dp[i][j][t],dp[i][j][t-1]);
        }
          
}

void getans(int st,int k){
  double tmp[105],p[105];
  ans=0;flag=false;
  for(int i=1;i<=n;i++) tmp[i]=-9999999;
  tmp[st]=0;//**tmp[st]!=1**
  for(int t=20;t>=0;t--){
      flag=false;
      for(int i=1;i<=n;i++)
        if(tmp[i]+dp[i][st][t]>=k){flag=true;break;}
      if(flag) continue;
      ans+=(1<<t);
      for(int i=1;i<=n;i++) p[i]=tmp[i];
      for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
          p[j]=max(p[j],tmp[i]+dp[i][j][t]);//不能是p[i]+dp[i][j][t] 
      for(int i=1;i<=n;i++) tmp[i]=p[i];
  }
  printf("%d\n",ans+1);
}

int main(){
  scanf("%d%d",&n,&q);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
      scanf("%d",&x);
      if(x==0) a[i][j]=-999999;
      else a[i][j]=log(x)/log(2);
      dp[i][j][0]=a[i][j];
    }
  init();
  for(int i=1;i<=q;i++){
      int pos;
      scanf("%d%d",&pos,&x);
      getans(pos,x);
  }
  return 0;
}

T3.最大前缀和

很显然是线段树，一定要画图

考虑维护什么？每个区间的max和sum

1.左儿子mx>=右儿子mx 说明右儿子的所有premax=左儿子mx

左区间的贡献为：左儿子sum

右区间的贡献为：左儿子mx*(r-mid)

2.左儿子mx<右左儿子mx

左区间的贡献为：左儿子sum

右区间的贡献为：

右右儿子的贡献为：右儿子sum-右左儿子sum

右左儿子的贡献为：递归计算

3.左儿子mx>右左儿子mx

左区间的贡献为：左儿子sum

右区间的贡献为：

右左儿子的贡献为：(mid-l+1)*左儿子mx

右右儿子的贡献为：递归计算

4.递归到叶子节点

写法和普通线段树差不多

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

const int maxn=3e5+10;
int n,m,pos;
ll a[maxn],x;
struct node{
  ll mx,siz,sum;
}tr[maxn*4];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

ll llread(){
  ll x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void pushup(int rt){
  tr[rt].mx=max(tr[rt<<1].mx,tr[rt<<1|1].mx);
  tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum; 
}

ll add(int l,int r,int rt,ll val){//递归求每个区间的sum
  if(tr[rt].mx<val) return 1ll*val*tr[rt].siz;
  if(l==r) return tr[rt].mx;//递归到叶子节点返回 
  if(val<tr[rt<<1].mx) return add(lson,val)+tr[rt<<1|1].sum;
  else return add(rson,val)+1ll*val*tr[rt<<1].siz;
}

void build(int l,int r,int rt){
  tr[rt].siz=r-l+1;
  if(l==r){
      tr[rt].mx=tr[rt].sum=a[l];
      return ;
  }
  build(lson);build(rson);
  tr[rt<<1|1].sum=add(rson,tr[rt<<1].mx);
  pushup(rt);
}

void update(int l,int r,int rt,int pos){
  if(l==r){
      tr[rt].mx=tr[rt].sum=a[l];
      return;
  }
  if(pos<=mid) update(lson,pos);
  else update(rson,pos);
  tr[rt<<1|1].sum=add(rson,tr[rt<<1].mx);
  pushup(rt);
}

int main(){
  n=read();
  for(int i=1;i<=n;i++) a[i]=llread();
  m=read();
  build(1,n,1);
  for(int i=1;i<=m;i++){
      pos=read();x=llread();
      a[pos]=x;
      update(1,n,1,pos);
      printf("%lld\n",tr[1].sum);
  }
  return 0;
}

总结：

1.冷静分析，注意时间，先把暴力打出来

2.不要着急写代码，理清思路后在开始，有些时候可以用倍增进行优化，可以模拟代码实现过程，线段树画图