首页 > 其他分享 >230226题解

230226题解

时间：2023-07-16 22:01:16浏览次数：35  
标签：输出 10 int 题解 ll 230226 long mod

A 数列

题目描述

给定一个长为\(n\)的数列\(A_1,A_2,…,A_n\)。

给出 \(q\)次询问，每次询问给定\(X\)，请你回答至少需要多少次操作，能够让数列中的每个数都变成\(X\) 。每次操作你可以选择数列中的一个数加\(1\)或者减\(1\)。询问之间相互独立。

输入格式

第一行两个整数\(n,q\)。

第二行\(n\)个整数\(A_1,A_2,…,A_n\)。

接下来\(q\)行，每行一个整数，表示询问的\(X\)。

保证 \(1 \le n,q≤2×10^5,0≤A_i,X≤10^9\) 。

输出格式

对于每个询问输出一行一个整数，表示答案。

样例 1

输入
5 3
6 11 2 5 5
5
20
0
输出
10
71
29

样例 2

输入
10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0
输出
3316905982
2811735560
5542639502
4275864946
4457360498

题解

十分简单得一道题

首先排序，方便用二分查找，因为操作是减一或加一，所以我们在数组大的那一边减一，小的那一边加一，

用前缀和数组\(\mathcal O(1)\)计算需要多少次

#include<bits/stdc++.h>
using namespace std;
int n,q,a[200010],maxn,minn = 0x7fffffff;
long long sum[200010];
int main(){
	scanf("%d%d",&n,&q);
	for(int i = 1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i = 1;i<=n;i++)
		sum[i] = (long long)(sum[i-1]+a[i]);
	for(int i = 1;i<=q;i++){
		long long x;
		scanf("%lld",&x);
		int l = lower_bound(a+1,a+n+1,x)-a;
		long long ans1 = x*(l-1)*1ll-sum[l-1];
		long long ans2 = sum[n]-sum[l-1]-x*(n-l+1)*1ll;
		printf("%lld\n",ans1+ans2);
	}
	return 0;
}

B 序列编号

题目描述

序列王国的国王小 A 想要给所有序列编号。具体来讲，他需要给每个长为\(n\)的，每个数属于\([1,k]\)的整数序列编一个\([1,m]\)之内的编号。

请你输出编号的方案数，模\(998244353998244353\)。

输入格式

一行三个整数\(n,k,m\)。

保证\(1≤n,k,m≤10^{18}\)。

输出格式

输出一行一个整数，表示答案。

样例 1

输入
2 2 2
输出
16

题解

这个题目一看就是组合数学，但是我并不会

得出的式子应该是\(m^{k^n}\)

证明如下：

对于每一个数列，每一个位置都有\(k\)种可能，每一个数列有\(n\)的长度

那么对于每一个数列来说都有\(k^n\)种可能

对于每一个数列来说，都有\(m\)种编号，总共有\(k^n\)种数列

所以总共\(m^{k^n}\)种

然后我们可以看看数据范围，明显是快速幂过不去的，我们需要找一种\(O(logn)\)的级别的算法，快速幂应该是\(O(n)\)的级别

欧拉函数在这个情况下\(\varphi(p) = p-1\)

扩展欧拉定理如下但好像对这道题没什么用

