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; }View Code
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(v[x]) continue; v[x]=1; for(int i=head[x];i;i=next[i]) { int y=ver[i],z=edge[i]; if(d[y]>d[x]+z) { d[y]=d[x]+z; q.push(make_pair(-d[y],y)); } } } for(int i=1;i<=tot;i++) { int x=from[i],y=ver[i],z=edge[i]; if(d[x]+z==d[y]) deg[y]++; } for(int i=1;i<=n;i++) if(deg[i]) ans=(1LL*ans*deg[i])%mod; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } dijkstra(); cout<<ans; return 0; }View Code
T3 開根號
題目
【題目描述】
【輸入格式】
輸入包含多組資料，每組資料包含一行兩個正整數L,R，
檔案以0 0結尾（結尾不需要輸出），
【輸出格式】
對于每組資料，輸出一行表示答案，保證答案在[0,263)范圍內，
【樣例輸入】
2 10 248832 248832 0 0
【樣例輸出】
13 5
【資料規模】
決議
可怕的數論題~~~
先把區間求和用前綴和表示，所以只需求[1,n]的答案，
依次求每個數的f(i)很麻煩，考慮求[1,n]中f(i)=k的個數，其個數用g(k)表示，
用p(k)表示[1,n]中開k次方還是正整數的數的個數，可以得到p(k)=n1/k(向下取整)，
則
，
所以用遞推推出答案就可以了，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; const double eps=1e-10; long long l,r,f[100]; long long solve(long long x) { if(x<2) return 1; int num=0; for(int i=63;i>=2;i--) { f[i]=(long long)(pow(x,(double)1.0/i)+eps)-1; for(int j=i+i;j<=63;j+=i) f[i]-=f[j]; num+=f[i]*(i-1); } return num+x; } int main() { cin>>l>>r; while(l!=0&&r!=0) { cout<<solve(r)-solve(l-1)<<endl; cin>>l>>r; } return 0; }View Code
T4 旅行
題目
【題目描述】
【輸入格式】
第一行包含兩個非負整數n,k，含義如【題目描述】所述，
接下來n-1行，每行三個正整數u,v,w，表示u,v之間有一條邊權為w的邊，
【輸出格式】
輸出一行一個整數，表示答案，保證存在合法解，
【輸入樣例】
5 6 1 2 3 1 3 4 2 4 2 2 5 3
【輸出樣例】
4
【資料規模】
決議
不難發現：
- dis(u,v)=dis(u,1)+dis(v,1)，
- 如果經過的邊數為奇數，那么必定有一個點的深度為奇數，另一個點的深度為偶數，
所以將所有點按深度的奇偶來分類，于是就有了兩個序列a，b，只需求ai+bi的第k小值即可，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> using namespace std; const int N=100010; struct node { long long v; int p; node(long long a,int b):v(a),p(b){} bool operator < (const node &a) const { return v>a.v; } }; priority_queue<node> q; int head[N],ver[N<<1],edge[N<<1],next[N<<1],tot; long long dis[N],deep[N],a[N],b[N],cnta,cntb; void add(int x,int y,int z) { ver[++tot]=y,edge[tot]=z,next[tot]=head[x],head[x]=tot; } void dfs(int x,int fa) { for(int i=head[x];i;i=next[i]) { int y=ver[i],z=edge[i]; if(y==fa) continue; dis[y]=-dis[x]+z,deep[y]=deep[x]+1; dfs(y,x); } } int main() { int n,k; cin>>n>>k; for(int i=1;i<=n-1;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } dfs(1,0); for(int i=1;i<=n;i++) if(deep[i]&1) a[++cnta]=dis[i]; else b[++cntb]=dis[i]; sort(b+1,b+cntb+1); for(int i=1;i<=cnta;i++) q.push(node(a[i]+b[1],i)); for(int i=1;i<=cnta;i++) head[i]=1; while(k>1) { node t=q.top(); q.pop(); if((++head[t.p])<=cntb) q.push(node(a[t.p]+b[head[t.p]],t.p)); k--; } cout<<q.top().v; return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/100185.html
標籤：C++
上一篇：交換排序
下一篇：c++指標全攻略