暑假集训day10

编程入门 行业动态 更新时间:2024-10-22 04:58:14

<a href=https://www.elefans.com/category/jswz/34/1766878.html style=暑假集训day10"/>

暑假集训day10

 其实这是两天前的,我们假设现在是7月10号。

今天主要学了矩阵快速幂滑动窗口

都比较容易实现

矩阵快速幂:方块(Blocks)poj3734

我们分为4中情况

分别为

a偶偶 a[n+1]=2b[n]+c[n]+d[n]

b奇奇 b[n+1]=2a[n]+c[n]+d[n]

c奇偶 c[n+1]=2c[n]+a[n]+b[n]

d偶奇 d[n+1]=2d[n]+a[n]+b[n]

知道了状态转移之后

可以通过初始的a[0]=1,b[0]=c[0]=d[0]=0推出结果

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct Mat{int p[4][4];
}ans,yzy;
const int mod=10007;
inline Mat operator *(const Mat a,const Mat b){Mat c;memset(c.p,0,sizeof(c.p));For(i,0,3)For(k,0,3)if(a.p[i][k])For(j,0,3)c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j])%mod;return c;
}
void init(){memset(ans.p,0,sizeof(ans.p));ans.p[0][0]=1;yzy.p[0][0]=2;yzy.p[1][0]=0;yzy.p[2][0]=1;yzy.p[3][0]=1;yzy.p[0][1]=0;yzy.p[1][1]=2;yzy.p[2][1]=1;yzy.p[3][1]=1;yzy.p[0][2]=1;yzy.p[1][2]=1;yzy.p[2][2]=2;yzy.p[3][2]=0;yzy.p[0][3]=1;yzy.p[1][3]=1;yzy.p[2][3]=0;yzy.p[3][3]=2;
}
void ksm(int n){while(n){if(n&1)ans=ans*yzy;yzy=yzy*yzy;n=n>>1;}printf("%d\n",ans.p[0][0]%mod);
}
int main()
{int T,n;scanf("%d",&T);For(i,1,T){scanf("%d",&n);init();ksm(n);}
}

 

Training little cats(poj_3735)

这题就是根据数据建矩阵,然后矩阵快速幂一下就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct Mat{long long p[101][101];
}ans,yzy;
int n,m,k;
inline Mat operator *(const Mat a,const Mat b){Mat c;memset(c.p,0,sizeof(c.p));For(i,0,n)For(l,0,n)if(a.p[i][l])For(j,0,n)c.p[i][j]+=a.p[i][l]*b.p[l][j];return c;
}
void init(){memset(ans.p,0,sizeof(ans.p));memset(yzy.p,0,sizeof(yzy.p));For(i,0,n)yzy.p[i][i]=1;For(i,0,n-1)ans.p[0][i]=0;ans.p[0][n]=1;For(i,1,k){int x,y;char c[3];scanf("%s%d",c,&x);x--;if(c[0]=='g')yzy.p[n][x]++;else if(c[0]=='s'){scanf("%d",&y);y--;For(i,0,n)swap(yzy.p[i][x],yzy.p[i][y]);}else For(i,0,n)yzy.p[i][x]=0;}
}
void ksm(){while(m){if(m&1)ans=ans*yzy;yzy=yzy*yzy;m=m>>1;}For(i,0,n-1)printf("%lld ",ans.p[0][i]);puts("");
}
int main()
{while(1){scanf("%d%d%d",&n,&m,&k);if(!n)break;init();ksm();}
}

 Subsequence(poj_3061)

本题滑动窗口随便弄一下就好了

#include<iostream>
#include<cstdio>
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
inline int read(){int t=1,num=0;char c=getchar();while(c>'9'||c<'0'){if(c=='-')t=-1;c=getchar();}while(c>='0'&&c<='9'){num=(num<<1)+(num<<3)+c-'0';c=getchar();}return num*t;
}
int T,n,s,a[100001],sum,ans,l,r;
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&n,&s);For(i,1,n)a[i]=read();ans=n+1;sum=a[1];l=r=1;while(1){while(r<n&&sum<s)sum+=a[++r];if(sum<s)break;ans=min(ans,r-l+1);sum-=a[l++];}if(ans>n)ans=0;printf("%d\n",ans);}
}

本文由Yzyet编写,网址为wwwblogs/Yzyet。非Yzyet同意,禁止转载,侵权者必究。

转载于:.html

更多推荐

暑假集训day10

本文发布于:2024-03-11 14:52:38,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1729206.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:暑假

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!