E-AC Challenge

这道题lx说是很简单的状压dp，然后分分钟过了，而我却感觉很难T_T，然后lx还推荐我做一做这道题：最小总代价

这题有一个要判断合不合法的vis数组，我之前没用这个数组也过了，但是这可能是数据太水了，而我的 −∞ $-\infty$ 开的是 −1e15 $-1e15$ 所以才阔以过，要是初值设为 0 $0$ 就过不了，而加上这个vis数组就能过，所以他这个才是正解~~~

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1<<21;
const int MOD=1e9+7;
LL dp[maxn];//dp[i]表示i的二进制中做这些题的最大值 
int flag[25],a[25],b[25];
bool vis[maxn];//表示这种状态是不是合法的 
int main()
{
    int N;
    while(cin>>N)
    {
        for(int i=1;i<=N;i++)
        {
            cin>>a[i]>>b[i];
            int M,t=0;
            cin>>M;
            for(int j=1;j<=M;j++)
            {
                int k;
                cin>>k;
                t|=(1<<(k-1));
            }
            flag[i]=t;
        }
        memset(vis,0,sizeof vis);
        for(int sta=1;sta<(1<<N);sta++)dp[sta]=0;//如果不想用vis来判断状态合法不合法，就要把这里设置成-inf,负得越多越好 
        dp[0]=0;
        vis[0]=1;                                //表示0这个状态是合法的 
        LL ans=0;
        for(int sta=0;sta<(1<<N);sta++)
        {
            if(vis[sta]==0)continue;                            //不合法的状态直接就跳过 
            for(int k=1;k<=N;k++)                               //看当前状态下每个问题能不能做 
            {
                if((sta&(1<<(k-1)))==(1<<(k-1)))continue;       //说明这个问题已经做过了 
                if((sta&flag[k])!=flag[k])continue;             //flag[k]有的，sta也要必须有 
                int now=sta|(1<<(k-1));
                int cnt=__builtin_popcount(now);                //库函数计算now中二进制1的个数 
                dp[now]=max(dp[now],(LL)a[k]*cnt+b[k]+dp[sta]);
                ans=max(ans,dp[now]);
                vis[now]=1;                                     //然后这个状态就是合法的了 
            }
        }
        cout<<ans<<endl;
    }
} 

J-Sum

题目链接：https://nanti.jisuanke.com/t/30999
这道题lzj和pwm的都超时了，但是对的，我的又WA了，我感觉我的复杂度应该阔以，然后就想做出来，然后他们两个就帮我“人工手动二分找bugT_T”，最后找了几次bug才过。。。

完了之后我发现我的代码其实还有好多是没有用的。。。然后总结了一哈，应该没什么冗余的了

刚刚逛知乎，出题人好像说本来想出 1e10 $1e10$ 的，还说 1e10 $1e10$ 也挺签到的T_T
这是知乎上的题解，我把Latex复制过来了（没看懂）： f(n)=∑ij≤nμ2(i)μ2(j) $f\left(n\right)=\sum _{ij\le n}{\mu }^2\left(i\right){\mu }^2\left(j\right)$，分 O(n1/2) $O\left(n^{1/2}\right)$ 段枚举 i $i$，需要计算一系列 g(⌊n/k⌋) $g(\lfloor n/k\rfloor )$ 的值，这里 g(n)=∑ni=1μ2(i)=∑⌊n√⌋i=1μ(i)⌊n/i2⌋ $g\left(n\right)=\sum _{i=1}^n{\mu }^2\left(i\right)=\sum _{i=1}^{\lfloor \sqrt{n}\rfloor }\mu \left(i\right)\lfloor n/i^2\rfloor$，分 O(n1/3) $O\left(n^{1/3}\right)$ 段枚举 i $i$ 进行计算，需要 O(n1/2) $O\left(n^{1/2}\right)$ 预处理 μ $\mu$ 的前缀和，总复杂度可以分析出是 O(n2/3) $O\left(n^{2/3}\right)$

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=2e7+5;
const int MOD=1e9+7;
int a[maxn];
bool vis[maxn];
vector<int>prime;
int sum[maxn];
void PHI(int n)
{
    memset(vis,1,sizeof(vis));
    a[1]=sum[1]=1;
    for(LL i=2;i<=n;i++)
    {
        if(vis[i])
        {
            prime.push_back(i);
            a[i]=2;             //如果是质数就是2 
            if(i*i<=n)a[i*i]=1;//如果是质数的平方就是1 
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)
            {
                int tp=i/prime[j];
                if(tp%prime[j]==0)a[i*prime[j]]=0;//如果一种质因子含有两个以上，那么就是0，比如2^3*3*5*7 
                else a[i*prime[j]]=a[tp];         //不然就是除掉这种质因子的值,比如2^2*3*5*7的值就是3*5*7的值 
                break;
            }
            else//每种质因子只有一个，那就是2^n 
            {
                a[i*prime[j]]=a[i]<<1;//又来了一种质因子，就乘2 
            }
        }
        sum[i]=sum[i-1]+a[i];
    }
}
int main()
{
    PHI(maxn-3);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int N;
        scanf("%d",&N);
        printf("%d\n",sum[N]);
    }
}

G-Lpl and Energy-saving Lamps

