[AHOI2007]宝库迷宫

Posted on May 8, 2010 by wjmzbmr

www.rqnoj.cn/Problem_301.html
晕。。竟然抄TopCoder的原题。。
看上去很难，因为10^10的搜索是要悲剧的。。但实际上只要每个点中间点向左向右搜出10^5的路径然后都排序就可以直接扫描得出结果了。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>2,maxn=10,maxp=100000+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct Array
{
double A[maxp];int n;
void set(){n=0;}
Array(){set();}
void add(double x){A[n++]=x;}
void Sort(){sort(A,A+n);}
double operator[](int v){return A[v];}
};
int n;double D[maxn][maxn];
Array L,R;
void DfsL(int pos,int d,double now)
{
if(!d){L.add(now);return;}
rep(i,n)DfsL(i,d-1,now+D[i][pos]);
}
void DfsR(int pos,int d,double now)
{
if(!d){R.add(now);return;}
rep(i,n)DfsR(i,d-1,now+D[pos][i]);
}
int main()
{
//freopen("in","r",stdin);
cin>>n;rep(i,n)rep(j,n){cin>>D[i][j];}
double ans=inf;
rep(i,n)
{
int l=n/2,r=n-l;
L.set();R.set();
DfsL(i,l,0);DfsR(i,r,0);
L.Sort();R.add(inf);R.add(-inf);R.Sort();int j=R.n-1;
for(int i=0;i<L.n;i++)
{
while(L[i]+R[j]>=2007)j–;
ans=min(ans,2007-L[i]-R[j]);
ans=min(ans,L[i]+R[j+1]-2007);
}
}
printf("%0.2lfn",ans);
}

[AHOI2007]红十字

Posted on May 8, 2010 by wjmzbmr

www.rqnoj.cn/Problem_300.html

题目:[AHOI2007]红十字

问题编号:300

题目描述

通往藏宝库的通道打开了，走下一段长长的楼梯，钻过一条矮矮的地道，你和小可可终于来到了藏宝库的门前。随之而来的就是最后一个挑战，只要能打开宝库的门，里面的宝藏就是你们的了。
宝库的门依然是通过机关打开，这个门很奇怪，是一个正方形，被划分成许多大小一致的正方形的小方格，这些方格不是红色就是白色，猛看上去这些方格组成了许多红十字状的标志。根据藏宝图记载，只要找到门上最大的红十字，按下它中心的方格，宝库的门就能打开了。
红十字标志也是一个正方形，边长为(2k+1)*(2k+1)，其中k为非负整数。它的四条边与门的边平行，而且恰由门上的 (2k+1)*(2k+1)个小方格组成。这里，红十字标志是以白色为底色，红色为十字的颜色。假设用1表示红色，用0表示白色。对应到计算机处理的数据中，就是除了正中列与正中行全为1外，其余方格均为0。以下是几种不同大小的标志：
1*1:
1
3*3
010
111
010
5*5
00100
00100
11111
00100
00100

小可可被这个机关难到了，现在只有靠你了，请你帮助他在这个门上找到一个最大的红十字标志，输出它的边长即可。

输入格式

输入文件中第一行有一个整数n（1<=n<=2,000），表示门由n个方格组成。
以下n行，每行n个字符，每个字符都是0或1。数据中不会出现全为0的情况。

输出格式

输出一个数，即最大的红十字标志的边长。

样例输入 5 00011 01011 11100 01001 00010 样例输出 3 三维状态图像
这道题挺有意思啊，首先求出每个点从4个方向最多按1能延伸多少，还有从四个方向开上的最大全为0正方形。。时限太紧了。。代码写的我要吐了。。我不得已只好用了指针。。ugly Code….
Code:
www.ideone.com/gXeXg

SPOJ New Distinct Substrings

Posted on May 7, 2010 by wjmzbmr

