ABC286 A-E题解

题目

虽然是大年三十，但是玩手机没写题有意思。从 50 分钟才开始看题。

A

题意：将数组中 \([p,q]\) 与 \([r,s]\) 的元素交换并输出。
sbt。

B

大意：将字符中的 na 换成 nya。
sbt。

C

题意：两种操作，将第一个元素换到最后花费 \(A\)，任意改变一个元素，花费 \(B\)。求将其变成回文串的最小花费。

猜了个结论，一操作只会在一开始做。于是就枚举一操作做几次，然后暴力扫一遍要改几个。

const int N=1e6+7,inf=1e18;
char c[N],s[N];
main(){
  int n,A,B,ans=inf;read(n);read(A);read(B);
  scanf("%s",c+1);
  for(int i=0;i<=n;i++){
    int res=i*A;
    for(int j=1;j<=n-i;j++)
      s[j]=c[i+j];
    for(int j=n-i+1,k=1;j<=n;j++,k++)s[j]=c[k];
    for(int j=1;j<=n-j+1;j++)
      if(s[j]!=s[n-j+1])res+=B;
    ans=min(ans,res);
  }
  cout<<ans;
  return 0;
}

D

题意：有 \(n\) 种硬币，第 \(i\) 种面值 \(a_i\) 元有 \(b_i\) 个，问能否凑出 \(x\) 元。

经典凑数字题，\(f_{i,j}\) 表示前 \(i\) 种硬币能否凑出 \(j\) 元，转移就是 \(f_{i,j}|=f_{i-1,j-ka_i}(0\le k \le b_i 且 j-ka_i\ge 0)\)，第一维需要滚掉。

const int N=1e6+7,inf=1e18,M=5e7+7;
bool f[M];
int a[N],b[N];
main(){
  int n,x;read(n);read(x);
  for(int i=1;i<=n;i++)read(a[i]),read(b[i]);
  f[0]=1;
  for(int i=1;i<=n;i++)for(int j=x;j>=0;j--)for(int k=0;k<=b[i];k++)
    if(j-a[i]*k>=0)f[j]|=f[j-a[i]*k];
  puts(f[x]?"Yes":"No");
  return 0;
}

E

题意：给定一个图，每个点有点权，多次询问 \(s\) 到 \(t\) 的最短路中经过点权和最大的那一种。

类似最短路计数，在 Floyd 的基础上定义 \(f_{i,j}\) 表示 \(i\) 到 \(j\) 的最短路中最大的点权和，初始化 \(f_{i,i}=a_i\)，若 \((i,j)\) 有边，则 \(f_{i,j}=a_i+a_j\)。转移就是跑 Floyd 时加一个相等时的判断。

const int N=307,inf=1e9+7;
int dis[N][N],a[N],f[N][N];
char c[N];
main(){
  int n;read(n);
  for(int i=1;i<=n;i++)read(a[i]),f[i][i]=a[i];
  for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=inf;
  for(int i=1;i<=n;i++){
    scanf("%s",c+1);
    for(int j=1;j<=n;j++)
      if(c[j]=='Y')dis[i][j]=1,f[i][j]=f[i][i]+f[j][j];
  }
  for(int k=1;k<=n;k++)
  for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++){
    if(dis[i][k]+dis[k][j]<dis[i][j])
      dis[i][j]=dis[i][k]+dis[k][j],f[i][j]=f[i][k]+f[k][j]-a[k];//多算一个 a[k]，下面同理。
    else if(dis[i][k]+dis[k][j]==dis[i][j])
      f[i][j]=max(f[i][j],f[i][k]+f[k][j]-a[k]);
  }
  int q;read(q);
  while(q--){
    int x,y;
    read(x);read(y);
    if(dis[x][y]==inf){puts("Impossible");continue;}
    printf("%lld %lld\n",dis[x][y],f[x][y]);
  }
  return 0;
}