国庆3

今天的题很奇怪

 

1

思路:看完题并且理解题意的牛肯定都知道怎么写了,递归+模拟,难度超
低。。只不过要细心一点哈。 注意处理两个人决策的优先级:比如不能把必杀绝招的处理放在连续攻击后面
2
直接 floyd。输出的时候统计路上节点即可
就是注意一点 .. 答案要+2 (加上起点和终点两个点)
3
经典的一道最短路模版题,将地图中相邻且相同的点距离为 0,不相同为 1,然
后建立两个假点,源点 s 和最上面一排所有点相连,距离为 0;同样的,汇点 t
和最下面一排所有点相连,距离也为 0;接下来就是求 s 到 t 的最短路 ans,输
出 ans+1 即为答案。同时,注意到地图范围是 20*20,BFS 暴搜也可以过
4
简单描述此题,就是求两个序列的最长上升公共子序列,而对于求最长公
共子序列和最长上升序列这两个动态规划的基础模型,我们已经十分熟悉。因
此本题可以考虑在经典问题的经典解法的基础上进行改动,于是我们想到,可
以先求两个序列的最长公共序列,再对其求最长上升序列,即为答案。(之所
以不选择先分别求最长上升序列,再求最长公共序列是因为答案一定为两个序
列的公共序列,反过来贪心算法错误,反例易举)但是,这个问题并不是这么
简单,因为这两个序列的最长公共序列可能有多个,而我们并不能确定最终的
答案在哪一个公共序列中,所以进一步考虑,我们可以先穷举所有公共序列,
对其分别求最长上升序列。
仔细考察一下这个算法,它的时间复杂度高达 O(m^8),这是我们无法接受
的结果。但是这个算法在构造所有公共序列时有较大提升空间,将此算法优化
至 O(n^4)后加了一个卡时应可以 AC 此题,此方法也不再赘述。
在第一个方法失败的基础上,我们希望能够抛开那两个经典问题的束缚,
另辟蹊径来解决此题。于是我们想到一种常用的状态表示法:用 opt[I,j]表示
a[i]=b[j],且以这个数作为结尾的最长上升公共子序列的长度,于是转移方程易
得:
max{max{opt[k,l]}1,1}(k  i,l  j, a[i]  b[ j], a[k]  b[l])
opt[i, j] 
0(a[i]  b[ j])
同样,此方法的时间复杂度达到了 O(m^4),仍是一个不理想的算法,但我
们可以通过纪录那些 a[i]=b[j]来加速查找的过程,这样优化后,程序的时间复
杂度介于 O(m^2)与 O(m^4)之间,但其完全由输入数据两个序列间的相似程度
决定,一旦输入的数据相似程度较高,该算法就瞬间退化为 O(m^4)的算法。
于是我们开始思考这个算法的瓶颈在什么地方。经过研究,发现我们用来
表示状态的方法不好,约束条件太多使得其必须用大量时间来转移。要想在时
间上有所突破,必须使用一种意义更广泛的状态表示法,如用 opt[I,j]表示以 b[j]
结尾且是 a[1]-a[i]的子序列的最长公共上升序列的长度。这样的状态表示法的外
延就比原来的表示方法更广了,同时我们惊奇的发现现在我们只要 O(m)的时间
就能维护一个 opt 单元了。转移方程如下:
max{max{opt[i 1, k]}1,1}(k  j, a[i]  b[ j],b[k]  b[ j])
opt[i, j] 
opt[i 1, j](a[i]  b[ j])
这样这个算法的时间复杂度就降为了 O(m^3),所有数据都能过了,但大数
据的时间仍不够理想,无论机器再烂一些或范围再大一些都有超时的可能,因
此此算法仍需继续优化。
继续思考上一个算法的瓶颈,如果想进一步优化,我们就希望能通过 O(1)
的时间来维护一个 opt 单元。但是仅仅通过一个 opt 数组,实现这个功能似乎有
难度(至少我没有想到什么好的方法来转移上升这个约束条件)。于是结合
2,4 两个方法,用 opt1[I,j]表示以 b[j]结尾且是 a[1]-a[i]的子序列的最长公共上
升序列的长度,用 opt2[I,j]表示 a[i]=b[j],且以这个数作为结尾的最长上升公共
子序列的长度,转移方程如下:
opt1[I,j]=max{opt1[I-1,j],opt2[I,j]}
opt2[I,j]=max{opt1[I-1,k]+1,1}(k<j,b[k]<b[j],a[i]=b[j])
但是如果仅仅这样,算法的时间复杂度仍为 O(m^3),不是我们预期的
O(m^2)。考虑到前几个算法在对付两个序列相似程度高的时候都在一定程度上
对一些子问题进行了重复计算,我们可以记录 a[i]=a[l]中的 I,l,在转移时先转
移 opt2[I,l],这样就可以减小枚举 k 的范围(事实上,相当于转移每一个 I,j 都
仅仅从 1 到 m 扫描了一遍。这个方法十分精妙,我尝试寻找这样的方法,但没
有成功,是在一些前辈的引导下想到的),转移方程如下:
opt1[I,j]=max{opt1[I-1,j],opt2[I,j]}
opt2[I,j]=max{opt2[I,point],opt1[I-1,k]+1,1}
(point=max{l}(a[l]=a[i]),point<k<j,b[k]<b[j],a[i]=b[j])
总结一下这道题目,就是优化优化再优化。

