差点一套把我直接送走 60+0+0+40=100…
题目描述 小明和小红在一起玩游戏，小明觉得现在玩的游戏太无聊了，便给小红出了一道数列问题。数列问题的题目如下：
一开始，小明给小红一个只含有数字1的数列，接下来，小红可以对这个数列进行以下操作中的一种操作：
· 对序列中已有的一个元素加1.
· 复制一个序列中已有的元素到序列的末尾. 比如：一开始序列中只有一个元素[1]
我们可以选择这个序列中的第一个元素进行第二种操作，即复制操作，这样，这个序列就变成了[1,1]
然后，我们可以对这个序列中的第一个元素进行第一种操作，即将第一个元素进行+1.这样，这个序列就变成了[2,1]
现在，小明问小红，她最少需要进行多少次操作，可以使得序列中所有元素的和至少为n。
小红面对小明的这个问题一脸懵逼，于是，她来求助聪明的你，希望你能够帮助她解决这个问题。
输入格式 第一行一个数字t,表示测试数据的组数。
接下来行，每行一个数字，表示序列所有元素和至少应该达到的数。
输出格式 对于每一个问题，回答一个数字，表示小红最少需要操作的次数。
样例 样例输入： 5 1 5 42 1337 1000000000 样例输出： 0 3 11 72 63244
手推数据，发现规律为：0,1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7… Solution1:map暴力枚举处理每个循环节开始的数，再在查询时找1~1e9中的 数，第一个大于等于它的数的操纵数即为答案,O(1e9t),再用一个map映射原数的话O(63244t) TLE 60 Solution2:公式，我不会证,但能想到成次方增加最优
#include<cstdio> #include<iostream> #include<cmath> using namespace std; int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); int k=0; for(int i=1;i<=n;i++) { if(i*i>=n) { k=i; break; } } if(k*(k-1)>=n) { printf("%d\n",k*2-3); } else{ printf("%d\n",2*k-2); } } return 0; }手推公式的题还是第一次考啊。。。
传送门 考试时没想到怎么处理两个组之间的数的所属，打了个假贪心，WA 0
Solution:设d[i]表示到i时能获得的最大价值，因为它所属的组最多从max(0,i-k+1)开始，min(n,i+k-1)结束，与其他元素无关，又因为i+k-1会被后面的数的前一部分统计到，所以只考虑前一部分
则dp[i]=max(dp[i],dp[j]+maxn*(i-j)) 其中 (上一组最后一个)i-k<=j<=i-1 maxn表示组内最大值，用RMQ优化
#include<cstdio> #include<iostream> #include<cmath> using namespace std; int maxn,n,k,a[10005],dp[10005],f[100005][20]; void ST_chushi() { for(int i=1;i<=n;i++) { f[i][0]=a[i]; } int t=(int)(log(n)/log(2))+1; for(int j=1;j<t;j++) { for(int i=1;i<=n-(1<<j)+1;i++) { f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } } int ST_search(int l,int r) { int kk=log(r-l+1)/log(2); return max(f[l][kk],f[r-(1<<kk)+1][kk]); }//RMQ部分 int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); dp[i]=a[i];//初始价值为自己 } ST_chushi(); for(int i=1;i<=n;i++){ for(int j=max(0,i-k);j<i;j++) { maxn=ST_search(j+1,i);//O(1)得到最大值 dp[i]=max(dp[i],dp[j]+maxn*(i-j)); } } printf("%d\n",dp[n]); return 0; }因为如果当前元素包含在下一组里面，由于i-k要小于当前元素，所以更新的值是j还没有被算作上一组的时候，所以更新不会出错
传送门 瞟了一眼题面，呵呵，不是和架设电话线重题吗 打完之后看到至少直接懵逼 可恶啊啊啊虽然不读漏还是不会 Solution：分层图最短路 那么分层图是什么呢，我认为大概长这样： 设dp[i][j]表示到i时用j次机会的最少花费（到了第j层图）,vis[i][j]表示到i时用j次机会是否出现过，那么我们有如下两种选择 1.花费一次机会，到达下一个点不花钱 2.花钱到达下一个点 而如果vis[i][j]=1了，就不用往下找了，因为肯定小于等于最优解（dijkstra的贪心策略） 然后就没有了
#include<cstdio> #include<iostream> #include<queue> #include<cstring> using namespace std; int n,k,m,st,sd,cnt,ans=0x3f3f3f3f,head[100005],dp[100005][11]; bool vis[100005][11]; struct ren{ int next,to,dis; }a[200005]; void add(int x,int y,int w) { a[++cnt].to=y; a[cnt].next=head[x]; head[x]=cnt; a[cnt].dis=w; } struct qren{ int u,val,used; qren(){}; qren(int U,int Val,int Used) { u=U; val=Val; used=Used; } bool operator<(const qren &a)const { return val>a.val; } }; priority_queue<qren> q; void dijkstra() { memset(dp,0x3f,sizeof(dp)); dp[st][0]=0; q.push((qren){st,0,0}); while(!q.empty()) { int u=q.top().u,now=q.top().used; q.pop(); if(vis[u][now]) { continue; } vis[u][now]=1; for(int i=head[u];i;i=a[i].next) { int v=a[i].to,w=a[i].dis; if(!vis[v][now+1]&&dp[v][now+1]>dp[u][now]&&now<k)//至多免费k条边(到第k层图) { dp[v][now+1]=dp[u][now];//不花钱 q.push((qren){v,dp[v][now+1],now+1}); } if(!vis[v][now]&&dp[v][now]>dp[u][now]+w) { dp[v][now]=dp[u][now]+w;//不使用免费机会,花钱 q.push((qren){v,dp[v][now],now}); } } } } int main() { scanf("%d%d%d",&n,&m,&k); scanf("%d%d",&st,&sd); st++; sd++; for(int i=1;i<=m;i++) { int x,y,w; scanf("%d%d%d",&x,&y,&w); x++; y++; add(x,y,w); add(y,x,w); } dijkstra(); for(int i=0;i<=k;i++) { ans=min(ans,dp[sd][i]);//每种花费的情况都要考虑（遍历每层图的结果） } printf("%d\n",ans); return 0; }动规+最短路确实挺巧妙的
传送门 居然没看出来两次最小生成树。。。 很裸的一道题，因为第一次找一级公路为最优，都是从小到大排序，因为答案由最大的决定，所以两样都往小取就是最优解
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int n,m,k,ans,cnt,fa[9000005]; bool vis[9000005]; struct ren{ int u,v,c1,c2,id; }a[9000005]; bool cmp(ren x,ren y) { return x.c1<y.c1; }//求一级公路 bool pmc(ren x,ren y) { return x.c2<y.c2; }//二级公路 int Find(int a) { if(a==fa[a]) { return a; } return fa[a]=Find(fa[a]); } int main() { scanf("%d%d%d",&n,&k,&m); m-=1; for(int i=1;i<=n;i++) { fa[i]=i; } for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].c1,&a[i].c2); a[i].id=i; } sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++) { int u=a[i].u,v=a[i].v; int fx=Find(u),fy=Find(v); if(fx==fy) { continue; } ans=max(ans,a[i].c1); fa[fx]=fy; vis[a[i].id]=1; cnt++; if(cnt==k) { break; } }//kruscal sort(a+1,a+1+m,pmc); for(int i=1;i<=m;i++) { if(vis[a[i].id]) { continue; }//第一次已经连上了就不用再造二级公路了 int u=a[i].u,v=a[i].v; int fx=Find(u),fy=Find(v); if(fx==fy) { continue; } ans=max(ans,a[i].c2); fa[fy]=fx; cnt++; if(cnt == n-1) { break; } } printf("%d\n",ans); return 0; }每一次太阳的下落，都是为下一次黎明作序
