C2020 2020.10.2模拟赛

信息学——模拟赛

---

考试情况

考场上期望得分VS实际得分

期望得分：

T1	T2	T3	总分
100	70	100	270

实际得分：

T1	T2	T3	总分
100	55	100	255

T1 物品选取

$1^o$ 分析

考虑DP，不难想到对于A，B，C类分别处理（同一状态，不同方程）。

首先B和C的类型是很好处理的，两个基本的背包。

考虑如何处理A（似乎有人弄出理论$O(nm)$的算法？反正我不会）。

考虑枚举2个量，总体积，当前物品取的体积。

总复杂度理论$O(nm)$到$O(nm^2)$，似乎最坏情况过不了，但实测是过了的（论常数的重要性）。

出题人给的正解也是这个……

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
int f[2005];
inline int max(int x,int y)
{
    return x>y?x:y;
}
inline void work1(int a,int b)
{
    for (register int i=m;i>=0;--i)
        for (register int j=1;j<=i;++j)
            f[i]=max(f[i],f[i-j]+a*j*j-b*j);
}
inline void work2(int a,int b,int c)
{
    for (register int i=m;i>=0;--i)
        for (register int j=1;j<=c;++j)
            if (b*j<=i)
               f[i]=max(f[i],f[i-b*j]+a*j);
}
inline void work3(int a,int b)
{
    for (register int i=b;i<=m;++i)
        f[i]=max(f[i],f[i-b]+a);           
}
int main(){
//  freopen("pack.in","r",stdin);
//  freopen("pack.out","w",stdout);
    n=read(),m=read();
    for (register int i=1;i<=n;++i)
        {
        int x=read(),a,b,c;
        if (x==1)
           a=read(),b=read(),work1(a,b);
        if (x==2)
           a=read(),b=read(),c=read(),work2(a,b,c);
        if (x==3)
           a=read(),b=read(),work3(a,b);
        }
    printf("%d",f[m]);
    return 0;
}

$2^o$ 思考与总结

所以说对于这种玄学的复杂度不要不敢写，毕竟理论上界也就$10^8$

很多时候往往会到不了理论上界，当然常数必须优秀（再次论常数重要性）。

T2 蛇形矩阵

$1^o$ 分析

最难的一道，还是个鬼畜推公式的题。

首先得会$O(1)$求一个数对应的位置和一个位置对应的数。

那么考虑计算每个数对于当前矩阵的贡献。

显然对于坐标为$(i,j)$，所求矩阵坐标为$(x,y)$，数为$a$的贡献为$a*(x-i+1)*(y-j+1)$。

将所有贡献求和，那么你就有60分了（但实测有很多常数优秀的跑到了60以上）。

考虑满分的范围是$n<=10^{10}$，容易联想到根号复杂度。

考虑对于$x$为右下角的矩阵进行拆分。

会发现它可以拆成一个正方形，加上很多宽为1的矩形（后文称为条）。

而我们发现正方形可以拆成诸多7字形（如图中5->6->7->8->9），而且条显然就是7字型的一部分，算法相似。

而7字型的个数是$\sqrt n$的数量级，如果我们能用$O(1)$的时间得到每个7字型就能以$O(\sqrt n)$的时间通过。

那么7字型如何求呢？

考虑拆成两个条再减去重叠部分（5->6->7与7->8->9），那么只要推条的公式就好了。

注意推的时候有多种情况要分类，需要考虑横条与竖条，以及7字型的奇偶性（算上单独的条公式总共6个……）。

下面的推导只推奇数7且横条的情况，其他同理。

接下来就开始愉快的推公式：

设当前是第$i$个7字，输入的$n$对应的数为$(x,y)$

则右上角数为$i^2$，坐标为$(1,i)$，左下角为$(i-1)^2+1$，坐标为$(i,1)$，右下角为右上角与左下角的平均数，坐标为$(i,i)$。

$$ans=((i-1)^2+1)*(x-i+1)*y+((i-1)^2+2)*(x-i+1)*(y-1)+\ldots+((i-1)^2+1+(i-1))*(x-i+1)*(y-i+1)$$
令$s=(i-1)^2+1$，将$(x-i+1)$提出：
$$ans=(x-i+1)*(s*y+(s+1)*(y-1)+\ldots+(s+i-1)*(y-i+1))$$
发现括号中每项都有一个$s*y$，提出
$$ans=(x-i+1)*(i*s*y+(y-s)+2(y-s)+\ldots+(i-1)*(y-s)-1^2-2^2-\ldots-(i-1)^2)$$
将$(y-s)$提出，两个都可写成求和：
$$ans=(x-i+1)*(i*s*y+\sum_{j=1}^{i-1}{(y-s)}-\sum_{j=1}^{i-1}{j^2})$$
发现第一个系数为等差，第二个为平方和，化简：
$$ans=(x-i+1)*(i*s*y+\frac{i*(i-1)}{2}*(y-s)-\frac{(i-1)*i*(2*i-1)}{6})$$
到此为止，横条公式完成。

剩下几种情况照这种推一遍就是了，几乎没什么不同。