\[a^b\equiv \left\{\begin{matrix} a^{b \ mod \ \varphi (p)+\varphi (p)},\gcd(a,p) \ne 1,b\ge \varphi(p) \\a^{b}, \gcd(a,p)\ne 1,b < \varphi(p) \\a^{b \ mod \ \varphi (p)},\gcd(a,p) = 1 \end{matrix}\right. (mod(p)) \]

注意：我们不对\(k^n\)进行欧拉降幂，因为没有这个必要，如果要降幂，我们还要计算对应的欧拉函数，时间复杂度是足够的

还有一点要注意的，在计算\(k^n\)时我们模数应该是\(mod-1\)而非\(mod\)，对于\(k\)，\(m\)还要在开始计算时进行一次取模，不然第一次计算就会溢出，这里的\(k\)也是需要\(mod-1\)

基本上这些就是所有的要点了所有坑都被我踩了一遍了QAQ

#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
ll n,k,m;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
ll qpow(ll x,ll y,ll modd){
	ll a = 1;
	for(;y;y>>=1,x = (ll)x*x%modd)
		if(y&1) a = (ll)a*x%modd;
	return a;
}
int main(){
	scanf("%lld%lld%lld",&n,&k,&m);
	k%=(mod-1),m%=mod;
	if(m==0){
		puts("0");
		return 0;
	}
	ll ans = qpow(k,n,mod-1);
	ans = qpow(m,ans,mod);
	printf("%lld",ans);
	return 0;
}

C 最小生成树

题目描述

给定一个 \(n\) 个点\(m\) 条边的无向图，图中可能有自环和重边，每条边有边权 \(c_i\) 且边权两两不同。

请你回答 \(q\) 次询问，每次询问给定 \((u,v,w)\) ，请你回答如果在图中\((u,v)\) 之间加入一条边权为$ w$ 的边，图中的最小生成树是否包含这条边。保证加入边后图中每条边边权仍两两不同。

输入格式

第一行三个整数\(n,m,q\) 。

接下来 \(m\) 行，每行三个整数 \(u,v,c\) 表示一条边。

接下来 \(q\) 行，每行三个整数 \(u,v,w\) 表示一次询问。

保证 \(2≤n≤2×10^5,n−1≤m≤2×10^5,1≤q≤2×10^5,1≤w_i,c_i≤10^9\) 。

输出格式

对每个询问输出一行 Yes 或 No 表示询问的答案。

样例 1

输入
5 6 3
1 2 2
2 3 3
1 3 6
2 4 5
4 5 9
3 5 8
1 3 1
3 4 7
3 5 7
输出
Yes
No
Yes

样例 2

输入
2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5
输出
Yes
No

题解

首先我们需要在原来的图上知道那些边被加入了最小生成树

再考虑询问，如果询问的边符合 kruskal 的要求，就输出 Yes

但明显是会炸时间的，所以我们只用跑一次 kruskal

离线下所有的询问，对于原图上的边才增加生成树中边的个数

对于询问则不改变生成树中边的个数，记录是否会被选到

#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v,w,id;
}e[500010];
int n,m,q,fa[200010],cnt;
bool a[200010];
bool cmp(edge a,edge b){
	return a.w<b.w;
}
void add(int u,int v,int w,int flag){
	e[++cnt].u = u;
	e[cnt].v = v;
	e[cnt].w = w;
	e[cnt].id = flag;
}
int find_(int x){
	return fa[x]==x?x:fa[x] = find_(fa[x]);
}
void kruskal(){
	int k = n-1,i = 1;
	while(k&&i<=cnt){
		int u = find_(e[i].u),v = find_(e[i].v);
		if(u!=v){
			a[e[i].id] = true;
			if(!e[i].id){
				fa[u] = v;
				k--;
			}
		}
		i++;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i = 1;i<=n;i++)
		fa[i] = i;
	for(int i = 1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w,0);
	}
	for(int i = 1;i<=q;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w,i);
	}
	sort(e+1,e+cnt+1,cmp);
	kruskal();
	for(int i = 1;i<=q;i++)
		if(a[i]) puts("Yes");
		else puts("No");
	return 0;
}

D 等差数

题目描述

对于一个数，如果它的数码形成一个等差数列，那么我们称之为等差数。例如\(234,369,86420,111\)都是等差数。

现在请你找出大于等于 \(X\) 的最小等差数。

输入格式

一行一个整数 \(X\)。

保证 \(1≤X≤10^{17}\) 。

输出格式

输出一行一个整数，表示答案。

样例 1

输入
152
输出
159

题解

容易知道一点，等差数在 \(10^9\) 范围内的个数不会超时间，各位可以通过排列组合枚举一下鸽子当太久记不到数据了

那么我们只需要暴力枚举出每一个等差数即可，当然不可能是一个一个数枚举

我们可以从等差数每一位的差来入手，枚举完差值再枚举第一位的数字，再由第一位的数字推至每一位

最后用二分查找即可知道询问在多少位

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long x;
	scanf("%lld",&x);
	set<long long> st;
	st.insert(0);
	for(int i = -9;i<=9;i++){
		for(int j = 1;j<=9;j++){
			long long a = j;
			st.insert(a);
			int tmp = j;
			while(true){
				tmp+=i;
				if(tmp<0||tmp>9){
					break;
				}
				a = a*10+tmp;
				st.insert(a);
				if(a>=x){
					break;
				}
			}
		}
	}
	printf("%lld",*st.lower_bound(x));
	return 0;
}

E 巧克力

题目描述

小 A 获得了长度为 \(L\) 的巧克力，他想要把巧克力分给他的朋友们。

