[原创]2016级新生程序设计全国邀请赛个人题解 [未完待续…]

2016-11-29 21:58:33 Tabris_ 阅读数：476

博客爬取于2020-06-14 22:42:33
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53400832

首先作为大二选手,做新生的题目就很尴尬了，然后3个小时单挑(6)加补题(2)，最后也只能8个题也是菜的可以。
外加膜拜一发rank1的新生队伍，Orz。。

棋盘村

从(0,0)走到(n,m)很好办 直接dp一下就能计算出来
因为不能路过强盗的位置和强盗一步就能走到的位置.所以这几个位置要特殊判断一下即可.

转移方程
dp[i][j]=dp[i−1][j]+dp[i][j−1];dp[i][j]=dp[i-1][j]+dp[i][j-1];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;
/*******************************/

const int mod = 1e9+7;
const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);


LL dp[30][30];
bool vis[30][30];
int fx[]={0,1,1,-1,-1,2,2,-2,-2};
int fy[]={0,2,-2,2,-2,1,-1,1,-1};
int main ()
{
    int n,m,x,y;
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            s1(n),s1(m),s1(x),s1(y);
            int xx,yy;
            memset(dp,0,sizeof(dp));
            memset(vis,0,sizeof(vis));
            vis[0][0]=1;
            Rep(i,0,8)
            {
                xx=x+fx[i];
                yy=y+fy[i];
                if(xx>=0&&yy>=0&&xx<=n&&yy<=m)
                    vis[xx][yy]=1;
            }
            dp[0][0]=1;
            Rep(i,0,n)Rep(j,0,m)
            {
                if(vis[i][j]) continue;
                if(i-1>=0) dp[i][j]+=dp[i-1][j];
                if(j-1>=0) dp[i][j]+=dp[i][j-1];
            }
            printf("%lld\n",dp[n][m]);
        }
    }
    return 0;
}

---------------------------------------------------------------------------------.

修建传送门

这道题首先看到了最小的最大值,我就想二分答案做,但是check部分想了好久也写不出来,于是放弃这个思路.

想了一下最暴力的思路
要枚举三个位置——两个传送阵+1个折中点的位置
在枚举过程中维护的就是几个距离的最大值即可
1)min_dis(1,n)
2)min_dis(1,折中点)
3)min_dis(1,折中点左边的位置) （通过传送阵之后的）

维护过程我们可以先处理个前缀和 这样的话就能O(1)O(1)维护了.

然而发现O(n3)O(n^3)的复杂度根本不可行

然后我们发现我们需要的距离一定是从11到其他点的 ，那么我们可以确定，其中一个传送阵一定要放在11位置上,否则的话最小的最大长度就是就会多了dis(1,左边的传送阵).
这样的话复杂度就降到了O(n2)O(n^2)
但是发现还是不够用

首先我们能够确定的是 一定要枚举一个值,
那么我们考虑是枚举第二个传送阵还是枚举折中的点…
发现如果开始就枚举折中的点的话,那么不好找传送阵.
于是决定枚举传送阵.

发现,如果枚举传送阵,那么我能能够利用双指针法的方式确定折中点.
这样的话复杂度就降到了O(n)O(n)

问题就解决了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
/***********************************************************************/

LL a[N],sum[N];
int n;
int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            s1(n);

            sum[0]=0;
            LL mi = 0;
            Rep(i,1,n-1)s1(a[i]),mi+=a[i],sum[i]=sum[i-1]+a[i];
            int l,r;
            l=1,r=2;
            //尺取法的思想  r枚举传送阵 l枚举折点
            //3个距离就是 1->l  r->l+1  r->n-1
            LL tem = mi ;
            while(r<=n)
            {
                while(l<r && sum[r-1]-sum[l] > sum[l] )l++;
                tem = max(sum[l-1],sum[r-1]-sum[l]);
                tem = max(tem,sum[n-1]-sum[r-1]);
                if(tem<mi) mi=tem;
                //printf("%d %d  <-%d\n",l,r,tem);
                r++;
            }
            printf("%lld\n",mi);
        }
    }
    return 0;
}

---------------------------------------------------------------------------------.

方方正正

这道题个人对最终的结果的证明是不太够的,但是也怼过去了…
其实就是来判断3个情况,
1.行和列的和是不是相等,不是的话那么一定不可能.
2.然后判断的是行的最大值和列上的非0值能不能对上,如果对不上的话那么也是不可能的.
3.同上，就是把行列交换一下,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;
/*******************************/

