Little-Qiao-CSDN博客

原创【二分栈优化dp】图解二分栈优化dp

文章目录原理什么是二分栈图解什么时候使用二分栈时间复杂度二分栈优劣例题[BZOJ1010][HNOI2008]玩具装箱题目大意输入输出样例限制分析二分栈代码CSP-S 2019 Day2T2 划分（88pts）题目大意分析原理什么是二分栈个人理解的二分栈，应该是一种类似刷表法的算法，对于每个点i，先更新自己的答案，再弹掉所有转移不如i的区间，最后在后面的 [i+1,n][i+1,n][i+1...

2019-12-02 13:26:12 1170 1

原创【状压dp，最短路】牛客CSP-S提高组赛前集训营5 B 十二桥问题

文章目录题目题目大意数据范围分析状压dp状压dp的优化最短路一点小技巧代码题目十二桥问题题目大意给你一个n个点m条边的无向图，每条边有一个权值d，其中有k条边必须经过，从1号点出发，求经过这k条边，并且回到1号点的最小花费。数据范围n ≤ 50000，m ≤ 200000， d ≤ 1e9， k ≤ 12分析状压dp首先拿到这道题，我们看到一个k ≤ 12的范围，是不是就想到了...

2019-11-08 23:22:40 273 1

原创 COCI 2016/2017 Round #3 T4 Kvalitetni

目录题目分析代码题目分析我会说这道题最难的其实是读题吗？？？（读题读了1h+）可能是翻译问题，反正是没讲清楚，我解释一下：1.所有类似于"(?)"的表达式的最大值为Z1（啊啊啊是Z1不是Zi啊）2.在表达式(()+()+()+......)或者(()*()*()*()*......)中有k项,则这个表达式里所有元素的总和的最大值为Zk（是不是被绕晕了）3...

2019-07-03 12:17:58 274 1

原创 [AtCoder Beginner Contest 131]A~E简要解析

【因中考失踪人口回归】咳咳，进入正题~~A题 Security题目大意就是输入一个四位数，看有没有连续的俩数字。code#include<cstdio>int main(){ int a,b,c,d; scanf("%01d %01d %01d %01d",&a,&b,&c,&d); if(a==b || b==c || c==d)...

2019-06-24 20:48:33 413 1

原创 UVa10817 Headmaster‘s Headache【状压dp（递推写法）】

失踪人口回归前言多日不见，博主在偷懒百忙之中，又重操旧业，开始写写博客了，这次呢，主要是因为一道非常恶心好的题。嗯，就是标题中的UVa10817了。（可能UVa的加载有点慢，这里帖vjudge上面的地址）这道题呢，相信大家也不陌生，就是某本算法竞赛书上面的例题了。我第一眼没去看它的分析，而是自己想了想我们之前做的几道状压dp，我觉得这不就是一道三进制的状压dp吗？？书上...

2018-08-16 09:21:10 271 2

原创【NOIP2017】总结

别问我为什么只写了三道题，第四题还没有理解……不说这么多，反正这次noip考的不咋地，220的分你说有多好……为什么呢？一，首先，我觉得我的1，2题还是做得不错的（只是花了1个多小时），至少这两道题得了满分，这使我至少不至于拿不到奖，最后结果也就是最后两道题决定的了。二，我的1,2题花的时间太多了（前面有提到），这使得我的3，4题的结果不是那么的理想……其实上，三题并不是多么难的题，我只是思维有

2017-11-23 13:46:24 171 1

原创【NOIP2017】棋盘

题目描述有一个m × m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费1 个金币。另外，你可以花费2 个金币施展魔法让下一个无色

2017-11-21 14:02:32 1464 1

原创【NOIP2017】图书管理员

题目描述图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他

2017-11-21 13:42:46 1751 1

原创【NOIP2017】成绩

题目描述牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是：总成绩 = 作业成绩× 20% + 小测成绩× 30% + 期末考试成绩× 50% 牛牛想知道，这门课程自己最终能得到多少分。输入只有1 行，包含三个非负整数A、B、C，分别表示牛牛的作业成绩、小测成绩和期末考试成绩。相邻两个数之间用一个空格隔开，三项成绩满分都是100 分。输出只有1 行，包含一个整数，

2017-11-21 13:29:12 1794 1

原创【回溯】八皇后的那些事儿

注：这次是修改了一下，以前写的太差了又不好改，只好重新发一遍。。。八皇后，是回溯的经典题，就不贴题目了，直接说说我的八皇后吧。我看了一会儿书，自己打成这样：bool a[9][9],y[20],q[20],p[20];int tot;int main(int i){ for(int j=1;j<=8;j++) if(!(y[j]&&q[i-j+7]&&p[i+j]))

2017-07-17 23:03:52 184

原创【综合运用】数制转换

咳咳，刚刚做了一道刷了快半年的题，，，，先给大家看看我的惨状：是不是很有意思！好了，到了分析环节了，为了省去大家不必要的时间（才不是怕丢脸呢<-_<-），我就直接从修改过几次的代码开始讲吧。1、//1.13//01:数制转换#include<cstdio>#include<cstring>#include<cmath>int a,b;//a,b储存进制long long x;char

2017-07-17 22:54:29 324

原创【高精】阶乘和

咳咳，这是一道高精的题，好久以前十分弱智的题（弱智吗？？？），只是看起来好难，于是一直放弃。。。可是今天看见了，发现1.6（openjudge）里面竟然就这一个没打钩，于是只好硬着头皮做了。。先贴上题目：15:阶乘和总时间限制: 1000ms 内存限制: 65536kB 描述：用高精度计算出S=1!+2!+3!+…+n!（n≤50）其中“!”表示阶乘，例如：5!=5*4*3*2*1。输入正

2017-07-03 00:54:18 1034 5

原创【基础算法】素数环

题目描述输入正整数n，把整数1，2，3，…，n组成一个环，使得相邻两个整数之和均为素数。小强同学看过这个题，笑了：呵呵，打表！Mr. Wu为了阻止小强打表，决定这样：把全部的解按字典序排序后，从1开始编号，依次输出指定编号的k组解。最后一行输出总的方案数。同一个素数环只算一次。输入第1行：2个整数，n(n第2行：共有k个从小到大排列的整数，表示要输出的解的编号。

2017-05-28 13:35:15 3811 1

little_qiao的博客