1 henucm

尚未进行身份认证

那就再努力一点吧

等级
博文 206
排名 3w+

BZOJ 2460(线性基)

题意:一个物品有两个属性,a和b。现在有很多这样的物品,要求从中取任意个,使得取出的物品中,任意几个物品的属性a的异或和不为0,同时满足b的和最大。首先,满足b的和最大,所以显然要按照b进行排序,首先选取b大的。然后就是满足a的异或和不为0。这里根据线性基的性质,线性基里面任意几个基底的异或值不为0,所以只要能够成功添加入线性基里面的向量,都可以直接满足这个要求,把其对应b的值加入结果。一直尝...

2019-05-28 00:10:24

线性基 (暂时先挖个坑)

定义设数集T的值域范围为[1,2n−1]。T的线性基是T的一个子集A={a1,a2,a3,...,an}。A中元素互相xor所形成的异或集合,等价于原数集T的元素互相xor形成的异或集合。可以理解为将原数集进行了压缩。性质1.设线性基的异或集合中不存在0。2.线性基的异或集合中每个元素的异或方案唯一,其实这个跟性质1是等价的。3.线性基二进制最高位互不相同。4.如果线性...

2019-05-24 01:18:45

ubuntu18.04安装微信,QQ,TIM等常用软件

一终端执行导入仓库命令sudowget-O-http://package.elementaryos.cn/apt/key/package.gpg.key|sudoapt-keyadd-二编辑/etc/apt/source.list文件sudovim/etc/apt/sources.list最后一行后插入debhttp://package.eleme...

2019-05-24 00:19:54

Codeforces gym 101612 Consonant Fencity (状态压缩+二进制枚举)

http://codeforces.com/gym/101612/attachments题意:是给定你一串字符,分为元音字母和辅音字母,将辅音字母变成大写,要构成尽量多的大写字母和小写字母的组合,最后输出改变后的字符串。思路:由于辅音字母的数量才19个,少到可以状态压缩,将相邻点建边,边权为1,这样可以将字符串转化为1个图,相邻字符的出现次数可以表现为图的权值,然后用二进制去枚举每一种...

2019-05-18 12:38:54

2018 ICPC EC-final i题Misunderstood Missing 倒序DP

http://codeforces.com/gym/102056/problem/I题意:有两种值A,D,A代表攻击一次怪兽能对怪兽造成的伤害。D代表每回合开始时A的增量。初始值均为0给出三种操作,求使用这三种操作在n回合后可以达到的对怪兽伤害的最大值:1.攻击怪兽,造成A+a[i]伤害。2.不攻击怪兽,但使D增加b[i]。3.不攻击怪兽,但使A增加c[i]。思路:题...

2019-05-14 15:14:09

Codeforces 451E Devu and Flowers 组合数+容斥原理

http://codeforces.com/problemset/problem/451/E题目大意:有n个花坛,要选s支花,每个花坛有f[i]支花。同一个花坛的花颜色相同,不同花坛的花颜色不同,问说可以有多少种组合。解题思路:2n的状态,二进制枚举出那些花坛的花取超过了,剩下的用C(n−1sum+n−1)隔板法计算个数,注意奇数的位置要用减的,偶数的位置用加的,容斥原理。#i...

2019-05-11 15:50:50

hdu 6397 组合数+容斥定理

http://acm.hdu.edu.cn/showproblem.php?pid=6397题意:给三个数n,m,k,在0~n-1中选出m个数排成一排使得他们的和等于k,这m个数可以相同,只要排列不同即可。求一共有多少种排列方式是满足题意的。思路这道题需要用到隔板法我们先引入一个问题,有x个小球,放到m个盒子里,每个盒子不能为空,问有多少种放法。这里保证每个小球都是相同的,并且。分...

2019-05-10 21:49:19

HDU 6400 Parentheses Matrix(构造)

今天又是一场自闭赛http://acm.hdu.edu.cn/showproblem.php?pid=6400题意:给一个只含'('和')'的矩阵,只考虑从行和列上的括号序列,构造一个矩阵使得合法括号序列的总数最多思路:第一眼看着就觉得应该分奇偶来判断然后开始分类讨论1.奇奇不可能随意输出就行2.奇偶如果行数为偶数那么列就是奇数我们需要构造成...

2019-05-09 21:22:33

2019年湘潭大学程序设计竞赛(重现赛) F 二分+前缀和

