CallmeChallenger-CSDN博客

原创 2020蓝桥杯国赛J题-质数行者题解

题目链接：https://www.lanqiao.cn/problems/1027/learning/思路：首先观察题干中对走法不同的定义：稍作停留的集合不同。所以可以考虑这么一个DP定义。在数轴上dp[i][j]dp[i][j]dp[i][j]代表从111出发到iii共走了jjj步的方案数方案数大概是n22\frac{n^2}{2}2n2（因为最小的质数是2）转移的复杂度大概是小于等于i的质数数量，大概是log2ilog_2ilog2i预处理dpdpdp数组的时间大概是5e75e75e7

2021-06-03 20:46:11 1698 3

原创树上背包问题

姑且叫做时间戳优化吧我们会遇到一类问题：给你一棵n<=5000的树，要在树上跑树形dp。我们可以轻松的想出dp的定义式，第一维是代表节点，第二维是题目要维护的信息。范围均是5000。如果我们暴力去跑的话，对于每个节点都要枚举所有子节点，并且第二维要枚举当前节点的值和子节点的值。这样效率是O(n3)O(n^3)O(n3)显然是不够的。我们可以加入一个优化，考虑当前子树的size，子树如果比较小，第二维就没有必要枚举那么多。更进一步，我们不要预处理每个子树的size，在dp的时候不断更新，每次的

2021-03-22 15:30:31 242

原创 Educational Codeforces Round 106部分题解

A. Domino on Windowsill题意：给定2∗n2*n2∗n的方格，第一行有k1个白格，第二行有k2个白格。且白格是连续且从1开始。其他位置为黑格。问能否放下w个白色骨牌和b个黑色骨牌（1∗2）（1*2）（1∗2）思路：显然我们可以直接算出两种骨牌放置个数。int _;int n,k1,k2,w,b;int main() { for(_=rd();_;_--){ n=rd();k1=rd();k2=rd(); w=rd();b=rd();

2021-03-19 12:50:39 306

原创 Codeforces 708C - Centroids[换根dp]

其实我也不懂我这个做法是不是换根题意：给定一颗树，你有一次将树改造的机会，改造的意思是删去一条边，再加入一条边，保证改造后还是一棵树。请问有多少点可以通过改造，成为这颗树的重心？（如果以某个点为根，每个子树的大小都不大于n/2 ，则称某个点为重心）题解：显然我们可以通过一次dfs先得到哪些点不用改造就可以成为重心。然后就是处理那些需要改造的点。这棵树如果我们以1为根，那么对于一个节点u,若它在第一次dfs时没有被标记，无非两种情况。1.以u为根的子树有一个节点v,size[v]>n/2

2020-12-16 14:52:37 256

原创 Codeforces Round 688 A-E题解

A.Cancel the Trains题意：横竖都有101条轨道，告诉你两种轨道上都有速度为1的一些火车，问最少取消多少辆使得不出现相撞题解：显然判断一下初始会有多少相撞就取消多少辆火车即可。int _,x,n,m;int vis[105];int main() { for(scanf("%d",&_);_;_--){ n=rd();m=rd(); memset(vis,0,sizeof(vis)); int ans=0;

2020-12-05 16:59:25 172

原创 Codeforces Round 685 A-E题解

A.Subtract or Divide题意：给定一个n，定义两种操作。操作1：n=n-1;操作2：n除以一个非自身的因数问最少几次操作使得n变成1题解：特判一下n=1,2,3的情况别的情况就偶数两次，奇数三次（奇数-1变成偶数）int main() { for(scanf("%d",&_);_;_--){ scanf("%d",&n); if (n==1){puts("0");continue;} if (n==2){

2020-11-23 19:21:51 155 2

原创 2020CCPC长春站F - Strange Memory

题意：给定一个树，每个点上有一个点权，计算题解:使用dsu on tree，把每个数拆开成二进制，存在数组上，在合并的时候统计答案#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll rd(){ ll x=0;char o,f=1; while(o=getchar(),o<48)if(o==45)f=-f; do x=(x<<3)+(x<<1)+(o

2020-11-12 19:19:05 323 2

原创 HDOJ-6191 Query on A Tree(树上启发式合并+trie树）

题意：给定一棵树，每个点有一个权值，每次询问以u为根的子树里，结点与x异或的最大值。题解：离线操作，用树上启发式合并维护trie树，在每个节点上时分别查询x保存起来。#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll rd(){ ll x=0;char o,f=1; while(o=getchar(),o<48)if(o==45)f=-f; do x=(x<<3

2020-11-11 21:16:41 157

原创 Codeforces Round 680 div1 A-B

A. Division题意：给定p,q,请找出最大的x满足p%x=0,x%q!=0.题解：先分类讨论，p%q!=0时,x=p就行了。所以就是讨论在p%q=0的情况下的解首先肯定想的是质因数分解，但是对p质因数分解显然不现实（p<=1e18).所以肯定只能对q。我们发现如果p%x=0,x质因数分解的结果一定是p分解的子集，同理q质因数分解的结果也是p分解结果的子集。如果要x%q!=0.那么肯定在某一个质因子上，x的数量要少于q的数量。具体实现就是对q进行质因数分解，对于q的每一个质因子都得到

2020-11-03 10:40:14 132

原创 Codeforces Round 676 完整题解

A.XORwice题意：给定a,b,你可以随机选择一个数x，求(a⊕x)+(b⊕x)的最小值。题解：在二进制上每一位考虑，如果某一位都是1或0，那么x的这一位就是0，如果一个是1，一个是0，那么他x不管怎么选这一位都会留下。这个过程跟异或是一样的，所以就是a^b。int main() { for(scanf("%d",&_);_;_--){ a=rd();b=rd(); printf("%lld\n",a^b); } return 0

2020-10-18 21:02:27 322 1

原创 CodeForces Round 669A-D题解

A:Ahahahahahahahaha题意：给定一个01串，01串的长度保证为偶数，问删除最多n/2个元素能否使得奇数位和等于偶数位置和题解：首先很明显0对于和是没有影响的，所以在原串中0的数量>=n/2那我们就直接输出n/2个0即可，问题就在于1的数量>n/2的时候怎么办。这时若(n/2)%2=0那我们同理输出n/2个1，若(n/2)%2=1,那就输出(n/2)+1个1（因为此时保证1的数量>(n/2))#include <bits/stdc++.h>using na

2020-09-09 11:34:03 218

原创 Codeforces Round 631 A-D题解

A. Dreamoon and Ranking CollectionA题大家应该都没啥问题叭QAQ 题意就是已经比赛了n场 n场的场次都已经告诉了你问你再比x次问你你最大的名次是多少（这个最大的名次是指 1-当前名次都已经拿过了）然后注意数据范围 n,x<=100 所以最多可以到两百名呢所以记得数组要开200多一点（呜呜我的代码日常很长所以手速很慢#include <bi...

2020-04-05 00:34:29 263 1

CallmeChallenger的博客