—— Summon, Light!

引理：
我们称 $X\ge M$ 时 $X\ mod\ M$ 为一次有效的取模，则 $X$ 在 $\lceil log_{2}X\rceil$ 次有效的取模后一定变为 0 。
简要说明：
考虑最坏情况，取 $M=\lfloor\frac{X}{2}\rfloor+1$ ，$X->\lfloor\frac{X-1}{2}\rfloor$
（当 $M’>M$ 或 $M’<M$ 时，$X$ 都会变得更小）

题解：
考虑到 $a[l]$ 有效取模次数是 $log$ 级别的，所以只需要快速找出下一次有效的取模
即，每次寻找不大于当前数的最靠左的数
可以二分右端点，并询问区间内最小的数
使用ST维护，预处理 $O(NlogN)$ ，询问 $O(1)$
取模 $O(logX)$ 次，二分 $O(logN)$ 次，rmq $O(1)$ ，每个case复杂度为 $O(M*logX*logN)$
ST好久没写。。。可能失败的二分也好久没写。。。T了好多好多次。。。代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100010;
int st[N][25];

void st_init(int n)
{
    for (int i=1;(1<<i)<=n;i++)
        for (int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}

int st_query(int l,int r)
{
    int k=0;
    while ((1<<(k+1))<=r-l+1) k++;
    return min(st[l][k],st[r-(1<<k)+1][k]);
}

int bsearch(int l,int r,int lim)
{
    int res=r+1;
    while (l<=r) {
        int m=(l+r)>>1;
        if (st_query(l,m)>lim) l=m+1;
        //区间最小值大于当前值，即区间所有数大于当前值
        else r=m-1,res=m;
    }
    return res;
}

int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&st[i][0]);
        st_init(n);
        scanf("%d",&m);
        while (m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            int res=st[l++][0];
            while (l<=r&&res) {
                l=bsearch(l,r,res);
                if (l<=r) {
                    res%=st[l++][0];
                }
            }
            printf("%d\n",res);
        }
    }
    return 0;
}

阅读全文 »

hdu 5728 PowMod 数论

发表于 2016-10-05 更新于 2022-10-11 Valine：

[PowMod][1]

先贴官方题解

其中第二段根本不懂。。。然后就去学习了一下

引理：设 p 为 n 的一个质因数，
$$if\quad p^2|n\quad then\quad \varphi(n)=\varphi(\frac{n}{p})\times p\quad else\quad \varphi(n)=\varphi(\frac{n}{p})\times \varphi(p)$$
前一部分可以用 $\varphi(n)$ 的定义来证明，后一部分就是积性函数的性质(详见[欧拉函数为什么是积性函数][2])

题中n is a square-free number表示 $n$ 没有平方因子。
我们设 $p$ 为 $n$ 的一个质因数，对 $p\mid i$ 的情况分类讨论：
$$\sum_{i=1}^{m}\varphi(i\times n)=\sum_{p\nmid i}^{m}\varphi(i\times n)+\sum_{p\mid i}^{m}\varphi(i\times n) \\
=\varphi(p)\times \sum_{p\nmid i}^{m}\varphi(i\times \frac{n}{p})+p\times \sum_{p\mid i}^{m}\varphi(i\times \frac{n}{p}) \\
(\because\ p\ is\ a\ prime\ number) \\
=\varphi(p)\times \sum_{p\nmid i}^{m}\varphi(i\times \frac{n}{p})+(\varphi(p)+1)\times \sum_{p\mid i}^{m}\varphi(\frac{i}{p}\times n) \\
(\because p\mid i\ 和\ p\nmid i\ 合并为全集 ) \\
=\varphi(p)\times \sum_{i=1}^{m}\varphi(i\times \frac{n}{p})+\sum_{p\mid i}^{m}\varphi(\frac{i}{p}\times n) \\
=\varphi(p)\times \sum_{i=1}^{m}\varphi(i\times \frac{n}{p})+\sum_{i=1}^{m/p}\varphi(i\times n)$$

再解释另一个式子：$a^b\equiv a^{\varphi(p)+b%\varphi(p)}\pmod p$，我们分两种情况：

$a$与$p$互质，那么由费马-欧拉定理，$a^{\varphi(p)}\equiv 1 \pmod p$，原式成立；
$a$与$p$不互质，则$a^x$在$\varphi(p)$次之内就会变为0。需要一个条件，$b\geq \varphi(p)$，那么实际上$a^b\equiv a^{\varphi(p)+b%\varphi(p)}\equiv 0 \pmod p$，原式成立。

但是为什么满足$b\geq \varphi(p)$我还是觉得很难解释，代码是抄标程的：

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int MOD=1000000007;
const int N=1e7+5;
bool b[N];
int phi[N],s[N],prime[700000];
int tot=0;

