Day28

Day28

今天积分赛
好好学习!!!

Steve的水池

Description:
Steve 拥有深棕色头发,晒黑的褐色皮肤,紫色的眼睛,身穿青蓝色的衬衫,一条紫蓝色牛仔裤以及灰黑色的鞋子。他还拥有2px至4px大小的胳膊。Steve 似乎拥有轻微的浅棕色胡子茬,或者拥有一张嘴,这取决于你怎样看他。

Steve 需要种庄稼,圈养动物来获得食物来源,为了抵抗怪物,他需要挖矿获得铁锭,金锭,甚至钻石来制作更高级的武器装备,通常,他还需要对武器装备附魔,来提升效果,为此,他不得不需要经常下矿。

在经历了枯燥又乏味的矿工生活后,Steve 打算建造一个水池来放松放松,他打算把水池建造成一个高度为1,长宽分别为N,M的水池,为此,他需要向水池中倒水,但Steve 只有一个水桶,他不想要浪费更多的铁锭来制作更多的水桶,为此,他需要尽可能少的往水池里倒水以尽快建造好水池,但是Steve 的世界有一个很奇怪的特性,每向一个区域倒水的时候,在这个区域会形成一个水源,当一个区域四个方向中至少有两个方向紧挨着这个区域的地方都为水源的话,这个区域也将会形成水源,Steve 想要知道最少他需要倒多少次水才能使水池每处都形成水源。

输入格式
输入第1行为一个整数T。(1 ≤ T ≤ 1000)
第2行到第T+1行每行为两个整数N,M代表水池的长宽。(1 ≤ N,M ≤ 10^9)

输出格式
输出为T行,每行输出一个整数,代表Steve 最少需要的倒水次数。

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

题解

规律题:规律为(n+m)/2

code:

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

int main()
{
int n, m;
int t;
scanf("%d",&t);
while(t --)
{
scanf("%d %d",&n, &m);
int ans = ceil(1.0 * (n + m) / 2);
printf("%d\n",ans);
}


return 0;
}

掷骰子

Description:
骰子,中国传统民间娱乐用来投掷的博具,早在战国时期就已经被发明。

现在给你 n 个骰子,求 n 个骰子掷出点数之和为 a 的概率是多少。
输入格式
第一行输入一个整数 T,表示有 T 组测试数据(1≤T≤10)
每组测试数据输入两个整数n,a,表示共有n个骰子,骰子点数总和为a(1≤n≤1000,n≤a≤6∗n)

输出格式
如题。答案对 109+7 取余。

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

题解

dp[i][j]表示投掷玩i个骰子和为j的方案书,dp[i][j]=求和(dp[i-1][j-k]),k为第i个骰子的点数。暴力转移即可

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
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
const ll mod=1000000007;
const int maxn=1000+10;
ll dp[maxn][maxn*6];
ll quickpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void solve(){
int t;
int n,a;
scanf("%d",&t);

while(t--){
memset(dp,0,sizeof(dp));
scanf("%d %d",&n,&a);
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=6*n;j++){
for(int k=j-6;k<j;k++){
if(k<0) continue;
dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
}
}
}
printf("%lld\n",dp[n][a]*quickpow(quickpow(6,n),mod-2)%mod);
}
}
int main()
{
solve();
return 0;
}

Subsequence

Description:
Steve 和 Alex 喜欢研究字符串,今天他们学到了一个新名词—“Subsequence“。对于字符串 s 和 t 来说,t 被称为 s 的”Subsequence“当且仅当 s 删除若干字母后能得到 t (也可以不删)。

例如:”ab”,”ac”,”bc”都是”abc”的”Subsequence“,而”ba”和”ca”则不是。

现在 Steve 和 Alex 手中各自有一个只由小写字母组成的字符串 s 和 t ,请判断 t 是否是 s 的”Subsequence“。

输入格式
第一行输入一个T,代表数据组数。
接下来输入T组,每组包含两行,第一行输入s,第二行输入t。
(1≤T≤1000,1≤|t|≤|s|≤10000)

