xyq0220 - 个人主页动态 - 牛客网

发布(104) 刷题

2020-10-14 00:48

牛客练习赛71 C- 数学考试 DP

牛客练习赛71 C- 数学考试 题意 求 的排列，有 个限制条件，第个限制条件 表示前 个数不能是 的排列，求符合要求的排列的个数。 答案对 20000311 取模。 做法1 设为满足限制的情况下放好了排列的前个数且最大值为的方案数，转移如下： ，说明这一位有限制。 否则，，表示若，那么第位只能放一种数，若，第位可以放种数，前面的部分可以前缀和优化。 复杂度为。 做法2 设为放置前个数满足前个限制，但是不满足第个限制的方案数。 ，为放置前个数不满足第个限制的方案数，对于，减去放置前个数满足前个限制不满足第个限制的所有方案数，表示从到的位置可以随意放，这样就可以不重复的计算出，在...

0 点赞评论收藏

转发

2020-10-13 16:18

牛客练习赛71 E- 神奇的迷宫点分治+NTT

牛客练习赛71 E- 神奇的迷宫 题意 给一颗个点的树，每条边的长度均为，Alice和Bob两人依次传送到树的某两个结点。对于任意一个人，传送到点的概率为，假设两人传送到的结点之间的最短距离为，那么他们挑战这个树的困难度为。 问他们挑战这个树的困难度的期望是多少。 分析 令表示两人最短距离为的概率，答案即为。 求可以用点分治来做，以作为分治中心时，枚举每个子树，用表示已经枚举过的子树中到根的距离为的点的概率之和，用表示当前子树中到根的距离为的点的概率之和，那么就可以更新，注意到这是一个卷积形式，所以我们对做一次卷积就能更新，因为答案要取模，所以用来做卷积。 复杂度为。 Code #inclu...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>字符串hash模板</span>

typedef long long ll; typedef unsigned long long ull; #define maxn 1005 struct My_Hash { ull base=131; ull p[maxn],ha[maxn]; void Insert(char s[]) { int len=strlen(s+1); p[0]=1,ha[0]=0; for(int i=1;i<=len;i++) { p[i]=p[i-1]*base; ...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>2020牛客暑期多校训练营（第二场）J 置换群，欧几里得求逆元</span>

题意 给一个大小为\(n\)的全排列\(A\)和一个整数\(k\)，让你找出一个置换排列\(P\)，使得\(\{1,2,\dots,n\}\)对\(P\)做\(k\)次置换后为\(A\)。 分析 把\(A\)的所有环求出来，设这些环的大小为\(r_1,r_2,\dots,r_c\)。因为\(k\)是大质数，所以可以对每个\(i\)求一个\(inv_i=k^{-1}(mod~r_i)\)，这个只需要把\(A\)中的第\(i\)个环转\(inv_i\)次就可以得到答案。 Code #include<algorithm> #include<iostream> #in...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>Gym-101987 2018-2019 ACM-ICPC, Asia Seoul Regional Contest K-TV Show Game 2-sat，tarjan</span>

题意 \(k\)盏灯，每盏灯有两种颜色R，B。有\(n\)个人，每个人猜三盏灯的颜色，让你求这\(k\)盏灯的颜色，使每个人都至少猜对两盏灯的颜色。 分析 转化成\(two-sat\)问题，对于每个人若猜错其中一盏灯，那么另外两盏灯的颜色必须猜对，建边，跑\(tarjan\)，输出答案。 Code #include<algorithm> #include<iostream> #include<cstring> #include<iomanip> #include<sstream> #include<cstdio>...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>Gym-101810 G ACM International Collegiate Programming Contest, Amman Collegiate Programming Contest (2018)</span>

