前言

十分抱歉由于T4一个括号没写对和T2的大数据出锅给大家带来了不好的比赛体验。

赛后总结

A (82/189) 满分: 100分
B (20/137) 满分: 100分
C (6/75) 满分: 100分
D (3/43) 满分: 100分

COOL

给你一个字符串，求其子序列cooooooooooooooooooooooool 中 l 位置的最小值。

30pts

由于 $|S|=25$ 因此显然不存在，输出 -1 即可。

100pts

可以先找第一个 c 的位置，然后再找第 $1-24$ 个 o 的位置 ,最后找一个 l 的位置即可。

代码如下

#include<bits/stdc++.h>

using namespace std;

const int maxn=100100;

char s[maxn];
int n,cpos,ocnt,opos,lpos;

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    //find c
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='c') {cpos=i;break;}
    }
    if(!cpos) 
    {
        cout<<-1<<'\n';
        return 0;
    }
    for(int i=cpos;i<=n;i++)
    {
        if(s[i]=='o') ocnt++;
        if(ocnt==24) {opos=i;break;}
    }
    if(ocnt!=24) 
    {
        cout<<-1<<'\n';
        return 0;
    }
    for(int i=opos;i<=n;i++)
    {
        if(s[i]=='l') {cout<<i<<'\n';return 0;}
    }
    cout<<-1<<'\n';
}

food

$n$ 个物品，每个物品可以选择 $[1,b_i]$ 个，单价为 $a_i$ 。并且买 $b_i$ 个会自动变成 $b_i 1$ 个，价格为 $a_i*b_i$ 。买多了会有惩罚。

30pts

显然我们会买 $15$ 个。将数组排序取前 $15$ 大即可

50pts

当 $b_i=1$ 就相当于买了只能买 $1$ 送 $1$ 。

当 $b_i=2$ 相当于买 $2$ 送 $1$ 或者单买。

设 $f[i][j]$ 表示在第 $[1,i]$ 个食堂，打了 $j$ 个菜品花费。

对于 $b_i=2$ 转移即为 $f[i][j]=min(f[i-1][j],f[i-1][j-3] b[i]*a[i],f[i-1][j-1] a[i])$

对于 $b_i=1$ 转移即为 $f[i][j]=min(f[i-1][j],f[i-1][j-2] a[i])$

100pts

继续枚举，对 $b_i=k$

$f[i][j]=min(f[i-1][j],f[i-1][j-k-1] b[i]*a[i],f[i-1][j-l] l*a[i])$ 其中 $l \in [1,b_i-1]$

注意转移时代码的细节

#include<bits/stdc++.h>

using namespace std;

const int maxn=1010;

int f[maxn][maxn],n,x,q;
int b[maxn],a[maxn],cnt;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>x>>q;
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=n;i++) f[i][0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        for(int j=1;j<=x+n;j++)
        {
            for(int k=1;k<=min(j,b[i]-1);k++)
            {
                f[i][j]=min(f[i-1][j-k]+a[i]*k,min(f[i][j],f[i-1][j]));
            }
            if(j>=b[i]+1) f[i][j]=min(f[i-1][j-b[i]-1]+b[i]*a[i],min(f[i][j],f[i-1][j]));
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=x;i<=x+n;i++)
    {
        ans=min(ans,f[n][i]+(i-x)*q);
    }
    cout<<ans<<'\n';
    return 0;
}

latex

本题分为两部分

表达式计算

假设表达式字符串 t ，其被复制结果为 t+'*'+t

由于乘法有一个优先级问题，因此我们用一个栈。

当运算符为加法时，将其放入栈顶部。

当为乘法是，取出栈顶元素，与其相乘再放入栈顶。

高精度计算

考虑到竖式计算即可。

考虑倒序，即 $a[0]$ 代表最低位，则 $a\cdot b$ 中，对每一对 $i,j$ 为 $ans_{i j}=a_i \cdot b_j$

但是每个人高精度写法不同，以下代码仅供参考。

#include<bits/stdc++.h>

using namespace std;

const int maxn=34100;
const int basew=201;

struct bigint{

    int a[220]={0};
    
}v[maxn];

map <string,bigint> val;
int f[maxn],n,cnt;

bigint operator+(const bigint &a,bigint &b)
{
    bigint ans;
    for(int i=basew;i>=1;i--)
    {
        ans.a[i]+=a.a[i]+b.a[i];
        if(ans.a[i]>=10) 
        {
            ans.a[i-1]+=ans.a[i]/10;
            ans.a[i]%=10;
        }
    }
    return ans;
}

bigint operator*(const bigint &a,bigint &b)
{
    bigint ans;
    for(int i=basew;i>=1;i--)
    for(int j=basew;j>=1;j--)
    {
        if(basew-(basew-i)-(basew-j)<=0) continue;
        ans.a[basew-(basew-i)-(basew-j)]+=a.a[i]*b.a[j];
    }
    for(int i=basew;i>=1;i--)
    {
        if(ans.a[i]>=10) ans.a[i-1]+=ans.a[i]/10,ans.a[i]%=10;
    }
    return ans;
}

