暑期集训第十四天（7-5）题解及总结

小总结：

昨天晚上调一道题题解总结又咕咕了......(虽然我也知道没几个人看)。

但是还是要补的，毕竟我想留下完整的第一次集训的一些东西qwq.....

昨天我考的是我集训以来最差的一次,险些都要掉到20开外了......结果一天都感觉用不上力气,一道绿题让lc帮我调了将近一个小时......

T1:食物链

 刚刚看到这道题还以为是之前考过的一道并查集的题目,但是读完题目之后才知道完全不一样......

做这道题之前我们要知道食物链的概念是一条链,不是一个环,于是我们考虑建好图之后从入度为0的点出发进行dfs,每到达一个出度为0的点之后就记一次答案,但是题目中有提到单单一个点不是一条食物链,但是我但是考虑过度了...明明我的dfs不用考虑但是之后我还是去了一次这些点,结果70->20。之后会T，想要拿到满分需要记忆化优化

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,m;
struct Node{
    int next,to;
}edge[N];
int Head[N],tot;
void Add(int x,int y){
    edge[++tot].to=y;
    edge[tot].next=Head[x];
    Head[x]=tot;
}
int dp[N],ru[N],chu[N],ans;
int dfs(int u){
    if(dp[u]) return dp[u];
    int ans=0;
    if(!chu[u]&&ru[u]) ans++;
    for(int i=Head[u];i;i=edge[i].next){
        int v=edge[i].to;
        ans+=dfs(v);
    }
    dp[u]=ans;
    return ans;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%lld%lld",&x,&y);
        Add(x,y);
        chu[x]++;ru[y]++;
    }
    for(int i=1;i<=n;++i){
        if(!ru[i]){
            ans+=dfs(i);
        }
    }
    printf("%lld
",ans);
    return 0;
}

T2：升降梯上

（鬼知道这是一道最短路呀）

最初我看到这道题的时候想到的是dp，当然我也写出来了，定义dp[i][j]表示当前在i层,上一次扳到j时的时间花费,但是时间效率是n^2*m^2的,T到了只剩下50pts.......