具体来讲，小 A 有 \(n\) 个朋友，小 A 打算给第 \(i\) 个朋友长度恰为 \(A_i\) 的一块巧克力。

现在，小 A 要通过如下方式将巧克力切成若干块：

选择一个长为 \(k\) 的巧克力，并且把它切成长度为 \(x,k−x\) 的两块。这里 \(x\) 必须满足 \(1≤x≤k−1\) 。这样的一次操作的代价是\(k\)。

请你计算小 A 最少需要多少的代价才能把巧克力分给他的朋友们。

输入格式

第一行两个整数 \(n,L\) 。

第二行 \(n\) 个整数，表示 \(A_1,A_2,…,A_n\)。

保证 \(2≤n≤2×10^5,1≤A_i≤10^9,A_1+A_2+⋯+A_n≤L≤10^{15}\)。

输出格式

输出一行一个数，表示最小需要的代价。

样例 1

输入
5 7
1 2 1 2 1
输出
16

题解

我们逆向思考一下这道题，把砍的过程换成拼的过程，那么就是每次将最小的两堆合并起来那么一定是最优

#include<bits/stdc++.h>
using namespace std;
long long ans,m,n,k;
priority_queue<long long,vector<long long>,greater<long long> >q;
int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i = 1;i<=n;i++){
		long long x;
		scanf("%lld",&x);
		q.push(x);
		m-=x;
	}
	if(m) q.push(m);
	while(q.size()>1){
		long long tmp = q.top();q.pop();
		long long cnt = q.top();q.pop();
		ans+=tmp+cnt;
		q.push(tmp+cnt);
	}
	printf("%lld",ans);
	return 0;
}

F 选拔

题目描述

AT 省即将进行竞赛省队选拔。

今年 AT 省共有 \(n\) 名选手，他们分别在 PION 和 IOTA 中获得了 \(P_i\) 和 \(Q_i\) 的排名。已知在两次比赛中没有同分的情况，因此 \(P,Q\) 均为 \([1,n]\) 的排列。

AT 省共有 \(k\) 个省队名额。为了维持一定的公平性，如果 \(P_x>P_y\) 和 \(Q_x>Q_y\) 同时满足且 \(x\) 入选了省队，那么 \(y\) 也必须入选省队。

请你求出有多少种选出省队选手的方案。模 998244353。

输入格式

第一行两个数 \(n,k\) 。

接下来两行，每行 \(n\) 个数，分别表示 \(P_1,P_2,…,P_n\) 和 \(Q_1,Q_2,…,Q_n\) 。

保证 \(1≤k≤n≤300\) 且 \(P,Q\) 均为 \([1,n]\) 的排列。

输出格式

输出一行一个整数，表示答案。

样例 1

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

题解

我们先去掉一个限制条件，把 p 数组先排好序，那么就只用考虑 q 的大小了

这时候我们可以用 dp 来计算答案万恶之源来了

设计一个 \(dp_{i,j,k}\) 分别表示当前的人，选择了多少个人，当前最小值

至于赋初始值为什么是 \(f_{0,0,n+1} = 1\) ，如果范围在 \([1,n]\) 时是没法凑出一种方案的

至于遍历时要开到 \(n+1\) 的范围也是如此

#include<bits/stdc++.h>
#define mod 998244353
#define N 310
using namespace std;
int n,q,a[N],p[N];
long long f[N][N][N],ans;
int main(){
	scanf("%d%d",&n,&q);
	for(int i = 1;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i = 1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a[p[i]] = x;
	}
	f[0][0][n+1] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=q;j++){
			for(int k = 1;k<=n+1;k++){
				f[i][j][min(k,a[i])]+=f[i-1][j][k];
				f[i][j][min(k,a[i])]%=mod;
				if(a[i]<k){
					f[i][j+1][k]+=f[i-1][j][k];
					f[i][j+1][k]%=mod;
				}
			}
		}
	}
	for(int i = 1;i<=n+1;i++)
		ans = (f[n][q][i]+ans)%mod;
	printf("%lld",ans);
	return 0;
}

标签：输出,10,int,题解,ll,230226,long,mod
From： https://www.cnblogs.com/cztq/p/17558671.html

