数据量比较小，还是直接暴力吧。
1 #include<stdio.h> 2 int a[1000010]; 3 int F(int m); 4 int main() 5 { 6 int i,sum,n,m; 7 for(i=1;i<=1000000;i++) 8 a[i]=F(i); 9 while(scanf("%d%d",&n,&m)!=EOF) 10 { 11 if(n==0&&m==0) 12 break; 13 sum=0; 14 for(i=n;i<=m;i++) 15 if(a[i]==1) 16 sum++; 17 printf("%d ",sum); 18 } 19 return 0; 20 } 21 int F(int m) 22 { 23 int i; 24 while(m) 25 { 26 if(m%10==4||m%100==62) 27 return 0; 28 m/=10; 29 } 30 return 1; 31 }
汉诺塔的变型，增加了一根柱子，直接上队里大神写的代码。
1 #include<stdio.h> 2 3 long long a[70], b[70]; 4 5 int main() 6 { 7 int i, j; 8 for(i = 1; i <= 60; i++) 9 { 10 b[i] = ((long long)1 << i) - 1; 11 } 12 13 a[1] = 1; 14 a[2] = 3; 15 a[3] = 5; 16 for(i = 4; i <= 64; i++) 17 { 18 a[i] = 2 * a[i-2] + 3; 19 for(j = 1; j < i; j++) 20 { 21 if(a[i] >= 2*a[i-j-1] + 2*b[j] + 1) 22 { 23 a[i] = 2*a[i-j-1] + 2*b[j] + 1; 24 } 25 26 else 27 break; 28 } 29 } 30 while(scanf("%d", &i) != EOF) 31 { 32 printf("%lld ", a[i]); 33 } 34 }
HDU 2680 Choose the best route
多个起点，一个终点，反向存图，跑一遍Dijkstra，比较得出最短路即可。
1 #include<stdio.h> 2 #include<string.h> 3 #include<vector> 4 using namespace std; 5 6 const int maxn = 1010; 7 int e[maxn][maxn]; 8 int d[maxn], bk[maxn]; 9 const int inf = 99999999; 10 int n, m, s, w; 11 12 void D(int s) { 13 for(int i = 0; i <= n; i++) { 14 d[i] = e[s][i]; 15 } 16 17 memset(bk, 0, sizeof(bk)); 18 bk[s] = 1; 19 20 for(int i = 1; i <= n; i++) { 21 int mind = inf, u = -1; 22 for(int j = 1; j <= n; j++) { 23 if(bk[j] == 0 && mind > d[j]) { 24 mind = d[j]; 25 u = j; 26 } 27 } 28 if(u == -1) 29 break; 30 bk[u] = 1; 31 32 for(int v = 1; v <= n; v++) { 33 if(d[v] > d[u] + e[u][v]) 34 d[v] = d[u] + e[u][v]; 35 } 36 } 37 } 38 39 int main() 40 { 41 while(scanf("%d%d%d", &n, &m, &s) != EOF) { 42 for(int i = 0; i <= n; i++) { 43 for(int j = 0; j <= n; j++) { 44 e[i][j] = (i == j ? 0 : inf); 45 } 46 } 47 for(int i = 0; i < m; i++) { 48 int u, v, ws; 49 scanf("%d%d%d", &u, &v, &ws); 50 if(ws < e[v][u]) 51 e[v][u] = ws; 52 } 53 scanf("%d", &w); 54 vector<int> a; 55 while(w--) { 56 int tmp; 57 scanf("%d", &tmp); 58 a.push_back(tmp); 59 } 60 61 D(s); 62 int ans = inf; 63 for(int i = 0; i < a.size(); i++) { 64 if(d[a[i]] < ans) 65 ans = d[a[i]]; 66 } 67 if(ans == inf) 68 printf("-1 "); 69 else 70 printf("%d ", ans); 71 } 72 return 0; 73 }
给出单词表，问单词中特殊词分别是哪些，特殊词就是一个单词通过重排还在单词表里，大小写不同也算出现。先将所有单词变为小写排个序（就不用真正的排列组合了），然后标记是否出现过，最后输出即可。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 int cmp1(struct data a,struct data b); 6 int cmp2(struct data a,struct data b); 7 void cpy(char *s1,char *s2); 8 struct data{ 9 char str1[25]; 10 char str2[25]; 11 int flag; 12 }; 13 data q[1010]; 14 int main() 15 { 16 int i=0,j,n,m; 17 while(scanf(" %s",q[i].str1)) 18 { 19 q[i].flag=0; 20 if(strcmp(q[i].str1,"#")==0) 21 break; 22 cpy(q[i].str2,q[i].str1); 23 sort(q[i].str2,q[i].str2+strlen(q[i].str2)); 24 i++; 25 } 26 sort(q,q+i,cmp1); 27 for(j=0;j<i-1;j++) 28 if(strcmp(q[j].str2,q[j+1].str2)==0) 29 q[j].flag=q[j+1].flag=1; 30 sort(q,q+i,cmp2); 31 for(j=0;j<i;j++) 32 if(q[j].flag==0) 33 printf("%s ",q[j].str1); 34 return 0; 35 } 36 int cmp1(struct data a,struct data b) 37 { 38 return strcmp(a.str2,b.str2)<0; 39 } 40 int cmp2(struct data a,struct data b) 41 { 42 return strcmp(a.str1,b.str1)<0; 43 } 44 void cpy(char *s1,char *s2) 45 { 46 int len,i; 47 for(i=0;s2[i];i++) 48 { 49 if(s2[i]>='A'&&s2[i]<='Z') 50 s1[i]=s2[i]+32; 51 else 52 s1[i]=s2[i]; 53 } 54 }
从一堆发票中筛选出合格的发票，然后用给定的经费报销最大额度的发票，经过包装的01背包问题。有两个重要的点，一个是其中单项物品的额度不超过600指的是三类中的任何一类总额度不超过，而不是一个物品，换句话说，一张发票上A有两个，它们的和不超过600；另一个是浮点数的01背包问题需要扩大相应精度的倍数。
1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 30 * 1000 * 100 + 10; 8 9 int dp[maxn],a[350]; 10 int main() 11 { 12 int n, m,s,p; 13 double q; 14 while(scanf("%lf%d", &q, &n), n != 0) { 15 16 s=0; 17 for(int i = 1; i <= n; i++) { 18 scanf("%d", &m); 19 char ch; 20 double pa = 0, pb = 0, pc = 0; 21 double pr; 22 int f = 1; 23 while(m--) { 24 scanf(" %c:%lf", &ch, &pr); 25 if(ch == 'A') 26 pa += pr; 27 else if(ch == 'B') 28 pb += pr; 29 else if(ch == 'C') 30 pc+= pr; 31 else f = 0; 32 } 33 if(f && pa <= 600 && pb <= 600 && pc <= 600 && pa + pb + pc <= 1000) 34 a[s++]=(int)((pa + pb + pc)*100); 35 } 36 37 p=(int)(q*100); 38 memset(dp,0,sizeof(dp)); 39 for(int i = 0; i < s; i++) { 40 for(int j = p; j >= a[i]; j--){ 41 dp[j] = max(dp[j], dp[j - a[i]] + a[i]); 42 } 43 } 44 printf("%.2lf ", dp[p]/100.0); 45 } 46 return 0; 47 }
给出一个有N个顶点的图，每一条边都存在，问每次不走重复的边，从起点返回终点能走几次，既然都能走，一共N*(N-1)/2条边，分成去和来两个部分，直接除以2即可。
1 #include<stdio.h> 2 3 int main() 4 { 5 int n; 6 while(scanf("%d",&n)!=EOF) 7 { 8 if(n==0) 9 break; 10 printf("%d ",(n-1)/2); 11 } 12 return 0; 13 }
二分匹配模板签到题。
1 #include<stdio.h> 2 #include<string.h> 3 int e[510][510],match[510],book[510],n,m; 4 int dfs(int u); 5 int main() 6 { 7 int k,i,j,a,b,sum; 8 while(scanf("%d",&k)!=EOF) 9 { 10 if(k==0) 11 break; 12 sum=0; 13 memset(e,0,sizeof(e)); 14 memset(match,0,sizeof(match)); 15 scanf("%d%d",&n,&m); 16 for(i=1;i<=k;i++) 17 { 18 scanf("%d%d",&a,&b); 19 e[a][b]=1; 20 } 21 for(i=1;i<=n;i++) 22 { 23 memset(book,0,sizeof(book)); 24 if(dfs(i)==1) 25 sum++; 26 } 27 printf("%d ",sum); 28 } 29 return 0; 30 } 31 int dfs(int u) 32 { 33 int i; 34 for(i=1;i<=m;i++) 35 { 36 if(book[i]==0&&e[u][i]==1) 37 { 38 book[i]=1; 39 if(match[i]==0||dfs(match[i])==1) 40 { 41 match[i]=u; 42 return 1; 43 } 44 } 45 } 46 return 0; 47 }