无    2017-02-26 11:43:45    137    1    0

题意

题解

建两棵树,一个原树,一个新树。
新树中每一个点代表一次操作的树。
对两棵树倍增,分类讨论讨论即可。
查询新树中第k个点在原树中的编号,可以考虑主席树查询区间k大,或者权值线段树的线段树合并。
时间复杂度:O(nlogn)

解题情况

搞了蛮久。
因为数据生成器写错了。。。

代码

  1. /**************************************************************
  2. Problem: 4539
  3. User: 941822900
  4. Language: C++
  5. Result: Accepted
  6. Time:16364 ms
  7. Memory:84644 kb
  8. ****************************************************************/
  9. #include<bits/stdc++.h>
  10. #define ll long long
  11. using namespace std;
  12. const int maxn=100000+10;
  13. vector<int> G[maxn];
  14. int n,m,q;ll N=1;
  15. int f1[maxn][20],f2[maxn][20];
  16. int dep1[maxn],dep2[maxn];ll dtr[maxn];
  17. #define lc ch[o][0]
  18. #define rc ch[o][1]
  19. #define mid ((l+r)>>1)
  20. int num;
  21. int root[maxn];
  22. int sumv[maxn*50];
  23. int ch[maxn*50][2];
  24. void add(int o,int l,int r,int x){
  25. if(l==r) ++sumv[o];
  26. else{
  27. if(x<=mid){
  28. if(!lc) lc=++num;
  29. add(lc,l,mid,x);
  30. }
  31. else{
无    2017-02-18 19:17:20    137    1    0

题意

题解

解题情况

代码

无    2017-02-18 11:40:49    142    1    0

题意

题解

很神的DP
问题可以转化为两个人分别取,取到相同序列的方案数
然后就是一个很简单的O(n3)dp了

解题情况

本人太弱不会转化,瞄了一眼题解

代码

  1. /**************************************************************
  2. Problem: 1566
  3. User: 941822900
  4. Language: C++
  5. Result: Accepted
  6. Time:7148 ms
  7. Memory:3280 kb
  8. ****************************************************************/
  9. #include<bits/stdc++.h>
  10. using namespace std;
  11. const int maxn=505;
  12. const int p=1024523;
  13. int n,m,ans,cur;
  14. char a[maxn],b[maxn];
  15. int f[2][maxn][maxn];
  16. int main()
  17. {
  18. f[cur][0][0]=1;
  19. scanf("%d%d",&n,&m);
  20. scanf("%s%s",a+1,b+1);
  21. for(int i=1;i<=(n>>1);i++) swap(a[i],a[n-i+1]);
  22. for(int i=1;i<=(m>>1);i++) swap(b[i],b[m-i+1]);
  23. for(int i=1;i<=n+m;i++){
  24. cur^=1;
  25. memset(f[cur],0,sizeof(f[cur]));
  26. for(int j=0;j<=i&&j<=n;j++)
  27. for(int k=0;k<=i&&k<=n;k++)
  28. if(i-j<=m&&i-k<=m){
  29. if(b[i-j]==b[i-k]) f[cur][j][k]+=f[
无    2017-02-18 08:43:55    129    1    0

题意

给出一棵treap,即每个点的数据 值、权值。根的数据值大于左孩子小于右孩子,根的权值比左右孩子都小。另外定义每个节点的访问次数,每个节点的代价为访问次数乘以深度(根深度为1)。整棵树的代价为每个节点的代价和。现在可以修改节点的权值,每修改一个代价为K。要求最后整棵树的代价与修改代价最小。(点数≤70)

题解

考虑本来是不同的,又是改为任何实数,所以一定能修改成符合题意的。
而这是一颗treap,中序遍历不变。
考虑先将权重离散化,再按数据值排序,区间dp。
设f[l][r][w],表示l~r中权值大于等于w的最小答案。
考虑枚举(l~r)中的点k为根进行转移。
时间复杂度O(n4)

解题情况

bzoj上数据范围都不给...
所以说我看了题解...

代码

  1. /**************************************************************
  2. Problem: 1564
  3. User: 941822900
  4. Language: C++
  5. Result: Accepted
  6. Time:200 ms
  7. Memory:2940 kb
  8. ****************************************************************/
  9. #include<bits/stdc++.h>
  10. using namespace std;
  11. const int maxn=75;
  12. int n,K,ans,pre[maxn],f[maxn][maxn][maxn];
  13. struct node{
  14. int a,b,c;
  15. node(){}
  16. node(int a,int b,int c):a(a),b(b),c(c){}
  17. }p[maxn];
  18. bool cmpa(const node& p1,const node& p2){
  19. return p1.a<p2.a;
  20. }
  21. bool cmpb(const node& p1,const node& p2){
  22. return p1.b<
无    2017-02-13 17:11:36    143    1    0

题意

在一场战争中,战场由n个岛屿和n-1个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为1的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他k个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。
侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布(但可以保证的是,资源不会分布到1号岛屿上)。不过侦查部门还发现了这台机器只能够使用m次,所以我们只需要把每次任务完成即可。
对于100%的数据,2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

题解

注意:sigma(ki)<=500000
考虑每次建虚数,在虚数上dp
其实也可以,一边建一边dp
时间复杂度:最坏O(sigma(ki)log(sigma(ki)))

解题情况

题目数据范围有问题?要卡long long.
用cin,cout就会RE?

代码

  1. /**************************************************************
  2. Problem: 2286
  3. User: 941822900
  4. Language: C++
  5. Result: Accepted
  6. Time:12912 ms
  7. Memory:61976 kb
  8. ****************************************************************/
  9. #include<bits/stdc++.h>
  10. #define ll long long
  11. usi
无    2017-02-13 09:56:27    82    1    0

题意

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

题解

先上一发整体二分。
问题变为:
序列支持区间加,区间求和
直接上动态开点线段树即可。

解题情况

昨天晚上就应该A了。
硬是拖到现在。
这题居然用cin,cout就会RE?

代码

  1. /**************************************************************
  2. Problem: 3110
  3. User: 941822900
  4. Language: C++
  5. Result: Accepted
  6. Time:8188 ms
  7. Memory:12236 kb
  8. ****************************************************************/
  9. #include<bits/stdc++.h>
  10. #define int long long
  11. #define getchar getchar_unlocked
  12. #define putchar putchar_unlocked
  13. using namespace std;
  14. const int maxn=50000+10;
  15. void read(int& ret){
  16. char c;ret=0;bool fu=false;
  17. while((c=getchar()),(c<'0'||c>'9'))
  18. fu=c=='-';
  19. do (ret*=10)+=c-'0';
  20. while((c=getchar()),(c>='0'&&c<='9'));
  21. if(fu) ret=-ret;
  22. }
  23. struct query{
  24. int t,ans;
  25. int k,a,b,c;
  26. void Read(){
  27. read(k);read(a);
  28. read(b);read(c);
  29. }
  30. bool operator < (const qu
无    2017-02-12 15:12:01    135    1    0

题意

给一个 N 个点 M 条边的连通无向图, 满足每条边最多属于一个环.
有 Q 组询问, 每次询问两点之间的最短路径.

题解

原图实际上是个仙人掌。
考虑建出它的圆方树。
在建好圆方树后, 首先需要解决的问题就是边权.
我们可以这么构造:
选出环上深度最小的点记为这个环的根.
方点向环的根连边, 边权为零.
环上其他点向方点连边, 边权为到环的根的最短路长度.
查询u,v距离时,先求出lca.
1.lca是圆点,则dis=dep[u]+dep[v]-dep[lca]*2
2.lca是方点,则dis=u到环的距离+v到环的距离+u,v到环上那两点的距离
1直接倍增,2先倍增,再考虑什么map之类的东西记一记。
时间复杂度O(nlogn)

解题情况

大概花了两个小时。

代码

  1. /**************************************************************
  2. Problem: 2125
  3. User: 941822900
  4. Language: C++
  5. Result: Accepted
  6. Time:604 ms
  7. Memory:5176 kb
  8. ****************************************************************/
  9. #include<bits/stdc++.h>
  10. using namespace std;
  11. const int maxn=10000+10;
  12. vector<int> G[maxn][2];
  13. int n,m,q,tot=2,first[maxn*2];
  14. int to[maxn*4],dis[maxn*4],next[maxn*4];
  15. int num,sz,fa[maxn],z[maxn],dfn[maxn],low[maxn];
  16. void addedge(int u,int v,int w){
  17. to[tot]=v;
  18. dis[tot]=w;
  19. next[tot]=first[
无    2017-02-12 11:50:18    107    1    0

题意

求一个仙人掌的直径

题解

和ioi2008island差不多,只是有多个环。
dp+单调队列即可。

解题情况

第一次写仙人掌,搞了好久

代码

  1. /**************************************************************
  2. Problem: 1023
  3. User: 941822900
  4. Language: C++
  5. Result: Accepted
  6. Time:444 ms
  7. Memory:7536 kb
  8. ****************************************************************/
  9. #include<bits/stdc++.h>
  10. using namespace std;
  11. const int inf=2e9;
  12. const int maxn=50000+10;
  13. vector<int> G[maxn];
  14. int fa[maxn],dep[maxn];
  15. int top,stk[maxn],a[maxn*2];
  16. int num,dfn[maxn],low[maxn];
  17. int n,m,ans,f[maxn],q[maxn*2];
  18. void dp(int u,int v){
  19. int tot=dep[v]-dep[u]+1;
  20. for(int i=v;i!=u;i=fa[i])
  21. a[tot--]=f[i];
  22. a[tot]=f[u];
  23. tot=dep[v]-dep[u]+1;
  24. for(int i=tot+1;i<=tot*2;i++)
  25. a[i]=a[i-tot];
  26. int l=1,r=0;
  27. for(int i=2;i<=tot*2;i++){
  28. if(l<=r&&i-q[l]>tot/2)
  29. ++l;
  30. if(l<=r)
  31. ans=max(ans,i+a[i]-q[l]+a[q[l]]);
  32. while(l<=r&&a[q[r]]-q[r]<a[i]-i)
  33. --
无    2017-01-24 17:05:40    331    1    0

题意

一般图最大匹配,带花树模板题

代码

无    2017-01-24 17:02:46    283    1    0

题意

二分图最大匹配模板题

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=500+10;
  4. int nl,nr,m,ans,l[maxn];
  5. bool vis[maxn],s[maxn][maxn];
  6. bool match(int u){
  7. for(int v=1;v<=nl;v++)
  8. if(s[u][v]&&!vis[v]){
  9. vis[v]=true;
  10. if(!l[v]||match(l[v])){
  11. l[v]=u;
  12. return true;
  13. }
  14. }
  15. return false;
  16. }
  17. int main()
  18. {
  19. cin>>nl>>nr>>m;
  20. for(int i=1;i<=m;i++){
  21. int u,v;
  22. scanf("%d%d",&u,&v);
  23. s[v][u]=true;
  24. }
  25. for(int i=1;i<=nr;i++){
  26. ans+=match(i);
  27. memset(vis,false,sizeof(vis));
  28. }
  29. cout<<ans<<endl;
  30. for(int i=1;i<=nl;i++)
  31. printf("%d ",l[i]);
  32. return 0;
  33. }
1/5