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大佬的解法。

赛后总结

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

相关内容

热门资讯

白酒板块11月19日跌0.55... 证券之星消息,11月19日白酒板块较上一交易日下跌0.55%,皇台酒业领跌。当日上证指数报收于394...
小雪降温了,炸一锅给孩子吃,当... 小雪降温了,炸一锅给孩子吃,当零食又当菜,越吃越香不上火 天冷又到了炸丸子的季节,这些丸子用来做汤或...
原创 奶... 标题:奶黄包这样做,香甜松软,奶味十足,就算不吃面食的都会爱上它! 在繁忙的都市生活中,寻找一份简...
原创 媳... 标题:媳妇自从学会了炸蘑菇,隔三差五就在家做一回,大人孩子抢着吃! 在美食的世界里,有一种简单却能...
爆火到排队!奶皮子糖葫芦成“甜... 最近,一种名叫“奶皮子糖葫芦”的网红甜食在社交平台上爆火。山楂、奶皮子、脆糖壳的搭配,让不少人直呼“...