940C链接：http://codeforces.com/problemset/problem/940/C
C. Phone Numbers
2 seconds
256 megabytes
standard input
standard output
And where the are the phone numbers?
You are given a string s consisting of lowercase English letters and an integer k. Find the lexicographically smallest string t of length k, such that its set of letters is a subset of the set of letters of s and s is lexicographically smaller than t.
It's guaranteed that the answer exists.
Note that the set of letters is a set, not a multiset. For example, the set of letters of abadaba is {a, b, d}.
String p is lexicographically smaller than string q, if p is a prefix of q, is not equal to q or there exists i, such that pi < qi and for all j < i it is satisfied that pj = qj. For example, abc is lexicographically smaller than abcd , abd is lexicographically smaller than abec, afa is not lexicographically smaller than ab and a is not lexicographically smaller than a.
Input
The first line of input contains two space separated integers n and k (1 ≤ n, k ≤ 100 000) — the length of s and the required length of t.
The second line of input contains the string s consisting of n lowercase English letters.
Output
Output the string t conforming to the requirements above.
It's guaranteed that the answer exists.
input
3 3
abc
output
aca
input
3 2
abc
output
ac
input
3 3
ayy
output
yaa
input
2 3
ba
output
baa
Note
In the first example the list of strings t of length 3, such that the set of letters of t is a subset of letters of s is as follows: aaa, aab, aac, aba, abb, abc, aca, acb, .... Among them, those are lexicographically greater than abc: aca, acb, .... Out of those the lexicographically smallest is aca.
题意就是给你m长的字符串a，输出在给定字符基础上，输出长度为n且字典序恰好比a大的那个字符串。
似乎没坑，直接模拟！
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+;
char s[maxn];
bool vis[];
int main()
{
int m,n;
while(cin>>m>>n)
{
cin>>s;
memset(vis,false,sizeof(vis));
for(int i=; i<m; i++) vis[s[i]-'a']=true;
if(m<n)
{
for(int i=m; i<n; i++)
{
int f=;
for(int j=; j<=&&f; j++)
{
if(vis[j])
f=,s[i]=j+'a';
}
}
}
else
{
int f=;
for(int i=n-; i>=&&!f; i--)
{
int pos=s[i]-'a';
for(int j=pos+; j<=; j++)
{
if(vis[j])
{
f=;
s[i]=j+'a';
break;
}
}
if(!f)
{
int ff=;
for(int j=; j<=&&ff; j++)
{
if(vis[j])
ff=,s[i]=j+'a';
}
}
}
}
for(int i=;i<n;i++) cout<<s[i];
cout<<endl;
}
return ;
}
932B链接：http://codeforces.com/problemset/problem/932/B
2 seconds
256 megabytes
standard input
standard output
Let us define two functions f and g on positive integer numbers.
You need to process Q queries. In each query, you will be given three integers l, r and k. You need to print the number of integers x between l and r inclusive, such that g(x) = k.
The first line of the input contains an integer Q (1 ≤ Q ≤ 2 × 105) representing the number of queries.
Q lines follow, each of which contains 3 integers l, r and k (1 ≤ l ≤ r ≤ 106, 1 ≤ k ≤ 9).
For each query, print a single line containing the answer for that query.
4
22 73 9
45 64 6
47 55 7
2 62 4
1
4
0
8
4
82 94 6
56 67 4
28 59 9
39 74 4
3
1
1
5
In the first example:
- g(33) = 9 as g(33) = g(3 × 3) = g(9) = 9
- g(47) = g(48) = g(60) = g(61) = 6
- There are no such integers between 47 and 55.
- g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4
g(x)函数满足以下性质： 1. g(x)=x x<=9
2.g(x)=f(x), x>9
其中，f(x)函数表示的是，将x数位分离，非零的各个位上的数字相乘.
解题思路：
第一反应求g(x)时候，记忆化+打表。
然后看了下查询区间和查询次数的数据范围，打表时候还是把每个数对应的1--9的个数都求出来，每次查询时候直接一次O(1)的访问就差不多了。
1A代码：
#include<cstdio>
#include<iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=1e6+;
int a[maxn][];
int num[maxn];
int get(int x)
{
if(num[x]!=-) return num[x];
else if(x<=) return x;
else
{
int ans=;
while(x)
{
if(x%!=) ans*=(x%);
x/=;
}
return get(ans);
}
}
void pre()
{
memset(num,-,sizeof(num));
for(int i=;i<=maxn;i++)
num[i]=get(i);
//for(int i=20;i<=30;i++) printf("%d ",num[i]);
for(int i=;i<=;i++) a[][i]=;
a[][]=;
for(int i=;i<=maxn;i++)
{
for(int j=;j<=;j++)
{
a[i][j]=a[i-][j];
}
int cnt=num[i];
a[i][cnt]++;
}
return ;
}
int main()
{
int n,x,l,r;
pre();
while(~scanf("%d",&n))
{
while(n--)
{
scanf("%d%d%d",&l,&r,&x);
if(num[l]==x)
cout<<a[r][x]-a[l][x]+<<endl;
else
cout<<a[r][x]-a[l][x]<<endl;
}
}
return ;
}