AcWing第80场周赛总结
admin
2024-03-20 14:27:11

第一题没什么好讲的,直接秒了,下次尽量要在5min内写完。
T2:寻找数字
第二题sb了,一直在想贪心的办法,但是考虑到这个比赛的难度 ,其实最原始的dfs才是正解。dfs的妙处在于:省去了对于各类可能不合法的情况的分类讨论,直接通过一个判断全部筛掉,而且可以保证答案的最小性,因为是dfs序。这题的时间复杂度理论上是O(n*lgn)的,但是实际上跑得飞快,只用了24ms就过了。所以就可以写出如下代码:

#include
#include
using namespace std;
const int N=35;
typedef long long ll;
int n,m;
ll ans=1e18;
int a[N];
void dfs(int u,int len,int s4,int s7){if(s4>(len+1)/2 || s7>(len+1)/2) return;if(u==len){ll res=0;for(int i=len;i>=1;i--){res=res*10+(ll)a[i];}if(res>=(ll)n) ans=min(ans,res); return;}a[u+1]=4;dfs(u+1,len,s4+1,s7);a[u+1]=7;dfs(u+1,len,s4,s7+1);a[u+1]=0;
}
int main(){cin>>n;m=(int)(log(n)/log(10))+1;if(m&1) dfs(0,m+1,0,0);else dfs(0,m,0,0);if(ans==1e18){dfs(0,m+2,0,0);}cout<

T3:摆放棋子
这题显然是一个dp,但是我用自己的神奇推法并没有办法AC,所以需要借鉴一下别人的优美写法:设fi,j,0/1表示填了前i个位置,且一共填了j个白子,最后一个子为白子(0)或黑子(1)。那么这种写法实际上是一种线性DP的写法,并且巧妙地找到了最后一个不同点:最后一个子的黑白。那么转移就非常简单了:
fi,j,0=∑k=1k2fi−k,j−k,1\sum_{k=1}^{k2}\ f_{i-k,j-k,1}∑k=1k2​ fi−k,j−k,1​
fi,j,1=∑k=1k1fi−k,j,0\sum_{k=1}^{k1}\ f_{i-k,j,0}∑k=1k1​ fi−k,j,0​
边界:f0,0,0=f0,0,1=1
代码较易,不予展示。
P.S.:y总的代码感觉无法透彻地理解,所以还是采用了nickxiao大佬的解法。

赛后总结

时间紧迫,不能迟到,然后不能思维定式,可以通过一些较为“朴素”的手法来简化问题,最后就是要多积累一些题目。

相关内容

热门资讯

教师专享福利!北京这些景区免票... 新京报讯 据首都教育消息,教师节将至,北京多家景区为老师们准备了专属免票福利!这份优惠合集已整理好,...
黑茶,喝的是一种境界与健康 在专门用来喝黑茶的茶具“飘逸杯”里,黑茶茶汤看起来并不像“黑茶”这个名字那样黑黢黢的一团。 玻璃器皿...
上海旅游节大巡游花车阵容抢先看... 2026上海旅游节大巡游9月12日外滩启幕,21辆全新主题花车携手21支境内外表演方队联袂登场,邀你...
原创 8... 上周门诊来了位 62 岁的张阿姨,得糖尿病快五年了,平时管嘴特别严,糖果、点心、甜饮料一概不碰,连水...
原创 餐... 2026年9月8日晚,南京浦口区泰冯路29号,墨语江南·阿婆菜餐厅户外帐篷里,灯火温润,其间还天降喜...