相关文章

  • 题解 HDU5726【GCD】/ LGT353762【Soso 的最大公约数】
    Problem给你一个长为\(N(1\leqN\leq1\times10^5)\)的整数序列：\(a_{1},\cdots,a_{n}(0<a_{i}\leq1\times10^9)\)。有\(Q(1\leqQ\leq1\times10^5)\)次提问。每次提问有个范围\(l,r\)，你需要计算出\(\gcd(a_{l},,a_{l+1},...,a_{r})\)，并且统计数对\((l’,r’......
  • Codeforces Round 896 Div2 A-D题解
    CodeforcesRound896A.Politics这题问的是，给一些人的在n个议题的观点，然后你可以随意安排顺序，每个议题人多的赢，反对派会离开，问随便安排议题，最多留下多少人，包括我自己这个题刚开始愣了半天，但是想到，那只要把所有和我观点一致的给留下来不就行了？？？然后交上去就AC了ACCode#inclu......
  • 题解 CF1842H【Tenzing and Random Real Numbers】
    看了题解。好难受，想用积分求概率，算了半天。发现没啥规律，不是不能算，就是太可怕了。Problem有\(n\)个\([0,1]\)范围内的均匀随机变量\(x_{1\cdotsn}\)和\(m\)条限制，每条限制形如\(x_i+x_j\le1\)或\(x_i+x_j\ge1\)。请你求出所有限制均满足的概率。对\(998244353\)......
  • Noip优质模拟赛口胡题解
    HDU5719题意概括：第一行输入t表示输入数据,每组数据第一行n，表示对1—n进行排序。接下来输入n个数b[n]表示排列中第i个数之前的最小值为b[i]。第三行n个数c[n]，表示排列中第i个数之前的最大值为c[i]。解题思路：递推,排除掉6种不可能的情况,1、b[i]>b[i-1]2、c[i]<c[i-1]3、b[i]......
  • 2023.07.16 高质量 NOIP 模拟赛题解
    HDU5719Arrange【模拟】给定数列\(B_n,C_n\)，求出满足\[B_i=\min_{j=1}^i\{A_j\},\quadC_i=\max_{j=1}^i\{A_j\}\]的排列\(A\)的数量。维护每个位置可能的数字数量，然后乘法原理即可。代码：http://acm.hdu.edu.cn/viewcode.php?rid=38654445。HDU5807KeepInTouch......
  • HHHOJ #1247. 「NOIP 2023 模拟赛 20230715 A」1 题解--zhengjun
    法老找来的题，说是找了三道其他模拟赛的T4拼成T1~T3，另外搞了道T4。思维好题，但是放在T1有点搞心态，但是还好大样例够强，400没挂。然而T3大样例输出错了，浪费了我0.5h，差评。首先发现向左走之后向右走是一定不优的，所以最短路的情况只能先向右再向左。考虑枚举起点\(s......
  • 题解 P2839【[国家集训队] middle】
    Problem一个长度为\(n\)的序列\(a\)，设其排过序之后为\(b\)，其中位数定义为\(b_{n/2}\)，其中\(a,b\)从\(0\)开始标号，除法下取整。给你一个长度为\(n\)的序列\(s\)。回答\(Q\)个这样的询问：\(s\)的左端点在\([a,b]\)之间，右端点在\([c,d]\)之间的子区间中，最大的中......
  • 你省（福建）省队集训 Day5 T1 题解
    简要题意有两个正整数\(a<b\le10^9\)，给出\(\dfrac{a}{b}\)的小数点后\(19\)位，要求还原\(a,b\)，保证有解。solution一个科技：\(\texttt{Stern-Brocottree}(SBT)\)，可以参考这个博客学习。先给出\(O(n)\)找的代码：......
  • 云斗杯 T2 派蒙是最好的伙伴！ 题解
    云斗杯T2题解赛时脑抽了只打了60pts暴力xwx。题目描述给定两个长度为\(n\)的\(01\)序列\({a_n}\)和\({b_n}\)，与另一个矩阵\({c_{n,n}}\)。矩阵\({c_{n,n}}\)的生成规则如下：\[c_{i,j}=a_i\timesb_j\]现给定一个数\(k\)，求在矩阵\(c_{n,n}\)内，有多少个......
  • freee Programming Contest 2023（AtCoder Beginner Contest 310）题解
    点我看题A-OrderSomethingElse直接比较\(P\)和\(Q+min(D_i)\)，输出较小值即可。点击查看代码#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<n;++i)#definerepn(i,n)for(inti=1;i<=n;++i)#defineLLlonglong#definefifirst#definesesecond#defi......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99