Day22

Day22

有是一次积分赛
有是自闭的一天
补题

wzy的大冒险——出发前的清理

Description:

由于上次学弟们没有ak,导致许多蚂蚁被留下了。wzy在出发冒险前请来了一只食蚁兽帮忙清理。
现在出现了一只食蚁兽。每个蚂蚁都有wzy给它的一个编号,食蚁兽要吃蚂蚁必须要确认蚂蚁的编号X是否满足要求,如下:

X的质因子的种类不超过13种
X的食蚁数是个素数(食蚁数的定义见最下方提示)
X的食蚁数是个回文数
如果都满足则输出 YES ,否则输出 NO

输入格式
第一行给定一个T,(1≤T≤1e5)
接下来T行,每行给出数字X,(1≤X≤1e17)

输出格式
每行输出 YES 或者 NO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
样例
input
3
121666
111666
1312333
output
NO
NO
YES
提示
补充:
1. 回文数至少为两位数,如 13122
2. 如果X的长度为 len1 ,令 len2=⌊len1/2⌋,则 X 的前 len2 位形成的数是它的食蚁数

code:

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
//打表做法
//借用别人的代码
#include <bits/stdc++.h>
#define PI acos(-1)
const int NN = 777;
typedef long long ll;
using namespace std;

int prime[NN] = {
11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,
10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,
16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,
34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,
71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,
79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,
97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,
1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,
1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,
1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,
1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,
1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,
1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,
1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,
1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,
1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,
1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,
1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,
1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,
1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,
3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,
3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,
3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,
3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,
3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,
3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,
3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,
3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,
3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,
3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,
3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,
3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,
3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,
7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,
7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,
7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,
7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,
7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,
7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,
7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,
7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,
7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,
7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,
7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,
9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,
9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,
9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,
9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,
9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,
9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,
9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,
9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,
9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,
9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};

bool isprime(ll N){
string str = std::to_string(N);
ll n = 0;
for(int i = 0;i<str.size()/2;i++){
n = n*10+(str[i]-'0');
}
if(n == 1||n ==0) return false;
int t = lower_bound(prime,prime+NN,n)-prime;
if(t == NN) return false;
if(prime[t] == n) return true;
return false;
}


ll ksm(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res*a;
a = a*a;
b<<=1;
}
return res;
}


bool divide(ll x){
int coun = 0;
for(int i = 2;i<=x/i && i<=100;i++){
if(x%i ==0 ){
while(x%i ==0) x/=i;
coun++;
if(coun>13) return false;
}
}
return true;
}


int main(){
ll T,N;
cin>>T;
while(T--){
scanf("%lld",&N);
if(!isprime(N)){
cout<<"NO"<<endl;
continue;
}
if(!divide(N)){
cout<<"NO"<<endl;
continue;
}
cout<<"YES"<<endl;
}
return 0;
}


//非打表做法
//#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 1e7+7;

