- 博客(16)
- 收藏
- 关注
RSS订阅原创 2018icpc沈阳网络预选赛 G题（容斥）
题目：https://nanti.jisuanke.com/t/31448题意：打表发现，求思路：正着求不好求，我们可以求 总和减去与m不互质的数的贡献 与m不互质的数我们可以分解m的质因子，对于当前的因子，我们会有这些数与m不互质对于因子的贡献就为该式就等于然后因子个数奇数个加偶数个减容斥一下就可以了。#include <iostream>#inc...
2018-09-08 20:36:35
412
原创 FZU 2303（数学期望）
http://acm.fzu.edu.cn/problem.php?pid=2303题意：在一个链式的n人追随者体系中，给你m块蛋糕，你可以把蛋糕分给其他人，每个人只能分一次，当你把蛋糕分给i时，你可以获得i的信任以及i的追随者的信任，问你分m快蛋糕取得的信任期望值。 思路：看了别人的题解， 推一遍公式上代码#include <algorithm>#includ...
2018-08-01 10:56:45
619
原创 codeforces 600C（贪心）
http://codeforces.com/problemset/problem/600/C题意：给你一个字符串，你可以改变它的任意字符，且可以任意调换字符顺序，输出字符改变次数最少的字典序序最小的字符串。（改变顺序次数不计）。思路：记录所有字符出现的次数，从小到大，当出现次数为奇数时，找到最右边一个出现次数为奇数的字符，左边字符数+1，右边字符数-1。处理到最后一定会是最多只存在一个出现...
2018-07-25 09:45:24
251
原创 埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 L（dp）
https://www.nowcoder.com/acm/contest/91/L#include<iostream>#include<bits/stdc++.h>using namespace std;const int maxn=1e5+5;const int maxk=1e7+5;int dp[2][maxk];int num[maxn];int main(){ int
2018-04-16 19:11:58
203
原创 牛客网 Wannafly挑战赛12 C（dp）
https://www.nowcoder.com/acm/contest/79/C比赛的时候没想到，看了别人的题解才做出来。#include<iostream>#include<string>#include<string.h>#include<stdio.h>using namespace std;int dpa[15],dpb[15];//dpa(b)[i]分别表示以a(b)结尾，i
2018-03-26 16:53:13
183
原创 poj 2762
http://poj.org/problem?id=2762 题意：给你n个房间，m条单向边，问你对于任意的x,y是否都有一条道路从x到y，或者从y到x。思路：先用tarjan缩点，再用拓扑排序，如果发现去掉一个点之后有新增两个入度为0的点，则不能。附上测试数据 4 4 1 2 2 3 3 4 2 4 Yes4 3 1 2 2 3 2 4 No#include <iostrea
2017-11-27 20:02:50
283
原创 双联通分量 HDU4738
题意：给你一张图，求w最小的桥。 http://acm.hdu.edu.cn/showproblem.php?pid=4738注意：可能不是联通图（先用并查集判断联通），没有人的时候要输出1，没有桥输出-1。#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#define MAXN 100
2017-11-14 20:06:12
132
原创 poj 1679（次小生成树）
http://poj.org/problem?id=1679 题意：给你一个图，求最小生成树是否唯一。 思路：求次小生成树，看它和最小生成树的权值是否相等。#include<iostream>#include<string.h>#include<stdio.h>#include<algorithm>#define INF 99999999using namespace std;int
2017-10-13 21:08:59
161
原创 hdu 1069（dp）
题意 ：给你n种方块， 每种方块有n种，你可以任意摆放，如果方块A的长和宽都小于方块B的长和宽，则方块A可以叠在方块B上，求你所能叠起来的最大高度。题解 ：一开始认为是贪心，后面发现貌似不可以。这道题是dp，状态转移方程 ：dp[i]=max(dp[i],dp[j]+block[i].h)#include <iostream>#include <stdio.h>#include <string.
2017-09-27 21:23:37
137
原创 zoj 3870
题意：给你一个数列，选出其中两个数A,B，求满足A^B>max(A,B)的个数。思路：假设A>B，”A^B>A”的条件是在A的二进制位为从左往右数ai为0的位置bi为1，如A=1111011011，则满足条件的B为00001XXXXX或00000001XX。#include <iostream>#include <stdio.h>#include <string.h>using namespa
2017-09-25 17:14:11
159
原创 zoj 3872（dp）
题意：我们定义数列的美为该数列的所有不相同的元素的总和，下面给你一个数列，让你求它所有子数列的美的总和。思路：当新增加一个数，它会和前面所有数都组成一个子数列，如1 2 3当加入第四个元素4时，就会有新增4个子数列 “4”，”3,4”，”2,3,4”，”1,2,3,4”，设它们为S1，当1 2 3 4 加入第五个元素5时，则会新增”5”,”4,5”,”3,4,5”,”2,3,4,5”,”1,2,3,
2017-09-25 16:50:41
192
原创 zoj 1610（线段树染色问题）
题意：染色后求一段区间上各个颜色的段数#include <iostream>#include <stdio.h>#include <string.h>using namespace std;struct node{ int l,r,w,f;}tree[8005*4+5];int a,b,x,num[8005],last;void build(int l,int r,int k
2017-09-20 21:38:41
536
原创 hdu 1166（线段树or树状数组）
线段树代码：#include <iostream>#include <stdio.h>#include <string.h>using namespace std;int n,x,y,a,num,ans;struct node{ int l,r,w,f;}tree[4*50000+1];void build(int l,int r,int k){ tree[k].l=
2017-09-15 21:37:37
122
原创 HDU 2846（Tire的变形）
http://acm.hdu.edu.cn/showproblem.php?pid=2846题意：给你p个字符串，q次询问，问p个字符串中含有q的字符串的个数。思路：看了别人的题解，讲p个字符串的后缀也存入字典树，但是这样会有abab这种字符串出现重复计数的情况，用vis作为标记，鶸表达能力有限，详细看代码。#include <iostream>#include <stdio.h>#includ
2017-09-13 21:40:24
361
原创 poj 2478 （欧拉函数）
http://poj.org/problem?id=2478题意：定义一个序列Fn是不可约有理数a / b的集合，(n>=b>a>0且gcd(a,b)=1）。思路：Fn为2到n欧拉函数的值的总和。#include <iostream>#include <stdio.h>#include <string.h>#define maxn 1000005#define ll long longus
2017-09-11 21:48:47
190
原创 hdu 5428(质因数分解)
http://acm.hdu.edu.cn/showproblem.php?pid=5428题意：给你一个数列，让你求这个数列的乘积的最小的因子，该因子应包含两个以上的因子（包括1和本身），比如4包含3个因子，那么它满足这个条件。如果找不到满足条件的因子，输出-1。思路：对每个因子分解质因数，如果质因数的个数大于或等于2，最小的两个质因子的乘积便是答案，否则输出-1。#include <iostre
2017-09-11 20:43:30
337
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人