4
4
2015
0

Bzoj 题一览 V [2015.3.3 - 2015.3.31]

早春略过芳草地 慵懒的阳光或也有了些许生机
三月 是个有着诗歌一般韵律的日子
每晚的机房 有着与题目的相约的痕迹
和着早雨 在淡抹的春意中小憩
摘选出的 13 道题 是在 衡阳八中 上 做题的痕迹 

2015.3.13

Bzoj 3884 上帝与集合的正确用法
  f(x) = 2^2^2^2^2^2..^2 Mod x
  f(x) = 2^((2^2^2^2^2..^2) Mod Phi(x)+Phi(x)) Mod x=2^(f(Phi(x))+Phi(x))
  f(1) = 0
  中间运算过程有可能超过 Longint 写了 Log2(n) 的二进制加法 速度上只有 200 Ms + 了
 
#include <cstdio>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
#define Rep(i,x,y) for (i=x;i<=y;++i)
 
int p;
 
int Phi(int x) {
    int i,T=x;
    Rep(i,2,(int)sqrt(x)) {
        if (!(x%i)) T=T/i*(i-1);
        while (!(x%i)) x/=i;
    }
    if (x>1) T=T/x*(x-1);
    return T;
}
 
int CalcC(int x,int y,int z) {
    int T=0;
    while (y) {
        if (y&1) T=(T+x)%z;
        x=(x+x)%z;
        y>>=1;
    }
    return T;
}
 
int Calc(int x,int y,int z) {
    int T=1;
    while (y) {
        if (y&1) T=CalcC(T,x,z);
        x=CalcC(x,x,z);
        y>>=1;
    }
    return T;
}
 
int Ask(int p) {
    if (p==1) return 0;
    int P=Phi(p);
    return Calc(2,Ask(P)+P,p);
}
 
int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&p);
        printf("%d\n",Ask(p));
    }
    return 0;
}
 
Bzoj 2423 [HAOI2010]最长公共子序列
动态规划
记 长度 F[i][j]=max(F[i-1][j],F[i][j-1],F[i-1][j-1]+1 | S[i]==S[j] )
记 方案总数 G[i][j] 分类讨论 S1[i]=S2[j] S1[i]!=S2[j] 讨论!=时注意容斥原理 需要减去之前的一段
注意滚动数组
 

2015.3.14

Bzoj 2456 mode
抵消思想 mode 一定是可以抵消到最后的
 
#include <cstdio>
 
using namespace std;
  
#define Rep(i,x,y) for (i=x;i<=y;++i)
 
int x,Mode,n,i,T;
 
int main () {
    scanf("%d",&n);
    scanf("%d",&Mode);
    T=1;
    Rep(i,1,n-1) { 
        scanf("%d",&x);
        if (x==Mode) ++T; else --T;
        if (T<0) Mode=x,T=1;
        }
    printf("%d\n",Mode);
    return 0;
}
 
Bzoj 1264 [AHOI2006]基因匹配Match
注意到恰好出现5次以及数字为[1..n]的排列的特点
F[i]=Max(F[j]|1<=j<i)+1
以树状数组维护 Max(F[j]) 可以降到 O(5*nLog2(5*n)) = O(nLog2n)
 
#include <cstdio>
 
using namespace std;
  
#define Rep(i,x,y) for (i=x;i<=y;++i)
#define _Rep(i,x,y) for (i=x;i>=y;--i)
#define Lowbit(x) x&(-x)
#define Max 101001
 
int n,N,S,T,x,C[Max],i,A[Max][6],k,p,F[Max],G[Max];
 
void Insert(int x,int y) {
    while (x<=N) {
        if (y>C[x]) C[x]=y;
        x+=Lowbit(x);
    }
}
 
int Query(int x) {
    int T=0;
    while (x>0) {
        if (C[x]>T) T=C[x];
        x-=Lowbit(x);
    }
    return T;
}
     
int main () {
    scanf("%d",&n);
    N=5 * n;
    Rep(i,1,N) { 
        scanf("%d",&x);
        A[x][++G[x]]=i;
    }
    Rep(i,1,N) {
        scanf("%d",&x);
        _Rep(k,5,1) {
            p=A[x][k];
            T=Query(p-1);
            if (T+1>F[p]) F[p]=T+1;
            Insert(p,F[p]);
            if (F[p]>S) S=F[p];
        }
    }
    printf("%d",S);
    return 0;
}
 

2015.3.15

Bzoj 1406 [AHOI2007]密码箱
x<n x^2 Mod n=1 => n | (x+1)(x-1)
n=xy => x |  K y | K 
所有 [1..n] n 的约数及其倍数 P 满足条件的数的 偏序序列
令 x = k-1 则 x-1 = k-2 Mod (n/P) = 0 可以得到 x = k-1 满足
令 x = k+1 则 x+1 = k+2 Mod (n/P) = 0 可以得到 x = k+1 满足
时间复杂度 O((n/P For Range(P 为 n 约数)) * Log 其) 好像是靠谱的
 
