又是一个签到题目，但是要注意一些坑点。首先sqrt不一定会返回int型，其次要特殊考虑a=0的case，因为我们使用的是f(r)-f(l-1)当a=0，sqrt(l-1)会变成sqrt(-1),会出错。 #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; while(n--) { int a,b; cin>>a>>b; if(a==0){ cout&...

题目大概意思是这样的，我们有一颗树，有q次询问，每一次会轰炸给出这个点的距离不超过二的点，每一次输出当前这个点被轰炸的次数。我们这个题目需要一些tricks，想想我们怎么样可以把每次轰炸的点的距离不超过2的点这么描述出来并且做到不重复不遗漏呢？我们可以这样考虑，我们使用一个eff数组，eff[u][0]表示u这个点的轰炸次数，eff[u][1]表示u这个点的儿子们轰炸次数，eff[u][2]表示u这个点的孙子们轰炸次数，那么每次轰炸一个点u,需要更新的是eff[fa[now]][0]++;//父亲节点自己eff[fa[now]][1]++;//父亲节点的儿子们eff[fa[fa[now]]][...

这个题数据范围太小，甚至不需要用手写的大数加法。 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> #include<stack> #include<map> #include<set> #include<queue> #include<iomanip> #include<string> ...

A题：这个题目直接贪心就好了，题目要求最大值那么我们来考虑一下，由于是非递减的序列，那么我们若走k步以上就会更小，不满足题意，所以我们只要枚举哪个点向前走k步。取所有可能情况的max,就可以快乐ac~~ #include<bits/stdc++.h> #define int long long using namespace std; int a[100010],sum[100010]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; c...

这个题可以用贪心的思想。我们要想染色最少次数，那么就一定要从叶子节点开始，因为有可能使得叶子结点的k[i]用得上。这个题目还有最重要的一点是要更新k[i],就是在dfs的时候，用儿子节点去更新该节点的k[i]，最远染色距离。那么我们就dfs来维护当前的最远染色距离，从儿子节点转移来的要记得减一，因为用了一个距离在父亲与儿子节点上，然后就快乐dfs就好了~~ #include<bits/stdc++.h> using namespace std; int n; int ans=0; const int N=2e5+10; vector<int> e[N]; int k[N...

这个题看起来无从下手，但是仔细分析会发现，我们dfs得出每个子树的节点个数，如果是奇数，那么我们就需要加上这条连向这个点的边权值，因为奇数个点不可能完成题目要求两两分组。如果节点个数为偶数就不用管。 #include<bits/stdc++.h> using namespace std; const int N=2e4+10; int h[N],e[N],w[N],ne[N],idx; long long ans; void add(int a,int b ,int c) { w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int...

题目大意是给你两个整数l,r，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。这个题我们可以考虑枚举因子，我们考虑从1-r段所有的数码出现次数，我们假设a和b是因子，那么a最大取 ，那么我们就只要两次循环，第一层枚举a，第二层枚举b，但是为了简便运算过程，我们再额外加一层循环，k从1取到9，分别记录a和b的首位数字，这里要注意别重复计数。最后我们直接f(r)-f(l-1)就可以得到结果了~ #include using namespace std; #define int lo...

题意是：给你n个背包，每个背包装了mi个物品，每个背包选一个，要求出选出物品价值前k小 的不同方案种数，很容易联想到背包dp。那么怎么做呢？我们可以考虑dp[i][j]表示前i个背包选出来价值和为j的方案个数，则有 dp[i][k]+=dp[i-1][k-a[i][j]];这个是状态转移方程，具体看代码CODE #include<bits/stdc++.h> using namespace std; int n,k; int dp[105][10010],a[105][110]; //dp[i][j]代表前i个宝盒我选了价值为j的方案数量 void solve() { ...

这个题简单，只要暴力的去判断是否是由连续的mq组成的，那么如果长度为奇数一定不可以，那么对于偶数长度，我们两个两个看，如果出现两个不是mq的就输出No，否则输出Yes code #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int main() { char s[N]; int t; scanf("%d",&t); while(t--) { scanf("%s",s); if(strlen(s)%2) { ...

这个题仔细分析观察，应该是要线性的时间复杂度，那么如何做呢？我们可以发现，我们要的是每一次加入元素后的中位数的值，那么我们就可以联想到使用堆来存储，这样就可以在线性时间复杂度求解。我们定义两个堆，一个是前半段q1，一个是后半段q2。在构造优先队列的时候，我们要把前半段定义成大根堆，后半段定义成小根堆，这样子有什么好处吗？答案是肯定的。因为我们这样子可以保证我们要的中位数一定是在前半段的队头或者后半段的队头（想想为什么）。我们每一次插入的时候，我们和前半段的队头进行比较，如果更大就加到后半段里面，否则加到前半段。这里有一个值得注意的地方，我们要维护前半段和后半段的数量差不超过1这样才能保证中位数...

这道题 千万别看错题误以为是kmp，其实不是的！！注意题目说的是子序列而不是子串，所以kmp不行那么这道题该怎么做呢？仔细想想，既然它给定了你一开始那个s字符串，就是待匹配的字符串，那么我们要做的就是去预处理一下。用一个dp数组，dp[i][j]代表第i个字符后面最近的'a'+j字符的位置，我们从后往前跑一遍，用last数组记录当前的26个字母位置（没有的话就是-1），这样的话，我们只要边从后往前遍历s字符串，再一边跟新last数组就OK啦。最后对于给定的字符判断一下，对于每一个检测字符如果找不到下一个字符就返回false，否则代表能找到返回true。 #include<bits/std...

首先我们可以注意到最后一行m=n-1,那么这个无向连通图就是一棵树了。那么再仔细的分析下，题目要求除了s之外度为1的点都不能到达s，那么除了s之外的度为1 的点就是叶子节点了，那么问题转化为了 如何删掉边权最短的一些边，从而使得s到不了任何一个（注意是任何一个）叶子节点。 思索了一下，这个题应该可以dfs+dp求解，我们可以令dfs(u)返回 u这个点到不了任何一个叶子节点的最小代价，那么对于任何一个点u 和它的非父亲节点v有两种选择。 选择删除u和v连着的边 即Wuv 选择删除使得v到不了任何一个子节点的代价，即dp[v] 那么我们就只要对这两种情况取min就可以。最后记得开long lo...

我们要考虑的是把这棵树分成最多min(n,k)个块，因为要保证每个块颜色不同最多有k种颜色，所以不能超过k，又因为最多有n个点，所以也不能超过n，因此最多分min(n,k）个块。 如果知道这个思路就好做了，我们只要分的块数用组合数公式 C(k,x)表示从k种颜色里挑出来x种颜色，C(n-1,x-1)表示从n-1条边选x-1条边，表示如何把这棵树分为x块。最后乘上x!表示这x种颜色的染色顺序，就能得到最终答案啦。为了简化运算，我们事先写一个循环把jc数组表示出来，jc[i]代表i的阶层。算的时候不要忘记取模，就可以快乐ac啦~ #include<bits/stdc++.h> #de...