28
2015
[bzoj]4373: 算术天才⑨与等差数列
-->http://www.lydsy.com/JudgeOnline/problem.php?id=4373
强制在线。。只能想到数据结构-。-
标算表示想不到-。-||| %Claris
我的做法是,用线段树维护区间最小值,区间哈希值,哈希采用平方和的方法(from 比利),对于一个知道了首项和公差的等差数列,其数列
$hash 值= n·a[1]·a[n]+ \frac{n(n-1)(2n-1)·k^2}{6}$
然后。。
25
2015
[bzoj]2657: [Zjoi2012]旅游(journey)
-->http://www.lydsy.com/JudgeOnline/problem.php?id=2657
嘛,两个三角形最多只有一条公共边-。-,然后以每个三角形为顶点与相邻的三角形连边,这样构成一棵树。。然后跑直径就好了
$O(N)$
#include<cstring> #include<algorithm> #include<cstdio> #include<map> using namespace std; #define nc() getchar() inline int read(){ int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc()); for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x; } #define N 200010 int i,j,k,m,n,x,y,cnt,last[N],z,who,dep[N],Dep; struct edge{int to,next;}e[N<<1]; inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt,e[++cnt]=(edge){u,last[v]},last[v]=cnt;} struct Edge{int l,r;bool operator <(const Edge&b)const{return(l<b.l)||(l==b.l)&&(r<b.r);}}; map<Edge,int>mp; void dfs(int x,int fa){ dep[x]=dep[fa]+1; for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa)dfs(y,x); if(Dep<dep[x])Dep=dep[x],who=x; } inline void Add(int x,int y){ if(mp[(Edge){x,y}]!=0)add(mp[(Edge){x,y}],i),mp[(Edge){x,y}]=0,mp[(Edge){y,x}]=0; else mp[(Edge){x,y}]=i,mp[(Edge){y,x}]=i; } int main(){ for(n=read(),i=1;i<n-1;++i){ x=read(),y=read(),z=read(); Add(x,y),Add(x,z),Add(y,z); } dfs(1,0),Dep=0,dep[0]=0,dfs(who,0); printf("%d",Dep); }
25
2015
[bzoj]2226: [Spoj 5971] LCMSum
-->http://www.lydsy.com/JudgeOnline/problem.php?id=2226
跟比利做题时不时就会出现这种我还没做过的题$0.0$
$O(T\sqrt n)$
#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define nc() getchar() inline int read(){ int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc()); for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x; } #define N 1000010 #define ll long long int i,j,k,m,n,x,y,T,phi[N],o;ll ans; int main(){ phi[1]=1; for(i=2;i<=N;++i)if(!phi[i])for(j=i;j<=N;j+=i){ if(!phi[j])phi[j]=j; phi[j]=phi[j]/i*(i-1); } for(ans=0,T=read();T--;){ for(ans=0,n=read(),o=sqrt(n),i=1;i<=o;++i)if(n%i==0){ if(i!=1)ans+=1ll*i*phi[i]/2; else ans+=1; if(i*i!=n)ans+=1ll*n/i*phi[n/i]/2; } printf("%lld\n",1ll*ans*n); } }
24
2015
[bzoj]4289: PA2012 Tax
-->http://qiancl.is-programmer.com/user_files/qiancl/Image/Problem%204289.%20--%20PA2012%20Tax.html
PA的题短小精悍-。-
考虑每条边建立一个点,边与边的转移可以通过枚举中间点,把与中间点有关的边暴力抠出来排序,从小到大加,从以中间点为终点的向以x点为起点的连边,边权为原边权,再连向下一条,边权是与上一条的差,再与上一条连边权为0的边,图构好后,直接跑最短路就行了
#include<cstring> #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; #define ll long long #define nc() getchar() inline int read(){ int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc()); for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x; } #define N 200010 #define pk push_back const ll inf=1ll<<60;queue<int>q;bool vis[N<<1]; int i,j,k,m,n,x,y,z,cnt,last[N<<1];ll dis[N<<1]; struct node{int u,v,w;bool operator <(const node&b)const{return w<b.w;}}; struct edge{int to,next,v;}e[N*6]; #define add(u,v,w) (e[++cnt]=(edge){v,last[u],w},last[u]=cnt) vector<node>E[N<<1]; int main(){ for(n=read(),m=read(),i=2;i<=m+1;++i){ x=read(),y=read(),z=read(); E[x].pk((node){i<<1,(i<<1)-1,z}),E[y].pk((node){(i<<1)-1,i<<1,z}); if(x==1)add(1,(i<<1)-1,z);if(y==1)add(1,i<<1,z); if(y==n)add((i<<1)-1,2,z);if(x==n)add(i<<1,2,z); } for(i=1;i<=n;++i){ int len=E[i].size();sort(E[i].begin(),E[i].end()); for(j=0;j<len;++j)add(E[i][j].u,E[i][j].v,E[i][j].w); for(j=0;j<len-1;++j)add(E[i][j].v,E[i][j+1].v,E[i][j+1].w-E[i][j].w),add(E[i][j+1].v,E[i][j].v,0); } for(i=2;i<=m+1<<1;++i)dis[i]=inf;q.push(1); while(!q.empty()){ int k=q.front();q.pop(),vis[k]=1; for(int i=last[k],y;i;i=e[i].next)if(dis[y=e[i].to]>dis[k]+e[i].v){ dis[y]=dis[k]+e[i].v; if(!vis[y])vis[y]=1,q.push(y); }vis[k]=0; } printf("%lld\n",dis[2]); }
22
2015
[bzoj]3072: [Pa2012]Two Cakes
……第一眼挺简单-。-
……第二眼不会-。-|||
……考虑DP$f[i][j]$表示 $a$串取了$i$次,$b$串取了$j$次,于是
$f[i-1][j] -> f[i][j]$
$f[i][j-1] -> f[i][j]$
$f[i-1][j-1] -> f[i][j] (a[i]!=b[j])$
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define nc() getchar() inline int read(){ int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc()); for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x; } #define N 1000100 int i,j,k,m,n,x,y,a[N],b[N],rk[N],f[5005][5005],g[N]; int main(){ for(n=read(),i=1;i<=n;++i)a[i]=read(),rk[a[i]]=i; for(i=1;i<=n;++i)b[i]=read(); memset(f,0x3f,sizeof f); f[0][0]=0; for(i=1;i<=n;++i) for(j=1;j<=n;++j){ f[i][j]=min(f[i][j],f[i-1][j]+1); f[i][j]=min(f[i][j],f[i][j-1]+1); if(a[i]!=b[j])f[i][j]=min(f[i][j],f[i-1][j-1]+1); } printf("%d\n",f[n][n]); }
18
2015
[bzoj]4345: [POI2016]Korale
-->http://www.lydsy.com/JudgeOnline/problem.php?id=4345
首先考虑第一个问题
定义二元组$(x,y)$表示当前价值为$x$,位置在$y$,则$(x,y)$可以转移到$(x+a[y+1],y+1)$以及$(x-a[y]+a[y+1],y+1)$两个状态,这个先把$a$数组排序,再加个小根堆维护就行了,复杂度$\mathcal{O}\left(k\log k\right)$