void getphi()
{
    phi[1]=1;
    for (int i=2;i<N;i++) {
        if (!b[i]) {
            phi[i]=i-1;
            prime[++tot]=i;
        }
        for (int j=1;j<=tot;j++) {
            if (i*prime[j]>=N) break;
            b[i*prime[j]]=1;
            if (i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
            } else {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
    s[0]=0;
    for (int i=1;i<N;i++)
        s[i]=(s[i-1]+phi[i])%MOD;
}

int getsum(int n,int m)
{
    if (m==0) return 0;
    if (m==1) return phi[n];
    if (n==1) return s[m];
    for (int i=1;i<=tot;i++) {
        if (n%prime[i]==0)
            return (1LL*(prime[i]-1)*getsum(n/prime[i],m)%MOD+getsum(n,m/prime[i]))%MOD;
    }
    return 0;
}

int pow(long long x,int n,int M)
{
    long long res=1;
    while (n) {
        if (n&1) res=res*x%M;
        x=x*x%M;
        n>>=1;
    }
    return res;
}

int solve(int k,int p)
{
    if (p==1) return 0;
    int now=solve(k,phi[p]);
    return pow(k,phi[p]+now,p);
}

int main()
{
    int n,m,p;
    getphi();
//  printf("%d\n",tot);
    while (scanf("%d%d%d",&n,&m,&p)!=EOF) {
        int k=getsum(n,m);
        printf("%d\n",solve(k,p));
    }
    return 0;
}

阅读全文 »

hdu 5919 Sequence II 主席树

发表于 2016-10-05 更新于 2022-10-11 Valine：

Sequence II

题意：给出原数列。每次询问一个区间时，把各个数字在这个区间中第一次出现的位置记作 $p_{1},p_{2},\cdots, p_{k}$ ，满足 $p_{1} < p_{2} < \cdots < p_{k}$ ，求 $p_{\lceil \frac{k}{2}\rceil}$ 。询问强制在线。

题解：camp 的题解搞得我莫名其妙。。。 $O(Mlog^{2}N)$ 明显过不了吧。。。

~~因为我重现赛的时候就是强行套了一个二分变成了这个复杂度。。。~~
本来我学主席树就是因为长春比完有人说要用到主席树。。。结果我还是没做出来= =
其实只要做过 SPOJ DQUERY 的应该都知道吧。。。~~然而我没做过~~
反正就是反着插进去插过的先删除就行了。。。
于是我又犯了一个很傻逼的错误。。。我以为一个一个读插进去和全读了反着插进去是一样的。。。从晚上WA到早上根本想不到是因为这个。。。最近输出很不稳定啊 OTZ

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;

const int N=2e5+5;
const int M=40*N;
int T[N],po[N],a[N];
struct Seg {
    int ls,rs,v;
} tr[M];
int tot,C,n,m;

void read(int &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x=c-'0';
    while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
}

int build(int l,int r)
{
    int rt=++tot;
    tr[rt].v=0;
    if (l==r) {
        tr[rt].ls=tr[rt].rs=0;
        return rt;
    }
    int m=l+r>>1;
    tr[rt].ls=build(l,m);
    tr[rt].rs=build(m+1,r);
    return rt;
}

int update(int rt,int l,int r,int pos,int d)
{
    int newrt=++tot;
    tr[newrt].v=tr[rt].v+d;
    if (l==r) return newrt;
    int m=l+r>>1;
    if (pos<=m) {
        tr[newrt].rs=tr[rt].rs;
        tr[newrt].ls=update(tr[rt].ls,l,m,pos,d);
    } else {
        tr[newrt].ls=tr[rt].ls;
        tr[newrt].rs=update(tr[rt].rs,m+1,r,pos,d);
    }
    return newrt;
}

int getsum(int rt,int l,int r,int L,int R)
{
    if (L<=l&&r<=R) return tr[rt].v;
    int m=l+r>>1;
    int res=0;
    if (L<=m) res+=getsum(tr[rt].ls,l,m,L,R);
    if (m<R) res+=getsum(tr[rt].rs,m+1,r,L,R);
    return res;
}

int query(int rt,int l,int r,int k)
{
    if (l==r) return l;
    int m=l+r>>1;
    int tmp=tr[tr[rt].ls].v;
    if (k<=tmp) return query(tr[rt].ls,l,m,k);
    else return query(tr[rt].rs,m+1,r,k-tmp);
}

void case_init()
{
    tot=0;
    T[n+1]=build(1,n);
    memset(po,-1,sizeof(po));
}

int main()
{
    read(C);
    for (int t=1; t<=C; t++) {
        read(n);
        read(m);
        for (int i=1;i<=n;i++)
            read(a[i]);
        case_init();
        for (int i=n; i; i--) {
            if (po[a[i]]==-1) {
                T[i]=update(T[i+1],1,n,i,1);
            } else {
                int tmp=update(T[i+1],1,n,po[a[i]],-1);
                T[i]=update(tmp,1,n,i,1);
            }
            po[a[i]]=i;
        }
        printf("Case #%d:",t);
        int ans=0;
        while (m--) {
            int p,q,l,r;
            read(p);
            read(q);
            p=(p+ans)%n+1;
            q=(q+ans)%n+1;
            l=min(p,q);
            r=max(p,q);
            int k=getsum(T[l],1,n,l,r);
            ans=query(T[l],1,n,(k+1)/2);
            printf(" %d",ans);
        }
        puts("");
    }
    return 0;
}

阅读全文 »

弱校联盟 2016 四川省赛

发表于 2016-10-02 更新于 2022-10-11 Valine：

。。。反正都不会。。。反正都是抄的。。。

Nearest Neighbor Search

水题。。。刚开始我还写了个判断在不在长方体之内的函数。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
struct point {
    int x,y,z;
} p[4];

inline long long sqr(long long x)
{
    return x*x;
}

int main()
{
    for (int i=0; i<3; i++)
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
    int x,y,z;
    if (p[0].x<p[1].x) x=p[1].x;
    else if (p[0].x>p[2].x) x=p[2].x;
    else x=p[0].x;
    if (p[0].y<p[1].y) y=p[1].y;
    else if (p[0].y>p[2].y) y=p[2].y;
    else y=p[0].y;
    if (p[0].z<p[1].z) z=p[1].z;
    else if (p[0].z>p[2].z) z=p[2].z;
    else z=p[0].z;
    printf("%lld\n",sqr(x-p[0].x)+sqr(y-p[0].y)+sqr(z-p[0].z));
}

Coins

神题。。。根本没想到要分类讨论。。。
就说一下比较难的 $a=0$ $and$ $b\geq 2$ $and$ $c>0$ 的情况：

首先可以放入 $k$ 个 3，那就有 $c$ 种不同的价钱。
考虑到 $b\geq 2$ ，我们可以拿出 $1$ 个 3，放入 $1$ 个 2，价钱会减 1，或者放入 $2$ 个 2，价钱会加 1，这样多了 $2c$ 种价钱。
下面可以先放入 $c$ 个 3（所有 3），再放入 $k$ 个 2，这样多了 $b$ 种价钱。
而当 $k\gt 2$ 时，我们发现【不，并没有 ˊ_>ˋ】还可以拿出 $1$ 个 3，并且不会重复。
放入所有 3，放入了 $k$ 个 2：$3c+2,3c+4,3c+6,3c+8,…$
除了前 2 个（$3c\pm 1$ 已经出现过了）都可以拿出 1 个 3：$3c+3,3c+5,…$
所以又多了 $b-2$ 种价钱。

总数为 $3c+2b-2$
其余看代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll solve(ll a,ll b,ll c)
{
    if (a>=2) {
        return 3*c+2*b+a;
    }
    if (a==1) {
        if (b>=1) return 3*c+2*b+a;
        if (b==0) return 2*c+a;
    }
    if (a==0) {
        if (b>=2)
            if (c==0) return b;
            else return 3*c+2*b-2;
        if (b==1) return 2*c+b;
        if (b==0) return c;
    }
}

int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    printf("%lld\n",solve(a,b,c));
}

Matrix Transformation

阅读全文 »

hdu 5546 Ancient Go 搜索

发表于 2016-09-30 更新于 2022-10-11 Valine：

Ancient Go

题意：给出棋盘，轮到 x 这一方下子，问能不能至少提掉一个 o 方的子。
题解：枚举每一个 o ，bfs 一下看看周围的 . 是不是少于等于 1 个，太简单辣！

考虑到要优化时间，枚举每一个 o 的时候直接把那一片 o 都标记了，这样就省了很多次 bfs 。
不得不说这真的是一道打击信心的题。。。。。。
虽然没有WA很多次，，，但是就是想不出来为什么WA。。。
实际上。。。数 . 的时候有些 . 会被数两次。。。比如：

1
2
3

.....xoox
.......ox
.......x.

因为从我的思路来讲，标记一片 o 是为了让下次不再搜索，但是 . 在下次还是会用到的，所以肯定不会标记。这样的后果就是搜索到 . 时其实并不知道它在这一次有没有被搜到过。。。
正确的做法要给 . 加上标记，可以用时间戳标记，代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
char map[10][10];
int b[10][10];
int index;

int bfs(int x,int y)
{
    int res=0;
    queue<PII> Q;
    Q.push(PII(x,y));
    b[x][y]=1;
    while (!Q.empty()) {
        int x=Q.front().first;
        int y=Q.front().second;
        Q.pop();
        for (int i=0;i<4;i++) {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if (xx<0||yy<0||xx>=9||yy>=9) continue;
            if (map[xx][yy]=='.') {
                if (b[xx][yy]!=index) {
                    ++res;
                    b[xx][yy]=index;
                }
                /*********WA*********
                ++res;
                ********************/ 
            } else if (map[xx][yy]=='o'&&!b[xx][yy]) {
                b[xx][yy]=1;
                Q.push(PII(xx,yy));
            }
        }
    }
    return res;
}

int main()
{
    int T,t=0;
    scanf("%d",&T);
WCON:
    while (++t<=T) {
        for (int i=0;i<9;i++)
            scanf("%s",map[i]);
        printf("Case #%d: ",t);
        memset(b,0,sizeof(b));
        index=0;
        for (int i=0;i<9;i++) {
            for (int j=0;j<9;j++) {
                if (map[i][j]=='o'&&!b[i][j]) {
                    ++index;
                    int tmp=bfs(i,j);
                    if (tmp<=1) {
                        puts("Can kill in one move!!!");
                        goto WCON;
                    }
                }
            }
        }
        puts("Can not kill in one move!!!");
    }
}

而在我上网查题解的时候又看到了另一种想法

这个想法就回避了数 . 的问题，当然我估计这个想法比较小众。。。因为大家觉得性能太差了。。。
所以说这题。。。出在现场赛还算是公平吧。。。~~就是太打击信心了 :-( ！！~~

阅读全文 »

hdu 3727 Jewel 主席树

发表于 2016-09-29 更新于 2022-10-11 Valine：

最近在学主席树。。。反正感觉挺神奇的。。。
我高中想学，但是并没有看懂。~~可能是他们写的太屎了~~
kuangbin的板子也不太行。
poj 2104 那题入门，程序是没错
但是太耦合了，变量也有点意义不明。。。
于是我又去找了找。。。发现应该给一个比利比利的链接

qsc菊苣教你主席树啊
这个讲的不错啊就是p2的时候码力实在太强。。。只能暂停学姿势
然后我又去找最佳实践，，，
但是感觉都有不舒服的地方。。。只能自己瞎编着上了
【知道最佳实践的一定要告诉我啊

Jewel

题意：初始的链为空，需要支持以下四个操作：略。
题解：Query_1 和 Query_3 很明显就是静态第k小，又因为是权值线段树，Query_2 就是前缀和呗。。。
因为数太大啦，再套个离散化，要离散化首先要把操作离线。~~ok，这样这题就AC啦~~
这题昨天晚上从开始读到调完正好一小时，而且中间也跟室友吹吹逼啥的
感觉自己码力很有进步啊！然后交上去WA了。。。
当然我其实知道一个WA点，，，answer 没改成 longlong
满怀信心，再交。。。又WA了。。。
刚刚又xjb交了一遍，还是WA
然后去查题解。。。发现我好像有什么地方理解错了。。。

… and the amounts of “Query_1”, “Query_2” and “Query_3” are all less than 35000.

三种询问的数量都不超过35000。。。我似乎理解成和了？？？？
。。。代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100001;
const int M=35000*3+N;
struct chair {
    int ls,rs,sum;
} T[M*40];
struct oper {
    int op,x,y,k;
} op[M];
int root[N],A[N];
long long ans[4];

int index;
int update(int rt,int l,int r,int x)
{
    int newroot=++index;
    T[newroot]=T[rt];
    T[newroot].sum++;
    if (l==r) return newroot;
    int m=l+r>>1;
    if (x<=m) T[newroot].ls=update(T[newroot].ls,l,m,x);
    else T[newroot].rs=update(T[newroot].rs,m+1,r,x);
    return newroot;
}

int query(int x,int y,int l,int r,int k)
{
    if (l==r) return l;
    int m=l+r>>1;
    int lsz=T[T[y].ls].sum-T[T[x].ls].sum;
    if (lsz>=k) {
        return query(T[x].ls,T[y].ls,l,m,k);
    } else {
        return query(T[x].rs,T[y].rs,m+1,r,k-lsz);
    }
}

int getrank(int rt,int l,int r,int L,int R)
{
    if (L<=l&&r<=R) return T[rt].sum;
    int m=l+r>>1;
    int res=0;
    if (L<=m) res+=getrank(T[rt].ls,l,m,L,R);
    if (m<R) res+=getrank(T[rt].rs,m+1,r,L,R);
    return res;
}

void case_init()
{
    index=root[0]=0;
    T[0].ls=T[0].rs=T[0].sum=0;
    memset(ans,0,sizeof(ans));
}

int main()
{
    int cas=0;
    int q;
    while (scanf("%d",&q)!=EOF) {
        int n=0;
        case_init();
        for (int i=1;i<=q;i++) {
            char s[10];
            scanf("%s",s);
            if (s[0]=='I') {
                op[i].op=0;
                scanf("%d",&op[i].x);
                A[++n]=op[i].x;
            } else if (s[6]=='1') {
                op[i].op=1;
                scanf("%d%d%d",&op[i].x,&op[i].y,&op[i].k);
            } else if (s[6]=='2') {
                op[i].op=2;
                scanf("%d",&op[i].x);
            } else if (s[6]=='3') {
                op[i].op=3;
                scanf("%d",&op[i].k);
            }
        }
        sort(A+1,A+1+n);
        
        int tot=0;
        for (int i=1;i<=q;i++) {
            if (op[i].op==0) {
                tot++;
                root[tot]=update(root[tot-1],1,n,lower_bound(A+1,A+1+n,op[i].x)-A);
            } else {
                long long tmp=0;
                if (op[i].op==1) 
                    tmp=A[query(root[op[i].x-1],root[op[i].y],1,n,op[i].k)];
                if (op[i].op==2) 
                    tmp=getrank(root[tot],1,n,1,lower_bound(A+1,A+1+n,op[i].x)-A);
                if (op[i].op==3) 
                    tmp=A[query(root[0],root[tot],1,n,op[i].k)];
                ans[op[i].op]+=tmp;
            }
        }
        
        printf("Case %d:\n",++cas);
        for (int i=1;i<4;i++)
            printf("%lld\n",ans[i]);
    }
}

阅读全文 »

HHUACM 综合训练2

发表于 2016-09-22 更新于 2022-10-11 Valine：

本次综合训练主要是2013年的大连online的题目，有难有易，其中题意不太清楚和要求非常高的题目就直接剔除了。这样题数少了，于是又加了2题2016年大连online的我觉得挺不错的题目。后来发现知识点有点重叠，不过训练一下也无妨。

Find the maximum

题意：给出 $N$ 求出最小的 $2\leq n\leq N$ 使得 $n/\varphi(n)$ 最大。
题解：做这题首先要知道 $\varphi(n)$ 的计算式（不作证明）: $\varphi(n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})…(1-\frac{1}{p_{k}})$
$$\therefore n/\varphi(n)=\frac{1}{(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})…(1-\frac{1}{p_{k}})}$$ $$=\frac{1}{\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}…\frac{p_k-1}{p_k}}$$ $$=\frac{p_1}{p_1-1}\frac{p_2}{p_2-1}…\frac{p_k}{p_k-1}$$ $$=(1+\frac{1}{p_1-1})(1+\frac{1}{p_2-1})…(1+\frac{1}{p_k-1})$$
其中 $p_1,p_2,…p_k$ 为 $n$ 的质因子。（考虑到大家提交的很多代码都是打表，这里我写的比较详细）

