目录
730. 机器人跳跃问题【二分】
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],n;
bool check(long long int mid)
{
for(int i=1;i<=n;i++)
{
mid=mid*2-h[i];
if(mid<0) return false;
if(mid>1e9) return true;
}
return true;
}
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
int l=0,r=1e6;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
3195. 有趣的数【DP 组合树】
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int mod=1e9+7;
typedef long long int LL;
LL c[N][N],n;
int main(void)
{
cin>>n;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0) c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
LL res=0;
for(int k=2;k<=n-2;k++)
res=(res+c[n-1][k]*(k-1)%mod*(n-k-1))%mod;
cout<<res;
return 0;
}
3205. 最优配餐【多源最短路】
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int g[N][N],n,m,k,d;
int dist[N][N];
struct node{int x,y,c;};
vector<node>ve;
queue<node>q;
void bfs()
{
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
while(q.size())
{
auto temp=q.front(); q.pop();
int x=temp.x,y=temp.y;
for(int i=0;i<4;i++)
{
int tempx=x+dx[i];
int tempy=y+dy[i];
if(tempx<=0||tempx>n||tempy<=0||tempy>n) continue;
if(g[tempx][tempy]) continue;
if(dist[tempx][tempy]>dist[x][y]+1)
{
dist[tempx][tempy]=dist[x][y]+1;
q.push({tempx,tempy,0});
}
}
}
}
int main(void)
{
memset(dist,0x3f,sizeof dist);
cin>>n>>m>>k>>d;
while(m--)
{
int x,y; scanf("%d%d",&x,&y);
q.push({x,y,0});
dist[x][y]=0;
}
while(k--)
{
int x,y,c; scanf("%d%d%d",&x,&y,&c);
ve.push_back({x,y,c});
}
while(d--)
{
int x,y; scanf("%d%d",&x,&y);
g[x][y]=1;
}
bfs();
long long int sum=0;
for(int i=0;i<ve.size();i++) sum+=1ll*dist[ve[i].x][ve[i].y]*ve[i].c;
cout<<sum<<endl;
return 0;
}
3215. 网络延时【树的直径】
#include<bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
int h[N],e[N],ne[N],idx;
int n,m,ans=0;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
int d1=0,d2=0;//最长路 次长路
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
int d=dfs(j);
if(d>=d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
ans=max(ans,d1+d2);
return d1+1;
}
int main(void)
{
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=2;i<=n+m;i++)
{
int x; cin>>x;
add(x,i);
}
dfs(1);
cout<<ans;
return 0;
}
3250. 通信网络【思维 图】
如果一个点A可以到达的点有s1个，有s2个点可以到达A。且s1+s2==n则这就是一个所求的点。
故可以建立反向边。这样就可以逆着求那些点可以到达它
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h1[N],h2[N],ne[N],e[N],idx;
int n,m,st1[N],st2[N];
void add(int h[],int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int h[],int st[])
{
st[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j]) dfs(j,h,st);
}
}
int main(void)
{
memset(h1,-1,sizeof h1);
memset(h2,-1,sizeof h2);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b; cin>>a>>b;
add(h1,a,b),add(h2,b,a);
}
int ans=0;
for(int i=1;i<=n;i++)
{
memset(st1,0,sizeof st1);
memset(st2,0,sizeof st2);
dfs(i,h1,st1);
dfs(i,h2,st2);
int cnt=0;
for(int j=1;j<=n;j++) if(st1[j]||st2[j]) cnt++;
if(cnt==n) ans++;
}
cout<<ans;
return 0;
}
3240. 压缩编码【区间DP】
猛的一看以为是哈夫曼树，直接合并任意俩点。但是题目要求字典序递增。
这其实就是暗示每次合并只可以合并相邻的点。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N],n,s[N];
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i],s[i]+=s[i-1];
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int l=i,r=i+len-1;
f[l][r]=1e9;
for(int k=l;k<r;k++)
{
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
}
}
cout<<f[1][n];
return 0;
}