这是新坑……
同时开了KDT和LCT的坑【不知道的同学等下就知道了】
READ MORE →
Link Cut Tree 学习笔记
先上一份代码……回去研究研究 @Sdchr
READ MORE →
BZOJ4278
Miller_Rabin 素数判定
后缀数组学习笔记
心情复杂
近来的训练暴露了很多的问题
我已经不会打暴力了
可能是OI比赛玩少了，就不会打暴力了？
但是更心寒的是我的知识点的欠缺
一下是待补的坑：
LCT
SA
数学姿势
DP优化姿势
考试的姿势……
心情复杂
8.4 小测1
题目放出来不是很好……就不放题目和代码了
稍微记录一下考试时候的一些记录
T1
dp[i][j][0/1]
pos : i
cnt : j
Connecting : 0/1
可以留意到最大字典序的子串一定包含了答案
而且一定是从开头包含
可以考虑利用这一点瞎搞
比如我们二分它这条最长串的长度，之后尝试构造？
这里的构造是我们要造出最大串是二分得到串的，且个数尽量小
可以考虑用kmp解决
kmp 匹配之后 在匹配结束的地方砍一刀
没有匹配就继续
这样子就是nlogn的
但是怎么找到最长的子串还是个问题……
我想到的是用SAM
好烦啊不想用SAM啊
T2
F(0,n) = n+1
F(m,0) = F(m-1,1)
F(m,n) = F(m-1,F(m,n-1))
打个表找找规律吧
日哦……真的烦
有点像是
F[0,n]=n+1
F[1,n]=n+2
F[2,n]=2*n+3
F[3,n]=F[2,F[3,m-1]]
F[3,0]=2+3
F[3,1]=4+3*(1+2)
F[3,2]=8+3*(1+2+4) = 29
F[3,3]=2*29+3
打完表
应该是30分
回去看T1
思路没什么错……就是代码量比较大
T3还剩五十分钟看出来是一个树链剖分套四tag线段树
mdzz码农题写个皮皮虾
BZOJ1367 [Baltic2004]sequence
1367: [Baltic2004]sequence
Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 1346 Solved: 550
[Submit][Status][Discuss]
Description
Input
Output
一个整数R
Sample Input
7
9
4
8
20
14
15
18
9
4
8
20
14
15
18
Sample Output
13
HINT
所求的Z序列为6,7,8,13,14,15,18.
R=13
Source
论文看不是很懂的可以去看看徐姥爷的题解
打错一个下划线wa N次，心痛一波ac率
|
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #include <queue> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 1000010 struct node { int c[2],val,dep; node() { c[0]=c[1]=val=0; dep=1; } int& operator [] (const int &x) { return c[x]; } }pool[N]; queue<int> q; int root[N],siz[N],_siz[N],tot,pcnt; int merge(int x,int y) { if(!x||!y) return (x+y); if(pool[x].val<pool[y].val) swap(x,y); pool[x][1]=merge(pool[x][1],y); if(pool[pool[x][0]].dep<pool[pool[x][1]].dep) swap(pool[x][1],pool[x][0]); pool[x].dep=pool[pool[x][1]].dep+1; return x; } int pop(int &x) { q.push(x); x=merge(pool[x][0],pool[x][1]); } int getpt() { static int ret; if( q.empty() ) ret=++pcnt; else { ret=q.front(); q.pop(); }; pool[ret]=node(); return ret; } int z[N],n,w[N]; ll ans; void init() { while(!q.empty()) q.pop(); read(n); For(i,1,n) read(z[i]),z[i]-=i; pool[0].dep=0; } int main() { int node=1; init(); For(i,1,n) { root[++tot]=getpt(); pool[root[tot]].val=w[tot]=z[i]; siz[tot]=_siz[tot]=1; while(w[tot]<w[tot-1]&&tot>1) { root[tot-1]=merge(root[tot-1],root[tot]); siz[tot-1]+=siz[tot]; _siz[tot-1]+=_siz[tot]; tot--; while(_siz[tot] != (siz[tot]>>1)+(siz[tot]&1)) pop(root[tot]),_siz[tot]--; w[tot]=pool[root[tot]].val; } } For(i,1,tot) { for(;siz[i];siz[i]--) ans+=abs(z[node++]-w[i]); } printf("%lld",ans); return 0; } |
BZOJ4361
神奇树状数组优化DP+组合数
思路很暴力……但是就是比较难连起来
第一步：
dp[i][j]表示枚举到第i位结尾且以第i位为结尾时 不下降子序列长度为j的情况数量
\( dp[i][j]=\sum_{k=1}^{j}(dp[i-1][k]) \)
第二步：
令 g[x] 表示所有长度为x的 不下降子序列 的数量
\( g[x]=\sum_{k=1}^{n}dp[k][x] \)
可以发现我们的ans和这个g[x]是由联系的
长度为x的 不下降子序列 的数量……和两个东西有关系
第一类—->从g[x+1]直接减少一位过来 第二类—->从非g[x+1]的过来 【参照定义理解】
第二类的数量是要记入答案的数量的
就稍微的暴力用n阶乘来做就好了，反正n不大
\( ans=\sum_{k=1}^{n}g[k]*(n-k)!-g[k+1]*g[k+1]*(n-k-1)!*(k+1) \)
以下代码
|
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 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 2010 #define mod 1000000007LL #define lb(x) (x&-x) ll sum[N][N]; void add(int y,int pos,int val) { for(;pos<=N;pos+=lb(pos)) sum[y][pos]+=val,sum[y][pos]%=mod; } int query(int y,int pos) { static ll ret; for(ret=0;pos;pos-=lb(pos)) ret+=sum[y][pos]; return (int)(ret%mod); } #undef lb int dp[N][N],a[N],c[N],n; ll g[N],ans,l[N]; void init() { read(n); For(i,1,n) read(a[i]),c[i]=a[i]; sort(c+1,c+1+n); For(i,1,n) a[i]=lower_bound(c+1,c+1+n,a[i])-c; for(int i=1;i<=n;i++) { for(int j=i;j>=2;--j) { dp[i][j]=query(j-1,a[i]); add(j,a[i],dp[i][j]); } dp[i][1]=1; add(1,a[i],1); } } int main() { init(); For(i,1,n) for(int j=1;j<=n;j++) g[i]+=dp[j][i],g[i]%=mod; l[0]=1; ans+=g[n]; for(int i=n-1;i;i--) { l[n-i]=l[n-i-1]*(n-i)%mod; ans+=g[i]*l[n-i]%mod-(g[i+1]*l[n-i-1])%mod*(i+1)%mod; ans%=mod; } printf("%lld\n",(ans+mod)%mod); return 0; } |
NOIP2013货物运输
为什么我在写这题的题解……
因为这题我本来想用树剖搞过去的……结果炸了
:-D然后就写了现在的倍增
|
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #define ll long long #define INF 10000000 #define For(i,a,b) for(int i=a;i<=b;i++) #define p(c) (c>='0'&&c<='9') char cc; int C; template <class T> void read(T &x) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 10010 #define M 50010 struct rec { int u,v,val; bool operator < (const rec &x) const { return val>x.val; } }REC[M]; struct UNF { int fa[N],siz[N]; void init(int n) { For(i,1,n) fa[i]=i,siz[i]=1; } int getfa(int x) { return fa[x]==x?x:fa[x]=getfa(fa[x]); } bool combine(int u,int v) { u=getfa(u); v=getfa(v); if(u==v) return false; siz[u]<siz[v]?swap(u,v):swap(u,u); fa[v]=u; siz[u]+=siz[v]; return true; } bool test(int u,int v) { return getfa(u)==getfa(v); } }UNF_set; struct Tedge { int to,val; }edge[N<<1]; int fst[N],nxt[N<<1],e_tot; #define TO edge[i].to #define VAL edge[i].val #define NXT nxt[i] void add_e(int a,int b,int val) { static int &i=e_tot; TO=b; VAL=val; NXT=fst[a]; fst[a]=i++; TO=a; VAL=val; NXT=fst[b]; fst[b]=i++; } int val[N],fa[N][15],mn[N][15],dep[N],n,m; void dfs(int x,int f) { fa[x][0]=f; mn[x][0]=val[x]; for(int i=1;i<15;i++) { fa[x][i]=fa[fa[x][i-1]][i-1]; mn[x][i]=min(mn[x][i-1],mn[fa[x][i-1]][i-1]); } for(int i=fst[x];~i;i=NXT) { if(TO==f) continue; val[TO]=VAL; dep[TO]=dep[x]+1; dfs(TO,x); } } int getLCA(int u,int v) { if(dep[u]>dep[v]) swap(u,v); int dis=dep[v]-dep[u]; for(int i=14;i>=0;i--) if((1<<i)&dis) v=fa[v][i]; if(u==v) return u; for(int i=14;i>=0;i--) if(fa[u][i]==fa[v][i]) continue; else u=fa[u][i],v=fa[v][i]; return fa[u][0]; } void init() { memset(fst,-1,sizeof(fst)); read(n); read(m); For(i,1,m) { read(REC[i].u); read(REC[i].v); read(REC[i].val); } sort(REC+1,REC+1+m); UNF_set.init(n); For(i,1,m)if(UNF_set.combine(REC[i].u,REC[i].v)) add_e(REC[i].u,REC[i].v,REC[i].val); } int main() { init(); int ans,u,v,p; for(int i=1;i<=n;i++) if(!val[i]) { val[i]=INF; dfs(i,0); } for(read(m);m;m--) { read(u); read(v); if(!UNF_set.test(u,v)) { puts("-1"); continue; } p=getLCA(u,v); ans=INF; for(int i=14;i>=0;i--) { if((dep[u]-dep[p])&(1<<i)) ans=min(ans,mn[u][i]),u=fa[u][i]; if((dep[v]-dep[p])&(1<<i)) ans=min(ans,mn[v][i]),v=fa[v][i]; } printf("%d\n",ans); } return 0; } |