明显地：

$p_1,p_2,…p_k$ 越小，$n$ 越小，而且 $n/\varphi(n)$ 越大；
$p_1,p_2,…p_k$ 的次方数没有贡献。
所以，只需要把最小的那些质数乘起来，就能得到满足条件的 $n$
为了增加(编程)难度，这题又加入了高精度，套用模板，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX=1000000;
int pr[100000],pt=0;
bool f[MAX];
char s[110];
struct BigInt {
    const static int mod = 10000;
    const static int DLEN = 4;
    int a[100],len;
    BigInt() {
        memset(a,0,sizeof(a));
        len = 1;
    }
    BigInt(int v) {
        memset(a,0,sizeof(a));
        len = 0;
        do {
            a[len++] = v%mod;
            v /= mod;
        } while(v);
    }
    BigInt(const char s[]) {
        memset(a,0,sizeof(a));
        int L = strlen(s);
        len = L/DLEN;
        if(L%DLEN)len++;
        int index = 0;
        for(int i = L-1; i >= 0; i -= DLEN) {
            int t = 0;
            int k = i - DLEN + 1;
            if(k < 0)k = 0;
            for(int j = k; j <= i; j++)
                t = t*10 + s[j] - '0';
            a[index++] = t;
        }
    }
    BigInt operator +(const BigInt &b)const {
        BigInt res;
        res.len = max(len,b.len);
        for(int i = 0; i <= res.len; i++)
            res.a[i] = 0;
        for(int i = 0; i < res.len; i++) {
            res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
            res.a[i+1] += res.a[i]/mod;
            res.a[i] %= mod;
        }
        if(res.a[res.len] > 0)res.len++;
        return res;
    }
    BigInt operator *(const BigInt &b)const {
        BigInt res;
        for(int i = 0; i < len; i++) {
            int up = 0;
            for(int j = 0; j < b.len; j++) {
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
                res.a[i+j] = temp%mod;
                up = temp/mod;
            }
            if(up != 0)
                res.a[i + b.len] = up;
        }
        res.len = len + b.len;
        while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--;
        return res;
    }
    bool operator >(const BigInt &b)const {
        if (len==b.len) {
            int k=len-1;
            while (k&&a[k]==b.a[k]) k--;
            if (k<0) return false;
            return a[k]>b.a[k];
        }
        return len>b.len;
    }
    void output() {
        printf("%d",a[len-1]);
        for(int i = len-2; i >=0 ; i--)
            printf("%04d",a[i]);
        printf("\n");
    }
};

