首页 > 其他分享 >洛谷P1037 [NOIP2002 普及组] 产生数

洛谷P1037 [NOIP2002 普及组] 产生数

时间:2022-08-18 14:25:49浏览次数:107  
标签:__ 10 ch 洛谷 NOIP2002 int rep P1037 vis

排列组合 QWQ

当我第一眼看见这到题,K 才 15???,于是默默的打出了暴搜。
以我这么高(la)超(ji)的水平,当然是
TLE.....
对着屏幕一呆,70行代码。。。。

步入正题:

再打深搜,那是不可能的。
发现:总方案数不就是对于每一个数的方案数乘起来吗?

注意

  1. 对于数字a,b,c, 若a可以变成b,b可以变成c,那么a就可以变成c。如何解决呢?_____(水水的floyd)。
  2. 注意到(n < $10^{30}$) 。 所以...高精度?(没错)no~ no~ no~,可以用__int128。

算法设计:

  1. 读入,顺便将u , v存入二维表$vis$, $vis[i][j]$表示 i 到 j是否可变。
  2. 跑一遍floyd;
  3. 将点 i (0 <= i <= 9)的出度个数用be[]数组存起来。
  4. ans将$be[i]$ 一个一个乘起来
  5. 完美输出

AC Code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N = 100,INF=1e9,mod=INF+7;
int be[N];
bool vis[N][N];

__int128 read()
{
    __int128 f=1,w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        w=w*10+ch-'0';
        ch=getchar();
    }
    return f*w;
}
void print(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
int main()
{
	__int128 ans=1,n;
	int k,a,b;
	n = read();
	cin >> k;
	rep(i,1,k){
		cin >> a >> b;
		vis[a][b] = 1;
	}
	rep(k,0,9)rep(i,0,9)rep(j,0,9)if(i==j || (vis[i][k] && vis[k][j]))vis[i][j] = true;
	rep(i,0,9)
		rep(j,0,9)
			if(vis[i][j])be[i]++;	
	while(n){
		ans *= be[n%10];	
		n/=10;
	}
	print(ans);	
	return 0;
}

记得点个赞哟~~

标签:__,10,ch,洛谷,NOIP2002,int,rep,P1037,vis
From: https://www.cnblogs.com/Vanczyx/p/16598551.html

相关文章

  • P1507 洛谷 理解与分析
    题目大意食品的体积就是01背包问题中的体积也就是w数组食品的所含卡路里就是01背包问题中的价值也就是v数组所以这就是一道01背包问题的模板题题目分析使......
  • 洛谷 P3157 [CQOI2011]动态逆序对
    Description对于序列\(a\),它的逆序对数定义为集合\[\{(i,j)|i<j\anda_i>a_j\}\]中的元素个数。现在给出\(1\simn\)的一个排列,按照某种顺序依次删除\(m\)个......
  • 洛谷P1972HH的项链 题解
    P1972[SDOI2009]HH的项链题目描述HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含......
  • [NOIP2002 提高组] 均分纸牌
    题目链接:https://www.luogu.com.cn/problem/P1031试题分析:首先分析样例:输入样例后,我们要先求出平均值,进而求出与平均值的差值: 我们能够得到三次移动:1.  7向右-4变......
  • 洛谷 P6242 【模板】线段树 3 吉司机线段树 区间取最小值 维护历史最大值和区间和
    题目背景本题是线段树维护区间最值操作与区间历史最值的模板。题目描述给出一个长度为 nn 的数列 AA,同时定义一个辅助数组 BB,BB 开始与 AA 完全相同。接下来......
  • 洛谷 P3964 松鼠聚会
    前言由于未知原因,解密被取消了。其实就是我懒$\color{white}{恭喜你发现本彩蛋!Name:UR\next\\\Password:Zjd6MWpnMjZhNA==空格\to下划线}$正文题面有......
  • 洛谷P1714切蛋糕题解
    P1714切蛋糕题目描述今天是小Z的生日,同学们为他带来了一块蛋糕。这块蛋糕是一个长方体,被用不同色彩分成了\(n\)个相同的小块,每小块都有对应的幸运值。小Z作......
  • 洛谷P2622 关灯问题II引发的关于DP实现形式及后效性的思考
      动态规划要求已经求解的子问题不受后续阶段的影响,即无后效性。而在这种递推的实现方式中,后面枚举的状态可能更新前面已经枚举过的状态。也就是说,这种递推的实现方式是......
  • 洛谷 P1654 OSU!
    思路考虑\(DP\)转移,设\(F[i]\)表示长度为\(i\)序列的期望分数。得到如下转移:\(F[i]=(F[i-1]-A[i-1]+A[i])p_i+F[i-1](1-p_i)\)其中\(A[i]\)的意义是:以\(i\)......
  • 洛谷-P2486 染色
    染色树链剖分考虑如果在数列上的话,就是用线段树处理这个问题线段树记录答案,并且处理区间和并的问题:如果区间合并的地方颜色相同,则加和后的答案要减一因此维护所有线段......