当前位置：网站首页>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基本工具介绍之选择线条工具（包教会）
- An工具介绍之摄像头
- 业界新标杆！阿里开源自研高并发编程核心笔记（2022最新版）
- Station B responded that "HR said that core users are all Loser": the interviewer was persuaded to quit at the end of last year and will learn lessons to strengthen management
- leetcode 11. 盛最多水的容器
- 什么是分布式锁？几种分布式锁分别是怎么实现的？
- An动画基础之元件的图形动画与按钮动画
- How to build an overseas purchasing system/purchasing website - source code analysis
- 技术分享 | 接口自动化测试如何搞定 json 响应断言？
猜你喜欢
信创建设看广州｜海泰方圆亮相2022 信创生态融合发展论坛
如何免费获得一个市全年的气象数据？降雨量气温湿度太阳辐射等等数据
Win11怎么禁止软件后台运行？Win11系统禁止应用在后台运行的方法
An工具介绍之形状工具及渐变变形工具
无监督学习KMeans学习笔记和实例
海外代购系统/代购网站怎么搭建——源码解析
一次内存泄露排查小结
How does Filebeat maintain file state?
setTimeout, setInterval requestAnimationFrame
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动画优化之传统引导层动画
ECCV 2022 | AirDet: 无需微调的小样本目标检测方法
【Verilog】HDLBits题解——Verification: Reading Simulations
899. 有序队列
R语言ggplot2可视化：使用patchwork包的plot_layout函数将多个可视化图像组合起来，ncol参数指定行的个数、byrow参数指定按照行顺序排布图
15. PARTITIONS「建议收藏」
R语言ggplot2可视化：使用ggpubr包的ggline函数可视化折线图、设置add参数为mean_se和dotplot可视化不同水平均值的折线图并为折线图添加误差线（se标准误差）和点阵图
Five, the function calls
【Verilog】HDLBits题解——Verification: Writing Testbenches
IronOS, an open source system for portable soldering irons, supports a variety of portable DC, QC, PD powered soldering irons, and supports all standard functions of smart soldering irons
[Verilog] HDLBits Problem Solution - Circuits/Sequential Logic/Latches and Flip-Flops
setTimeout, setInterval requestAnimationFrame
Mysql重启后innodb和myisam插入的主键id变化总结
pandas连接oracle数据库并拉取表中数据到dataframe中、筛选当前时间（sysdate）到一天之前的所有数据（筛选一天范围数据）
YOLOv5 training data prompts No labels found, with_suffix is used, WARNING: Ignoring corrupted image and/or label appears during yolov5 training
self-discipline
【Verilog】HDLBits题解——Circuits/Sequential Logic/Latches and Flip-Flops
An动画基础之元件的影片剪辑效果
新评论接口——京东评论接口
SQL分页查询_Sql根据某个字段分页