void init_pr()
{
    for (int i=2;i<MAX;i++) {
        if (!f[i]) pr[++pt]=i;
        for (int j=1;j<=pt;j++) {
            if (i*pr[j]>=MAX) break;
            f[i*pr[j]]=1;
            if (i%pr[j]==0) break;
        }
    }
}

int main()
{
    init_pr();
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%s",s);
        BigInt n(s);
        BigInt a(1),b(1);
        for (int i=1;i<=pt;i++) {
            BigInt tmp(pr[i]);
            b=a*tmp;
            if (b>n) break;
            a=b;
        }
        a.output();
    }
    return 0;
}

The Frog’s Games

题意：青蛙要跳过一条长为 $L$ ，两岸之间有 $n$ 块石头的河，最多只能跳 $m$ 次，求青蛙至少需要的跳跃能力（跳一次的最大长度）。
题解：可以发现，最后的答案具有单调性，即，若跳跃能力 $k$ 可以跳过这条河，那么跳跃能力 $x(x\geq k)$ 一定能跳过这条河。
由此，使用二分答案可以解决，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=500010;
int a[N];
int L,n,m;

bool check(int l)
{
    int cnt=0,pre=0;
    for (int i=1;i<=n+1;) {
        while (pre+l>=a[i]&&i<=n+1) i++;
        pre=a[i-1];
        if (++cnt>m) return false;
    }
    return true;
}

