牛牛排队 题解

根据题目意思模拟，取掏手机打开健康码和排队的时间的较大值。

最终答案为 。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
void solve(){
    ll x,y,a,b,c;
    scanf("%lld%lld%lld%lld%lld",&x,&y,&a,&b,&c);
    printf("%lld\n",max(x*y,a+b)+c);
}
int main(){
    int t;scanf("%d",&t);
    while(t--)solve();
}

斗地主 题解

​ 由于这一回合选什么牌对之后回合选牌并没有影响，所以我们可以考虑使用 来解决问题。

​ 我们设计这么一种状态 表示前 回合，选的牌分值是 的方案数。

​ 那么枚举这一回合的牌，转移式就是：
​ 关于答案的统计，我们发现 的值域很小，所以暴力统计的复杂度为。

#include<bits/stdc++.h>
using namespace std;
#define P 1000000007
#define M 105
int n,m,k,a[M],dp[M][M];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i)scanf("%d",&a[i]);
    dp[0][0]=1;
    for(int i=0;i<n;++i){
        for(int j=0;j<k;++j)
            for(int l=1;l<=m;++l){
                dp[i+1][(j+a[l])%k]=(dp[i+1][(j+a[l])%k]+dp[i][j])%P;
            }
    }
    int ans=0;
    for(int i=0;i<k;++i){
        int tp=i,f=0;
        while(tp){
            if(tp%10==9||tp%10==7)f=1;
            tp/=10;
        }
        if(f)ans=(ans+dp[n][i])%P;
    }printf("%d",ans);
}

点权 题解

题解提供两种写法，先讲贪心写法。

这虽然是一个树上的题目，但是在图上它也同样可以写。

因为这实质上是最短路模型。

与一般最短路不同的是，这题一个点要从两个点转移过来。

我们假设的答案是从转移过来的，为号结点点权变为2的答案。

那么有，若的度数小于,则,,其中表示对应两条边的边权。

由于边权非负，那么我们有

所以我们开一个堆，把所有的叶子都丢进去，然后不断拿出堆中答案最小的点去更新它相邻的点。

复杂度和迪杰斯特拉一样都是的

#include<bits/stdc++.h>
using namespace std;
#define M 100005
struct hh{
    int p,w;
    bool operator<(hh x)const{
        return w>x.w;
    }
};
vector<hh>d[M];
int n;
int mi1[M],mi2[M],ans[M],deg[M];
priority_queue<hh>q;
void merge(int x,int w){
    if(w<mi1[x])mi2[x]=mi1[x],mi1[x]=w;
    else if(w<mi2[x])mi2[x]=w;
}
int main(){
    scanf("%d",&n);
    for(int i=1,u,v,w;i<n;++i){
        scanf("%d%d%d",&u,&v,&w);
        d[u].push_back((hh){v,w});
        d[v].push_back((hh){u,w});
        deg[u]++;deg[v]++;
    }
    memset(mi1,63,sizeof(mi1));memset(mi2,63,sizeof(mi2));memset(ans,63,sizeof(ans));
    for(int i=1;i<=n;++i)if(deg[i]<=1)q.push((hh){i,0}),ans[i]=mi1[i]=mi2[i]=0;
    while(!q.empty()){
        int p=q.top().p,w=q.top().w;q.pop();
        if(w>ans[p])continue;
        for(int i=0;i<(int)d[p].size();++i){
            int v=d[p][i].p;
            merge(v,w+d[p][i].w);
            if(mi1[v]+mi2[v]<ans[v])ans[v]=mi1[v]+mi2[v],q.push((hh){v,ans[v]});
        }
    }
    for(int i=1;i<=n;++i)if(ans[i]>1e9)ans[i]=-1;
    for(int i=1;i<=n;++i)printf("%d ",ans[i]);
}

换根DP写法：

对于一个点，如果只考虑子树的情况，那么它的答案一定是从最小的两个儿子转移过来的。

然后需要解决的就是，一个点可能从父亲转移过来，那么我们先把每个点只考虑子树内的答案跑出来，然后用换根DP求父亲的贡献。