最后由于算了右下两次，单独减掉即可。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
const int mod=1e9+7;
int n,m,x,y,ans;
inline int get_x(int num)
{
    int now=sqrt(num);
    if (now*now==num)
       return now&1?1:now;
    now++;
    int cnt=((now-1)*(now-1)+1+now*now)/2;
    if (num>=cnt)
       return now&1?now-(num-cnt):now;
    else
       return now&1?now:now-(cnt-num);
}
inline int get_y(int num)
{
    int now=sqrt(num);
    if (now*now==num)
       return now&1?now:1;
    now++;
    int cnt=((now-1)*(now-1)+1+now*now)/2;
    if (num>=cnt)
       return now&1?now:now-(num-cnt);
    else
       return now&1?now-(cnt-num):now;
}
inline int calc(int i,int j,int now,int k)//我只退了4种情况公式，最后算条可以巧妙的用
{
    if (k==1)
       return ((y-j+1)%mod*(i*now%mod*x%mod-i*(i-1)/2*(x+now)%mod+i*(i-1)*(2*i-1)/6%mod+mod)%mod)%mod;
    if (k==2)
       return ((x-j+1)%mod*(i*now%mod*y%mod+i*(i-1)/2*(y-now)%mod-i*(i-1)*(2*i-1)/6%mod+mod)%mod)%mod;
    if (k==3)
       return ((y-j+1)%mod*(i*now%mod*x%mod+i*(i-1)/2*(x-now)%mod-i*(i-1)*(2*i-1)/6%mod+mod)%mod)%mod;
    if (k==4)
       return ((x-j+1)%mod*(i*now%mod*y%mod-i*(i-1)/2*(y+now)%mod+i*(i-1)*(2*i-1)/6%mod+mod)%mod)%mod;
}
signed main(){
    n=read(),x=get_x(n),y=get_y(n),m=min(x,y); 
    for (register int i=m;i>=1;--i)
        {
        int cnt=((i-1)*(i-1)+1+i*i)/2,now;
        if (i&1)
           {
           now=i*i%mod,ans=(ans+calc(i,i,now,1))%mod;
           now=(i*i-2*i+2)%mod,ans=(ans+calc(i,i,now,2))%mod;
           ans=(ans-cnt*(x-i+1)%mod*(y-i+1)%mod+mod)%mod;
           }
        else
           {
           now=(i*i-2*i+2)%mod,ans=(ans+calc(i,i,now,3))%mod;
           now=i*i%mod,ans=(ans+calc(i,i,now,4))%mod;
           ans=(ans-cnt*(x-i+1)%mod*(y-i+1)%mod+mod)%mod;
           }
        ans=(ans+mod)%mod;
        }
    for (register int i=m+1;i<=y;++i)
        {
        int now;
        if (i&1)
           now=i*i%mod,ans=(ans+calc(x,i,now,1))%mod;
        else
           now=(i*i-2*i+2)%mod,ans=(ans+calc(x,i,now,3))%mod;
        ans=(ans+mod)%mod;
        } 
    for (register int i=m+1;i<=x;++i)
        {
        int now;
        if (i&1)
           now=(i*i-2*i+2)%mod,ans=(ans+calc(y,i,now,2))%mod;
        else
           now=i*i%mod,ans=(ans+calc(y,i,now,4))%mod;
        ans=(ans+mod)%mod;
        }
    printf("%lld",ans=(ans+mod)%mod);
    return 0;
}

$2^o$ 思考与总结

这种题考场上的确性价比不高，先打部分分，正解靠后做。

T3 正则表达式

$1^o$ 分析

这题最重要的话是这句：

如果存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0。

翻译一下就是：

如果A,B可以相互到达，则其边权为0

而$A$与$B$相互到达，这是很明显的强连通分量的特点。

考虑跑遍$Tarjan$缩点，则同一个$SCC$中的点之间的边权都为$1$，重新建图跑遍最短路就好了。

总结一下就是：建图——>缩点——>重新建图——>最短路

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define INF INT_MAX
#define mp make_pair
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
struct node{
    int v,nex;
    int w;
}line[2000005],edge[2000005];
int head[1000005],len,tot,num;
int dfn[200005],low[200005],col[200005],st[200005],top;
priority_queue< pair<int,int> > q;
int dist[200005];
bool vst[200005];
inline void make_map(int u,int v,int w)
{
    len++;
    edge[len].nex=head[u];
    edge[len].v=v;
    edge[len].w=w;
    head[u]=len;
}
inline void Tarjan(int x)
{
    dfn[x]=low[x]=++num,st[++top]=x;
    for (register int i=head[x];i;i=edge[i].nex)
        {
        int y=edge[i].v;
        if (!dfn[y])
           Tarjan(y),low[x]=min(low[x],low[y]);
        else
        if (!col[y])
           low[x]=min(low[x],dfn[y]);
        }
    if (dfn[x]==low[x])
       {
       col[x]=++tot;
       while (top&&st[top]!=x)
             col[st[top--]]=tot;
       top--;
       }
}
inline void Dijstra()
{
    memset(vst,0,sizeof(vst));
    for (register int i=1;i<=n;++i)
        dist[i]=INF;
    q.push(mp(0,1)),dist[1]=0;
    while (!q.empty())
          {
          int x=q.top().second;
          q.pop();
          if (vst[x])
             continue;
          vst[x]=1;
          for (register int i=head[x];i;i=edge[i].nex)
              {
              int y=edge[i].v,z=edge[i].w;
              if (dist[y]>dist[x]+z)
                 dist[y]=dist[x]+z,q.push(mp(-dist[y],y));
              }
          }
}
int main(){
//  freopen("regexp.in","r",stdin);
//  freopen("regexp.out","w",stdout);
    n=read(),m=read();
    for (register int i=1;i<=m;++i)
        {
        int u=read(),v=read(),w=read();
        make_map(u,v,w);
        }
    for (register int i=1;i<=n;++i)
        if (!dfn[i])
           Tarjan(i);
    for (register int x=1;x<=n;++x)
        for (register int i=head[x];i;i=edge[i].nex)
            {
            int y=edge[i].v;
            if (col[x]==col[y])
               edge[i].w=0;
            }
    Dijstra();
    printf("%d",dist[n]);
    return 0;
}

$2^o$ 思考与总结

缩点是重要的中间步骤处理，很多时候都需要用缩点创造条件，一定不能把$Tarjan$忘了。