20181023 模拟赛

 除了附加题AK模拟赛祭 T1 matrix 给出一个方阵，和q次修改，每次修改会选择某一行或某一列，后面的修改可以覆盖前面的修改 emmm，一般类似于后面的修改覆盖前面的修改，都会从后向前做，然而，这里只需要对每一行和每一列存储该行最后的修改以及修改的时间就行了 然后在输出矩阵的时候，找该点所在行和所在列的优先级大的那个进行输出就可以了 水题一道 ``` #include<bits/stdc++.h> using namespace std; int n,m,q,xx[1010],yy[1010],idx[1010],idy[1010],op,k,s; int read(){ int u=0;char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') u=(u<<1)+(u<<3)+c-'0',c=getchar(); return u; } int main(){ n=read(),m=read(),q=read(); for(int i=1;i<=q;i++){ op=read(),k=read(),s=read(); if(op==1) xx[k]=s,idx[k]=i; else yy[k]=s,idy[k]=i; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) printf("%d%c",idx[i]>idy[j]?xx[i]:yy[j],j==m?'\n':' '); return 0; } ``` T2 coordinate 一开始站在原点，每次可以向上或向左或向右走一步，给出n，求出走n步有多少种情况 做这道题有很多方法，第一种就是暴力打表找规律，对于n，dfs出有多少种情况，然后找规律、 可以发现 $f[i]=2\times f[i-1]+f[i-2]$ 当然，如果我们仔细分析，也可以发现，相对于i-1步，我们就增加了第一步，那么我们第一步如果向上或向左或向右走，然后向上走，那么就是f[i-1]的部分 如果我们第2步向左或向右走，那么第一步相应的只能向左或向上以及向右或向上，加起来就是一个f[i-1]和一个第一步和第二部都向上走的情况，这就是f[i-2] 同样推出了同一个递推式 然后，我们对于$1\times10^{9}$的数据范围，我们明显不能用$O(n)$的算法解决 只能用$O(log_2n)$的算法解决 我们回想一下曾经做过的斐波那契数列的求第n项，就是用矩阵乘法，我们可以看到 $\lgroup^{f[n]}_{f[n-1]}\rgroup=\lgroup^{2f[n-1]+f[n-2]}_{f[n-1]}\rgroup=\lgroup^{2,1}_{1,0}\rgroup*\lgroup^{f[n-1]}_{f[n-2]}\rgroup=\lgroup^{2,1}_{1,0}\rgroup^{n-1}*\lgroup^{f[1]}_{f[0]}\rgroup$ 然后就是矩阵快速幂，并取模 ``` #include<bits/stdc++.h> #define mod 1000000007 using namespace std; int n; struct sq{ long long x1,x2,y1,y2; }base; sq multy(sq a,sq b){ sq t; t.x1=(a.x1*b.x1+a.x2*b.y1)%mod; t.x2=(a.x1*b.x2+a.x2*b.y2)%mod; t.y1=(a.y1*b.x1+a.y2*b.y1)%mod; t.y2=(a.y1*b.x2+a.y2*b.y2)%mod; return t; } sq powmod(sq a,int b){ if(b==1) return a; sq t=powmod(a,b>>1); t=multy(t,t); if(b&1) t=multy(t,a); return t; } int main(){ scanf("%d",&n); if(n==1){ printf("%d",3); return 0; } base=(sq){2,1,1,0}; sq k=powmod(base,n-1); printf("%lld",(3ll*k.x1+1ll*k.x2)%mod); } ``` T3 calabash 你有一个有向无环图，每个边有边权，问从1到n最小的平均点权是多少 首先，该题的数据范围一看非常小，点数小于200，边数小于2000 那么我就想到了对到达每一个点的每一种点数都存一个最小边权和 然后用这种方式相当于将每一个点都拆成200个点，然后跑一边spfa，用最短路求出来就可以了 emmm，感觉并不难啊 ``` #include<bits/stdc++.h> using namespace std; int n,m,x,y,w,vl[210][210],vi[210][210],cnt; double minn=1e9; vector<int> g[210],l[210]; queue<int> qq,dd; void spfa(){ qq.push(1),dd.push(0); vi[1][0]=1; vl[1][0]=0; while(!qq.empty()){ cnt++; int u=qq.front(),d=dd.front();qq.pop(),dd.pop(); vi[u][d]=0; for(int i=0;i<g[u].size();i++){ int v=g[u][i],le=l[u][i]; if(vl[v][d+1]>vl[u][d]+le){ vl[v][d+1]=vl[u][d]+le; if(!vi[v][d+1]) qq.push(v),dd.push(d+1),vi[v][d+1]=1; } } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&x,&y,&w),g[x].push_back(y),l[x].push_back(w); memset(vl,0x7f,sizeof(vl)); spfa(); for(int i=1;i<n;i++) minn=min(minn,(double)vl[n][i]/(double)(i+1)); printf("%lf",minn); } ``` T4 mixedblood 你有一排多个点，每个点都有x,a,b,c,d四个值，从某一个点出发向比它编号大的点出发需要|x[j]-x[i]|+d[i]+a[j]，如果向比它编号小的点出发需要|x[i]-x[j]|+c[i]+b[j]，我们规定，从某个点开始每个点最多只经过一遍，最后回到出发点，多次走（之前走过的点都不能再走）最多需要多少值 对于这道题，第一开始看是一脸懵逼的，然后发现了x的值是随x的递增而递增的 所以我们可以对每一个点的点权进行重新的定义 li为从左边走到这个点，lo表示从左边离开这个点，ri表示从右边走到这个点，ro表示从右边离开这个点 那么，很明显，从左边离开或走到该点，都会增加x[i]的权值，而从右边离开和走到该点都会减少x[i]的权值，然后加上a,b,c,d的值，就可以得到 $li=a[i]+x[i],lo=c[i]+x[i],ri=b[i]-x[i],ro=d[i]-x[i]$ 然后我们根据从哪边走到该点和从哪边走出该点分成四类 1.左进左出 $sum[i][1]=li[i]+lo[i]$ 2.右进右出 $sum[i][2]=ri[i]+ro[i]$ 3.左进右出 $sum[i][3]=li[i]+ro[i]$ 4.右进左出 $sum[i][4]=ri[i]+lo[i]$ 然后就是类似于括号匹配的东西搞一搞 $dp[i][j]$表示到$i$这个点，还有$j$个$sum[i][1]$没有匹配时的最大权值和 然后就是对该点的状态进行分类讨论就可以了 ``` #include<bits/stdc++.h> using namespace std; int n; long long li[5010],ri[5010],lo[5010],ro[5010],sum[5010][5],dp[5010][5010],x[5010],a[5010],b[5010],c[5010],d[5010],inf; long long read(){ int u=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1;else f=1;c=getchar();} while(c>='0'&&c<='9') u=(u<<1)+(u<<3)+c-'0',c=getchar(); return u*f; } int main(){ n=read(); for(int i=1;i<=n;i++) x[i]=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); for(int i=1;i<=n;i++) c[i]=read(); for(int i=1;i<=n;i++) d[i]=read(); for(int i=1;i<=n;i++){ li[i]=a[i]+x[i],ri[i]=b[i]-x[i],lo[i]=c[i]+x[i],ro[i]=d[i]-x[i]; if(i==1) li[i]=0,lo[i]=0; if(i==n) ri[i]=0,ro[i]=0; sum[i][1]=li[i]+lo[i]; sum[i][2]=ri[i]+ro[i]; sum[i][3]=li[i]+ro[i]; sum[i][4]=ri[i]+lo[i]; } memset(dp,128,sizeof(dp)); inf=0x8080808080808080; dp[0][0]=0; for(int i=1;i<=n;i++){ for(int j=i;j>=0;j--){ if(j>=1){ if(dp[i-1][j-1]!=inf) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+sum[i][2]); if(dp[i-1][j]!=inf) dp[i][j]=max(dp[i][j],dp[i-1][j]+max(sum[i][3],sum[i][4])); } if(dp[i-1][j+1]!=inf)dp[i][j]=max(dp[i][j],dp[i-1][j+1]+sum[i][1]); } } printf("%lld",dp[n][0]); } ```