int bs(int l,int r)
{
    while (l<r) {
        int m=(l+r)>>1;
        if (check(m)) r=m;
        else l=m+1;
    }
    return l;
}

int main()
{
    while (scanf("%d%d%d",&L,&n,&m)!=EOF) {
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        int l=L,r=L;a[n+1]=L;
        for (int i=1;i<=n+1;i++)
            l=min(a[i]-a[i-1],l);
        printf("%d\n",bs(l,r));
    }
    return 0;
}

Different GCD Subarray Query

阅读全文 »

hdu 4417 Super Mario

发表于 2016-09-08 更新于 2022-10-11 Valine：

这题很明显离线做比较水。。。

把询问和每块砖都按高度排序
不断向树状数组插入满足条件的砖的位置
对每个询问求在 [L,R] 的区间和
也就是把前缀和减一减
【树状数组不能有0，所以传参之前我都加了1。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1e5+5;
const int MAX=N;
struct query {
    int l,r,h,id;
} q[N];
struct brick {
    int h,pos;
} a[N];
int c[MAX],ans[N];

struct cmp {
    template<typename T> 
    bool operator()(const T &a,const T &b)
    {
        return a.h<b.h;
    }
};

void ins(int x,int d)
{
    for (;x<MAX;x+=x&(-x)) {
        c[x]+=d;
    }
}