输出格式
输出T行,如果t是s的”Subsequence“,输入”YES”,否则输出”NO”。

1
2
3
4
5
6
7
8
9
10
11
12
13
样例
input
3
abc
ac
abc
ba
abc
a
output
YES
NO
YES

题解

设置一个指针j,如果s1i = s2j,j往后移,判断到最后j是否为m即可,m为t的长度

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin >> t;
while(t --)
{
string s1, s2;
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
int i = 0, j = 0;
while(i < n && j < m)
{
if(s1[i] == s2[j]) j ++;
i ++;
}
if(j == m) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return 0;
}

Steve的游戏名

Description:
定义一个字符串s是一步字符串,当 s 满足以下两个条件:

s 中仅包含小写字母。
对于任意的1≤i<|s|满足,s[i]+1=s[i+1],也就是说,s[i]在英文字母表中的位置的下一位是s[i+1],特别的,我们认为z的下一位是a,其中|s|表示s的长度。
举个例子:abc、zab 都是一步字符串,而 acd、zbc不是。
Steve 特别喜欢长长的名字,因此他在 Minecraft 中的名字特别特别的长。
Alex 对 Steve 的名字特别感兴趣,她想知道 Steve 的名字中有多少个子串是一步字符串。
形式化来说,对于一个字符串 s,问有多少对 <i,j> 满足 1≤i≤j≤n,且 s[i]…s[j] 是一步字符串。
保证 Steve 在 Minecraft 中的名字仅包含小写英文字母。

输入格式
输入包含多组测试数据。
第一行一个数字 T ,表示测试数据个数。
接下来每两行表示一个测试数据。
第一行一个数字 n 。
第二行一个长度为 n 的字符串 s。

数据范围:1≤T≤100,1≤n≤2⋅105

输出格式
一个数字表示答案。

1
2
3
4
5
6
7
8
9
10
样例
input
2
3
abc
3
zab
output
6
6

题意

O(|s|)的遍历即可,遇到不满足条件的更新最新的满足条件的最大区间|l,r|,答案加上(r-l+1)*(r-l)/2

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

int main()
{
ll t, n;
string str;
scanf("%d",&t);
while(t --)
{
scanf("%d",&n);
cin >> str;
ll x = 1, ans = 0;
for(int i = 0; i < n - 1; i ++)
{
if((str[i] - 'a' + 1) % 26 == (str[i + 1] - 'a') % 26) x ++;
else
{
ans += (1 + x) * x / 2 - x;
x = 1;
}
}
if(x) ans += (1 + x) * x / 2 - x;
ans += n;
cout << ans << '\n';
}
return 0;
}

数字串

Description:
给你一个长度为 n 的数字串,找出其中位数不超过15位的不包含前导0和后导0的数 x ,使得 x+f(x) 是一个回文数,其中 f(x) 表示将 x 反转过来的数。

输入格式
多组输入,处理到文件结束,样例保证不超过1000组。
每组第一行一个整数 n ,表示数字串的长度(1≤n≤1000),
接下来一行输入一个长度为 n 的数字串。

输出格式
第一行一个数 m 表示数字串中符合条件的数的个数(数可以重复)。
第二行从小到大输出 m 个数,每个数字之间以空格隔开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
样例
input
3
123
output
6
1 2 3 12 23 123
提示
1+1=2,
2+2=4,
3+3=6,
12+21=33,
23+32=55,
123+321=444

暴力即可过
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
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
const ll mod=1000000007;
const int maxn=1000000+10;
char s[maxn];
ll a[maxn];
ll fan(ll x){
ll res=0;
while(x){
res=res*10+x%10;
x/=10;
}
return res;
}

void solve(){
ll n;

while(~scanf("%lld",&n)){
scanf("%s",s);
ll sum=0;
for(int i=0;i<n;i++){
if(s[i]=='0') continue;
ll x=0;
for(int j=0;j<15 && i+j<n;j++){
x=x*10+s[i+j]-'0';
if(s[i+j]=='0') continue;
if(x+fan(x)==fan(x+fan(x))){
a[sum++]=x;
}
}
}
sort(a,a+sum);
printf("%lld\n",sum);
for(int i=0;i<sum;i++) printf("%lld ",a[i]);
printf("\n");
}
}