两遍dfs，第一遍求出每个点从子孙转移来、使得点权 的前三小消耗；第二遍求出从祖先转移来，使得点权的最小消耗

最后对于每一个点选择两个消耗最小的，就是答案

#include<bits/stdc++.h>
using namespace std;
#define M 100005
#define ckmi(a,b) ((a>b)&&(a=b))
struct hh{
    int p,w;
};
vector<hh>d[M];
int dp[M],mx1[M],mx2[M],mx3[M],inf=(1e9)+100000,ans[M];
void merge(int x,int t){
    if(t<mx1[x])mx3[x]=mx2[x],mx2[x]=mx1[x],mx1[x]=t;
    else if(t<mx2[x])mx3[x]=mx2[x],mx2[x]=t;
    else if(t<mx3[x])mx3[x]=t;
}
void dfs(int x,int f){
    dp[x]=inf;mx1[x]=inf;mx2[x]=inf;mx3[x]=inf;
    if(d[x].size()<=1)dp[x]=0;
    for(int i=0;i<(int)d[x].size();++i){
        int v=d[x][i].p;
        if(v==f)continue;
        dfs(v,x);
        merge(x,dp[v]+d[x][i].w);//这里维护出前三小的叶子
    }
    ckmi(dp[x],mx1[x]+mx2[x]);//只考虑子树内的答案。
}
void Dfs(int x,int f){
    ans[x]=dp[x];ckmi(ans[x],mx1[x]+mx2[x]);
    for(int i=0;i<(int)d[x].size();++i){
        int v=d[x][i].p;
        if(v==f)continue;
        int t=dp[x];dp[x]=inf;//这是当x失去v这个儿子时的DP值
        if(d[x].size()<=1)dp[x]=0;//父亲可能是叶子
        int s=dp[v]+d[x][i].w;
        if(s==mx1[x])ckmi(dp[x],mx2[x]+mx3[x]);
        else if(s==mx2[x])ckmi(dp[x],mx1[x]+mx3[x]);
        else ckmi(dp[x],mx1[x]+mx2[x]);//这是把父亲换到儿子的位置
        merge(v,dp[x]+d[x][i].w);//合并
        Dfs(v,x);dp[x]=t;
    }
}
void rd(int &x){
    x=0;int c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
}
int main(){
    int n;rd(n);
    for(int i=1,u,v,w;i<n;++i){
        rd(u);rd(v);rd(w);
        d[u].push_back((hh){v,w});
        d[v].push_back((hh){u,w});
    }
    dfs(1,0);ans[1]=dp[1];Dfs(1,0);
    for(int i=1;i<=n;++i)if(ans[i]==inf)ans[i]=-1;
    for(int i=1;i<=n;++i)printf("%d ",ans[i]);
}

牛牛玩 generals 题解

1. 操作：由于每头牛扩展的时候留下的兵是相同的，所以我们用set维护所有兵力相同的区间。

   扩展时消耗的兵力就是 。

   直接在 set 中遍历这些区间统计区间和。如果某个区间的一部分在 中，将其拆成两段即可。

   而每次操作，除了两边的两个区间，中间被包含的区间访问后就会被删去。

   每次操作只额外增加个区间，在整个过程中的区间总数为。

   所以对区间的操作总数是的。

   在std::set上加入、删除和分裂一个区间复杂度为，因此操作的总复杂度为。

   然后考虑占领了某一个人的家的情况，我们可以使用并查集来维护某一个区间当前是属于谁的，

   当一个牛的表明它的家没有被占领，如果被占领了，那么我们令。

   所以对于每一次操作，我们每次可以把所有家被占领的牛给存下来，然后把他们的全部指向

   这样我们就可以使用并查集查询一个区间属于谁。

2. 操作：在操作时同步修改每头牛的兵力即可查询。

总时间复杂度为 。

有部分选手可能写的较为复杂，std给出一种较为简洁的实现方式。

