2010年9月27日
这是四川网络赛的B题，题目意思很简单，求不超过n,包含数字13并能被13整除的个数.很遗憾，但是没想到是dp ,推了半天做出来。惭愧啊。最初是用稀疏表来做，但很遗憾，TLE了。最后参考别人的代码。自己再想想才AC了。太菜了。加油啊。
思路： 令dp1[i][j][k] 表示在位置i (i>=0)的数字为 j(0<=j<10) 时，从j*10^i ---- (j+1)*10^i-1 ，这 10^i 个数中，包含连续数字13且模 13 的余数为k 个数。同理 dp2[i][j][k] 表示不包含连续数字13，余数为k 的个数。 递归方程: 9 dp1[i][j][kk]= Σ（dp1[i-1][t][k]）其中kk=(j*10^i+k)%13; t=0 这里需要注意特殊情况，即出现了13. 这时在上面的基础上需加上 dp2[i][t][k], 9 dp1[i][j][kk]= Σ（dp2[i-1][t][k]）; t=0 同理 9 dp2[i][j][kk]= Σ（dp2[i-1][t][k]）; t=0 若出现13 则dp2[i][j][kk]=0; 初始时 dp2[0][k][k]=1,（0<=k<10）其余的为0. 最后对输入的n,只需在此基础上计算即可。当要注意出现 13 的特殊计数。即要加上 dp2[i][j][k].
2010年8月14日
题意： 就是求str1 的最长后缀与 str2 的最长前缀。使得 str1+str2 的长度最小，并且字典序最小。 分析： 利用kmp 求出最长相同的后缀和前缀。在利用串比较函数比较最小字典序。具体可以参考代码。
  code
