煞笔出题人一百块标程都不给我
1.题目一
首先每个点记录一下上一个跟它颜色相同的点在哪
然后用树状数组维护：若一个新的颜色出现，则在该点位置+1
则一段区间[L,R]颜色个数为ask(R)-ask(L-1)
那么把询问按右端点排序，每次将r[i-1]+1到r[i]的点+1，同时将上一个颜色相同的点-1
可以确保答案仍然正确（因为某种颜色在后面出现过了前面就不需要再统计了，同时后面一段必然在当前询问区间内）
于是复杂度O(mlogn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
// <sequence.cpp> - 02/19/16 08:09:14 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } #define lowbit(x) (x&-x) const int MAXN=50002,MAXM=100002,MAXC=1000002; int a[MAXN],last[MAXN],c[MAXN]; int color[MAXC]; int ans[MAXM]; int n; struct query{int l,r,i;}q[MAXM]; bool cmp(query a,query b){return a.r==b.r?a.l<b.l:a.r<b.r;} void plu(int w,int x){ while(w<=n){ c[w]+=x; w+=lowbit(w); } } int get(int x){ int sum=0; while(x){ sum+=c[x]; x-=lowbit(x); } return sum; } int main(){ freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); n=getint(); int m=getint(); for(int i=1;i<=n;i++){ a[i]=getint(); if(color[a[i]])last[i]=color[a[i]]; color[a[i]]=i; } for(int i=0;i<m;i++)q[i].l=getint(),q[i].r=getint(),q[i].i=i; sort(q,q+m,cmp); int R=0; for(int i=0;i<m;i++){ for(int o=R+1;o<=q[i].r;o++){ plu(o,1); if(last[o])plu(last[o],-1); } R=q[i].r; ans[q[i].i]=get(q[i].r)-get(q[i].l-1); } for(int i=0;i<m;i++)printf("%d\n",ans[i]); return 0; } |
2.题目二
还不会
3.题目三
暴搜加个剪枝就能过了。。
4.题目四
后悔当时YJP讲递推转矩阵快速幂的时候没听。。
不过现在会了！
矩阵快速幂真是一个神奇的东西！
首先我们定义一个矩阵
$$\begin{pmatrix}f(i)&i+1&1\end{pmatrix}$$
其中f(i)表示第i天的答案
那么第0天的矩阵为
$$\begin{pmatrix}0&1&1\end{pmatrix}$$
每天我们将矩阵乘以这样一个矩阵【矩阵乘法都学过吧 不会的自行去补
$$\begin{pmatrix}x&0&0\\1&1&0\\0&1&1\end{pmatrix}$$
那么我们将第i天的矩阵乘以它可以得到的是
$$\begin{pmatrix}f(i)&i+1&1\end{pmatrix}
\begin{pmatrix}x&0&0\\1&1&0\\0&1&1\end{pmatrix}=
\begin{pmatrix}xf(i)+i+1&i+2&1\end{pmatrix}$$
其中xf(i)+i+1即为第i+1天答案 i也自动加了1 是不是很神奇233
那么第n天的答案即为
$$\begin{pmatrix}0&1&1\end{pmatrix}\begin{pmatrix}x&0&0\\1&1&0\\0&1&1\end{pmatrix}^n$$
把后面的那个用快速幂算。。于是复杂度变为了O(logn)
就可以A了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// <double.cpp> - 02/19/16 13:17:49 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } int w; struct matrix{ lol a[3][3]; matrix(){for(int i=0;i<3;i++)for(int o=0;o<3;o++)a[i][o]=0;} matrix(lol b[3][3]){for(int i=0;i<3;i++)for(int o=0;o<3;o++)a[i][o]=b[i][o];} matrix operator *(matrix b){ matrix ans; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++)ans.a[i][j]=(ans.a[i][j]+(a[i][k]*b.a[k][j])%w)%w; return ans; } }; lol f(lol x,lol n){ lol sb1[3][3]={{x,0,0},{1,1,0},{0,1,1}},sb2[3][3]={{0,1,1},{0,0,0},{0,0,0}}; matrix j=matrix(sb1),ans=matrix(sb2); while(n){ if(n&1)ans=ans*j; j=j*j; n>>=1; } return ans.a[0][0]; } int main(){ freopen("double.in","r",stdin); freopen("double.out","w",stdout); lol n,x; cin>>n>>x>>w; x%=w; cout<<f(x,n)<<endl; return 0; } |
作为出题人我要%%%%%
【谁啊
【T4数据都是错的←_←