Luogu 魔法学院杯-第二弹（萌新的第一法blog）

本文主要是介绍Luogu 魔法学院杯-第二弹（萌新的第一法blog），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

虽然有点久远还是放一下吧。

传送门：https://www.luogu.org/contest/show?tid=754

第一题沉迷游戏，伤感情

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;long long t,n,ans,i,c[10005],last,now,sum[10005],s;
deque<long long> q;inline long long read()
{long long ret=0,iep=1;char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') iep=-1;ch=getchar();}while (ch>='0'&&ch<='9') {ret=ret*10+ch-'0';ch=getchar();}return ret;
}int main()
{t=read();while (t--){n=read();ans=0;memset(sum,0,sizeof sum);for (i=1;i<=n;i++) s=read(),sum[i]=s+sum[i-1];q.clear();for (i=1;i<=n;i++){c[i]=read();while (!q.empty() && c[i]<=c[q.back()]) q.pop_back();q.push_back(i);}last=0;while (!q.empty()){now=q.front();q.pop_front();ans+=(sum[now]-sum[last])*c[now];last=now;}printf("%lld\n",ans);}
}

第二题精研白学，减智商

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int n,m,t,x,y,last,i,k,tot;
double f[10005][2],z,a[1500];struct node{int x,y;double z;
}A[10005];struct edge{double s[305][305];edge operator *(const edge &x) const{edge ret;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){ret.s[i][j]=0;for (int k=1;k<=n;k++)ret.s[i][j]+=s[i][k] * x.s[k][j];}return ret;}
}mat,map;inline int read()
{int ret=0,iep=1;char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') iep=-1;ch=getchar();}while (ch>='0'&&ch<='9') {ret=ret*10+ch-'0';ch=getchar();}return ret;
}int dfs()
{last=0;for (i=1;i<=n;i++) f[i][0]=a[i];for (i=1;i<=n;i++) f[i][(last+1)%2]=0;for (i=1;i<=tot;i++) f[A[i].y][(last+1)%2]+=f[A[i].x][last%2]*map.s[A[i].y][A[i].x]*1.0;
}edge ksm(int x)
{if (x==1) return mat;edge ret=ksm(x/2);ret=ret*ret;if (x&1) return ret*mat;return ret;
}int doit()
{last=0;for (i=1;i<=n;i++) f[i][0]=a[i];for (k=1;k<=t;k++){for (i=1;i<=n;i++) f[i][(last+1)%2]=0;for (i=1;i<=tot;i++) f[A[i].y][(last+1)%2]+=f[A[i].x][last%2]*A[i].z*1.0;last++;}
}int main()
{n=read();m=read();t=read();tot=0;if (n<100){for (i=1;i<=m;i++)tot++,A[tot].x=read(),A[tot].y=read(),cin>>A[tot].z,mat.s[A[tot].y][A[tot].x]+=A[tot].z;map=ksm(t);for (i=1;i<=n;i++) cin>>a[i];dfs();last++;for (i=1;i<n;i++)printf("%.6f ",f[i][last%2]);printf("%.6f\n",f[n][last%2]);}else{for (i=1;i<=m;i++)tot++,A[tot].x=read(),A[tot].y=read(),cin>>A[tot].z;for (i=1;i<=n;i++) cin>>a[i];doit();for (i=1;i<n;i++)printf("%.6f ",f[i][last%2]);printf("%.6f\n",f[n][last%2]);}return 0;
}