https://ac.nowcoder.com/acm/contest/893/F首先预处理出前缀和,a[i]表示这个区间有多少个1然后二分答案,最对答案进行O(n)验证只需判断区间内0或1的个数加上m是否不小于当前二分的答案即可时间复杂度O(nlongn)#include<stdio.h>#include<string.h>#include<m...

2019-05-05 15:09:40

2019年湘潭大学程序设计竞赛(重现赛)ABCD

https://ac.nowcoder.com/acm/contest/893#questionA#include<stdio.h>#include<string.h>#include<math.h>#include<map>#include<set>#include<deque>#include&lt...

2019-05-05 15:06:34

CodeForces - 1070 A Find a Number(记忆化宽搜)

http://codeforces.com/contest/1070题意:给出两个正整数d和s,求最小的正整数n,使得n为d的倍数,且n的每一位加起来等于s。思路不难想到搜索,但是n可能很大,以至于超出longlong的范围,显然这个题还没有复杂到综合考察大数运算。所以在这里使用一个带有数论知识的DP。vis[i][j]i为余数j为位数和。根据...

2019-05-04 15:52:22

牛客练习赛45 A B C

https://ac.nowcoder.com/acm/contest/847#questionA找到A前面Q的数量*后面Q的数量最后注意是longlong类型#include<stdio.h>#include<string.h>#include<math.h>#include<map>#include<set...

2019-05-04 12:36:42

Educational Codeforces Round 64 (Rated for Div. 2) A B C

传送门A题意:给你n个图形1代表圆2代表等妖三角形高等于底边长3代表正方形求n个图形内切有多少个不同的点若他们内切点为无数则输出Infinite这种就是无解的情况然后还有一种情况就是312正方形圆三角形他们三者内切我们需要-1#include<iostream>#include<algorithm>#...

2019-05-02 17:59:35

Codeforces Round #556 (Div. 2) A B C

传送门A题意:给你早上买入和晚上卖出股票价格(股票数量无限)以及你所拥有多少钱,问一晚后你最多能够拥有多少钱#include"bits/stdc++.h"#definelllonglongusingnamespacestd;intmain(){ inta[1100],b[1100]; intn,m,r; cin>>n>>m&gt...

2019-05-02 13:07:50

hdu 5446 Lucas+中国剩余定理

传送门题意:给你三个数n,m,k,第二行是k个数,p1,p2,p3...pk,所有p的值不相同且p都是质数,求C(n,m)%(p1*p2*p3*...*pk)的值思路:我们知道题目要求C(n,m)%(p1*p2*p3*...*pk)的值其实这个就是中国剩余定理最后算出结果后的最后一步求余那C(n,m)相当于以前我们需要用中国剩余定理求的值然而C(n,m)太...

2019-05-02 01:13:31

2019浙江省赛B zoj4101 Element Swapping(推公式)

传送门题意:数组a通过交换一对数字,得到了b数组,给出x=∑nk=1kak和y=∑nk=1ka2k和b数组,问有多少对l,r(l<=r)能满足条件思路:假设交换了(i,j),那么:i*a[i]->i*a[j],j*a[j]->j*a[i]因此对于原来的x、y有:可以得到:将得到的两个式子相除,有:第一个式子可以化简为X−x=...

2019-05-02 00:53:50

P1869 愚蠢的组合数 卢卡斯定理

传送门#include<cstdio>typedeflonglongll;llfact(intn,llp){//n的阶乘求余pllret=1;for(inti=1;i<=n;i++)ret=ret*i%p;returnret;}voidex_gcd(lla,llb,...

2019-04-30 18:37:45

数论 组合数

组合数大家应该不陌生一般我们用杨辉三角性质杨辉三角上的每一个数字都等于它的左上方和右上方的和(除了边界)第n行,第m个就是,就是C(n,m)(从0开始)递归式模板时间复杂度是O(n^2)#include<cstdio>constintN=2000+5;constintMOD=(int)1e9+7;i...

2019-04-30 00:42:00

数论 素数

嗯...也没啥好说的存个板子找到时候方便点判断一个数是否是素数时间复杂度是O(√n)boolprime(intx){//判断x是不是质数,是返回true,不是返回falseif(x<=1)returnfalse;for(inti=2;i<=sqrt(x+0.5);i++){//0.5是防止根号的精度误差...

2019-04-30 00:36:05

deque 的用法

和queue差不多这里就放一张图就ok了忘了的时候方便找

2019-04-28 14:14:42
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。