int query(int x)
{
    int res=0;
    for (;x;x-=x&(-x)) {
        res+=c[x];
    }
    return res;
}

int main()
{
    int T,n,m;
    scanf("%d",&T);
    for (int t=1;t<=T;t++) {
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++) {
            scanf("%d",&a[i].h);
            a[i].pos=i;
        }
        for (int i=0;i<m;i++) {
            scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);
            q[i].id=i;
        }
        sort(a,a+n,cmp());
        sort(q,q+m,cmp());
        int k=0;
        for (int i=0;i<m;i++) {
            for (;k<n&&a[k].h<=q[i].h;k++)
                ins(a[k].pos+1,1);
            ans[q[i].id]=query(q[i].r+1)-query(q[i].l-1+1);
        }
        printf("Case %d:\n",t);
        for (int i=0;i<m;i++)
            printf("%d\n",ans[i]);
        memset(c,0,sizeof(c));
    }
    return 0;
}

阅读全文 »

poj 3690 Constellations

发表于 2016-09-08 更新于 2022-10-11 Valine：

最近在翻 ICPC online 的题。。。
终于找到一个能做的水题结果WA了七八次。。。
可能我果然还是不会C/C++语言吧 OTZ

行状压和列状压都行吧。。。
然后我就暴力枚举右下角
感觉写的比能查到的题解好看一点。。。
【差点就全服最短了2333333

goto 什么的要谨慎。。。不行就写成函数嘛

#include <cstdio>
typedef long long ll;
int n,m,t,p,q;
char map[1010][1010],pat[60][60];
ll ro[1010][1010],mat[60];
int main()
{
    int cas=0;
    while (scanf("%d%d%d%d%d",&n,&m,&t,&p,&q),n) {
        for (int i=0;i<n;i++)
            scanf("%s",map[i]);
        ll mask=(1LL<<q)-1;//就因为只写了1没写LL结果WA了两小时。。。 
        for (int i=0;i<n;i++) {
            ll tmp=0;
            for (int j=0;j<m;j++)
                ro[i][j]=tmp=((tmp<<1)|(map[i][j]=='*'))&mask;
        }
        int ans=0;
WCON:
        while (t--) {
            for (int i=0;i<p;i++)
                scanf("%s",pat[i]);
            for (int i=0;i<p;i++) {
                ll tmp=0;
                for (int j=0;j<q;j++)
                    tmp=(tmp<<1)|(pat[i][j]=='*');
                mat[i]=tmp;
            }
            for (int i=p-1;i<n;i++) {
                for (int j=q-1;j<m;j++)
                    if (ro[i][j]==mat[p-1]) {
                        int k=0;
                        while (k<p&&ro[i-k][j]==mat[p-1-k]) k++;
                        if (k==p) {
                            ans++;
                            goto WCON;
                        }
                    }
            }
        }
        printf("Case %d: %d\n",++cas,ans);
    }
    return 0;
}

