526互联

1.9

发布时间 2024-01-09 20:12:56作者: HS_xh

几个月前写的傻逼物理被 jjdw 指出了错误，哎，怎么当时我没看出来结论写错了啊？最离谱的是我开头结尾结论错了，但是中间推导没错，乐了

为啥洛天依就能天天来，好羡慕完全抛弃 whk 的爷，whker 学奥赛就像被肢解 \(.\)

地精部落

题意是求 \(1-n\) 的波动序列的方案数

考虑 DP

\(dp_{i,j}\) 表示以 \(i\) 个数的排列，且开头 \(<=j\) 且开头下降的波动序列方案数

当开头的数 \(<j\) 时，显然方案数为 \(dp_{i,j-1}\)

当开头的数为 \(j\) 时，尝试把 \(j\) 去掉，则剩下的方案和 \(i-1\) 个数的排列、第一个数 \(<=j-1\)（因为原序列开头是 \(j\)，并且开头下降要求原序列的第二个数比\(j\) 小）且开头上升的抖动序列的方案一一对应

开头上升的序列方案怎么算？

有一个结论，一个 \([1,i]\) 的序列一定可以对应 \([n-i+1,n]\) 的序列

证明不会

所以当开头的数为 \(j\) 时，\(dp_{i-1,i-j+1}\)

所以总的动态转移方程是

\[dp_{i,j}=dp_{i,j-1}+dp_{i-1,i-j+1} \]

然后就可以写了

Code 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5*1e3;
int dp[N][N];
inline int read()
{
    int s = 0,w = 1;char ch = getchar();
    while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
    while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}
    return s*w;
}
signed main()
{
    int n=read();
    int p=read();
    dp[1][1]=1;
    for(int i=2;i<=n;++i)
        for(int j=1;j<=i;++j)
            dp[i][j]=(dp[i][j-1]+dp[i-1][i-j+1])%p;
    int ans=0;
    for(int i=1;i<=n;++i)
        ans+=dp[n][i]%p;
    cout<<(ans<<1)%p;
}

我用了二维数组每维存 \(n\) 的大小，这是数据不强，如果数据强一点肯定会爆二维数组，所以有一个比较高级的写法

Code 
int dp[2][4300]={0};
dp[1][1]=1;
for(i=2;i<=n;i++)
    for(j=1;j<=i;j++)
        dp[i&1][j]=(dp[i&1][j-1]+dp[(i&1)^1][i-j])%p;
    printf("%lld",(f[n&1][n]<<1)%p);

显然二进制优化，这样可以省去许多空间从而支持比较大的数据

再放道小学化学题

\(\text{FeSO}_4\) 和 \(\text{Fe}_2(\text{SO}_4)_3\) 的混合物中， \(\text{S}\) 元素的质量分数为 \(\text {23\%}\)，求 \(\text{Fe}\) 的质量分数

解

可以发现两种物质都只含有硫酸根，所以可以通过硫元素的质量分数求出硫酸根的质量分数，从而求出铁元素的质量分数

\[\text {Ar}\ \ \ \ \ \frac{\text {S}}{\text{SO}_4}=\frac {32} {96}=\frac 13 \]

\[\therefore \text{SO}_4 的质量分数为\ 69\% \]

\[\therefore \text{Fe} 的质量分数为\ 31\% \]

这么简单就不用看解题过程了吧，答案是 \(31\%\)

发现一整个闲话没打过一个句号，看着有点难受啊

积极文件夹里机房里看见我是及缴费单哦机房地32额2饿12饿2饿2dqwdwdijiiuwahdhqwad而丢2爷6e87dciueshivdsjg 防控IE我就佛IE五金芙蓉it分2
：“”“”“”：“”：：LP{"LP{"L:
X":X:"A:X"A"X:?A":>X"ALP{)_E!@I()u(@!E&YEU@
；按道理poqwkpir90duxi90saWIXWA
PW[,3RWLPWLFPQW'LFP32RP[32LFPLKVPSAKFPO3WLKFPOlp@(\(U*!@(&\)!@&\(*!@\)@(#\(()#!@*%\))#%(%#!@%()!#@%#!@(%&!*#@%&^：？{}？“”}？}{}{}“”}？{}：？{}？{}]]JHHAUCHUYAHGUYHGCUY我，电器外壳及浮动额温计佛IE玩具我偶尔玩手机封口费我服务114514哎我怎么死了，最近好烦，但是我宣泄了！！！！1

腿疼，明天就要体侧了，腿疼，怎么办啊，我 1000 米满不了分了，1000米要爆 0 了，期末挂分了QTQ

我到现在仍然没打过一个句号。