Capture The Flag

C++11(clang++ 3.9) 解法, 执行用时: 767ms, 内存消耗: 71988K, 提交时间: 2019-07-16 22:20:44

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

const int N=20;
char s[N];

map<int,string>MP;
vector<ll>vec;
int L=33,R=126;

void dfs(int pos,ll v,ll pw,ll p,ll m,string s){
    if(pos>=4){
        MP[v]=s;
        vec.push_back(v);
        return ;
    }
    for(int i=L;i<=R;i++){
        dfs(pos+1,(v+pw*i)%m,pw*p%m,p,m,s+(char)(i));
    }
}

bool gao(ll x){
    auto it=lower_bound(vec.begin(),vec.end(),x);
    return it!=vec.end() && (*it==x);
}

ll Hash(string s,ll p,ll m){
    ll ans=0;
    ll pw=1;
    for(auto ch:s){
        ans+=(ll)ch*pw;
        ans%=m;
        pw=pw*p%m;
    }
    return ans;
}

void solve(){
    ll p,m;
    cin>>p>>m>>s;
    ll h=Hash(s,p,m);
//  cout<<h<<endl;
    dfs(1,0,1,p,m,"");
    sort(vec.begin(),vec.end());
    ll pw=1;
    for(int i=1;i<=3;i++) (pw*=p)%=m;
    for(auto i:vec){
        ll j=(h-(i*pw)%m+m)%m;
        if(gao(j)){
            string t=MP[j]+MP[i];
        //  cout<<Hash(t,p,m)<<endl;
            cout<<MP[j]<<MP[i]<<endl;
            return ;
        }
    }
    assert(0);
}

int main(){

    solve();
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 631ms, 内存消耗: 71944K, 提交时间: 2019-06-08 16:10:06

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

const int N=20;
char s[N];

map<int,string>MP;
vector<ll>vec;
int L=33,R=126;

void dfs(int pos,ll v,ll pw,ll p,ll m,string s){
	if(pos>=4){
		MP[v]=s;
		vec.push_back(v);
		return ;
	}
	for(int i=L;i<=R;i++){
		dfs(pos+1,(v+pw*i)%m,pw*p%m,p,m,s+(char)(i));
	}
}

bool gao(ll x){
	auto it=lower_bound(vec.begin(),vec.end(),x);
	return it!=vec.end() && (*it==x);
}

ll Hash(string s,ll p,ll m){
	ll ans=0;
	ll pw=1;
	for(auto ch:s){
		ans+=(ll)ch*pw;
		ans%=m;
		pw=pw*p%m;
	}
	return ans;
}

void solve(){
	ll p,m;
	cin>>p>>m>>s;
	ll h=Hash(s,p,m);
//	cout<<h<<endl;
	dfs(1,0,1,p,m,"");
	sort(vec.begin(),vec.end());
	ll pw=1;
	for(int i=1;i<=3;i++) (pw*=p)%=m;
	for(auto i:vec){
		ll j=(h-(i*pw)%m+m)%m;
		if(gao(j)){
			string t=MP[j]+MP[i];
		//	cout<<Hash(t,p,m)<<endl;
			cout<<MP[j]<<MP[i]<<endl;
			return ;
		}
	}
	assert(0);
}

int main(){

	solve();
    return 0;
}

详情