头像

ytczy666




离线:2天前


分享 sss

ytczy666
15天前

因为处理玩完一颗子树后,它要么是颜色都相同(显然不用再管它了)
要么显然是留到它的父亲,留一条路径延伸过来。
那么显然就是子树中存在一条到根的路径。
使得这条路径上的点与其他点不同。
那么我们设计三位DP
设f[u][0/1][0/1]
表示u这颗子树它最终变为了哪种颜色且是否留了路径
那么我们考虑第三维是0的情况:
若如果我们最终要变成与根节点相同的颜色。
f[u][c][0] = f[l][c][0] + f[r][c][0]
f[l][c^1][1]



新鲜事 原文

ytczy666
1个月前
明天要月考(草),仍然慌语文,作文这tm的是啥啊


活动打卡代码 AcWing 340. 通信线路

ytczy666
1个月前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <deque>
using namespace std;
const int N=1010,M=10010;
int n,m,k;
int head[N],to[M<<1],nex[M<<1],w[M<<1],cnt;
int dis[N];
bool vis[N];
deque<int> q;

void add(int u,int v,int c){
    to[++cnt]=v;
    w[cnt]=c;
    nex[cnt]=head[u];
    head[u]=cnt;
}

bool check(int x){
    memset(dis,63,sizeof dis);
    memset(vis,0,sizeof vis);
    dis[1]=0;
    q.push_back(1);
    while(q.size()){
        int u=q.front();
        q.pop_front();

        if(vis[u])continue;
        vis[u]=true;

        for(int i=head[u];i;i=nex[i]){
            int v=to[i],c=w[i]>x;
            if(dis[v]>dis[u]+c){
                dis[v]=dis[u]+c;
                if(!c)q.push_front(v);
                else q.push_back(v);
            }
        }
    }
    return dis[n]<=k;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1,u,v,c;i<=m;++i){
        scanf("%d%d%d",&u,&v,&c);
        add(u,v,c),add(v,u,c);
    }
    int l=0,r=1e6;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid))r=mid-1;
        else l=mid+1;
    }
    if(l==1e6+1)
        puts("-1");
    else printf("%d",l);
    return 0;
}


活动打卡代码 AcWing 1129. 热浪

ytczy666
2个月前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N=2510,M=6210,inf=0x3f3f3f3f;
int n,m,s,t;
int head[N],to[M<<1],nex[M<<1],w[M<<1],cnt;
int dis[N];

struct node{
    int u,d;
    bool operator < (const node &b) const{
        return d>b.d;
    }
};
priority_queue<node> q;

void add(int u,int v,int c){
    to[++cnt]=v;
    w[cnt]=c;
    nex[cnt]=head[u];
    head[u]=cnt;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,u,v,c;i<=m;++i){
        scanf("%d%d%d",&u,&v,&c);
        add(u,v,c),add(v,u,c);
    }

    memset(dis,63,sizeof dis);
    dis[s]=0;
    q.push((node){s,0});

    while(!q.empty()){
        node x=q.top(); q.pop();
        int u=x.u,d=x.d;
        if(d>dis[u])continue;
        for(int i=head[u];i;i=nex[i]){
            int v=to[i],c=w[i];
            if(dis[v]>d+c){
                dis[v]=d+c;
                q.push((node){v,dis[v]});
            }
        }
    }
    printf("%d",dis[t]);
    return 0;
}


新鲜事 原文

