当前位置: 首页 > news >正文

2025国庆Day4

模拟赛

T1

简单做法:

发现本题所有运算全是加法

直接记录c,s之和

转移即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;	
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
const int MOD=998244353;
int dp[1005][1005][2];
int a[1005][1005],c[1005][1005][2],sum[1005][1005][2];
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);int n=read(),m=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char s;cin>>s;if(s=='.') a[i][j]=1;}}sum[1][1][0]=sum[1][1][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i-1][j]){jiaa(sum[i][j][0],(sum[i-1][j][0]+sum[i-1][j][1])%MOD);jiaa(c[i][j][0],(c[i-1][j][0]+sum[i-1][j][0]*(i*j)%MOD+sum[i-1][j][1]*(i*j)%MOD)%MOD);jiaa(dp[i][j][0],(dp[i-1][j][0]+c[i-1][j][0]+sum[i-1][j][0]*(i*j)%MOD+dp[i-1][j][1]+sum[i-1][j][1]*(i*j)%MOD)%MOD);}if(a[i][j-1]){jiaa(sum[i][j][1],(sum[i][j-1][0]+sum[i][j-1][1])%MOD);jiaa(c[i][j][1],(c[i][j-1][1]+sum[i][j-1][1]*(i*j)%MOD+sum[i][j-1][0]*(i*j)%MOD)%MOD);jiaa(dp[i][j][1],(dp[i][j-1][1]+c[i][j-1][1]+sum[i][j-1][1]*(i*j)%MOD+dp[i][j-1][0]+sum[i][j-1][0]*(i*j)%MOD)%MOD);}}}if(!a[n][m]){cout<<0<<'\n';return 0;}int ans=(dp[n][m][0]+dp[n][m][1])%MOD;ans=ans*ksm(2,MOD-2,MOD)%MOD;cout<<ans<<'\n';return 0;
}

高级做法:

按拐点dp

前缀和优化

实现较为麻烦

T2

可以建出虚树

直接跑dfs求树的重心即可

或者观察:

点集的重心⼀定是“dfs序中位数”的祖先

此处,若点集⼤⼩为奇数,“dfs序中位数”即为点集按 dfs 序排序后,最中间的点

若为偶数,排序后最中间的点有两个,重⼼⼀定是它们之⼀的祖先

通过倍增的⽅法找到重⼼

具体地,可以发现重心⼀定是“中位数”的所有祖先(包括“中位数”本⾝)中,满⾜“条件1”的、深度最深的⼀个

若点集大小为偶数,对中间两个点分别找一次重心

取dep较大的即可

带权做法类似

T3

将偶数的边连两次,奇数的边连一次

找欧拉路径即可

T4

数学!

容斥原理

image

image

图论

最小生成树

kruskal prim

brouvka:每次取每个点的最小出边,合并,直到只剩一个点

最短路

https://www.luogu.com.cn/problem/P4568

分层图

https://www.luogu.com.cn/problem/UVA1151

暴力用哪个套餐

每次套餐内的点合并,跑prim

复杂度O(n2*2q)小常数2e8能过

https://www.luogu.com.cn/problem/P1396

求最小瓶颈路

易证一定是最小生成树上的路径

若多测树上倍增即可

https://www.luogu.com.cn/problem/P3008

是不是可以SPFA

对所有的双向边联通块缩点

一定是dag

拓扑排序更新dis

欧拉路径

欧拉路径存在,当且仅当图是联通图,且度数为奇数的点的个数不超过 2

  1. 如果度数为奇数的点个数为 0,则欧拉路⼀定是欧拉回路:即起点和终点相同

  2. 如果度数为奇数的点个数为 2,则欧拉路径必定从它们中的⼀个出发,并在另⼀个终⽌

构造方案将起点终点连边,求欧拉回路即可

若没有欧拉回路,如何构建?

容易发现奇度数的点一定是偶数个

将这些奇度数的点两两连边即可

二分图

二分染色当且仅当不存在奇环

联通分量

image

并查集维护到fa的路径奇偶性

若su^sv==w%2就存在答案

注意若联通块内存在奇环,一定有答案

CF547D

对每个点,横纵坐标连边

形成的图强制补成有欧拉回路的图

跑欧拉回路即可

(欧拉回路定向题,从x->y染红,反之染蓝)

image

T3 加强版

对于所有奇度数的点连边

边权是原图的最短路

对新图进行最小匹配

http://www.hskmm.com/?act=detail&tid=24988

相关文章:

  • gis坐标计算
  • day17 课程()
  • NKOJ全TJ计划——NP11744
  • ROIR 2025
  • trick 小记
  • python编写AI生常用匡架及使用指令集
  • 123123
  • 1005模拟赛总结
  • 2025.10.5 2024CCPC郑州
  • 20250531MATLAB三维绘图 - 教程
  • 概率期望dp 复习笔记
  • 2025.10
  • PCIe扫盲——物理层逻辑部分基础(一)
  • 仅需3%训练数据的文本归一化技术
  • 价值原语博弈协议:价值原语共识锚定原则
  • 实用指南:工作流引擎-16-开源审批流项目之 整合Flowable官方的Rest包
  • 25fall做题记录-October - Amy
  • 嗯嗯
  • PCIe扫盲——AckNak 机制详解(二)
  • ASP.NET Core SignalR 身份认证集成指南(Identity + JWT) - 详解
  • utorrent 2.2.1
  • 2025热缩管厂家 TOP 企业品牌推荐排行榜,氟橡胶,双壁,线缆标识,防滑花纹,DR 耐油橡胶,PVDF,标识,航插用,军用热缩管公司推荐!
  • 市场交易反心理特征之八:劣仓驱逐良仓
  • 做题笔记18
  • 2025桩基检测机构最新企业咨询服务推荐排行榜,海上桩基检测,水上桩基检测服务推荐这十家公司!
  • 算法坑点
  • [省选联考 2025] 图排列 题解
  • Windows下安装并采用kubectl查看K8S日志
  • 实用指南:UV 包管理工具:替代 pip 的现代化解决方案
  • C/C++与Java、Python、Go在各个阶段的区别