题意 字符串\(S\)的能量\(P(S)\)定义为 \[P(S)=\sum_{i=1}^{n}N_i\times V_i \] \(N_i\)是满足\(S_i=S_j\)的下标\(j(i<j\le n)\)的个数，\(V_i\)是字符\(S_i\)的\(ASCII\)码。 给一个长度为\(n\)的字符串\(s\)和一个整数\(k\)，你可以对字符串\(s\)做最多\(k\)次操作，每次操作你可以将字符串\(s\)中的任意一个字符\(s_i\)变为任意一个小写字母。你的目标是最大化字符串\(s\)的能量。 分析 首先，字符串\(s\)的字母的顺序不会影响答案，令\(cn...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>Gym-102001，2018 ICPC Asia Jakarta Regional Contest K Boomerangs</span>

题意 给一个\(n\)个点\(m\)条边的无向图\(G=(V,E)\)，让你找最多有多少个回力镖，回力镖是一个三元组\((u,v,w)\)表示边\((u,v)\subseteq E\)且边\((v,w)\subseteq E\)，每个边只能存在于一个回力镖中。 分析 dfs深搜，回溯过程中将当前结点\(u\)的前向边两两组成回力镖，如果多出了一条边就和u的父亲组成回力镖，这样构造最多会浪费每次dfs的根节点连的一条前向边，所以总答案为每个连通块的边数向下整除2的和。 Code #include<algorithm> #include<iostream> #in...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>codeforces 1373G Pawns 线段树</span>

题意 给一个\(n\times n\)的空棋盘，棋盘的第\(k\)列是一个特殊的列，有\(m\)次操作，每次增加一个棋子或者移走一个棋子，如果能使用以下规则将所有棋子移动到第\(k\)列，那么这个棋盘是好的。 在格子\((x,y)\)位置的棋子，能移动到\((x,y+1),(x+1,y+1),(x-1,y+1)\); 你能做任意次移动； 棋子不能移动到棋盘外； 每个格子只能放一个棋子。 你可以在棋盘顶部增加一些行，使棋盘能够是好的。每次操作后，问棋盘至少增加多少行，可以将它变成好的。 分析 令\(f[x]\)为有多少棋子要在第\(x\)行上面，答案为\(max(...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>codeforces 1369E DeadLee</span>

题意 李的店里有\(n\)种美食，第\(i\)种美食有\(a_i\)个，李有\(m\)个朋友，第\(i\)个朋友喜欢第\(x_i\)和第\(y_i\)个两种不同的美食，每个朋友来到店会吃两种他喜欢的美食各一个，如果其中一种美食不够了就只吃另一种美食，李想让你帮他安排朋友到店的先后顺序，使他的每个朋友都至少吃到一种美食。 分析 令\(s_i\)为每个朋友两种食物都吃到的情况下第\(i\)种食物需要的个数。 若存在\(s[i]<=a[i]\)，则无论如何喜欢这个食物的人都能得到满足，我们可以将喜欢这个食物的人往后放，并将他们喜欢的另一种食物\(x\)的需要个数\(s[x]\)减一，继...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>codeforces 1373F Network Coverage</span>

题意 给一个\(n\)个点的环，每个点是一个容量为\(a[i]\)的空水池，给\(n\)个水桶，第\(i\)个桶里有\(b[i]\)升水，第\(i\)个桶只能给第\(i\)和第\(i+1\)个水池加水，特殊的，第\(n\)个桶只能给第\(n\)个和第\(1\)个水池加水，问是否能将所有水池加满。 分析 二分\(b[1]\)给\(a[1]\)加了多少水，我们可以贪心的得到\(b[1]\)给\(a[2]\)加了多少水，\(b[2]\)给\(a[2]\)加了多少水.... 有两种情况： 断流，因为\(b[1]\)给\(a[1]\)加了太多的水，导致无法加满\(a[2],a[3],\d...

0 点赞评论收藏

转发

2020-07-14 00:10

已编辑

<span>gym-102082，2018-2019, ICPC, Asia Yokohama Regional Contest 2018 J Colorful Tree</span>

题意 给定一个\(n\)个点的树，每个点有个初始颜色\(c_i\)，有\(m\)次询问，询问有两种： \(U~x_k~y_k\)，将第\(x_k\)个点的颜色改为\(y_k\)。 \(Q~y_k\)，找到一个边数最少的子图，使得这个子图包括所有颜色为\(y_k\)的点，输出这个子图的边数。 分析 对每种颜色的点用一个set来存，set的排序规则按照dfs序，能发现每修改一个点的颜色对该颜色的答案的贡献只和其在set中前后的两个点\(l,r\)有关，set中增加一个点\(x\)对答案的贡献为\(dis(l,x)+dis(x,r)-dis(l,r)\)，删除一个点对答案的贡献...

0 点赞评论收藏

转发

2020-07-14 00:11

已编辑

<span>codeforces 1367 F1，F2 Flying Sort</span>

题意 给出一个长度为\(n\)的数组\(a\)，每次操作能将一个数移动到数组的首位或末尾，问最少经过多少次操作能将这个数组变成单调不降的。 分析 在\(F_1\)中数组\(a\)的每个数字互不相同，我们发现只要找到最长的连续上升子序列（连续指在数组排序后两个数字是相邻的），n减去它的长度\(len\)即为答案，因为这个序列是有序的，只需要\(n-len\)次操作将其他位置的数移动到这个序列的两边使数组整体有序即可。 在\(F_2\)中数组\(a\)中可能会有相同的数字，我们可以用近似的方式去做，找到一个最长的连续不降子序列且除了首尾的数字，和序列中的其他数字相同的数字都要在这个子序列中...

0 点赞评论收藏

转发

2020-07-14 00:11

已编辑

<span>“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 C 张老师的旅行</span>

题目链接 分析 设\(dp[l][r][0]\)为走过区间\([l,r]\)的景点且落脚点为\(l\)用的最短时间，\(dp[l][r][1]\)为走过区间\([l,r]\)的景点且落脚点为\(r\)用的最短时间。 则有转移: \(dp[l][r][0]=min(dp[l+1][r][0]+p[l+1]-p[l],dp[l+1][r][1]+p[r]-p[l])\)。 \(dp[l][r][1]=min(dp[l][r-1][1]+p[r]-p[r-1],dp[l][r-1][0]+p[r]-p[l])\)。 转移的过程中要判断一些合法情况和边界情况。 Code #...

0 点赞评论收藏

转发

2020-07-14 00:11

已编辑

<span>“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 H-时空栈</span>

题目链接 分析 将时间\(t\)离散化，按\(t\)建线段树，维护每个时间\(t\)的栈的大小\(s[t]\)。 在时间\(t\)入栈一个数即为将区间\([t,n]\)加\(1\) 在时间\(t\)出栈即为将区间\([t,n]\)减\(1\) 查询时间\(t\)的栈顶元素， 找到时间\(t\)之前的最后的某个时间\(t1\)满足\(s[t1]<s[t]\)，那么在\(t1+1\)时刻必定有一个入栈操作，且入栈的数即为时间\(t\)的栈顶元素。 Code #include<algorithm> #include<iostream> #in...

0 点赞评论收藏

转发

2020-07-14 00:11

已编辑

<span>Codeforces 1349A 1350C Orac and LCM</span>

题意 给出一个长度为\(n\)的数组\(a\)，计算\(\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})\)。 分析 对每个数质因子分解，对每个质因子用数组存下出现的幂次。 单独考虑一个质因子\(p\)对答案的贡献，若\(a_i,a_j\)中质因子\(p\)的幂次分别为\(k_1,k_2(k1,k2>=0)\)，那么\(\textrm{lcm} (a_i,a_j)\)中\(p\)的幂次为\(\textrm{max} (k_1,k_2)\)。 若\(n\)个数都有质因子\(p\)，且\(n\)个数中第二小的幂次为\(k\)，贡献即为\(...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务