20221015
硬币
01背包
可以发现，每种硬币面值与其可以组成的价值呈一种类树形关系。例如\(1,2,3,4\)。\(1\)可以构造出\(3,4,5\)，\(2\)可以构造出\(3,5,6\)它们都可以对构造出\(5\)产生一种不同的构造方法，即对构造出\(5\)的方案数做出贡献。那我们就可以用\(dp\)来存下最初能构造出的数字的方案数，统计答案时减去被删去的数字的贡献，统计完后复原。\(dp[i][j]\)为到第\(i\)枚硬币能构造出\(j\)的方案数。\(dp[i][j+a[i]]+=dp[i-1][j](dp[i-1][j]>0)\)。
可以发现，这其实就是个以能构造出的数值\(j\)作为容量，方案数作为价值的01背包。
貌似会爆longlong，所以用dp[i]>0判断会WA几个点，这个可以用__int 128处理
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=105;
int n,a[N];
ll dp[300005];
int main(){
in(n);
fo(i,1,n)in(a[i]);
dp[0]=1;
fo(i,1,n)
for(int j=300000;j>=0;--j)
if(dp[j]&&j+a[i]<=300000)dp[j+a[i]]+=dp[j];
fo(i,1,n){
int ans=0;
fo(j,0,300000)
if(dp[j]&&j+a[i]<300000)dp[j+a[i]]-=dp[j];
fo(j,1,300000)if(dp[j])++ans;
out(ans),putchar('\n');
for(int j=300000;j>=0;--j)
if(dp[j]&&j+a[i]<=300000)dp[j+a[i]]+=dp[j];
}
return 0;
}
序列
暴力
枚举一个起点，从前往后一个一个判断是否可行。看似这样是\(O(n^{2})\)的，但实际上在随机数据下很难跑到这个复杂度。当然，会被最后一个数据hack掉，但是再加点剪枝实际上也能过。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(ll i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=1000005;
int n;
int a[N],b[N];
ll now,ans;
int main(){
in(n);
fo(i,1,n)in(a[i]),in(b[i]);
fo(i,1,n){
now=a[i];
if(n-i+1<=ans)continue;
fo(j,i+1,n){
if(now>b[j]){
ans=max(ans,j-i);
break;
}
else if(now<a[j])now=a[j];
else if(j>=n)ans=max(ans,j-i+1);
}
}
out(ans);
return 0;
}
暴力2
同样的，每次判断是否可行。若不行，就向这个点之前的点找可行的点。
单调队列
我们每次肯定都贪心的选择满足条件的情况下能取到的最低温度，这样才能使答案尽可能大。然后在这个基础上进行判断。可以则继续，不可以则使队头出队到可行为止。
小y的炮
贪心
这道题应该很容易想到贪心，这里就浅谈一下满分的贪心。对所有的炮按攻击高度从小到大排序，再将其中不中用或者说打得又没别人高，力度还没别人强的炮删去。这样就能保证我们排序后的炮一定是在自身能打到的高度到比它射程低的炮能打到的高度之间伤害最高的。然后我们再将所有炮将高度为\(h\)的山夷平的最少炮弹数\(F[h]\)，最后统计答案即可。更细节的内容会在注释中说明。
点击查看代码
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#define ll long long
#define int long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define zo(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=250005;
int h[N];
int n,m,k;
struct kpow{
ll a,d;
}p[N],q[N];
int cnt;
inline bool cmp(kpow x,kpow y){return x.a==y.a?x.d<y.d:x.a<y.a;}
ll t;
int ans;
unordered_map <ll,ll> F;
signed main(){
in(n),in(m),in(k);
zo(i,n,1)in(h[i]);
fo(i,1,m)in(p[i].a),in(p[i].d);
sort(p+1,p+m+1,cmp);
fo(i,1,m){
while(cnt>0&&p[i].d>=q[cnt].d)--cnt;
q[++cnt]=p[i];
}
//保证每个炮一定是在自身能打到的高度到比它射程低的炮能打到的高度之间伤害最高的
F[0]=0;
int st,ed;
fo(i,1,cnt){
st=max(q[i-1].a,q[i].a-q[i].d)+1,ed=q[i].a;
fo(h,st,ed){
t=(h-q[i-1].a-1)/q[i].d+1;
F[h]=F[max(h-t*q[i].d,0ll)]+t;//处理F数组
//注意，这样处理出来可能会有高于q[i-1].a+1,但小于st的高度没有被处理出来
}
}
int pos=1;
fo(i,1,n){
while(pos<=cnt&&q[pos].a<h[i])++pos;
if(pos>cnt)break;
t=(h[i]-q[pos-1].a-1)/q[pos].d+1;
//保证h[i]-t*q[pos-1].a一定在已经处理了F数组的高度
//因为h[i]-t*q[pos-1].a一定大于st
t+=F[max(0ll,h[i]-t*q[pos].d)];
if(t<=k)k-=t,++ans;
else break;
}
out(ans),putchar(' '),out(k);
return 0;
}
统计损失
树形dp
一眼树形\(dp\)，但是在进行状态转移时，需要转个弯，不能直接硬来。在只有两个点时很容易想到怎么处理，用两点权值加上两点权值乘积即可。但是，三个点时怎么办呢？
像这样，蓝色的路径很容易求出，但红色的路径仿佛就很难求出了。接下来让我们仔细分析如何求出这张图的答案。蓝色的边就是边上两点的乘积，红色的边就是三点的乘积，也是一条蓝边与第三点的乘积，而答案就是他们的和。假设这三个点的权值就是它们的编号，两条蓝边的答案分别是\(1\times 2\)和\(1\times 3\)而红边的答案是\(1\times 2\times 3\)貌似并不能看出点什么。但是，你仔细想想，又求积又求和难道不能想到点什么吗？比如乘法分配律。
如果这还不能想到，那我们把情况放到更多边的时候。
\((x,y)\)代表从\(x\)到\(y\)的一条最短路径。\((1,2)\)贡献的答案是\(1\times 2\)，\((1,3)\)是\(1\times 3\)，\((1,4)\)是\(1\times 4\)，\((2,3)\)是\(1\times 2\times 3\),\((2,4)\)是\(1\times 2\times 4\)...然后再联系乘法分配律。诶，你就会惊讶地发现\((2,4)\)和\((3,4)\)的答案，其实就是\((1,2)\)\((1,3)\)答案的和乘上\(4\)。也就是说\(1\times 2\times 4+1\times 3\times 4=(1\times 2+1\times 3)\times 4\)显而易见的乘法分配律，与子树的情况同样如此。这样我们的状态转移方程也就可以确定了。在每次计算一个点与其一个子树时进行，\(dp[x]=dp[x]+dp[v]\times w[x](x为父节点,v为子节点)\)
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=100005,mod=10086;
int n;
ll w[N];
struct edge{
int v,nex;
}e[N<<1];
int head[N],tot;
inline void add(int u,int v){
e[++tot].v=v,e[tot].nex=head[u],head[u]=tot;
}
ll ans;
int uu,vv;
ll dp[N];
inline void dfs(int x,int fa){
dp[x]=w[x],ans+=w[x];
for(int i=head[x];i;i=e[i].nex){
int v=e[i].v;
if(v==fa)continue;
dfs(v,x);
ans=(ans+dp[x]*dp[v])%mod;
dp[x]=(dp[x]+w[x]*dp[v])%mod;
}
}
int main(){
in(n);
fo(i,1,n)in(w[i]);
fo(i,1,n-1){
in(uu),in(vv);
add(uu,vv);
add(vv,uu);
}
dfs(1,1);
out(ans);
return 0;
}