当前位置:网站首页>2019南昌网络赛 C题,Hello 2019
2019南昌网络赛 C题,Hello 2019
2022-08-09 07:01:00 【swust_fang】
题意:求包含9012,但是不包含8012的最小删除次数
解题思路:首先将字符串反转,按照题解思路为线段树维护矩阵即可
我们将线段树的每个区间用矩阵表示,矩阵mat[5][5]维护2019这个序列的情况~
首先明确矩阵mat表示的意义:我们需要构成一个长度为4的序列
mat[0][1]表示"2"所需要的最小花费值
mat[0][2]表示"20"所需要的最小花费值
mat[0][3]表示"201"所需要的最小花费值
mat[0][4]表示"2019"并且没有"2018"所需要的最小花费值
遇到一个'2',那么我们用到这个'2',mat[0][1]=0,如果不用mat[0][1]=1
遇到一个'0',那么我们用到这个'0',mat[1][2]=0,如果不用mat[1][1]=1
遇到一个'1',那么我们用到这个'1',mat[2][3]=0,如果不用mat[2][2]=1
遇到一个'9',那么我们用到这个'9',mat[3][4]=0,如果不用mat[3][3]=1
2019我们的数字我们都可以选择转移或者不转移,但是遇到8无论是3还是4的情况都要花费1来删除他~
遇到一个'8',那么我们不用到这个'8',mat[3][3]=1,mat[4][4]=1
从i->j的情况明显可以通过i->k,k->j来转移来找到最优
dp转移方程:ans.mat[i][j]=min(ans.mat[i][j],a.mat[i][k]+b.mat[k][j]);
合并的话直接用线段树区间合并就可以了
这题着实好难,比赛后发现,200多队暴打tourist~(wu
//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#include<bitset>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-6;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int maxn=2e5+5;
int n,q;
string s;
struct matrix
{
int mat[5][5];
matrix() {memset(mat,0,sizeof(mat));}
}tree[maxn<<2];
matrix mul(matrix a,matrix b)
{
matrix ans;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
{
ans.mat[i][j]=inff;
for(int k=0;k<5;k++)
ans.mat[i][j]=min(ans.mat[i][j],a.mat[i][k]+b.mat[k][j]);
}
return ans;
}
void build(int tr,int l,int r)
{
if(l==r)
{
for(int i=0;i<=4;i++)
for(int j=0;j<=4;j++)
if(i==j) tree[tr].mat[i][j]=0;
else tree[tr].mat[i][j]=inff;
switch(s[l])
{
case '2':tree[tr].mat[0][1]=0,tree[tr].mat[0][0]=1;break;
case '0':tree[tr].mat[1][2]=0,tree[tr].mat[1][1]=1;break;
case '1':tree[tr].mat[2][3]=0,tree[tr].mat[2][2]=1;break;
case '9':tree[tr].mat[3][4]=0,tree[tr].mat[3][3]=1;break;
case '8':tree[tr].mat[3][3]=1,tree[tr].mat[4][4]=1;break;
}
return;
}
int mid=half;
build(tr<<1,l,mid),build(tr<<1|1,mid+1,r);
tree[tr]=mul(tree[tr<<1],tree[tr<<1|1]);
}
matrix query(int i,int l,int r,int ql,int qr)
{
if(ql<=l&&qr>=r) return tree[i];
int mid=half;
if(qr<=mid) return query(Lson,ql,qr);
else if(ql>=mid+1) return query(Rson,ql,qr);
else return mul(query(Lson,ql,qr),query(Rson,ql,qr));
}
int main()
{
cin>>n>>q;
cin>>s;
reverse(s.begin(),s.end());
s=" "+s;
build(1,1,n);
int l,r;
while(q--)
{
scanf("%d %d",&l,&r);
l=n-l+1,r=n-r+1;
swap(l,r);
matrix ans=query(1,1,n,l,r);
if(ans.mat[0][4]==inff) puts("-1");
else printf("%d\n",ans.mat[0][4]);
}
return 0;
}
边栏推荐
- 顺序表删除所有值为e的元素
- Error: flask: TypeError: 'function' object is not iterable
- codeforces Valera and Elections (这思维题是做不明白了)
- 单例 DCL(double check lock) 饱汉模式和饿汉模式
- Tkinter可以选择的颜色
- P6 ali machine test of 2020 Fibonacci number
- 2017.10.26模拟 b energy
- VS2019 common shortcut keys
- 【nuxt】服务器部署步骤
- 排序第一节——插入排序(直接插入排序+希尔排序)(视频讲解26分钟)
猜你喜欢
The working principle of the transformer (illustration, schematic explanation, understand at a glance)
stm32定时器之简单封装
分布式理论
当酷雷曼VR直播遇上视频号,会摩擦出怎样的火花?
unity第一课
分布式id 生成器实现
什么是分布式事务
高项 03 项目立项管理
错误:为 repo ‘oracle_linux_repo‘ 下载元数据失败 : Cannot download repomd.xml: Cannot download repodata/repomd.
6 states of a thread
随机推荐
入门cv必读的10篇baseline论文
事务总结
Example of using the cut command
力扣第 305 场周赛复盘
Simple to use Lambda expressions
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道
The AD in the library of library file suffix. Intlib. Schlib. Pcblib difference
P7 Alibaba Interview Questions 2020.07 Sliding Window Algorithm (Alibaba Cloud Interview)
搭载开源鸿蒙系统的嵌入式XM-RK3568工业互联方案
日期处理,字符串日期格式转换
分布式id 生成器实现
failed (13: Permission denied) while connecting to upstream
XxlJobConfig distributed timer task management XxlJob configuration class, replace
Altium designer软件常用最全封装库,包含原理图库、PCB库和3D模型库
leetcode 之 70 爬楼梯问题 (斐波那契数)
Transaction concluded
【Shell】查找进程的pid并根据pid获取该进程所占用的端口号以及该进程在系统中所下达的指令名称
字节跳动面试题之镜像二叉树2020
移远EC20 4G模块拨号相关
【Oracle 11g】Redhat 6.5 安装 Oracle11g