1 C202044zxy

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

[模板] Matrix-Tree 定理

一、题目点此看题二、解法本题就是矩阵树定理中外向树的情况。矩阵树定理原来求的是生成树的数量,但是这里要求生成树边权乘积之和,观察行列式的定理,不难发现矩阵构建时换成边权就行了。有两个结论:外向树的度数矩阵是到该点的入边权值总和;内向树的度数矩阵是到该点的出边权值总和如果需要指定iii为根,那么就删除iii行iii列的再求行列式即可原理作者没有搞太懂,中考完了再深究吧。#include <cstdio>#include <iostream>using name

2020-07-08 13:24:28

CQOI2020 游记

DAY 0总觉得会考后缀自动机(结果没有),然后摸了摸鱼。DAY 1第一题没过多久就想出来606060分的做法,然后写了。第二题很快想出来404040分的二项式定理,然后写了。T1,T2T1,T2T1,T2感觉就难以优化了,一直在想T3T3T3(可能想了两个多小时),还是什么分都拿不到。Day 2第一题写了暴力,状压dpdpdp没想到,303030分。第二题写了暴力,101010分。第三题知道是matrix-tree\text{matrix-tree}matrix-tree定理,但是我不会

2020-07-01 17:40:49

[省选联考 2020 A 卷] 组合数问题