int prime[MAXN];
int visit[MAXN];
void Prime(){ //网上随便找了个素筛板子,好像visit[i]==0表示素数(为什么两个数组不反过来用
memset(visit,0, sizeof(visit));
memset(prime, 0, sizeof(prime));
for (int i = 2;i <= MAXN; i++) {
// cout<<" i = "<<i<<endl;
if (!visit[i]) {
prime[++prime[0]] = i; //纪录素数, 这个prime[0] 相当于 cnt,用来计数
}
for (int j = 1; j <=prime[0] && i*prime[j] <= MAXN; j++) {
visit[i*prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
}
}
}

char s[20];
char w[20];

int main()
{
// ll q;
// q = 2*3*5*7*11*13;
// q = q*17* 19* 23*29*31*37*41; //13:304250263527210 14:13082761331670030
Prime();
int i, k, flag, n;
ll a, b;
int t;
cin>>t;
while(t--)
{
scanf("%lld", &a);
if(a<=1000) //食蚁数长度在两位及以上,所以a的长度在四位及以上
{
printf("NO\n");
continue;
}
b = a;
k = 0;
flag = 1;
while(b) //统计a的长度并且转换为字符串
{
s[k++] = b%10;
b/=10;
}
n = k; //长度
if(n>=16) //a长度为1617位,食蚁数长度为8位;或者a==100000000000000000,食蚁数==100000000
{
printf("NO\n");
continue;
}
for(i=0; i<k/2; i++) //取食蚁数字符串
w[i] = s[k-i-1];
k/=2; //k为食蚁数位数
if(!(k%2)) //一个回文数如果位数为偶数位那么它一定不是素数(11除外)
{
if(a/100==11 || a/1000==11) printf("YES\n");
else printf("NO\n");
continue;
}
for(i=0; i<k/2; i++) //检查回文串
{
if(w[i] != w[k-i-1])
{
flag = 0;
break;
}
}

n = a/pow(10, n-k);
if(flag && !visit[n]) printf("YES\n");
else printf("NO\n");
}

return 0;
}

wzy的大冒险——出发咯QAQ

Description:
wzy踏上了冒险的旅程。
现在他从地精手里买了一份地图,地图上有n个城镇。
他从第一个城镇出发,走向(没钱只能走)第n个城镇,现在,请你帮wzy找到一条最短的路径,并倒序(从n到1)输出一条最短路径。
举个栗子:如果有两条路径6 4 3 1和6 5 2 1,我们选择6 4 3 1这条。
地精小提示:路是单向的QAQ。

输入格式
第一行两个数n,m ,(1≤n≤10^3,1≤m≤10^3)

接下来m行,每行三个数x,y,z,表示点 x 与点 y 之间有一条权值为 z 的有向边 (1≤x,y,z≤10^3).

输出格式
第一行一个整数表示 1 到 n 的最短距离;
第二行倒序输出这条路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
样例
input
5 7
1 2 69
1 3 87
1 4 79
2 5 94
2 3 10
3 5 79
4 5 43
output
122
5 4 1

code:

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>
using namespace std;
const int maxn=1e3+10;
const int INF=0x3f3f3f3f;
int a[maxn][maxn],dis[maxn],f[maxn];
bool vis[maxn];
int n,m,u,v,w;
struct node{
int d,id;
bool friend operator < (node a,node b)
{
return a.d > b.d;
}
};

priority_queue<node> q;
void solve()
{
for(int i=1;i<=n;i++) dis[i]=INF;
dis[1]=0;
q.push(node{dis[1],1});
while(!q.empty())
{
node p=q.top();
q.pop();
int mid=p.id;
if(vis[mid]==1) continue;
vis[mid]=1;
for(int i=1;i<=n;i++)
{
if(dis[i]>dis[mid]+a[mid][i])
{
dis[i]=dis[mid]+a[mid][i];
f[i]=mid;//这就是记录路径所用到的数组
q.push(node{dis[i],i});
}
}
}
cout<<dis[n]<<endl;
}
int main()
{
cin>>n>>m;
f[1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) a[i][j]=INF;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
a[u][v]=w;
}
solve();
cout<<n<<" ";
while(f[n]!=n)//输出最短路径所用到的查找
{
cout<<f[n]<<" ";
n=f[n];
}
}

wzy的大冒险——数学王国

Description:
wzy这一次来到了数学王国,加号国王为了考验他,找来了一个数字n,告诉了wzy这个数字的阶乘的末尾零的个数Q,猜错的话就要把wzy赶出去。现在请你帮帮wzy求这个数最小为多少。
若不存在输出”impossible”(输出不带引号)。

输入格式
输入数据包含T组(1≤T≤10000)
每一组数据包含一个数字Q (0≤Q≤10^8)

输出格式
对于每一组数据请输出这个数字n,否则输出”impossible”(输出不带引号)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
样例
input
3
1
2
5
output
5
10
impossible
input
1
10000000
output
40000010

code:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e9;
int solve(ll x)
{
ll ans = 0;
while(x)
{
ans = ans + (x / 5);
x = x / 5;
}
return ans;
}

int er_fen(ll n)
{
ll l = 0, r = maxx;
ll mid;
while(l <= r)
{
mid = l + r;
if(solve(mid / 2) >= n)
r = mid / 2 - 1;
else
l = mid / 2 + 1;
}
return r;
}

int main()
{
int T;
cin >> T;
while(T --)
{
ll x, y;
cin >> x;
y = er_fen(x) + 1;
if(solve(y) == x)
printf("%lld\n",y);
else
puts("impossible");
}

return 0;
}

