A-操作序列

题目描述

给出一个长度无限的数列，初始全部为零，有三种操作：

  • 增加操作：给下标为 tt 的数加 cc 。特别注意，如果在下标 [t−30,t+30][t-30,t+30] 内有不为零的数，增加操作无效。
  • 削减操作：让数列中下标最小的不为零数变为零。
  • 查询操作：查询数列中下标为 tt 的数字是多少。

输入描述

第一行包含一个整数 N,1≤N≤106N,1 \le N \le 10^6，表示操作总数。
随后 N 行，每行由两个数字或一个数字组成。
若一行中有两个数字，分别代表增加操作的$ t,c$ 。
若一行中只有数字−1-1，执行削减操作。
若一行中只有一个不为 −1-1的数字，则代表查询操作的数字 tt。
保证t，ct，c均为非负整数且在整形范围内。

输出描述

削减操作时，先输出该数字，再变为零。
若序列元素全为零，则削减操作无效，此时输出 “skipped”。
查询时，输出该位置上的数。

示例1

输入
7
140 1
120 2
100 3
120
100
−1-1
100
输出
0
3
3
0

示例2

输入
4
140 3
−1-1
140 1
−1-1
输出
3
1

示例3

输入
3
−1-1
−1-1
−1-1
输出
skipped
skipped
skipped

思路

这题看上去很吓人，实际上不用手写什么复杂的数据结构，熟练运用STL的map即可。

  • 增加操作：显得很鸡肋，发现只有[t−30,t+30][t-30,t+30]全部为0才能增加，所以实际的效果是在map中插入(t,c)(t,c)。
  • 削减操作：下标最小的不为0的数即为map的开头。如果全部为0，那么map就是空的。
  • 查询操作：直接使用find函数。

代码

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
#include<map>
#include<iostream>
using namespace std;
map<int,int>num;
map<int,int>::iterator it;
bool check(int t)
{
    if(num.find(t)!=num.end()) return false;
    else
    {
        int l=t,r=t;
        int T=30;
        while(T--)
        {
            l--;
            l=max(0,l);
            if(num.find(l)!=num.end()) return false;
            r++;
            r=min(0x7fffffff,r);
            if(num.find(r)!=num.end()) return false;
        }
    }
    return true;
}
void opt()
{
    int t;
    cin>>t;
    char sign;
    sign=getchar();    
    if(sign==' ')
    {
        int c;
        cin>>c;
        if(check(t)) num.insert(make_pair(t,c));
    }
    else
    {
        if(t==-1)
        {
            if(num.empty()) cout<<"skipped"<<endl;
            else
            {
                it=num.begin();
                cout<<it->second<<endl;
                num.erase(it);
            }
        }
        else
        {
            it=num.find(t);
            cout<<it->second<<endl;
        }
    }
    
}
int main()
{
    int N;
    cin>>N;
    while(N--) opt();
    return 0;
}

后记


可以看到map还是非常慢的，爬了快三秒。

B-树上子链

题目描述

给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。

输入描述

第一行输入一个 n,1≤n≤105n,1 \le n \le 10^5。
接下来一行包含nn个数，对于每个数 ai,−105≤ai≤105a_i, -10^5 \le a_i \le 10^5，表示 i 结点的权值。
接下来有n−1n-1行，每一行包含两个数u，v（1≤u,v≤n,u≠v）u，v（ 1 \le u,v \le n , u≠ v），表示uu与vv之间有一条边。

输出描述

仅包含一个数，表示我们所需要的答案。

示例1

输入
5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5
输出
4
说明
样例中最大子链为1 -> 2 -> 5

备注

一个结点，也可以称作一条链

思路

