湖南中医药大学信息科学与工程学院第四届大学生程序设计竞赛——正式赛题解

• 问题A:X星人的统计
• 问题B:X星人的报数
• 问题C:X星人的迷宫
• 问题D:X星人的高考
• 问题E:X星人的匹配
• 问题F:X星人的成绩
• 问题G:X星人的变换
• 问题H:X星人的游戏
• 问题I:X星人的宝石
• 问题J:X星人的车牌
• 问题K:X星人的括号
• 问题L:X星人的翻译

题目描述
一年一度的X星人口普查又开始了，其中有一项是统计各民族X星人的数量。X星人分属四个不同的民族，四个民族分别用A、B、C和D表示。
现在给出N个X星人的民族信息，请统计各民族X星人的总数。

输入
单组输入。
第1行输入统计的总人数N，N<=10^6。
第2行输入N个X星人的民族信息，四个民族分别用A、B、C和D表示，两两之间用英文空格隔开。

输出
请按照A、B、C、D的顺序分别输出每一个民族的总人数，两两之间用英文空格隔开。

样例输入

10
A C B D A C B D D A

样例输出

3 2 2 3

分析
签到题，直接按照题意模拟即可

代码

#include 
#include 
using namespace std;
const int N=1e6+5;
int num[5];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        getchar();
        char x;scanf("%c",&x);
        num[x-'A']++;
    }
    for(int i=0;i<4;i++){
        if(i!=3)printf("%d ",num[i]);
        else printf("%dn",num[3]);
    }
    return 0;
}

题目描述
N个X星人站成一排，他们发明了一种奇怪的报数方式。
从第1个人开始报数，第1个人报数为1，第2个人报数为2，接下来奇数位置的人报数为前一个人报数加1，偶数位置的人报数为前一个人的两倍。
请问第N个人的报数是多少？

输入
输入一个正整数N(N<=40)。

输出
输出第N个人的报数。

样例输入

4

样例输出

6

题解
签到题，也是按照题目意思简单模拟即可。

代码

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N=45;
int a[N];
int main()
{
    int n;scanf("%d",&n);
    a[1]=1,a[2]=2;
    for(int i=3;i<=n;i++){
        if(i%2)a[i]=a[i-1]+1;
        else a[i]=2*a[i-1];
    }
    printf("%dn",a[n]);
    return 0;
}

题目描述
X星人进入了一个树形迷宫，该迷宫由一个N层的满二叉树组成。迷宫的每一个节点都有一个计分权重，只有找到那条从根节点开始到叶子结点的计分权重和最大的路径，X星人才能够顺利走出迷宫。
现在给出该树形迷宫每一个节点的权重值，你能否编写一个程序计算出权重和最大的路径所对应的总权重。

输入
单组输入
第1行输入一个正整数N，表示二叉树的节点层数。（N<=20）
第2行输入2^N-1个正整数，分别表示迷宫中每一个节点的权重，两两之间用英文空格隔开。第1个数字表示根节点的权重，接下来两个数字表示根节点左、右孩子的权重，再接下来四个数字表示第3层的四个节点的权重，…，以此类推。每个节点的权重均不超过1000。

输出
输出从根节点出发到叶子节点权重和最大的路径所对应的权重。

样例输入

3
10 20 30 100 20 50 40

样例输出

130

题解
中等题，直接用DFS或者BFS搜索，搜索到根节点时，维护一个最大的权重即可。

代码

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N=1500000+5;
int a[N];
int n,ans=0;
void dfs(int x,int sum){
    if(x>n)return ;
    sum+=a[x];
    ans=max(ans,sum);
    dfs(x*2,sum);
    dfs(x*2+1,sum);
}
int main()
{
    scanf("%d",&n);
    n=pow(2,n)-1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs(1,0);
    printf("%dn",ans);
    return 0;
}

