- 博客(558)
- 收藏
- 关注
RSS订阅原创 牛客练习赛45
A QAQ:dp[i][0]表示前i个字符可以组成的"Q",dp[i][1]表示前i个字符可以组成的"QA",dp[i][2]表示前i个字符可以组成的"QAQ"。扫一遍即可。#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=1e5+10;char t[5005]...
2019-05-04 12:19:09
268
原创 Wannafly挑战赛1 C:MMSet2
题面最优的点一定在给定点集中最远的两点的简单路径上。#include<bits/stdc++.h>using namespace std;const int maxn=3e5+10;int head[maxn],To[maxn*2],Next[maxn*2],tol;void add_edge(int x,int y){ To[tol]=y; Nex...
2019-04-02 18:43:14
307
1
原创 Codeforces Round #549 (Div. 1) B. Lynyrd Skynyrd(倍增)
题面按照贪心策略，枚举以每个位置为结尾，则往前遍历，找到它的前一个数字最近的出现位置，然后往前跳n-1步，倍增判断一下跳到了哪个点。然后线段树查询一下区间最大值即可。#include<bits/stdc++.h>using namespace std;const int maxn=2e5+10;vector<int>G[maxn];int n,m,Q,...
2019-04-02 18:40:03
257
原创 牛客挑战赛30 C-小G砍树(换根)
题面先考虑1号店最后移除时候的贡献，我们可以钦定1号点为根，并钦定他最后移除然后就是一个树形dp设fifi表示i号点子树移除方案数量，sizeisizei表示1为根时子树大小显然有dp式子fx=(sizex−1)!∏(sizei)!∏fifx=(sizex−1)!∏(sizei)!∏fi(满足1为根时x是i的爹)然后最后移除点1的情况的贡献就算出来了我们考虑换根先考虑...
2019-03-09 18:10:02
279
原创 BZOJ 4423: [AMPPZ2013]Bytehattan(对偶图+并查集维护连通性)
题面/*转成对偶图，若删这条边之前此边对应对偶图中的两个点已经联通，则对偶图中这两点在连一条边就形成了一个割，所以删除这条边两点不连通。*/#include<bits/stdc++.h>using namespace std;const int maxn=3e6+10;int par[maxn],n,k;int Find(int x){ if(x==pa...
2019-01-27 09:58:25
275
原创 hdu 6184 Counting Stars(三元环计数)
题目链接题解链接#include<bits/stdc++.h>using namespace std;const int maxn=2e5+10;int n,m,from[maxn],to[maxn];vector<int>G[maxn],s[maxn];int in[maxn],re[maxn],rev[maxn],val[maxn];int mai...
2019-01-19 19:56:34
175
原创 hdu 6191 Query on A Tree(字典树+启发式合并)
题目链接每个节点建一颗字典树，启发式合并就好了。内存n*logn*logn,内存超限，考虑合并完之后废弃的字典树的节点存一下，后面再次利用。#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=1e5+10;int tree[maxn*55][2],a[maxn]...
2019-01-17 20:38:48
174
原创 hihoCoder #1048 : 状态压缩·二
链接：http://hihocoder.com/problemset/problem/1048题解：https://blog.csdn.net/my_sunshine26/article/details/74612684#include<bits/stdc++.h>using namespace std;const int mod=1000000007;int dp[1...
2019-01-17 20:33:30
239
原创 Codeforces Round #519 by Botan Investments
题目：http://codeforces.com/contest/1043A. Elections枚举k的值#include<bits/stdc++.h>using namespace std;int n,a[105];int work(){ int sum=0,ma=0; for(int i=1;i<=n;i++) sum+...
2018-11-21 14:09:50
223
原创 BZOJ 1013: [JSOI2008]球形空间产生器sphere（高斯消元）
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1013思路：存在二次项，考虑两式相减可以把所有未知数的二次项消掉，n+1 个等式用第一个与后面的做差，形成n个不等式，然后高斯消元即可。代码：#include<cstdio>#include<cmath>#include<algorithm...
2018-11-02 14:46:31
151
原创 BZOJ 2648: SJY摆棋子(kd tree)
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2648#include<bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;const int maxn=1e6+100;int idx,n,m,tol,ans;struct node{ ...
2018-10-26 12:18:24
182
原创 hdu 4347 The Closest M Points （kd tree 模板题）
题目：http://acm.hdu.edu.cn/showproblem.php?pid=4347#include<bits/stdc++.h>using namespace std;#define sq(x) (x)*(x)const int maxn=6e4+10;int idx,n,k,m,lson[maxn],rson[maxn],tol;struct node...
2018-10-26 12:12:32
194
原创 codeforces 1040E. Network Safety
题目：http://codeforces.com/contest/1040/problem/E思路：若x,y之间有一条边，权值分别为a[x],a[y], 设t=a[x]^a[y],则只有a[x]^t==a[y],a[y]^t==a[x],因此只有其中一个数异或上t才是不安全的，两个数都异或上t则相当于交换x,y。可以按0~(1<<k)-1逐个考虑每个x,若x==t时...
2018-09-06 10:08:04
436
原创 codeforces 1037F. Maximum Reduction(启发式合并)
题目：http://codeforces.com/contest/1037/problem/F思路：找出最大的一个点(值相同时取左边的点)，计算以此点为最大值能够形成多少个合法的区间，然后处理该点左右两个区间，一直递归下去。假设以i为左端点，合法的右端点有i+(k-1),i+2*(k-1),i+3*(k-1),i+4*(k-1)i+t*(k-1)不能超过区间的范围。#includ...
2018-09-04 16:39:30
341
原创 2017 CCPP 秦皇岛
题目：链接A - Balloon Robot设机器人从0位置出发， 对于每一个a[i],b[i]算出b[i]时间机器人与s[a[i]]的距离，即所需等待时间，此时如果将机器人位置向前推进1，则它越过的t[i]时间都会加上m，因为要相遇就要多走一圈，然后所有的等待时间-1。代码：#include<bits/stdc++.h>using namespace st...
2018-09-02 10:20:28
146
原创 2018 icpc 南京网络赛
题目：链接A. An Olympian Math Problem输出n-1即可(女朋友猜的)。#include<bits/stdc++.h>using namespace std;#define ll long longll fac[103];int main(){ ll n,T;cin>>T; while(T--) { ...
2018-09-01 22:37:00
2180
原创 2017 icpc 沈阳现场赛
题目：链接F Heron and His Triangle:暴力跑了几发，把搞出来的数扔进oeis里发现对于条件成立的t数组有t[i]=4*t[i-1]-t[i-2]。因此找到第一个大于等于N的t[i]就好了。但是数值范围超过了long long，因此要用大数，这样一个个找过去会超时，可以先对询问排序，这样下次的询问就可以接着上次的位置寻找。代码：#include...
2018-08-30 23:18:56
964
原创 2017 icpc 沈阳网络赛
题目：链接B cable cable cable:观察得，答案为K*(M-K+1)#include<bits/stdc++.h>using namespace std;#define ll long longint main(){ ll M,K; while(~scanf("%lld%lld",&M,&K)) pri...
2018-08-30 22:08:30
526
原创 2017 CCPC 杭州赛区
题面：http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdfProblem A. Super-palindrome：每个奇数长度的子串都是回文，有两种情况：1. aaaaaaa 都是相同字符2.ababababab 两个不同的字符一直交替。枚举每两个字符即可。代码：#include<bit...
2018-08-28 12:34:14
935
原创 codeforce 1027 F. Session in BSU
F. Session in BSUtime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPolycarp studies in Berland State University. Soon he will have...
2018-08-23 10:19:45
260
原创 BZOJ 4568: [Scoi2016]幸运数字(lca+线性基)
4568: [Scoi2016]幸运数字Time Limit: 60 Sec Memory Limit: 256 MBSubmit: 2256 Solved: 921[Submit][Status][Discuss]DescriptionA 国共有 n 座城市，这些城市由 n-1 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立...
2018-08-19 22:58:49
139
原创 BZOJ 2460: [BeiJing2011]元素(线性基)
2460: [BeiJing2011]元素Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 2412 Solved: 1250[Submit][Status][Discuss]Description 相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力...
2018-08-19 22:55:13
157
原创 hdu 3949 XOR(线性基)
XORTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4619 Accepted Submission(s): 1612 Problem DescriptionXOR is a kind of bit operator...
2018-08-19 22:51:35
183
原创 BZOJ 3110: [Zjoi2013]K大数查询(整体二分)
3110: [Zjoi2013]K大数查询Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 11673 Solved: 3512[Submit][Status][Discuss]Description有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2 a b...
2018-08-15 11:22:17
165
原创 洛谷 P1306 斐波那契公约数
对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？Update：加入了一组数据。输入输出格式输入格式： 两个正整数n和m。（n,m<=10^9）注意：数据很大 输出格式： Fn和Fm的最大公约数。由于看了大数字就头晕，所以只要输出最后的8位数字就...
2018-08-14 19:14:14
152
原创 codeforce 1017 F. The Neutral Zone
F. The Neutral Zonetime limit per test5 secondsmemory limit per test16 megabytesinputstandard inputoutputstandard outputNotice: unusual memory limit!After the war, destroyed cities...
2018-08-14 16:17:59
170
原创 POJ 2104 K-th Number(整体二分)
K-th NumberTime Limit: 20000MS Memory Limit: 65536K Total Submissions: 67933 Accepted: 23979 Case Time Limit: 2000MS DescriptionYou are working for Macrohard company in data ...
2018-08-12 21:37:17
234
原创 BZOJ 4372: 烁烁的游戏(动态点分治)
4372: 烁烁的游戏Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 804 Solved: 288[Submit][Status][Discuss]Description背景：烁烁很喜欢爬树，这吓坏了树上的皮皮鼠。题意：给定一颗n个节点的树，边权均为1，初始树上没有皮皮鼠。烁烁他每次会跳到一个节点u，把周围与他距离不超过d的...
2018-08-12 13:04:24
266
原创 BZOJ 3730: 震波(动态点分治)
3730: 震波Time Limit: 15 Sec Memory Limit: 256 MBSubmit: 3441 Solved: 611[Submit][Status][Discuss]Description在一片土地上有N个城市，通过N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为1，其中第i个城市的价值为value[i]。不幸的是，这片土地常常发生地震...
2018-08-10 18:06:54
214
原创 BZOJ 1095: [ZJOI2007]Hide 捉迷藏(动态点分治)
1095: [ZJOI2007]Hide 捉迷藏Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 5415 Solved: 2276[Submit][Status][Discuss]Description 捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏...
2018-08-10 17:29:23
250
原创 hdu 6356 Glad You Came(倍增)
Glad You CameTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 777 Accepted Submission(s): 269 Problem DescriptionSteve has an integ...
2018-08-06 21:44:25
227
原创 hdu 5909 Tree Cutting(树形dp+树上点分治)
Tree CuttingTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)Total Submission(s): 1291 Accepted Submission(s): 498 Problem DescriptionByteasar has a tree...
2018-08-05 21:34:23
259
原创 hdu 6336 Problem E. Matrix from Arrays
Problem E. Matrix from ArraysTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1286 Accepted Submission(s): 583 Problem DescriptionKa...
2018-08-05 16:54:32
128
原创 hdu 6341 Problem J. Let Sudoku Rotate(数独)
题目：http://acm.hdu.edu.cn/showproblem.php?pid=6341思路：预处理每一个4*4 格子旋转的四种状态。然后dfs即可，时间上限4^(16) 但是实际上数独限制较多，大多数情况中途已经剪掉。代码： #include<bits/stdc++.h>using namespace std;char txt[20][20];in...
2018-08-05 16:47:10
258
原创 hdu 4812 D Tree(树上点分治)
D TreeTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)Total Submission(s): 6331 Accepted Submission(s): 1347 Problem DescriptionThere is a skyscraping ...
2018-08-04 09:50:25
252
原创 hdu 5977 Garden of Eden(树上点分治)
Garden of EdenTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1844 Accepted Submission(s): 602 Problem DescriptionWhen God made th...
2018-08-03 15:31:52
521
原创 SPOJ COT - Count on a tree(LCA+主席树)
COT - Count on a tree#tree You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.We will ask you to perform the following operation:u v ...
2018-08-02 09:31:42
145
原创 HDU 6333 Problem B. Harvest of Apples(莫对算法)
Problem B. Harvest of ApplesTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 647 Accepted Submission(s): 235 Problem DescriptionTher...
2018-08-01 22:38:43
169
原创 BZOJ 2653: middle(二分+主席树)
Description一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。 Input第一行序列长度n。接下来n行...
2018-07-31 20:37:56
160
原创 牛客练习赛23 托米的游戏(概率，期望)
链接：https://www.nowcoder.com/acm/contest/156/F来源：牛客网 题目描述题目背景编不下去了托米有一棵有根树 T, 树根为1，每轮他会在剩下的子树中等概率一个点 u, 砍掉 u 的子树 (包含 u)，如果树上的点都被砍光了，游戏结束。求出这个游戏进行的期望轮数，可以证明这个数一定是有理数，设他为 , 你需要告诉他一个整数 x 满足 输入描述...
2018-07-29 20:31:07
238
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人