这场考试真的把我打自闭了。 先是T2调了半个小时一直过不了样例，再后面三题都做完了T1却毫无思路。。。 总体不是特别难，3道提高+，一道不知道。
小明和小红在一起玩游戏，小明觉得现在玩的游戏太无聊了，便给小红出了一道数列问题。数列问题的题目如下： 一开始，小明给小红一个只含有数字1的数列，接下来，小红可以对这个数列进行以下操作中的一种操作：
· 对序列中已有的一个元素加1. · 复制一个序列中已有的元素到序列的末尾. 比如：一开始序列中只有一个元素[1]我们可以选择这个序列中的第一个元素进行第二种操作，即复制操作，这样，这个序列就变成了[1,1] 然后，我们可以对这个序列中的第一个元素进行第一种操作，即将第一个元素进行+1.这样，这个序列就变成了[2,1] 现在，小明问小红，她最少需要进行多少次操作，可以使得序列中所有元素的和至少为n。 小红面对小明的这个问题一脸懵逼，于是，她来求助聪明的你，希望你能够帮助她解决这个问题。
第一行一个数字 t ( 1 ≤ t ≤ 1000 ) t(1\le t\le1000) t(1≤t≤1000)，表示测试数据的组数。 接下来行，每行一个数字 n ( 1 ≤ n ≤ 1 0 9 ) n(1\le n\le10^9) n(1≤n≤109)，表示序列所有元素和至少应该达到的数。
对于每一个问题，回答一个数字，表示小红最少需要操作的次数。
样例输入
5 1 5 42 1337 1000000000样例输出
0 3 11 72 63244企图硬算：没打出来，失败。
企图爆搜：程序爆炸，失败。
企图骗分：过了样例并且AC。
(⊙ˍ⊙) (⊙o⊙) (⊙▽⊙)！
尝试输出 n \sqrt n n (别问我为毛要尝试，只是单纯做不来还闲着没事)
[input]n[output]sqrt(n)[ans]11.000000052.2360683426.48074111133736.56501172100000000031622.77660263244好像，，有什么规律？
如果第二列的小数部分>=0.5 第三列的值为(int)第二列的值×2否则，如果第二列的小数部分不为0 第三列的值为(int)第二列的值×2-1否则 第三列的为(int)第二列的值×2-2其中 (int)x 表示 ⌊ x ⌋ \lfloor x\rfloor ⌊x⌋
那这题就粗来啦！
#include<cmath> #include<cstdio> int t,n,mn; void ly_AK_IOI(int x){ //不要管这个函数名 double y=sqrt(x); int z=(int)y; if(y-z>=0.5) printf("%d",z<<1); else if(y-z==0) printf("%d",(z<<1)-2); else printf("%d",(z<<1)-1); return; } int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); ly_AK_IOI(n); if(t)puts(""); } return 0; }链接
这。。好像。。可能。。大概。。应该。。也许。。或许。。大约。。(以下省略1万字)是道DP吧？ 【凭感觉做题晚期患者】 用 f [ i ] f[i] f[i] 表示让第 i i i 头奶牛为当前分组的最后一头，已分好的所有组的奶牛技能值之和。
#include<cstdio> int n,k,mx; int a[10005],f[10005]; int max(int x,int y){ return x>y?x:y; } int min(int x,int y){ return x<y?x:y; } int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i){ mx=0; for(int j=i;j<min(i+k,n+1);++j){ //枚举第i~i+k-1头牛为当前分组末尾的情况 mx=max(mx,a[j]); //求当前分组的最大值，因为每次循环会多一头牛，所以每次都要重新求 f[j]=max(f[j],(j-i+1)*mx+f[i-1]); //不用在程序末尾重新把技能值相加的好方法 } } printf("%d",f[n]); return 0; }链接
听他们说，这是一道分层图，可惜我不会 所以，我们可以先动动我们不太灵光的脑子，先打一个 Dijkstra 模板！ 好像是因为还没有彻底从上一道DP中清醒过来吧，所以，我突然发现！！ 我可以用DP来做这道题鸭！ 枚举从0条免费航线到 k k k 条免费航线时的最短路，也就是跑 k + 1 k+1 k+1 次最短路就行啦~ 这数据范围应该过的了叭~ 那么怎么实现这个“DP最短路”呢？ 简单，把 Dijkstra 里的 dis 数组改一下，用 dis[i][j] 表示从起点出发，有 i i i 条免费航线时到 j j j 的最短路就行啦~
#include<queue> #include<cstdio> #include<vector> using namespace std; const int maxn=1e4+5; struct ly_AK_IOI{ //同样不要注意这个结构体名 int e,w; //终点、权值 WJC_AK_IOI(int E=0,int W=0){ e=E,w=W; } }; int dis[15][maxn]; bool vis[15][maxn]; int n,m,k,x,y,z,s,t; vector<WJC_AK_IOI>g[maxn]; priority_queue<pair<int,int> >q; void add(int b,int r,int d){ g[b].push_back(WJC_AK_IOI(r,d)); g[r].push_back(WJC_AK_IOI(b,d)); return; } void Dijkstra(void){ for(int i=0;i<=k;++i){ //枚举免费航线数量 q.push(make_pair(0,s)); dis[i][s]=0; while(!q.empty()){ int f=q.top().second; q.pop(); if(vis[i][f])continue; vis[i][f]=1; for(int j=0;j<g[f].size();++j){ int e=g[f][j].e,w=g[f][j].w; if(dis[i][e]>dis[i][f]+w){ dis[i][e]=dis[i][f]+w; q.push(make_pair(-dis[i][e],e)); //以上为Dijkstra板子 } if(i){ //防RE if(dis[i][e]>dis[i-1][f]){ dis[i][e]=dis[i-1][f]; //第一维只用到i和i-1，貌似可以用滚动数组优化 q.push(make_pair(-dis[i][e],e)); //但我懒得写，能过就行QWQ } } } } } return; } void read(int&x){ x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch&15); ch=getchar(); } return; } int main(){ read(n);read(m);read(k);read(s);read(t); for(int i=0;i<=10;++i){ for(int j=0;j<n;++j) //坑点：编号从0到n-1，但是貌似用memset就不用在意这些QWQ dis[i][j]=0x3f3f3f3f; } while(m--){ read(x);read(y);read(z); add(x,y,z); } Dijkstra(); printf("%d",dis[k][t]); return 0; }链接
考试的时候只让输出花费最大的公路的花费估计是老师懒得写SPJ，所以我就不写路径啦~
总体来说，就是两次最小生成树。
为了方便先把 m--。
第一次从 1 1 1 到 m m m 枚举一级公路。
Q:一级公路花费不是更大吗？为什么不是 1 1 1 到 k k k 呢？A:万一前 k k k 条边有环，也就是 f i n d ( b e g i n ) = = f i n d ( e n d ) find(begin)==find(end) find(begin)==find(end) ， c o n t i n u e continue continue 了呢？（80分死在这儿了QAQ）
我们用变量 c n t cnt cnt 统计加入最小生成树的边数，当 c n t = = k cnt==k cnt==k 时， b r e a k break break。
第二次从 1 1 1 到 m m m 循环枚举二级公路。
#include<cstdio> #include<algorithm> using std::sort; const int maxn=2e4+5; int f[maxn]; int n,k,m,ans,cnt; struct ly_AK_IOI{ //同样不要在意这个结构体名 int b,e,c; //起点、终点、权值 ly_AK_IOI(int B=0,int E=0,int C=0){ b=B,e=E,c=C; } bool operator<(const yzk_AK_IOI q)const{ return c<q.c; } }a[maxn],b[maxn]; //A、B分别存一级公路、二级公路 int max(int x,int y){ return x>y?x:y; } void init(){ //初始化函数，因为没有调用而查了20 mins错。。。 for(int i=1;i<=n;++i) f[i]=i; return; } int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } void bing(int x,int y){ f[x]=y; return; } void read(int&x){ x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch&15); ch=getchar(); } return; } int main(){ read(n);read(k);read(m); m--; init(); for(int i=1;i<=m;++i){ read(a[i].b);read(a[i].e); b[i].b=a[i].b;b[i].e=a[i].e; read(a[i].c);read(b[i].c); //A、B的起点相同，权值不同，个人认为两个数组比较好理解 } sort(a+1,a+m+1); sort(b+1,b+m+1); for(int i=1;i<=m;++i){ if(cnt==k)break; int fx=find(a[i].b); int fy=find(a[i].e); if(fx==fy)continue; //之所以i不能从1到k就是因为这里可能被continue掉 bing(fx,fy); ans=max(ans,a[i].c); //统计最大花费 cnt++; //统计已加入的边数，与AK差的20分在这儿QWQ } //最小生成树模板 for(int i=1;i<=m;++i){ int fx=find(b[i].b); int fy=find(b[i].e); if(fx==fy)continue; bing(fx,fy); ans=max(ans,b[i].c); //统计最大花费 } printf("%d",ans); return 0; }2021.1.5 update GM童鞋你很不错，居然考原题哈哈哈哈哈 （考完下来） 我给你讲这道公路修建问题我绝对A不了！我以前写过题解！考场上的思路绝对和我题解里的思路不一样！A了我吃shit！ 操他妈的它A了
法二的代码不知道被哪个天杀的销毁了。（其实是XSC062自己）
思路也忘了QwQ
(*^▽^)ツ▄ ←点赞、关注、收藏
