多校A层冲刺NOIP2024模拟赛03
还有一个半小时结束才来，题基本没打，全口胡。
T1 五彩斑斓（colorful）
直接统计答案难做，考虑统计四个顶点都一样的。
知道\(n\)行\(m\)列的矩阵有\(\frac{n\times (n+1)\times m\times (m+1)}{4}\)个子矩阵，这个想成选择矩阵的边界就可以证明。
如何统计四个顶点都一样的?
考虑枚举矩阵的上下边界，分别记为\(i,j\)，然后扫描每一列，记当前扫描到\(k\)。
如果\(c_{i,k}\ne c_{j,k}\)，那么这一列不会作为右边界，舍弃。
如果\(c_{i,k}=c_{j,k}\)，那么这一列可以成为右边界或左边界，计数器\(ct_{c_{i,k}}++\),然后\(ans+=ct_{c_{i,k}}\)
清空的时候再扫描一遍列就行了。
时间复杂度\(O(n^2m)\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = infile("colorful.in"),*OutFile = outfile("colorful.out");
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 410,V = 1e6 + 10;
int n,m,a[N][N],ct[V];
inline void solve(){
cin>>n>>m;
rep(i,1,n,1)rep(j,1,m,1)cin>>a[i][j];
ll ans = 0;
rep(i,1,n,1)rep(j,i,n,1){
rep(k,1,m,1) if(a[i][k] == a[j][k]){++ct[a[i][k]];ans += ct[a[i][k]];}
rep(k,1,m,1) if(a[i][k] == a[j][k]) ct[a[i][k]] = 0;
}
cout<<1ll*n*(n+1)*m*(m+1)/4-ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T2 错峰旅行（travel）
答案就是每秒钟时不拥挤的城市个数的乘积，离散化处理一下即可。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = infile("travel.in"),*OutFile = outfile("travel.out");
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e3 + 10,M = 2e6 + 10,mod = 1e9 + 7;
int s,t,n,m,p[M],ct[N];
struct node{int x,p,d;}a[M];int tot;
inline int power(int a,int b,int mod){
int res = 1;
for(;b;a = 1ll*a*a%mod,b>>=1) if(b&1) res = 1ll*res*a%mod;
return res;
}
inline void solve(){
cin>>n>>m>>s>>t;
p[++p[0]] = s;p[++p[0]] = t+1;
rep(i,1,m,1){
int x,l,r;cin>>x>>l>>r;r++;
p[++p[0]] = l;p[++p[0]] = r;
a[++tot] = {x,l,1};a[++tot] = {x,r,-1};
}
m <<= 1;
sort(a+1,a+1+m,[](node x,node y){return (x.p == y.p?x.d<y.d:x.p<y.p);});
sort(p+1,p+1+p[0]);p[0] = unique(p+1,p+1+p[0]) - p - 1;
//cerr<<power(2,100,mod)<<'\n';
//exit(0);
ll lsum = 1,nsum = 0,lnum = n,nnum = 0;
for(int i = 1,j = 0;i < p[0]; ++i){
nsum = 0,nnum = lnum;
//cerr<<i<<": ";
while(j < m && a[j + 1].p <= p[i]){
j++;
int x = a[j].x,d = a[j].d;
if(ct[x] > 0 && ct[x] + d <= 0) ++nnum;
else if(ct[x] <= 0 && ct[x] + d > 0) --nnum;
ct[x] += d;
//cerr<<j<<' ';
}
//cerr<<'\n';
nsum = lsum*power(nnum,p[i+1]-p[i],mod)%mod;
lsum = nsum,lnum = nnum;
}
cout<<nsum<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T3 线段树（segment）
区间dp
记\(w_i\)表示包含\(i+0.5\)的区间个数，\(sum_{i,j}\)表示包含\([l,r]\)的区间个数。
\(w\)差分+前缀和解决，考虑如何求\(sum\)
先初始化\(sum_{l,r}\)为恰好为\([l,r]\)的个数，然后有\(sum_{l,r} = sum_{l,r}+sum_{l-1,r}+sum_{l,r+1}-sum_{l-1,r+1}\)
dp方程为\(f_{l,r} = \min\limits_{l\le k<r}f_{l,k}+f_{k+1,r}+w_k-sum_{l,r}\)
答案为\(f_{1,n}+q\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
const int N = 510;
ll f[N][N],n,q,sum[N][N],w[N];
signed main(){
infile("segment.in");outfile("segment.out");
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>q;
for(int i = 1,l,r;i <= q; ++i){
cin>>l>>r;sum[l][r]++;
w[l]++,w[r]--;
}
for(int i = 1;i <= n; ++i) w[i] += w[i-1];
for(int len = n - 1;len >= 1; --len){
for(int l = 1;l + len - 1 <= n; ++l){
int r = l + len - 1;
sum[l][r] = sum[l][r] + sum[l-1][r] + sum[l][r+1] - sum[l-1][r+1];
}
}
for(int len = 2;len <= n; ++len){
for(int l = 1;l + len - 1 <= n; ++l){
int r = l + len - 1;
f[l][r] = LLONG_MAX;
for(int k = l;k < r; ++k){
f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+w[k]-sum[l][r]);
}
}
}
cout<<f[1][n]+q<<'\n';
}
T4 量子隧穿问题（experiment）
计数转概率的trick，就是合法方案 = 合法概率\(\times\)总方案数。
暴力的5pts直接搜索。
发现有\(n\)个顶点\(n\)条边，考虑基环树。
记\(f_{i,j}\)表示狗跑到第\(i\)个盒子\(j\)时有猫的概率。
先考虑一棵树怎么做。对于一条\(u\rightarrow v\)的边，有\(\begin{cases} f_{u,u} &= f_{u-1,u}\times f_{u-1,v}\\ f_{u,v} &= f_{u-1,v}+f_{u-1,u}\times (1-f_{u-1,v}) \end{cases}\)
初始化\(f_{0,i} = [s_i=C]+\frac{[s_i=?]}{2}\)
将基环树环上起点编号最小的一条边删去，然后钦定起点和终点有/无猫，就可以当成一棵树来做。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int mod = 1e9 + 7,N = 5010,inv2 = 500000004;
struct DSU{
vector<int> fa;
DSU(int n) :fa(n+1){iota(fa.begin(),fa.end(),0);}
inline int find(int x){while(x != fa[x])x = fa[x] = fa[fa[x]];return x;}
inline bool insame(int x,int y){return find(x) == find(y);}
inline bool Merge(int x,int y){
x = find(x),y = find(y);
if(x == y) return false;else return fa[y] = x,true;
}
};
int n,to[N],p[N];
char s[N];
inline void solve(){
cin>>n>>(s+1);rep(i,1,n,1) cin>>to[i];
DSU f1(n),f2(n); rep(i,1,n,1) f1.Merge(i,to[i]);
int res;
drep(i,n,1,1) if(f1.insame(i,n) && !f2.Merge(i,to[i])) res = i;
int ans = 0;
for(int l:{0,1})for(int r:{0,1}){
rep(i,1,n,1) p[i] = 0;
rep(i,1,n,1){
if(s[i] == 'C') p[i] = 1;
if(s[i] == '?') p[i] = inv2;
}
int q;
rep(i,1,n,1){
if(i == res){
q = 1ll*(l?p[i]:1-p[i]+mod)*(r?p[to[i]]:1-p[to[i]]+mod)%mod;
p[i] = l,p[to[i]] = r;
}
int x = p[i],y = p[to[i]];
p[i] = 1ll*x*y%mod;p[to[i]] = (0ll+x+1ll*y*(1-x+mod)%mod)%mod;
}
ans = (ans + 1ll*q*p[n]%mod)%mod;
}
int tim = 0;rep(i,1,n,1) tim += (s[i] == '?');
while(tim--)ans = ans*2%mod;
cout<<ans<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
int T;cin>>T;
while(T--)solve();
}