#include<bits/stdc++.h>
using namespace std;
#define M 100005
int mk[M];
struct hh{
    int l,r,w,p;//l,r表示区间的两个端点，w表示这段区间的兵力，我们存在set中的一段区间的兵力全部相同，p表示区间属于谁
    bool operator<(hh x)const{
        return l<x.l;
    }
};
set<hh>q;
set<hh>::iterator it;
int ans[M],a[M],fa[M],sk[M];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);//并查集维护当前区间属于谁
}
int main(){
    int n,m,t;
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        mk[a[i]]=i;fa[i]=i;
    }
    for(int i=1;i<=m;++i)q.insert((hh){i,i,0,mk[i]});//刚开始将所有区间***去，无主的格子就当属于0
    while(t--){
        int f;
        scanf("%d",&f);
        if(f==1){
            int x,l,r,p,cnt=0;
            scanf("%d%d%d%d",&x,&l,&r,&p);
            it=q.upper_bound((hh){r,0,0,0});
            int ans1=(r-l+1)*p,ans2=0,ans3=0;//ans1表示这段区间总兵力，ans2表示这段区间中自己的兵力，ans3表示别人的兵力
            --it;//找到左端点<=r的左后一个区间
            while(1){
                int l1=it->l,r1=it->r,w1=it->w,p1=it->p;
                if(r1<l)break;
                --it;//迭代器需要先把元素取出来再删除，否则会出事情
                q.erase((hh){l1,r1,w1,p1});
                p1=find(p1);//求出这个区间属于谁
                int l2=max(l1,l),r2=min(r1,r);//求区间交集
                if(p1==x)ans2+=w1*(r2-l2+1);//属于自己
                else{
                    ans3+=w1*(r2-l2+1);//属于别人
                    ans[p1]-=w1*(r2-l2+1);
                    if(l2<=a[p1]&&r2>=a[p1])sk[++cnt]=p1;//把家被占领的存下来
                }
                if(l1<l)q.insert((hh){l1,l-1,w1,p1});//裂出左边部分
                if(r1>r)q.insert((hh){r+1,r1,w1,p1});//裂出右边部分
            }
            q.insert((hh){l,r,p,x});//插回去
            ans[x]+=ans1-ans2;
            printf("%d\n",ans1-ans2+ans3);
            for(int i=1;i<=cnt;++i)fa[sk[i]]=x,ans[x]+=ans[sk[i]];//更新并查集
        }
        else{
            int x;
            scanf("%d",&x);
            printf("%d\n",ans[x]);
        }
    }
    for(int i=1;i<=n;++i)if(fa[i]==i)printf("%d\n",i);
}

牛牛选路径

约定：称度数为奇数的点为奇点，称度数为偶数的点为偶点。

贪心策略：

对于每一个连通块，考虑以下两种情况：

1. 如果不存在奇点，则选择点权最小的点作为头尾连接一条路径。

2. 存在奇点，则必然有偶数个奇点，只需要选出这些奇点之间的最优匹配，

   而这个最优匹配就是：排序之后不断取最小值和最大值匹配。

证明：

1. 没有奇点时，可以直接提取一条欧拉回路。

2. 存在奇点时，对于任何一个合法的匹配，均存在方案，使得以匹配为头尾的链组，将每条边覆盖奇数次。

   下面给出了一个合法的构造：

   1. 设匹配点集合为，在之间连接一条虚边，记为，得到新图。

      容易在原图上找到某一条之间的路径，记作。

   2. 在上求一个欧拉回路，

      此时容易通过将替换为的操作将虚边实化，称实化的路径为额外路径，记实化的环为。

   3. 对于每一个，其对应的路径为删除这一段，容易发现路径的头尾是对应的。

      此时，上的额外路径均比其他路径少被遍历了恰好一次（因为在其对应的这里被删除了）。

   4. 如果上的非额外路径被遍历了偶数次，则在某一条路径中，额外增加一段绕过一整个的段。

   这样就保证了上的非额外路径被遍历了奇数次；而额外路径被遍历了偶数次，不产生贡献；

   而上的非额外路径就对应了原图的所有边，故构造合法。