1 #include<iostream>
2using namespace std;
3
4const int maxn=100005;
5char a[maxn],b[maxn];
6int next_a[maxn],next_b[maxn];
7
8void Getnext(char *str,int next[])
9 {
10 int j=1,k=0;
11
12 next[0]=-1;
13 next[1]=0;
14 while(str[j])
15  {
16 if(str[j]==str[k])
17 {
18 next[j+1]=k+1;
19 k++;
20 j++;
21 }
22 else if(k==0)
23 {
24 next[j+1]=0;
25 j++;
26 }
27 else k=next[k];
28 }
29 }
30
31int KMPIndex(char *str1,char *str2,int next[])
32{
33 int i,j;
34
35 i=j=0;
36 while(str1[i])
37 {
38 if(str1[i]==str2[j])
39 {
40 i++;
41 j++;
42 }
43 else if(j==0)i++;
44 else j=next[j];
45 }
46 return j;
47}
48
49int main()
50{
51 int k1,k2;
52 while(EOF!=scanf("%s %s",a,b))
53 {
54 Getnext(a,next_a);
55 Getnext(b,next_b);
56 k1=KMPIndex(a,b,next_b);
57 k2=KMPIndex(b,a,next_a);
58
59 if(k1==k2)
60 {
61 if(strcmp(a,b)<=0)
62 printf("%s%s\n",a,b+k1);
63 else
64 printf("%s%s\n",b,a+k1);
65 }
66 else if(k1<k2)
67 printf("%s%s\n",b,a+k2);
68 else
69 printf("%s%s\n",a,b+k1);
70 }
71 return 0;
72}
73
74
摘要: 分析： 题目的意思很好理解，就是选择满足在 H1--H2,与A1---A2 之间的最大的 L。显然该用二维线段树来做，代码很好写，需要注意 H1 > H2 和 A1 > A2 的情况。另外还需要采用double 型。
codeCode highlighting produced by Actipro ... 阅读全文
2010年8月13日
思路：
将所有输入的单词插入trie 树中，再在table 中枚举每个点的八个方向，作为单
词的起点。如果枚举成功。这标记出现的单词。
code
1#include<iostream>
2using namespace std;
3
4const int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
5
6typedef struct Tnode
7{
8 int end;
9 Tnode * next[26];
10 Tnode()
11 {
12 end=-1;
13 memset(next,0,sizeof(next));
14 }
15}Trie;
16
17Trie *root=new Trie;
18char map[1010][1010];
19int res[1010][3];
20int l,c,w,px,py;
21
22void Insert(Trie *cur,char *s,int id)
23{
24 int i;
25 if(*s==0)
26 { cur->end=id;
27 return ;
28 }
29 i=*s-'A';
30 if(cur->next[i]==NULL)
31 cur->next[i]=new Trie;
32 Insert(cur->next[i],s+1,id);
33}
34
35void input()
36{
37 int i;
38 char word[1010];
39
40 scanf("%d%d%d",&l,&c,&w);
41
42 for(i=0;i<l;i++)
43 scanf("%s",map[i]);
44 for(i=0;i<w;i++)
45 {
46 scanf("%s",word);
47 Insert(root,word,i);
48 }
49}
50
51void search(Trie *cur,int x,int y,int k)
52{
53 if(cur==NULL)
54 return ;
55 if(cur->end>-1)
56 {
57 res[cur->end][0]=px;
58 res[cur->end][1]=py;
59 res[cur->end][2]=k;
60 }
61 if(x<0||x>=l||y<0||y>=c)
62 return ;
63 int i=map[x][y]-'A';
64 search(cur->next[i],x+dir[k][0],y+dir[k][1],k);
65}
66
67int solve()
68{
69 int i,j,k;
70 for(i=0;i<l;i++)
71 for(j=0;j<c;j++)
72 for(k=0;k<8;k++)
73 {
74 px=i;py=j;
75 search(root,i,j,k);
76 }
77 return 1;
78}
79
80void output()
81{
82 int i;
83 for(i=0;i<w;i++)
84 printf("%d %d %c\n",res[i][0],res[i][1],res[i][2]+'A');
85}
86
87int main()
88{
89 input();
90 solve();
91 output();
92 return 0;
93}
题意：
给定一个n*n (n<=20) 的方格，里头放有一些非负数，选择一些不相邻的格子，使其和最大。
分析：
主要思想是从第一行到第N行，从第一列到第N列进行DP，用位来保存状态，比如在i行j列，对所有的0到2^n -1 状态进行计算，最后的结果是从i=n-1,j=n-1的2^n个状态求最大就OK了。别以为这运算量很大，其实只有O(n*n*2^n)比直接暴搜O(n!*n!)快了N多，因为这题数据比较小，N最大为20，所以可以这么DP。但如果N很大的话这种方法显然不行，那就要用到最大流了。
1#include<iostream>
2using namespace std;
3
4const int mm=1<<20+1;
5int rect[51][51];
6int dp[2][mm];
7int maxn=-1;
8int n;
9
10int solve()
11{
12 int i,j,k,p,t,z;
13 for(i=0;i<n;i++)
14 {
15 for(j=0;j<n;j++)
16 {
17 t=1<<j;
18 p=(i*n+j)%2;
19 for(k=0;k<(1<<n);k++)
20 {
21 if((k&t)==0)
22 dp[1-p][k]=dp[p][k]>dp[p][k+t]? dp[p][k]:dp[p][k+t];
23 else if(j>0&&(k&(t>>1)))dp[1-p][k]=0;
24 else dp[1-p][k]=dp[p][k-t]+rect[i][j];
25 }
26 }
27 }
28 return 0;
29}
30
31int main()
32{
33 int i,j;
34 while(EOF!=scanf("%d",&n))
35 {
36 for(i=0;i<n;i++)
37 for(j=0;j<n;j++)
38 scanf("%d",&rect[i][j]);
39 maxn=-1;
40 memset(dp,0,sizeof(dp));
41 solve();
42 for(i=0;i<(1<<n);i++)
43 {
44 if(dp[(n*n)%2][i]>maxn)
45 maxn=dp[(n*n)%2][i];
46 }
47 printf("%d\n",maxn);
48 }
49 return 0;
50}
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 24 | 25 | 26 | 27 | 28 | 29 | 30 | | 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 | 1 | 2 | 3 | 4 |
|
公告
常用链接
留言簿
随笔分类
随笔档案
文章分类
文章档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|