题目列表
神秘能量
原理在于，对于自然数 $i$，在 $n$ 以内，一定有 $\left\lfloor\frac{n}{i}\right\rfloor$ 个数字是 $i$ 的倍数。
很好解释，$i$ 的倍数 $i$ 个一循环。
然后容斥，$[l,r]$ 的答案是 $[1,r]-[1,l-1]$。
做完可以做一下洛谷 P1403。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
long long ans=0;
int l,r;
cin>>l>>r;
l--;
for(int i=1;i<=r;i++)
{
ans+=(r/i-l/i);
}
cout<<ans<<endl;
return 0;
}城市联盟
我们考虑贪心，只要不满足条件的，直接踢出去，同时把其他和它有联系的城市也删减一个边。
代码
#include<bits/stdc++.h>
using namespace std;
bool f[520];
set<int>a[520];
int n,m,x,y,sum;
bool ok()
{
for(int i=1;i<=n;i++)
{
if(f[i])continue;
if(a[i].size()>=x&&sum-y>a[i].size()){}
else return 0;
}
return 1;
}
int main()
{
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
cin>>n>>m>>x>>y;
sum=n;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
a[u].insert(v);
a[v].insert(u);
}
while(!ok())
{
for(int i=1;i<=n;i++)
{
if(f[i])continue;
if(a[i].size()>=x&&sum-y>a[i].size()){}
else
{
f[i]=1;
sum--;
for(int j:a[i])
{
a[j].erase(i);
}
}
}
}
cout<<sum<<endl;
return 0;
}花园计划
01背包改版，可以选择 取第一种\取第二种\不取
代码
#include<bits/stdc++.h>
using namespace std;
int a[220];
int b[220];
int c[220];
int d[220];
int f1[2000020];
int f2[2000020];
int main()
{
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
int n,m,s;
cin>>m>>n>>s;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i]>>c[i]>>d[i];
}
for(int i=1;i<=n;i++)
{
bool flag=0;
for(int j=m;j>=b[i];j--)
{
f1[j]=max(f1[j],f1[j-b[i]]+a[i]);
}
for(int j=m;j>=d[i];j--)
{
f2[j]=max(f2[j],f2[j-d[i]]+c[i]);
}
for(int j=0;j<=m;j++)f1[j]=f2[j]=max(f1[j],f2[j]);
}
cout<<f1[m]+s<<endl;
return 0;
}爬塔游戏
一个 Floyd。
先找出直接到的，然后再看一下有没有跳跃能更快的，最后做一遍最短路找最短时间。
建图注意，大楼两边互建，跳的时候只能往一边建。
注意很多开根号啥的，很烦。
代码
#include<bits/stdc++.h>
#define xy x[i],y[i],x[j],y[j]
using namespace std;
double f[120][120];
int x[120];
int y[120];
int u[120];
int n,v;
double tower_dis(int x_1,int y_1,int x_2,int y_2)
{
return sqrt(1.0*(x_1-x_2)*(x_1-x_2)+1.0*(y_1-y_2)*(y_1-y_2));
}
double tower_time(int x_1,int y_1,int x_2,int y_2)
{
return tower_dis(x_1,y_1,x_2,y_2)/v;
}
bool can_jump(int x_1,int y_1,int x_2,int y_2)
{
return (x_1==x_2)&&(y_1>y_2);
}
double jump_time(int y_1,int y_2)
{
return sqrt((y_1-y_2)*2.0/10.0);
}
int main()
{
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
for(int i=1;i<=120;i++)
{
for(int j=1;j<=120;j++)
{
f[i-1][j-1]=1e9;
}
}
cin>>n>>v;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i]>>u[i];
}
for(int i=1;i<=n;i++)
{
if(u[i]!=0)
{
int j=u[i];
f[i][j]=min(f[i][j],tower_time(xy));
f[j][i]=min(f[j][i],tower_time(xy));
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(can_jump(xy))
{
f[i][j]=min(f[i][j],jump_time(y[i],y[j]));
}
}
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=min=(f[i][j],f[i][k]+f[k][j]);
}
}
}
cout<<fixed<<setprecision(2)<<f[1][n]<<endl;
return 0;
}