3. 匹配的最优性：

   设排序之后的奇点点权为，容易由排序不等式得到证明：

   1. 如果有一个匹配，满足，那么就必然存在一个匹配满足。

      由二元排序不等式，此时交换总更优。

   2. 排除的情况后，此时问题变成了对于每个，匹配一个。

      那么可以直接分成两个集合，由多元排序不等式得到最优解。

#include<bits/stdc++.h>
using namespace std;
#define M 100005
#define P 998244353 
int n,m,a[M],deg[M],sk[M];
vector<int>d[M];
bool cmp(int x,int y){
    return a[x]<a[y];    
}
int main(){
    int mx=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1,x,y;i<=m;++i){
        scanf("%d%d",&x,&y);
        d[x].push_back(y);
        d[y].push_back(x);
        deg[x]^=1;deg[y]^=1;
    }
    int cnt=0,ans=0;
    for(int i=1;i<=n;++i)if(deg[i])sk[++cnt]=i;
    if(cnt==0){
        ans=1e9;
        for(int i=1;i<=n;++i)ans=min(ans,a[i]*a[i]);
    }else{
        sort(sk+1,sk+cnt+1,cmp);
        for(int i=1;i<=cnt/2;++i)ans+=a[sk[i]]*a[sk[cnt-i+1]];
    }
    printf("%d",ans%P);
}

作文 题解

令为题中的重要串，为的长度，显然我们需要维护写出的字符串与的匹配。

考虑用 来求解该题。令 表示已经匹配到 的第 位时，在结束前匹配整个串的概率。由于 在第一次出现以后，就无需考虑后继的情况，那么边界条件就是 ，答案就是 。

考虑状态接上句子的转移，设这个后继状态为：

1. 如果在接上句子的中途就出现了串整串，则；

2. 否则，令 就是接上 这个句子后，与 串匹配的长度。

则对于每个，可以从其所有后继状态中得到转移：

其中为这一轮结束的概率。

预处理

可以考虑用（自动机）维护，枚举串，依次接上每一位。

令表示出现的句子的总长，则暴力的复杂度为 （因为在新接上串时，还要考虑前个字符的失配）；

而用自动机维护的复杂度为。

求解

对以上提到的转移，容易发现每个的后继构成的转移关系不具有拓扑序，即实际的转移可能是这种循环形式：
此时可以看成是以为元的 元线性方程组，可以使用高斯消元进行求解，复杂度为。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) f|=IO=='-';
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

bool Mbe;
const int N=210,INF=1e9+10,P=1e9+7;

int n,m;
char s[N];
char t[1010][N];
int G[N][N],nxt[N][26],fail[N];
ll qpow(ll x,ll k=P-2) {
    ll res=1;
    for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
    return res;
}

bool Med;
int main(){ 
    m=rd();
    rep(i,1,m) scanf("%s",t[i]+1);
    scanf("%s",s+1),n=strlen(s+1);
    rep(i,1,n) nxt[i-1][s[i]-'a']=i;
    rep(i,1,n) {
        rep(j,0,25) if(nxt[i][j]) fail[nxt[i][j]]=nxt[fail[i]][j];
        else nxt[i][j]=nxt[fail[i]][j];
    }
    rep(i,0,n-1) {
        rep(j,1,m) {
            int p=i;
            for(int k=1;t[j][k] && p!=n;++k) p=nxt[p][t[j][k]-'a'];
            G[i][p]++;
        }
    }
    rep(i,0,n-1) G[i][i]-=m+1,Mod2(G[i][i]);
    G[n][n]=G[n][n+1]=1;
    rep(i,0,n) {
        if(!G[i][i]){ 
            rep(j,i+1,n) if(G[j][i]) {
                swap(G[i],G[j]);
                break;
            }
        }
        assert(G[i][i]);
        ll inv=qpow(G[i][i]);
        rep(j,i,n+1) G[i][j]=G[i][j]*inv%P;
        rep(j,0,n) if(i!=j) drep(k,n+1,i) G[j][k]=(G[j][k]+1ll*(P-G[j][i])*G[i][k])%P;
    }
    printf("%d\n",G[0][n+1]);
}