2 一只酷酷光儿( CoolGuang)

尚未进行身份认证

我要认证

桃李不言 下自成蹊

等级
TA的排名 2w+

【Nowcoder】追债之旅 | 定长最短路、思维转换

题目链接:https://ac.nowcoder.com/acm/problem/14700题目大意:给出n个点m条边的城镇,求从1~n恰好经过k条边的最短路,k<=10题目思路:n<=1000其实n<=10000应该也可以做考虑dis[i][k]代表从1出发到达i点经历了k条边的最小花费所以更新的话,也就像最短路那么去更新了if dis[e][k+1] > dis[i][k] + w : dis[e][k+1] = dis[i][k...

2020-08-06 01:44:06

【Nowcoder】蓝魔法师 | 树形dp、组合计数

题目链接:https://ac.nowcoder.com/acm/problem/20811题目大意:给出n个点的一棵树,问有多少种删边方案使得删边后各连通块大小小于等于k?题目思路:考虑树形dp与组合数学结合定义dp状态 dp(i,k) 代表 i的子树全部合法且i的连通块大小是k那么显然对于任意一个节点u来说初始:dp[u][1] = 1接下来枚举每一条边,对于一条边来言有删除与不删除两种状态:1.删除:删除此边,那么就意味着当前以u节点连通块大小为k的方案数 都可以

2020-08-05 01:52:19

【Nowcoder】2020牛客暑期多校训练营(第八场)I - Interesting Computer Game | 并查集、思维、离散化

题目链接:https://ac.nowcoder.com/acm/contest/5673/I题目大意:从1~n给出n组数据,每次可以选择a 或者选择b,选了之后不能在选,问最多选多少个?题目思路:和之前总结的一道题很像:https://blog.csdn.net/qq_43857314/article/details/107253264注意到关联性,所以不可以贪心的去搞考虑并查集当一些点连同时如果当前存在n-1条边,也就是是一棵树,你总可以使得有n-1个点被选如果大于等

2020-08-03 17:14:05

【upc】画 (picture) | 区间dp、思维转换

题目描述licunchun 找到了一张画。licunchun 学习了膜法,想要一块一块地,让里面的颜色消失。照片的颜色只有一行。licunchun 每次可以选择中间一段相同颜色的一段直接让它消失。licunchun 想知道所需要的最少次数。licunchun 冥思苦想了1145141919810都没有想出来,于是把问题交给了你。输入第一行输入T,表示数据组数对于每组数据:第一行给定一个n,表示照片的长度。第二行,给定一串s,用来描述这个照片的颜色。为了方便,颜色的描述统一用小写字母

2020-08-02 17:02:25

【upc】 保龄球 (bowling) | 单调队列优化dp

chen03 正在打 爆零球 保龄球。在 chen03 的面前有n个球瓶等距排成一排,从左到右的编号分别为 1,2,...,n。每个球瓶都有一个分值(可能为负数),第i个球瓶的分值为ai。每当 chen03 用球击倒一个球瓶,他就会得到相应的分值。chen03 有 k 个保龄球,每个球的直径为w。也就是说,每个球可以击倒一个长度为w的区间内的所有球瓶。当然,每个球只能投出一次。在某个球瓶被击倒后,球瓶原来的位置会留出空位。另外,球瓶1的左边、球瓶n的右边都有足够的空位。chen03 投出的保龄球可以经

2020-07-31 17:21:06

【Nowcoder】2020牛客暑期多校训练营(第六场)H-Harmony Pairs | 数位dp

本以为自己刷的数位dp够多了没想到这种类型的真的没见过不过没事 学到新知识了!题目链接:https://ac.nowcoder.com/acm/contest/5671/H题目大意:询问在小于n中,有多少对(i,j),使得i的数位和大于j的数位和,但是i<j题目思路:第一反应数位dp .. 肯定数位dp但是我卡在一个地方了..如何才能同时满足两个条件呢然后我就一直在搞 :枚举权值和 分上下两次dp等等..发现去重是个困难的事比赛结束后,看了一下代码瞬间懂了

2020-07-31 00:04:34

【Codeforces 301D】Yaroslav and Divisors | 树状数组、顺序统计

题目链接:https://codeforces.com/contest/301/problem/D题目大意:给出一个n的全排列,m次询问,每次询问区间[x,y]内,有多少对(a,b)满足a%b == 0题目思路:首先可以确定的是,a%b == 0满足因子关系因为n为全排列,所以可以通过筛法把 因子关系都确定之后假设 x在i位置,x的倍数在k位置可以把[i,k]看为一个合法区间所以题目变成了 询问在一个区间内,完全包含多少个合法区间就有了顺序统计的思想枚举右端点,利用记