阅读全文 »

hdu 5828 Rikka with Sequence

发表于 2016-08-20 更新于 2022-10-11 Valine：

多校8的一道题。。。【看标题识出题人 ←_←
非常蛋疼的一道题，官方题解根本不知道在说什么，标程写得跟坨屎一样= =
先贴一份比赛中菊苣AC的代码

/************************************************
 *Author        :mathon
 *Email         :luoxinchen96@gmail.com
*************************************************/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define xx first
#define yy second
#define pr(x) cout << #x << " " << x << " "
#define prln(x) cout << #x << " " << x << endl
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
template<class T> inline T lowbit(T x) { return x & (-x); }
const int MAXN = 1e5 + 5;
int A[MAXN];
struct SegT {
    ll sum[MAXN<<2];
    ll is_same[MAXN<<2], lazy[MAXN<<2];
    void init() {
        memset(sum, 0, sizeof(sum));
        memset(is_same, 0, sizeof(is_same));
        memset(lazy, 0, sizeof(lazy));
    }
   
    void push_up(int rt) {
        if(is_same[rt << 1] && is_same[rt << 1 | 1] &&
                is_same[rt << 1] == is_same[rt << 1 | 1]) {
            is_same[rt] = is_same[rt << 1];
        } else {
            is_same[rt] = 0;
        }
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    void push_down(int rt, int l, int r) {
        int m = (l + r) >> 1;
        if(is_same[rt]) {
            is_same[rt << 1] = is_same[rt];
            is_same[rt << 1 | 1] = is_same[rt];
            sum[rt << 1] = is_same[rt] * (m - l + 1);
            sum[rt << 1 | 1] = is_same[rt] * (r - m);
        } else {
            lazy[rt << 1] += lazy[rt];
            lazy[rt << 1 | 1] += lazy[rt];
            sum[rt << 1] += lazy[rt] * (m - l + 1);
            sum[rt << 1 | 1] += lazy[rt] * (r - m);
            lazy[rt] = 0;
            if(is_same[rt << 1]) {
                is_same[rt << 1] += lazy[rt << 1];
                lazy[rt << 1] = 0;
            }
            if(is_same[rt << 1 | 1]) {
                is_same[rt << 1 | 1] += lazy[rt << 1 | 1];
                lazy[rt << 1 | 1] = 0;
            }
        }
    }
    
    void build(int l, int r, int rt) {
        if(l == r) {
            sum[rt] = A[l];
            is_same[rt] = A[l];
            return;
        }
        int m = (l + r) >> 1;
        build(lson);
        build(rson);
        push_up(rt);
    }
    void update1(int L, int R, int x, int l, int r, int rt) {
        if(L <= l && r <= R) {
            sum[rt] += (ll)x * (r - l + 1);
            if(is_same[rt]) {
                is_same[rt] += x;
            } else {
                lazy[rt] += x;
            }
            return;
        }
        int m = (l + r) >> 1;
        push_down(rt, l, r);
        if(m >= L) update1(L, R, x, lson);
        if(m < R) update1(L, R, x, rson);
        push_up(rt);
    }
    void update2(int L, int R, int l, int r, int rt) {
        if(L <= l && r <= R && is_same[rt]) {
            is_same[rt] = sqrt(is_same[rt]);
            sum[rt] = is_same[rt] * (r - l + 1);
            return;
        }
        int m = (l + r) >> 1;
        push_down(rt, l, r);
        if(m >= L) update2(L, R, lson);
        if(m < R) update2(L, R, rson);
        push_up(rt);
    }
    ll query(int L, int R, int l, int r, int rt) {
        if(L <= l && r <= R) {
            return sum[rt];
        }
        int m = (l + r) >> 1;
        push_down(rt, l, r);
        ll res = 0;
        if(m >= L) res += query(L, R, lson);
        if(m <  R) res += query(L, R, rson);
        return res;
    }
}seg;
int main(void) {
#ifdef MATHON
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int T; scanf("%d", &T);
    while(T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        seg.init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
        }
        seg.build(1, n, 1);
        for (int i = 0; i < m; i++) {
            int op;
            scanf("%d", &op);
            if(op == 1) {
                int l, r, x;
                scanf("%d%d%d", &l, &r, &x);
                seg.update1(l, r, x, 1, n, 1);
            } else if(op == 2) {
                int l, r;
                scanf("%d%d", &l, &r);
                seg.update2(l, r, 1, n, 1);
            } else if(op == 3) {
                int l, r;
                scanf("%d%d", &l, &r);
                ll res = seg.query(l, r, 1, n, 1);
                printf("%lld\n", res);
            }
        }
    }
    return 0;
}

