MX-NOIP 2024 模拟 3.5
赠的场次，质量却很高。
#3.5
T1 交换
连状压都打的复杂度超劣，真是水平下降严重。
其实也基本想到了，前面一大部分贪心确定，后面的做部分分状压 dp。
设 \(f_s\) 表示填了 \(s\) 集合，最优的 \(n'\)，\(g_s\) 表示此时对应的 \(n\)。
枚举最高位填哪个数，转移比较简单。
往前换的最大代价只有 \(n \times k \le 10^{17}\) ，而如果换到的位置比 18，19 还要高，那么显然一定会换。
因此最多只有后 \(19\) 位是不确定的，前面一定是前 \(n-19\) 最大值。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=19;
typedef pair<int,int> PII;
PII q[N];
int ans[N];
char s[N];
int n,m,k;
int f[1<<M],g[1<<M];
int pw[M+5];
signed main()
{
freopen("swap.in","r",stdin);
freopen("swap.out","w",stdout);
cin>>(s)>>k;
n=strlen(s);
reverse(s,s+n);
for(int i=0;i<n;i++)
{
int x=s[i]-'0';
q[i]={x,i};
}
m=min(n,19ll);
sort(q,q+n);
for(int i=m;i<n;i++) ans[i]=q[i].first;
for(int i=0;i<m;i++) swap(q[i].first,q[i].second);
sort(q,q+m);
pw[0]=1;
for(int i=1;i<=m;i++) pw[i]=pw[i-1]*10;
memset(f,-0x3f,sizeof f);
f[0]=0;
for(int s=0;s<(1<<m);s++)
{
int p=__builtin_popcount(s);
for(int i=0;i<m;i++)
{
if((s>>i)&1) continue;
int t=s|(1<<i);
int v=__builtin_popcount((s>>i));
int nf=f[s]+q[i].second*pw[p]-v*k,ng=g[s]+q[i].second*pw[p];
if(f[t]<nf) f[t]=nf,g[t]=ng;
else if(f[t]<=nf) f[t]=nf,g[t]=ng;
}
}
int x=g[(1<<m)-1];
for(int i=0;i<m;i++) ans[i]=x%10,x/=10;
for(int i=n-1;i>=0;i--) cout<<ans[i];
cout<<"\n";
return 0;
}
T2 字符串
为啥我比赛的时候一点不会啊，该加训期望最值问题了。
一直想的是每个串独立？其实根本不是。
先考虑两个串，一位一位填，如果这一位两个串都一样那显然只能是某一个，然后第一个不一样的位置上，选啥都行，之后必须都和某个串的后缀相同。
总共只能错 \(1\) 次，因此是 \(p^{2\times m-1}\)
然后考虑能不能状压拿下 60pts。
看到这个和 LCP 有关系想到 Trie。
建出来虚树，这样结点数就正确了。
设 \(f_{u,s}\) 表示以 \(u\) 为根的子树，\(s\) 集合已经填上。
-
如果不是叶子：\(f_{u,s}= \max\{p\times f_{ls,s}+(1-p)\times f_{rs,s},(1-p) \times ? + p \times ?\}\)
-
如果是叶子：当前集合内已经有了这个元素，那就寄了，\(f_{u,s}=0\)，否则，向集合中加入这个东西，返回根结点进行计算 \(f_{1,s+\{u\}}\)
考虑这个状压在干什么：对于每个 Trie 的点，如果往左走，必须保证左儿子内部还有没访问到的，往右走同理。
因此对于每个节点，他是正确的必须要保证恰好向左儿子走了 \(k_1\) 次，右儿子走了 \(k_2\) 次。
设 \(g_{a,b}\) 表示向左走了 \(a\) 次，向右走了 \(b\) 次，最大胜率。
枚举最后一步使用更大胜率的是向左走还是向右走。
\(g_{a,b}= \max\{(1-p) \times g_{a-1,b} + p \times g_{a,b-1},p \times g_{a-1,b} + p \times g{a,b-1}\}\)。
所有节点对应的 \(g\) 乘起来就是答案。
状压 dp 代码（贺的）：
点击查看代码
#include <bits/stdc++.h>
#define double long double
using namespace std;
bool st;
const int N = 1010 * 1010;
int n, m;
double p;
int ch[N][2], cnt = 0, tot = 0, id[N];
int d[N];
int lt[40], rt[40];
int rk[N];
void insert(int x) {
string s;
cin >> s;
int p = 0;
for (int i = 0; i < m; i++) {
bool op = s[i] - '0';
if (!ch[p][op]) {
ch[p][op] = ++cnt;
d[cnt] = d[p] + 1;
}
p = ch[p][op];
}
id[p] = x;
}
int dfs(int x) {
if (rk[x])
return rk[x];
return dfs(ch[x][0] + ch[x][1]);
}
double dp[40][1 << 18];
int w[40];
bitset<(1 << 18)> book[40];
double Pow[1010];
int len[40];
double to(int x, int y) { return Pow[len[y] - len[x] - 1]; }
double dfs(int x, int s) {
if (x == 1 && s == (1 << n) - 1)
return 1;
if (!x)
return 0;
if (book[x][s])
return dp[x][s];
book[x][s] = 1;
double ans;
if (w[x]) {
if (s >> w[x] - 1 & 1)
ans = 0;
else
ans = dfs(1, s | (1 << w[x] - 1));
} else
ans = max(p * dfs(lt[x], s) * to(x, lt[x]) + (1 - p) * dfs(rt[x], s) * to(x, rt[x]),
p * dfs(rt[x], s) * to(x, rt[x]) + (1 - p) * dfs(lt[x], s) * to(x, lt[x]));
return dp[x][s] = ans;
}
bool ed;
signed main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> p;
Pow[0] = 1;
for (int i = 1; i <= m; i++) Pow[i] = Pow[i - 1] * max(p, 1 - p);
for (int i = 1; i <= n; i++) insert(i);
for (int i = 0; i <= cnt; i++)
if (i == 0 || id[i] || ch[i][0] && ch[i][1])
rk[i] = ++tot;
for (int i = 0; i <= cnt; i++) {
if (!rk[i])
continue;
w[rk[i]] = id[i];
len[rk[i]] = d[i];
if (ch[i][0])
lt[rk[i]] = dfs(ch[i][0]);
if (ch[i][1])
rt[rk[i]] = dfs(ch[i][1]);
}
cout << setprecision(20) << fixed << dfs(1, 0);
return 0;
}
正解代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=N*N;
double f[N][N];
int tr[M][2],sz[M],idx;
char str[N];
int n,m;
double p;
void insert(char s[])
{
int u=0;
for(int i=0;s[i];i++)
{
int c=s[i]-'0';
if(!tr[u][c]) tr[u][c]=++idx;
u=tr[u][c];
sz[u]++;
}
}
signed main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
cin>>n>>m>>p;
f[0][0]=1;
for(int j=1;j<=n;j++) f[0][j]=f[0][j-1]*max(p,1-p);
for(int i=1;i<=n;i++)
{
f[i][0]=max(p,1-p)*f[i-1][0];
for(int j=1;j<=n;j++)
{
double v1=f[i-1][j]*p+f[i][j-1]*(1-p);
double v2=f[i][j-1]*p+f[i-1][j]*(1-p);
f[i][j]=max(v1,v2);
}
}
for(int i=1;i<=n;i++)
{
cin>>str;
insert(str);
}
double res=1;
for(int u=0;u<=idx;u++)
{
// printf("%d %d %.3lf\n",sz[tr[u][0]],sz[tr[u][1]],f[sz[tr[u][0]]][sz[tr[u][1]]]);
res=res*f[sz[tr[u][0]]][sz[tr[u][1]]];
}
cout<<fixed<<setprecision(12)<<res<<"\n";
return 0;
}
T3 房间
场切啦！！简单集合容斥转哈希维护。
满足题目要求的点对一定满足：
- 删掉一个就联通了
- 删掉的一个和起点连通和终点不连通，另一个和起点不连通和终点连通，这两个点联通。
第一个去个重就行了。
然后考虑判断和起点终点联通就是暴力枚举相邻的连通块，然后看一下存不存在。
判断两个点联通第一种情况也是枚举相邻连通块判断有没有交集，第二种是他俩是相邻的两个，这个可以暴力判断。、
然后判断和一个东西集合有交，由于集合大小很小，可以把集合子集全部哈希，然后容斥即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rnd(time(0));
const int N=1e3+10,V=N*N;
typedef pair<int,int> PII;
int id[N][N],tot;
char g[N][N];
int p[V];
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
vector<int> vec;
PII pos[V];
bool inS[V],inT[V];
vector<int> ne[V];
int val[V];
unordered_map<int,int> Map;
bool chk(int x,int y)
{
if(x<1 || x>n || y<1 || y>m) return false;
if(g[x][y]=='#') return false;
return true;
}
int find(int x)
{
if(p[x]!=x) return p[x]=find(p[x]);
return p[x];
}
void merge(int x,int y)
{
int px=find(x),py=find(y);
if(px==py) return;
p[px]=py;
}
bool check(int x,int y)
{
return find(x)==find(y);
}
bool is_ne(int x,int y)
{
for(auto a:ne[x])
{
for(auto b:ne[y])
{
if(a==b) return true;
}
}
return false;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>(g[i]+1);
for(int j=1;j<=m;j++)
{
id[i][j]=++tot,p[tot]=tot,val[tot]=rnd();
pos[tot]={i,j};
if(g[i][j]=='#') vec.push_back(tot);
}
}
// for(auto x:vec) cout<<x<<"\n";
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!chk(i,j)) continue;
for(int d=0;d<4;d++)
{
int x=i+dx[d],y=j+dy[d];
if(!chk(x,y)) continue;
merge(id[i][j],id[x][y]);
}
}
}
if(check(id[1][1],id[n][m]))
{
int sz=vec.size();
cout<<sz*(sz-1)/2<<"\n";
return 0;
}
for(auto x:vec)
{
int i=pos[x].first,j=pos[x].second;
for(int d=0;d<4;d++)
{
int a=i+dx[d],b=j+dy[d];
if(!chk(a,b)) continue;
int y=find(id[a][b]);
ne[x].push_back(y);
if(y==find(id[1][1])) inS[x]=true;
if(y==find(id[n][m])) inT[x]=true;
}
sort(ne[x].begin(),ne[x].end());
ne[x].erase(unique(ne[x].begin(),ne[x].end()),ne[x].end());
}
for(auto x:vec)
{
if(inS[x]) continue;
if(!inT[x]) continue;
int sz=ne[x].size();
for(int s=1;s<(1<<sz);s++)
{
int w=0;
for(int j=0;j<sz;j++)
{
if((s>>j)&1) w^=val[ne[x][j]];
}
Map[w]++;
}
}
int res=0;
for(auto x:vec)
{
if(!inS[x]) continue;
if(inT[x]) continue;
int sz=ne[x].size();
int cnt=0;
for(int s=1;s<(1<<sz);s++)
{
int f=(__builtin_popcount(s)&1)?1:-1;
int w=0;
for(int j=0;j<sz;j++)
{
if((s>>j)&1) w^=val[ne[x][j]];
}
if(Map.count(w)) cnt+=f*Map[w];
}
int a=pos[x].first,b=pos[x].second;
// if(cnt) printf("[%d %d %d]\n",a,b,cnt);
for(int u=0;u<4;u++)
{
int c=a+dx[u],d=b+dy[u];
if(c<1 || c>n || d<1 || d>m) continue;
if(g[c][d]=='.') continue;
if(inS[id[c][d]]) continue;
if(!inT[id[c][d]]) continue;
if(is_ne(x,id[c][d])) continue;
cnt++;
}
res+=cnt;
// if(cnt) printf("[%d %d %d]\n",a,b,cnt);
}
// cout<<res<<"\n";
int sz=vec.size(),cnt=0;
for(auto x:vec)
{
if(!inS[x]) continue;
if(!inT[x]) continue;
cnt++;
res+=sz-1;
}
// cout<<cnt<<"\n";
res-=cnt*(cnt-1)/2;
cout<<res<<"\n";
return 0;
}
T4 电力公司
模拟赛见过很好的题目！！！
没有中途交点这个条件相当于匹配的左端点，右端点都是单调递增的。
然后就转化为在网格图上 dp，状态应该还得压一个二进制串表示当前行是否选了，列是否选了。
本质是分层图最长路。
可以获得 \(40\) 分的高分。
多组询问，考虑对一维分治。
每次处理 \([a,b]\) 跨过 \(mid\) 的询问，它必然在某个条竖线穿过 \(mid\)，枚举这个竖线，跑两个单源最长路，枚举询问合并答案即可。
注意这个枚举的中转点要特别注意，他的代价提前算，因为钦定他选了。
他的贡献只能在一边算。
点击查看代码
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define max(A,B) (A)>(B)?(A):(B)
using namespace std;
const int N=310,M=1e5+10,Inf=1e9;
int f[N][N][3],g[N][N][3];
int ans[N][N][3];
int w[N][N];
int Ans[M];
int u[N],v[N];
struct Node
{
int a,b,c,d,id;
};
int n,m;
inline void clear(int l1,int r1,int l2,int r2,int tp)
{
for(int i=l1;i<=r1;i++) for(int j=l2;j<=r2;j++) ans[i][j][tp]=f[i][j][0]=f[i][j][1]=f[i][j][2]=-Inf;
}
inline void Dp1(int l1,int r1,int l2,int r2,int tp)
{
int res=0;
f[l1][l2][0]=0,f[l1][l2][2]=0;
int tmp=w[l1][l2];
w[l1][l2]=0;
for(int i=l1;i<=r1;i++)
{
for(int j=l2;j<=r2;j++)
{
int maxv=-Inf;
ans[i][j][tp]=max(max(f[i][j][0],f[i][j][1]),f[i][j][2]);
if(i+1<=r1)
{
f[i+1][j][0]=max(max(f[i][j][0],f[i][j][1]),f[i][j][2]);
f[i+1][j][2]=f[i][j][2];
}
if(j+1<=r2)
{
f[i][j+1][0]=max(max(f[i][j][0],f[i][j][1]),f[i][j][2]);
f[i][j+1][1]=f[i][j][1];
}
for(int s=0;s<3;s++)
{
int t=3^s,c=((t>>0)&1)*u[i]+((t>>1)&1)*v[j],val=f[i][j][s]-c+w[i][j];
maxv=max(maxv,val);
}
if(i+1<=r1) f[i+1][j][2]=max(f[i+1][j][2],maxv);
if(j+1<=r2) f[i][j+1][1]=max(f[i][j+1][1],maxv);
ans[i][j][tp]=max(ans[i][j][tp],maxv);
}
}
w[l1][l2]=tmp;
}
inline void Dp2(int l1,int r1,int l2,int r2,int tp)
{
f[r1][r2][0]=0,f[r1][r2][2]=0;
for(int i=r1;i>=l1;i--)
{
for(int j=r2;j>=l2;j--)
{
int maxv=-Inf;
ans[i][j][tp]=max(max(f[i][j][0],f[i][j][1]),f[i][j][2]);
if(i-1>=l1)
{
f[i-1][j][0]=max(max(f[i][j][0],f[i][j][1]),f[i][j][2]);
f[i-1][j][2]=f[i][j][2];
}
if(j-1>=l2)
{
f[i][j-1][0]=max(max(f[i][j][0],f[i][j][1]),f[i][j][2]);
f[i][j-1][1]=f[i][j][1];
}
for(int s=0;s<3;s++)
{
int t=3^s,c=((t>>0)&1)*u[i]+((t>>1)&1)*v[j],val=f[i][j][s]-c+w[i][j];
maxv=max(maxv,val);
}
if(i-1>=l1) f[i-1][j][2]=max(f[i-1][j][2],maxv);
if(j-1>=l2) f[i][j-1][1]=max(f[i][j-1][1],maxv);
ans[i][j][tp]=max(ans[i][j][tp],maxv);
}
}
}
inline void solve(int l,int r,vector<Node> &Q)
{
if(l>r || Q.size()<=0) return;
vector<Node> L,R,now;
int mid=l+r>>1;
for(auto &it:Q)
{
if(it.b<mid) L.push_back(it);
else if(it.a>mid) R.push_back(it);
else now.push_back(it);
}
if(now.size())
{
for(int j=1;j<=n;j++)
{
Dp2(l,mid,1,j,2);
Dp1(mid,r,j,n,1);
for(auto &it:now)
{
int a=it.a,b=it.b,c=it.c,d=it.d,id=it.id;
if(c<=j && d>=j)
Ans[id]=max(Ans[id],ans[a][c][2]+ans[b][d][1]-v[j]);
}
clear(l,mid,1,j,2);
clear(mid,r,j,n,1);
}
}
if(L.size()) solve(l,mid-1,L);
if(R.size()) solve(mid+1,r,R);
}
signed main()
{
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>u[i];
for(int i=1;i<=n;i++) cin>>v[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>w[i][j];
vector<Node> vec;
for(int i=1,a,b,c,d;i<=m;i++)
{
cin>>a>>b>>c>>d;
vec.push_back({a,b,c,d,i});
}
clear(1,n,1,n,1),clear(1,n,1,n,2);
solve(1,n,vec);
for(int i=1;i<=m;i++) cout<<Ans[i]<<"\n";
return 0;
}