ytczy666
2个月前
啊啊啊作文好难写啊(((



ytczy666
3个月前

题意

$\;$
现在有一个长度为$n$的序列$a$,你最多可以进行$k$次单点修改,最小化$max(|a_i-a_{i-1}|)$
$$n,k\leq 2\times 10^3,\; -10^9 \leq a_i\leq 10^9$$

样例

$\;$
$In:$
$6\;\;3$
$1 \;\;2 \;\;3 \;\;7 \;\;8 \;\;9$
$\;$
$out:$
$1$
$\;$

Solution

$\;$
看到最小化一个最大值这条信息,马上想到的应该就是二分
所以我们二分答案这个最大值,问题就被我们转化成了:判断是否可以通过不超过 $k$ 次操作使得序列任意相邻两个数差的绝对值小于$mid$
而这个东西我们是可以DP的。但如何设计状态?
我们发现如果仅仅这样设计:”设$f_i$表示$1$到$i$中要满足条件最少要修改多少次”,这个东西是很难进行转移的,因为序列是会进行修改的,而这个DP状态无法考虑修改的情况。
我举个例子可能会更好理解一些:
正常地,按照这个例子,若$a_i$进行了修改,状态转移是:$f_i=min(f_i, f_{i-1} +1)$,条件是:$|a_i-a_{i-1}|>mid$
但我们发现:$f_{i-1}$这个值不一定是在$a_{i-1}$没被修改的情况下得到的。而若其恰好会被修改,换句话说,$a_{i-1}$并不是原来的值,那么$|a_i-a_{i-1}|>mid$这个条件就出现错误了
$\;$

正确设计状态

$\;$
所以我们针对$a_{i-1}$并不是原来的值这个问题来思考如何改进状态。
因为在原先的状态中,我们并不知道$a_{i-1}$是否被修改,所以我们不妨强制其不被修改,然后把DP值中” 最少要修改多少次 “改为” 最多有多少个数不被修改
那么状态就变为了:设$f_i$表示$1$到$i$中要满足条件最多有多少个数不被修改,且强制$a_i$不被修改。
而这里状态转移略微有些变化:由于我们不知道上一个不修改的地方是哪里,所以我们枚举$j\;(1\leq j < i)$
那么$[j+1,i-1]$这段区间进行修改需要满足的条件是$|a_i-a_j| \leq mid \times (i - j)$ (应该比较好理解)
直接$n^2$枚举进行状态转移,与$LIS$问题的转移方程有点类似
而最后判断是否可行时,我们需要枚举序列中最后一个没被修改的位置$x$,看看$f_x$是否$\geq n-k$。而如果整个序列找不到这样的$x$说明不可行
那么这道题就做完了。
时间复杂度:$O(n^2)$
$\;$

Code

#include <bits/stdc++.h>
const int N = 2010;
#define LL long long
int n, K, dp[N];
LL a[N];
LL get_abs(LL a, LL b)
{
      if(a < b) std::swap(a, b);
      return a - b;
}
bool check(LL mid)
{
      for(int i=1;i<=n;i++) dp[i] = 1;
      for(int i=1;i<=n;i++)
      for(int j=1;j<i;j++)
      {
      if(get_abs(a[i], a[j]) <= 1LL * (i - j) * mid) dp[i] = std::max(dp[i], dp[j] + 1);
      }
      for(int i=1;i<=n;i++) if(dp[i] >= (long long)n - K) return true;
      return false;
}
int main()
{
      scanf("%d%d", &n, &K);
      for(int i=1;i<=n;i++) scanf("%lld", &a[i]);
      LL l = 0, r = 2000000000;
      while(l < r)
      {
      LL mid = (l + r) >> 1;
      if(check(mid)) r = mid;
      else l = mid + 1;
      }
      printf("%lld", l);
      return 0;
}



ytczy666
3个月前

博客食用更佳~ https://www.cnblogs.com/czyty114/p/13474327.html

题意

$\;$
给定三个数$n,d,mod$。现在需要你求出,满足有$n$个节点,除了度数为$1$的节点,其它节点的度数都为$d$的不同构的树的数量。输出答案对$mod$取模的结果。
$$n\leq 1000, \;d\leq 10, \;10^8\leq mod \leq 10^9$$

Solution

$\;$
一般来说,计数类问题需要满足的条件是不能重复,不能遗漏
什么是不同构?如下三棵树就是同构的

所以我们首先要确定一棵树的根,否则这棵树可能会被重复算多次。
$\;$

确定根节点

$\;$
但是根节点并不能随便的挑选一个。这里我们挑选重心作为根节点。
原因就在于:重心在一棵树上是唯一的(当然有特殊情况是两个,这个我们后面会陈述),所以对于一棵树来说,它只会在以其重心为根时会被算一次,从而避免了算重复。
而重心还满足什么性质?我们知道,重心将整棵树分成的联通块中最大的那个不超过整棵树大小的一半。
而根据重心的这几条性质,我们就可以考虑进行DP。
$\;$

考虑DP

$\;$
状态设计:
首先,因为我们最终要得到一颗$n$个节点的树,所以第一维状态表示这棵树有$i$个节点。
其次,由于最终每个点的度数都为$d$,所以第二维状态表示根节点有$j$棵子树。
最后,由于我们要满足根节点是重心的条件,所以第三维状态表示根节点下面的子树大小都不超过$k$
综上所述。$f_{i,j,k}$表示$i$个节点,其中根节点有$j$棵子树,且子树大小都不超过$k$的树的数量。
状态转移:
由于树是不同构的,所以我们并不关心子树之间的相对顺序,所以我们DP的时候默认子树是从小到大排的。
因为子树大小都是不超过$k$的,而若子树大小都小于$k$,那么状态转移可得:$f_{i,j,k}=f_{i,j,k-1}$
否则说明有若干棵子树大小是等于$k$的,则我们枚举有$t$棵这样的子树,那么除去这$t$棵子树,剩下部分的状态即为$f_{i-t\times k,j-t,k-1}$。
而由于子树之间是可以相同的。
所以这$t$棵子树的方案数,实际就是从$f_{k,d-1,k-1}$这么多数量中选出$t$棵且可以重复的方案数,即为:$C(f_{k,d-1,k-1}+t-1,t)$
那么状态转移可得:$f_{i,j,k}=f_{i-t\times k,j-t,k-1} \times C(f_{k,d-1,k-1}+t-1,t)$
$\;$

统计答案

$\;$
直接输出$f_{n,d,\lfloor \frac{n}{2} \rfloor}$?那说明你太天真了~
注意:这里的DP是基于一棵树只有一个重心的情况。而对于那些有双重心的树,是会被会算两遍的,所以我们要将这种情况减去一遍。
那么我们来分析,什么时候会出现双重心的情况?
显然,只有可能是一条边连接的两个点分别挂着两颗点数相同的子树,如下图:

而我们发现,这种情况一定有偶数个节点。
而对于这种情况的数量,如何求呢?
因为是两个节点分别挂着两颗点数相同的子树,而这样树的数量显然就是$f_{n/2,d-1,n/2-1}$
而此时方案数即为从$f_{n/2,d-1,n/2-1}$这么多数量选出不重复的两个,即为$C(f_{n/2,d-1,n/2-1},2)$
为什么这里必须是不重复?
因为按照我们DP的过程,两边子树相同这样的情况只会被我们算一遍。(因为儿子是可以交换的)
这个地方还需读者稍微理解一下。
综上所述:
当$n$为奇数时,$Ans = f_{n,d,\lfloor \frac{n}{2} \rfloor}$
当$n$为偶数时,$Ans = f_{n,d,\lfloor \frac{n}{2} \rfloor}-C(f_{n/2,d-1,n/2-1},2)$
那么整道题就做完了。
但有一些DP的边界条件还是要多多注意,细节都在代码里。
而且不要忘记要特判,当$n\leq 2$时直接输出$1$即可
$\;$

Code

#include <bits/stdc++.h>
const int N = 1010;
int n, d, mod, f[N][20][N], fac[20], Inv[20];
int ksm(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = 1LL * ans * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int C(int n, int m)
{
    if(m > n) return 0;
    int ans = 1;
    for(int i=n-m+1;i<=n;i++) ans = 1LL * ans * i % mod;
    ans = 1LL * ans * Inv[m] % mod;
    return ans;
}
int main()
{
    scanf("%d%d%d", &n, &d, &mod);
    if(n == 1 || n == 2)
    {
        puts("1");
        return 0;
    }
    fac[0] = Inv[0] = 1;
    for(int i=1;i<=d;i++) fac[i] = 1LL * fac[i - 1] * i % mod;
    Inv[d] = ksm(fac[d], mod - 2);
    for(int i=d-1;i>=1;i--) Inv[i] = 1LL * Inv[i + 1] * (i + 1) % mod;
    for(int i=0;i<=n;i++) f[1][0][i] = 1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=std::min(d,i-1);j++)
        {
            for(int k=1;k<=n;k++)
            {
                f[i][j][k] = f[i][j][k - 1];
                for(int t=1;t<=j;t++)
                {
                    if(i >= t * k && j >= t && k - 1 >= 0)
                    {
                        //printf("%d\n", C(f[k][d - 1][k - 1] + t - 1, t));
                        if(k > 1)
                        f[i][j][k] = (f[i][j][k] + 1LL * f[i - t * k][j - t][k - 1] * 
                        C(f[k][d - 1][k - 1] + t - 1, t) % mod) % mod;
                        else
                        {
                            f[i][j][k] = (f[i][j][k] + 1LL * f[i - t * k][j - t][k - 1] * 
                            C(f[k][0][k - 1] + t - 1, t) % mod) % mod;
                        }
                    }
                }
            }
        }
    }
    int res;
    if(n & 1)   
        res = f[n][d][n / 2];
    else
        res = (f[n][d][n / 2] - C(f[n / 2][d - 1][n / 2 - 1], 2) + mod) % mod;
    printf("%d", res);
    return 0; 
} 



ytczy666
3个月前

博客食用更佳: https://www.cnblogs.com/czyty114/p/13455596.html

题意

$\;$
给定一棵$n$个点的树$T$,和一张$n$个点$m$条边的图$S$,求有多少种点之间的对应关系的方案使得$T$为$S$的一个子图(等价于$T$中的每条边在某种点的对应关系下在$S$中都存在)
$$n\leq 17$$
$\;$

Solution

暴力

$\;$
一种朴素的想法就是暴力的枚举每一种对应方式:
如下是$n=3$的情况,箭头左边是树中的每个点,右边对应的是图中的每个点
1->1, 2->2, 3->3
1->1, 2->3, 3->2
1->2, 2->3, 3->1
1->2, 2->1, 3->3
1->3, 2->1, 3->2
1->3, 2->2, 3->1
然后我们对每种情况我们再用$O(n)$的时间去判断树中的每条边是否在图中都存在即可
时间复杂度:$O(n!\times n)$
$\;$

子集枚举DP

$\;$
我们由题中得出$T$是一棵树,而其实如果$T$是一张图,用上面的暴力算法也是可做的,所以我们要思考如何利用树的特殊性质来挖掘隐含的细节
我们发现,题中的最大难点并不是处理$T$是$S$的子图这个限制条件,而是去计算点之间的对应关系,使得方案数不重不漏
所以我们得到了一个思路:在树$T$上进行树形DP
$\;$
首先是设计状态
第一维:$i$,当然存的是以$i$为根的子树的信息
第二维:$j$,由于子树与外界之间还有限制条件,即:根节点$i$与其父亲在DP中在图中分别对应的点会有边的限制条件,所以$j$表示的是$i$在图中的对应点
第三维:$k$,由于树上的每个点只能唯一对应图中的点,所以如果只有前两维状态,我并不能知道目前这棵子树中每个点已经对应到了图中的哪些点,所以就可能导致我们会算重,即:树上的某几个点对应到了图中的同一个点上,所以$k$是表示我们目前选的点集,用一个压缩后的二进制数来表示
综上所述:$f_{i,j,k}$表示以$i$为根的子树,其中$i$对应的是图中的编号为$j$的点,且子树中已经选了集合为$k$的点,满足这棵子树是$T$中把集合为$k$的点在其中的对应点挑出来所对应的图的子图
呃,可能有点长,读者可以仔细地多读几遍再消化理解。
那么对于子图也就是边的这个限制条件,我们只需在DP的过程中判断$i$与它的每个儿子在图中是否有边即可。
因此状态转移方程也易得出:
$$f_{i,j,k}=\prod_{v\in son_u} \sum_{p\in Edge_{p,j}} \sum_{q\in k} f_{v,p,q}$$
时间复杂度:$O(n^3\times 3^n)$
$\;$

容斥原理优化

$\;$
我们发现,上面的DP限制时间的主要因素是我们枚举了$k$,也就是我们目前选的点集。
这样导致时间暴增。
我们考虑如何去优化这个东西。
而仔细分析即可发现枚举$k$是为了防止算重,那我们不妨可以大胆的扔掉$k$,直接进行DP。
而这样的时间复杂度只有$O(n^3)$
但这样显然是错的。
所以我们考虑如何去减掉重复的情况。
我们发现,因为多个点对应图中的一个点。那么图中一定存在若干个点没有与树中的点对应
于是这个东西就可以容斥了:我们在图中枚举与树中对应的点有哪些,记为点集$A$,容斥系数显然为$(-1)^{n-|A|}$
则我们就可以通过这种方式,在DP时只需选我们枚举的点集进行状态转移即可。
时间复杂度:$O(n^3 \times 2^n)$
$\;$

Code

#include <bits/stdc++.h>
const int N = 20;
#define LL long long
int n, m, mp[N][N], c[N], len;
LL res, f[N][N];
std::vector<int> G[N];
void Dfs(int u, int fa)
{
    for(int i=1;i<=len;i++) f[u][c[i]] = 1;
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i];
        if(v == fa) continue;
        Dfs(v, u);
        for(int j=1;j<=len;j++)
        {
            LL now = 0;
            for(int k=1;k<=len;k++)
            {
                if(mp[c[j]][c[k]]) now += f[v][c[k]];
            }
            f[u][c[j]] *= now;
        }   
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        mp[u][v] = mp[v][u] = 1;
    }
    for(int i=1;i<n;i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v); G[v].push_back(u);
    }
    for(int S=1;S<(1<<n);S++)
    {
        memset(f, 0, sizeof(f));
        len = 0; int cnt = 0;
        for(int i=0;i<n;i++)
        {
            if(S >> i & 1) c[++len] = i + 1, cnt ++;
        }
        Dfs(1, 0);
        LL t;
        if((n - cnt) & 1) t = -1;
        else t = 1;
        for(int i=1;i<=len;i++) res += t * f[1][c[i]];
    }
    printf("%lld", res);
    return 0;
} 



