首页 > 其他分享 >CF--EDU--142

CF--EDU--142

时间:2023-02-14 17:13:42浏览次数:60  
标签:ch 142 -- CF long int using define

D. Fixed Prefix Permutations

思路

字典树的应用
因为要对前面已经有过的信息进行筛选,可以用字典树来进行维护

思路

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using pdd=pair<double,double>;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define TT int _=read();while(_--)
#define int long long
using ll=long long;
const ll inf=1e18;
//#define double long double
#define endl '\n'
const int M=5e4+5;

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<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

inline void print(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x/10)print(x/10);
    putchar(x%10+'0');
}

//对前面的信息进行更新合并,经典的字典树呀
int n,m;
int a[M][11],b[M][11];
int ch[M*10][11],tot;

void insert(int c[]) {
    int p=0;
    for(int i=1;i<=m;i++) {
        if(!ch[p][c[i]])ch[p][c[i]]=++tot;
        p=ch[p][c[i]];
    }
}

int solve(int c[]) {
    int p=0;
    for(int i=1;i<=m;i++) {
        if(ch[p][c[i]]==0)return i-1;
        p=ch[p][c[i]];
    }
    return m;
}

signed main() {
    TT {
        for(int i=0;i<=tot;i++)
            for(int j=1;j<=10;j++)ch[i][j]=0;
        tot=0;
        n=read(),m=read();
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                a[i][j]=read();
                b[i][a[i][j]]=j;//这个位置应该是什么数,才可以进行匹配
            }
            insert(b[i]);
        }
        for(int i=1;i<=n;i++)
            cout<<solve(a[i])<<' ';
        cout<<'\n';
    }
    return 0;
}

标签:ch,142,--,CF,long,int,using,define
From: https://www.cnblogs.com/basicecho/p/17120195.html

相关文章

  • macOS Ventura 13.2.1发布
    想要体验最新的macOSVentura13.2.1系统?哪里可以下载最新正版macOSVentura13.2.1呢?苹果今天发布了macOSVentura13.2.1,这是macOSVentura操作系统的一个小版本更新。m......
  • 小波去噪算法的简易实现及其扩展(小波锐化、高斯拉普拉斯金字塔去噪及锐化)之二。
    上一篇文章谈及了GIMP里实现的小波分解,但是这仅仅是把图像分解为多层的数据,如果快速的获取分解数据以及后续怎么利用这些数据,则是本文的重点。一、我们先来看看......
  • 基于Spring MVC的前后端分离开发
    一.后台服务器端开发:先搭建一个springMVC项目1.新建一个web项目2.引入相关jar包,编写配置文件(1).引入spring包spring-framework-5.0.8.RELEASE,这个包里有相关Bean、co......
  • 二分法计算错误
    2023牛客冬季训练5-A二分代码出错,使用upper_bound()正确while(l<r){intmid=l+r+1>>1;if(a[mid]<=x)......
  • 1599 - 米老鼠偷糖果
       ......
  • 《黑吗旅游网》综合案例五 登录
    登录功能分析:  Servlet层:@WebServlet("/loginServlet")publicclassLoginServletextendsHttpServlet{protectedvoiddoPost(HttpServletRequestreque......
  • Markdown的基本使用方法
    标题一级标题:#+空格+标题名称+回车二级标题有两个#三个标题有三个#.......字体加粗:在需要加粗字的前后端各添加两个*+回车加粗斜体:在需要斜体字的前后端各添加一个......
  • 计算机基础知识
    冯.诺依曼体系结构cpu里面主要有运算器和控制器,控制器可以控制输入设备、存储器、输出设备,运算器从存储器中提取数据进行运算然后返回给存储器。计算机软件系统软件:;DOS......
  • WebUploader 文件上传,兼容ios和安卓
    varupImg=WebUploader.create({auto:true,swf:'webuploader-0.1.5/Uploader.swf',//图片接收服务端。server:contextPath+'simpleUpload',//......
  • 我已经受够了“系统异常”!
    作为用户,你有没有这样的经验:用个软件,隔三岔五弹个框:系统异常!作为程序员,你有没有这样的经验:运营同学又屁颠屁颠跑来求助:“用户不能下单了!”“报什么错?”“系统异常!”无......