https://www.spoj.pl/problems/SUBST1/
这是经典的题目了。。求出后缀数组和Height数组，然后用n*(n+1)/2-所有Height的和就OK了囧。。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=50000+10;
using namespace std;
char C[maxn];int ta[maxn],tb[maxn],sa[maxn],n,m,*x=ta,*y=tb,h[maxn];
void Sort()
{
static int w[maxn];
rep(i,m)w[i]=0;rep(i,n)w[x[y[i]]]++;rep(i,m-1)w[i+1]+=w[i];
for(int i=n-1;i>=0;i–)sa[–w[x[y[i]]]]=y[i];
}
bool cmp(int a,int b,int l)
{return y[a]==y[b]&&y[a+l]==y[b+l];}
void Da()
{
rep(i,n)x[i]=C[i],y[i]=i;Sort();int i,j,p;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++)y[p++]=i;
rep(i,n)if(sa[i]>=j)y[p++]=sa[i]-j;Sort();
for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(sa[i-1],sa[i],j)?p-1:p++;
}
}
void CalH()
{
static int R[maxn];
int i,j,k=0;
for(i=1;i<=n;i++)R[sa[i]]=i;
for(i=0;i<n;h[R[i++]]=k)
for(k?k–:0,j=sa[R[i]-1];C[i+k]==C[j+k];k++);
}
void Solve()
{
scanf("%s",C);n=strlen(C);C[n++]=0;m=256;
Da();n–;long long ans=n;ans*=n+1;ans/=2;
CalH();rep(i,n)ans-=h[i+1];cout<<ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
int t;cin>>t;while(t–)Solve();
}

Suffix Array…

Posted on May 6, 2010 by wjmzbmr

好不容易写了个SA的代码，以前写过但是忘掉了囧。。。
Code：
#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000+10;char C[maxn];int n,sa[maxn],ta[maxn],tb[maxn],m,tv[maxn];void sort(int*x,int*y,int m){ static int w[maxn]; rep(i,m)w[i]=0;rep(i,n)w[x[y[i]]]++; rep(i,m)if(i)w[i]+=w[i-1]; for(int i=n-1;i>=0;i–)sa[–w[x[y[i]]]]=y[i];}inline bool cmp(int*r,int i,int j,int l){ return r[i]==r[j]&&r[i+l]==r[j+l];}void Da(){ int*x=ta,*y=tb,i,j,p; rep(i,n)x[i]=C[i],tv[i]=i;sort(x,tv,m); for(j=1,p=1;p<n;j*=2,m=p) { for(p=0,i=n-j;i<n;i++)y[p++]=i; rep(i,n)if(sa[i]>=j)y[p++]=sa[i]-j;sort(x,y,m); for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; }}int main(){ scanf("%s",C);n=strlen(C);C[n++]=0;m=’Z’+1; Da(); rep(i,n)printf("%dn",sa[i]);}

期中考试悲剧了。。

Posted on May 4, 2010 by wjmzbmr

RT。。。科学和语文全挂了。。。算了。。专心搞OI了。。我回来啦!。。。。

SGU 232

Posted on May 2, 2010 by wjmzbmr

acm.sgu.ru/problem.php
算法不难想。。但因为各种各样的SB原因WA了N次。。主要是我是SB。。
很显然设d=(N,K),那么按题目的说法一共有d类。。每类长度都是N/d。。那么只要求出每类的最大值然后比较一下就可以知道全部的最大值了，而每类中那个很显然是个最大表示法的经典问题。。所以就OK了。。但是K太打了所以要用long long这玩意搞的我累死。。晕啊！
我决定了。。以后我不论什么变量都用long long。。TMD老子不要效率了。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=150000+1;
using namespace std;
int A[maxn],n;
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int get(ll i){return A[i%n];}
int main()
{
//freopen("in","r",stdin);
char c;int k,d,l;cin>>n>>k;k%=n;d=gcd(k,n),l=n/d;
scanf("n");rep(i,n)scanf("%c",&c),A[i]=c-‘0’;
int m=-1;
rep(a,d)
{
int i=0,j=1;ll t=0;
while(i<l&&j<l&&t<l)
{
int A=get(a+(i+t)*k),B=get(a+(j+t)*k);
if(A==B)t++;
else
{
if(A<B){i+=t+1;t=0;}
else{j+=t+1;t=0;}
if(i==j)j++;
}
}
t=a+min(i,j)*ll(k);t%=n;bool c;
if(m<0)c=true;
else rep(i,l)
{
int A=get(t+ll(i)*k),B=get(m+ll(i)*k);
if(A<B){c=false;break;}
if(A>B){c=true;break;}
}
if(c)m=t;
}
rep(i,n)printf("%d",get(m+ll(i)*k));
printf("n");
}