bigint getval(string &t)
{
    stack <pair<bigint,char> > s;
    //记录表达式出现的位置
    vector<int> p;
    int tn=t.size();
    for(int i=0;i<tn;i++)
    {
        if(t[i]=='+'||[i]=='*') p.push_back(i);
    }
    string nowver=t.substr(0,p[0]);
    p.push_back(tn);
    s.push({val[nowver],'+'});
    for(int i=0;i<p.size()-1;i++)
    {
        nowver=t.substr(p[i]+1,p[i+1]-p[i]-1);
        if(t[p[i]]=='*') 
        {
            bigint x=s.top().first*val[nowver];
            char f=s.top().second;
            s.pop();
            s.push({x,f});
        }
        else
        {
            bigint x=val[nowver];
            s.push({x,p[i]});
        }
    }
    bigint ans;
    while(!s.empty())
    {
        bigint x=s.top().first;
        char f=s.top().second;
        s.pop();
        ans=ans+x;
    }
    return ans;
}

int getf(int x)
{
    if(x==f[x]) return x;
    return f[x]=getf(f[x]);
}

void init()
{
    for(int i=1;i<=10000;i++) f[i]=i;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string tmp,v;
        bigint vt;
        cin>>tmp>>v;
        int tn=v.size();
        for(int j=tn-1;j>=0;j--)
        {
            vt.a[basew-(tn-1-j)]=v[j]-'0';
        }
        val[tmp]=vt;
    }
    string t;
    vector <int> eq;
    while(cin>>t)
    {
        if(t[0]=='$')
        {
            ++cnt;
            t=t.substr(1,t.size()-2);
            t=t+'*'+t;
            v[cnt]=getval(t);
        }
    }
    int flag=1;
    for(int i=1;i<=cnt;i++)
    {
        int flag=0;
        for(int j=1;j<=basew;j++)
        {
            if(v[i].a[j]) 
            {
                flag=1;
            }
            if(flag) cout<<v[i].a[j];
        }
        if(!flag) cout<<0;
        cout<<'\n';
    }
}

driver

考虑函数 $y=O_t- (1 \frac{O_t}{O_{max}}) *(w_{i,j})$

当斜率小于 $0$ 时,说明 $O_{max}< w$ 显然这条路走不通。我们考虑走得通的情况，则斜率一定大于 $0$

换句话说，当斜率大于 $0$ 带的油越多越能走。

当我们到终点时，假设之前最多加油为 $k$ 油箱还会剩下 $k$ 的油

20pts

枚举访问顺序即可。

40pts

一棵树的情况，直接bfs能走就走

50pts

如果带 $1L$ 油不可以，那么就得带 $2L$

设 $f[i][1/2]$ 表示带 $1/2L$ 油走到这里的最短路即可。

100pts

设 $f[i][1/2/.../O_{max}]$ 表示带 $1/2/.../O_{max}L$ 油走到这里的最短路。

考虑转移，之前已经想到，带的油越多越能走。因此可以二分或者倒序扫描得到一条边要通过需要油的最小值。

当 $(i,j)$ 这一条边在 $v$ 油量时可以走通，那么可以有转移 $f[j][t]=\min(f[i][t] dis,f[i][t])$ 否则必须先加油到 $i$

这里可以使用一个分层图最短路来做，第 $i$ 层代表油量为 $i$ 能走的边的子图。 $\min(dis[i][n] i)$ 即为最后的答案。

#include<bits/stdc++.h>

using namespace std;

const int maxn=310*210;

int dis[maxn],n,m,mino[3200],vis[maxn],ans;
// int mp[maxn][maxn]; 
int Omax; //最大油量
vector <pair<int,int>> G[310*210];
vector <tuple<int,int,int>> E;//存储初始权值

int nodeindex(int x,int w) //分层第w层的点编号
{
    return x+(w-1)*n;
}

void addedge(int x,int y,int dis,int f) //f=1 单向边 f=2 双向边
{
    G[x].push_back({y,dis});
    if(f==2) G[y].push_back({x,dis});
}  

void dijkstra(int st)
{
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pair<int,int> > q;
    q.push({0,st});
    dis[st]=0;
    while(!q.empty())
    {
        int t=q.top().second;
        q.pop();
        if(vis[t]) continue;
        vis[t]=1;
        for(auto [u,k]:G[t])
        {
            if(dis[t]+k<dis[u])
            {
                dis[u]=dis[t]+k;
                q.push({-dis[u],u});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>Omax;
    for(int i=1,x,y,z;i<=m;i++)
    {
        cin>>x>>y>>z;
        E.push_back({x,y,z});
        // mp[x][y]=mp[y][x]=z;
    }
    for(int o=Omax,cnt=0;o;o--,cnt=0)
    for(auto [x,y,z]:E)
    {
        cnt++;
        //由于没有边权为0的边 因此从1开始
        if((1+(o/Omax))*z<=o)
        {
            if(o==1)
            {
                int xxx=1;
            }
            addedge(nodeindex(x,o),nodeindex(y,o),(1+(o/Omax))*z,2);
            mino[cnt]=o; //记录如果想走通这一条路至少需要加多少油
        }
        else
        {
            if(!mino[cnt]) continue;
            //否则想要过去，就必须跨层。
            addedge(nodeindex(x,o),nodeindex(y,mino[cnt]),(1+(mino[cnt]/Omax))*z,1);
            addedge(nodeindex(y,o),nodeindex(x,mino[cnt]),(1+(mino[cnt]/Omax))*z,1);
        }
    }
    dijkstra(1);
    ans=0x3f3f3f3f;
    for(int i=1;i<=Omax;i++)
    {
        ans=min(ans,dis[nodeindex(n,i)]+i);
    }
    cout<<ans<<'\n';
}

/*
3 2 100
1 2 10
2 3 1
*/

第四场比赛题解

前言

COOL

30pts

100pts

food

30pts

50pts

100pts

latex

表达式计算

高精度计算

driver

20pts

40pts

50pts

100pts