ytczy666
4个月前

这是一篇用递推方式写的数位DP,大家可以借鉴参考~

#include <bits/stdc++.h>
#define LL long long
const int N = 20;
const LL mod = 1000000007;
int T;
LL L, R, nums[N], cnt, f1[N][7][7][2][2], f2[N][7][7][2][2], f3[N][7][7][2][2]; 
LL Solve(LL n)
{
    cnt = 0; memset(nums, 0, sizeof(nums));
    memset(f1, 0, sizeof(f1)); memset(f2, 0, sizeof(f2)); memset(f3, 0, sizeof(f3));
    while(n)
    {
        nums[++cnt] = n % 10;
        n /= 10;
    }
    std:: reverse(nums + 1, nums + cnt + 1);
    f1[0][0][0][0][1] = 1; 
    for(int i=0;i<cnt;i++)
    {
        for(int j=0;j<7;j++)
        {
            for(int k=0;k<7;k++)
            {
                for(int l=0;l<=1;l++)
                {
                    for(int r=0;r<=1;r++)
                    {
                        if(f1[i][j][k][l][r] || f2[i][j][k][l][r] || f3[i][j][k][l][r])
                        {
                            int up = (r == 0) ? 9 : nums[i + 1];
                            for(int p=0;p<=up;p++)
                            {
                                f1[i + 1][(10 * j + p) % 7][(k + p) % 7][l || (p == 7)][r && (p == up)]
                                = (f1[i + 1][(10 * j + p) % 7][(k + p) % 7][l || (p == 7)][r && (p == up)] + f1[i][j][k][l][r]) % mod;
                                f2[i + 1][(10 * j + p) % 7][(k + p) % 7][l || (p == 7)][r && (p == up)]
                                = (f2[i + 1][(10 * j + p) % 7][(k + p) % 7][l || (p == 7)][r && (p == up)] + 10 * f2[i][j][k][l][r] + p * f1[i][j][k][l][r]) % mod;
                                f3[i + 1][(10 * j + p) % 7][(k + p) % 7][l || (p == 7)][r && (p == up)]
                                = (f3[i + 1][(10 * j + p) % 7][(k + p) % 7][l || (p == 7)][r && (p == up)] + 100 * f3[i][j][k][l][r] + 20 * p * f2[i][j][k][l][r] + p * p * f1[i][j][k][l][r]) % mod;
                            }
                        }
                    }
                }
            }
        }
    }
    LL res = 0;
    for(int j=1;j<7;j++)
        for(int k=1;k<7;k++)
            for(int r=0;r<=1;r++)
            {
                res = (res + f3[cnt][j][k][0][r]) % mod;
            }
    return res;
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", (Solve(R) - Solve(L - 1) + mod) % mod);
    }
    return 0;
}


新鲜事 原文

ytczy666
6个月前
咕咕咕