月度归档：2013年10月

[POJ 1988]

并查集。

题意是，原有30,000个栈，每个栈中有一个cube，总共最多100,000个操作，每个操作可以是将一个栈叠到另一个上，或者是求某个cube下方有多少个cube。

很明显的”由cube指定的stack号来作叠置操作”暗示了要用并查集的。但以前写过的并查集仅能够实现（1）路径压缩；（2）按秩合并。也即f[i]表示的值可以是（1）栈编号(当f[i]>=0；（2）栈大小(当f[i]<0)。由此，不难推出，如果额外增设一个p[i]，记录每个cube到栈顶间有多少个cube，那么就可以有：栈大小 – 上方cube数 – 1 = 下方cube数。进一步分析p[i]的更新方式，每次作union(a,b)时，是将a整个放在b上的，也即此时p[b]=f[a]。但如果要使p[i]值正确，压缩路径前要记录原父cube，递归处理压缩路径后，将父cube的p值累加到本cube的p值上。跑出来只有500+ms，改成非递归可能才会快点。

#include<cstdio>
#include<cstring>

char s[2];
int m,f[30000],p[30000];

int fi(int i)
{
    if(f[i]<0) return i;
    int j=f[i];
    f[i]=fi(f[i]);
    p[i]+=p[j];
    return f[i];
}

void un(int a,int b)
{
    int fa=fi(a),fb=fi(b);
    p[fb]=f[fa];
    f[fa]+=f[fb];
    f[fb]=fa;
}

void init()
{
    memset(f,-1,sizeof f);
    memset(p,0,sizeof p);
}

void solve()
{
    int i,j,k,l;
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='M')
        {
            scanf("%d%d",&i,&j);
            un(i-1,j-1);
        }
        else
        {
            scanf("%d",&i);
            i--;
            j=fi(i);
            printf("%d\n",p[i]-f[j]-1);
        }
    }
}

int main()
{
    while(~scanf("%d",&m))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

char s[2];

int m,f[30000],p[30000];

int fi(int i)

{

if(f[i]<0) return i;

int j=f[i];

f[i]=fi(f[i]);

p[i]+=p[j];

return f[i];

}

void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

p[fb]=f[fa];

f[fa]+=f[fb];

f[fb]=fa;

}

void init()

{

memset(f,-1,sizeof f);

memset(p,0,sizeof p);

}

void solve()

{

int i,j,k,l;

while(m--)

{

scanf("%s",s);

if(s[0]=='M')

{

scanf("%d%d",&i,&j);

un(i-1,j-1);

}

else

{

scanf("%d",&i);

i--;

j=fi(i);

printf("%d\n",p[i]-f[j]-1);

}

int main()

{

while(~scanf("%d",&m))

{

init();

solve();

}

return 0;

}

[POJ 1177]

发表回复

Picture

题意大概是，给出N个矩形的描述，矩形间可能有重叠，问最后图形的总周长。

这题和早上做的November Rain都被人分类成线段树，但我愣是没有想明白，这个线段树可以怎么用。也都是数组处理了一下就A了。

说说这题，首先周长可以划分为平行于x轴和平行与y轴两部分。这两部分是独立的，可以分类处理，且处理方式类似。下面以与x轴平行为例说明。

首先将所有点坐标离散化，然后用一个struct数组，记录每条边的：y坐标、起止x离散坐标、下边界标记b（是某矩形下边界则为1，否则为0）。然后将2N条边先按y从小到大，再按x从小到大排序。初始化一个全0的数组t，大小为离散化x坐标的个数，表示某段边被覆盖的次数。然后遍历struct数组，对每条边，更新其包含的各线段j的覆盖情况，若边的b==1，则t[j]++，若此时t[j]==1则表示为图形的下边界，为周长的一部分；若边的b==0，则t[j]–，若此时t[j]==0则表示为图形的上边界，也为周长的一部分。

与Y轴平行的边，处理方式类似。由此便能在O(2N*lg(2N)+2NK)的时间内计算完整个图形的周长了，这里K是每条边包含离散线段的数目。貌似K最多是O(N)的，但题目没有这么刁钻的数据，最后也就跑了16MS。

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

int n,r[5000][4],ei[20001],er[10000],d[10000],erl,pl,sum;
int t[20001],tl;

struct P
{
    int f,es,ed;
    char b;
    bool operator < (const P &p) const
    {
        if(f<p.f) return 1;
        if(f>p.f) return 0;
        return es<p.es;
    }
}p[10000];

void init()
{
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&r[i][0],&r[i][1],&r[i][2],&r[i][3]);
        r[i][0]+=10000; r[i][1]+=10000;
        r[i][2]+=10000; r[i][3]+=10000;
    }
    sum=0;
}

