吴国庆

分类

acm(50) Codeforces(6) Xcpc(4) 未归档(2) 算法学习(6) 题解(38)

/ 注册

全部文章（共106篇）

完全平方数

题意：多次查询[l,r]范围内的完全平方数个数定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x0<=l,r<=1e9 题解：预处理出范围内所有完全平方数（小于1e5个），然后分别二分l，r所在的位置做差就可以代码： #pragma GCC optimize(2) #...

2020-04-15

0 662

Music Problem

题意：给n个时间长度（秒），问这些时间是否能组成3600的倍数 -- 题解：方案1：bitset<3603>b，记录每个时间是否能够得到，枚举每个数的贡献：最后看b0是否为1即可方案2：普通背包，令dp[i]表示i是否到达，然后转移即可，注意转移顺序！！代码 1 #pragma ...

2020-04-15

0 737

相反数

相反数题意：给一个数n，输出n颠倒后的数与n的和 n<1e5 代码 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define...

2020-04-15

0 718

【每日一题】4月9日 Running Median

题目描述 For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the m...

2020-04-08

0 814

牛客算法周周练1（ABCDE）

A Maximize The Beautiful Value 题目大意：给一单调不减序列，问进行一次操作和序列的最大值是多少？操作为：选择下标为j的数字使他向前移动大于等于k个位置,显然j>k; 题解: 显然贪心来讲，大的数位置越靠后越大，所以对于每个数我们肯定贪心的向前移动K个位置，...

2020-04-08

0 603

【每日一题】4月8日黑白树

题目描述一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[...

2020-04-07

0 715

【每日一题】4月7日树

题目描述 shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数题解太妙了太妙了，1.首先既然任意相同颜色的点的路径均为一个颜色，那这其实就是当于一个联通块。那么本题...

2020-04-06

0 717

【每日一题】4月2日月月查华华的手机

题意给一主串s，有m次询问，每次询问串t是否为s的子序列题解很简单的一道题呀！考虑最暴力的方法：每次询问的串直接在主串上扫描复杂度为O(nsumbi)但其实这其中有很多步骤是没有意义的我们只需要把每种字母出现的位置存进一个vector里，然后对于每次询问，只需循环模拟二分就可以啦！时间复杂度...

2020-04-05

0 530

【每日一题】4月1日 Rinne Loves Edges

题目描述 Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 w现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。定义...

2020-04-05

0 581

【每日一题】3月31日城市网络

题目描述有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。在每次行程开始时，你手上有...

dp

2020-04-05

0 652