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

第一题没什么好讲的，直接秒了，下次尽量要在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大佬的解法。

赛后总结

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

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：五、伊森商城 前端基础-Vue 计算属性和侦听器 过滤器 组件化 生命周期钩子函数 p25

下一篇：第七十二天 P1025 [NOIP2001 提高组] 数的划分

相关内容

热门资讯

清代第一美食家 题图：袁枚像 《随园食单》不只是食谱，更是清代文人的雅致生活范本。 新近出版的《袁枚的讲究：趣读〈随...
原创 越... 今天咱来唠唠越南美食。你要是去过越南街头，肯定对那些小吃摊印象深刻。好多摊儿看着不咋起眼，甚至有点 ...
原创 4... 我跟你们说，这次去泰国，在朱拉隆功大学美食街，那可真是体验了一把啥叫 “4 人 200 块吃到撑” ...
原创 在... 今天咱唠唠那些在咱国内不咋受待见，到了国外却让富人们疯狂追捧，甚至成了炫富密码的食品。你说这事儿怪不...
原创 头... 自今年4月起，外卖平台掀起的补贴热潮席卷国内咖啡茶饮市场，社交媒体上流传的各类 “奶茶0元购” 教程...
拉图卡梅尔骑士 | 所有的葡萄... 葡萄，这颗晶莹剔透的果实，自远古时代便与人类文明交织在一起。从地中海沿岸的古老酒窖到现代顶级酒庄的橡...
西安蓝天白云：登高看风景，杜陵...
暑假去安徽五天四夜旅游，五天四... 黄山，这座被誉为“天下第一奇山”的壮丽之地，一直以来都是我心中的旅游圣地。它的奇松、怪石、云海、温泉...
原创 韩... 近日，一则韩国网红拍摄的中国旅游视频在中国社交媒体上掀起了轩然大波。这名女网红来到延边的朝鲜族聚居地...
庆元主场 宠你没话讲！温州球迷...
麻辣干锅鸡香翻全家，酸汤鱼片清... 麻辣干锅鸡端上桌，香气扑鼻，辣得让人直咽口水！这道菜可是家宴的顶梁柱，鸡肉嫩滑，土豆藕片吸满汤汁，咬...
从传承到创新，“长沙小椒傲”的... 长沙晚报掌上长沙8月17日讯（全媒体记者 尹玮）美食竞技综艺《一饭封神》正在腾讯视频热播。节目除了在...
原创 西... 前两天刷到个视频，老外第一次见菜单上写着 “dragon and tiger fight”，脸都白了...
张家界旅游二日二晚游价格多少？... 去年夏天，我拉着闺蜜去张家界玩了一圈，原本以为旅游肯定贵得要命，结果全靠导游娜娜帮忙，省了一大笔钱！...
暑假去安徽跟团游3天2晚纯玩团... 黄山，这座被誉为“天下第一奇山”的仙境，一直是我心心念念的旅行目的地。终于，在这个假期，我决定踏上这...
原创 2... 头条首发大赛 为了您更好的阅读互动体验，为了您及时看到更多内容，点个“关注”我们每天为您更新精彩故事...
不得不说这条攀岩线路的视觉冲击...
去甘肃5天两个人需要多少钱，自... 家人们，现在甘肃甘南旅游那热度简直居高不下！它那独特的藏地风情、壮美的自然风光，就像一块巨大的磁石，...
原创 接... 在这个盛夏的八月，第35届青岛国际啤酒节如火如荼，犹如一场盛大的狂欢。经过整整一个月的闹哄哄营业，终...
一景区小火车脱轨，导致游客被困... 据报道，有网友发视频称，广西河池市罗城县罗城棉花天坑景区8月16日发生小火车脱轨的现象，一度导致部分...