首页 > 其他分享 >CF1195D2的题解

CF1195D2的题解

时间:2024-03-27 12:36:49浏览次数:32  
标签:int 题解 代码 long 100010 CF1195D2

(一)

虽说代码较长,但非常好理解,还是最优解(公开的就两个)。

考虑对每个数单独算贡献,循环枚举与它进行运算的数的长度,然后确定那个数的位置即可,再乘以出现的数位对应的贡献,如出现在倒数第二位就乘 \(10\)。

难度应该不到绿。

(二)

AC 代码。

#include<bits/stdc++.h>
#define int long long//记得开 long long
using namespace std;
const int md=998244353;
int n,sum[21],mx,ans,a[100010],siz[100010];
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%lld",&x);a[i]=x;
		while(x)siz[i]++,x/=10;
		sum[siz[i]]++;//统计数的位数
		mx=max(mx,siz[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=mx;j++){
			if(!sum[j])continue;
			int p1=siz[i],p2=j,d=1,s=0,x=a[i];
			bool flag=0;//flag 表示填的是当前数,还是进行运算的另一个数
			while(p1&&p2){
				if(!flag)s=(s+(x%10)*d)%md,p1--,x/=10;
				else p2--;
				flag^=1;
				d=d*10%md;
			}
			while(x){
				s=(s+(x%10)*d)%md;
				x/=10;
				d=d*10%md;
			}
			ans=(ans+sum[j]*s)%md;
		}
		for(int j=1;j<=mx;j++){
			if(!sum[j])continue;
			int p1=siz[i],p2=j,d=1,s=0,x=a[i];
			bool flag=1;
			while(p1&&p2){
				if(!flag)s=(s+(x%10)*d)%md,p1--,x/=10;
				else p2--;
				flag^=1;
				d=d*10%md;
			}
			while(x){
				s=(s+(x%10)*d)%md;
				x/=10;
				d=d*10%md;
			}
			ans=(ans+sum[j]*s)%md;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

标签:int,题解,代码,long,100010,CF1195D2
From: https://www.cnblogs.com/Jh763878/p/18098703

相关文章

  • AT_abc343_f的题解
    (一)F<E。显然是线段树,虽然分块也能过。每个线段树上的节点记录最大值,第二大值,最大值个数,第二大值个数。合并操作注意值相等的情况。(二)AC代码。赛事写得有点乱。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,q,a[400010];structnode{ int......
  • CF1676H2的题解
    (一)题意转化为求\(i<j\)且$a_j\lea_i$的有序对\((i,j)\)数。二维偏序,容易想到用树状数组或归并排序做。(二)AC代码(树状数组)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,t,tree[200010],a[200010];intlowbit(intx){ returnx&-x;......
  • P10185的题解
    (一)考虑对每一种颜色单独求解。对于一次第\(k\)种的“循环”,美丽度会加上\[\sum_{i=1}^{a_k}C_{n}^{i}\timesv_k^{i}=(v_k+1)^{a_k}-1\]相信大家都学过二项式定理。“循环”次数取决于其他珠子是否出现,即\(2^{\sum_{i=1}^{a_i}-a_k}\)。再将两式相乘就愉快AC了。(二)警......
  • CF1904C的题解
    (一)不太好想。(我看了题解才会)当\(k>2\)时,可以选两次相同的\(i\)和\(j\)。再将生成的数做差。当\(k=1\)时,直接\(Θ(n^2)\)枚举。当\(k=2\)时,先枚举第一次的\(i\)和\(j\),再用lower_bound()实现查找第二次选择的数。时间复杂度\(Θ(n^2\log_2{n})\)。注......
  • CF1929C的题解
    (一)每次下注,要么赚\(y\times(k-1)\),要么亏\(y\)。由于不知道什么时候会输,每次都下能赚回前面所有的金额好了。第一次下\(1\),共下\(x+1\)次。(二)AC代码。#include<bits/stdc++.h>usingnamespacestd;intt,k,x,a;intmain(){ scanf("%d",&t); while(t--){ scan......
  • CF1213D1的题解
    (一)直接暴力!!!对于每一个数,枚举它能生成的数。然后对于每一个可能的答案,开长度为\(k\)的优先队列维护,同时统计操作次数和。时间复杂度为\(Θ(\log^2_2n)\)。惊讶地发现顺便把双倍经验给切了。(卡过)(二)AC代码。#include<bits/stdc++.h>usingnamespacestd;intcnt,n,k,su......
  • CF1922C的题解
    (一)从\(i\)到\(j\)有两种走法,一种是用\(a_j-a_i\)的代价,一种是用\(1\)的代价,前提是\(j\)是\(i\)最近的。显然如果符合条件选第二种。先考虑从左向右走。(和从右向左相同)考虑走到了节点\(i\),如果\(a_{i+1}-a_{i}>a_{i}-a_{i-1}\),那么花费\(1\)的代价向右走,否则花......
  • AT_arc169_a的题解
    (一)由于每次把子节点的权值加到父节点中,深度越深影响越大。将\(1\)号节点视作父节点,不难发现,同一深度的节点对其贡献度相等,都为\(1\timesnow\val\)。因为\(10^{100}\)极大,所以统计每层权值和,从深往浅扫。(二)AC代码。#include<bits/stdc++.h>#defineintlonglongus......
  • CF1922B的题解
    (一)因为\(2^{n}+2^{n}=2^{n+1}\)。设取的三个数为\(2^i\),\(2^j\),\(2^k\),\(i\lej\lek\)。因为\(2^i+2^j>2^k\),所以\(j=k\)。(反证法易证)此时\(i\)任意取。注意不要重复取。将答案分为两类计算,\(i=j=k\)和\(i<j=k\)。(二)AC代码。#include<bits/stdc++.h>#define......
  • 20240327每日一题题解
    20240327每日一题题解Problem一些整数可能拥有以下的性质:性质1:是偶数;性质2:大于\(4\)且不大于\(12\)。小A喜欢这两个性质同时成立的整数;Uim喜欢这至少符合其中一种性质的整数;小B喜欢刚好有符合其中一个性质的整数;正妹喜欢不符合这两个性质的整数。现在给出一个......