wzy的大冒险——a+b问题

Description:
每个ACMer都是从a+b问题开始的,今天wzy翻到了他的第一个a+b程序,并想让你来输出它

#include<stdio.h>
int main()
{
int a,b;
scanf(“%d %d”,&a,&b);
int c=a+b;
printf(“%d\n”,c);
return 0;
}
输入格式
本题无输入

输出格式
将上面代码输出

1
2
3
4
5
6
7
8
9
10
11
12
样例
input
output
#include<stdio.h>
int main()
{
int a,b;
scanf("%d %d",&a,&b);
int c=a+b;
printf("%d\n",c);
return 0;
}

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;

int main()
{
printf("#include<stdio.h>\n");
printf("int main()\n");
printf("{\n");
printf("int a,b;\n");
printf("scanf(\"");
cout << "%d " << "%d";
printf("\",&a,&b);\n");
printf("int c=a+b;\n");
printf("printf(\"");
cout << "%d\\n";
printf("\",c);\n");
printf("return 0;\n");
printf("}\n");

return 0;
}

wzy的大冒险——炉石传说

Description:
wzy来到了炉石传说的世界。
他发现他现在有n个攻击力为ai的随从,每个随从只能攻击一次。
对面的boss有m个血量为bi的具有嘲讽的随从(嘲讽即为你必须先把这些怪物击败才可攻击boss)。
当我方随从攻击力大于等于敌方随从血量时,敌方随从死亡。
由于boss的强力技能,对方的随从只能受到一次攻击,受到攻击后无法再一次受到攻击。(你无法使两个随从都攻击对方的同一个的随从)。
wzy必须先干掉对方的所有随从才能使用剩下的随从攻击boss本身。
对方boss有k的血量,现在请问wzy能否干掉敌方boss回归现实世界?

输入格式
第一行为三个数n,m,k。n 为wzy拥有的随从数量,m为boss拥有的随从数量,k为boss血量。
第二行为n个数,分别是wzy随从的攻击力;
第三行为m个数,分别是boss随从的血量。
以上数据范围均在[1,100]范围内

输出格式
如果胜利输出Win,否则输出Lose

1
2
3
4
5
6
7
样例
input
4 3 2
2 4 6 8
3 5 7
output
Win

code:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 101;

int cmp(int a, int b)
{
return a > b;
}
int a[maxx], b[maxx];
int main()
{
int n, m, k;
cin >> n >> m >> k;
memset(a, 0, sizeof a);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= m; i ++) cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int flag = 0;
if(n <= m) puts("Lose");
else
{
int ans = 0;
if(a[n] >= b[m])
{
for(int i = 1; i <= m; i ++)
{
for(int j = 1;j <= n; j ++)
{
if(a[j] < b[i])
{
ans += a[j];
a[j] = 0;
}
else
{
a[j] = 0;
b[i] = 0;
break;
}
}
}
for(int i = 1; i <= n; i ++) ans += a[i];
for(int i = 1; i <= m; i ++)
if(b[i] != 0)
flag = 1;
if(ans >= k && flag == 0) puts("Win");
else puts("Lose");
}
else puts("Lose");
}
return 0;
}

wzy的大冒险——接龙红包

Description:
最近QQ更新了一个新的功能–“接龙红包”,会长作为算协的土豪,便开始在群里发红包,wzy总是抢的又快又准,现在他开始研究成语接龙的奥秘。
现在QQ的词库里面有n种成语,每种成语由一个只由小写字母组成的字符串表示,现在wzy发现了一个问题,如果有个同学说了一个成语,但是在词库里找不到可以接在它后面的成语(即找不到一个成语的首字母和该成语的尾字母相同),这样的成语被称为死局成语,现在zy想知道在词库里面有多少这样的死局成语。

输入格式
第一行输入n,接下来n行每行输入一个字符串代表一个成语s。
(1≤n≤100,1≤|s|≤20)

输出格式
第一行输出死局成语的个数m。
接下来m行每行输出一个死局成语,输出顺序应和输入顺序保持一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
样例
input
3
aaa
bab
abc
output
1
abc
input
3
a
b
c
output
0

code:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxx=1e5;