const int mod = 1e9+7;
const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);

int main()
{
    int r,c;
    while(~s1(r))
    {
        s1(c);
        LL t,sr,sc,nr,nc,mr,mc;
        sr=sc=nr=nc=mr=mc=0;
        Rep(i,1,r)
        {
            scanf("%lld",&t);
            if(t>0) nr++;
            sr+=t;
            if(t>mr) mr = t;
        }
        Rep(i,1,c)
        {
            scanf("%lld",&t);
            if(t>0) nc++;
            sc+=t;
            if(t>mc) mc = t;
        }
       // printf("%lld %lld %lld %lld\n",nr,mr,nc,mc);
        if(sr!=sc||nr<mc||nc<mr)
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}

---------------------------------------------------------------------------------.

陈月亮的数学题

这道题目粗看很难 但是想一想其实还是能做的
首先对于n1+n2+n3+…+nkn_1+ n_2+ n_3+ …+ n_k 还是非常好求的
我们想到将N按照算数基本定理展开变成
N=p1a1∗p2a2∗p3a3∗…∗pnanN= p_1^{a_1}* p_2^{a_2}* p_3^{a_3}*…* p_n^{a_n}
这时候我们有N的因子个数为(a1+1)(a2+1)(a3+1)…(ak+1)(a_1+1) (a_2+1) (a_3+1)…(a_k+1) = $\prod_{i=1}^{k}(a_i+1) $

这时候我考虑某一个N的因子也就是将a1a_1变成x∈[0,a1]x∈[0,a_1]
那么最终N的所有因子的因子个数和就是
∏i=1k(1+2+3+…+ai+1)\prod_{i=1}^{k}(1+2+3+…+a_i+1) = $\prod_{i=1}^{k}\frac{(1+a_i+1)(a_i+1)}{2} $

但是说了半天我们计算的只是S=n1+n2+n3+…+nkS= n_1+ n_2+ n_3+ …+ n_k的值
那么我对于S=n13+n23+n33+…+nk3S= n_1^3+ n_2^3+ n_3^3+ …+ n_k^3该如何求解呢

首先我们知道这样三个数列的前n项和
1+2+3+…+n=(1+n)n21+2+3+…+n= \frac{(1+n)n}{2}
12+22+32+…+n2=(2+n)(1+n)n61^2+2^2+3^2+…+n^2 = {\frac{(2+n)(1+n)n}{6} }
$ 1^3+ 2^3+ 3^3+ …+ n^3 = {(\frac{(1+n)n}{2})}^2$
…

证明过程从略.(方法好像叫列项相消…

然后我们发现其中两项很相像,
通过观察法发现,与题目要求的有很强的对应关系,那么结论也会有很强的对应关系,
所以得出结论 , 我们只要求出∏i=1k((1+ai)ai2)2\prod_{i=1}^{k}{(\frac{(1+a_i)a_i}{2})}^2即可,事实发现可行,于是AC…

但是我们需要怎么才能证明得出呢?
考虑到N只有一个素因子的时候,那么他的因子的因子个数和就是
1+2+3+…+ai=∑i=1aii=(1+ai)ai21+2+3+…+ a_i=\sum_{i=1}^{a_i}i= {\frac{(1+a_i)a_i}{2} }
=>S(N)=13+23+33+…+ai3=∑i=1aii3=((1+ai)ai2)2S(N) =1^3+ 2^3+ 3^3+ …+ a_i^3=\sum_{i=1}^{a_i}i^3= {(\frac{(1+a_i)a_i}{2})}^2
那么对于N有2个素因子的时候他的因子的因子个数和就是
(1+2+3+…+a1)(1+2+3+…+a2)=∑i=1ai(i∑j=1ajj)=((1+a1)a12)((1+a2)a22)(1+2+3+…+ a_1)( 1+2+3+…+ a_2) =\sum_{i=1}^{a_i}(i\sum_{j=1}^{a_j}j)= (\frac{(1+a_1)a_1}{2})( \frac{(1+a_2)a_2}{2})
=>S(N)=(13+23+33+…+a13)(13+23+33+…+a23)=∑i=1ai(i3∑j=1ajj3)=((1+a1)a12)2((1+a2)a22)2S(N)= (1^3+ 2^3+ 3^3+ …+ a_1^3) (1^3+ 2^3+ 3^3+ …+ a_2^3)=\sum_{i=1}^{a_i}(i^3\sum_{j=1}^{a_j}j^3)={(\frac{(1+a_1)a_1}{2})}^2{(\frac{(1+a_2)a_2}{2})}^2
然后采用数学归纳法，即可得出对于N有多个素因子的时候
=>∏i=1k((1+ai)ai2)2\prod_{i=1}^{k}{(\frac{(1+a_i)a_i}{2})}^2

最后一句 ,以后再也不想证明数学题了,尼玛墨迹死了，还这么绕….

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;
/*******************************/

const int mod = 1e9+7;
const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);

int prime[N],kp;
bool Is_or[N];
void Prime()
{
    int n = 65540;
    kp=0;
    memset(Is_or,true,sizeof(Is_or));
    Is_or[0]=Is_or[1]=false;
    for(int i=2;i<n;i++)
    {
        if(Is_or[i]) prime[kp++]=i;
        for(int j=0;j<kp&&prime[j]*i<n;j++)
        {
            Is_or[prime[j]*i]=false;
            if(i%prime[j]==0) break;
        }
    }
    return ;
}
vector<int>a;
int main()
{
    Prime();
    int _,n;
    while(~s1(_))
    {
        while(_--)
        {
            a.clear();
            s1(n);
            int cnt;
            for(int i=0;i<kp&&n>=prime[i]*prime[i];i++)
            {
                cnt=0;
                while(n%prime[i]==0) cnt++,n/=prime[i];
                a.pb(cnt);
            }
            if(n>1)   a.pb(1);
            LL ans = 1,tmp;
            for(int i=0;i<a.size();i++)
            {
                tmp = (a[i]+1)*(a[i]+2)/2;
                ans*=tmp*tmp;
            }
            printf("%lld\n",ans);
        }
    }

    return 0;
}

---------------------------------------------------------------------------------.

Nine Digits

这道题目其实和HDU1430是一样的
这里有我HDU1430的题解.传送阵

本题问的是从1~9这个原序列到达其他序列的最少旋转次数，那么翻过来也就是从给定的某一个序列到达1~9这个原序列的最少旋转次数。因为9！==3628809！==362880 我们只要预处理出所有的情况就行了。

这道题目要求得最少次数，很容易想到BFS
然后根据题目的1~9的全排列，显然就是康拓展开。
利用康拓展开值来确定一个序列。

每一次BFS的过程中，向其旋转一个2*2后的序列一遍一遍的搜索就行了。（！！！注意的是 从当前序列到原序列是顺时针旋转的，那么从原序列过来就是逆时针的 ，否则 虽然还是能过掉挺多数据，那也是WA啊。。别问我怎么知道能过掉很多数据的 /哭笑）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
/***********************************************************************/

int step[363333];
int jiecheng[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int a[10],b[10];

int Cantor_expansion(int a[])
{
    //Rep(i,0,8)printf("%c%d",(i%3==0)?'\n':' ',a[i]);puts("");

    int x=0,len = 9 ;
    for(int i=0; i<len; i++)
    {
        for(int j=i+1; j<len; j++)
            if(a[j]<a[i])
                x+=jiecheng[len-1-i];
    }
    return x ;
}

bool h[10];
void Cantor_inexpansion(int x)
{
    memset(h,0,sizeof(h));
    int ind ,tem ,len = 9;
    for(int i=0; i<len; i++)
    {
        ind = 0;
        tem = x/jiecheng[len-1-i];
        x  %=   jiecheng[len-1-i];
        for(int j=1; j<=len; j++)
        {
            if(h[j]) continue;
            if(ind==tem)
            {
                a[i]=j;
                break;
            }
            ind++;
        }
        h[a[i]]=1;
    }
    //Rep(i,0,8)printf("%d%c",a[i],(i==8)?'\n':' ');

    return ;
}

int opera(int ind)
{
    Rep(i,0,8) b[i]=a[i];
    int temp;
    if(ind==1)
        temp=b[0],b[0]=b[1],b[1]=b[4],b[4]=b[3],b[3]=temp;
    else if(ind==2)
        temp=b[1],b[1]=b[2],b[2]=b[5],b[5]=b[4],b[4]=temp;
    else if(ind==3)
        temp=b[3],b[3]=b[4],b[4]=b[7],b[7]=b[6],b[6]=temp;
    else if(ind==4)
        temp=b[4],b[4]=b[5],b[5]=b[8],b[8]=b[7],b[7]=temp;

    return Cantor_expansion(b);
}

void BFS()
{
    memset(step,-1,sizeof(step));
    queue<int>q;
    int xx[10]= {1,2,3,4,5,6,7,8,9};
    int x = Cantor_expansion(xx);
    step[x]=0;
    q.push(x);
    int tem,tmp;
    while(!q.empty())
    {
        tem = q.front(),q.pop();
        Cantor_inexpansion(tem);
        for(int i=1;i<=4;i++)
        {
            tmp = opera(i);
            if(step[tmp]!=-1) continue;
            step[tmp] = step[tem] + 1 ;
            q.push(tmp) ;
        }
    }
    return ;
}

int main()
{
    BFS();
    while(~s1(a[0]))
    {
        Rep(i,1,8) s1(a[i]);
        int x = Cantor_expansion(a);
        printf("%d\n",step[x]);
    }
    return 0;
}

---------------------------------------------------------------------------------.

Diamond

不会…
---------------------------------------------------------------------------------.

FBI Tree

这道题 据说不知道什么是后序遍历的16级同学暴力就过了
但是我这里真不知道怎么暴力 ,于是就模拟了一下题意,建了一颗二叉树,然后后序遍历了一下.(话树写的好糙啊但最后也怼过去了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;
/*******************************/

const int mod = 1e9+7;
const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);

int tree[1<<16],n;
char a[1<<16];
# define ll (rt<<1)
# define rr (rt<<1|1)
# define mid ((l+r)>>1)
void pushup(int rt)
{
    if(tree[ll]==3||tree[rr]==3)tree[rt]=3;
    else if(tree[ll]==1&&tree[rr]==1)tree[rt]=1;
    else if(tree[ll]==1&&tree[rr]==2)tree[rt]=3;
    else if(tree[ll]==2&&tree[rr]==1)tree[rt]=3;
    else if(tree[ll]==2&&tree[rr]==2)tree[rt]=2;
}

void build(int rt,int l,int r)
{
    if(l==r)
    {
        tree[rt]=a[l]-'0'+1;
        return ;
    }
    build(ll,l,mid);
    build(rr,mid+1,r);
    pushup(rt);
}
int ans;
void visit(int rt)
{
   // printf("%d",rt);
    ans++;
    if(ans>=(1<<(n+1))) return;
    if(tree[rt]==1)        printf("B");
    else if(tree[rt]==2)   printf("I");
    else if(tree[rt]==3)   printf("F");
    else printf("*");
}

void dfs(int rt,int l,int r)
{
    if(l==r);
    else
    {
        dfs(ll,l,mid);
        dfs(rr,mid+1,r);
    }
    visit(rt);
    return ;
}

int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            ans = 0;
            s1(n);
            scanf("%s",a+1);
            build(1,1,(1<<(n+1))-1);

            dfs  (1,1,(1<<(n+1))-1);
            //printf("%d\n",(1<<(n+1))-1);
            puts("");
            //printf("%d\n",ans);
        }
    }
    return 0;
}