这个用到了记录相等的一段，这样就不用每次更新到叶子了。
赛后题库里的数据加强了，我用这种方法T了好几遍只好去找新的姿势了。。。

应该考虑一下记相等到底有什么作用。
实际上就是把区间开根号变成了类似于区间增减的东西，然后就可以 lazy-tag。
所以用一种奇怪的姿势（反正我是想不出来。。。）
对于一个区间，可以分为三种情况：

区间内所有数相等
区间内极差大于1
区间内极差等于1

情况1开根号相当于区间增减。
情况2会转化成3或者1。
情况3，开根号后极差可能相等，转化为情况1。
如果仍然差一，此时显然区间所有数减去了相同的值。

又是改了一遍才过。。。OTZ

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long llint;
const int N=1e5+5;
llint add[N<<2],sum[N<<2];
llint mav[N<<2],miv[N<<2];
void push_up(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    mav[rt]=max(mav[rt<<1],mav[rt<<1|1]);
    miv[rt]=min(miv[rt<<1],miv[rt<<1|1]);
}
void push_down(int rt,int l,int r)
{
    if (add[rt]) {
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        mav[rt<<1]+=add[rt];
        mav[rt<<1|1]+=add[rt];
        miv[rt<<1]+=add[rt];
        miv[rt<<1|1]+=add[rt];
        int m=(l+r)>>1;
        sum[rt<<1]+=add[rt]*(m-l+1);
        sum[rt<<1|1]+=add[rt]*(r-m);
        add[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    if (l==r) {
        scanf("%I64d",&sum[rt]);
        mav[rt]=miv[rt]=sum[rt];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int L,int R,int d,int l,int r,int rt)
{
    if (L<=l&&r<=R) {
        add[rt]+=d;
        mav[rt]+=d;
        miv[rt]+=d;
        sum[rt]+=(llint)d*(r-l+1);
        return ;
    }
    push_down(rt,l,r);
    int m=(l+r)>>1;
    if (L<=m) update(L,R,d,lson);
    if (m<R) update(L,R,d,rson);
    push_up(rt);
}
void update2(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R) {
        if (mav[rt]==miv[rt]) {
            llint tmp=sqrt(mav[rt]);
            add[rt]+=tmp-mav[rt];
            sum[rt]+=(llint)(tmp-mav[rt])*(r-l+1);
            mav[rt]=miv[rt]=tmp;
            return;
        } else if (mav[rt]==miv[rt]+1) {
            llint t1=sqrt(mav[rt]);
            llint t2=sqrt(miv[rt]);
            if (t1==t2+1) {
                add[rt]+=t1-mav[rt];
                sum[rt]+=(llint)(t1-mav[rt])*(r-l+1);
                mav[rt]=t1;
                miv[rt]=t2;
                return;
            }
        }
    }
    push_down(rt,l,r);
    int m=(l+r)>>1;
    if (L<=m) update2(L,R,lson);
    if (m<R) update2(L,R,rson);
    push_up(rt);
}
llint query(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R) {
        return sum[rt];
    }
    push_down(rt,l,r);
    int m=(l+r)>>1;
    llint res=0;
    if (L<=m) res+=query(L,R,lson);
    if (m<R) res+=query(L,R,rson);
    return res;
}
void init()
{
    memset(add,0,sizeof(add));
}
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        init();
        build(1,n,1);
        int k,l,r,x;
        while (m--) {
            scanf("%d%d%d",&k,&l,&r);
            if (k==1) {
                scanf("%d",&x);
                update(l,r,x,1,n,1);
            } else if (k==2) {
                update2(l,r,1,n,1);
            } else {
                printf("%I64d\n",query(l,r,1,n,1));
            }
        }
    }
    return 0;
}

啥？你说复杂度？
我怎么知道= =

阅读全文 »

—— Summon, Light!

hdu 5875 Function ST+二分

Function

hdu 5728 PowMod 数论

[PowMod][1]

hdu 5919 Sequence II 主席树

Sequence II

弱校联盟 2016 四川省赛

Nearest Neighbor Search

Coins

Matrix Transformation

hdu 5546 Ancient Go 搜索

Ancient Go

hdu 3727 Jewel 主席树

Jewel

HHUACM 综合训练2

Find the maximum

The Frog’s Games

Different GCD Subarray Query

hdu 4417 Super Mario

poj 3690 Constellations

hdu 5828 Rikka with Sequence