void solve()
{
    int i,j,k,l;
    for(i=tl=0;i<n;i++)
    {
        t[tl++]=r[i][0]; t[tl++]=r[i][2];
    }
    sort(t,t+tl);
    ei[t[0]]=0;
    er[0]=t[0];
    for(i=erl=1;i<tl;i++)
    {
        if(t[i]==t[i-1])
            continue;
        ei[t[i]]=erl;
        er[erl]=t[i];
        d[erl]=er[erl]-er[erl-1];
        erl++;
    }
    for(i=pl=0;i<n;i++)
    {
        p[pl].f=r[i][1]; p[pl].es=ei[r[i][0]];
        p[pl].ed=ei[r[i][2]]; p[pl].b=1; pl++;
        p[pl].f=r[i][3]; p[pl].es=ei[r[i][0]];
        p[pl].ed=ei[r[i][2]]; p[pl].b=0; pl++;
    }
    sort(p,p+pl);
    memset(t,0,sizeof t);
    for(i=0;i<pl;i++)
    {
        if(p[i].b)
        {
            for(j=p[i].es+1;j<=p[i].ed;j++)
            {
                t[j]++;
                if(t[j]==1)
                    sum+=d[j];
            }
        }
        else
        {
            for(j=p[i].es+1;j<=p[i].ed;j++)
            {
                t[j]--;
                if(t[j]==0)
                    sum+=d[j];
            }
        }
    }
    for(i=tl=0;i<n;i++)
    {
        t[tl++]=r[i][1]; t[tl++]=r[i][3];
    }
    sort(t,t+tl);
    ei[t[0]]=0;
    er[0]=t[0];
    for(i=erl=1;i<tl;i++)
    {
        if(t[i]==t[i-1])
            continue;
        ei[t[i]]=erl;
        er[erl]=t[i];
        d[erl]=er[erl]-er[erl-1];
        erl++;
    }
    for(i=pl=0;i<n;i++)
    {
        p[pl].f=r[i][0]; p[pl].es=ei[r[i][1]];
        p[pl].ed=ei[r[i][3]]; p[pl].b=1; pl++;
        p[pl].f=r[i][2]; p[pl].es=ei[r[i][1]];
        p[pl].ed=ei[r[i][3]]; p[pl].b=0; pl++;
    }
    sort(p,p+pl);
    memset(t,0,sizeof t);
    for(i=0;i<pl;i++)
    {
        if(p[i].b)
        {
            for(j=p[i].es+1;j<=p[i].ed;j++)
            {
                t[j]++;
                if(t[j]==1)
                    sum+=d[j];
            }
        }
        else
        {
            for(j=p[i].es+1;j<=p[i].ed;j++)
            {
                t[j]--;
                if(t[j]==0)
                    sum+=d[j];
            }
        }
    }
    printf("%d\n",sum);
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        solve();
    }
    return 0;
}

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

128

129

130

131

132

133

134

135

136

137

138

139

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,r[5000][4],ei[20001],er[10000],d[10000],erl,pl,sum;

int t[20001],tl;

struct P

{

int f,es,ed;

char b;

bool operator < (const P &p) const

{

if(f<p.f) return 1;

if(f>p.f) return 0;

return es<p.es;

}

}p[10000];

void init()

{

int i;

for(i=0;i<n;i++)

{

scanf("%d%d%d%d",&r[i][0],&r[i][1],&r[i][2],&r[i][3]);

r[i][0]+=10000; r[i][1]+=10000;

r[i][2]+=10000; r[i][3]+=10000;

}

sum=0;

}

void solve()