int main()
{
solve();
return 0;
}

Alex的午饭

Description:
Steve和Alex每天都在为午饭吃什么而发愁,因为吃的东西实在是太多了,而且很多都特别好吃。为了解决吃什么的问题,Alex决定每次吃饭前发布一个问卷调查,让他的好朋友选出他们今天最想吃的食物,然后Alex会根据问卷的结果来确定吃什么

每个问卷只收集一种食物,每个食物都由一个数字num来表示。Alex会选出问卷中出现次数超过问卷总数一半的数字来决定今天的午饭

输入格式
单组输入,每组两行
第一行有一个整数N (1≤N≤2×10^7)
第二行有N个整数num (num≤10^18),代表每个问卷中的数字

输出格式
输出一个整数,即出现次数超过N/2的数

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

ps:用map做的话会超时
好像是什么xx摩尔算法吧

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){

int t;
ll x, ans;
int res = 0;
scanf("%lld",&t);
int i;
for(i = 0; i < t; i ++)
{
scanf("%lld",&x);
if(!res)
ans = x;
if(x == ans)
res ++;
if(x != ans)
res --;
}
printf("%lld\n",ans);
return 0;
}

The war land

Description:
Steve 和 Alex 开始玩一款叫做战争大陆的游戏,整个地图由 n 个岛屿和 n−1 条桥梁组成,第 i 个岛屿的战略能力为 wi ,整个地图是联通的。游戏开始 Steve 和 Alex 需要断掉一座桥梁,这样整个地图就被划分为了两个联通的区域 A 和 B 并且 A 和 B 之间无法到达。
为了使游戏尽可能公平,现在他们想让 A 和 B 的战略能力之和的差值的绝对值最小。

输入格式
第一行输入T代表数据组数。
接下来T组,对于每一组:
第一行输入n,接下来n−1行,每行输入两个数字u,v代表u和v之间的岛屿有一座桥梁,最后一行输入n个数,第i个数代表第i个岛屿的战略值wi。
(1≤T≤10,1≤n≤100000,1≤wi≤10^9,1≤u,v≤n)

输出格式
输出T组,对于每组输入,输出最小的差值的绝对值。
picg.9GafXAtx.png

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

题意

这是一棵树,我们以1为根节点DFS统计以i为根的子树的大小,然后切一条边其实就是割掉一个子树,处理之后枚举即可。复杂度O(T·n)

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
#include<bits/stdc++.h>

using namespace std;
const int N = 200001;
long long siz[N],w[N];
vector<int> G[N];
void dfs(int u,int par){
siz[u]=w[u];
for(int v:G[u]){
if(v==par) continue;
dfs(v,u);
siz[u]+=siz[v];
}
}

int main(){
int T;
cin>>T;
while(T--){
memset(siz,0,sizeof(siz));
int n;cin>>n;
for(int i=1;i<=n;i++) G[i].clear();
int u,v;
for(int i=1;i<=n-1;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++) cin>>w[i];
dfs(1,0);
long long ans=999999999999999999;
for(int i=2;i<=n;i++){
ans=min(ans,abs(siz[1]-2*siz[i]));
}
cout<<ans<<endl;
}
return 0;
}

Number throry

Description:
steve 学完了快速幂,现在会他快速的计算:(i^j)%d , Alex 作为一个数学大师,给了 steve 一个问题:已知
i∈[1,n],j∈[1,m] ,计算满足 (i^j)%d=0 的 (i,j) 的对数。

输入格式
T组输入,对于每一组输入三个数n,m,d。
(1≤T≤1000,1≤n,m,d≤10^9)。

输出格式
对于每组输入,输出答案,每个答案占一行。

1
2
3
4
5
6
7
8
9
10
11
12
样例
input
4
3 10 7
3 5 3
10 30 6
100 100 8
output
0
5
30
4937