排序。。。

Posted on May 2, 2010 by wjmzbmr

我SB了。。。各位神牛WS我囧。。。。最近教一个同学排序于是就写了3个排序的基本算法。。我发现基数排序真是快的跟鬼一样。。。
快速排序：
#include <iostream>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=10000000;
using namespace std;
int A[maxn];
void sort(int l,int r)
{
if(r-l<2)return;
int h=l,x=A[l+rand()%(r-l+1)];
for(int i=l;i<=r;i++)if(A[i]<x){int t=A[i];A[i]=A[h];A[h]=t;h++;}
sort(l,h-1);sort(h+1,r);
}
int main()
{
int n;cin>>n;rep(i,n)scanf("%d",A+i);sort(0,n-1);
}堆排序：
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=10000000;
using namespace std;
int n,A[maxn];
inline int swap(int&a,int&b){a^=b^=a^=b;}
void Up(int i)
{
if(i/2&&A[i/2]>A[i])swap(A[i],A[i/2]),Up(i/2);
}
void Down(int i)
{
int p=i*2;if(p>n)return;
if(p+1<=n&&A[p+1]<A[p])++p;
if(A[i]>A[p])swap(A[i],A[p]),Down(p);
}
int main()
{
scanf("%d",&n);rep(i,n)scanf("%d",A+i+1),Up(i+1);
rep(i,n)swap(A[1],A[n–]),Down(1);
}基数排序（每4位）：
#include <algorithm>
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>2,maxn=1000000;
using namespace std;
int S0[maxn],S1[maxn],n,C[16]={};
int*A=S0,*B=S1;
int main()
{
scanf("%d",&n);rep(i,n)scanf("%d",A+i);
rep(x,4)
{
int d=x*4;rep(i,16)C[i]=0;
rep(i,n)C[(A[i]>>d)&15]++;rep(i,16)if(i)C[i]+=C[i-1];
for(int i=n-1;i>=0;i–)B[–C[(A[i]>>d)&15]]=A[i];
swap(A,B);
}
}无论从代码长度还是速度来说。。都是基数排序强。。囧啊。。

USACO OPEN 2010

Posted on April 28, 2010 by wjmzbmr

真是悲剧阿。。第一题我想到了dP但因为我以为回来前只能跳一次导致噢只对了3个。。第二题我DP写对了。。但是没用long long。。WA一个点。。第3题悲剧了。。骗分都没写。。OrzWinmad神牛AC!!

SGU 370

Posted on April 27, 2010 by wjmzbmr

题目在http://acm.sgu.ru/problem.php?contest=0&problem=370
首先特判掉n=1或m=1或n、m都等于1的情况。。
然后答案就是p<=n&&p<=m&&(p,q)=1的数对的个数。。
很明显可以用容斥原理做。。
就OK了。。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000000+1;
int n,m,pnt,*P;
long long ans=0;
int S[maxn][10],D[maxn]= {};
void dfs(int p,int ch,int now)
{
    if(now>n)return;
    if(p==pnt)
    {
        if(ch&1)ans-=n/now;
        else ans+=n/now;
        return;
    }
    dfs(p+1,ch,now);
    dfs(p+1,ch+1,now*P[p]);
}

int main()
{
    //freopen("in","r",stdin);
    cin>>n>>m;
    n--;
    m--;
    if(m>n)swap(n,m);
    if(!n)
    {
        cout<<0<<endl;
        return 0;
    }
    if(!m)
    {
        cout<<1<<endl;
        return 0;
    }
    for(int i=1; i<=m; i++)
    {
        if(i==1)
        {
            ans+=n;
            continue;
        }
        int t=i,a;
        P=S[i];
        for(a=2; a*a<=t; a++) if(t%a==0)
            {
                while(t%a==0)
                {
                    t/=a;
                }
                break;
            }
        if(t==i)P[D[i]++]=t;
        else
        {
            D[i]=D[t]+1;
            memcpy(P,S[t],sizeof(S[t]));
            P[D[i]-1]=a;
        }
        pnt=D[i];
        dfs(0,0,1);
    }
    cout<<ans+2<<endl;
}

COCI 2010-7题解