【数学/数位DP】牛客网19寒假R3G

链接:https://ac.nowcoder.com/acm/contest/329/G
来源:牛客网

经过了选号和漫长的等待,处女座终于拿到了给小姐姐定制的手环,小姐姐看到以后直呼666!

处女座其实也挺喜欢6这个数字的,实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样,想起了小姐姐。

现在你要给处女座展示一系列数字,你想知道他的内心会激动多少次。对于同一个数字,他最多只会激动一次,即如果这个数是66666,他还是只会激动一次。

输入描述:

一行包括两个数字l,r,表示你给处女座展示的数字范围为 [l,r]

输出描述:

一行一个整数,表示处女座内心激动的次数。

  • 示例1
  • 输入
    10 20

  • 输出
    1

  • 备注
    0≤l≤r≤10^18

此题做法很多。

1. 数学

可以先想求不含6的数有多少个,那么题目实际上是问的去掉6以后,给定一个数,问这个数在不含6的数组成的序列中排第几个。那么可以看成是给定一个9进制数,问在十进制数里排第几个(值是多少)。

比如18,看成九进制1\times9^1 + 7\times9^0 = 16
由于6被去掉了,那么8就排在了第7位。这个思想在很多题目里都可以用到。

那么如果给定的数本来就含6怎么处理呢?
第一,x5999x6xxx内所包含的 不含6 的数其实是一样多的。
第二,通过列表可以发现,凡是某一位有6的都不存在了,相当于问12之间有多少个1。所以对于含6的数,把最高位的6改为5,低位全部改成9就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,pl,pr;
ll ni[22]={0},num[22]={0};

string 
Read the rest

【poj1961\kmp算法next数组思想】Period

http://poj.org/problem?id=1961

Period
Time Limit: 3000MS Memory Limit: 30000K
Total Submissions: 20690 Accepted: 10091

Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can … Read the rest

【字符串哈希】CH1401 兔子与兔子

描述
很久很久以前,森林里住着一群兔子。有一天,兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列(小兔子是外星生物,DNA 序列可能包含 26 个小写英文字母),然后我们每次选择两个区间,询问如果用两个区间里的 DNA 序列分别生产出来两只兔子,这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入格式
第一行一个 DNA 字符串 S。
接下来一个数字 m,表示 m 次询问。
接下来 m 行,每行四个数字 l1, r1, l2, r2,分别表示此次询问的两个区间,注意字符串的位置从1开始编号。
其中 1 ≤ length(S), m ≤ 1000000

输出格式
对于每次询问,输出一行表示结果。如果两只兔子完全相同输出 Yes,否则输出 No(注意大小写)

样例输入
aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2
样例输出
Yes
No
Yes

字符串哈希的练习模板题。

  • 坑:strlen很慢,放在循环里会超时。
  • s+1输入字符串,s[0]是结束符,如果传入strlen(s)会返回1;
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=1e6+23;
char s[maxn];
int m,l1,l2,r1,r2;
ull f[maxn],p[maxn];
Read the rest

【对顶堆】Running Median POJ – 3784

Running Median
Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3467		Accepted: 1606
Description

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.
Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set 
Read the rest

【STL::set】CH1301 邻值查找(迭代器使用学习)

描述
给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 A_i,求:
min(1≤j<i) ⁡|A_i-A_j|
以及令上式取到最小值的 j(记为 P_i)。若最小值点不唯一,则选择使 A_j 较小的那个。

输入格式
第一行一个整数n,第二行n个数A_1~A_n。

输出格式
n-1行,每行2个用空格隔开的整数。分别表示当i取2~n时,对应的 min(1≤j<i) ⁡|A_i-A_j| 和 P_i 的值。

样例输入
3
1 5 3
样例输出
4 1
2 1
数据范围与约定
对于30%的数据: n<=100
对于70%的数据: n<=10^4
对于100%的数据: n<=10^5, |A_i|<=10^9

一种做法是用set,因为set是有序集合,直接依次插入,每次找比这个数大的和小的,比较一下做差的绝对值。

  • 迭代器的使用:
  • set的迭代器只支持++和–两种运算
  • it++ 和 ++it 是不一样的,前者先返回自己,再运算,后者是先运算再返回自己。在使用的时候需要注意。
  • *号解除引用,*(it++) 和 *(++it)也是不一样的。尽管有括号。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+233;
map<int,int> hm;
set<int> st;
int n;
int k[maxn]={0};
int main()
{
    scanf("%d",&n);
    scanf("%d",&k[1]);
    st.insert(k[1]);
    hm[k[1]]=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&k[i]);
        st.insert(k[i]);
        
Read the rest

【栈/CF534B】Game with string

http://codeforces.com/contest/1104/problem/B

题意:
给定一串小写字母序列,每次取连着的两个相同字母,直到无法取为止

 

用栈来做。

由于必须取连着的两个,所以依次进栈,遇到和栈顶相同的就弹出,同时把取的次数+1

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+233;
char ss[maxn];
stack<int> prs;
int cond=0;
int main()
{
    scanf("%s",ss);
    int len=strlen(ss);
    prs.push(ss[0]);
    for(int i=1;i<len;i++)
    {
        if(!prs.empty()&&prs.top()==ss[i])
        {
            prs.pop();
            cond++;
        }
        else
        {
            prs.push(ss[i]);
        }   
    }
    printf("%s",(cond%2==1)?"Yes":"No");
}

 … Read the rest

