[UVa 11549]Calculator Conundrum

很有趣的一个题。

很明显,求出的结果一定会循环,形成一个环。然后呢?假如有一只乌龟和一只兔子在这个赛道上赛跑(同起点),兔子的速度是乌龟的两倍,那么最后兔子一定会“追上”乌龟,然后接下来的情况就是以前的循环了。

这种神奇的算法叫做Floyd判圈算法。话说还有一种Brent判圈算法……常数比它还要小。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
char buf[25];
int n;
inline ull next(ull x){
    register ull res=0;
    register int i,length;
    memset(buf,0,sizeof(buf));
    length=sprintf(buf,"%llu",x*x);
    length=min(length,n);
    for(i=0;i<length;i++){
        res=res*10+buf[i]-'0';
    }
    return res;
}
int main(){
    ull k1,k2,ans;
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%llu",&n,&k1);
        ans=k1;
        k2=k1;
        do{
            k1=next(k1);
            k2=next(k2);
            if(k2>ans)
                ans=k2;
            k2=next(k2);
            if(k2>ans)
                ans=k2;
        }while(k1!=k2);
        printf("%llu\n",ans);
    }
    return 0;
}

[UVa 10635]Prince and Princess

这个名字真有童话风味哎……

直接LCS肯定会TLE。注意每个序列都是不重复序列,所以可以将A映射到[tex][1,p+1][/tex],然后再把B映射一下(有的可能A里面没有?反正既然A里没有就和LCS没关系了),就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
    int T,n,p,q,x;
    register int i,ans,k,Case=0;
    scanf("%d",&T);
    while(T--){
        Case++;
        scanf("%d%d%d",&n,&p,&q);
        CL_ARR(Hash,0);
        for(i=1;i<=(p+1);i++){
            scanf("%d",&x);
            Hash[x]=i;
        }
        for(i=1;i<=(q+1);i++){
            scanf("%d",&x);
            B[i]=Hash[x];
        }
        CL_ARR(g,0x7f);
        ans=0;
        for(i=1;i<=(q+1);i++){
            k=lower_bound(g+1,g+2+q,B[i])-g;
            d[i]=k;
            g[k]=B[i];
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",Case,ans);
    }
    return 0;
}

[LA 3942]Remember the Word

Trie第一题……

首先,容我吐槽一下UVa这个OJ,速度特别感人(同学们可以实践一下)。

这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex],枚举其前缀查是否为单词,然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。

然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex],在前缀树中查找之,就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100,所以查找会很快辣~

代码:

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int n;
vector<int> AnsList;
namespace Trie{
	const int maxnode=400005;
	const int sigma_siz=26;
	int Tree[maxnode][sigma_siz];
	int val[maxnode];
	int siz;
	inline int idx(char c){
		return c-'a';
	}
	inline void InitTrie(){
		siz=0;
		val[0]=0;
		CL_ARR(Tree[0],0);
	}
	void Insert(char *s,int v){
		register int u=0,n=strlen(s);
		register int i,c;
		REP(i,n){
			c=idx(s[i]);
			if(!Tree[u][c]){
				siz++;
				Tree[u][c]=siz;
				val[siz]=0;
				CL_ARR(Tree[siz],0);
			}
			u=Tree[u][c];
		}
		val[u]=v;
	}
	void Query(char *s,int len){
		register int i,c,u=0;
		AnsList.clear();
		REP(i,len){
			if(!s[i])
				break;
			c=idx(s[i]);
			if(!Tree[u][c])
				break;
			u=Tree[u][c];
			if(val[u])
				AnsList.push_back(val[u]);
		}
	}
};

char Text[maxn];
int len[maxW];
char buf[maxL];
int d[maxn];
int main(){
	register int i,j,Case=0;
	int m;
	while(scanf("%s%d",Text,&m)==2){
		Case++;
		n=strlen(Text);
		Trie::InitTrie();
		REP_B(i,m){
			scanf("%s",buf);
			len[i]=strlen(buf);
			Trie::Insert(buf,i);
		}
		d[n]=1;
		DREP(i,n){
			d[i]=0;
			Trie::Query(Text+i,n-i);
			REP(j,AnsList.size()){
				d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
			}
		}
		printf("Case %d: %d\n",Case,d[0]);
	}
	return 0;
}