soj上都有;
T1:
给定一个正整数S,现在要求你选出若干个互不相同的正整数,使得它们 的和不大于S,而且每个数的因数(不包括本身)之和最大。
赛中思路:从小数据开始枚举,找到规律(但明显是错的 );
正确思路:此题其实是一个01背包(可我连背包都忘了 ),先求出每个数的因数和,选出来的每个整数相当于重量w[i];每个整数的因数和相当于价值c[i]背包最大容量为s,f[i][x]表示考虑了前i个数,当前得到的和为x时(背包已装容量),得到的因数和(价值)最大值;
代码如下
#include<bits/stdc++.h>
using namespace std;
int read()
{
int x=0,f=1;
char ch;
while(ch>'9'||ch<'0')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int ysh[1005],m,f[1005][1005];
int main()
{
m=read();
ysh[1]=0;
for(int i=2;i<=m;i++){
int ans=1;
for(int j=2;j<=i/2;j++){
if(i%j==0) ans+=j;
}
ysh[i]=ans;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
if(j>=i) f[i][j]=max(f[i-1][j-i]+ysh[i],f[i-1][j]);
else f[i][j]=f[i-1][j];
}
}
printf("%d",f[m][m]);
return 0;
}
T2:
给一个长度为n 的数组A,给定L;R,求所有满足长度大等于L,小等于R 的A 数组的子区间的平均值的最大值。
赛中思路:无脑暴力(是真的不会 )
正确思路:二分+ 单调队列。
二分平均值,然后再每个数减去这个平均值,此时所有和大等于0 的区间的平均值大于二分值。统计减去平均值后序列的前缀和,问题变为询问在前缀和si 之前[i−R; i−L] 区间是否存在一个数sj,使得si sj ,用单调队列优化可以做到O(n)。
反思:此题其实为一个动态区间,加上优先队列后可以优化;
代码如下:
#include<bits/stdc++.h>
using namespace std;
int read()
{
int x=0,f=1;
char ch;
while(ch>'9'||ch<'0')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
double b[200005],maxx;//
double mid,L=0x3f3f3f3f,R,a[200005];//
int l,r,n,q[200005];
bool check(double mid)
{
int h=1,t=0;
maxx=0;
q[0]=0;
for(int i=1;i<=n;i++) b[i]=a[i]-mid*i;//
for(int i=l;i<=r;i++) maxx=max(maxx,b[i]);
for(int i=l+1;i<=n;i++)
{
while(t>0&&b[q[t]]>b[i-l]) t--;//i-l右端点,i-r左端点,队尾元素必须小于新加入元素,维护单调性;
q[++t]=i-l;//把右端点存入队列;
while(q[h]<i-r) h++;//保证队列在左端点右边;
maxx=max(maxx,b[i]-b[q[h]]);
}
if(maxx) return true;
return false;
}
int main()
{
n=read();
l=read();
r=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
L=min(L,a[i]);
R=max(R,a[i]);
a[i]+=a[i-1];
}
while(R-L>1e-6)
{
mid=(L+R)/2;
if(check(mid)) L=mid;
else R=mid;
}
printf("%.4lf",L);
return 0;
}
T3
赛中思路:没有思路
正确思路:判断是否能加入一条边时,如果这条边的两端已经联通,我们需要知道这个联通块是否有环。如果不连通,那么可以加入这条边,而且通过两端的联通块是否有环可以得到新的联通块是否有环。于是我们用并查集维护连通性,额外维护联通块里是否有环即可。
时间复杂度O((n + m) log n)。
“树”+“树”=“树”,“树”+“环套树”=“环套树”,“树”加边就是“环套树”,环之间不能合并,若有节点不在环套树森林中,则无解。
代码如下:
#include<bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
int n,m,fa[N],group[N];
long long tot,ans;
int read()
{
int x=0,f=1;
char ch;
while(ch>'9'||ch<'0')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int getfa(int x)
{
if(fa[x]!=x)
{
fa[x]=getfa(fa[x]);
}
return fa[x];
}
struct node{
int x,y,w;
bool operator <(const node &q)const {
return q.w>w;
}
}a[N];
signed main()
{
n=read();
m=read();
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
a[i].x=read();
a[i].y=read();
a[i].w=read();
}
int r,t;
sort(a+1,a+1+m);
for(int i=1;i<=m;i++)
{
r=getfa(a[i].x);
t=getfa(a[i].y);
if(r==t&&!group[r]){//在同一联通块,且r不是环;
group[r]=1;
tot++;
ans+=a[i].w;
}
else
{
if(group[r]&group[t]) continue;//都是环,不合并
fa[r]=t;
group[t]=group[r]|group[t];//合并联通块
tot++;
ans+=a[i].w;
}
}
if(tot!=n) printf("No");
else printf("%lld",ans);
return 0;
}
这次被神仙们吊打,垫底了,下次要加油啊。
转载:https://blog.csdn.net/qq_39282287/article/details/102470347