P2241 统计方形(数据加强版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; ll n,m,z,c; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(i==j) z+=(n-i)*(m-j); else c+=(n-i)*(m-j); } } cout<<z<<" "<<c<<" "<<"\n"; return 0; }
P2089 烤鸡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int n,ans=0,a[10000][10],b[10]; void DFS(int tot,int cnt){ if(cnt==10){ if(tot==n){ for(int i=0;i<10;i++) a[ans][i]=b[i]; ans++; } }else if(tot>=n) ; else{ for(int i=1;i<=3;i++){ b[cnt]=i; DFS(tot+i,cnt+1); } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; DFS(0,0); cout<<ans<<"\n"; for(int i=0;i<ans;i++){ for(int j=0;j<10;j++) cout<<a[i][j]<<" "; cout<<"\n"; } return 0; }
P1008 [NOIP1998 普及组] 三连击 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int num[10]={0}; bool vis[10]={0}; int f(int m){ int sum=0; for(int i=3*m-2;i<=3*m;i++){ sum*=10; sum+=num[i]; } return sum; } void DFS(int n){ if(n==10&&f(1)*2==f(2)*1&&f(1)*3==f(3)*1){ cout<<f(1)<<" "<<f(2)<<" "<<f(3)<<endl; return ; } for(int i=1;i<=9;i++){ if(!vis[i]){ num[n]=i; vis[i]=1; DFS(n+1); vis[i]=0; } } return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); DFS(1); return 0; }
P1618 三连击(升级版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int a,b,c,num[10]={0}; bool vis[10]={0},ans=false; int f(int m){ int sum=0; for(int i=3*m-2;i<=3*m;i++){ sum*=10; sum+=num[i]; } return sum; } void DFS(int n){ if(n==10&&f(1)*b==f(2)*a&&f(1)*c==f(3)*a){ cout<<f(1)<<" "<<f(2)<<" "<<f(3)<<endl; ans=true; return ; } for(int i=1;i<=9;i++){ if(!vis[i]){ num[n]=i; vis[i]=1; DFS(n+1); vis[i]=0; } } return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>a>>b>>c; DFS(1); if(!ans) cout<<"No!!!"; return 0; }
P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int n,k,a[30],ans=0; bool isprime(int x){ if(x==1) return false; for(int i=2;i<=sqrt(x);i++){ if(x%i==0) return false; } return true; } void DFS(int last,int sum,int cur){ if(cur==k){ if(isprime(sum)) ans++; return ; } for(int i=last;i<=n;i++) DFS(i+1,sum+a[i],cur+1); } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; DFS(1,0,0); cout<<ans<<endl; return 0; }
P1157 组合的输出 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int n,r,a[100]; void DFS(int t){ if(t>r){ for(int i=1;i<=r;i++) cout<<setw(3)<<a[i]; cout<<endl; return ; } for(int i=a[t-1]+1;i<=n;i++){ a[t]=i; DFS(t+1); } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>r; DFS(1); return 0; }
P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int n,vis[100],a[100]; void DFS(int k){ if(k==n){ for(int i=1;i<=n;i++) cout<<setw(5)<<a[i]; cout<<endl; return ; } for(int i=1;i<=n;i++){ if(!vis[i]){ vis[i]=1; a[k+1]=i; DFS(k+1); vis[i]=0; } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; DFS(0); return 0; }
P1088 [NOIP2004 普及组] 火星人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const int maxn=1e4+10; int n,m,a[maxn],cnt,flag; bool vis[maxn]; void DFS(int step){ if(flag) return ; if(step>n){ cnt++; if(cnt==m+1){ for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<"\n"; flag=true; } return ; } for(int i=1;i<=n;i++){ if(cnt==0) i=a[step]; if(!vis[i]){ vis[i]=1; a[step]=i; DFS(step+1); vis[i]=0; } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; DFS(1); return 0; }
P3392 涂国旗 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int n,m,ans=INF,w[60],b[60],r[60]; string s; int check(char ch){ int tot=0; for(int i=0;i<m;i++) if(s[i]!=ch) ++tot; return tot; } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>s; w[i]=w[i-1]+check('W'); b[i]=b[i-1]+check('B'); r[i]=r[i-1]+check('R'); } for(int i=1;i<n-1;i++) for(int j=i+1;j<n;j++) ans=min(ans,w[i]+b[j]-b[i]+r[n]-r[j]); cout<<ans<<"\n"; return 0; }
P3654 First Step (ファーストステップ) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int r,c,k,ans,dir[2][2]={{0,1},{1,0}}; char mp[110][110]; void DFS(int x,int y,int i,int j){ if(j>k){ ans++; return ; } if(mp[x][y]!='.' || x<0 || y<0 || x>=r || y>=c) return ; DFS(x+dir[i][0],y+dir[i][1],i,j+1); return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>r>>c>>k; for(int i=0;i<r;i++) for(int j=0;j<c;j++) cin>>mp[i][j]; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ if(mp[i][j]=='.'){ for(int k=0;k<2;k++) DFS(i,j,k,1); } } } if(k==1) ans/=2; cout<<ans<<endl; return 0; }
P1217 [USACO1.5] 回文质数 Prime Palindromes - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; bool ispalindrome(int x); bool isprime(int x); int main(){ int a,b; cin>>a>>b; for(int i=a;i<=b;i++){ if(ispalindrome(i)&&isprime(i)){ cout<<i<<endl; } } return 0; } bool ispalindrome(int x){ int c[10],count=0; while(x!=0){ c[count++]=x%10; x/=10; } for(int i=0;i<count;i++,count--){ if(c[count-1]!=c[i]){ return false; } } return true; } bool isprime(int x){ for(int i=2;i<=sqrt(x);i++){ if(x%i==0){ return false; } } return true; }
P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; //0 1 2 3 4 5 6 7 8 9 //6 2 5 5 4 5 6 3 7 6 int n,ans=0,x[1001]={6,2,5,5,4,5,6,3,7,6},b[4]; void DFS(int t){ for(int i=0;i<=999;i++){ if(n-x[i]>=0){ b[t]=i; n-=x[i]; if(t==3){ if(b[1]+b[2]==b[3] && n==0) ans++; }else DFS(t+1); n+=x[i]; } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; n-=4; for(int i=10;i<=999;i++) x[i]=x[i/10]+x[i%10]; DFS(1); cout<<ans<<"\n"; return 0; }
P3799 妖梦拼木棒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const int mod=1e9+7; const int N=1e5+10; ll n,ans,maxa,a[N],num[N]; ll C(ll x,ll k){ return (k==1ll?x:x*(x-1ll)/2ll)%mod; } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; maxa=max(maxa,a[i]); num[a[i]]++; } for(int i=2;i<=maxa;i++){ if(num[i]>=2ll){ ll t=C(num[i],2ll)%mod; for(int j=1;j<=i/2;j++){ if(j!=i-j&&num[j]>=1&&num[i-j]>=1){ ans+=t*C(num[j],1)*C(num[i-j],1)%mod; } if(j==i-j&&num[j]>=2){ ans+=t*C(num[j],2)%mod; } ans%=mod; } } } cout<<ans<<"\n"; return 0; }
P2392 kkksc03考前临时抱佛脚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int s[5],a[5][20],ans,res=0,l,r; void DFS(int sub,int pos){ if(pos>s[sub]){ ans=min(ans,max(l,r)); return ; } l+=a[sub][pos]; DFS(sub,pos+1); l-=a[sub][pos]; r+=a[sub][pos]; DFS(sub,pos+1); r-=a[sub][pos]; } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>s[1]>>s[2]>>s[3]>>s[4]; for(int i=1;i<=4;i++){ ans=INF; l=0,r=0; for(int j=1;j<=s[i];j++) cin>>a[i][j]; DFS(i,1); res+=ans; } cout<<res<<endl; return 0; }
P2036 [COCI2008-2009 #2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int n,s[15],b[15],vis[15],ss=1,bb=0,ans=INF; void DFS(int cnt){ if(cnt>n) return ; for(int i=1;i<=n;i++){ if(!vis[i]){ ss*=s[i]; bb+=b[i]; ans=min(ans,abs(ss-bb)); vis[i]=1; DFS(cnt+1); vis[i]=0; ss/=s[i]; bb-=b[i]; } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>s[i]>>b[i]; DFS(1); cout<<ans<<endl; return 0; }
标签:洛谷,int,ll,算法,long,枚举,DFS,ans,const From: https://www.cnblogs.com/accbulb/p/18030961