正解是最短路,把某一层的某一个扳的位置映射在一条直线上,i层第j个的位置为i*m+j,之后把每层可以扳到的位置建一条以时间为长度的边,之后把该层可以跳到的层之间进行连一条以时间为长度的边,最后从起始的点找一条到i层某一状态的最短路就可以了,千万注意边不要连到1~n之外.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct Node{
    int next,to,dis;
}edge[N];
int a[N],Head[N],tot,m,n;
void Add(int x,int y,int z){
    edge[++tot].to=y;
    edge[tot].dis=z;
    edge[tot].next=Head[x];
    Head[x]=tot;
}
int dis[N],vis[N],begin;
struct Edge{
    int num,dis;
    Edge(int x,int y){
        num=x;dis=y;
    }
    bool operator < (const Edge &a)const{
        return a.dis<dis;
    }
};
priority_queue<Edge>q;
void dijkstra(int x){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[x]=0;q.push(Edge(x,0));
    while(!q.empty()){
        int u=q.top().num;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=Head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].dis){
                dis[v]=dis[u]+edge[i].dis;
                q.push(Edge(v,dis[v]));
            }
        }
    }
}
int change(int x,int j){
    return x*m+j;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i]);
        if(a[i]==0){
            begin=change(1,i);
        }
    }
    for(int i=1;i<n;++i)
        for(int j=1;j<=m;++j){
            if(i+a[j]>0&&i+a[j]<=n&&a[j]!=0){
                Add(change(i,j),change(i+a[j],j),2*abs(a[j]));
            }
            for(int k=1;k<=m;++k){
                if(k!=j){
                    Add(change(i,j),change(i,k),abs(k-j));
                }
            }
        }
    dijkstra(begin);
    int ans=2147483647;
    for(int i=1;i<=m;++i) ans=min(ans,dis[change(n,i)]);
    if(ans!=0x3f3f3f3f) printf("%d
",ans);
    else printf("-1
");
    return 0;
}

T3:Password

 前天虎哥说会有一道数论的题目,还重点提了一下拓展欧几里德,我其他的几乎没怎么看,谁知道老师考了一道矩阵乘法和欧拉定理的题目......

考虑题目要求的答案是p^fibo(p)%q的答案,既然p是质数,q还小于p,于是p,q一定互质,我们根据欧拉定理可以知道p^φ(q)≡1(mol q),于是我们可以把fibo(p)拆为x*φ(q)+t,前面的φ(q)次方都是一,对答案没有贡献,直接减去,最后我们只需要求出p^t % q的值就可以了,减去φ(q)的过程我们可以用矩阵乘法求fibo函数的过程中对该数取模,在得到t之后进行一个倍增快速幂就可以了,注意取模的个数,%的太多也不好,会T掉,之后找gyz大佬才调好......

#include<bits/stdc++.h>
#define debug printf("-debug-
")
#define int long long
using namespace std;
const int N=5e6+10;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct squ{
    int a[3][3];
};
int Mod;
squ multiply(squ a,squ b){
    squ ans;
    memset(ans.a,0,sizeof(ans.a));
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            for(int k=1;k<=2;++k){
                ans.a[i][j]=(ans.a[i][j]%Mod+a.a[i][k]*b.a[k][j]%Mod)%Mod;
            }
    return ans;
}
void cal(squ &a,squ b,int cnt){
    while(cnt){
        if(cnt & 1){
            a=multiply(a,b);
        }
        cnt>>=1;b=multiply(b,b);
    }
}
squ fibo,origin;
int getphi(int x){
    int ans=x;
    for(int i=2;i<=sqrt(x+0.5);++i){
        if(x%i==0){
            ans=ans/i*(i-1);while(x%i==0) x/=i;
        }
        
    }
    if(x!=1) ans=ans/x*(x-1);
    return ans;
}
int Pow(int x,int cnt,int M){
    int ans=1;
    while(cnt){
        if(cnt & 1) ans=ans*x%M;
        cnt>>=1;x=x*x%M;
    }
    return ans%M;
}
signed main(){
    int T=read(),p=read();
    while(T--){
        origin.a[1][1]=1;origin.a[1][2]=1;
        origin.a[2][1]=1;origin.a[2][2]=0;
        fibo.a[1][1]=fibo.a[1][2]=1;
        fibo.a[2][1]=fibo.a[2][2]=0;
        int x=read(),y=read();
        Mod=getphi(y);
        if(x>2)
            cal(fibo,origin,x-2);
        //printf("%d
",fibo.a[1][1]);
        printf("%lld
",Pow(p,fibo.a[1][1],y));
    }
    return 0;
}

T4:子串

 考场上没能想出正解的思路......看数据范围打了一个30的基础分就没有再看了......

这道题卡内存,于是我们在定义好状态之后要考虑优化,定义dp[i][j][k][p]表示a串的第i个位置为止使用k个子串匹配b串前j位字符的状态,最后一维表示当前状态该数选不选,如果当前我们不选这位数字,那么存在转移dp[i][j][k][0]=dp[i-1][j][k][1]+dp[i-1][j][k][0],因为既然前面不选,当前的状态就与前面无关了,于是都加上,如果要选,要分情况讨论,如果a[i]==b[j],那么dp[i][j][k][1]=dp[i-1][j-1][k][1](在上一位基础上续上)+dp[i-1][j-1][k-1][0](前面断了,这是第k段的开端)+dp[i-1][j-1][k-1][1](令起炉灶不管前面自成一段),如果a[i]!=a[j],由于我们选不了,dp[i][j][k][1]就是0啦.我们注意到当前转移只与上一位有关系,于是可以用滚动数组压掉一位,之后要注意每次跑完一位要清空另一位,因为滚动的话我们之前的计算结果不清空可能会对之后的结果造成影响.这样就解决了.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char a[2001],b[201];
int n,m,t,f[2][201][201][2],s,k;
const int Mod=1000000007;
int main(){
    scanf("%d%d%d",&n,&m,&t);
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=n;++i){
        k=!k;
        f[k][1][1][0]=s;
        if(a[i]==b[1]){
            f[k][1][1][1]=1;s++;
        }
        for(int j=2;j<=m;++j)
            for(int p=1;p<=t;++p){
                if(a[i]==b[j])
                    f[k][j][p][1]=((f[!k][j-1][p-1][1]+f[!k][j-1][p][1])%Mod+f[!k][j-1][p-1][0])%Mod;
                f[k][j][p][0]=(f[!k][j][p][0]+f[!k][j][p][1])%Mod;
            }
        for(int j=1;j<=m;++j)
            for(int p=1;p<=t;++p)
                f[!k][j][p][1]=f[!k][j][p][0]=0;
            
    }
    printf("%d
",(f[k][m][t][1]+f[k][m][t][0])%Mod);
    return 0;
}

一道单调队列的基础题目

 昨天(或是前天???)的模拟赛之中的第一题被longdie的大佬的单调队列优化的n^2dp给碾压了,而我这一块并不是十分的熟练,于是找了一道接近板子的题目......

考虑维护r-l+1之中可以转移到一个位置的长度里面的最大值,既然要求最大值,重点又确定(指定某一位置),这样做当然不会更差,在维护到结尾之后对可以跳出去的位置统计一下就可以了.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,l,r,ans=-2147483647,val[N],dp[N];
deque<int>q;
int main(){
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;++i) scanf("%d",&val[i]);
    memset(dp,128,sizeof(dp));dp[0]=0;
    for(int i=l;i<=n;++i){
        while(!q.empty() && dp[i-l]>=dp[q.back()]) q.pop_back();
        while(!q.empty() && i-q.front()>r) q.pop_front();
        q.push_back(i-l);
        dp[i]=dp[q.front()]+val[i];
    }
    for(int i=n+1-r;i<=n;++i) ans=max(ans,dp[i]);
    printf("%d
",ans);
}

一道区间dp的基础题目

 这道题最初想复杂了,lc大佬也A的很懵,于是我们就从8点多到九点一直在调我的垃圾代码......

如果a[i]==a[j],我们有dp[i][j]=min(dp[i][j],min(dp[i+1][j],dp[i][j-1]));这道题的精华就在这个式子之上了,如果a[i]==a[j],那么我们可以从相邻的两个状态进行转移,因为既然两个边界相等,那么我们可以在原来基础上把i到j都先刷上同一种颜色,这样就不用在费一次的刷子次数了,之后再套上一个区间dp的板子格式,把上面的式子嵌入其中就可以了.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char a[N];
int dp[100][100];
int vis[51][51][100];
int main(){
    scanf(" %s",a+1);
    int len=strlen(a+1);
    for(int i=1;i<=len;++i) dp[i][i]=1;
    for(int i=1;i<=len;++i)
        for(int j=i+1;j<=len;++j)
            dp[i][j]=0x3f3f3f3f;
    for(int d=2;d<=len;++d)
        for(int i=1,j;(j=i+d-1)<=len;++i){
            if(a[i]==a[j]) dp[i][j]=min(dp[i][j],min(dp[i+1][j],dp[i][j-1]));
            for(int k=i;k<j;++k){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
            //printf("%d %d %d
",i,j,dp[i][j]);
        }
    printf("%d
",dp[1][len]);//dedcecbcd  5
    //dbdcd 3
    return 0;
}

总结:

今天(或者说是昨天)可能随着集训的进行状态有些下滑,于是我的成绩对我进行了警告处分......

晚上吃完饭后又被文化课的班主任拉了去打扫高考教室,班主任一边在旁边开班会,好像是期末动员???(反正我不用参加qwq)

现在我对于学校考试的感觉是虎哥出题没思路,老姚出题调不出,老姚虎哥相结合,明天爆零不是梦

过几天就要高考了,祝愿高三学长们和我都能取得一个好成绩吧.