【数论】三角关系

一个高中学长问的一道题,挺有意思的。也是简单数论

t1 T2

T2

根据同余的加性,(以下以=代替同余号)

由于a+b=b+c(%k),b=b(%k)

所以可以得到a=c(%k)

同理可以得到a=b=c(%k)

所以目标转化为找同余数。由于任意两个相加需要是K的倍数,所以他们的余数必须都为k/2或者0。

设余数为i,在k是偶数的时候余数可以是k/2和k,在k为奇数的时候i只能是k。

算出每组的个数,再组合数算一下。任意m个里取1个有m种排法,取2个有6*C(m,2)种,取3个有A(3,3)*C(m,3)种。答案就是他们加起来。由于解题的时候在上课,所以我并没有写代码,提问者照着我的思路写了,并且AC了…………

T3

是Java,把int改为long long就AC了… Read the rest

VScode配置g++编写c++

  1. 将g++添加到环境遍历
  2. 安装插件”code runner”
  3. 设置-插件-run code configuration-Run in terminal 勾选上(否则如果程序里有输入等待将无法继续)
  4. 下载微软官方插件C/C++ 以便于调试
  5. 在目录下的.vs文件夹里面生成:launch.json/tasks.json
{
    // 使用 IntelliSense 了解相关属性。 
    // 悬停以查看现有属性的描述。
    // 欲了解更多信息,请访问: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(gdb) Launch",
            "type": "cppdbg",
            "request": "launch",
            
            
            "program": "{fileDirname}/{fileBasenameNoExtension}.exe",
            
            
            //"program": "enter program name, for example {workspaceFolder}/a.exe",              "args": [],              "stopAtEntry": false,              "cwd": "{workspaceFolder}",
            "environment": [],
            "externalConsole": true,
            "MIMode": "gdb",
            //"miDebuggerPath": "/path/to/gdb",
            "miDebuggerPath": "C:/Program Files (x86)/Dev-Cpp/MinGW64/bin/gdb.exe",
            "preLaunchTask": "g++",
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ]
        
Read the rest

【数论】蓝桥杯历届试题 小数第n位

http://lx.lanqiao.cn/problem.page?gpid=T456

问题描述
  我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。
  如果我们把有限小数的末尾加上无限多个0,它们就有了统一的形式。


  本题的任务是:在上面的约定下,求整数除法小数点后的第n位开始的3位数。
输入格式
  一行三个整数:a b n,用空格分开。a是被除数,b是除数,n是所求的小数后位置(0<a,b,n<1000000000)
输出格式
  一行3位数字,表示:a除以b,小数后第n位开始的3位数字。
样例输入
1 8 1
样例输出
125
样例输入
1 8 3
样例输出
500
样例输入
282866 999000 6
样例输出
914

考虑到n取1e10,double的精度肯定是不够的。所以把数字放大10^n+2倍%1000进行计算。但由于b和1000不一定互质,所以不一定找得到逆元。

这里介绍一个公式

[latex]

\frac{a}{b} \mod p = \frac{a \mod b \times p}{b}

所以本题:

\frac{a}{b} \times 10^{n+2} \mod 10^3 = \frac{a \times 10^{n+2} \mod b \times 10^3}{b}

= \frac{(a \mod b \times 10^3) \times (10^{n+2} \mod b \times 10^3)}{b}

n取1e10,所以快速幂一下。就做完了,简单数论

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,n,mod;
ll ksm(ll 
Read the rest

蓝桥杯历届试题 小计算器

http://lx.lanqiao.cn/problem.page?gpid=T459

问题描述
  模拟程序型计算器,依次输入指令,可能包含的指令有


  1. 数字:'NUM X',X为一个只包含大写字母和数字的字符串,表示一个当前进制的数
  2. 运算指令:'ADD','SUB','MUL','DIV','MOD',分别表示加减乘,除法取商,除法取余
  3. 进制转换指令:'CHANGE K',将当前进制转换为K进制(2≤K≤36)
  4. 输出指令:'EQUAL',以当前进制输出结果
  5. 重置指令:'CLEAR',清除当前数字


  指令按照以下规则给出:
  数字,运算指令不会连续给出,进制转换指令,输出指令,重置指令有可能连续给出
  运算指令后出现的第一个数字,表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
  重置指令后出现的第一个数字,表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
  进制转换指令可能出现在任何地方


  运算过程中中间变量均为非负整数,且小于2^63。
  以大写的'A'~'Z'表示10~35
输入格式
  第1行:1个n,表示指令数量
  第2..n+1行:每行给出一条指令。指令序列一定以'CLEAR'作为开始,并且满足指令规则
输出格式
  依次给出每一次'EQUAL'得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040

按题意模拟就可以了。由于是整数,所以把所有进制化为十进制计算,省去了自己写运算的东西。输出的时候转再转换一下就可以了。有个坑点是在ADD等运算之间可能转换进制。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,char> eco;
map<char,ll> deco;
int k=10;
ll ans=0;
char num[99];
void init()
{
	for(ll i=0;i<=9;i++)
	{
		eco[i]=i+'0';
		deco[i+'0']=i;
	}
	for(ll i='A';i<='Z';i++)
	{
		eco[i-'A'+10]=i;
		deco[i]=i-'A'+10;
	}
}
ll getnum()
{
	
Read the rest