题目描述
一年一度的X星高考如期举行。今年X星新高考一卷的数学真的很难，据说把很多考生都考哭了。
今年数学考试的多选题仍然是4道题，每题5分，共20分。在每小题给出的4个选项中，有多项符合题目要求，全对得5分，选对但不全得2.5分，有选错的得0分。每道题均包含A、B、C和D四个选项。
现在给出某X星考生的多选题答案和正确答案，请编写一个程序计算该X星考生最终多选题的得分

输入
单组输入。
每组输入两行，第1行包含该X星人四道多选题的答案，两两之间用空格隔开；第2行包含四道多选题的正确答案，两两之间用空格隔开（答案不一定按照字典序排列）。

输出
输出该X星考生最终多选题的得分(答案保留一位小数)。

样例输入

A BC AC ABC
AB BC AD AB

样例输出

7.5

题解
简单题，可以直接在正确答案中依次判断是否存在X星考生选择的答案，若全部完全匹配，则全对得5分；若选对但不全对得2.5分；一旦有选错的得0分。
需要注意，ABCD是包含AD的，一开始有的同学直接判断在ABCD中使用find函数，查是否能find到AD，这是显然不对的。

代码

#include 
#include 
#include 
#include 
#include 

using namespace std;
string a[5],b[5];
int main()
{
    for(int i=1;i<=4;i++)cin>>a[i];
    for(int j=1;j<=4;j++)cin>>b[j];
    double ans=0;
    for(int i=1;i<=4;i++){
        string s=a[i],t=b[i];
        int num=0,flag=1;
        for(int i=0;i
            if(t.find(s[i])
            if(num==t.size())ans+=5;
            else ans+=2.5;
        }
    }
    printf("%.1fn",ans);
    return 0;
}

题目描述
X星人有一个只包含数字0和1的目标串a和一个匹配串b ，匹配串除了0和1还有两种特殊匹配符，第一种是’?‘可以匹配任何一个字符，另外一种是’*'可以匹配任意字符串(包含空字符串)，现在需要你判断目标串和匹配串能不能完全匹配(对于两个串都不能有未匹配字符)。

输入
单组输入，第一行输入目标串a，第二行输入匹配串b。输入保证两个字符串长度均<=1e3。

输出
完全匹配输出true，否则输出false。

样例输入

00
*

样例输出

true

题解
困难题，动态规划， d p ( i , j ) dp(i,j) dp(i,j) 代表考虑 a a a中以 i i i为结尾的子串和 b b b中的 j j j为结尾的子串是否匹配。即最终我们要求的结果为 d p [ n ] [ m ] dp[n][m] dp[n][m]（ n n n为 a a a串的长度， m m m为 b b b串的长度）。
状态转移：也就是我们要考虑 d p ( i , j ) dp(i,j) dp(i,j)如何求得，前面说到了 b b b有三种字符，所以这里的状态转移也要分三种情况讨论：
b [ j ] b[j] b[j]为普通字符：匹配的条件是前面的字符匹配，同时 a a a中的第 i i i个字符和 b b b中的第 j j j位相同。 即 d p ( i , j ) = d p ( i − 1 , j − 1 ) & & a [ i ] = = b [ j ] dp(i,j) = dp(i - 1, j - 1) && a[i] == b[j] dp(i,j)=dp(i−1,j−1)&&a[i]==b[j] 。
b [ j ] b[j] b[j] 为 ′ ? ′ '?' ′?′：匹配的条件是前面的字符匹配， a a a中的第 i i i个字符可以是任意字符。即 d p ( i , j ) = d p ( i − 1 , j − 1 ) & & b [ j ] = = ′ ? ′ dp(i,j)=dp(i-1,j-1)&&b[j]=='?' dp(i,j)=dp(i−1,j−1)&&b[j]==′?′。
b [ j ] b[j] b[j]为 ′ ∗ ′ '*' ′∗′：可匹配任意长度的字符，可以匹配 0 0 0个字符、匹配 1 1 1个字符、匹配 2 2 2个字符…
当匹配为 0 0 0个： d p ( i , j ) = d p ( i , j − 1 ) dp(i,j)=dp(i,j-1) dp(i,j)=dp(i,j−1)
当匹配为 1 1 1个： d p ( i , j ) = d p ( i − 1 , j − 1 ) dp(i,j)=dp(i-1,j-1) dp(i,j)=dp(i−1,j−1)
当匹配为 2 2 2个： d p ( i , j ) = d p ( i − 2 , j − 1 ) dp(i,j)=dp(i-2,j-1) dp(i,j)=dp(i−2,j−1)
…
当匹配为 k k k个： d p ( i , j ) = d p ( i − k , j − 1 ) dp(i,j)=dp(i-k,j-1) dp(i,j)=dp(i−k,j−1)
因此对于 b [ j ] = ′ ∗ ′ b[j]='*' b[j]=′∗′的情况，想要 d p ( i , j ) = t r u e dp(i,j)=true dp(i,j)=true，只需要其中一种情况为$true $即可。也就是状态之间是「或」的关系：
d p [ i ] [ j ] = d p [ i ] [ j − 1 ] ∣ ∣ d p [ i − 1 ] [ j − 1 ] ∣ ∣ . . . ∣ ∣ d p [ i − k ] [ j − 1 ] ( i > = k ) dp[i][j]=dp[i][j-1]||dp[i-1][j-1]||...||dp[i-k][j-1](i>=k) dp[i][j]=dp[i][j−1]∣∣dp[i−1][j−1]∣∣...∣∣dp[i−k][j−1](i>=k)

我们通常可以通过「代数」进简化，将 i − 1 i-1 i−1代入上述的式子：
d p [ i − 1 ] [ j ] = d p [ i − 1 ] [ j − 1 ] ∣ ∣ d p [ i − 2 ] [ j − 1 ] ∣ ∣ . . . ∣ ∣ d p [ i − k ] [ j − 1 ] ( i > = k ) dp[i-1][j]=dp[i-1][j-1]||dp[i-2][j-1]||...||dp[i-k][j-1](i>=k) dp[i−1][j]=dp[i−1][j−1]∣∣dp[i−2][j−1]∣∣...∣∣dp[i−k][j−1](i>=k)

可以发现， d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]与 d p [ i ] [ j ] dp[i][j] dp[i][j]中的 d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j−1]开始的后半部分是一样的，因此有：
d p [ i ] [ j ] = d p [ i ] [ j − 1 ] ∣ ∣ d p [ i − 1 ] [ j ] ( i > = 1 ) dp[i][j]=dp[i][j-1]||dp[i-1][j] (i>=1) dp[i][j]=dp[i][j−1]∣∣dp[i−1][j](i>=1)

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=1e3+5;
bool dp[N][N];//a串前i个字符和b串前j个字符能不能匹配成功
char a[N],b[N];
int main()
{
    scanf("%s %s",a+1,b+1);
    int n=strlen(a+1),m=strlen(b+1);
    dp[0][0]=1;
    for(int j=1;j<=m;j++){
        if(b[j]=='*')dp[0][j]=dp[0][j-1];//前缀有很多个*
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[j]=='*')dp[i][j]=dp[i][j-1]||dp[i-1][j];
            else if(dp[i-1][j-1]&&(a[i]==b[j]||b[j]=='?')){
                dp[i][j]=1;
            }
        }
    }
    if(dp[n][m])puts("true");
    else puts("false");
    return 0;
}

