题意：多米诺骨牌，求有多少骨牌会被推掉
#include<bits/stdc++.h> using namespace std; vector<int> v[10005]; int vis[10005],num; void dfs(int z) { vis[z]=1; num++; for(int i=0;i<v[z].size();i++) { if(vis[v[z][i]]==0) { dfs(v[z][i]); } } } int main() { int t; scanf("%d",&t); while(t--) { int n,m,l; memset(vis,0,sizeof(vis)); scanf("%d%d%d",&n,&m,&l); for(int i=0;i<=n;i++) { v[i].clear(); } for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y); } num=0; for(int i=1;i<=l;i++) { int z; scanf("%d",&z); if(vis[z]==0)dfs(z); } printf("%d\n",num); } }
//深搜
题意：给一个数n，求1~n中包含49的数的个数
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll d; ll dp[25][3]; void init() { dp[0][0]=1;//dp[i][0]表示i位数内不含49的个数 dp[0][1]=dp[0][2]=0;//dp[i][1]表示i位数内以9为首的不含49的个数 for(int i=1;i<20;i++) //dp[i][2]表示i位数内含49的个数 { dp[i][0]=10*dp[i-1][0]-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=10*dp[i-1][2]+dp[i-1][1]; } } ll check(ll d) { int num[25]={0},len=0; while(d>0) { num[++len]=d%10; d/=10; } ll sum=0; int flag=0; for(int i=len;i>=1;i--)//逐位添加 { sum+=dp[i-1][2]*num[i]; if(flag) sum+=dp[i-1][0]*num[i]; else { if(num[i]>4)sum+=dp[i-1][1]; } if(num[i+1]==4&&num[i]==9)flag=1; } if(flag)sum++; return sum; } int main() { int t; init(); scanf("%d",&t); while(t--) { scanf("%lld",&d); printf("%lld\n",check(d)); } }
//数位dp
题意：从起点(x,y)开始可向上或者向右移动lcm(x,y)步，现在给出一个终点，求有多少个点作为起点可到达该终点
思路：设起点为(qt,pt),t为最小公因数，最小公倍数为qpt，故终点为(qt,pt+qpt)--->(qt,(1+q)pt), 因此可逆推出 终点(x,y),x<y时，若y%(x+1)==0则有一个点可作为起始点
#include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); for(int i=1;i<=t;i++) { long long a,b,num=1; scanf("%lld%lld",&a,&b); printf("Case #%d: ",i); int d=__gcd(a,b); a/=d; b/=d; while(1) { if(a>b)swap(a,b); if(b%(a+1)) break; b=b/(a+1); num++; } printf("%lld\n",num); } }
//逆推
题意：求一个序列的连续子序列之和能否被m整除
#include<bits/stdc++.h> using namespace std; int num[5005]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); int flag=0,sum=0; memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); sum+=x; if(sum%m==0)flag=1;//前缀和被m整除 if(num[sum%m]==1)flag=1;//当序列的前缀和出现两次除m余数相同时，说明，连续子序列和存在被m整除的情况 num[sum%m]++; } if(flag)printf("YES\n"); else printf("NO\n"); } }
题意：先给出n个店的店名，再给出m个n行，每行为涨价值以及对应的店名，求memory店铺的商品价值在所有店铺商品价值的排名
#include<bits/stdc++.h> using namespace std; map<string,int> m; int money[10005]; int main() { int n,t,flag; scanf("%d",&n); getchar(); for(int i=1;i<=n;i++) { string s; char ch; while(ch=getchar()) { if(ch==‘\n‘)break; s+=ch; } m[s]=i; if(s=="memory") flag=i; } scanf("%d",&t); while(t--) { for(int i=1;i<=n;i++) { int in; scanf("%d",&in); string s; char ch; getchar(); while(ch=getchar()) { if(ch==‘\n‘)break; s+=ch; } money[m[s]]+=in; } int sum=0; for(int i=1;i<=n;i++) { if(money[i]>money[flag])sum++; } printf("%d\n",sum+1); } }
//map容器
题意："A > B","A = B","A < B"根据这三类信息判断信息是冲突，是否完整。
#include<bits/stdc++.h> using namespace std; int x[20005],y[20005],f[10005],in[20005]; vector<int> vec[10005]; char ch[20005]; int n,m; int find(int x) { return f[x]==x?x:find(f[x]); } void work() { queue<int> q; int num=0,ans=0; for(int i=1;i<=n;i++) { int t1=find(i); if(t1==i) { if(in[t1]==0) q.push(t1);//添加0入度点进入队列 num++;//记录点数 } } int flag=0; while(q.size()) { if(q.size()>1)//队列出现超过一个元素，说明信息不完整，有至少一对点的大小关系不能确定 { flag=1; } int z=q.front(); q.pop(); ans++; for(int i=0;i<vec[z].size();i++) { int t1=find(vec[z][i]); in[t1]--; if(in[t1]==0)q.push(t1); } } if(ans!=num) printf("CONFLICT\n"); else { if(flag) printf("UNCERTAIN\n"); else printf("OK\n"); } }
//并查集+拓扑排序
原文：https://www.cnblogs.com/llhsbg/p/11789493.html