9-25NOIP模拟赛总结

T1

开始写了个错误的贪心，发现正解就是个爆搜，回溯次数很少

T2

第二题是一个模拟题，只需要分开算每一位的贡献就好了。

T3

暴力，学习了SPFA的slf优化，就A了，slf优化就是双端队列优化，这样可以大大减小SPFA的增广次数。

void SPFA()
{
    deque<int>q;
    q.push_back(1);
    mem(vis,0);
    REP(i,1,n)dis[i] = inf;
    dis[1] = 0; 
    while(!q.empty())
    {
        int x = q.front();q.pop_front();vis[x] = 0;
        for(int i = be[x]; i; i = ne[i])
        {
            int v = to[i];
            if(dis[v] > dis[x] + w[i])
            {
                dis[v] = dis[x] + w[i];
                if(!vis[v])
                {
                    vis[v] = 1;
                    if(q.empty() || dis[v] > dis[q.front()])q.push_back(v);
                    else q.push_front(v);
                }
            }
        }
    }
}

经验与总结

人要有梦想，能优化的还是要尽量优化。