题目描述
与蓝星一样，X星高考也在6月7日和6月8日如期举行。N个X星考生在估算他们的总成绩，现在已经知道M对X星考生之间的成绩关系，格式为：A B，即A的总成绩高于B的总成绩。
现在需要对这N个X星人的成绩进行排序，请问还需要补充多少个关系？
输入数据保证不会出现冲突，如果不需要补充关系即可得到完整的成绩排序则输出0。

输入
单组输入。
第1行输入两个正整数N和M，分别表示X星考生的人数（考生序号从1到N）和已知关系的数量，其中：1<=N<=100，1<=M<=10000。
接下来M行表示M对成绩关系，每行包含两个正整数A和B，表示A的总成绩高于B的总成绩。输入数据保证不会出现冲突，即不会出现无法排序的情况。

输出
输出要对这N个X星人的成绩进行排序还需要补充的关系个数，如果不需要补充关系即可得到完整的成绩排序则输出0。

样例输入

3 2
1 2
1 3

样例输出

1

题解
中等题，构建关系图很容易想到使用拓扑排序，先想清楚关系图可能会形成几棵树，所以在处理到同一层度数为0的节点可能有多个，显然需要对同层这些节点的关系进行补全，假设有N个这样的节点就需要补上N-1对关系，拓扑处理完每一层后就可以得到答案。

