T1 统计数字
题目
【题目描述】
设 S(N ) 表示 N 的各位数字之和，如 S(484) = 4+8+4 = 16， S(22) = 2+2 = 4。
如果一个正整数满足 S(x*x) = S(x) *S(x)，我们称之为 Rabbit N umber。比方说，22 就是一个 Rabbit N umber，因为 S(484) = S(22) *S(22)。
现在，给出一个区间 [L, R]，求在该区间内的 Rabbit N umber 的个数。
【输入格式】
输入仅一行，为空格隔开的两个数 L 和 R。
【输出格式】
输出仅一行一个整数，表示所求 Rabbit N umber 的个数。
【输入样例】
58 484
【输出样例】
24
【数据规模】
1 <= L <= R <= 10^9
解析
看完题目第一反应：从L枚举到R，依次判断每个数是不是Rabbit N umber。然而数据规模是109，显然超时。
不过没事，打完暴力后，随便试一些数字，看看有没有什么规律。
1~1000内的Rabbit N umber如下：
1 2 3 10 11 12 13 20 21 22 30 31 100 101 102 103 110 111 112 113 120 121 122 130 200 201 202 210 211 212 220 221 300 301 310 311 1000
不难发现，无论是哪一位上，都没有大于3的数字（更大的范围内也是，可以自己试试），至于为什么，这里便不给出详细证明了（因为本蒟蒻不会）。
所以便有了剪纸：任何位上有大于3的数字就跳过。
于是便有了两种做法：
- dfs+剪纸
- 打表+二分
打表这里就不说了（太麻烦），这里来讲dfs做法：
dfs(int temp):temp可以理解为当前数是由temp+一个新的个位数组成的数，具体看代码就懂了。
从temp=0开始搜，每次dfs函数里处理个位为0 1 2 3的数，满足条件且在L~R的范围内就累加个数，
处理完后，如果数字小于等于R/10的话，就dfs(x)（即还可以增加位数）。
最后输出总个数就好了，别忘了开long long，至于S(x)，直接模拟就好了。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; long long read() { long long num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } long long l,r,ans; int S(long long x) { int n=0; while(x>0) { n+=x%10; x/=10; } return n; } void dfs(int temp) { for(int i=0;i<=3;i++) { long long x=temp*10+i; int s=S(x); if(x==0||S(x*x)!=s*s) continue; if(l<=x&&r>=x) ans++; if(x<=r/10) dfs(x); } } int main() { //freopen("rabbit.in","r",stdin); //freopen("rabbit.out","w",stdout); l=read(),r=read(); dfs(0); cout<<ans; return 0; }
T2 数边方案
题目
【题目描述】
给你一张有n个点m条边的无向连通图，每条边有边权，设disai表示这张图中点i到点1的最短距离。
现在要求你在这张图中删去m-(n-1)条边，使得这张图变成一棵树，设disbi表示这棵树中点i到点1的最短距离。 现在请你求出，有多少种删边方案，使得对于任意的i，都有disai=disbi。
【输入格式】
第一行包含两个正整数n,m，表示无向连通图的点数和边数。
接下来有m行，每行有3个正整数u,v,w，表示点u和点v之间有一条边权为w的无向边。
数据保证无重边、无自环。
【输出格式】
输出一行一个整数，表示满足条件的方案数对2147483647取模的结果。
【输入样例】
3 3 1 2 2 1 3 1 2 3 1
【输出样例】
2
【数据规模】
解析
据说有个叫最短路图的东西，就是把原图中满足dis(u)+w=dis(v)的边(u,v,w)保留下来构成的子图。
本题中，边权一定为正整数，所以最短路图是一个有向无环图，答案只需枚举有向无环图中生成树的数量即可，然而仍然过不了。
事实上，在构造最短路图的过程中，就是在给每个点选一个父亲，而可选父亲总数就是这个点的入度，显然答案为入度之积。
具体实现是用最短路，本蒟蒻采用的是Dijkstra。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> using namespace std; priority_queue<pair<int,int> > q; const int N=1010,M=1000100; const long long mod=2147483647; int n,m,head[N],ver[M],edge[M],from[M],tot,next[M],d[N],deg[N]; long long ans=1; bool v[N]; void add(int x,int y,int z) { ver[++tot]=y,edge[tot]=z,from[tot]=x,next[tot]=head[x],head[x]=tot; } void dijkstra() { memset(d,0x7f7f7f7f,sizeof(d)); memset(v,false,sizeof(v)); d[1]=0; q.push(make_pair(0,1)); while(q.size()) { int x=q.top().second; q.pop(); if