2017.5.13阶段模拟考试

预计分数:100+50(其实感觉自己写的对)+100

实际分数:100+0+100

P1149 火柴棒等式

题目描述

给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:

注意:

  1. 加号与等号各自需要两根火柴棍
  2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C>=0)
  3. n根火柴棍必须全部用上

输入输出格式

输入格式:

输入文件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 }

P1113 杂务

题目描述

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..n,在输入文件中是有序的);
  • 完成工作所需要的时间len(1<=len<=100);
  • 一些必须完成的准备工作,总数不超过100个,由一个数字0结束。有些杂务没有需要准备的工作只描述一个单独的0,整个输入文件中不会出现多余的空格。

输出格式:

一个整数,表示完成所有杂务所需的最短时间。

输入输出样例

输入样例#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 }

P2782 友好城市

题目背景

题目描述

有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的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,树状数组,扩展欧几里得,高难度搜索的题目。。。
结果居然一个都没考。。。。。。。。。。。。。

%>_<%

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

HDU 4609 3-idiots

http://acm.hdu.edu.cn/showproblem.php?pid=4609 题意:给你一组数,问可以组成多少个三角形 分析:才知道原来有FFT...

2916
来自专栏数据结构与算法

洛谷P4213 Sum(杜教筛)

题目描述 给定一个正整数N(N\le2^{31}-1)N(N≤231−1) 求ans_1=\sum_{i=1}^n\phi(i),ans_2=\sum_{i=1...

2956
来自专栏数据结构与算法

2596 售货员的难题

2596 售货员的难题 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 钻石 Diamond 题目描述 Description 某...

3586
来自专栏owent

PKU POJ 2728 Desert King 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2728

853
来自专栏数据结构与算法

BZOJ1101: [POI2007]Zap(莫比乌斯反演)

Description   FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gc...

3615
来自专栏数据结构与算法

BZOJ3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛(dp)

设$f[i]$表示到第$i$个位置,该位置放了牡牛的方案,$g[i]$表示到第$i$个位置,且该位置放了牝牛的方案数

741
来自专栏calmound

畅通工程再续(最小生成树)

这道题被坑的难受,很基础的题目,但是还是wa的郁闷,主要的错误是不懂的分析,导致变量的定义出错,记录k点的最短边要double的却依旧写int导致wa的找不出错...

3187
来自专栏数据结构与算法

11.6NOIP模拟赛解题报告

很显然的一个贪心是从左往右扫,如果遇到一个不合法的点\(i\),那么升级\(i + R\)处的炮台。。

983
来自专栏数据结构与算法

BZOJ2462: [BeiJing2011]矩阵模板(二维hash)

二维矩阵hash,就是对行和列分配一个不同的base,然后分别做一遍hash,这样会减少冲突的概率。

811
来自专栏数据结构与算法

LOJ#2552. 「CTSC2018」假面(期望 背包)

转移的时候若要淦这个人,那么\(f[i][j] = (f[i - 1][j] + 1) * p + (f[i - 1][j]) * (1 - p)\)

1594

扫码关注云+社区

领取腾讯云代金券