代码

#include
using namespace std;
const int N=1e5+5;
struct node{
    int v,to,nex;
}e[N];
int head[N],cnt;
void add(int a,int b){
    e[++cnt].to=b;
    e[cnt].nex=head[a];
    head[a]=cnt;
}
int num[1005];
int main(){
    memset(head,-1,sizeof head);
    cnt=0;
    int n,m,a,b;
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        add(a,b);
        ++num[b];
    }
    queue q;
    for(int i=1;i<=n;++i){
        if(!num[i]){
            q.push(i);
        }
    }
    int ans=0;
    while(!q.empty()){
        int k=q.size();
        ans+=k-1;
        while(k--){
            int x=q.front();q.pop();
            for(int i=head[x];~i;i=e[i].nex){
                int to=e[i].to;
                --num[to];
                if(num[to]==0){
                    q.push(to);
                }
            }
        }
    }
    cout< 
问题G:X星人的变换 
题目描述
 X星人发明了一种简单的基于字符串变换的加密方法，具体规则如下：
 (1) 将输入的明文字符串（明文中只包含小写字母和空格）以单词为单位进行逆序，即将明文中的第1个单词移到最后，第2个单词移到倒数第二，…，最后一个单词移到最前面。
 (2) 再将每一个单词的第一个字母和它的最后一个字母进行调换。
 (3) 输出变换之后的密文字符串。
 
输入
 单组输入，每组输入一行字符串表示加密之前的明文，字符串中仅包含小写字母和空格，且长度不超过1000。
 
输出
 输出变换之后的密文字符串。
 
样例输入
 
 
 
i love hnucm
 
 
样例输出
 
 
 
mnuch eovl i
 
 
题解
 简单题，直接按照题目意思模拟，得到每一个单词进行变换即可。
 
代码
 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=1e3+5;
