预计分数:100+50(其实感觉自己写的对)+100
实际分数:100+0+100
给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:
注意:
输入格式:
输入文件matches.in共一行,又一个整数n(n<=24)。
输出格式:
输出文件matches.out共一行,表示能拼成的不同等式的数目。
输入样例#1:
样例输入1:
14
样例输入2:
18
输出样例#1:
样例输出1:
2
样例输出2:
9
【输入输出样例1解释】
2个等式为0+1=1和1+0=1。
【输入输出样例2解释】
9个等式为:
0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
思路:上来先看了一眼数据范围,n<=24,打表!!
然后读了读题,发现这是一个暴力求解的题目,但是想了想老师应该不会出这么水的题(事实证明高估老师了),于是想了一会儿高端做法
无解。so还是暴力吧,n<=24,暴力了一下发现当i=2088的时候(此时需要25根)是不满足条件的。但是2088^3很明显超时啊,。。。一个点就
要跑17s+。。。但是别忘了n<=24!!!!!17s又不是太长、、在我做完第三题之前肯定能跑完吧,二话不说打表!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 int a[10001]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,88,128};
8 int ed=0;
9 int main()
10 {
11 int n;
12 scanf("%d",&n);
13 cout<<a[n];
14 return 0;
15 }
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 int a[10001]={6,2,5,5,4,5,6,3,7,6,8};
8 int ed=0;
9 int p;
10
11 int main()
12 {
13 freopen("debug.in","r",stdin);
14 freopen("debug.out","w",stdout);
15 for(int l=0;l<=24;l++)
16 {
17 int n;
18 scanf("%d",&n);
19 for(int i=10;i<9000;i++)
20 {
21 p=i;
22 int tot=0;
23 while(p!=0)
24 {
25 tot=tot+a[(p%10)];
26 p=p/10;
27 }
28 a[i]=tot;
29 if(tot>24)
30 {
31 ed=i;
32 break;
33 }
34 }
35 //for(int i=0;i<9000;i++)
36 // cout<<i<<" "<<a[i]<<endl;
37 n=n-4;
38 int ans=0;
39 for(int i=0;i<ed;i++)
40 {
41 for(int j=0;j<ed;j++)
42 {
43 for(int k=0;k<ed;k++)
44 {
45 if(i+j==k&&(a[i]+a[j]+a[k]==n))
46 {
47 //printf("%d+%d=%d\n",i,j,k);
48 ans++;
49 }
50 }
51 }
52 }
53 printf("%d %d\n",l,ans);
54 }
55
56
57 return 0;
58 }
John的农场在给奶牛挤奶前有很多杂务要完成,每一项杂务都需要一定的时间来完成它。比如:他们要将奶牛集合起来,将他们赶进牛棚,为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的,因为这样才有更多时间挤出更多的牛奶。当然,有些杂务必须在另一些杂务完成的情况下才能进行。比如:只有将奶牛赶进牛棚才能开始为它清洗乳房,还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作,这个可以最早着手完成的工作,标记为杂务1。John有需要完成的n个杂务的清单,并且这份清单是有一定顺序的,杂务k(k>1)的准备工作只可能在杂务1..k-1中。
写一个程序从1到n读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作,并且,你可以假定John的农场有足够多的工人来同时完成任意多项任务。
输入格式:
第1行:一个整数n,必须完成的杂务的数目(3<=n<=10,000);
第2 ~ n+1行: 共有n行,每行有一些用1个空格隔开的整数,分别表示:
输出格式:
一个整数,表示完成所有杂务所需的最短时间。
输入样例#1:
7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0
输出样例#1:
23
思路:
错解:读完题立马想到拓扑排序(事实证明我掉坑里了,坑是那种能爬出来的那种),于是暴力写完拓扑排序但是发现这题有个坑,就是当
两件任务同时做的时候,如果他们的时间差太多,那么可以让耗时短的那个先继续往下做能做的来等那个耗时长的。。。。。然后就是DFS+
各种标记。后来自己造了几个数据发现还能过。。。。
然而
zero=.=
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<queue>
7 using namespace std;
8 const int MAXN=10001;
9 int n,meiyong,spend;
10 int rudu[MAXN];
11 int mst=0;
12 struct node
13 {
14 int u,v,nxt;
15 }edge[MAXN];
16 int num=1;
17 int head[MAXN];
18 int maxnspend;//记出当前环节时间最长的任务的时间
19 int vis[MAXN];// 记录节点是否被删除
20 int w[MAXN];// 记录每一个节点所需要的花费
21 int flag[MAXN];
22 int ans=0;
23 int how=0;
24 void dfs(int now,int maxns,int spendnow)
25 {
26 for(int i=head[now];i!=-1;i=edge[i].nxt)
27 {
28 spendnow+=w[edge[i].v];
29 int will=edge[i].v;
30 if(rudu[will]==1&&spendnow<=maxns)
31 {
32 flag[will]=1;
33 dfs(will,maxns,spendnow);
34 }
35 spendnow-=w[edge[i].v];
36 }
37 }
38 void topsort()
39 {
40 queue<int>q;
41
42 for(int i=1;i<=n;i++)
43 if(rudu[i]==0)
44 q.push(i);
45 while(q.size()!=0)
46 {
47 how++;
48 int p=q.front();
49 q.pop();
50 maxnspend=-1;
51 for(int i=head[p];i!=-1;i=edge[i].nxt)
52 {
53 if(flag[edge[i].v]==0)
54 maxnspend=max(maxnspend,w[edge[i].v]);
55 }
56 int flag2=0;// 默认需要干
57 for(int i=head[p];i!=-1;i=edge[i].nxt)
58 {
59 int to=edge[i].v;
60 rudu[to]--;
61 if(rudu[to]==0)
62 {
63 dfs(to,maxnspend,w[edge[i].v]);
64 q.push(to);
65 if(w[to]!=maxnspend)
66 {
67 flag[to]=1;
68 }
69 else if(w[to]==maxnspend&&flag2==1)flag[to]=1;
70 else flag2=1;
71 }
72
73 }
74 if(flag[p]==0)
75 ans=ans+w[p];
76 }
77 printf("%d",ans);
78 }
79 int main()
80 {
81 //freopen("","r",stdin);
82 //freopen("","w",stdout);
83
84 scanf("%d",&n);
85 for(int i=1;i<=n;i++)head[i]=-1;
86 for(int i=1;i<=n;i++)
87 {
88 scanf("%d%d",&meiyong,&spend);
89 w[meiyong]=spend;
90 while(scanf("%d",&mst))
91 {
92 if(mst==0)break;
93 rudu[meiyong]++;
94 edge[num].u=mst;
95 edge[num].v=meiyong;
96 edge[num].nxt=head[mst];
97 head[mst]=num++;
98 }
99 }
100 topsort();
101 return 0;
102 }
正解:这明显是一道关键路径问题,(说好的不考呢。。。),但是不会也没关系,因为他有很多解法。
1.因为题目让着求能完成的最小值。。。其实这句话的关键不是在最小值。而是在能完成!so如果每一个点都选择时间最大的那个
去做的话一定能完成。然后就是去枚举每一个点,去求能到达它的最大值,最后再在每一个点的最大值中取一个最大的!!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<queue>
7 using namespace std;
8 const int MAXN=100001;
9 int n,meiyong;
10 int rudu[MAXN];
11 int mst=0;
12 struct node
13 {
14 int u,v,nxt;
15 }edge[MAXN];
16 int num=1;
17 int head[MAXN];
18 int w[MAXN];
19 int spend[MAXN];
20 void topsort()
21 {
22 queue<int>q;
23 for(int i=1;i<=n;i++)
24 if(rudu[i]==0)
25 q.push(i),spend[i]=w[i];
26 while(q.size()!=0)
27 {
28 int p=q.front();
29 q.pop();
30 for(int i=head[p];i!=-1;i=edge[i].nxt)
31 {
32 int to=edge[i].v;
33 rudu[to]--;
34 if(rudu[to]==0)
35 q.push(to);
36 spend[to]=max(spend[to],spend[edge[i].u]+w[edge[i].v]);
37 }
38 }
39 int ans=-1;
40 for(int i=1;i<=n;i++)
41 ans=max(ans,spend[i]);
42 printf("%d",ans);
43 }
44 int main()
45 {
46 //freopen("","r",stdin);
47 //freopen("","w",stdout);
48
49 scanf("%d",&n);
50 int s=0;
51 for(int i=1;i<=n;i++)head[i]=-1;
52 for(int i=1;i<=n;i++)
53 {
54 scanf("%d%d",&meiyong,&s);
55 w[meiyong]=s;
56 while(scanf("%d",&mst))
57 {
58 if(mst==0)break;
59 rudu[meiyong]++;
60 edge[num].u=mst;
61 edge[num].v=meiyong;
62 edge[num].nxt=head[mst];
63 head[mst]=num++;
64 }
65 }
66 topsort();
67 return 0;
68 }
2.假设我们不用拓扑排序,那我们可以记录出每一个最晚出现的位置,因为最晚出现的话其他的任务一定能完成,然后不断的贪最晚的就好
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=100001;
6 int meiyong,v;
7 int k;
8 int dp[MAXN];
9 int ans=-1;
10 int main()
11 {
12 int n;
13 scanf("%d",&n);
14 for(int i=1;i<=n;i++)
15 {
16 scanf("%d%d",&meiyong,&v);
17 while(scanf("%d",&k))
18 {
19 if(k==0)break;
20 dp[i]=max(dp[i],dp[k]);
21 }
22 dp[i]+=v;
23 }
24 //printf("%d",dp[n]);
25 for(int i=1;i<=n;i++)
26 {
27 ans=max(ans,dp[i]);
28 }
29 printf("%d",ans);
30 return 0;
31 }
无
有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。没对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避免事故。编程帮助政府做出一些批准和拒绝申请的决定,使得在保证任意两条航道不相交的情况下,被批准的申请尽量多。
输入格式:
第1行,一个整数N(1<=N<=5000),表示城市数。
第2行到第n+1行,每行两个整数,中间用一个空格隔开,分别表示南岸和北岸的一对友好城市的坐标。(0<=xi<=10000)
输出格式:
仅一行,输出一个整数,表示政府所能批准的最多申请数。
输入样例#1:
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例#1:
4
1<=N<=5000,0<=xi<=10000
思路:原题啊,把南边的排一遍序,然后求北面的最长上升子序列
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 const int MAXN=5001;
8 int n;
9 struct node
10 {
11 int x,y;
12 }a[MAXN];
13 int comp(const node &a ,const node & b)
14 {
15 return a.x<b.x;
16 }
17 int dp[MAXN][4];
18 int tot=0;
19 int ans=1;
20 void dfs(int p)
21 {
22 if(dp[p][3]!=0)
23 {
24 tot++;
25 dfs(dp[p][3]);
26 }
27 ans=max(ans,tot);
28 }
29 int main()
30 {
31 //freopen("","r",stdin);
32 //freopen("","w",stdout);
33 scanf("%d",&n);
34 for(int i=1;i<=n;i++)
35 scanf("%d%d",&a[i].x,&a[i].y),dp[i][2]=0x7fff;
36 sort(a+1,a+n+1,comp);
37 for(int i=1;i<=n;i++)
38 dp[i][1]=a[i].y;
39 for(int i=1;i<=n;i++)// 每一个节点
40 {
41 for(int j=i-1;j>=1;j--)// 它之前的节点
42 {
43 if(dp[i][1]>=dp[j][1])
44 {
45 if(dp[i][1]<=dp[j][2])
46 {
47 dp[j][2]=dp[i][1];
48 dp[j][3]=i;
49 }
50 }
51 }
52 }
53 for(int i=1;i<n;i++)
54 {
55 tot=1;
56 if(dp[i][2]!=0x7fff)
57 {
58 tot++;
59 dfs(dp[i][3]);
60 }
61
62 }
63 printf("%d",ans);
64 return 0;
65 }
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int MAXN=5001;
6 struct node
7 {
8 int north;
9 int south;
10 }a[MAXN];
11 int comp(const node & a ,const node & b)
12 {
13 return a.north<b.north;
14 }
15 int ans[MAXN];
16 int main()
17 {
18 int n;
19 scanf("%d",&n);
20 for(int i=1;i<=n;i++)
21 scanf("%d%d",&a[i].north,&a[i].south);
22 sort(a+1,a+n+1,comp);
23 for(int i=1;i<=n;i++)
24 {
25 for(int j=1;j<=i-1;j++)
26 {
27 if(a[j].south<a[j+1].south)
28 {
29 ans[i]=max(ans[i],ans[j]+1);
30 }
31 }
32 }
33 printf("%d",ans[n]+1);
34 return 0;
35 }
总结:
这次考试,,怎么说呢?,,成绩一般,但是自我感觉还可以,因为没有出现因为低级错误而失分的情况。而且第一题能想到
用打表做,说明考试经验有了一定的提升。第二题做错了就是做错了,也没什么好懊悔的。只能说明自己能力不够。
这次考试也反映出了最近学习的一些弊端,就是像做动规题的时候,很少能够深入的研究一个题,感觉自己做不出来,就去看题解
这样的话,就大大降低了对题目的把握能力。以至于在考试的时候,能想到一个看似对,但实际上暴零的题解。
顺便吐槽一下,,考试之前我可是认真的准备了线段树,KMP,树状数组,扩展欧几里得,高难度搜索的题目。。。
结果居然一个都没考。。。。。。。。。。。。。
%>_<%