POJ 1850

news/2025/3/19 19:44:43/

组合数,

给一个字符串, 这个字符串必须为字典序升序,否则输出0,

求这个字符串排列在第几个;

距离 a = 1  ; b=2.... ab=27 ac=28.... ba不可以 az=51, bc = 52..... 长度不超过10

那么首先特盘递增,其次这个字符串是升序,所以对于长度 n 的 我们可以先加上 C[26] [ n - 1 ] C 代表组合数

26个字母先选出 n-1 个,之后对 n 长度开始处理

每次暴力搜素,因为 只有 26个字母,对于第 i 位, 搜索 s [i-1]   -  z ,进行一波组合数计算, 第一位 从 a 开始 每次都是

加上 c[ 26- s[i-1]  ]  [  strlen(s) - i  - 1 ]  就好了

以下为 AC 代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
#define ll long long int
ll c[30][30];
void combine()
{for(int j=0;j<=26;j++)for(int i=0;i<=j;i++)if(!j||i==j)c[j][i]=1;elsec[j][i]=c[j-1][i-1]+c[j-1][i];
}
char s[20];
int main()
{combine();scanf("%s",s);int len = strlen(s);int ans = 0;for(int i=1;i<len;i++){if(s[i]<=s[i-1]){printf("0\n");return 0;}}int sum=0;for(int i=1;i<len;i++)sum+=c[26][i];int st = 1;for(int i=0;i<len;i++){int en = s[i]-'a'+1;for(int j=st;j<en;j++){sum += c[26-j][len-(i+1)];}st = en+1;}printf("%d\n",sum+1);return 0;
}

 


http://www.ppmy.cn/news/690077.html

相关文章

HDOJ1850

题意&#xff1a;桌子上有M堆扑克牌&#xff1b;每堆牌的数量分别为Ni(i1…M)&#xff1b;两人轮流进行&#xff1b;每走一步可以任意选择一堆并取走其中的任意张牌&#xff1b;桌子上的扑克全部取光&#xff0c;则游戏结束&#xff1b;最后一次取牌的人为胜者。 现在我们不想研…

【CRC】一文搞懂CRC-8 SAE J1850 ZERO校验和

一、什么是 CRC 校验和 CRC —— Cyclic redundancy check 循环冗余校验&#xff0c;一种校验接收到的数据是否完整的算法&#xff0c;广泛应用于数据通信&#xff0c;大概流程如下 CRC8 —— 针对 8 位数据的 CRC 校验和 二、CRC-8 如何计算 首先&#xff0c;想要确定一个…

【代码】SAE J1850 CRC8算法 C语言的2种方式实现

循环冗余校验&#xff08;Cyclic Redundancy Check&#xff0c; CRC&#xff09;是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术&#xff0c;主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。…

GD32 汽车诊断协议J1850-PWM 测试

J1850-PWM 硬件说明:  MCU: GD32C103 120M,128K,32k RAM.  输入:USB 5V.  OBD功能口定义:OBD(2,10)VPWM、OBD 7(K线)、OBD 6(CAN H)、OBD 14(CAN L)、OBD 15(L线). 软件说明: 一、汽车CAN2.0(双线OBD 6、14) 1、支持波特率:1M、800K、500K、250K、125K、100K、62K、50…

POJ1850

题目链接&#xff1a;https://vjudge.net/problem/POJ-1850 AC思路&#xff1a; 可以把一个字符串S(设其长度为len) 所对应的数字看成排在其前面的所有字符串的个数加一。 对于S&#xff0c;排在其前面的字符串可以分成两类&#xff1a; 1、长度小于len 的所有字符串&#xff1…

GD32 汽车诊断协议 J1850-VPW 测试

J1850-VPW 硬件说明:  MCU: GD32C103 120M,128K,32k RAM.  输入:USB 5V.  OBD功能口定义:OBD(2,10)VPWM、OBD 7(K线)、OBD 6(CAN H)、OBD 14(CAN L)、OBD 15(L线). 软件说明: 一、汽车CAN2.0(双线OBD 6、14) 1、支持波特率:1M、800K、500K、250K、125K、100K、62K、50…

DELL 1850 产品简介

DELL 1850 使用的芯片是 Intel 1.处理器 32&64T 兼容 2.远程管理(可以进行远程安装软件,但要求在同一个局域网内,不能通过公网中转完成远程安装) SC1420 是dell 入门级产品,最多2个cpu 1800 ,1850 是戴尔的主要产品, 2800,2850 要比 1800,1850 扩展性好 185…

H3C(s1850)初始化配置流程

H3C&#xff08;s1850&#xff09;初始化配置流程 1.配置时间 clock datetime HH:MM:SS YYYY/MM/DD clock timezone bj add 8 2.配置交换机名称 sysname 3.关闭console登录认证 user-interface aux 0 authentication-mode none 4.开启Telnet服务 service telnet enable 5.配置…