网站一年维护费用多少,平面设计的工作内容是什么,国网电子商务平台官网,手表网站制作模板前言
分数250250#xff0c;十分开心 正题 T1#xff1a;音乐节拍
洛谷题目链接#xff1a;https://www.luogu.org/problemnew/show/P2969
大意
有n段音乐#xff0c;每段音乐持续时间不同#xff0c;q个询问求一个时间点再放那首歌
考试时
开始时发现询问的时间点不…前言
分数250250250十分开心 正题 T1音乐节拍
洛谷题目链接https://www.luogu.org/problemnew/show/P2969
大意
有n段音乐每段音乐持续时间不同q个询问求一个时间点再放那首歌
考试时
开始时发现询问的时间点不是按顺序来的于是就想到了离线算法。
解题思路
先将询问排个序然后一个指针指向现在的音乐如果不是的话就往前推。
代码
#includecstdio
#includealgorithm
#define MN 50000
using namespace std;
struct node{int num,que,ans;
}qu[MN1];
int n,q,b[MN1];
bool cmp(node x,node y)
{return x.quey.que;
}
bool cmp2(node x,node y)
{return x.numy.num;
}
int main()
{//freopen(mnotes.in,r,stdin);//freopen(mnotes.out,w,stdout);scanf(%d%d,n,q);for (int i1;in;i)scanf(%d,b[i]);for (int i1;iq;i){scanf(%d,qu[i].que);qu[i].numi;//标记}sort(qu1,qu1q,cmp);//排序int j1,nowb[1]-1;//记录现在位置for (int i1;iq;i){while (qu[i].quenow)//往前推{j;nowb[j];}qu[i].ansj;//记录}sort(qu1,qu1q,cmp2);//排回原来的顺序for (int i1;iq;i)printf(%d\n,qu[i].ans);//输出
} T2电视游戏问题
大意
洛谷链接https://www.luogu.org/problemnew/show/P2967 有n个价格不同平台上面有不同的游戏每个游戏有不同的价格和价值要求价格不超过v时价值最大。
考试时
开始就想到了然后以为会超时就没打
解题思路
用f[0][i]f[0][i]f[0][i]表示到现在并且买了这个平台用了i元时最大价值 用f[1][i]f[1][i]f[1][i]表示到上次用了i元时最大价值 要将上一次继承过来
f[0][i]f[1][i−w]f[0][i]f[1][i−w]f[0][i]=f[1][i-w]
然后动态转移
f[0][i]max{f[0][i−w]c}f[0][i]max{f[0][i−w]c}f[0][i]=max\{ f[0][i-w]+c \}
最后更新f[1]f[1]f[1]
f[1][j]max{f[0][j] , f[1][j]}f[1][j]max{f[0][j],f[1][j]}f[1][j]=max\{f[0][j]\ \ ,\ \ f[1][j]\}
代码
#includecstdio
#includealgorithm
using namespace std;
int n,v,f[51][100001],w,c,k,wc;
int main()
{freopen(vidgame.in,r,stdin);freopen(vidgame.out,w,stdout);scanf(%d%d,n,v);for (int i1;in;i){scanf(%d%d,w,k);for (int jw;jv;j)f[0][j]f[1][j-w];//继承上次for (int m1;mk;m){scanf(%d%d,wc,c);for (int jv;jwwc;j--)f[0][j]max(f[0][j],f[0][j-wc]c);//动态转移}for (int j1;jv;j)f[1][j]max(f[0][j],f[1][j]),f[0][j]0;//更新最大}printf(%d,f[1][v]);
} T3头晕的奶牛
洛谷链接https://www.luogu.org/problemnew/show/P2017
大意
一个n个点的图有m1条有向边有m2条无向边将无向边变为有向边使得图变为有向无环图。
考试时
有向无环图我就想到了拓扑排序然后就敲了一个东西发现不行。然后我就研究发现可以将所有的点都集结在终点是出度为0的。然后打了一个奇怪的东西就80。
解题思路
先用有向边建图然后再进行拓扑排序之后一条无向边的话就将拓扑序排在前面的连排在后面的因为拓扑序排在后面的无论如何也回不到前面。
代码
#includecstdio
#includealgorithm
using namespace std;
struct node{int to,next;
}a[300001];
int n,m1,m2,x,y,ls[100001],in[100001],tot,head,tail,state[100001];
int d[100001],s,t,star,ta;
void addl(int x,int y)
{a[tot].toy;in[y];a[tot].nextls[x];ls[x]tot;
}
void bfs()//拓扑排序
{do{xstate[head];for (int ils[x];i;ia[i].next){ya[i].to;if (!d[y]){in[y]--;if (in[y]0){state[tail]y;d[y]ta;}}}}while (headtail);
}
int main()
{//freopen(dizzy.in,r,stdin);//freopen(dizzy.out,w,stdout);scanf(%d%d%d,n,m1,m2);for (int i1;im1;i){scanf(%d%d,x,y);addl(x,y);}for (s1;sn;s)if (in[s]0) state[tail]s,d[s]ta;//寻找起点bfs(),t;for (int i1;im2;i){scanf(%d%d,x,y);if (d[x]d[y]) printf(%d %d\n,x,y);//判断else printf(%d %d\n,y,x);}
} T4过路费
洛谷https://www.luogu.org/problemnew/show/P2966
大意
一个图一个点到另一个点的距离就是路径边权和加上路径上的最大点值。
考试时
写了一个spfa然后发现一种情况 这时spfa就会走1−2−4−51−2−4−51->2->4->5代价11可是如果走1−3−4−51−3−4−51->3->4->5的话代是价10。然后我就想到了一个方法 用f[i][j]f[i][j]f[i][j]表示到达i点时路径上最大点值的是j时的最短距离。 然后超时70分
解题思路
首先我们将点值进行排序用num[i]num[i]num[i]表示点权从小到大排在第iii的点。然后枚举k" role="presentation" style="position: relative;">kkk时我们先从点权最小的点开始枚举然后
dis[i][j]min{dis[i][k]dis[k][j]}dis[i][j]min{dis[i][k]dis[k][j]}
dis[i][j]=min\{dis[i][k]+dis[k][j]\} cost[i][j]min{dis[i][j]max{c[i],c[j],c[k]}}cost[i][j]min{dis[i][j]max{c[i],c[j],c[k]}}
cost[i][j]=min\{dis[i][j]+max\{c[i],c[j],c[k]\}\} 排点权的目的是为了保证max{c[i],c[j],c[k]}max{c[i],c[j],c[k]}max\{c[i],c[j],c[k]\}中有里面最大的代码
#includecstdio
#includealgorithm
#includecstring
#define maxs(x,y,z) max(x,max(y,z))
using namespace std;
int n,m,k,num[251],dis[251][251],cost[251][251],c[251],x,y,w;
int main()
{memset(dis,127/3,sizeof(dis));memset(cost,127/3,sizeof(cost));scanf(%d%d%d,n,m,k);for (int i1;in;i){num[i]i;scanf(%d,c[i]);}for (int i1;im;i){scanf(%d%d%d,x,y,w);dis[x][y]dis[y][x]min(dis[x][y],w);//无向图}for (int i1;in;i)for (int ji1;jn;j)if (c[num[i]]c[num[j]])swap(num[i],num[j]);//排序for (int q1;qn;q){int knum[q];for (int i1;in;i)for (int j1;jn;j)if (i!ji!kj!k){dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);cost[i][j]min(cost[i][j],dis[i][j]maxs(c[i],c[j],c[k]));//Floyd}}for (int i1;ik;i){scanf(%d%d,x,y);printf(%d\n,cost[x][y]);}
}