2020-07-30 18:22:30

【Nowcoder】[AHOI2006]上学路线ROUTE | 最短路、最小割

题目链接:https://ac.nowcoder.com/acm/problem/19874题目大意:给出一张图,每条边都有一个时间与花费,问1~n的最短路 和 最少花费使得1~n的最短路边大题目思路:1~n的最短路变大,那么就需要破坏最短路图所以也就是将最短路图还原出来之后再最短路图上跑最小割即可被最短路卡的疯狂wa 不知道spfa还原问题出在哪~Code:/*** keep hungry and calm CoolGuang!***/#pragma GCC opt

2020-07-30 02:22:13

【upc】奶茶 (milktea) | 并查集、拓扑排序

问题 F: 奶茶 (milktea)时间限制:2Sec内存限制:128 MB提交状态题目描述光阴荏苒,飞鱼奶茶店已经开业几个月了。这天,老翁到奶茶店里买奶茶,顺便问了小鱼一个问题。老翁原先有n+m个正整数,分别是a1,a2,...,an,b1,b2,...,bn,但它们被小Y吃了。她忘记了这些数具体是多少,只记得对于每个数对(i,j),ai和bj的大小关系(可能是大于,小于或者等于)。她还记得这些正整数的中最小的恰为1。老翁问小鱼,在已知条件下,这n+m个正整数中每个数的最小值分...

2020-07-29 17:01:02

【Nowcoder】2020牛客暑期多校训练营(第五场)B-graph | 最小异或生成树

题目链接:https://ac.nowcoder.com/acm/contest/5670/B题目大意:给你一棵树,你可以删除一些边或者增加一些边,但是在过程中必须保证图联通并且出现的任何一个环的异或和为0题目思路:考虑加边成为完全图那么 如何做到加边过程中 做到出现的环为0呢?考虑从任意一个根出发,到达u的异或和为x,到达v的异或和为y那么 u 与 v之间的异或和即为 x^y所以说只需要在u与v之间增加权值为x^y的边这样就可以保证上述两个条件并且成为完全图之后就可

2020-07-28 22:03:55

【Codeforces 888G】Xor-MST | 最小异或生成树、字典树、分治

题目大意:给出n个点的权值,让你求出最小异或生成树:若连接 x,y,则这条边的权值为a[x] ^a[y]题目思路:会这个题首先要会一个01字典树的经典题目:1.询问x与一组数异或中的最大或者最小值2.如果不会这个需要先去学一下这个内容有了此基础之后,便可以在字典树上贪心的进行操作首先考虑一组数在字典树中的表示:现在如果要为4匹配一条边,由图中可以看出绝对是5为6匹配一条边,由图中可以看出绝对是4为什么呢?首先按照字典树贪心的顺序,从高位到底位进行建树.

2020-07-28 22:01:12

【Nowcoder】2020牛客暑期多校训练营(第六场)K- K-Bag | 思维枚举、哈希散列

题目链接:https://ac.nowcoder.com/acm/contest/5671/K题目大意:k-bag的定义是指:一个序列恰好有若干个 长度为k的全排列构成给出一个序列,询问当前序列是否是一个k-bag的连续子序列题目思路:这种题基本就是考虑最终状态考虑最终状态:绝对是在两边加了几个使其变成了k-bag在两边加可以转换为只在左边加,在左边加又可以转换为把前x个隔离出去比如 3-bag 2 3 2 3 1 1 在左边+1个,就相当于保留前2个,后面保留了1个

2020-07-27 17:03:05

【智算之道】2020智算之道初赛第三场题解

