吴国庆

题解

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

/ 注册

全部文章 / 题解（共38篇）

水题(water)

题意：其中，f(1)=1;f(2)=1;Z皇后的方案数：即在Z×Z的棋盘上放置Z个皇后，使其互不攻击的方案数。题解：打表后可以发现F函数为斐波那契数列，所以问题就变成如何去求x！在m进制下末尾0的个数和Z皇后的个数由于Z<=14 所以说这一部分直接打表即可考虑如何求x！在m进制下末...

2020-04-15

2 837

小H和游戏

题意：小H正在玩一个战略类游戏，她可以操纵己方的飞机对敌国的N座城市(编号为1~N)进行轰炸敌国的城市形成了一棵树，小H会依次进行Q次轰炸，每次会选择一个城市A进行轰炸，和这座城市距离不超过2的城市都会受损(这里距离的定义是两点最短路径上的边数)，轰炸结束后，小H还想知道当前城市A受损的次数作为游...

2020-04-15

3 744

完全平方数

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

2020-04-15

0 659

Music Problem

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

2020-04-15

0 725

相反数

相反数题意：给一个数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 710

【每日一题】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 808

牛客算法周周练1（ABCDE）

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

2020-04-08

0 611

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

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

2020-04-07

0 711

【每日一题】4月7日树

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

2020-04-06

0 708

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

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

2020-04-05

0 520