国庆day5

嗯~~今天再次爆0(又是高兴的一天),今天我再来说一下刷样例的得分:第一题30分,第三题55~77,第四题20分,我也不知道我哪来的自信相信自己的代码而不相信样例的(虽然都过样例了)

第一题:模拟,但我改了良久就是没改出来~~,只改了30分(跟刷样例同分):连续5次发必杀且怒气值已<100,则第六次就要蓄力一次 (因为连续攻击次数=5)。这一个一直弄不出来,在改了一个小时后也成共放弃,但好像可以用函数。。。
第二题:用FLOYD算法,再参考一位大神的代码也打出来了(毕竟核心代码只有五行)代码如下:
for(int i=1;i<=n;i++)
for(int i=1;i<=n;i++) 
{     
for(int j=1;j<=n;j++)     
{         
for(int k=1;k<=n;k++)         
{             
if(f[i][k]+f[i][j]<f[j][k]) 
{             
 f[j][k]=f[i][k]+f[i][j]; 
 }
第三题:好像用搜缩,还没改出来。。。。
第四题:用DP(不会)
又是HAPPY的一天

国庆集训Day。。。

1:模拟,但是是个人都知道。but怎么模拟???主次分不清ค(TㅅT) 。。。

2:最后20分钟才发现题目弄错了ヾ(・ω・`。),不知怎么给了我10分。已改。

3:打了好久好久,方法是对的,样例是过的,提交是开心的,结果是凄惨的                 ヽ(*。>Д<)o゜

4:最长公共上升子序列,组合了两个子序列问题。嗯。蛮好的。我还能说啥,,,

Bye

Day 5

今日做题全程一脸懵逼,全部都是刷数据的,得了72分,不要问我为什么,我也不知道.

唯一会的只有一道题就是景点,那道题Floyd套公式就好。

世界要用递归+模拟

消消乐是真不会。

窃取密码我好后悔最长上升公共子序列没有认真听。

国庆Day5

T1世界

纯模拟我哭了

编了递归一直输No answer

有30靠我好感动


T2景点

本来只想靠这题拿分

结果最后几分钟发现题意理解错了

来不及改也不会改aa

我以为只有一条最短路径

我以为真的只是我以为、、

用Floyd求出所有某点到某点的最短路径

附上for(j=1;j<=n;j++){

if(a[w1][j]+a[j][w2]==a[w1][w2])

ans++; }

记得for(i=1;i<=n;i++)

a[i][i]=0;//不然过不了


T3消消乐

求出每一列的总消除数

small=min(small,ans[i]);

77分!!

本来只想骗一个样例

骗着骗着就对了7个样例?!


T4窃取密码

会求最长上升子序列

但不会求最长公共子序列、、

cu

2019.10.4签到

59.61.214.20:3001题库上,题号为2755的题目“数列”没有清晰题解,为了方便后人学习,我总结了更清晰的题解。

更准确的题意:

要在每一列选一个数(或者不选),满足以下条件:
如果在第一行选,那它必须大于等于你已经选择的上一个数(下文的“上一个数”都表示“你已经选择的上一个数”)
如果在第二行选,那么必须小于等于上一个数
如果在第三行选,对于连续的一段在第三行选的数,必须满足方向相同(都小于等于上一个数或者都大于等于上一个数,并且这连续的一段的第一个数也要符合和它的上一个数方向相同)

看下面的样例:

6
1 2 3 6 5 4
5 4 3 7 8 9
1 2 3 6 5 4

【样例解释】
取第三行1 2 3(增),然后取第1行6(增),然后取第三行5 4(减),长度为6。

如果第三行第五列的5改成7,7就不能取了,因为6,5,4递减,6,7,4不递减。出题人在【简版题意】中描述不准确,造成了许多人误解了题意。

题解:参考“拦截导弹问题”的做法,设f[i][0/1/2/3]表示必须选a[i][0/1/2/2]的前i列最优值,并满足各自的递增递减之类的限制。a[i][0/1/2]分别代表第一、二、三个数列的第i个数,f[i][2/3]的不同之处是,前者强制递增,后者强制递减,也就是把“方向一致”的条件拆分成两种情况罢了。状态转移方程如下:

if a[i][0]>=a[j][k]
f[i][0]=max f[i][0],f[j][k]+1 ;
if a[i][1]<=a[j][k]
f[i][1]=max f[i][1],f[j][k]+1 ;
if a[i][2]>=a[j][k]&&k!=3
f[i][2]=max f[i][2],f[j][k]+1 ;
if a[i][3]<=a[j][k]&&k!=2
f[i][3]=max f[i][3],f[j][k]+1 ;

这是60分的方法,要100分,再用线段树维护。

QAQ又炸了............................

总结了一下原因,有以下几点:

1、对DP不够熟练,没有发现和合理应用DP!!!!!!!!!QAQ

2、舍本逐末,一开始就去打最后一题,又死磕不出来,没有坚定的打下去,回过头去打第一题,没有专心!!!!!!!!!QAQ

3、比其他人早去吃饭了>_>

4、看到第一题类似图论有点小小的恐惧>_>

5、忘记SPFA怎么打了!!!!!!!!!QAQ

6、最长公共子序列是什么来着<^_^>?

7、没有刷       90      分的样例 QAQ     (就是看不到)

 

 

 

国庆Day4

T1密室逃脱

用并查集做

开两个数字分别存a和b的爸爸的爸爸的爸爸(*n)

自己也是自己的爸爸!!

再一个一个比较

找到最近一个共同的爸爸就return 0;

于是 就AC了

(o直接输1就90数据太水了)


T2买花

cin>>n;

for(int i=0;i<n;++i) {

cin>>a>>b;

if((a&b)==b)

cout<<1<<endl;

else

cout<<0<<endl;

继续阅读国庆Day4

国庆基地校Day2

今天考的一塌糊涂

唉~~~~~~~~~~~~~~~~~~o(︶︿︶)o o(︶︿︶)o

最后一题明明就已经讲过了

忘了😥

先讲第四题

这题其实就是最长公共子序列

我们要注意该题的子串不是连续的我们分别枚举两个字符串的每一位,如果当前两位相等,显然可以新增加一个字母。如果不相等,由之前的状态推来即可。

f[i][j]表示x列的前i个元素和y列的前i个元素的LCS

f[i][j]= ① 0      若i=0或j=0

②f[i-1][j-1]+1  若i,j>0 ,x[i]=y[i]

③max{f[i][j-1],f[i-1][j]}  若i,j>0 ,x[i]=y[i]

 

第一题:

这一题我们只要一次 DFS 遍历加上并查集就可以                            

轻松完成了

先建立一个含i的s[i]

然后用DFS 遍历树,当遍历节点 i 时,处理所有有关子树的询问 A(p,q),如果 S[i]中包含节点 p、q,那么 A(p,q)=i,否则进入下一步

将 s[i]合并到 s[Father[i]]中。

我是用while(b[l]!=b[w])来判断l与w,我设置了一个函数b[l]与b[w]指向每次l与w的“头”

然后用他们“头的位置”来不断调整l与w的更新值

刚刚我发现我的第二种情况忘记加while了而且最后输出的l不对所以错了

我改正之后就AC了,(与老师不一样)我的100分没了!!!!!!

完整代码如下:


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
#include<bits/stdc++.h>
using namespace std;
int n,m,x,i,j,q1,qst,a[10000001],b[10000001],l,w;
int main()
{
 freopen("flee.in","r",stdin);
 freopen("flee.out","w",stdout);
 cin>>n;
 for(i=1;i<n;i++)
 {
 cin>>a[i]>>x;
 b[x]=a[i];
 }
 cin>>qst;
 cin>>l>>w;
 if(l==w)
 {
 cout<<l;
 return 0;
 }
 if(w>=l)
 {
 while(b[l]!=b[w])
 {
 if(b[w]>0)
 {
 w=b[w];
 }
 if(l!=w&&b[l]==b[w])
 {
 cout<<b[l];
 return 0;
 }
 if(l==w&&b[l]==b[w])
 {
 cout<<l;
 return 0;
 }
 if(b[l]>0)
 {
 l=b[l];
 }
 }
 }
 else
 {
 while(b[l]!=b[w])
 {
 if(b[l]>0)
 {
 l=b[l];
 }
 if(l!=w&&b[l]==b[w])
 {
 cout<<b[l];
 return 0;
 }
 if(l==w&&b[l]==b[w])
 {
 cout<<l;
 return 0;
 }
 if(b[w]>0)
 {
 w=b[w];
 }
 }
 }
 cout<<b[l];
return 0;
}

没错,就是47行那个的while和69行的b[l],其实你打b[l]或b[w]都行,他们的“头”一样。

第二题:

我发现一个超级厉害的二进制转换方法————

if((a&b)==b) cout<<1<<endl;

else   cout<<0<<endl;

虽然没怎么看懂,但很好用就对了

第三题:

不怎么会,但核心代码就是:

f(i,j):=max{max{f(tree[i].l,k)+f(tree[i].r,j-1-k)}(0<=k<=j-1),f(tree[i].r,j)}

这个了

谢啦!!☆⌒(*^-゜)v