当前位置：网站首页>8/7 牛客6+div2D+倍增lca
8/7 牛客6+div2D+倍增lca
2022-08-08 11:06:00 【钟钟终】
J Number Game
此题分析的差不多了，但是思路想到扩欧那里去了，越想越着急，便做不出了
思路：a的值不会改变，b的值会出现b和a-b两种
c 的值： 初始 c
第一轮： b-c 和 a-b-c
第二轮: a-2b+c 和 -a+2b+c
第三轮： -a+3b-c 和 2a-3b-c
第四轮: 2a-4b+c 和 -2a+4b+c
根据b和c的正负号可进行归类，奇数轮为一组，偶数轮为一组，得出四个公式：
b-c+k(2b-a)a-b-c+k(a-2b)a-2b+c+k(a-2b)-a+2b+c+k(2b-a)
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
const int N =2e5+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int a,b,c,x;
signed main()
{
int t;cin>>t;
while(t--)
{
cin>>a>>b>>c>>x;
int x1=b-c,x2=a-b-c,x3=a-2*b+c,x4=-a+2*b+c;
if(b==a-b)
{
if(c==x||b-c==x) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else if((x-x1)%(2*b-a)==0||(x-x2)%(a-2*b)==0||(x-x3)%(a-2*b)==0||(x-x4)%(2*b-a)==0)
{
cout<<"Yes"<<endl;
}
else
cout<<"No"<<endl;
}
return 0;
}
M. Z-Game on grid
题意很清楚，不过我还是没想到可以用dp去做，思路：
1.三种状态，f[i][j][0]表示从i行j列出发可否到达A ；f[i][j][1]表示从i行j列出发可否到达B ；f[i][j][2]表示从i行j列出发可否平局；
2.预处理:若该格子为A，则f[i][j][0]=1；若该格子为B，则f[i][j][1]=1；若n行m列没有其他字母，则f[i][j][2]=1（这个题目没说清楚）。
3.为保证无后效性，逆推状态。对于A来说，右边和下边若一旦出现了1，就肯定向A的方向走，则该格子必定为1；对于B来说，右边和下边若一旦出现了1，就肯定向不是A的方向走，只有当该格子右边和下变都为B时，该格子才为1
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
const int N =2e5+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m;
char mp[505][505];
bool f[505][505][3];
signed main()
{
int t;cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
f[i][j][0]=f[i][j][1]=f[i][j][2]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='A') f[i][j][0]=1;
else if(mp[i][j]=='B')
f[i][j][1]=1;
}
if(mp[n][m]=='.')f[n][m][2]=1;
for(int i=n;i>=1;i--)
{
for(int j=m;j>=1;j--)
{
if(i==n&&j==m) continue;
if(i==n)
{
f[i+1][j][0]=f[i][j+1][0];
f[i+1][j][1]=f[i][j+1][1];
f[i+1][j][2]=f[i][j+1][2];
}
if(j==m)
{
f[i][j+1][0]=f[i+1][j][0];
f[i][j+1][1]=f[i+1][j][1];
f[i][j+1][2]=f[i+1][j][2];
}
if((i+j)&1) //Bob走
{
if(mp[i][j]=='.'){
f[i][j][0]=max(f[i][j][0],f[i][j+1][0]&&f[i+1][j][0]); //Bob能否走到A
f[i][j][1]=max(f[i][j][1],f[i][j+1][1]&&f[i+1][j][1]); //Bob能否走到B
f[i][j][2]=max(f[i][j][2],f[i][j+1][2]&&f[i+1][j][2]);
}
}
else
{
if(mp[i][j]=='.'){
f[i][j][0]=max(f[i][j][0],f[i][j+1][0]||f[i+1][j][0]);
f[i][j][1]=max(f[i][j][1],f[i][j+1][1]||f[i+1][j][1]);
f[i][j][2]=max(f[i][j][2],f[i][j+1][2]||f[i+1][j][2]);
}
}
}
}
if(f[1][1][0]) cout<<"yes ";
else cout<<"no ";
if(f[1][1][2]) cout<<"yes ";
else cout<<"no ";
if(f[1][1][1]) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
倍增lca
模板：
int dep[N]; //存u点的深度
int fa[N][20]; //存从u点向上跳2^i层的祖先节点
vector<int>e[N];
void dfs(int u,int pare)
{
dep[u]=de[pare]+1;
fa[u][0]=pare;
for(int i=1;i<=19;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:e[u])
if(v!=pare) dfs(v,u);
}
//利用st表求lca
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
//先跳到同一层
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
if(u==v) return v;
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
Eezie and Pie
倍增lca+树上差分
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
const int N =2e6+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,d[N],num[N],ans[N];
int dep[N]; //存u点的深度
int fa[N][20]; //存从u点向上跳2^i层的祖先节点
vector<int>e[N];
void dfs(int u,int pare)
{
dep[u]=dep[pare]+1;
fa[u][0]=pare;
for(int i=1;i<=19;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:e[u])
if(v!=pare) dfs(v,u);
}
void dfs2(int u,int pare)
{
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v!=pare)
{
dfs2(v,u);
num[u]+=num[v];
ans[u]+=ans[v];
}
}
ans[u]++;
}
//利用st表求lca
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
//先跳到同一层
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
if(u==v) return v;
//跳到lca的下一层
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
signed main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
cin>>d[i];
num[i]=ans[i]=0;
}
dfs(1,0);
for(int i=1;i<=n;i++)
{
int g=min(d[i],dep[i]-1); //可经过的路径长度
g=dep[i]-g; //向上最大可跳到到的层数
int u=i;
for(int j=19;j>=0;j--) //跳到第g层
if(dep[fa[u][j]]>=g)
u=fa[u][j];
num[fa[u][0]]--; //标记该子树中不能到达的节点数
}
dfs2(1,0);
for(int i=1;i<=n;i++)
cout<<ans[i]+num[i]<<" ";
cout<<endl;
return 0;
}
P3128 [USACO15DEC]Max Flow P
不明白这模板哪错了，看了2个消失了，快烦死了 哭……
啊啊，我真的蠢，卧槽，我没有调用深搜函数。。。。
思路：就是将每次询问u，v的路径上经过的点+1，通过倍增实现。
方式：++cnt[u],++cnt[v],--cnt[g],--cnt[fa[g][0]];
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
const int N =2e6+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,cnt[N],ans;
int dep[N]; //存u点的深度
int fa[N][20]; //存从u点向上跳2^i层的祖先节点
vector<int>e[N];
void dfs(int u,int pare)
{
dep[u]=dep[pare]+1;
fa[u][0]=pare;
for(int i=1;i<=19;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:e[u])
if(v!=pare) dfs(v,u);
}
//利用st表求lca
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
//先跳到同一层
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
if(u==v) return v;
//跳到lca的下一层
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int dfs2(int u,int pare)
{
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v!=pare)
{
dfs2(v,u);
cnt[u]+=cnt[v];
}
}
ans=max(ans,cnt[u]);
}
signed main()
{
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
cout<<lca(2,3)<<endl;
dfs(1,0)
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;
int g=lca(u,v);
//cout<<lca<<endl;
++cnt[u],++cnt[v],--cnt[g],--cnt[fa[g][0]];
}
dfs2(1,0);
cout<<ans<<endl;
return 0;
}
边栏推荐
- 一文读懂配置管理（CM）
- 基于ftp协议的上传与下载
- LeetCode_487_最大连续1的个数Ⅱ
- day01 - Introduction to Web API - Introduction to DOM - Getting Elements - Event Basics - Manipulating Elements - Exclusive Operations - Custom Attribute Operations - Node Operations - Cases: Dynamica
- 为什么说键值数据库有高可扩展性呢？
- Oracle ASM disk group replaces old storage scheme with new storage
- 键值数据库是将什么作为标识符的呢？
- Apple developer account application process full version
- 典型的图数据库有哪些呀？
- 网盘目录搜索系统源码+搭建教程
猜你喜欢
day02 -DOM—高级事件（注册事件、事件监听、删除事件、DOM事件流、事件对象、阻止默认行为、阻止事件冒泡、事件委托）—常用鼠标事件—常用的键盘事件
部署spark2.2集群(standalone模式)
微服务负载均衡器LoadBalancer实战
卫星互联网真能替代 5G？
【地平线旭日X3派试用体验】WIFI连接，SSH登录，TogetherROS安装（第二节）
ReentrantLock原理,ReentrantLock和synchronized区别
轻量级接口自动化框架（jmeter+ant+jenkins）
探究！一个数据包在网络中的心路历程
Jingdong, zhang, director of the cloud wireless products division treasure jingdong cloud wireless treasure close relationship with the open source | the great god, open source BUFF gain strategy revi
基于ftp协议的上传与下载
随机推荐
微服务负载均衡器LoadBalancer实战
JVM的GC讲解及调优
openssl 创建证书
详细讲解修改allure报告自定义的logo和名称中文
Mysql索引优化实战
Pattern Recognition Study Notes: Chapter 6 Other Classification Methods (Continuously updated...)
【力扣】两数相加
Optional common method analysis
ReentrantReadWriteLock读写锁和票据锁StempedLock
文档数据库中的文档有什么用呢？
Supervisor 后台进程管理
关于那些我们都听过的营销工具—优惠券
Hystrix熔断器
d切片示例
ReentrantLock源码分析和使用案例
上海控安SmartRocket系列产品推介（二）：SmartRocket Modeler可视化建模开发工具
列存储数据库是什么呢？
About the Celery service report under win Process 'Worker' exited with 'exitcode 1' [duplicate]
JSON Schema模式用法
【Force】Add two numbers