int main()
{
string str[maxx], str2[maxx];
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> str[i];
}
int ans = 0, len = 1;
for(int i = 1; i <= n; i ++)
{
int flag = 0;
// if(str[i][0] == str[i][str[i].size() - 1]) continue;
for(int j = 1; j <= n; j ++)
{
if(str[j][0] == str[i][str[i].size() - 1])
{
flag = 1;
break;
}
}
if(flag) continue;
ans ++;
str2[len ++] = str[i];
}
cout << ans << endl;
for(int i = 1; i <= len; i ++)
cout << str2[i] << endl;

return 0;
}

大树的水塘

Description:
那一天,世界上所有的人类都……变成了石头!

3700年后,千空和大树从石头中苏醒过来,但是世界发生了翻天覆地的变化,人类文明已经不复存在

天才少年千空立志用自己的科学知识在这个「石之世界」中重建文明

为了生存,淡水是必不可少的,每次都用海水进行蒸馏会比较麻烦,所以千空决定让大树建造一个水塘来存储雨水

水塘建造在一个无限长,高度不超过100,宽度为1的峡谷里,所以只需要往里面填石头,即可达到蓄水的目的

当大树建造好水塘让千空去检查的时候,千空一口老血喷了出来:因为大树是一个体力笨蛋,所以建造的水塘底部是参差不齐的,这使得建造蓄水相同体积的水塘,大树多用了好多石头

已知每块石头中的规格是1×1×1,水塘的长度为N,宽度为1,在第i位置,大树放了ai个石头

设大树建造的水塘蓄水量为V

请你求出在长度和宽度不变的情况下,建造一个蓄水量不小于V的水塘最多可以节约多少石头

输入格式
单组输入

第一行一个数N (1≤N≤10^7)表示水塘的长度

第二行有N个非负数xi (0≤xi≤100),表示第i个位置上放的石头数

输出格式
输出有两行

第一行输出大树建造的水塘的蓄水量V

第二行输出最多可以节约多少石头

提示:
water.7mDyN9DT.png
water_new.pQvfFov7.png

1
2
3
4
5
6
7
样例
input
5
2 1 3 1 3
output
3
8

code:

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e7 + 10;
int a[maxx];
int l[maxx], r[maxx];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
int max_left, max_right;
int cnt_left, cnt_right;
ll v;
cin >> n;
ll sum = 0;
for(int i = 0; i < n; i ++)
//输入每个石块,算出总石头个数
cin >> a[i], sum += 1LL * a[i];
max_left = max_right = 0;
v = 0;
//前后缀
for(int i = 0; i < n; i ++)
max_left = max(max_left, a[i]), l[i] += max_left;
for(int i = n - 1; i >= 0; i --)
max_right = max(max_right, a[i]), r[i] += max_right;
//利用前后缀和的优势找出来,算出储水体积
for(int i = 0; i <= n; i ++)
v += 1LL * min(l[i], r[i]) - a[i];
cout << v << "\n";
//除去两边的石块(因为两边都是石头)
int height = ceil(1.0 * v / (n - 2));
//保证储水不溢出,两边都要有防护
cout << sum - height * 2 << "\n";

return 0;
}

幸运素数

Description:
跳皮筋 我第一,马兰开花二十一;

二五六 二五七,二八二九三十一;

三五六 三五七,三八三九四十一;

……

童谣《马兰花》作为建国以来最大的数学难题,里面数字的含义困扰了全国人民几十年,并且一直未解

难道这些数字真的只是为了押韵生搬硬凑的数字吗?

并!不!是!

经过wzy的多年研究,他发现了里面潜藏的惊天大秘密(并没有):

28=256,而257是离256最近的素数

28是第二个完美数,29是离28最近的素数

31是第四个幸运素数

仅仅这一句话中,就出现了二进制、素数、完美数、幸运数!

这哪里是童谣?这分明就是中国版的达芬奇密码!

今天wzy就来考考你《马兰花》里出现的数学知识:

幸运数是经由类似埃拉托斯特尼筛法的演算法后留下的整数集合,是在1955年波兰数学家乌拉姆提出。

由一组由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, …
先将所有偶数删去,只留下奇数:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25,…
然后把数列中的第 2 个数字(设该数字为 x )的倍数对应的数删除,即把所有第 nx,x∈Z+ 个数删除,例如上述例子中,第 2 数字是 3 ,所以删去所有第 3n 个数:

1, 3, 7, 9, 13, 15, 19, 21, 25,…
新数列的第 3 项(每次都加上 1 )为 7 ,因此将新数列的第 7n 个数删除:

1, 3, 7, 9, 13, 15, 21, 25,…
若一直重复上述的步骤,最后剩下的数就是幸运数

(以上内容来自维基百科幸运数)

我们将既是幸运数又是素数的数叫做幸运素数

现在给你一个数N,请判断N是否是一个幸运素数

输入格式
第一行一个数T,代表有T个数(1≤T≤2×10^5)

第1∼T行,每行一个正整数N(1≤N≤2×10^5)

输出格式
对于每个输入的数N,如果N是幸运素数,输出Yes,否则输出No

1
2
3
4
5
6
7
8
9
10
样例
input
3
1
2
3
output
No
No
Yes

code:

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
#include<bits/stdc++.h>
using namespace std;
const int maxx = 2e5 + 50;
int prime[maxx], luck[maxx];
vector<int> v;

void get_prime()
{
for(int i = 1; i < 200010; i ++)
prime[i] = 1;
prime[0] = prime[1] = 0;
for(int i = 2; i < 200010; i ++)
{
for(int j = 2; j * i < 200010; j ++)
prime[i * j] = 0;
}
}

void get_luck()
{
v.push_back(0);
for(int i = 1; i < 200010; i += 2)
v.push_back(i);
for(int i = 1; i < 200010; i ++)
luck[i] = 0;
int ti = 2;
while(true)
{
int len = v.size();
int s = v[ti];
if(s > len - 1)
break;
for(int i = s; i < len; i += s)
v[i] = 0;
for(auto it = v.begin() + 1; it < v.end(); it ++)
if(*it == 0)
v.erase(it);
ti ++;
}
for(int i = 1; i < v.size(); i ++)
luck[v[i]] = 1;
}


int main()
{
get_prime();
get_luck();
int t , n;
scanf("%d",&t);
for(int i = 1; i <= t; i ++)
{
scanf("%d",&n);
if(luck[n] && prime[n])
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

NO GAME NO LIFE

Description:
空白,永不败北!

作为世界的唯一神灵,游戏之神特图的日常就是改变自己的外表,在世界各地游荡

在被空和白在一次网上的国际象棋比赛击败后,他以拯救人类种的名义将兄妹二人召唤到迪斯博德

来到迪斯博德的空白,常常因为在游戏上找不到对手而感到无聊

在风和日丽的一个下午,空白出门视察国情,在路上偶遇了扮成人类种闲逛的特图,特图为了打发时间,决定向空白发起挑战,游戏内容如下:

在一棵有着N个节点的树上,第i个节点上有xi颗钻石,由最先开始的一方选择一个节点进行标记,标记完成后,双方轮流进行如下操作:拿走标记节点的一颗钻石,并将标记移至与当前节点直接相连的节点,至到出现无法拿石子的一方停止。

空白兄妹听完游戏规则后,立刻做出了回应,但前提是空白作为先手选择节点

特图自认为这是一个特别公平的游戏,所以就答应了这个要求

每当一棵树出现后,空白凭借超人的数学能力,能够在一秒内快速判断出能否获胜

输入格式
单组输入,第一行一个正整数N (2≤N≤10^6),表示这棵树有N个节点

第二行有N个正整数xi (1≤xi≤100),表示i节点上有xi颗钻石

接下来N−1行,每行两个整数x,y (1≤x,y≤N),表示节点x与节点y相连

输出格式
如果空白可以获胜,输出Blank

否则输出Teto

1
2
3
4
5
6
7
8
9
10
11
12
13
样例
input
2
1 1
1 2
output
Teto
input
2
1 2
1 2
output
Blank

code:

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
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e6 + 10;
int a[maxx];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
int x, y;
for(int i = 1; i < n; i ++)
cin >> x >> y;
sort(a, a + n);
n = unique(a, a + n) - a;
if(n == 1)
cout<<"Teto"<<endl;
else
cout<<"Blank"<<endl;

return 0;
}
/*不要直接用cin,cout,会超时*/

---------------- The End ----------------
0%