前言
- 比赛链接。
上午要输液所以没有打，就下午改一改，应该明天就能回去了。
T1 与和
\(x\&y=a\)，说明 \(x,y\) 二进制中都包含 \(a\) 且其余位上均不重合，故此若 \((s-2a)\&a=0\) 即符合，特殊的，因为 \(x\&y=a\le \min(x,y)\)，所以 \(x+y=s\ge 2a\)，需要特判。
T2 函数
对于 \(f_1(f_2(x))\ge f_2(f_1(x))\)，有 \(a_1a_2x+a_1b_2+b_1\ge a_2a_1x+a_2b_1+b_2\)，移项有 \(\dfrac{b_1}{a_1-1}\le \dfrac{b_2}{a_2-1}\)，故此将 \(\dfrac{b_i}{a_i-1}\) 作为关键字降序排序即可作为决策顺序。
之后直接 DP 转移即可，设 \(f_{i,j}\) 位前 \(i\) 个数中选择了 \(j\) 个时的最大值，有：
\[f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1}\times a_i+b_i) \]第一维可以滚掉。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,k;
ll f[11];
struct aa {int a,b;}e[N];
bool cmp(aa a,aa b) {return a.b*(b.a-1)>b.b*(a.a-1);}
signed main()
{
read(n,k);
for(int i=1;i<=n;i++) read(e[i].a,e[i].b);
sort(e+1,e+1+n,cmp);
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=min(i,k);j>=1;j--)
f[j]=max(f[j],f[j-1]*e[i].a+e[i].b);
write(f[k]);
}
T3 袋鼠
和某次的 DP 搬运工是同一种题型，预设型 DP。
原问题可以转化为 \(1\sim n\) 的全排中能够满足对于任意 \(a_i\) 满足 \(a_{i-1}<a_1,a_i>a_{i+1}\) 或 \(a_{i-1}>a_i,a_i<a_{i+1}\) 的有多少。
那么考虑预设型 DP，从小到大插数，设 \(f_{i,j}\) 为前 \(i\) 个数分成了 \(j\) 段，那么有：
-
\(i\ne s\) 且 \(i\ne t\)：
-
\(i\) 新开了一段，因为后面插入的数能接到他两边的一定都比他大，所以一定合法，加入前共有 \(j-1\) 段所以有 \(j\) 个位置可以放但是若 \(i>s\) 就不能放开头了，同理 \(i>t\) 就不能放结尾了，故有：
\[f_{i,j}+=(j-[i>s]-[i>t])\times f_{i-1,j-1} \] -
\(i\) 接在一段的开头或结尾且并不使两段接壤，因为此时与他相邻的数一定小于他，而后面再加入的与其相邻的数一定大于他，故一定不合法。
-
\(i\) 使两段接壤，因为此时与其相邻的两个数一定都小于他，所以一定合法，在进行这一步前有 \(j+1\) 个段产生 \(j\) 个间隙，故此有：
\[f_{i,j}+=j\times f_{i-1,j+1} \]
-
-
\(i=s\) 或 \(i=t\)：
此时他是一定接在开头或结尾的，故最终只有一个数与其相邻，因为之前加入的数都比他小，所以一定合法，同时不存在使两段接壤的情况，只需要考虑新开一段和接在原来段的开头或结尾即可，其所填位置唯一，故有：
\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j} \]
最终一定只有一段，故答案为 \(f_{n,1}\)，第一维可以滚掉，那么类似的之前做的 P2467 [SDOI2010] 地精部落 这题也可以用预设型 DP 直接做了，DP 多开两维表示当前首尾选没选就行了。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e3+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,s,t,f[2][N];
signed main()
{
read(n,s,t);
f[1][1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
{
if(i!=s&&i!=t) f[i&1][j]=(1ll*f[(i-1)&1][j-1]*(j-(i>s)-(i>t))%P+1ll*f[(i-1)&1][j+1]*j%P)%P;
else f[i&1][j]=f[(i-1)&1][j-1]+f[(i-1)&1][j];
}
write(f[n&1][1]);
}
T4 最短路
还没有打。
标签：write,read,void,28,Tp,2024,int,inline,集训 From： https://www.cnblogs.com/Charlieljk/p/18367698