类似求树的直径，但是树的直径涉及的是边权，这里涉及的是点权，只需要把树形DP的转移方程修改一下。
假设一棵树有nn个节点，n−1n-1条边；令dp[u]dp[u]表示从节点uu出发，走向以uu为根的子树，能够到达的最远节点的距离，设uu的子节点为v1,v2,...,vtv_1,v_2,...,v_t；设经过节点uu的所有最长链的长度为F[u]F[u]，那么有ans=max⁡1⩽u⩽nF[u]ans = \mathop {\max }\limits_{1 \leqslant u \leqslant n} F[u];类似于树的直径，显然有

F[u]=max⁡1⩽i<j⩽tdp[vi]+dp[vj]+w[u]F[u] = \mathop {\max }\limits_{1 \leqslant i < j \leqslant t} dp[v_i] + dp[v_j] + w[u]

我们先用dp[u]+dp[vi]dp[u]+dp[v_i]更新F(u)F(u),再用dp[v]+w[u]dp[v]+w[u]更新dp[u]dp[u]即可。

代码

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
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int N=100009;
ll n,dp[N],w[N],cnt;
ll ans=-1e18;
vector<int>tree[N];//邻接矩阵存图
void dfs(int u,int father)
{
	dp[u]=w[u];
	int i,l=tree[u].size()-1;
	for(i=0;i<=l;i++)
	{
		int v=tree[u][i];
		if(v==father) continue;
		dfs(v,u);
		ans=max(ans,dp[u]+dp[v]);//更新F(u),直接存入ans
		dp[u]=max(dp[u],dp[v]+w[u]);//更新dp[u]
	}
    ans=max(dp[u],ans);//循环结束，最后一步更新的dp[u]漏下来了。
}
void solve()
{
	int x,y;
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>w[i];
	for(i=1;i<=n-1;i++)
	{
		cin>>x>>y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	dfs(1,0);
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
	return 0;
}

D-收集纸片

题目描述

我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。
假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。
你只能沿着 x 轴或 y 轴方向移动，从位置 (i,j) 移动到相邻位置 (i+1,j)，(i-1,j)，(i,j+1) 或 (i,j-1) 距离增加 1。

输入描述

在第一行中给出一个T,1≤T≤10T, 1 \le T \le 10, 代表测试数据的组数。
对于每组输入，在第一行中给出房间大小，第二行给出你的初始位置。
接下来给出一个正整数$ n,1 \le n \le 10$代表纸片的个数。
接下来 n 行，每行一个坐标代表纸片的位置。
保证房间小于 20×2020 \times 20，纸片一定位于房间内。

输出描述

对于每组输入，在一行中输出答案。
格式参见样例。

示例1

输入
1
10 10
1 1
4
2 3
5 5
9 4
6 5
输出
The shortest path has length 24

思路1

用DFS的方式遍历所有的情况，找出最小的那个。DFS的起点为(start,0,0)，从起点开始，搜索到的纸片为0，走过的步数为0。

代码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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int n,a,b;
struct node
{
    int x,y;
};
node paper[20],start;
int ans=1000000009;
bool vis[20];
void dfs(node now,int step,int cnt)
{
    if(cnt==n)
    {
        ans=min(ans,step+abs(now.x-start.x)+abs(now.y-start.y));
        return;
    }
    int i;
    for(i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(paper[i],step+abs(now.x-paper[i].x)+abs(now.y-paper[i].y),cnt+1);
            vis[i]=0;//回溯
        }
    }
}
void solve()
{
    int i;
    memset(vis,0,sizeof(vis));
    cin>>a>>b>>start.x>>start.y>>n;
    for(i=1;i<=n;i++) cin>>paper[i].x>>paper[i].y;
    dfs(start,0,0);
    printf("The shortest path has length %d\n",ans);
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

思路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
#include<iostream>
#include<algorithm>
using namespace std;
int a[10000];//用来排列纸片的顺序
const int N=15;
struct node
{
    int x,y;
}paper[N],start;
void solve()
{
    int i;
    for (i=0;i<=9999;i++) a[i]=i;
    int ans,ax,by,n;
    ans =1000000000;
    cin>>ax>>by>>start.x>>start.y>>n;
    for (i=1;i<=n;i++) cin>>paper[i].x>>paper[i].y;
    do
    {
        int res=abs(start.x-paper[a[1]].x)+abs(start.y-paper[a[1]].y);
        for (i=2;i<=n;i++)
        {
            res=res+abs(paper[a[i]].x-paper[a[i-1]].x)+abs(paper[a[i]].y-paper[a[i - 1]].y);
        }
        res+=abs(start.x-paper[a[n]].x)+abs(start.y-paper[a[n]].y);
        ans=min(ans,res);
    } while(next_permutation(a+1,a+1+n));
    cout<<"The shortest path has length "<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while (t--) solve();
    return 0;
}

E-方块涂色

题目描述

一块矩形区域被划分为了n行m列的小方格，初始情况下这些方格都是未被上色的。
为了使得矩形看起来不是单一的色彩，现在挑选出r行c列格子并将挑选出的格子上色。
请计算上色完成后，未上色格子的数目。

输入描述

多组输入
每组输入在一行中给出四个数字 n,m,r,cn, m, r, c，含义如题所示。
数据保证有 1≤n,m≤106,1≤r≤n,1≤c≤m1 \le n, m \le 10^6, 1 \le r \le n, 1 \le c \le m。

输出描述

每组输入输出一行代表答案。

示例1

输入
5 5 2 3
输出
6
说明

示例2

输入
3 2 2 1
2 4 2 4
输出
1
0

思路

选哪一行哪一列并无关系，这是很简单的容斥原理，观察样例的图就可得出结论。

代码

1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
int main()
{
	long long n,m,a,b;
	while(~scanf("%lld%lld%lld%lld",&n,&m,&a,&b))
	{
        printf("%lld",m*n-a*m-b*n+a*b);
		putchar('\n');
	}
	return 0;
}

F-累乘数字

题目描述

我们知道将一个大于1的数乘以另一个大于1的数会使乘积大于任意一个乘数。
现在给出两个数字 n,dn, d，你能否计算将nn乘以dd次100的结果。

输入描述

多组输入
每组输入在一行中给出$ n, d, 1 \le n, d \le 100n,d$。

输出描述

每组输入输出一行代表答案。

示例1

输入
5 1
11 1
85 2
输出
500
1100
850000

思路

每乘一个100，数字末尾就多两个0，用string模拟一下即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<string>
#include<iostream>
using namespace std;
int main()
{
	string n;
    int d;
	while(cin>>n>>d)
	{
		string t="00";
		while(d--)
		{
			n=n+t;
		}
		cout<<n<<endl;
	}
	return 0;
}

H-货物种类

题目描述

某电商平台有n个仓库，编号从1到n。
当购进某种货物的时候，商家会把货物分散的放在编号相邻的几个仓库中。
我们暂时不考虑售出，你是否能知道，当所有货物购买完毕，存放货物种类最多的仓库编号为多少？

输入描述

在第一行中给出两个正整数n,m,1≤n,m≤105n, m, 1\le n, m \le 10^5，分别代表仓库的数目和进货的次数。
接下来 m 行，每行三个正整数l,r,d,1≤l,r≤n,1≤d≤109l,r,d,1 \le l,r \le n, 1 \le d \le 10^9。编号在l和r之间的仓库收进编号为d的货物。

输出描述

在一行中输出存放货物种类最多的仓库编号，若满足条件的仓库不止一个，则输出编号最小的那个。

示例1

输入
5 5
1 1 1
3 3 1
2 5 2
5 5 1
4 5 1
输出
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
#include<iostream>
#include<map>
#include<vector>
using namespace std;
void solve()
{
    const int N=100007;
    int n,m;
    struct node
    {
        int l,r,d;
    }opt[N];
    vector<int>edge_add[N];
    vector<int>edge_erase[N];
    map<int,int>vis;
	cin>>n>>m;
	int i;
	for(i=1;i<=m;i++)
	{
		cin>>opt[i].l>>opt[i].r>>opt[i].d;
        //差分添加
		edge_add[opt[i].l].push_back(opt[i].d);
		edge_erase[opt[i].r+1].push_back(opt[i].d);
	}
	int cnt=0,ans=0;
	int maxx=-1;
	int j;
	for(i=1;i<=n;i++)
	{
		int len;
		len=edge_add[i].size();
		//左区间加
		for(j=0;j<len;j++)
		{
		//如果vis[]这种商品没有出现过的话,该点商品种类数增加。
			if(!vis[edge_add[i][j]]) cnt++;
			vis[edge_add[i][j]]++;
		}
		len=edge_erase[i].size();
		//右区间减
		for(j=0;j<len;j++)
		{
			vis[edge_erase[i][j]]--;
			if(!vis[edge_erase[i][j]]) cnt--;
		}
		if(cnt>maxx)
		{
			maxx=cnt;
			ans=i;//记录位置，由于从1开始遍历，得到的答案必定是最小值。
		}
	}
	cout<<ans;
}
int main()
{
	solve();
	return 0;
}

J-计算A+B

题目描述

在一行中给出一个字符串，请判断是否满足A + B格式，如果满足，输出计算结果，否则输出"skipped"。
此处A,B均为大于等于0的整数，保证数据没有前导零。

输入描述

第一行输入一个n, 1≤n≤1000n1 \le n \le 1000n,代表测试数据的组数。
接下来nn行，每行输入一个长度不超过10000的字符串。

输出描述

对于每组输出，输出结果。

示例1

输入
4
2+2
1+2
+12
0+0
输出
4
3
skipped
0

思路

不合法有两种情况：①加号不止一个或没有；②有一个加号，位置不对。
对于合法的算式，取加号两边的数，套一下BigInteger板子。

代码

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
#include<string>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
struct BigInteger
{
    static const int BASE=100000000; //和WIDTH保持一致
    static const int WIDTH=8;//八位一存储,如修改记得修改输出中的%08d
    bool sign;//符号, 0表示负数
    size_t length;//位数
    vector<int> num;//反序存
    //构造函数
    BigInteger(long long x=0) 
	{ 
		*this=x;
	}
    BigInteger(const string &x) 
	{
	 	*this=x; 
	}
    BigInteger(const BigInteger &x) 
	{ 
		*this=x; 
	}
    //剪掉前导0，并且求一下数的位数
    void cutLeadingZero()
    {
        while(num.back()==0&&num.size()!=1)
        {
            num.pop_back();
        }
        int tmp=num.back();
        if(tmp==0) length=1;
        else
        {
            length=(num.size()-1)*WIDTH;
            while(tmp>0)
            {
                length++;
                tmp/=10;
            }
        }
    }
    //赋值运算符
    BigInteger &operator=(long long x)
    {
        num.clear();
        if(x>=0) sign=true;
        else
        {
            sign=false;
            x=-x;
        }
        do
        {
            num.push_back(x%BASE);
            x/=BASE;
        }while(x>0);
        cutLeadingZero();
        return *this;
    }
    BigInteger &operator=(const string &str)
    {
        num.clear();
        sign=(str[0]!='-'); //设置符号
        int x,len=(str.size()-1-(!sign))/WIDTH+1;
        for(int i=0;i<len;i++)
        {
            int End=str.size()-i*WIDTH;
            int start=max((int)(!sign),End-WIDTH); //防止越界
            sscanf(str.substr(start,End-start).c_str(),"%d",&x);
            num.push_back(x);
        }
        cutLeadingZero();
        return *this;
    }
    BigInteger &operator=(const BigInteger &tmp)
    {
        num=tmp.num;
        sign=tmp.sign;
        length=tmp.length;
        return *this;
    }
    //绝对值
    BigInteger abs() const
    {
        BigInteger ans(*this);
        ans.sign=true;
        return ans;
    }
    //正号
    const BigInteger &operator+() const 
	{
	 	return *this; 	
	}
    //负号
    BigInteger operator-() const
    {
        BigInteger ans(*this);
        if (ans!=0) ans.sign=!ans.sign;           
        return ans;
    }
    // + 运算符
    BigInteger operator+(const BigInteger &b) const
    {
        if(!b.sign)
        {
            return *this-(-b);
        }
        if(!sign)
        {
            return b-(-*this);
        }
        BigInteger ans;
        ans.num.clear();
        for(int i=0,g=0;;i++)
        {
            if(g==0&&i>=num.size()&&i>=b.num.size()) break;              
            int x=g;
            if(i<num.size()) x+=num[i];               
            if(i<b.num.size()) x+=b.num[i];               
            ans.num.push_back(x%BASE);
            g=x/BASE;
        }
        ans.cutLeadingZero();
        return ans;
    }
    // - 运算符
    BigInteger operator-(const BigInteger &b) const
    {
        if(!b.sign)
        {
            return *this+(-b);
        }
        if(!sign)
        {
            return -((-*this)+b);
        }
        if(*this<b)
        {
            return -(b-*this);
        }
        BigInteger ans;
        ans.num.clear();
        for(int i=0,g=0;;i++)
        {
            if (g==0&&i>=num.size()&&i>=b.num.size()) break;             
            int x=g;
            g=0;
            if(i<num.size())
                x+=num[i];
            if(i<b.num.size())
                x-=b.num[i];
            if (x<0)
            {
                x+=BASE;
                g=-1;
            }
            ans.num.push_back(x);
        }
        ans.cutLeadingZero();
        return ans;
    }
    // * 运算符
    BigInteger operator*(const BigInteger &b) const
    {
        int lena=num.size(),lenb=b.num.size();
        BigInteger ans;
        for(int i=0;i<lena+lenb;i++) ans.num.push_back(0);          
        for (int i=0,g=0;i<lena;i++)
        {
            g=0;
            for (int j=0;j<lenb;j++)
            {
                long long x=ans.num[i+j];
                x+=(long long)num[i]*(long long)b.num[j];
                ans.num[i+j]=x%BASE;
                g=x/BASE;
                ans.num[i+j+1]+=g;
            }
        }
        ans.cutLeadingZero();
        ans.sign=(ans.length==1&&ans.num[0]==0)||(sign==b.sign);
        return ans;
    }
    //*10^n 大数除大数中用到
    BigInteger e(size_t n) const
    {
        int tmp=n%WIDTH;
        BigInteger ans;
        ans.length=n+1;
        n/=WIDTH;
        while(ans.num.size()<=n) ans.num.push_back(0);           
        ans.num[n]=1;
        while(tmp--) ans.num[n]*=10;           
        return ans*(*this);
    }
    // /运算符 (大数除大数)
    BigInteger operator/(const BigInteger &b) const
    {
        BigInteger aa((*this).abs());
        BigInteger bb(b.abs());
        if (aa<bb) return 0;            
        char *str=new char[aa.length+1];
        memset(str,0,sizeof(char)*(aa.length+1));
        BigInteger tmp;
        int lena=aa.length,lenb=bb.length;
        for (int i=0;i<= lena-lenb;i++)
        {
            tmp=bb.e(lena-lenb-i);
            while(aa>=tmp)
            {
                str[i]++;
                aa=aa-tmp;
            }
            str[i]+='0';
        }
        BigInteger ans(str);
        delete[] str;
        ans.sign=(ans==0||sign==b.sign);
        return ans;
    }
    // %运算符
    BigInteger operator%(const BigInteger &b) const
    {
        return *this-*this/b*b;
    }
    // ++ 运算符
    BigInteger &operator++()
    {
        *this=*this+1;
        return *this;
    }
    // -- 运算符
    BigInteger &operator--()
    {
        *this=*this-1;
        return *this;
    }
    // += 运算符
    BigInteger &operator+=(const BigInteger &b)
    {
        *this=*this+b;
        return *this;
    }
    // -= 运算符
    BigInteger &operator-=(const BigInteger &b)
    {
        *this=*this-b;
        return *this;
    }
    // *=运算符
    BigInteger &operator*=(const BigInteger &b)
    {
        *this=*this*b;
        return *this;
    }
    // /= 运算符
    BigInteger &operator/=(const BigInteger &b)
    {
        *this=*this/b;
        return *this;
    }
    // %=运算符
    BigInteger &operator%=(const BigInteger &b)
    {
        *this=*this % b;
        return *this;
    }
    // < 运算符
    bool operator<(const BigInteger &b) const
    {
        if(sign!=b.sign) //正负，负正
        {
            return !sign;
        }
        else if(!sign&&!b.sign) //负负
        {
            return -b<-*this;
        }
        //正正
        if (num.size()!=b.num.size())
            return num.size()<b.num.size();
        for (int i=num.size()-1;i>=0;i--)
        {
        	if (num[i]!=b.num[i]) return num[i]<b.num[i];               
		}           
        return false;
    }
    bool operator>(const BigInteger &b) const 
	{
	 	return b<*this;
	}                     // >  运算符
    bool operator<=(const BigInteger &b) const 
	{ 
		return !(b<*this); 
	}                 // <= 运算符
    bool operator>=(const BigInteger &b) const 
	{ 
		return !(*this<b); 
	}                 // >= 运算符
    bool operator!=(const BigInteger &b) const 
	{
	 	return b<*this||*this<b; 
	}       // != 运算符
    bool operator==(const BigInteger &b) const 
	{
		 return !(b<*this)&&!(*this<b); 
	} //==运算符
    // 逻辑运算符
    bool operator||(const BigInteger &b) const 
	{
	 	return *this!=0||b!=0;
	} // || 运算符
    bool operator&&(const BigInteger &b) const 
	{
	 	return *this!=0&&b!=0; 
	} // && 运算符
    bool operator!() 
	{
	 	return (bool)(*this==0); 
	}// ！ 运算符 
    //重载<<使得可以直接输出大数
    friend ostream &operator<<(ostream &out,const BigInteger &x)
    {
        if (!x.sign) out<<'-';           
        out<<x.num.back();
        for (int i=x.num.size()-2;i>=0;i--)
        {
            char buf[10];
            //如WIDTH和BASR有变化,此处要修改为%0(WIDTH)d
            sprintf(buf,"%08d",x.num[i]);
            for (int j=0;j<strlen(buf);j++) out<<buf[j];               
        }
        return out;
    }
    //重载>>使得可以直接输入大数
    friend istream &operator>>(istream &in,BigInteger &x)
    {
        string str;
        in>>str;
        size_t len=str.size();
        int start=0;
        if (str[0]=='-') start=1;           
        if (str[start]=='\0') return in;           
        for (int i=start;i<len;i++)
        {
            if (str[i]<'0'||str[i]>'9') return in;                
        }
        x.sign=!start;
        x=str.c_str();
        return in;
    }
};
void solve()
{
	string s;
	cin>>s;
	int i;
	int l=s.size()-1;
	int cnt=0;
	int p;
	bool flag=1;
	for(i=0;i<=l;i++)
	{
		if(s[i]=='+') 
		{
			p=i;
			cnt++;
		}
	}
	if(cnt!=1) cout<<"skipped"<<endl;
	else
	{	
		if(s[0]=='+'||s[l]=='+')cout<<"skipped"<<endl;
		else
		{
			string a="";
			string b="";
			for(i=0;i<p;i++) a=a+s[i];
			for(i=p+1;i<=l;i++) b=b+s[i];
			BigInteger ans=0;
			ans=BigInteger(a)+BigInteger(b);
			cout<<ans<<endl;
		}	
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
}