/*x<n x^2 Mod n=1 => n | (x+1)(x-1)*/
/*n=xy => x |  K y | K */
 
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
 
using namespace std;
  
#define Rep(i,x,y) for (i=x;i<=y;++i)
const int Maxn = 1000001;
 
int N,n,i,A[Maxn],Top,k;
set<int> S;
 
int main () {
    scanf("%d",&n);
    N=(int)sqrt(n);
    Rep(i,1,N) if (!(n%i)) A[++Top]=n/i;
    Rep(i,1,Top) {
        int x=A[i];
        for (k=x;k<=n;k+=x) {
            if ((k-2)%(n/x)==0) S.insert(k-1);
            if ((k+2)%(n/x)==0) S.insert(k+1);
        }
    }
    S.insert(1);
    for (set<int>::iterator it=S.begin(); it!=S.end(); ++it) if (*it<n) printf("%d\n",*it);
    return 0;
}
 
Bzoj 1050 [HAOI2006]旅行comf
将边表排序
固定一条最短边 Min 将其后的以并查集维护连通性 若联通 则 Max = Its Edge
求得 Max/Min 最小
 

2015.3.22

Bzoj 3295 [Cqoi2011]动态逆序对
树状数组套线段树 
内层的线段树可以打删除标记
询问的时候直接在很多棵线段树上一起走一遍即可
注意其满足区间减法
因此可以 以 AskSeg(R) - AskSeg(L-1) 简化操作
 

2015.3.24

Bzoj 1816 [Cqoi2010]扑克牌
二分答案
注意 最大值为 Min(m,Mid) m 为总共的数量 Mid 为该次判断最多能用的数量 也就是保证总共不超过每副牌一张
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std;
 
#define Rep(i,x,y) for (i=x;i<=y;++i)
 
const int Maxn = 61;
 
int n,m,L,R,A[Maxn],i,Mid;
 
bool Check(int x) {
   int i,T=min(m,x);
   Rep(i,1,n) 
    if (A[i]<x) { 
        T=T-(x-A[i]);
        if (T<0) return 0;
    }
    return 1;
}
 
int main () {
    scanf("%d%d",&n,&m);
    Rep(i,1,n) scanf("%d",&A[i]);
    L = 0, R = 1000000000;
    while (L+1<R) {
       Mid=(L+R)>>1;
       if (Check(Mid)) L=Mid; else R=Mid;
    }
    if (Check(R)) printf("%d",R); else printf("%d",L);
    return 0;
}
 
Bzoj 1876 [SDOI2009]SuperGCD
Python 直接辗转相除
A,B=input(),input()
x=A%B;
while x!=0:
    A=B
    B=x
    x=A%B
print B

 

2015.3.28

 
Bzoj 1046 [HAOI2007]上升序列
求出以每一个为开头的最长上升子序列 
询问时直接贪心
 

Bzoj 1833 [ZJOI2010]count 数字计数

S[a,b] = S[1,b] - S[1,a-1] 
S[1,x] 可以通过数位 Dp 或者分块统计的思想 Log10 接近于常数时间计算
 

2015.3.29

Bzoj 1052 [HAOI2007]覆盖问题
http://tianyong1995.blog.163.com/blog/static/20772234420127193820630/
二分答案 L
重建矩形 从左上角/右上角/左下角/右下角 开始枚举 判断
时间复杂度 O(8*n*Log2(Inf))
 
[另外个人感觉可以线段树 + 扫描线 + 贪心的 离线以后扫描 大概可以做到 O(n(Log2n)^2) 以上做法未写过 正确性不保证]
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
const int Maxn = 20010 , Inf = 2015032990;
 
#define Rep(i,x,y) for (i=x;i<=y;++i)
 
int n,X[2],Y[2],_X[2],_Y[2],x[Maxn],y[Maxn],__X[2],__Y[2],L,R,Mid,i;
bool P[Maxn];
 
bool Ok(int W) {
    int S = 0,i,j,p,q,_x,_y,k,_S;
    Rep(i,0,1) Rep(j,0,1) {
        S = 0;
        _x = X[i] , _y = Y[j];
        _X[1] = _Y[1] = -Inf ;
        _X[0] = _Y[0] = Inf;
        memset(P,0,sizeof(P)); //注意每次枚举第一个正方形时把之前的清零 
        Rep(k,1,n)
            if (!P[k] && abs(x[k]-_x)<=W && abs(y[k]-_y)<=W) P[k]=1,++S;
            else {
                _X[0] = min(_X[0],x[k]);        
                _X[1] = max(_X[1],x[k]);
                _Y[0] = min(_Y[0],y[k]);
                _Y[1]= max(_Y[1],y[k]);
            }
        if (S==n) return 1;
        //printf("Continue");
        Rep(p,0,1) Rep(q,0,1) {
            _S = S; //枚举第二个正方形时在第一个的基础上累加而不是直接累加 
            _x = _X[p] , _y = _Y[q];
            __X[1] = __Y[1] = -Inf ;
            __X[0] = __Y[0] = Inf; //注意赋初值 
            Rep(k,1,n)
                if (!P[k] && abs(x[k]-_x)<=W && abs(y[k]-_y)<=W) ++_S; //注意这里不能标记 P[k] 因为之后还要用 
                else if (!P[k]){
                    __X[0] = min(__X[0],x[k]);      
                    __X[1] = max(__X[1],x[k]);
                    __Y[0] = min(__Y[0],y[k]);
                    __Y[1]= max(__Y[1],y[k]);
                }
            if (_S==n || (__X[1]-__X[0]<=W && __Y[1]-__Y[0]<=W)) return 1;
        }
    }
     
    return 0;
}
 
