题解：USACO23OPEN-Silver
T1 Milk Sum
给定一个长度为 \(N\) 的序列 \(a_1,a_2,...,a_n\)，现在给出 \(Q\) 次操作每次将 \(a_x\) 修改为 \(y\) ， 每次修改后，求将序列重排后的 \(T\) 的最大值，定义 \(T=\sum_{i=1}^{n}i \times a_i)\)
每次修改数组后会将序列还原成原样（修改不继承）
有一个显然的结论：对于\(\forall 0<a<b, 0<c<d\) ,满足\(a*c+b*d<a*d+b*c\)
所以将序列从小到大排序得到的 \(T\) 一定更大
所以预先把排好的原序列存下来，对于每次修改只需要二分出修改后应放的位置，然后（1）减掉原来数的贡献，（2）加上现在数的贡献，（3）所有位置后挪1或前挪1的贡献变化
#include<bits/stdc++.h>
using namespace std;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define ll long long
#define ull unsigned long long
#define mem(a) memset(a,0,sizeof(a))
const int N=2e5+5;
int n,q;
struct node{ int id; ll x; }a[N];
ll b[N],c[N];
ull sum[N],tot=0;
inline bool cmp1(const node &u,const node &v){ return u.x==v.x ? u.id<v.id : u.x<v.x; }
inline bool cmp2(const node &u,const node &v){ return u.id<v.id; }
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&n);
F(i,1,n) scanf("%lld",&a[i].x),a[i].id=i;
sort(a+1,a+n+1,cmp1);
F(i,1,n) b[i]=a[i].x,c[a[i].id]=i;
F(i,1,n) sum[i]=sum[i-1]+b[i],tot+=1ll*b[i]*i;
sort(a+1,a+n+1,cmp2);
scanf("%d",&q); while(q--){
int i,j;
scanf("%d %d",&i,&j);
int w=upper_bound(b+1,b+n+1,j)-b;
if(a[i].x<j){//bigger
--w;
// printf("w1=%d\n",w);
ull res=tot-1ull*a[i].x*c[i]+1ull*w*j-(sum[w]-sum[c[i]]);
printf("%llu\n",res);
}
else if(a[i].x==j) printf("%lld\n",tot);
else{//smaller
ull res=tot-1ull*a[i].x*c[i]+1ull*w*j+(sum[c[i]-1]-sum[w-1]);
printf("%llu\n",res);
}
}
return 0;
}
T2 Field Day
（又是逆向思维题...）
给出 \(N\) 个长度为 \(C\) 的 \(GH\) 串，将 \(G\) 看作 \(0\) ，将 \(H\) 看作 \(1\) ， 则每个串可看做01串，对于每个 \(i\) ，求 \(max_{j=1}^{n} popcount(a_i \oplus a_j)\)
\(2 \leq N \leq 10^5,1 \leq C \leq 18\)
暴力是 \(O(N^2)\) 的，发现本题的特点如下：
（1） \(C\) 很小，算一下本质不同的 \(01\) 串只有 \(2^{18}\) 个，大概是25万多一点。
※（2）最大值不是很好求，考虑倒过来想，转化成求最小值。
（3）与串 \(a_i\) 差异度为 \(k\) 的一个串 \(t\) 可以看做是 将 \(a_i\) 的其中 \(k\) 个数一步一步取反后得到的。
一个数可以由多个给出的串通过这样的取反变化得到，但我们只关心至少要改变几个数位才能得到 \(t\)（求最小值嘛），所以如果我们能找到一种操作顺序，使第一次得到 \(t\) 花的就是最少步数的话，那\(0-2^c-1\) 下的每个数都只需要访问一遍就可以了！
什么样的操作顺序使我们需要的呢？灵光一现，考虑广搜，先搜出每个串改1个数位能得到的结果，再考虑改2个数，再改3个，4个....一直到 \(c\) 个，每次都把上一层更新出的数存下来用于下一层更新，访问过的数不再重复访问，时间复杂度 \(O(2^C)\)。
广搜写法：
#include<cstdio>
#include<queue>
using namespace std;
#define ri register int
#define F(i,l,r) for(ri i=l;i<=r;++i)
const int N=1e5+5;
queue<int> q;
int c,n,a[N],f[(1<<18)+100];
char s[22];
bool vis[(1<<18)+100];
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d%d",&c,&n);
F(i,1,n){
scanf("%s",s+1);
int sum=0;
F(j,1,c) sum=(sum<<1)+(s[j]=='G');
a[i]=sum; q.push(sum); vis[sum]=1;
}
while(q.size()){
int x=q.front();q.pop();
F(i,1,c){
int y=x^(1<<(i-1));
if(vis[y] || f[y]) continue;
f[y]=f[x]+1;
vis[y]=1; q.push(y);
}
}
F(i,1,n) printf("%d\n",c-f[(1<<c)-1-a[i]]);
return 0;
}
用循环模拟广搜：
#include<cstdio>
using namespace std;
#define ri register int
#define F(i,l,r) for(ri i=l;i<=r;++i)
#define min(x,y) x<y?x:y
const int N=1e5+5;
int sum,c,n,a[N],f[(1<<18)+100];
char s[22];
int main(){
freopen("b.in","r",stdin); freopen("b.out","w",stdout);
scanf("%d%d",&c,&n);
F(i,0,(1<<c)-1) f[i]=99999999;
F(i,1,n){
scanf("%s",s+1);
sum=0;
F(j,1,c) sum=(sum<<1)+(s[j]=='G');
f[sum]=0;
a[i]=sum;
}
F(i,1,c) F(j,0,(1<<c)-1) f[j^(1<<i-1)]=min(f[j^(1<<i-1)],f[j]+1);
F(i,1,n) printf("%d\n",c-f[(1<<c)-1-a[i]]);
return 0;
}
T3 Pareidolia
给定一个仅包含小写字母的字符串 \(s\) ， 长度不超过 \(3 \times 10^5\)。
定义函数 \(B(s)\) 表示把 \(s\) 中的若干个字母删去后，形成尽量多个bessie相连的形式(bessiebessiebessie...)，返回bessie的最大数量。
如 \(B(\text{"bqessiyexbesszieb"})=2\)。
求 \(s\) 的所有子串的 \(B\) 函数之和。
两个误区：
（1）一个字符最多只能存在于一个bessie中而非多个。还担心会不会一匹配多，把问题想复杂了
（2）审题不清：没发现任意字母都可以删去，还以为是KMP，写到最后再读题发现问题之后哭死，只剩不到1h，直接失去继续写下去的动力了。。。（想好再下笔！！！）
对我来说，光是如何简明地书写判断是否找到了一个新的bessie都有难度。。。
由于模式串是固定的而且只有六位，直接对于 b,e,s,i这几种字符记录我所在的bessie串的开头b所在的位置即可。开头记录下来，串的位置当然也就确定啦！而且后面统计答案还要用到
考虑新发现一个bessie串对答案的贡献。记 \(f_i\) 为以i结尾的所有子串的B函数之和，\(pos\) 为新发现的bessie串的开头位置。则有
emm...可以感性理解为：继承没发现这个串之前的答案 + 起点为1-pos，终点固定成i的所有串都会多看到当前这个新串。
最终答案 \(sum=\sum_{i=1}^{n} f_i\)
注意有些字符的更新是有顺序的，不要写挂了。
#include<cstdio>
const int N=3e5+5;
char s[N];
int p[10];
long long f[N],sum=0;
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%s",s+1);
for(int i=1;s[i];++i){
// F(i,1,6) printf("%d ",p[i]); puts("");
if(s[i]=='b') p[1]=i;
else if(s[i]=='e') p[2]=p[1],p[6]=p[5];
else if(s[i]=='s') p[4]=p[3],p[3]=p[2];//不能写反，否则一个's'会同时更新p[4],p[3]
else if(s[i]=='i') p[5]=p[4];
if(p[6]) f[i]=f[p[6]-1]+p[6];
//f[i]:以i结尾的所有子串的B函数之和
//p[6]:以i结尾的能含有当前这个新增bessie的子串的数量
//p[6]位置以前的所有串还能多包含一个bessie（即当前新增的这个）,所以要+f[p[6]-1]
sum+=f[i];
} printf("%lld",sum);
return 0;
}
存疑：为什么下面这种写法是错的？？？
#include<bits/stdc++.h>
using namespace std;
char c[300005];
unsigned long long p[10];
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%s",c+1);
unsigned long long lenc=strlen(c+1);
unsigned long long ans=0;
unsigned long long sum=0;
for(unsigned long long i=1;i<=lenc;i++){
if(c[i]=='b') p[1]=i;
if(c[i]=='e'){
p[2]=p[1];
if(p[5]!=p[6]) sum+=p[5];
p[6]=p[5];
}
if(c[i]=='s') p[4]=p[3],p[3]=p[2];
if(c[i]=='i') p[5]=p[4];
ans+=sum;
}
printf("%llu",ans);
return 0;
}
模拟赛总结：
1.感觉T1写了近两个小时有点慢了，如果把找 \(a_x\) 原位置直接也写成lower_bound可能会节省很多时间（毕竟每写一个二分查总是要调很久...）
2.T2部分分拿的还是很稳的，但对于C较小这个性质的运用还是差了些：只想到了用bitset优化异或过程。还有，积累逆向思维的经验：原问题不好想，那就承认它不好想，就大胆考虑倒过来想
（由于正着做不好想，所以我们考虑倒过来想）
3.T3首先审题不清（想好再下笔），第二想复杂了，被吓到了（还是要多手玩几个样例去自己体会题目的要求，不要偷懒 ~ ~ ~）
写在最后：距离NOIP2023仅剩16天，耳边又想起了中考前我的语文老师告诉我的那句话，
“行百里者半九十。”
希望不留遗憾~加油NOIP2023!