A.水杯一个模拟的水题..Code:int main(){ ll water_templat = -1,water_val = -1; ll L,A,B; read(n);read(L);read(A);read(B); for(int i=1;i<=n;i++){ int opt,x;scanf("%d",&opt); if(opt!=3) scanf("%d",&x); if(opt =

2020-07-26 21:24:30

【百度之星】2020初赛第三场 1005(hdu6787) | 经典dp

题目思路:如果掷骰子得话,会最多向前移动11位,所以说如果有连续的11个传送器,那无论结果如何都是过不去得所以题目转换为给你m个传送器,构造长度为n不能有m个连续的传送器得方案数如果没有传送方向,是一个很经典的dp考虑dp j,i,k 代表以i结尾连续的传送器有j个,当前已经放了k个不放:考虑当前位置放还是不放,不放的话应该加上之前连续0~10个:放:首先考虑如何放!第i个连续j个放k个的方案数 应该有dp[i-1][j-1][k-1]转移过来因为此时目的地...

2020-07-26 17:50:14

【Codeforces 1163D】Mysterious Code | AC自动机、fail树上dp

题目链接:https://codeforces.com/contest/1163/problem/D题目大意:首先定义f(s,t)函数,表示t中含有s串个数之后首先给出一个c串,由'*'和小写字母组成,其中'*'可以替换为26个字母中的任意一个之后给出两个串s,t。要求你根据c串中的'*'构造c串使得f(s,c) - f(t,c)最大题目思路:多字符串包含关系必然会想到AC自动机首先考虑,建立AC自动机时,节点得权值情况在字典树上s的终结点权值为1,t的终结点权值为-1

2020-07-26 13:16:39

【upc】小Y的图 | 树上倍增、最小生成树

问题 B: 小Y的图时间限制:1Sec内存限制:256 MB提交状态题目描述小Y有一个n个点的无向图,图中的每个点从1到n标号。图中还有m条边,每条边有一个长度。小Y有Q个询问,每次询问两个点所有路径中,最长的边最小值是多少,若这两个点之间没有任何路径,输出 -1。输入第一行三个整数n、m和Q。接下来m行每行三个整数x、y、z(1≤x,y≤n,1≤z≤1000000),表示有一条连接x和y长度为z的边。接下来Q行每行两个整数x、y(x≤y),表示一组询问。...

2020-07-24 17:22:06

【Codeforces 149E】Martian Strings | KMP、AC自动机

想刷下AC自动机的题,搜出来个这个但是用KMP过了..题目链接:https://codeforces.com/contest/149/problem/E题目大意:给出一个t串,和m个s串,对于每个s串判断是否可以在t串中找出两个子串使得T[a,b] + T[c,d] = s输出所有可以的s串的个数题目思路:Thinking_1嗯...稍后会更新AC自动机的写法考虑kmp,pre_i代表s串前缀与t串前i个前缀匹配的最大长度预处理好pre数组之后将s串翻转,处理

2020-07-24 12:45:28

【HDU 5880】 Family View | AC自动机、敏感词屏蔽

题目大意:给出几个敏感词汇s_i,一个字符串t需要将t字符串中所有的敏感词汇以*的形式输出题目思路:AC自动机板子题..题目比较典型,博客存储一下。不懂评论里可以交流Code:/*** keep hungry and calm CoolGuang!***/#pragma GCC optimize(2)//#include <bits/stdc++.h>#include<stdio.h>#include<string.h>#inc

2020-07-24 03:18:15

【百度之星】2020初赛第一场1007 Mosquito (hdu6749) | 最大流、状态压缩、优化建图

题目大意:中文题意题目思路:首先可以肯定,如果,肯定-1否则的话一定可以跑满所有点。既然一定可以跑满所有点,那么剩下的即为检验问题。可以发现当前的t满足二分的单调性,如果最小的t可以,那么t+1一定也可以。所以说就可以二分当前的时间t,看t是否存在一种合法的分配方案。考虑到一个性质,一个蚊子只能占据一个,所以和网络流相关。接下来就变成了,使用网络流检验当前t是否合法如何建图呢?我们可以这么想:首先S点对k个窗户的流量为a[k],之后每个窗户可以对当前t时间内...

2020-07-23 01:43:09

【upc】 合并果子 | 并查集、树上前缀和

柠檬树上柠檬果,柠檬树下我和我Re-see特别喜欢柠檬。Re-see一共采了n个柠檬。一开始每个柠檬自成一堆。之后她又做了Q次操作1 x y:Re-see觉得不够酸爽,决定把第x个柠檬和第y个柠檬所在的柠檬堆合并。特别的,如果x,y本来就在一堆里,那么什么也不做2 a b:Re-see酸了,对第a个柠檬所在的柠檬堆中每个柠檬挤了b毫升柠檬汁喝。Re-see操作完后决定吃柠檬,请你回答此时每个柠檬被挤了多少毫升柠檬汁输入第一行2个正整数n,Q接下来Q行表示操作输出输出1行..

2020-07-22 16:56:37

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv3
    阅读者勋章Lv3
    授予在CSDN APP累计阅读博文达到30天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取