暑假集训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
发布评论