{

int i,j,k,l;

for(i=tl=0;i<n;i++)

{

t[tl++]=r[i][0]; t[tl++]=r[i][2];

}

sort(t,t+tl);

ei[t[0]]=0;

er[0]=t[0];

for(i=erl=1;i<tl;i++)

{

if(t[i]==t[i-1])

continue;

ei[t[i]]=erl;

er[erl]=t[i];

d[erl]=er[erl]-er[erl-1];

erl++;

}

for(i=pl=0;i<n;i++)

{

p[pl].f=r[i][1]; p[pl].es=ei[r[i][0]];

p[pl].ed=ei[r[i][2]]; p[pl].b=1; pl++;

p[pl].f=r[i][3]; p[pl].es=ei[r[i][0]];

p[pl].ed=ei[r[i][2]]; p[pl].b=0; pl++;

}

sort(p,p+pl);

memset(t,0,sizeof t);

for(i=0;i<pl;i++)

{

if(p[i].b)

{

for(j=p[i].es+1;j<=p[i].ed;j++)

{

t[j]++;

if(t[j]==1)

sum+=d[j];

}

else

{

for(j=p[i].es+1;j<=p[i].ed;j++)

{

t[j]--;

if(t[j]==0)

sum+=d[j];

}

for(i=tl=0;i<n;i++)

{

t[tl++]=r[i][1]; t[tl++]=r[i][3];

}

sort(t,t+tl);

ei[t[0]]=0;

er[0]=t[0];

for(i=erl=1;i<tl;i++)

{

if(t[i]==t[i-1])

continue;

ei[t[i]]=erl;

er[erl]=t[i];

d[erl]=er[erl]-er[erl-1];

erl++;

}

for(i=pl=0;i<n;i++)

{

p[pl].f=r[i][0]; p[pl].es=ei[r[i][1]];

p[pl].ed=ei[r[i][3]]; p[pl].b=1; pl++;

p[pl].f=r[i][2]; p[pl].es=ei[r[i][1]];

p[pl].ed=ei[r[i][3]]; p[pl].b=0; pl++;

}

sort(p,p+pl);

memset(t,0,sizeof t);

for(i=0;i<pl;i++)

{

if(p[i].b)

{

for(j=p[i].es+1;j<=p[i].ed;j++)

{

t[j]++;

if(t[j]==1)

sum+=d[j];

}

else

{

for(j=p[i].es+1;j<=p[i].ed;j++)

{

t[j]--;

if(t[j]==0)

sum+=d[j];

}

printf("%d\n",sum);

}

int main()

{

while(~scanf("%d",&n))

{

init();

solve();

}

return 0;

}

[POJ 2888]

发表回复

Magic Bracelet

数论。

本来这题是在分类表里靠后的位置的，但由于最近在啃具体数学，第四章讲了“莫比乌斯反演”，就顺势把题做一下。

题意是这样的，有一个长度为n的珠串，每个珠子的颜色有m种，但其中有k对颜色是不能相邻的，问在剔除因旋转导致的重复后总共有多少种可能的珠串。

先讲这题的简化版，是POJ 2154，区别在于没有珠子间不能连接的限制。

其基本的思想仍然是Polya定理。但是这里由于n值太大，无法直接枚举出所有的置换群。于是需要考虑将具有相同数量循环节的置换群合并处理。具体的合并方式是要利用到欧拉函数phi()的性质的。总共的置换群有n个，对n的每个因子d，有n/d个循环节的置换群其每个循环节长度为d，而这样的循环群总数是phi(d)个。又因为欧拉函数满足sum_{d\n} phi(d) == n，因此计数式子就可以转化为 (sum_{d\n} phi(d) * n^(n/d)) / n。计算phi(d)的时间复杂度是O(lgd)，而n的因子总数是不超过1000的（最多9个不同因子），n的n/d次方是可以在O(lg(n/d))时间内计算得到的，由此问题便能在合理时间内求解了。

另外就是计算的时候，要注意利用模运算的性质，使用int来处理（比long long快很多），同时尽量减少进行模运算的次数，否则还是会TLE的。

下面是2154的代码：

#include<cstdio>
#include<cstring>
#include<cmath>

#define pl 4000

int n,m,o;
int p[pl]={2,3},pn[pl][2],pnl;

void initp()
{
    int i,j,k,l;
    for(i=2;i<pl;i++)
    {
        for(j=p[i-1]+2;1;j+=2)
        {
            for(k=0,l=sqrt(j);p[k]<=l&&j%p[k];k++);
            if(p[k]>l)
            {
                p[i]=j;
                break;
            }
        }
    }
}

inline int phi(int d)
{
    int i,j,k;
    for(i=0,j=d,k=sqrt(d);p[i]<=k;i++)
        if(d%p[i]==0)
        {
            j-=j/p[i];
            while(d%p[i]==0)
                d/=p[i];
        }
    if(d>1)
        j-=j/d;
    return j%m;
}

inline int pm(int d)
{
    int i,j,k;
    k=n%m;
    for(i=1;i<=d;i<<=1);
    i>>=1;
    for(j=1;i;i>>=1)
    {
        j=j*j%m;
        if(i&d)
            j=j*k%m;
    }
    return j;
}

void init()
{
    int i,j,k,l;
    memset(pn,0,sizeof pn);
    for(i=pnl=0,j=n,k=sqrt(n);p[i]<=k&&j>1;i++)
    {
        if(j%p[i]==0)
        {
            pn[pnl][0]=p[i];
            while(j%p[i]==0)
            {
                j/=p[i];
                pn[pnl][1]++;
            }
            pnl++;
        }
    }
    if(j>1)
    {
        pn[pnl][0]=j;
        pn[pnl][1]=1;
        pnl++;
    }
}

void calc(int i,int d)
{
    if(i==pnl)
    {
        o=(o+phi(d)*pm(n/d-1))%m;
        return;
    }
    int j,k,l;
    for(j=0,k=1;j<=pn[i][1];j++,k*=pn[i][0])
        calc(i+1,d*k);
}

void solve()
{
    o=0;
    calc(0,1);
    printf("%d\n",o);
}

int main()
{
    initp();
    scanf("%*d");
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include<cstdio>

#include<cstring>

#include<cmath>

#define pl 4000

int n,m,o;

int p[pl]={2,3},pn[pl][2],pnl;

void initp()

{

int i,j,k,l;

for(i=2;i<pl;i++)

{

for(j=p[i-1]+2;1;j+=2)

{

for(k=0,l=sqrt(j);p[k]<=l&&j%p[k];k++);

if(p[k]>l)

{

p[i]=j;

break;

}

inline int phi(int d)

{

int i,j,k;

for(i=0,j=d,k=sqrt(d);p[i]<=k;i++)

if(d%p[i]==0)

{

j-=j/p[i];

while(d%p[i]==0)

d/=p[i];

}

if(d>1)

j-=j/d;

return j%m;

}

inline int pm(int d)

{

int i,j,k;

k=n%m;

for(i=1;i<=d;i<<=1);

i>>=1;

for(j=1;i;i>>=1)

{

j=j*j%m;

if(i&d)

j=j*k%m;

}

return j;

}

void init()

{

int i,j,k,l;

memset(pn,0,sizeof pn);

for(i=pnl=0,j=n,k=sqrt(n);p[i]<=k&&j>1;i++)

{

if(j%p[i]==0)

{

pn[pnl][0]=p[i];

while(j%p[i]==0)

{

j/=p[i];

pn[pnl][1]++;

}

pnl++;

}

if(j>1)

{

pn[pnl][0]=j;

pn[pnl][1]=1;

pnl++;

}

void calc(int i,int d)

{

if(i==pnl)

{

o=(o+phi(d)*pm(n/d-1))%m;

return;

}

int j,k,l;

for(j=0,k=1;j<=pn[i][1];j++,k*=pn[i][0])

calc(i+1,d*k);

}

void solve()

{

o=0;

calc(0,1);

printf("%d\n",o);

}

int main()

{

initp();

scanf("%*d");

while(~scanf("%d%d",&n,&m))

{

init();

solve();

}

return 0;

}

回到2888。这题额外增加了珠子间的连接限制，对应的处理方式是这样的：初始化矩阵a[m][m]元素全为1，若i和j不能相邻，则a[i][j]=a[j][i]=0，然后计算b = a^d，则长度为d的珠串其总可能数是sum{b[i][i]}。这里当i<=j时，(a^d)[i][j]表示的是，以种类i开始长度为d，结尾能够与种类j的珠子相连的珠串总数。至于为什么是这样，推一下就明白了。于是这里计数式子就变成了(sum_{d\n} phi(d) * sum{(a^(n/d))[i][i]}) / n。落实到具体实现时，在对n做除法时，要转化成乘以模运算下n的乘法逆元。前面的每一步处理也要控制好在int的范围内以及限制模运算的使用次数。

#include<cstdio>
#include<cstring>
#include<cmath>

#define pl 4000
#define mod 9973

int n,m,o;
int p[pl]={2,3},pn[pl][2],pnl;
int a[10][10],b[10][10],t[10][10];

void initp()
{
    int i,j,k,l;
    for(i=2;i<pl;i++)
    {
        for(j=p[i-1]+2;1;j+=2)
        {
            for(k=0,l=sqrt(j);p[k]<=l&&j%p[k];k++);
            if(p[k]>l)
            {
                p[i]=j;
                break;
            }
        }
    }
}

int phi(int d)
{
    int i,j,k;
    for(i=0,j=d,k=sqrt(d);p[i]<=k;i++)
        if(d%p[i]==0)
        {
            j-=j/p[i];
            while(d%p[i]==0)
                d/=p[i];
        }
    if(d>1)
        j-=j/d;
    return j%mod;
}

void mul(int a[10][10],int b[10][10])
{
    int i,j,k,l;
    memset(t,0,sizeof t);
    for(i=0;i<m;i++)
        for(j=0;j<m;j++)
        {
            for(k=0;k<m;k++)
                t[i][j]+=a[i][k]*b[k][j];
            t[i][j]%=mod;
        }
    memcpy(a,t,sizeof t);
}

int pm(int d)
{
    int i,j,k,l;
    memset(b,0,sizeof b);
    for(i=0;i<m;i++)
        b[i][i]=1;
    for(i=1;i<=d;i<<=1);
    for(i>>=1;i;i>>=1)
    {
        mul(b,b);
        if(i&d)
            mul(b,a);
    }
    for(i=j=0;i<m;i++)
        j+=b[i][i];
    return j%mod;
}

void init()
{
    int i,j,k,l;
    for(i=0;i<m;i++)
        for(j=0;j<m;j++)
            a[i][j]=1;
    while(o--)
    {
        scanf("%d%d",&i,&j);
        a[i-1][j-1]=a[j-1][i-1]=0;
    }
    memset(pn,0,sizeof pn);
    for(i=pnl=0,j=n,k=sqrt(n);p[i]<=k&&j>1;i++)
    {
        if(j%p[i]==0)
        {
            pn[pnl][0]=p[i];
            while(j%p[i]==0)
            {
                j/=p[i];
                pn[pnl][1]++;
            }
            pnl++;
        }
    }
    if(j>1)
    {
        pn[pnl][0]=j;
        pn[pnl][1]=1;
        pnl++;
    }
}

void calc(int i,int d)
{
    if(i==pnl)
    {
        o=(o+phi(d)*pm(n/d))%mod;
        return;
    }
    int j,k,l;
    for(j=0,k=1;j<=pn[i][1];j++,k*=pn[i][0])
        calc(i+1,d*k);
}

void solve()
{
    o=0;
    calc(0,1);
    int i,j;
    for(i=1,j=n%mod;(i*j)%mod!=1;i++);
    printf("%d\n",o*i%mod);
}

int main()
{
    initp();
    scanf("%*d");
    while(~scanf("%d%d%d",&n,&m,&o))
    {
        init();
        solve();
    }
    return 0;
}

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

128

129

130

131

132

133

134

135

136

137

138

139

140

#include<cstdio>

#include<cstring>

#include<cmath>

#define pl 4000

#define mod 9973

int n,m,o;

int p[pl]={2,3},pn[pl][2],pnl;

int a[10][10],b[10][10],t[10][10];

void initp()

{

int i,j,k,l;

for(i=2;i<pl;i++)

{

for(j=p[i-1]+2;1;j+=2)

{

for(k=0,l=sqrt(j);p[k]<=l&&j%p[k];k++);

if(p[k]>l)

{

p[i]=j;

break;

}

int phi(int d)

{

int i,j,k;

for(i=0,j=d,k=sqrt(d);p[i]<=k;i++)

if(d%p[i]==0)

{

j-=j/p[i];

while(d%p[i]==0)

d/=p[i];

}

if(d>1)

j-=j/d;

return j%mod;

}

void mul(int a[10][10],int b[10][10])

{

int i,j,k,l;

memset(t,0,sizeof t);

for(i=0;i<m;i++)

for(j=0;j<m;j++)

{

for(k=0;k<m;k++)

t[i][j]+=a[i][k]*b[k][j];

t[i][j]%=mod;

}

memcpy(a,t,sizeof t);

}

int pm(int d)

{

int i,j,k,l;

memset(b,0,sizeof b);

for(i=0;i<m;i++)

b[i][i]=1;

for(i=1;i<=d;i<<=1);

for(i>>=1;i;i>>=1)

{

mul(b,b);

if(i&d)

mul(b,a);

}

for(i=j=0;i<m;i++)

j+=b[i][i];

return j%mod;

}

void init()

{

int i,j,k,l;

for(i=0;i<m;i++)

for(j=0;j<m;j++)

a[i][j]=1;

while(o--)

{

scanf("%d%d",&i,&j);

a[i-1][j-1]=a[j-1][i-1]=0;

}

memset(pn,0,sizeof pn);

for(i=pnl=0,j=n,k=sqrt(n);p[i]<=k&&j>1;i++)

{

if(j%p[i]==0)

{

pn[pnl][0]=p[i];

while(j%p[i]==0)

{

j/=p[i];

pn[pnl][1]++;

}

pnl++;

}

if(j>1)

{

pn[pnl][0]=j;

pn[pnl][1]=1;

pnl++;

}

void calc(int i,int d)

{

if(i==pnl)

{

o=(o+phi(d)*pm(n/d))%mod;

return;

}

int j,k,l;

for(j=0,k=1;j<=pn[i][1];j++,k*=pn[i][0])

calc(i+1,d*k);

}

void solve()

{

o=0;

calc(0,1);

int i,j;

for(i=1,j=n%mod;(i*j)%mod!=1;i++);

printf("%d\n",o*i%mod);

}

int main()

{

initp();

scanf("%*d");

while(~scanf("%d%d%d",&n,&m,&o))

{

init();

solve();

}

return 0;

}

虽然上面写了这么多但很多都是现学现卖的OTL。不过数论还真是很有意思的东西……

[POJ 3286]

发表回复

How many 0’s?

数学。

比较不擅长的题目类型，虽然一直以来都挺喜欢数学的；）

问的是输入unsigned int m和n，问[m, n]的所有数字打印出来后，总共包含多少个0。

题意非常明确的，其实就是要推出函数calc(d)，能返回0到d所有0的个数，那么calc(n)-calc(m-1)就是结果。

对于某个具体的d，这里基本的思路是将其包含的数按范围划分，例如d=109250时，首先拆成[0, 100000]，[100001, 109000]，[109001, 109200]和[109201, 109250]。那么就可以分情况讨论各个范围内数字所含0的总数，最后累加起来即可。

这里采用的方式是从高位开始拆数。例如，将[0, 109250]包括的0拆成三部分：（1）[0, 100000]，（2）[0, 9250]，（3）以”10″为前缀导致[0, 9250]额外引入的0。那么就可以对[0, 9250]迭代地计算其中包含的0了。也即，此时算法复杂度是和d的位数线性相关的，基本上是O(1)。下面分别讨论三部分含0数目的计算方法。

（1）这里可以预处理，例如a[i]=10^i时，分别计算[1, a[i]]以及[a[i]+1, a[i]*2]范围内所含0的总数，设为b[i]和c[i]。例如a[2]=10^2=100时，b[i]为[1, 100]内0的总数，c[i]为[101, 200]内0的总数。这样处理的原因是，（1）中每次都是拆最高位的，这样当最高位为k时，即为b[i]+(k-1)*c[i]。这里b[i]和c[i]有递推关系，当然其实暴力打表也可以的。

（2）这部分是迭代的，和原本的d处理方法相同；

（3）这部分比较麻烦。首先要记录前缀中含0的个数，然后由d去除最高位后剩余的dd计算需要增加多少个0。这里分情况讨论一下即可。如果前缀有j个0，那么最前面的0包括dd*j个，然后再额外处理后面每一位的情况。

看了别人的基本思路，自己推起来也还是磕磕绊绊。表达起来就更是觉得繁琐了……

#include<cstdio>
#define ll long long

ll a[11],b[11],c[11];
ll m,n;

void init()
{
    ll i,j,k,l;
    a[0]=1;
    for(i=1,k=l=0;i<11;i++,l=l*10+9,k+=l)
    {
        a[i]=a[i-1]*10;
        b[i]=b[i-1]+c[i-1]*9+1;
        c[i]=b[i]+k;
    }
}

ll calc(ll d)
{
    if(!d) return 0;
    ll i,j,k,dd,sum=0;
    for(i=0;i<11&&a[i]<=d;i++);
    i--;
    dd=d-a[i];
    sum=b[i];
    while(dd>=a[i])
    {
        dd-=a[i];
        sum+=c[i];
    }
    if(dd)
    {
        for(i--,j=0;i>0&&a[i]>dd;i--,j++);
        sum+=dd*j;
        while(i)
        {
            sum+=a[i]-1;
            i--;
        }
    }
    return sum+calc(dd);
}

void solve()
{
    if(m==0) 
        printf("%lld\n",calc(n)+1);
    else
        printf("%lld\n",calc(n)-calc(m-1));
}

int main()
{
    init();
    while(~scanf("%lld%lld",&m,&n)&&m!=-1)
        solve();
    return 0;
}

#include<cstdio>

#define ll long long

ll a[11],b[11],c[11];

ll m,n;

void init()

{

ll i,j,k,l;

a[0]=1;

for(i=1,k=l=0;i<11;i++,l=l*10+9,k+=l)

{

a[i]=a[i-1]*10;

b[i]=b[i-1]+c[i-1]*9+1;

c[i]=b[i]+k;

}

ll calc(ll d)

{

if(!d) return 0;

ll i,j,k,dd,sum=0;

for(i=0;i<11&&a[i]<=d;i++);

i--;

dd=d-a[i];

sum=b[i];

while(dd>=a[i])

{

dd-=a[i];

sum+=c[i];

}

if(dd)

{

for(i--,j=0;i>0&&a[i]>dd;i--,j++);

sum+=dd*j;

while(i)

{

sum+=a[i]-1;

i--;

}

return sum+calc(dd);

}

void solve()

{

if(m==0)

printf("%lld\n",calc(n)+1);

else

printf("%lld\n",calc(n)-calc(m-1));

}

int main()

{

init();

while(~scanf("%lld%lld",&m,&n)&&m!=-1)

solve();

return 0;

}

[POJ 3301]

发表回复

Texas Trip

三分法。

其实一开始我是二分做的，二分的对象是正方形的边长，判断可行行则是将整幅图每次旋转一个微小角度，计算与坐标轴平行覆盖所有点的最小正方形。虽然这题精度和数据规模都一般，但还是妥妥的TLE了。于是看了讨论，又参考了这篇文章。

思路还是很清晰的，旋转范围是[0,pi/2]，在这范围内最短边长值是凹函数。于是对角度三分之后，计算所有点坐标中x、y两方向上的最大差值，并取较大值为此时正方形边长。迭代直到精度足够即可。

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

int n;
double r[30],a[30];
const double eps=1e-8;
const double ma=3.141592653589793/2;

void init()
{
    int i;
    double x,y;
    for(i=0;i<n;i++)
    {
        scanf("%lf%lf",&x,&y);
        r[i]=sqrt(x*x+y*y);
        a[i]=asin(y/r[i]);
        if(x<0)
        {
            if(y>0)
                a[i]=ma*2-a[i];
            else
                a[i]=-ma*2-a[i];
        }
    }
}

double calc(double m)
{
    int i;
    double x,y,lx,rx,by,ty;
    lx=by=1e30;
    rx=ty=-1e30;
    for(i=0;i<n;i++)
    {
        x=r[i]*cos(a[i]+m);
        y=r[i]*sin(a[i]+m);
        lx=min(lx,x);
        rx=max(rx,x);
        by=min(by,y);
        ty=max(ty,y);
    }
    return max(rx-lx,ty-by);
}

void solve()
{
    double l,h,m,mm,e,ee;
    for(l=0,h=ma;l<h-eps;)
    {
        m=(l+h)/2;
        mm=(m+h)/2;
        e=calc(m);
        ee=calc(mm);
        if(e<ee)
            h=mm;
        else
            l=m;
    }
    e=calc(l);
    printf("%.2f\n",e*e);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d",&n))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int n;

double r[30],a[30];

const double eps=1e-8;

const double ma=3.141592653589793/2;

void init()

{

int i;

double x,y;

for(i=0;i<n;i++)

{

scanf("%lf%lf",&x,&y);

r[i]=sqrt(x*x+y*y);

a[i]=asin(y/r[i]);

if(x<0)

{

if(y>0)

a[i]=ma*2-a[i];

else

a[i]=-ma*2-a[i];

}

double calc(double m)

{

int i;

double x,y,lx,rx,by,ty;

lx=by=1e30;

rx=ty=-1e30;

for(i=0;i<n;i++)

{

x=r[i]*cos(a[i]+m);

y=r[i]*sin(a[i]+m);

lx=min(lx,x);

rx=max(rx,x);

by=min(by,y);

ty=max(ty,y);

}

return max(rx-lx,ty-by);

}

void solve()

{

double l,h,m,mm,e,ee;

for(l=0,h=ma;l<h-eps;)

{

m=(l+h)/2;

mm=(m+h)/2;

e=calc(m);

ee=calc(mm);

if(e<ee)

h=mm;

else

l=m;

}

e=calc(l);

printf("%.2f\n",e*e);

}

int main()

{

scanf("%*d");

while(~scanf("%d",&n))

{

init();

solve();

}

return 0;

}

又学到了很实用的算法。 ^ ^

[POJ 3422]

发表回复

Kaka’s Matrix Travels

费用流。

好久没写网络流的题目了，敲了很久，不过还是1A了。

这题和以前qoshi推荐的DP是同类题目，但这超过了DP能求解的规模，所以只能用费用流来做了。思路是把矩阵每个元素拆点为ui和vi，并根据费用流算法的需要进行建图。然后重复k次增广操作即可。增广用的是基于栈的spfa。g++下跑了938ms。

#include<cstdio>
#include<cstring>

#define inf 0x0fffffff

int n,m,hd[5000],el,b[5000],f[5000],p[5000],sm,ed;
int stk[5000],sl;

struct E
{
    int u,v,c,f,p;
}e[50000];

inline void adde(int u,int v,int c,int f)
{
    e[el].u=u; e[el].v=v; e[el].c=c; e[el].f=f;
    e[el].p=hd[u]; hd[u]=el++;
}

void sa(int ui,int uj,int f)
{
    int i,j,k,l;
    i=(ui*n+uj)*2;
    j=i+1;
    adde(i,j,1,f);
    adde(j,i,0,-f);
    adde(i,j,inf,0);
    adde(j,i,0,0);
    if(ui<n-1)
    {
        k=i+2*n;
        adde(j,k,inf,0);
        adde(k,j,0,0);
    }
    if(uj<n-1)
    {
        k=i+2;
        adde(j,k,inf,0);
        adde(k,j,0,0);
    }
}

void init()
{
    int i,j,k,l;
    el=sm=0;
    memset(hd,-1,sizeof hd);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&k);
            sa(i,j,k);
        }
    ed=((n-1)*n+n-1)*2+1;
}

void solve()
{
    int i,j,k,l;
    while(m--)
    {
        sl=0;
        memset(b,0,sizeof b);
        memset(f,-1,sizeof f);
        stk[sl++]=0;
        b[0]=1;
        f[0]=0;
        while(sl)
        {
            i=stk[--sl];
            b[i]=0;
            for(l=hd[i];l!=-1;l=e[l].p)
            {
                if(e[l].c==0) continue;
                j=e[l].v;
                if(f[i]+e[l].f>f[j])
                {
                    f[j]=f[i]+e[l].f;
                    p[j]=l;
                    if(!b[j])
                    {
                        b[j]=1;
                        stk[sl++]=j;
                    }
                }
            }
        }
        sm+=f[ed];
        for(i=ed;i;i=j)
        {
            l=p[i];
            j=e[l].u;
            e[l].c--;
            e[l^1].c++;
        }
    }
    printf("%d\n",sm);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

#include<cstdio>

#include<cstring>

#define inf 0x0fffffff

int n,m,hd[5000],el,b[5000],f[5000],p[5000],sm,ed;

int stk[5000],sl;

struct E

{

int u,v,c,f,p;

}e[50000];

inline void adde(int u,int v,int c,int f)

{

e[el].u=u; e[el].v=v; e[el].c=c; e[el].f=f;

e[el].p=hd[u]; hd[u]=el++;

}

void sa(int ui,int uj,int f)

{

int i,j,k,l;

i=(ui*n+uj)*2;

j=i+1;

adde(i,j,1,f);

adde(j,i,0,-f);

adde(i,j,inf,0);

adde(j,i,0,0);

if(ui<n-1)

{

k=i+2*n;

adde(j,k,inf,0);

adde(k,j,0,0);

}

if(uj<n-1)

{

k=i+2;

adde(j,k,inf,0);

adde(k,j,0,0);

}

void init()

{

int i,j,k,l;

el=sm=0;

memset(hd,-1,sizeof hd);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

scanf("%d",&k);

sa(i,j,k);

}

ed=((n-1)*n+n-1)*2+1;

}

void solve()

{

int i,j,k,l;

while(m--)

{

sl=0;

memset(b,0,sizeof b);

memset(f,-1,sizeof f);

stk[sl++]=0;

b[0]=1;

f[0]=0;

while(sl)

{

i=stk[--sl];

b[i]=0;

for(l=hd[i];l!=-1;l=e[l].p)

{

if(e[l].c==0) continue;

j=e[l].v;

if(f[i]+e[l].f>f[j])

{

f[j]=f[i]+e[l].f;

p[j]=l;

if(!b[j])

{

b[j]=1;

stk[sl++]=j;

}

sm+=f[ed];

for(i=ed;i;i=j)

{

l=p[i];

j=e[l].u;

e[l].c--;

e[l^1].c++;

}

printf("%d\n",sm);

}

int main()

{

while(~scanf("%d%d",&n,&m))

{

init();

solve();

}

return 0;

}

books and reading

发表回复

最近读完了松本行弘的程序世界，以及最后的贵族。

前一本，在之前的几篇笔记里也有提及，除部分篇章略显单薄外，全书大部分都是作者多年来关于计算机语言的思考，在很多方面也打开了我的思路，实在是值得一读的好书。但这里主要还是想写写另一本。

从小到大都有政治课，但我经常是不及格，小时候也比较贪玩，对这种无法理解的东西一点兴趣也没有。应付考试也是拿着老师发的资料背一下忽悠过去。中考，高考，研究生考试，一晃都学了10多年政治课了，却也没感觉到学明白了什么。国内对政治这个话题真是非常敏感，来到北京之后更是加深了这种感觉。平时理工科就和政治不太沾边，同学间聊天也话题也很少涉及。身边朋友里几乎不关心政治的人也不在少数。

但大概每个年轻人都会或多或少对这个社会抱有好奇，尤其是在认识到面前不合情理地充满阻挠的时候。我也不例外。

最后的贵族一书原名往事并不如烟，作者是章诒和先生，主要讲述的是新中国建国伊始的一些事情。作者的父亲是当年被划为右派头目的章伯钧，是新中国首任交通部部长，也是当时的民主党派“农工民主党”的主席。还是引用作者本人的序吧：

这本书是我对往事的片断回忆，但它不是回忆录。

在中国和从前的苏联，最珍贵和最难得的个人活动，便是回忆。因为它是比日记或写信更加稳妥的保存社会真实的办法。许多人受到侵害和惊吓，销毁了所有属于私人的文字记录，随之也抹去了对往事的真切记忆。此后，公众凡是应该作为记忆的内容，都由每天的报纸社论和文件、政策、决议来确定。于是，历史不但变得模糊不清，而且以不可思议的速度被改写。这样的“记忆”就像手握沙子一样，很快从指缝里流掉。从前的人什么都相信，相信……，后来突然又啥都不信了。何以如此？其中恐怕就有我们这个社会长期回避真实、掩盖真实、拒绝真实的问题。

我这辈子没有什么意义和价值，经历了天堂、地狱、人间三部曲，充其量不过是一场孤单的人生。我拿起笔，也是在为自己寻找继续生存的理由和力量，拯救我即将枯萎的心。而提笔的那一刻，才知道语言的无用，文字的无力。它们似乎永远无法叙述出一个人内心的爱与乐，苦与仇。

寂静的我独坐在寂静的夜，那些生活的影子便不期而至，眼窝里就会涌出泪水，提笔则更是泪流不止，毫无办法，已成疾。因为一个平淡的词语，常包藏着无数寒夜里的心悸。我想，能够悲伤也是一种权利。

往事如烟，往事并不如烟。我仅仅是把看到的、记得的和想到的记录下来而已，一共写了六篇，涉及八人（不包括我的父母）。这些人，有的深邃如海，有的浅白如溪。前者如罗隆基、聂绀弩，后者如潘素、罗仪凤。他（她）们有才、有德、有能，除了史良，个个心比天高、命如纸薄。可说而不可看，或者可看不可想。过去，咱们这儿总喊“解放全人类”，却残酷地践踏身边的人。其实，不论贵贱和成败，人既不应当变为圣像，也不应当遭受藐视。

书是献给父母的。他们在天国远远望着我，目光怜悯又慈祥。

这本书实在让我无法评论，想写的东西太多太多。能读到这种毫无保留地讲述过去事实的书籍，实在是太好了。

昨天路过什刹海的时候，在地图上竟然看到有“张伯驹潘素故居纪念馆”。找到了门口，却很可惜的发现没有开放。这也是我第一次到什刹海，环顾四周，大概是北京城内风景最好的一角了。书中讲述的小说般的故事，却真真实实的发生在不远的过去，伸出双手仿佛就能触碰。回头想想，为何非要千里迢迢从广东到北京读研。其中最吸引我的，也就是这点了吧。

[POJ 3150]

发表回复

Cellular Automaton

矩阵运算。

题意抽象出来，即是求A^k*x(mod m)，其中A是n*n的循环矩阵，x是n维列向量。

很直接的思路是O(n^3*lgk)，但这里n最大500，TLE的。如果利用A是循环矩阵的性质，那么其实每次只要计算第一行就可以了，其他行都可以由第一行移位得到。这样就可以O(n^2*lgk)，实现出来最快500ms。

#include<cstdio>
#include<cstring>

#define ll long long
#define size n<<3

ll n,m,d,e,a[500],b[500],t[500],x[500],y[500];

void init()
{
    ll i,j,k,l;
    for(i=0;i<n;i++)
        scanf("%lld",x+i);
    memset(a,0,size);
    memset(b,0,size);
    memset(y,0,size);
    b[0]=1;
    for(i=j=0,k=0;k<=d;k++)
    {
        a[i]=1;
        ++i;
        if(i==n) i=0;
        a[j]=1;
        --j;
        if(j==-1) j=n-1;
    }
}

void mul(ll b[],ll a[])
{
    ll i,j,k,l;
    memset(t,0,size);
    for(i=0;i<=n/2;i++)
    {
        for(j=0,k=i;j<n;j++)
        {
            t[i]+=b[j]*a[k];
            ++k;
            if(k==n) k=0;
        }
        t[i]%=m;
    }
    for(i=1;i<=n/2;i++)
        t[n-i]=t[i];
    memcpy(b,t,size);
}

void solve()
{
    ll i,j,k,l;
    for(i=1;i<=e;i<<=1);
    for(i>>=1;i;i>>=1)
    {
        mul(b,b);
        if(i&e)
            mul(b,a);
    }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            y[i]=(y[i]+b[j]*x[(i+j)%n])%m;
    for(i=0;i<n-1;i++)
        printf("%lld ",y[i]);
    printf("%lld\n",y[n-1]);
}

int main()
{
    while(~scanf("%lld%lld%lld%lld",&n,&m,&d,&e))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#define ll long long

#define size n<<3

ll n,m,d,e,a[500],b[500],t[500],x[500],y[500];

void init()

{

ll i,j,k,l;

for(i=0;i<n;i++)

scanf("%lld",x+i);

memset(a,0,size);

memset(b,0,size);

memset(y,0,size);

b[0]=1;

for(i=j=0,k=0;k<=d;k++)

{

a[i]=1;

++i;

if(i==n) i=0;

a[j]=1;

--j;

if(j==-1) j=n-1;

}

void mul(ll b[],ll a[])

{

ll i,j,k,l;

memset(t,0,size);

for(i=0;i<=n/2;i++)

{

for(j=0,k=i;j<n;j++)

{

t[i]+=b[j]*a[k];

++k;

if(k==n) k=0;

}

t[i]%=m;

}

for(i=1;i<=n/2;i++)

t[n-i]=t[i];

memcpy(b,t,size);

}

void solve()

{

ll i,j,k,l;

for(i=1;i<=e;i<<=1);

for(i>>=1;i;i>>=1)

{

mul(b,b);

if(i&e)

mul(b,a);

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

y[i]=(y[i]+b[j]*x[(i+j)%n])%m;

for(i=0;i<n-1;i++)

printf("%lld ",y[i]);

printf("%lld\n",y[n-1]);

}

int main()

{

while(~scanf("%lld%lld%lld%lld",&n,&m,&d,&e))

{

init();

solve();

}

return 0;

}

看评论还有一种O(n*lgn*lgk)的算法……但是想了一早上也没明白怎么弄，饿得不行吃饭先了……