题目链接：https://nanti.jisuanke.com/t/30996
题意：有N个房间，每个房间都有旧灯泡，每个月都会给M个灯泡，然后从左到右去看每个房间够不够把所有旧灯泡都换了，每个月换完如果还有剩就放在下个月继续用，最后Q次询问，随便问一个月换了多少个房间，以及还剩多少个灯泡

懂了题意确实比较简单
因为询问是乱的，所以阔以把询问记录下来，然后就是怎样快速找到换的那间房间，换个说法就是怎样快速找到比当前剩的灯泡小的值，就是用线段树了啊~

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
const int inf=1e9;
int Min[maxn<<2];
int N,M,Now,ans;
int q1[maxn],q2[maxn];
void pushup(int id)
{
    Min[id]=min(Min[id<<1],Min[id<<1|1]);
}
void Build(int id,int L,int R)
{
    if(L==R)
    {
        int t;
        scanf("%d",&Min[id]);
        return ;
    }
    int mid=L+R>>1;
    Build(id<<1,L,mid);
    Build(id<<1|1,mid+1,R);
}
void Add(int id,int L,int R)
{
    if(Min[id]>Now)return ;
    if(L==R)
    {
        Now-=Min[id];
        Min[id]=inf;
        ans++;
        return ;
    }
    int mid=L+R>>1;
    Add(id<<1,L,mid);
    Add(id<<1|1,mid+1,R);
    pushup(id);
}
int main()
{
    while(cin>>N>>M)
    {
        Now=ans=0;
        Build(1,1,N);
        for(int i=1;i<=maxn-5;i++)
        {
            Now+=M;
            Add(1,1,N);
            q1[i]=ans;
            q2[i]=Now;
        }
        int Q;
        cin>>Q;
        while(Q--)
        {
            int t;
            scanf("%d",&t);
            cout<<q1[t]<<" "<<q2[t]<<endl;
        }
    }
}

L-Magical Girl Haze

题目链接：https://nanti.jisuanke.com/t/31001
题意：求 1 $1$ 到 N $N$ 的最短路，只不过阔以选 K $K$ 条路让他权值为 0 $0$
参考这位童鞋的博客：https://blog.csdn.net/axuhongbo/article/details/82289535

补这道题的时候看什么分层，没懂分层啥意思？？？然后问彭老板他懂了没，他给我说了后我才懂，还有这种操作？？？

就拿样例来说吧，我们先建个图就是第 0 $0$ 层蓝色的线，然后复制一个图放在第一层，怎么处理 K $K$ 条路的权值为 0 $0$ 喃？就在第 0 $0$ 层和第一层上对应的点上连一条权值为 0 $0$ 的边就行了，然后求 1 $1$到 N $N$ 的最短路就是求第 0 $0$ 层的 ① 号点到每一层的 ⑤ 号点中取最小的么~
我见得还是太少了，第一次看见这样的操作感觉好骚啊0.0

然后我就想怎么建图，哇，要10倍的点，20倍的边，而且建怎么建嘛，不好建，然后我就放弃了T_T

结果一看别人的代码，？？？，为什么就是建的普通的图啊？？？

建图的目标其实就是维护这个 dis[i] $dis\left[i\right]$ 这个数组，而每一层的图其实是一样的，每一次维护的时候都阔以用原来的图

所以最终是这样的：用 dis[i][k] $dis\left[i\right]\left[k\right]$ 表示起点到第 k $k$ 层的第 i $i$ 个点，然后每一次都先把本层的图先松弛出来，然后再考虑这一层和下一层之间权值为 0 $0$ 的边~

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
const int inf=1e9;
int N,M,K;
struct Edge
{
    int t,v,nxt;
    Edge(){}
    Edge(int t,int v):t(t),v(v){}
    bool operator<(const Edge a)const
    {
        return v>a.v;
    }
};
Edge E[maxn<<1];
int head[maxn];
int tot;
void AddEdge(int aa,int bb,int val)
{
    E[++tot].t=bb;
    E[tot].v=val;
    E[tot].nxt=head[aa];
    head[aa]=tot;
}
int dis[maxn][11];
void Dij(int st)
{
    for(int i=1;i<=N;i++)for(int k=0;k<=K;k++)dis[i][k]=inf;
    for(int k=0;k<=K;k++)dis[1][k]=0;
    priority_queue<Edge>que;
    que.push(Edge(st,0));
    while(!que.empty())
    {
        int u=que.top().t;
        que.pop();
        for(int i=head[u];i!=-1;i=E[i].nxt)
        {
            int t=E[i].t;
            int v=E[i].v;
            for(int k=0;k<=K;k++)
            {
                if(dis[u][k]+v<dis[t][k])//这一层先松弛 
                {
                    dis[t][k]=dis[u][k]+v;
                    que.push(Edge(t,dis[t][k]));
                }
                if(k==0)continue;//第0层没有下一层了 
                else if(dis[u][k-1]<dis[t][k])//然后这一层与下一层再松弛 
                {
                    dis[t][k]=dis[u][k-1];
                    que.push(Edge(t,dis[t][k]));
                }
            }
        }
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(head,-1,sizeof head);
        tot=0;
        cin>>N>>M>>K;
        for(int i=1;i<=M;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            AddEdge(u,v,w);
        }
        Dij(1);
        cout<<dis[N][K]<<endl; 
    }
}