int main () {
    scanf("%d",&n);
    X[1] = Y[1] = -Inf ;
    X[0] = Y[0] = Inf;
    Rep(i,1,n) {
        scanf("%d%d",&x[i],&y[i]);
        X[0] = min(X[0],x[i]);      
        X[1] = max(X[1],x[i]);
        Y[0] = min(Y[0],y[i]);
        Y[1]= max(Y[1],y[i]);
    }
    L = 0 , R = Inf;
    //if (Ok(1)) { printf("YES"); return 0; }
    while (L+1<R) {
        Mid = (L+R)>>1;
        if (Ok(Mid)) R = Mid ; else L = Mid;
    }
    if (Ok(L)) printf("%d",L); else printf("%d",R);
    return 0;
}

 

Bzoj 1068 [SCOI2007]压缩
Problem & Solution & Code:
/*{
 
(M)abcRdRMxyRz
 
abcabcdabcabcdxyxyz
 
abc
abcabc
abcabcd
abcabcdabcabcd
abcabcdabcabcd(M)xy
abcabcdabcabcdxyxy
abcabcdabcabcdxyxyz
 
M标记当前开始压缩
 
R重复一遍
 
abcMabc -> abcMabc abcM c
 
http://blog.csdn.net/qpswwww/article/details/44173265
 
不妨设整个字符串长度为n。根据题意，我们可以看作在区间
[1,n]之前已经放有一个字母M。那么我们就是要用若干个M和R，将字符串中的循环节括起
来，并使最终压缩后的字符串尽量短，显然这是个划分DP，而且用记忆化搜索写起来简单些。 
 实际上我们只需要DP出字符串中怎么放M就可以了，如果发现当前dp的区间中不含M，并且左右两半是一样的，那么就在中点处放一个R就行了。因此我们用f[L][R][k]来表示区间
[L,R]，
k=1表示
[L,R]中有缝隙处放了M(注：不包含
L?1和R+1，并且约定
L?1处一定有个M，或
L?1=0)，压
缩后的字符串长度。显然边界条件是f[i][i][0]=1,f[i][i][1]=inf(因为只有一个元素的区间就没有缝隙放M)。那么对于区间
[L,R]，如果其中放
了M，那么我们就暴力枚举其中一个M放在哪里，并用分割后的两个区间的状态做转移。如果其中没放M，我们先判断这个区间是否是一个循环节(左右两半的字符串一样)，是的话那么这个区间只需要左半部分压缩后的长度+一个R就够了。否则我们就枚举R放在哪里，这样这个R就和前面的L?1和L之间的那
个M对应起来，括起来了一个循环节部分，然后再用这个循环节部分的dp值做转移，R后面的那部分保持压缩之前的样子不变。
 
说起来比较复杂，不过看代码就很清晰了。注意那个判断循环节的函数，一定要有特判，即这个区间长度是偶数，如果是奇数显然不能把这段字符串分成相等的两半，不特判会WA！！！
 
}
 
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cstdlib>
  
using namespace std;
  
const int Maxn =50 , Inf = 2015032990;
  
#define Rep(i,x,y) for (i=x;i<=y;++i)
  
char S[Maxn];
int F[Maxn][Maxn][2]={0},L;
 
 
bool Ok(int L,int R){
    int i;
    Rep(i,L,(L+R)>>1) if (S[i]!=S[i+((R-L+1)>>1)]) return 0;
    return 1;
}
 
int Dfs(int L,int R,int x) {
    int T = R-L+1,i;
    if (T==1) return 1;
    if (F[L][R][x]) return F[L][R][x];
    if (x==1) Rep(i,L,R-1) T = min(T,Dfs(L,i,1) + 1 + Dfs(i+1,R,1)); //+M
    Rep(i,L,R-1) T = min(T,Dfs(L,i,x) + R-i); //~ +M
    if (Ok(L,R) && (!((R-L+1)&1))) T=min(T,Dfs(L,(L+R)>>1,0)+1); //+R
    F[L][R][x] = T;
    return T;
}
 
int main () {
    scanf("%s",S+1);
    L = strlen(S+1) ;
//  printf("%d",Ok(1,4));
    cout << Dfs(1,L,1) << endl;
    return 0;
}
Category: 题目 | Tags: 二分 数论 贪心 动态规划 树状数组 线段树 图论 并查集 栈 枚举 前缀和 线性扫描 | Read Count: 891
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com