题解
质因子分解.png

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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=(ans*a);
a=(a*a);
b>>=1;
}
return ans;
}

int main(){
int T;
scanf("%d",&T);
while(T--){
ll n,m,d;
scanf("%lld %lld %lld",&n,&m,&d);
vector<pair<ll,ll> > prs;
for(ll i=2;i*i<=d;i++){
if(d%i==0){
long long cnt=0;
while(d%i==0){
d/=i;cnt++;
}
prs.push_back({i,cnt});
}
}
ll res=0;
if(d!=1) prs.push_back({d,1});
for(ll j=1;j<=min(m,1LL*30);j++){
ll g=1;
for(auto v:prs){
g*=qpow(v.first,(v.second+j-1)/j);
}
if(j==30) res+=(m-29)*(n/g);
else res+=n/g;
}
printf("%lld\n",res);
}
return 0;
}

Steve的难题

Description:
Steve参加了2019年的暑期集训,在集训最后一场积分赛时,Steve英勇AC,提交了几十发全A了。Steve顿时惊叹,这不都是水题吗,于是接下来碰到的问题却难倒了他。求1n! 模p意义下的值。

输入格式
多组输入,处理到文件结束。
每行输入两个数n,p,(1≤n≤10^5,n<p≤10^9).
数据保证 p 是个质数。
输出格式
如题

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

题解

求解逆元裸题,可以用exgcd(扩展gcd),也可以用费马小定理,由于p为质数,因此x的逆元为x^(p-2)%p

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quick_pow(ll a, ll b, ll p)
{
ll res = 1;
if(b <= 0) return res;
while(b)
{
if(b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}

//x 的逆元为 x^(p - 2) % p;
int main()
{
ll n, p;
while(~scanf("%lld %lld", &n, &p))
{
ll res = 1;
for(ll i = 1; i <= n; i ++)
{
res = res * quick_pow(i, p - 2, p) % p;
}
printf("%lld\n", res);
}

return 0;
}

Steve’s Shortest Path

Description:
Alex 和 Steve 来到了一个神奇的国度,这个国家有 n 个城市和 m 条道路。这 m 条道路都是双向的,而且这个国家的客车有个特点,每辆客车除出发城市和到达城市外有且仅可经过一个城市。

假设u城市到v有一条道路并且 v 到 p 有一条道路,那么客车从 u 出发不能到达 v 但是能到达 p,Steve 和 Alex 在编号为 1 的城市,他们想知道能不能到达编号为 n 的城市,如果能,最少需要坐几次客车?

输入格式
单组输入。
第一行输入 n 和 m 代表城市的个数和路径的条数。
接下来 m 行每行输入两个数 u 和 v 代表 u 到 v 之间有条路。(2≤n,m≤10^6,1≤u,v≤n)。

输出格式
如果 Steve 和 Alex 能够到达终点,输出最少需要坐几次车才能到达,否则输出−1。

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

题解

直接BFS/Dijkstra即可,记录两个状态分别代表到达i点最短路为奇偶的情况.即dis[i][0]代表到i点走了偶数步的最短路,dis[i][1]代表到i点走了奇数步的最短路,然后答案即为dis[i][0]/2

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
vector<int>vec[maxn];
int step[maxn];
bool vis[maxn];
int n,m;
void bfs(int x){
queue<int>que;
que.push(x);
vis[x]=1;
step[x]=0;
while(!que.empty()){
x=que.front();
que.pop();
for(int i=0;i<vec[x].size();i++){
int y=vec[x][i];
for(int j=0;j<vec[y].size();j++){
int z=vec[y][j];
if(vis[z]) continue;
vis[z]=1;
step[z]=step[x]+1;
que.push(z);
if(z==n) return ;
}
}
}
}

int main()
{
scanf("%d %d",&n,&m);
int u,v;
for(int i=0;i<m;i++){
scanf("%d %d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
}
bfs(1);
if(step[n]==0) printf("-1\n");
else printf("%d\n",step[n]);
return 0;
}

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