|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <stdio.h> int main() { int n,t; while(scanf("%d",&n)) { if(n==0) break; int c[205]={}; t = 1%n; int i=0; while(1) { i++; if(c[t]) { for(int j=c[t];j<i;j++) printf("1"); for(int j=c[t]-1;j>=0;j--) printf("0"); printf("\n"); break; } c[t]=i; t =(t*10+1)%n; } } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include <iostream> #include <string.h> #include <vector> using namespace std; int visit[110]; int r[110]; int graph[110][110]; vector<int> vb; int mx; int n,k; int judge(int a) { for(int i=1;i<=n;i++) { if(graph[a][i]) { if(visit[i]==1 && i!=a) return 0; } } return 1; } int backtrack(int node) { if(node>n) { vb.clear(); int cnt=0; for(int i=1;i<=n;i++) { if(visit[i]) { cnt++; vb.push_back(i); } } if(cnt>mx) { mx=cnt; for(int i=0;i<vb.size();i++) r[i+1]=vb[i]; } } else { visit[node]=0; backtrack(node+1); visit[node]=1; if(judge(node)) backtrack(node+1); visit[node]=0; } } int main() { int t,a,b; cin>>t; while(t--) { memset(visit,0,sizeof(visit)); memset(graph,0,sizeof(graph)); cin>>n>>k; for(int i=0;i<k;i++) { cin>>a>>b; graph[a][b]=1; graph[b][a]=1; } mx=0; backtrack(1); cout<<mx<<"\n"; for(int i=1;i<=mx;i++) cout<<r[i]<<(i!=(mx)?" ":"\n"); } return 0; } |
Using binary search to find the minimum value,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <iostream> #include <string.h> #include <vector> #define ll long long using namespace std; ll b[505]; vector<int> res[505]; int main() { int t; int books,writer; cin>>t; while(t--) { cin>>books>>writer; ll total=0,minwrk=0,mid=0; for(int i=0;i<books;i++) { cin>>b[i]; total+=b[i]; if(minwrk<b[i]) minwrk = b[i]; } //bin search while(minwrk<total) { int required=1; ll sum=0; mid= (total+minwrk)/2; for(int i=0;i<books;i++) { if(sum+b[i]>mid) { required++; sum=0; } sum+=b[i]; } if(required>writer) minwrk=mid+1; else total=mid; } ll sum =0; int j=writer-1; for(int i=books-1;i>=0;i--) { if((sum+b[i])>total || j>i) { j--; sum=0; } sum+=b[i]; res[j].push_back(b[i]); } for(int i=0;i<writer;i++) { for(int l=res[i].size()-1;l>=0;l--) { if(l!=res[i].size()-1) cout<<" "<<res[i][l]; else cout<<res[i][l]; } res[i].clear(); if(i!=writer-1) cout<<" / "; } cout<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <stdio.h> #include <string.h> #include <string> #include <iostream> using namespace std; int table[1001][1001]; int main() { int n,len; string s; cin>>n; getchar(); while(n--) { getline(cin,s); if(s=="") { cout<<0<<"\n"; continue; } memset(table,0,sizeof(table)); len = s.size(); for(int i=0;i<=len;i++) { table[i][i]=1; } for(int length=2;length<=len;length++) { for(int i=0;i<=len-length+1;i++) { int end=i+length-1; if(end<0 || end>=len) continue; if(s[i]==s[end] && length==2) { table[i][end]=2; } else if(s[i]==s[end]) { table[i][end]=table[i+1][end-1]+2; } else { table[i][end] = max(table[i+1][end],table[i][end-1]); } } } cout<<table[0][len-1]<<"\n"; } return 0; } |
Meet in the middle  and binary search algorithm is used to solve this problem.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include <iostream> #include <string.h> #include <algorithm> #include <map> using namespace std; int A[4001]; int B[4001]; int C[4001]; int D[4001]; int E[16008001]; int F[16008001]; //map<int,int> mp; struct myHash { int value; int valueOccuredNumberOfTimes; }FF[16008001]; int main() { int t,n,x,cnt,a; int low,mid,high; int k,l; cin>>t; while(t--) { cin>>n; cnt=0; //mp.clear(); for(int i=0;i<n;i++) { cin>>A[i]>>B[i]>>C[i]>>D[i]; } k=0; l=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { E[k++]=A[i]+B[j]; F[l++]=C[i]+D[j]; } } sort(F,F+l); FF[0].value = F[0]; FF[0].valueOccuredNumberOfTimes=1; int ind=0; for(int i=1;i<l;i++) { if(F[i]==F[i-1]) { FF[ind].valueOccuredNumberOfTimes+=1; } else { ind+=1; FF[ind].value=F[i]; FF[ind].valueOccuredNumberOfTimes=1; } } ind+=1; for(int i=0;i<k;i++) { x = E[i]*(-1); low=0; high=ind; while((high-low)>1) { mid=(low+high)/2; if(FF[mid].value<x) low=mid; else high=mid; } if(FF[low].value==x) { cnt+=FF[low].valueOccuredNumberOfTimes; //cout<<FF[low].value<<" "<<FF[low].valueOccuredNumberOfTimes<<"\n"; } else if(FF[high].value==x) { cnt+=FF[high].valueOccuredNumberOfTimes; } } cout<<cnt<<"\n"; if(t) cout<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int mat[25][25]; int dist[25][25]; vector<int> vb[25]; bool visit[25]; int fire; int kase=1; int mx=0,cnt=0; int res[25]; void dfs(int s,int k) { if(s==fire) { cnt++; for(int i=0;i<k;i++) { cout<<res[i]<<(i==(k-1)?"\n":" "); } return; } //for(int i=0;i<vb[s].size();i++) for(int i=1;i<=mx;i++) { if(visit[i]) continue; if(!mat[s][i]) continue; if(!dist[i][fire]) continue; visit[i]=1; res[k] = i; dfs(i,k+1); visit[i]=0; //int d = vb[s][i]; //if(dist[s][d]==0)// //continue; //if(visit[d]==0) //{ //visit[d]=1; //res[k]=d; //dfs(d,k+1); //visit[d]=0; //} } } void floyd() { for(int i=1;i<=mx;i++) { for(int j=1;j<=mx;j++) { for(int k=1;k<=mx;k++) { if(dist[j][i]==1 && dist[i][k]==1) dist[j][k] = 1; } } } } int main() { int a,b,k; for(int i=0;i<25;i++) { res[i] = 0; } while(scanf("%d",&fire)!=EOF)//cin>>fire { mx=0; memset(mat,0,sizeof(mat)); memset(dist,0,sizeof(dist)); while(cin>>a) { cin>>b; if(a==0 && b==0) { break; } dist[a][b]=1; dist[b][a]=1; mat[a][b]=1; mat[b][a]=1; //vb[a].push_back(b); //vb[b].push_back(a); mx = max(mx,max(a,b)); } cnt=0; /*if(fire==1) { cout<<"There are "<<0<<" routes from the firestation to streetcorner "<<fire<<".\n"; }*/ //else memset(visit,0,sizeof(visit)); visit[1]=1; k=0; res[k]=1; k+=1; floyd(); //for(int i=1; i<=mx; i++) //sort(vb[i].begin(), vb[i].end()); cout<<"CASE "<<kase++<<":\n"; dfs(1,k); cout<<"There are "<<cnt<<" routes from the firestation to streetcorner "<<fire<<".\n"; } return 0; } |
Theory: This is an np-hard problem. As the degree of each node can be at most 3 so using dfs ,it can be solved. Follow the link
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream> #include <stdio.h> #include <vector> #include <string.h> using namespace std; //vector<int> vb[30]; int mat[30][30]; int visit[30]; int n,m; int length; void search(int a,int len) { if(len>length) length = len; for(int i=0;i<n;i++) { //a=vb[step][i]; if(mat[a][i]>0) { mat[a][i]-=1; mat[i][a]-=1; search(i,len+1); mat[a][i]++; mat[i][a]++; } } } int main() { int a,b; //memset(visit,0,sizeof(visit)); while(cin>>n>>m) { if(n==0 && m==0) break; memset(mat,0,sizeof(mat)); //for(int i=0;i<n;i++) //vb[i].clear(); length=0; for(int i=0;i<m;i++) { cin>>a>>b; //vb[a].push_back(b); //vb[b].push_back(a); mat[a][b]++; mat[b][a]++; } int len =0; for(int i=0;i<n;i++) { //visit[0]=1; search(i,0); //visit[0]=0; } cout<<length<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <stdio.h> using namespace std; int prime[40]={0,0,2,3,0,5,0,7,0,0,0,11, 0,13,0,0,0,17,0,19,0,0, 0,23,0,0,0,0,0,29,0,31,0, 0,0,0,0,37,0,0}; bool visit[17]; int numbers[17]; int n; int search(int step) { if(step==n) { if(prime[1+numbers[step-1]]) { for(int i=0;i<n;i++) cout<<numbers[i]<<((i==(n-1))?"\n":" "); } } for(int i=1;i<=n;i++) { if(prime[numbers[step-1]+i] && !visit[i]) { visit[i]=1; numbers[step]=i; search(step+1); visit[i]=0; } } } int main() { int kase=1; int c=0; while(cin>>n) { if(c) cout<<"\n"; c=1; cout<<"Case "<<kase++<<":\n"; numbers[0]=1; visit[1]=1; search(1); } return 0; } |
This problem can be solved using dfs,bfs or union find algorithm, BFS solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> #include <stdio.h> #include <string.h> #include <map> #include <queue> #include <string> using namespace std; int to; bool visit[26]; int graph[26][26]; void bfs(int a) { int b; queue<int> q; q.push(a); while(!q.empty()) { b =q.front(); q.pop(); visit[b]=1; for(int i=0;i<=to;i++) { if(graph[b][i]==1 && visit[i]==0) { q.push(i); visit[i]=1; graph[b][i]=0; graph[i][b]=0; } } } } int main() { int t,c=0; string s; cin>>t; scanf("\n"); while(t--) { getline(cin,s); to = s[0]-65; memset(graph,0,sizeof(graph)); memset(visit,0,sizeof(visit)); while(1) { getline(cin,s); if(s=="") break; graph[s[0]-65][s[1]-65]=1; graph[s[1]-65][s[0]-65]=1; } int cnt=0; for(int i=0;i<=to;i++) { if(visit[i]==0) { bfs(i); cnt++; } } cout<<cnt<<endl; if(t) cout<<endl; if(c==t) break; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #define ll long long using namespace std; int arr[23]={0,1,8,27,64,125,216,343,512,729, 1000,1331,1728,2197,2744,3375,4096,4913,5832, 6859,8000,9261 }; ll ways[10005]; int main() { for(int j=0;j<10005;j++) ways[j]= 0; ways[0]=1; for(int i=1;i<=21;i++) { for(int j=arr[i];j<10005;j++) ways[j]+=ways[j-arr[i]]; } int n; while(cin>>n) { //cout<<calc(1,n)<<"\n"; cout<<ways[n]<<"\n"; } return 0; } |