题目：Problem
1.幸运序列
因为循环的情况只有一个
就是447->474->447->474…
所以特判一下 O(n)扫一遍即可
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
// <lucky.cpp> - 10/23/15 08:20:46 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')getchar(),fh=-1; while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } int main(){ freopen("lucky.in","r",stdin); freopen("lucky.out","w",stdout); int n=getint(),k=getint(),a[100002]; for(int i=1;i<=n;i++)scanf("%1d",&a[i]); for(int i=1;i<=n&&k;i++){ if(a[i]==4&&a[i+1]==7){ if(i&1)a[i+1]=a[i],k--; else{ if(a[i-1]==4){ if(k&1)a[i]=7; break; } a[i]=a[i+1];k--; } } } for(int i=1;i<=n;i++)cout<<a[i]; return 0; } |
2. 無名
F**K THIS STUPID STRING HASH
F**K THIS STUPID STRING HASH
F**K THIS STUPID STRING HASH
一开始用的trie树存 但是超时了
然后按正解的字符串hash来
然后调了一个晚上
TMD
再也不相信什么hash碰撞率低了
题解：
首先O(n^2)求出所有原串中前缀和后缀的位置
然后枚举各个前缀后缀组合
找到一个就hash标记
之后发现一样的就跳过
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
// <noname.cpp> - 10/23/15 08:20:46 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #include <ctime> #include <map> #include <set> using namespace std; typedef long long lol; const long long MOD=1000000097ll; const long long SD=173ll; int getint(){ int res=0; char ch=getchar(); while(ch<'0'||ch>'9')ch = getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return res; } long long pow(long long a,int b){ long long ans=1; while(b!=0){ if(b&1)ans=ans*a%MOD; a=a*a%MOD; b>>=1; } return ans; } map <long long,bool> h; char s[2001],a[2001],b[2001]; bool pre[2001],sub[2001]; int ls,la,lb,ans; lol hash[2002]; int main(){ freopen("noname.in","r",stdin); freopen("noname.out","w",stdout); scanf("%s",s);scanf("%s",a);scanf("%s",b); ls=strlen(s);la=strlen(a);lb=strlen(b); for(int i=0;i<ls-la+1;i++){ int j; for(j=0;j<la&&s[i+j]==a[j];j++); if(j==la)pre[i]=1; } for(int i=ls-lb;i>=0;i--){ int j; for(j=0;j<lb&&s[i+j]==b[j];j++); if(j==lb)sub[i]=1; } hash[0]=0; hash[1]=s[0]-'a'+1; for(int i=2;i<=ls;i++)hash[i]=(hash[i-1]*SD+s[i-1]-'a'+1)%MOD; for(int i=0;i<ls-la+1;i++) if(pre[i]) for(int j=i+max(0,la-lb);j<=ls-lb;j++){ int l=i+1,r=j+lb-1+1,ha=(hash[r]-hash[l-1]*pow(SD,r-l+1)%MOD+MOD)%MOD; if(sub[j]&&!h[ha]){ h[ha]=1; ans++; } } cout<<ans<<endl; return 0; } |
3.字符串转换
这道题本来是打的暴力想骗点分的 结果莫名A掉了
呵呵
枚举就好了
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// <trans.cpp> - 10/23/15 08:20:46 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0; char ch=getchar(); while(ch<'0'||ch>'9')ch = getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return res; } char a[1000002],b[1000002]; int la,lb; bool src3(int w,int p){ for(int i=0;i<w;i++)if(a[la-i-1]!=b[i+p])return 0; return 1; } void src2(int i,int p){ if(src3(la-p-i,i)){cout<<p-1<<" "<<p+i;exit(0);} if(p+i==la)return; if(b[i]==a[i+p])src2(i+1,p); } void src1(int i){ if(i==la-1)return; if(a[i]==b[la-1-i])src1(i+1); src2(0,i+1); } int main(){ freopen("trans.in","r",stdin); freopen("trans.out","w",stdout); cin.getline(a,1000001); cin.getline(b,1000001); la=strlen(a);lb=strlen(b); if(la!=lb){cout<<"-1 -1";return 0;} src1(0); cout<<"-1 -1"; return 0; } |
说点什么