---------------------------------------------------------------------------------.

下雪啦

没有想好怎么hash 待补题…
---------------------------------------------------------------------------------.

行编辑器

水题一个,没有什么好说的,随便做就行了
可以双端队列,
但是时效性最好的还是用数组做,用一个"指针"维护一下就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;
/*******************************/

const int mod = 1e9+7;
const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);


char ch[1010101];
char  a[1010101];
int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            scanf("%s",ch);
            int len = strlen (ch);
            int pos=0;
            Rep(i,0,len-1)
            {
                if(ch[i]=='#')
                {
                    pos--;
                    if(pos<0) pos=1;
                }
                else if(ch[i]=='@')
                {
                    pos=0;
                }
                else
                {
                    a[pos++]=ch[i];
                }
            }
            Rep(i,0,pos-1)
            printf("%c",a[i]);
            puts("");
        }
    }
    return 0;
}

---------------------------------------------------------------------------------.

Another Tree

这题不会。
---------------------------------------------------------------------------------.

小明和字符串

简单模拟，没有什么好说的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;
/*******************************/

const int mod = 1e9+7;
const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);


char a[10101];
int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            scanf("%s",&a);
            int len = strlen (a);
            char ch,num=0;
            Rep(i,0,len-1)
            {
                if(a[i]>='0'&&a[i]<='9')
                {
                    num+=a[i]-'0';
                }
                else
                {
                    while(num--)printf("%c",ch);
                    num=0;
                    printf("%c",a[i]);
                    ch=a[i];
                }
            }
            while(num--)printf("%c",ch);
            puts("");
        }
    }
    return 0;
}

---------------------------------------------------------------------------------.