暑假集训2
2022/8/12 23:58:01
本文主要是介绍暑假集训2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
题面
A.LCIS
一道裸的求LCIS(最长公共上升子序列)题.
\(dp\)数组储存到\(b\)的第\(i\)项，\(a\)从\(1-n\)的且以\(b[i]\)结尾的最⻓公共上升⼦序列⻓度.
那么\(dp\)过程显然：
if(a[i]>b[j]&&maxx<f[j]) maxx=f[j];更新可以⽤于更新\(b\)序列与\(a\)序列前\(i\)位的最⻓⻓度的最⼤值.if(a[i]==b[j]) f[j]=maxx+1;因为\(j\)是内循环，所以如果\(maxx\)被更新了，则现在的\(b[j]\)是等于\(a[i]\)，⼀定⽐更新\(maxx\)的\(bj\)⼤.
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define rg register
#define rll rg ll
#define maxn 3001
using namespace std;
static inline ll read()
{
rll f=0,x=0;rg char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
static inline void write(rll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);putchar(x%10|48);
}
ll n,maxx;
ll a[maxn],b[maxn],dp[maxn];
ll ans;
int main()
{
n=read();
for(rll i=1;i<=n;i++) a[i]=read();
for(rll i=1;i<=n;i++) b[i]=read();
for(rll i=1;i<=n;i++)
{
maxx=0;
for(rll j=1;j<=n;j++)
{
if(a[i]==b[j]) dp[j]=maxx+1;
if(a[i]>b[j]&&maxx<dp[j]) maxx=dp[j];
}
}
for(rll i=1;i<=n;i++) ans=max(ans,dp[i]);
write(ans);
return 0;
}
B.平凡的函数
递推题.
在每一次线性筛求素数时筛一遍 \(f(i\times prime[j])\) ，按照题意的三种情况更新即可.
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define rg register
#define rll rg ll
#define maxn 50000001
using namespace std;
static inline ll read()
{
rll f=0,x=0;rg char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
static inline void write(rll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);putchar(x%10|48);
}
ll n;
ll dp[maxn];
ll prime[maxn],cnt;
bool fl[maxn];
static inline void xxs()
{
for(rll i=2;i<maxn;i++)
{
if(!fl[i])
{
prime[++cnt]=i;
dp[i]=i^1;
}
for(rll j=1;j<=cnt&&i*prime[j]<maxn;j++)
{
fl[i*prime[j]]=1;
rll t=i*prime[j],k=0;
while(!(t%prime[j])) t/=prime[j],k++;
if(t==1) dp[i*prime[j]]=prime[j]^k;
else dp[i*prime[j]]=dp[t]*(prime[j]^k);
if(!(i%prime[j])) break;
}
}
}
int main()
{
dp[1]=1; xxs();
n=read();
for(rll i=1;i<=n;i++) dp[i]+=dp[i-1];
write(dp[n]);
return 0;
}
C. 那一天她离我而去
暴力应该很好想，就是把所有和起点相连的边依次删除，每次跑一遍最短路.这样可以得到 \(77pts\) 的好成绩.
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define rg register
#define maxn 100001
#define rll rg ll
#define pll pair<ll,ll>
#define inf 4557430888798830399
using namespace std;
inline ll read()
{
rll f=0,x=0;rg char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
inline void write(rll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);putchar(x%10|48);
}
ll t,n,m,ans;
vector<pair<ll,ll> > g[maxn];
ll dis[maxn];
queue<ll> q;
bool fl[maxn];
static inline void spfa(rll x,rll ban)
{
memset(dis,0x3f,sizeof(dis));
dis[x]=0;q.push(x);fl[x]=1;
while(!q.empty())
{
rll t=q.front();q.pop();fl[t]=0;
for(rll i=0;i<g[t].size();i++)
{
rll to=g[t][i].first;
if(t==1&&to!=ban) continue;
else if(t==ban&&to==n+1) continue;
if(dis[to]>dis[t]+g[t][i].second)
{
dis[to]=dis[t]+g[t][i].second;
if(!fl[to]) { q.push(to),fl[to]=1; }
}
}
}
ans=min(ans,dis[n+1]);
}
int main()
{
t=read();
while(t--)
{
ans=inf;n=read();m=read();
for(rll i=1;i<=n;i++) g[i].clear();
for(rll i=1,u,v,w;i<=m;i++) u=read(),v=read(),w=read(),g[u].push_back((pll) { (v==1)?n+1:v,w }),g[v].push_back((pll) { (u==1)?n+1:u,w });
if(g[1].size()<=1) { puts("-1");continue; }
for(rll i=0;i<g[1].size();i++) spfa(1,g[1][i].first);
write(ans==inf?-1:ans);puts("");
}
return 0;
}
既然已经想到这了，那么一定可以优化.
考虑分组进行最短路，由于两个不同的数字它们的二进制数一定不同，所以可以将每一个二进制位0和1分组，那么这样每一组点组成的环一定会被更新.
具体流程：
- 建边时端点为1的特殊处理
- 枚举二进制的每一位
- 枚举与点1相连的每一个点
- 若其二进制下该位为1，将点n+1向该点连边
- 否则，将该点向点n+2连边
- 每一次连完所有边后跑一遍从点n+1到点n+2最短路，然后将边删除
- 统计每次最短路的最小值
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define rg register
#define maxn 80001
#define rll rg ll
#define pll pair<ll,ll>
#define inf 4557430888798830399
using namespace std;
inline ll read()
{
rll f=0,x=0;rg char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
inline void write(rll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);putchar(x%10|48);
}
ll t,len,n,m,ans;
vector<pair<ll,ll> > g[maxn];
ll dis[maxn];
queue<ll> q;
bool fl[maxn];
static inline void spfa(rll x)
{
memset(dis,0x3f,sizeof(dis));
dis[x]=0;q.push(x);fl[x]=1;
while(!q.empty())
{
rll t=q.front();q.pop();fl[t]=0;
for(rll i=0;i<g[t].size();i++)
{
rll to=g[t][i].first;
if(dis[to]>dis[t]+g[t][i].second)
{
dis[to]=dis[t]+g[t][i].second;
if(!fl[to]) { q.push(to),fl[to]=1; }
}
}
}
}
int main()
{
t=read();
while(t--)
{
for(rll i=1;i<=len;i++) g[i].clear();
ans=inf;len=n=read();m=read();
for(rll i=1,u,v,w;i<=m;i++)
{
u=read(),v=read(),w=read();
if(v!=1) g[u].push_back((pll) { v,w });
if(u!=1) g[v].push_back((pll) { u,w });
}
for(rll i=1;i<=n;i<<=1)
{
rll x=++len,y=++len;
for(rll j=0;j<g[1].size();j++)
{
if(g[1][j].first&i) g[x].push_back((pll) { g[1][j].first,g[1][j].second });
else g[g[1][j].first].push_back((pll) { y,g[1][j].second });
}
spfa(x);ans=min(ans,dis[y]);
}
write(ans==inf?-1:ans);puts("");
}
return 0;
}
D.熟练剖分
这题和树链剖分没什么关系，是一道使用树形 \(dp\) 求概率的题.
懒得打式子了，放上std的题解(非本人原创).
以下把题面所求的精彩操作称为最长轻链.
而这个东西显然是可以由子节点转移到父亲节点的.
\(dp[i][j]\)表示在点 i 为根的子树中，向下最长轻链长度为 j 的概率.
对于一个点，先枚举它选择的重儿子是谁，然后扫一遍它的所有儿子,让 \(G[i][j]=Σ_{(k\leq j)}dp[i][k]\)，假如当前扫的儿子是 x（x 是重儿子）.
\[dp[i][j]=dp[x][j]*G[i][j]+G[x][j]*dp[i][j]-dp[x][j]*dp[i][j] -----（1） \]不是重儿子的需要相应的改一下，还有要注意 dp 数组更新的顺序，标程是先把 dp 暂存到了一个别的数组里.
转移的时候如果(1)式子的 \(j\) 循环到了 \(size[i]\)，那么复杂度可以被卡到 \(N^3\)，我们发现当 \(j>size[x]+1\) 的时候 \(dp[x][j]=0\),\(G[x][j]=1\),\(dp[i]\)相当于没有变，所以只要 \(j\) 循环到 \(size[x]+1\) 就行了.
由于每一次循环G数组都需要更新，因此可以压掉一维.
每个节点只有在 dp 它父亲时会被枚举成为重儿子，然后最多把整棵树的大小扫一遍，所以复杂度为 \(O(N^2)\).
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define rg register
#define maxn 3001
#define mod 1000000007
#define rll rg ll
using namespace std;
inline ll read() { rll f=0,x=0; rg char ch=getchar(); while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return f?-x:x; } inline void write(rll x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10|48); }
ll n,k[maxn],ans;
vector<ll> g[maxn];
ll rt,rd[maxn],dep[maxn];
ll dp[maxn][maxn];//dp[i][j]为以点i为根的子树中，向下最长轻链长度为j的概率
ll p[maxn];//p[i]:当前重儿子深度为i的概率，即为以上的G
ll h[maxn];//h[i]:当前的最大深度为i的概率
bool fl;
static inline ll ksm(rll a,rll b) { rll ans=1; a%=mod; for(rll i=b;i;i>>=1) { if(i&1) ans=ans*a%mod;a=a*a%mod; } return ans; }
static inline void dfs(rll x)
{
dep[x]=1;
if(g[x].empty()) dp[x][0]=1;
for(rll i=0;i<g[x].size();i++)
{
rll to=g[x][i];dfs(to);
dep[x]+=dep[to];
}
for(rll i=0;i<g[x].size();i++)
{
for(rll j=0;j<=n;j++) p[j]=1;
rll t=g[x][i];
for(rll j=0;j<g[x].size();j++)
{
rll to=g[x][j];
for(rll k=0;k<=dep[to];k++)
{
rll tp=p[k],tf;
if(k) tp-=p[k-1];
if(t==to)
{
tf=dp[to][k];
if(k) tf-=dp[to][k-1];
h[k]=(tp*dp[to][k]%mod+tf*p[k]%mod-tp*tf%mod+mod)%mod;
}
else
{
tf=dp[to][k-1];
if(k>1) tf-=dp[to][k-2];
h[k]=(tp*dp[to][k-1]%mod+tf*p[k]%mod-tp*tf%mod+mod)%mod;
}
}
p[0]=h[0];
for(rll k=1;k<=dep[to];k++) p[k]=(p[k-1]+h[k])%mod;
}
for(rll j=dep[x];j;j--) p[j]=(p[j]-p[j-1]+mod)%mod;
for(rll j=0;j<=dep[x];j++) dp[x][j]=(dp[x][j]+p[j]*ksm(k[x],mod-2)%mod)%mod;
}
for(rll i=0;i<=dep[x];i++) dp[x][i]=(dp[x][i]+dp[x][i-1])%mod;
}
int main()
{
n=read(); for(rll i=1;i<=n;i++) { k[i]=read();for(rll j=1,t;j<=k[i];j++) t=read(),g[i].push_back(t),rd[t]++; }
for(rll i=1;i<=n;i++) if(!rd[i]) { rt=i;break; }
dfs(rt);
for(rll i=n;i;i--) ans=(ans+i*(dp[rt][i]-dp[rt][i-1]+mod)%mod)%mod;
write(ans%mod);
return 0;
}
就写这些吧.
这篇关于暑假集训2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-06-05做软件测试需要懂代码吗？
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡？
- 2024-05-31全网首发第二弹！软考2024年5月《软件设计师》真题+解析+答案！（11-20题）
- 2024-05-31全网首发！软考2024年5月《软件设计师》真题+解析+答案！（21-30题）
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司，哪像华为一样，用得上IPD（集成产品开发）？
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm，再安排pandas等模块，说是没有打包工具?
- 2024-05-29java11新特性
