当前位置：网站首页>8/2 训练日志(dp+思维+字典树)
8/2 训练日志(dp+思维+字典树)
2022-08-03 12:42:00 【钟钟终】
活动地址：CSDN21天学习挑战赛
E. Pashmak and Graph
题意：给定一张带权值的有向图，n个顶点m条边，找出一条长度最大权值递增的路径，输出长度。
思路：
1.若是以每个点都进行一次遍历，必定会超时；g[i]表示在到达i点时满足题意得长度最大是多少
2.还需将权值进行升序排列，前面权值小的肯定先经过
3.再开一数组，dp[i]表示第i条边结尾的最大长度
4.状态转移方程：dp[i]=g[e[i].u]+1
#include<bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,m,g[N],dp[N];
struct node
{
int u,v,w;
bool operator <(const node & e)const
{
return w<e.w;
}
}e[N];
int main()
{
IOS;
//g[i]表示在到达i点时满足题意得长度最大是多少
//dp[i]表示第i条边结尾的最大长度
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;cin>>u>>v>>w;
e[i]=(node){
u,v,w};
}
sort(e+1,e+m+1);
int ans=0,k=1;
e[m+1].w=-1;
for(int i=1;i<=m;i++)
{
dp[i]=g[e[i].u]+1;
if(e[i].w!=e[i+1].w) //权值相等的连续段
{
for(int j=k;j<=i;j++)
g[e[j].v]=max(dp[j],g[e[j].v]);
k=i+1;
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
return 0;
}
C. awoo’s Favorite Problem
题意：将一个串通过两个变换规则变成连一个串
思路：
1.将b全部删除，看看字符串s和t是否相等
2.比较s中a和c的下标是否分别大于、小于t中a和c下标
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n;
vector<int>v1,v2;
string s,tt;
int main()
{
int t;scanf("%d",&t);
while(t--)
{
v1.clear();
v2.clear();
scanf("%d",&n);
cin>>s>>tt;
s=" "+s;
tt=" "+tt;
string s1,s2;
for(int i=1;i<=n;i++)
{
if(s[i]!='b') s1+=s[i],v1.push_back(i);
if(tt[i]!='b') s2+=tt[i],v2.push_back(i);
}
int flag=1;
if(s1!=s2)
{
cout<<"NO"<<endl;
continue;
}
for(int i=0;i<v1.size();i++)
{
//cout<<v1[i]<<" "<<v2[i]<<endl;
if(s1[i]=='a'&&v1[i]>v2[i])
{
flag=0;break;
}
if(s1[i]=='c'&&v1[i]<v2[i])
{
flag=0;break;
}
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
E. Add Modulo 10
刚开始看了tag里面有暴力，写了一个纯纯暴力的做法，真的脑淤血了。
int main()
{
//IOS;
int t;cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
while(a[n]%2)
{
a[n]+=a[n]%10;
}
int flag=1;
for(int i=n-1;i>=1;i--)
{
int tmp=a[i];
while(a[i]<a[n])
{
a[i]+=a[i]%10;
if(a[i]==tmp)
break;
}
if(a[i]!=a[n])
{
flag=0;break;
}
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
找规律发现：除了0和5结尾的数，其他数都会陷入2，4，8，6这样的怪圈。每个周期都会增加20。
列出公式：A[i] + k1 * 20 == A[j] + k2 * 20
化简得到：(A[i] - A[j]) % 20 == 0
将0和5结尾的数字，看能否统一为同一个数字。
#include<bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,a[N];
int main()
{
//IOS;
int t;cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int cnt=0,mx=-1;
for(int i=1;i<=n;i++)
{
if(a[i]%10==5) a[i]+=5,cnt++;
else if(a[i]%10==0) cnt++;
else
{
while(a[i]%10!=2)
a[i]+=a[i]%10;
mx=max(mx,a[i]);
}
}
int flag=1;
if(n==cnt)
{
for(int i=2;i<=n;i++)
if(a[i]!=a[i-1])
{
flag=0;break;
}
}
else if(cnt>0) flag=0;
else
{
for(int i=1;i<=n;i++)
{
if((mx-a[i])%20!=0)
{
flag=0;break;
}
}
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
字典树
char s[N];
int ch[N][26]; //存储从结点p沿着j这条边走到的子节点
int cnt[N]; //存储一节点p结尾的单词插入次数
int idx; //给结点编号
void ins(char *s)
{
int p=0;
for(int i=0;s[i];i++)
{
int j=s[i]-'a';
if(!ch[i][j]) ch[i][j]=++idx;
p=ch[p][j];
}
cnt[p]++;
}
int query(char *s)
{
int p=0;
for(int i=0;s[i];i++)
{
int j=s[i]-'a';
if(!ch[i][j]) return 0;
p=ch[i][j];
}
return cnt[p];
}
P2922 [USACO08DEC]Secret Message G
类型：属于01的字典树
思路：
1.数组cnt[i]表示以i结尾的字符串个数
2.数组sum[i]表示经过结点i的字符串个数
3.统计不同长度的前缀为res+sum[p]-cnt[p];
代码：
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
char s[N];
int ch[N][26]; //存储从结点p沿着j这条边走到的子节点
int cnt[N]; //存储一节点p结尾的单词插入次数
int idx; //给结点编号
int n,m,k,sum[N];
int ss[N];
void ins(int s[])
{
int p=0;
for(int i=0;i<k;i++)
{
int j=s[i];
if(ch[p][j]==-1) ch[p][j]=++idx;
p=ch[p][j];
sum[p]++;
}
cnt[p]++;
}
int query(int s[])
{
int p=0,res=0;
for(int i=0;i<k;i++)
{
int j=s[i];
if(ch[p][j]==-1) return res;
p=ch[p][j];
res+=cnt[p];
}
return res+sum[p]-cnt[p];
}
int main()
{
cin>>m>>n;
memset(ch,-1,sizeof ch);
for(int i=1;i<=m;i++)
{
cin>>k;
for(int j=0;j<k;j++)
cin>>ss[j];
ins(ss);
}
for(int i=1;i<=n;i++)
{
cin>>k;
for(int j=0;j<k;j++)
cin>>ss[j];
cout<<query(ss)<<endl;
}
return 0;
}
P2580 于是他错误的点名开始了
思路：本来想联系一下字典树得模板题，但这个题目只需要一个map容器就解决了。
若不存在改键，则map容器中Int类型得默认值为0
#include<bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,m;
map<string,int>mp;
int main()
{
//IOS;
cin>>n;
for(int i=1;i<=n;i++)
{
string s;cin>>s;
mp[s]=1;
}
cin>>m;
while(m--)
{
string s;cin>>s;
if(mp[s]==1)
cout<<"OK"<<endl,mp[s]+=1;
else if(mp[s]>1)
cout<<"REPEAT"<<endl;
else
cout<<"WRONG"<<endl;
}
return 0;
}
边栏推荐
- An动画基础之元件的影片剪辑动画与传统补间
- __unaligned修饰指针
- PolarFormer: Multi-camera 3D Object Detection with Polar Transformers 论文笔记
- 【必读要点】Pod控制器Deployment更新、回退详解
- Mysql重启后innodb和myisam插入的主键id变化总结
- 【精品必知】Pod生命周期
- Feature dimensionality reduction study notes (pca and lda) (1)
- An基本工具介绍之选择线条工具（包教会）
- 基于php校园医院门诊管理系统获取（php毕业设计）
- In order to counteract the drop in sales and explore the low-end market, Weilai's new brand products are priced as low as 100,000?
猜你喜欢
基于php网上零食商店管理系统获取（php毕业设计）
How to disable software from running in the background in Windows 11?How to prevent apps from running in the background in Windows 11
An工具介绍之形状工具及渐变变形工具
PolarFormer: Multi-camera 3D Object Detection with Polar Transformers 论文笔记
一次内存泄露排查小结
漫画：怎么证明sleep不释放锁，而wait释放锁？
Oracle is installed (system disk) and transferred from the system disk to the data disk
期货开户中常见问题汇总
层次分析法
An动画基础之元件的影片剪辑效果
随机推荐
Free Internet fax platform fax _ don't show number
随机森林项目实战---气温预测
Jmeter使用
数据库基础知识一（MySQL）[通俗易懂]
Feature Engineering Study Notes
Database basics one (MySQL) [easy to understand]
YOLOv5训练数据提示No labels found、with_suffix使用、yolov5训练时出现WARNING: Ignoring corrupted image and/or label
从零开始C语言精讲篇5：指针
图像融合DDcGAN学习笔记
Kubernetes 网络入门
Image fusion DDcGAN study notes
从器件物理级提升到电路级
云计算服务主要安全风险及应对措施初探
(through page) ali time to upload the jar
shell编程之条件语句
R语言ggplot2可视化：使用ggpubr包的ggline函数可视化折线图、设置add参数为mean_se和dotplot可视化不同水平均值的折线图并为折线图添加误差线（se标准误差）和点阵图
Apache APISIX 2.15 版本发布，为插件增加更多灵活性
Nodejs 安装依赖cpnm时，install 出现Error: Cannot find module ‘fs/promises‘
R语言绘制时间序列的自相关函数图：使用acf函数可视化时间序列数据的自相关系数图
一些测试相关知识