theme：给定数字n,求[1,n]中只由字符0或1构成的数字个数。1<=n<=1e9
solution :只由01组成的数为：
1
10 11
100 101 110 111
1000 1001 1010 1011 1100 1101 1110 1111...
可以看出下一行为上一行每个数*10或*10+1的结果。所以我们可以从1开始递归，每次在当前数的基础上*10,*10+1,直到>n结束。
相当于预处理出从小到大的范围内满足条件的值然后lower_bound()找到n所处位置即可。
#include<bits/stdc++.h> #include<vector> #include<algorithm> using namespace std; #define far(i,t,n) for(int i=t;i<n;++i) #define pk(a) push_back(a) typedef long long ll; typedef unsigned long long ull; using namespace std; int ans=0; ll n; void cnt(ll x) { if(x>n) return; ++ans; cnt(x*10); cnt(x*10+1); } int main() { cin>>n; cnt(1); cout<<ans<<endl; }theme:给定n与h，求所有n个节点的二叉树中，高度<=h(包含根节点及叶子节点)的个数。
solution:用dp[i][j]表示i个节点的二叉树，高度<=h的个数，则状态转移方程为
, 0<=k<i
由转移方程知每个数是前一列若干数两两相乘，所以要一列一列地算，循环时j在外层循环，初始化所有dp[0][j]=1
#include<bits/stdc++.h> #include<vector> #include<algorithm> using namespace std; #define far(i,t,n) for(int i=t;i<n;++i) #define pk(a) push_back(a) typedef long long ll; typedef unsigned long long ull; using namespace std; ll dp[40][40]; void getDp(int n) { for(int i=0;i<=n;++i) dp[0][i]=1; for(int j=1;j<=n;++j) { for(int i=1;i<=n;++i) for(int k=0;k<i;++k) { dp[i][j]+=dp[k][j-1]*dp[i-k-1][j-1]; } } } int main() { int n,h; cin>>n>>h; getDp(n); ll ans=dp[n][n]-dp[n][h-1]; cout<<ans<<"\n"; }theme:给定n个点和m条边，要求最终达到每个节点都属于且只属于一个经过所有节点的环，问最少还要添加多少条边 。
solution:由题意知最终要形成一个环，所以最终所有节点的度都为2。用并查集，
首先将输入的图形存入并查集形成多个连通分量。并记录每个节点的度。判断是否有度>2的点，直接输出NO。
否则从小到大遍历每个节点，若该节点度<2,则将它与最小的度<2且与它不在同一个并查集的点相连，遍历一遍后整个图将变成一条链。
连接两个度为1的端点，此时形成了一个大环。
最后再判断一下所有节点是不是属于同一个并查集，避免形成多个环。
注意可以由自圈与重边。
#include<bits/stdc++.h> #include<vector> #include<algorithm> using namespace std; #define far(i,t,n) for(int i=t;i<n;++i) #define pk(a) push_back(a) typedef long long ll; typedef unsigned long long ull; using namespace std; int fa[100]; int degree[100]; vector<pair<int,int>>ans; void init(int n) { for(int i=0; i<=n; ++i) fa[i]=i; } int Find(int x) { return fa[x]==x?x:fa[x]=Find(fa[x]); } void unit(int x,int y) { x=Find(x); y=Find(y); fa[y]=x; } int main() { int n,m; while(cin>>n>>m) { ans.clear(); memset(degree,0,sizeof(degree)); init(n); far(i,0,m) { int x,y; scanf("%d%d",&x,&y); degree[x]++; degree[y]++; unit(x,y); } far(i,1,n+1) if(degree[i]>2) { cout<<"NO\n"; return 0; } //连成一条链 far(i,1,n+1) { far(j,i+1,n+1) if(degree[j]<=1&°ree[i]<=1&&Find(i)!=Find(j)) { degree[j]++; degree[i]++; unit(i,j); ans.push_back({i,j}); } } far(i,1,n+1) if(degree[i]>2) { cout<<"NO\n"; return 0; } //连端点成环 int s=0,e=0; far(i,1,n+1) { if(degree[i]<=1) { if(!s) s=e=i; else { if(i!=s) { if(e==s) e=i; } } } } if(s!=0&&e!=0) { ans.push_back({s,e}); unit(s,e); degree[s]++; degree[e]++; } for(int i=1; i<=n; ++i) if(Find(i)!=Find(1)||degree[i]!=2) { cout<<"NO\n"; return 0; } cout<<"YES\n"; int sz=ans.size(); cout<<sz<<"\n"; sort(ans.begin(),ans.end()); far(i,0,sz) printf("%d %d\n",ans[i].first,ans[i].second); } }
