昨天晚上调一道题题解总结又咕咕了......(虽然我也知道没几个人看)。
但是还是要补的，毕竟我想留下完整的第一次集训的一些东西qwq.....
昨天我考的是我集训以来最差的一次,险些都要掉到20开外了......结果一天都感觉用不上力气,一道绿题让lc帮我调了将近一个小时......
刚刚看到这道题还以为是之前考过的一道并查集的题目,但是读完题目之后才知道完全不一样......
做这道题之前我们要知道食物链的概念是一条链,不是一个环,于是我们考虑建好图之后从入度为0的点出发进行dfs,每到达一个出度为0的点之后就记一次答案,但是题目中有提到单单一个点不是一条食物链,但是我但是考虑过度了...明明我的dfs不用考虑但是之后我还是去了一次这些点,结果70->20。之后会T，想要拿到满分需要记忆化优化
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 const int N=1e6+10; 5 int n,m; 6 struct Node{ 7 int next,to; 8 }edge[N]; 9 int Head[N],tot; 10 void Add(int x,int y){ 11 edge[++tot].to=y; 12 edge[tot].next=Head[x]; 13 Head[x]=tot; 14 } 15 int dp[N],ru[N],chu[N],ans; 16 int dfs(int u){ 17 if(dp[u]) return dp[u]; 18 int ans=0; 19 if(!chu[u]&&ru[u]) ans++; 20 for(int i=Head[u];i;i=edge[i].next){ 21 int v=edge[i].to; 22 ans+=dfs(v); 23 } 24 dp[u]=ans; 25 return ans; 26 } 27 signed main(){ 28 scanf("%lld%lld",&n,&m); 29 for(int i=1;i<=m;++i){ 30 int x,y; 31 scanf("%lld%lld",&x,&y); 32 Add(x,y); 33 chu[x]++;ru[y]++; 34 } 35 for(int i=1;i<=n;++i){ 36 if(!ru[i]){ 37 ans+=dfs(i); 38 } 39 } 40 printf("%lld\n",ans); 41 return 0; 42 }
（鬼知道这是一道最短路呀）
最初我看到这道题的时候想到的是dp，当然我也写出来了，定义dp[i][j]表示当前在i层,上一次扳到j时的时间花费,但是时间效率是n^2*m^2的,T到了只剩下50pts.......
正解是最短路,把某一层的某一个扳的位置映射在一条直线上,i层第j个的位置为i*m+j,之后把每层可以扳到的位置建一条以时间为长度的边,之后把该层可以跳到的层之间进行连一条以时间为长度的边,最后从起始的点找一条到i层某一状态的最短路就可以了,千万注意边不要连到1~n之外.
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e6+10; 4 struct Node{ 5 int next,to,dis; 6 }edge[N]; 7 int a[N],Head[N],tot,m,n; 8 void Add(int x,int y,int z){ 9 edge[++tot].to=y; 10 edge[tot].dis=z; 11 edge[tot].next=Head[x]; 12 Head[x]=tot; 13 } 14 int dis[N],vis[N],begin; 15 struct Edge{ 16 int num,dis; 17 Edge(int x,int y){ 18 num=x;dis=y; 19 } 20 bool operator < (const Edge &a)const{ 21 return a.dis<dis; 22 } 23 }; 24 priority_queue<Edge>q; 25 void dijkstra(int x){ 26 memset(dis,0x3f,sizeof(dis)); 27 memset(vis,0,sizeof(vis)); 28 dis[x]=0;q.push(Edge(x,0)); 29 while(!q.empty()){ 30 int u=q.top().num;q.pop(); 31 if(vis[u]) continue; 32 vis[u]=1; 33 for(int i=Head[u];i;i=edge[i].next){ 34 int v=edge[i].to; 35 if(dis[v]>dis[u]+edge[i].dis){ 36 dis[v]=dis[u]+edge[i].dis; 37 q.push(Edge(v,dis[v])); 38 } 39 } 40 } 41 } 42 int change(int x,int j){ 43 return x*m+j; 44 } 45 int main(){ 46 scanf("%d%d",&n,&m); 47 for(int i=1;i<=m;++i){ 48 scanf("%d",&a[i]); 49 if(a[i]==0){ 50 begin=change(1,i); 51 } 52 } 53 for(int i=1;i<n;++i) 54 for(int j=1;j<=m;++j){ 55 if(i+a[j]>0&&i+a[j]<=n&&a[j]!=0){ 56 Add(change(i,j),change(i+a[j],j),2*abs(a[j])); 57 } 58 for(int k=1;k<=m;++k){ 59 if(k!=j){ 60 Add(change(i,j),change(i,k),abs(k-j)); 61 } 62 } 63 } 64 dijkstra(begin); 65 int ans=2147483647; 66 for(int i=1;i<=m;++i) ans=min(ans,dis[change(n,i)]); 67 if(ans!=0x3f3f3f3f) printf("%d\n",ans); 68 else printf("-1\n"); 69 return 0; 70 }
前天虎哥说会有一道数论的题目,还重点提了一下拓展欧几里德,我其他的几乎没怎么看,谁知道老师考了一道矩阵乘法和欧拉定理的题目......
考虑题目要求的答案是pfibo(p)%q的答案,既然p是质数,q还小于p,于是p,q一定互质,我们根据欧拉定理可以知道pφ(q)≡1(mol q),于是我们可以把fibo(p)拆为x*φ(q)+t,前面的φ(q)次方都是一,对答案没有贡献,直接减去,最后我们只需要求出pt % q的值就可以了,减去φ(q)的过程我们可以用矩阵乘法求fibo函数的过程中对该数取模,在得到t之后进行一个倍增快速幂就可以了,注意取模的个数,%的太多也不好,会T掉,之后找gyz大佬才调好......
1 #include<bits/stdc++.h> 2 #define debug printf("-debug-\n") 3 #define int long long 4 using namespace std; 5 const int N=5e6+10; 6 inline int read(){ 7 int x=0,f=1; 8 char ch=getchar(); 9 while(ch<‘0‘||ch>‘9‘){ 10 if(ch==‘-‘) 11 f=-1; 12 ch=getchar(); 13 } 14 while(ch>=‘0‘&&ch<=‘9‘){ 15 x=(x<<1)+(x<<3)+(ch^48); 16 ch=getchar(); 17 } 18 return x*f; 19 } 20 struct squ{ 21 int a[3][3]; 22 }; 23 int Mod; 24 squ multiply(squ a,squ b){ 25 squ ans; 26 memset(ans.a,0,sizeof(ans.a)); 27 for(int i=1;i<=2;++i) 28 for(int j=1;j<=2;++j) 29 for(int k=1;k<=2;++k){ 30 ans.a[i][j]=(ans.a[i][j]%Mod+a.a[i][k]*b.a[k][j]%Mod)%Mod; 31 } 32 return ans; 33 } 34 void cal(squ &a,squ b,int cnt){ 35 while(cnt){ 36 if(cnt & 1){ 37 a=multiply(a,b); 38 } 39 cnt>>=1;b=multiply(b,b); 40 } 41 } 42 squ fibo,origin; 43 int getphi(int x){ 44 int ans=x; 45 for(int i=2;i<=sqrt(x+0.5);++i){ 46 if(x%i==0){ 47 ans=ans/i*(i-1);while(x%i==0) x/=i; 48 } 49 50 } 51 if(x!=1) ans=ans/x*(x-1); 52 return ans; 53 } 54 int Pow(int x,int cnt,int M){ 55 int ans=1; 56 while(cnt){ 57 if(cnt & 1) ans=ans*x%M; 58 cnt>>=1;x=x*x%M; 59 } 60 return ans%M; 61 } 62 signed main(){ 63 int T=read(),p=read(); 64 while(T--){ 65 origin.a[1][1]=1;origin.a[1][2]=1; 66 origin.a[2][1]=1;origin.a[2][2]=0; 67 fibo.a[1][1]=fibo.a[1][2]=1; 68 fibo.a[2][1]=fibo.a[2][2]=0; 69 int x=read(),y=read(); 70 Mod=getphi(y); 71 if(x>2) 72 cal(fibo,origin,x-2); 73 //printf("%d\n",fibo.a[1][1]); 74 printf("%lld\n",Pow(p,fibo.a[1][1],y)); 75 } 76 return 0; 77 }
考场上没能想出正解的思路......看数据范围打了一个30的基础分就没有再看了......
这道题卡内存,于是我们在定义好状态之后要考虑优化,定义dp[i][j][k][p]表示a串的第i个位置为止使用k个子串匹配b串前j位字符的状态,最后一维表示当前状态该数选不选
原文：https://www.cnblogs.com/li-jia-hao/p/13255854.html