string ans[N];
int main()
{
    string s;getline(cin,s);
    int k=0;
    string t;
    for(int i=0;i
        if(isalpha(s[i]))t+=s[i];
        else ans[k++]=t,t="";
    }
    if(t!="")ans[k++]=t;
    for(int i=k-1;i>=0;i--){
        t=ans[i];
        int len=t.size();
        swap(t[0],t[len-1]);
        cout< 
问题H:X星人的游戏 
题目描述
 X星人准备开发一个24点游戏。在游戏中随机给出四个1-9之间的数字，包含1和9，用加、减、乘、除和加括号的方式将这四个数字组成一个算式，每个数字必须使用且只能使用一次，使得其最终的计算结果等于24。例如，输入3、8、8、9这四个数字，对应的算式可以是：(9-8)×8×3=24。【注：四个数字的出现次序可以调整，除法是用’/'表示即向下取整。】
 现在请你编写一个程序，输入四个1-9之间的数字，判断能否通过加入运算符和括号使得它们组成一个结果为24的算式。如果能够组成，请输出“Yes”，否则输出“No”。
 
输入
 单组输入。
 输入四个1-9之间的数字，两两之间用空格隔开。
 
输出
 如果通过加入运算符和括号，使得四个输入的数字可以组成一个结果为24的算式则输出“Yes”，否则输出“No”。
 
样例输入
 
 
 
3 8 8 9
 
 
样例输出
 
 
 
Yes
 
 
题解
 中等题，可以直接暴力DFS，将几个符号分别插入到几个数字中，暴力搜索到每一种情况，判断是否等于24即可。
 
代码
 dfs
 
#include
#define ll long long
using namespace std;
const int maxn=1e5+5;
int a[5],vis[5],ans=0;
void dfs(double now,int num){
    // cout<
        ans=1;
        return;
    }
    for(int i=1;i<=4;++i){
        if(vis[i])continue;
        vis[i]=1;
        dfs(now+a[i],num+1);
        dfs(now-a[i],num+1);
        dfs(now*a[i],num+1);
        dfs(now/a[i],num+1);
        vis[i]=0;
    }
}
int main(){
    for(int i=1;i<=4;++i){
        cin>>a[i];
    }
    for(int i=1;i<=4;++i){
        memset(vis,0,sizeof(vis));
        vis[i]=1;
        dfs(a[i],1);
    }
    if(ans)cout<<"Yes"< 
更严谨的方法
 
#include
using namespace std;
vector v,u;
int a[4];
string s;
char op[4]={'+','-','*','/'};
void dfs(int p){
    if(p==3){
        s+=a[p]+'0';
        v.push_back(s);
        s.pop_back();
        return;
    }
    for(int i=0;i<4;i++){
        s+=a[p]+'0';
        s+=op[i];
        dfs(p+1);
        s.pop_back();
        s.pop_back();
    }
}
int idx;
bool spj;
int cnt(string str){
    if(spj){
        return -1;
    }
    int n=str.size();
    int num=0;
    char sign='+';
    stack sta;
    spj=0;
    while(idx
        char ch=str[idx++];
        if(ch=='('){
            num=cnt(str);
        }else if(isdigit(ch)){
            num=ch-'0';
        }
        if(!isdigit(ch)||idx==n){
            if(sign=='+'){
                sta.push(num);
            }else if(sign=='-'){
                sta.push(-num);
            }else if(sign=='*'){
                num=sta.top()*num;
                sta.pop();
                sta.push(num);
            }else if(sign=='/'){
                if(num==0){
                    spj=1;break;
                }else{
                    num=sta.top()/num;
                    sta.pop();
                    sta.push(num);
                }
            }
            sign=ch;
            num=0;
        }
        if(ch==')'){
            break;
        }
    }
    if(spj){
        return -1;
    }
    int ans=0;
    while(!sta.empty()){
        ans+=sta.top();
        sta.pop();
    }
    return ans;
}
bool ju(){
    string p0,p1,p2,ss;
    for(auto str:v){
        p1=str.substr(0,5);
        p2=str.substr(5,2);
        ss='('+p1+')'+p2;
        u.push_back(ss);
        p1=str.substr(0,2);
        p2=str.substr(2,5);
        ss=p1+'('+p2+')';
        u.push_back(ss);
        p1=str.substr(0,3);
        p2=str.substr(3,4);
        ss='('+p1+')'+p2;
        u.push_back(ss);
        p0=str.substr(0,2);
        p1=str.substr(2,3);
        p2=str.substr(5,2);
        ss=p0+'('+p1+')'+p2;
        u.push_back(ss);
        p1=str.substr(0,4);
        p2=str.substr(4,3);
        ss=p1+'('+p2+')';
        u.push_back(ss);
        p0=str.substr(0,3);
        p1=str.substr(3,1);
        p2=str.substr(4,3);
        ss='('+p0+')'+p1+'('+p2+')';
        u.push_back(ss);
    }
    for(auto str:u){
        idx=0;
        spj=0;
        if(cnt(str)==24){
            return true;
        }
    }
    return false;
}
int main(){
    for(int i=0;i<4;i++){
        cin>>a[i];
    }
    bool flag=0;
    do{
        v.clear();
        u.clear();
        dfs(0);
        if(ju()){
            flag=1;break;
        }
    }while(next_permutation(a,a+4));
    if(flag){
        cout<<"Yes"<
        cout<<"No"< 
问题I:X星人的宝石 
题目描述
 X星人A和X星人B有很多的宝石，每个宝石都有一个价值v。
 现在他们要进行一个游戏，现有一个宝石堆，X星人A和X星人B轮流进行操作，A先手，每一回合，从宝石堆中拿走一个石子。
 
如果某个X星人拿走宝石后，所有已经拿走的宝石价值之和可以被3整除，那么该X星人输掉游戏
如果不满足上一条，且最后宝石都被拿完，那么B直接获胜（不管在谁的回合）
 X星人A和X星人B马上就精通了该游戏，对每一步都能做出最佳的决策，如果A获胜，输出"A win"，若B获胜，输出"B Win"
 
输入
 第一行包括一个正整数n(1≤n≤1e5)
 第二行包括n个正整数v1,v2…vn(1≤vi≤1e4)，代表宝石堆中每个宝石的价值
 
输出
 如果A获胜，输出"A win"，若B获胜，输出"B Win"
 
样例输入
 
 
 
2
 2 1
 
 
样例输出
 
 
 
A win
 
 
题解
 思维困难题。这里我们只简单讲一下博弈的规则。
 
A只有一种获胜方式，是使得B在选石子时凑成3的倍数；而B除了能够通过让A凑成3的倍数以外，还能通过让游戏常规结束来获胜。
 
因此整个游戏过程，我们只需要关心「已被移除的石子总和」和「剩余石子个数/价值情况」即可。
 
更进一步的，我们只需关心已被移除的石子总和是否为3的倍数，以及剩余石子的价值与已移除石子总和相加是否凑成 3的倍数即可。
 
所以我们可以按照石子价值除以3的余数分成三类，并统计相应数量。
 
不失一般性考虑，某个回合开始前，已移除的石子总和状态为x（共三种，分别为除以3余数为0、1和2，其中当状态为 0，且非首个回合时，说明凑成3的倍数，游戏结束），剩余石子价值除以3的余数s分别为0、1和2。
 
首先如果当前x = 1时，不能选择s=2的石子，否则会导致凑成总和为3的倍数而失败；同理x=2时，不能选择s=1的石子；而选择s=0的数字，不会改变 x的状态，可看做换手操作。
 
同时成对的s=0的等价于没有s=0的石子（双方只需要轮流选完这些s=0的石子，最终会回到先手最开始的局面）；而选择与x相同的s会导致x改变（即x=1时，选择s=1的石子，会导致 x=2；而x=2时，选s=2的石子，会导致x=1）。
 
代码
 
#include 
#include 
using namespace std;
const int N=1e5+5;
int v[N];
int num[5];
bool check(){
    if(num[0]%2==0)return num[1]&&num[2];//如果余数为0的数的个数为偶数个，不影响最后的结果。
    //只要同时存在余数为1和余数为2的数，先取个数少的那个，总会有剩余的数，而且Bob输
    return abs(num[1]-num[2])>2;
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)v[i]%=3,num[v[i]]++;
    if(check())puts("A win");
    else puts("B win");
    return 0;
}
 
问题J:X星人的车牌 
题目描述
 X星的车牌号码一共有9位，从“000000000”到“999999999”。
 某X星人不喜欢车牌号码中包含“2”和“14”这两组数字，因为他不喜欢一个人过会让他伤心的情人节。例如：“0020013579”和“1234148866”是该X星人不喜欢的号码，但是“1004010400”则不在不喜欢号码之列。【注：对于不足9位的数字可以在其高位补充若干个零使其达到9位。】
 
输入
 单组输入，输入两个正整数n和m，满足1<=n<=m<10^9。
 
输出
 统计在n和m之间（包含n和m）X星人不喜欢的号码个数。
 
样例输入
 
 
 
1 20
 
 
样例输出
 
 
 
4
 
 
题解
 中等题，数位DP，dp数组的处理
 
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i][j]
      
     
    dp[i][j]表示在前i位中，第i位为j的个数
 转态转移：考虑第
    
     
      
       
        i
       
       
        −
       
       
        1
       
      
      
       i-1
      
     
    i−1位，假设为
    
     
      
       
        k
       
      
      
       k
      
     
    k，根据要求，
    
     
      
       
        j
       
      
      
       j
      
     
    j为
    
     
      
       
        1
       
      
      
       1
      
     
    1时
    
     
      
       
        k
       
      
      
       k
      
     
    k不为
    
     
      
       
        4
       
      
      
       4
      
     
    4且
    
     
      
       
        k
       
      
      
       k
      
     
    k不能等于
    
     
      
       
        2
       
      
      
       2
      
     
    2，按照这个进行状态转移。
 
代码
 
#include 
#include 
#include 
using namespace std;
const int N=35;
int f[N][10];//f[i][j]表示在前i位中，第i位为j的个数
int l,r;
void init(){
    for(int i=0;i<=9;i++){
        if(i!=2)f[1][i]=1;
    }
    for(int i=1;i
        for(int j=0;j<=9;j++){
            if(j==2)continue;
            for(int k=0;k<=9;k++){
                if(k==2||(j==1&&k==4))continue;
                f[i][j]+=f[i-1][k];
            }
        }
    }
}
int dp(int n){
    if(!n)return 1;
    vectornums;
    while(n)nums.push_back(n%10),n/=10;
    int res=0,last=0;
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        for(int j=0;j
            if(j==2||(last==1&&j==4))continue;
            res+=f[i+1][j];
        }
        if((last==1&&x==4)||x==2)break;
        last=x;
        if(!i)res++;
    }
    return res;
}
int main()
{
    init();
    scanf("%d %d",&l,&r);
    printf("%dn",r-l+1-(dp(r)-dp(l-1)));
    return 0;
}
 
问题K:X星人的括号 
题目描述
 在X星人的语言中，括号具有一些特殊的含义。因此，X星人经常使用四种括号，包括“(”和“)”、“<”和“>”、“{”和“}”、“[”和“]”。但是在使用这些括号的时候需要同种类型的左括号和右括号逐一匹配，例如：“({[]})”是一个合法的括号匹配，而“{[(]))”不是合法的括号匹配。
 现在给出一串由各种括号组成的字符串，请编写一个程序输出其中包含的最长匹配连续子括号串的长度。
 
输入
 单组输入。
 输入占一行，包含一个由“(”和“)”、“<”和“>”、“{”和“}”、“[”和“]”8种括号字符组成的括号字符串，其长度不超过1000。
 
输出
 输出输入括号串的最长匹配连续子括号串的长度，如果一对匹配的括号都没有则输出0。
 
样例输入
 
 
 
[[(({<>})]}{()}
 {[(<)>]}
 
 
样例输出
 
 
 
6
 0
 
 
提示
 对于输入样例1，其最长匹配子括号串为“({<>})”，长度为6。
 对于输入样例2，不存在连续且匹配的括号，因此输出0。
 
题解
 中等题，使用栈来模拟。栈顶记录的是与目前探查的括号序列并列的最左边的括号的前一个字符的位置。
 从左向右遍历字符串元素。遇到左括号则将该位置压入栈。如果遇到右括号的话，如果不能与栈顶的左括号匹配，则说明这个右括号是多余的，压入栈。如果遇到右括号能匹配，则找到了一个括号序列。这个时候栈顶元素为与这个右括号匹配的左括号的位置。但注意到可能有多个括号并列的情况，进行一次出栈后栈顶元素就是与目前探查的括号序列并列的最左边的括号的前一个字符的位置。观察到了一个新的括号序列，更新最大长度。
 
代码
 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int main(){
    string s;
    while(cin>>s){
        stackp;
        int ma=0;
        for(int i=0;i
            if(!p.empty()){
                if(s[i]==')'&&s[p.top()]=='(')p.pop();
                else if(s[i]==']'&&s[p.top()]=='[')p.pop();
                else if(s[i]=='}'&&s[p.top()]=='{')p.pop();
                else if(s[i]=='>'&&s[p.top()]=='<')p.pop();
                else p.push(i);
            }
            else p.push(i);
            if(!p.empty())ma=max(ma,i-p.top());
            else ma=max(ma,i+1);
        }
        printf("%dn",ma);
    }
    return 0;
}
 
问题L:X星人的翻译 
题目描述
 X星人非常喜欢地球上一个伟大的国家——中国，他们觉得中国的一切都很美好，包括语言和文字。
 但是X星人发现要掌握中国的文字——“中文”有点太难，他们非常希望能够编写程序将一个阿拉伯数字翻译成中文，例如将“1234.567”翻译为“一千二百三十四点五六七”，将“001001.10010”翻译为“一千零一点一零零一零”。
 
输入
 单组输入。
 输入一个浮点数，整数部分的最前面和小数部分的最后面可能存在一个或多个0，其中整数部分不超过10位（包括前面的0），小数部分不超过6位（包括后面的0）。
 
输出
 输出数字翻译之后的中文读法，整数部分最前面的零不需要读出，但是小数部分最后面的零需要全部读出来。
 
样例输入
 
 
 
010100010.30900
 
 
样例输出
 
 
 
一千零一十万零一十点三零九零零
 
 
题解
 困难题，题意不难理解，模拟比较复杂。
 这里只提一点，每四位的处理方法是一样的，只是每个四位的单位分别是亿，万，注意细节。
 
代码
 
#include 
#include 
#include 
#include 
#include 
using namespace std;
string wei[4] = {"千","百","十",""};
string shu[10] = {"零","一","二","三","四","五","六","七","八","九"};
//n少于等于4位
string numToCn(int n)
{
    if(n==0)return "";
    string re="",s=to_string(n);
    //是否有非零数字出现了
    bool notLing = false;
    //上一个数是否为零
    bool ling=false;
    for(int i=(int)s.size() - 1,j=3;i>=0;i--,j--){
        if(s[i] == '0'){
            if(!ling && notLing){
                ling = true;
                re="零"+re;
            }
        }
        else{
            re=shu[(s[i]-'0')]+wei[j]+""+re;
            notLing=true;
            ling=false;
        }
    }
    return re;
}

int main()
{
    string s;cin>>s;
    int i=0;
    while(s[i]=='0')i++;
    int l=i;
    string res;
    for(;i
        if(s[i]=='.')break;
    }
    string zs=s.substr(l,i-l);
    string xs;
    if(i!=s.size())xs=s.substr(i+1);
    else xs="";
    //cout<
        //处理5-8位
        res+=numToCn(stoi(zs.substr(0,zs.size()-4)))+"万";
        //处理1-4位
        int low=stoi(zs.substr(zs.size()-4,4));
        //拼接
        if(low<1000&&low!=0)res+="零";
        res+=""+numToCn(low);
    }
    else{
        int low=stoi(zs.substr(zs.size()-4,4));//低四位
        int high;
        if(zs.size()==9)high=stoi(zs.substr(1,zs.size()-5));
        else high=stoi(zs.substr(2,zs.size()-6));
        if(low==0&&high==0)res+=numToCn(stoi(zs.substr(0,2)))+"亿";
        else{
            res+=numToCn(stoi(zs.substr(0,2)))+"亿";
            //处理5-8位
            if(high<1000){
                res+="零";
                if(high!=0)res+=numToCn(high)+"万";
            }
            else res+=numToCn(high)+"万";
            //处理1-4位
            if(low<1000&&low!=0&&high!=0)res+="零";
            res+=numToCn(low);
        }
    }
    if(xs!=""){
        res+="点";
        for(int i=0;i
            res+=shu[xs[i]-'0'];
        }
    }
    cout<