一、题目点此看题二、解法trdnr手把手教你推式子,这就是大佬吧,i了i了先把多项式展开(算系数对应的贡献):∑i=0nai∑k=0nki×xk(nk)\sum_{i=0}^na_i\sum_{k=0}^nk^i\times x^k\binom{n}{k}i=0∑n​ai​k=0∑n​ki×xk(kn​)这里需要用到第二类斯特林数的知识,先要康康这个。感觉一个比较套路的东西是用第二类斯特林数展开幂次,由于斯特林数的下标不能过大(这里展开xkx^kxk的话斯特林数就会含kkk,而含iii的话要好做

2020-06-27 11:38:27

CF623E Transforming Sequence

一、题目点此看题二、解法首先有一个显然的dpdpdp,设dp[i][j]dp[i][j]dp[i][j]为前iii轮选jjj个的方案数:dp[i][k]=∑dp[i−1][j]×C(n−j,j−k)×2jdp[i][k]=\sum dp[i-1][j]\times C(n-j,j-k)\times 2^jdp[i][k]=∑dp[i−1][j]×C(n−j,j−k)×2j发现这样很不好优化,我们设f[i][j]=dp[i][j]C(n,j)f[i][j]=\frac{dp[i][j]}{C(n,j)

2020-06-19 11:01:47

[十二省联考2019]异或粽子

一、题目点此看题二、解法

2020-06-19 09:50:14

CF712E Memory and Casinos

一、题目点此看题二、解法这道题正向走不通,要反向做,设dp[i]dp[i]dp[i]为iii到终点的概率:fi=fi−1×(1−pi)+fi+1×pif_i=f_{i-1}\times(1-p_i)+f_{i+1}\times p_ifi​=fi−1​×(1−pi​)+fi+1​×pi​fi−fi−1=pi(fi+1−fi)f_i-f_{i-1}=p_i(f_{i+1}-f_i)fi​−fi−1​=pi​(fi+1​−fi​)设gi=fi−fi−1g_i=f_i-f_{i-1}gi​=fi​−fi−

2020-06-18 19:55:48

[HDU 1814] Peaceful Commission

一、题目点此看题二、解法这就是2-sat\text{2-sat}2-sat带字典序最小解的经典问题,时间复杂度O(n2)O(n^2)O(n2),还是结合代码讲更好:#include <cstdio>#include <iostream>using namespace std;const int M = 20005;int read(){ int num=0,flag=1;char c; while((c=getchar())<'0'||c&gt

2020-06-17 21:58:51

[HDU 4421]Bit Magic

一、题目点此看题二、解法我们分成0−300-300−30位分别考虑,判断合法就用2-sat\text{2-sat}2-sat,设iii表示000,i+ni+ni+n表示111,我们考虑建图。或运算:如果是111,连(i,j+n),(j,i+n)(i,j+n),(j,i+n)(i,j+n),(j,i+n);如果是000,连(i+n,i),(j+n,j)(i+n,i),(j+n,j)(i+n,i),(j+n,j)(这样保证只会选000,因为111一定不合法)与运算:如果是111,连(i,i+n),(

2020-06-17 20:56:12

Eliminate the Conflict

一、题目点此看题二、解法因为不能失败,所以只能有两种选择,我们尝试把它转化成2−sat2-\text{sat}2−sat问题。先处理出能选的两种出法(ai,bia_i,b_iai​,bi​),考虑k=0k=0k=0(相同)时候怎么建图:如果ai≠aja_i\not=a_jai​​=aj​,连(ai,bj),(aj,bi)(a_i,b_j),(a_j,b_i)(ai​,bj​),(aj​,bi​)如果ai≠bja_i\not=b_jai​​=bj​,连(ai,aj),(bj,bj)(a_

2020-06-17 19:08:12

[POJ 3683]Priest Johns Busiest Day

一、题目点此看题二、解法如果在开始时进行婚礼,那么就定义它为真,否则它为假。如果两个人在开始时冲突,那么至少一个人需要选择在结束时,也就是x′∨y′x'\vee y'x′∨y′,其他情况类推然后2-sat\text{2-sat}2-sat,时间主要是建图,时间复杂度O(n2)O(n^2)O(n2),坑点就是时间相等时是合法的。#include <cstdio>#include <iostream>#include <stack>using namespa

2020-06-16 22:05:54

[模板] 2-SAT问题

一、题目点此看题二、解法考虑用图论的方式解决,把每个点xxx拆成两个点xxx和x′x'x′,分别表示该点选111和000的情况,有向边的含义就是选了起点就必选终点,来建边:x∨yx\vee yx∨y,考虑xxx选000,yyy就必须选111;yyy选000,xxx就必须选111,也就是连(x′,y),(y′,x)(x',y),(y',x)(x′,y),(y′,x)x∨y′x\vee y'x∨y′,连(x′,y),(y,x)(x',y),(y,x)(x′,y),(y,x)x′∨yx'\vee y

2020-06-16 20:51:15

CF850E Random Elections

一、题目点此看题二、解法三个候选人其实是一样的,所以我们求出AAA的答案,然后把答案乘333就行了。考虑如果A−BA-BA−B,A−CA-CA−C这两个投票情况的iii位(第iii的选民投的票),如果是(0,0)(0,0)(0,0)(AAA都不赢),那么就有BCABCABCA和CBACBACBA,同理可得,如果是(1,0)(1,0)(1,0)和(0,1)(0,1)(0,1)那么111种方案,(1,1)(1,1)(1,1)也是两种方案。综上,这一位异或为000就两种情况,否则只有一种。我们把fff数

2020-06-15 21:20:09

CF914G Sum the Fibonacci

一、题目点此看题二、解法首先明确我们需要干什么:(f[sa∣sb]×cnt[sa∣sb])&(f[sc]×cnt[sc])&(f[sd⊕se]×cnt[sd⊕se])(f[s_a|s_b]\times cnt[s_a|s_b])\&(f[s_c]\times cnt[s_c])\&(f[s_d\oplus s_e]\times cnt[s_d\oplus s_e])(f[sa​∣sb​]×cnt[sa​∣sb​])&(f[sc​]×cnt[sc​])&

2020-06-15 16:01:15

CF662C Binary Table

一、题目点此看题二、解法观察到nnn很小,我们肯定要从这里入手,设iii列的状态压缩为sis_isi​,我们先枚举行的翻转选择xxx,那么列翻转后的状态是yi=si⊕xy_i=s_i\oplus xyi​=si​⊕x,设fif_ifi​为二进制iii最少有多少个111(可翻转),那么答案就是:∑i=1mfsi⊕x\sum_{i=1}^m f_{s_i\oplus x}i=1∑m​fsi​⊕x​我们枚举这个sis_isi​和yiy_iyi​,那么xxx就不需要了,设qiq_iqi​为有多少列的初始状态

2020-06-13 21:49:05

[学习笔记] min-max容斥

结论及证明给定集合SSS,max(S)max(S)max(S)为集合SSS中的最大值,min(S)min(S)min(S)为集合SSS中的最小值,则我们有一个式子:max(S)=∑T⊆S(−1)∣T∣−1×min(T)max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}\times min(T)max(S)=T⊆S∑​(−1)∣T∣−1×min(T)不多说,直接开证(淦 ),首先我们设一个容斥系数f(∣T∣)f(|T|)f(∣T∣)使这个式子成立:max(S)=∑T⊆Sf(∣T

2020-06-13 20:51:42

[HAOI2015]按位或

一、题目点此看题

2020-06-13 20:17:21

创世纪

一、题目题目描述applepi手里有一本书《创世纪》,里面记录了这样一个故事……上帝手中有着N 种被称作“世界元素”的东西,现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素,所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它,这样上帝就可以保持对世界的控制。由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大石头的二律背反命题,我们知道上帝不是万能的,而且不但不是万能的,他甚至有事情需要找你帮忙——上帝希望知道他最多可以

2020-06-13 15:31:57

无聊的数对

一、题目点此看题二、解法本题的关键是理解:x xor y 的二进制表示下有奇数个1如果xxx有奇数个111,yyy有奇数个111,那么x⊕yx\oplus yx⊕y一定有偶数个111,可以发现只有一个为奇数个111,一个为偶数个111的情况异或起来才是奇数个111,问题转化成了在这些区间的并集中有多少个数奇数个111,有多少个数偶数个111显然就可以用动态开点线段树了,如果一个点被完全覆盖,如果他是叶子,判断加到哪一维,否则000的个数和111的个数都是len/2len/2len/2,当然需要从0

2020-06-13 15:10:01

[JOI 2018 Final]毒蛇越狱

一、题目点此看题二、解法考虑一个子集反演:f(s)=∑i∈sg(i)f(s)=\sum_{i\in s} g(i)f(s)=i∈s∑​g(i)g(s)=∑i∈s(−1)∣s∣−∣i∣f(i)g(s)=\sum_{i\in s}(-1)^{|s|-|i|}f(i)g(s)=i∈s∑​(−1)∣s∣−∣i∣f(i)下面给出证明:f(s)=∑i∈s∑j∈i(−1)∣i∣−∣j∣f(j)f(s)=\sum_{i\in s}\sum_{j\in i}(-1)^{|i|-|j|}f(j)f(s)=i∈s∑​j

2020-06-12 20:59:00

[WC2018] 州区划分

一、题目点此看题二、解法设dp[s]dp[s]dp[s]为选出来的点状压为sss,所得到的满意度总和,转移:dp[s]=1f[s]∑i∈sdp[i]×g[s−i]dp[s]=\frac{1}{f[s]}\sum_{i\in s}dp[i]\times g[s-i]dp[s]=f[s]1​i∈s∑​dp[i]×g[s−i]其中f[s]f[s]f[s]是www总和的ppp次方,g[s]g[s]g[s]是www总和的ppp次方 乘上 这个状态是否合法。显然这个柿子可以用快速子集卷积,然鹅我TTT了,不说

2020-06-11 22:05:25

查看更多

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