2018.12.26 考试(哈希，二分，状压dp)

T1

解题思路

　　发现有一个限制是每个字母都必须相等，那么就可以转化成首尾的差值相等，然后就可以求出\(k-1\)位的差值\(hash\)一下。\(k\)为字符集大小，时间复杂度为\(O(nk)\)。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<map>

using namespace std;

typedef unsigned long long ull;

typedef long long LL;

const int MAXN = 100005;

const int mod = 131;

const ull base = 666623333;

const int MOD = 1e9+7;

int n,cnt,sum[MAXN][60];

char s[MAXN];

LL ans;

ull hsh[MAXN];

map<char,int> mp;

map<ull,int> SUM;

int main(){

    scanf("%d%s",&n,s+1);

    for(int i=1;i<=n;i++){

        if(!mp.count(s[i])) mp[s[i]]=++cnt;

        sum[i][mp[s[i]]]=1;

    }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=cnt;j++)

            sum[i][j]+=sum[i-1][j];

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

        //for(int j=1;j<=cnt;j++)

            //printf("sum[%d][%d]=%d\n",i,j,sum[i][j]);

    for(int i=1;i<=n;i++){

        ull now=1;

        for(int j=2;j<=cnt;j++)

            now=now*base+(ull)(sum[i][j]-sum[i][j-1]+mod);

        hsh[i]=now;

        SUM[now]=SUM[now]+1;

    }

    hsh[0]=1;

    for(int j=1;j<cnt;j++)

        hsh[0]=hsh[0]*base+mod;

    SUM[hsh[0]]=SUM[hsh[0]]+1;

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

        SUM[hsh[i]]=SUM[hsh[i]]-1;

        ans=(ans+SUM[hsh[i]])%MOD;

    }

    printf("%lld\n",ans);

    return 0;

}

T2

传送门

解题思路

　　二分一个时间，使得一对粒子的距离之和\(<=L\)，然后重复\(k\)次，时间复杂度\(O(nklog(MAX)\)。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 50005;

const double eps = 1e-6;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return f?x:-x;

}

void out(int x){

	if(!x) return ;out(x/10);putchar('0'+x%10);

}

int n,L,k,Maxx[3],Maxy[3],ans[105][2];

bool visx[MAXN],visy[MAXN];

double disx[3],disy[3],now;

struct Data{

	int v,t;

}a[MAXN],b[MAXN];

inline bool check(int tmp,double lim){

	Maxx[1]=Maxx[2]=Maxy[1]=Maxy[2]=disx[1]=disx[2]=disy[1]=disy[2]=0;

	for(register int i=1;i<=n;i++){

		if(!visx[i] && a[i].t<=lim) {

			if((double)(lim-a[i].t)*a[i].v>disx[1]) {

				Maxx[2]=Maxx[1];disx[2]=disx[1];

				disx[1]=(double)(lim-a[i].t)*a[i].v;Maxx[1]=i;

			}

			else if((double)(lim-a[i].t)*a[i].v>disx[2]) Maxx[2]=i,disx[2]=(double)(lim-a[i].t)*a[i].v;

		}

		if(!visy[i] && b[i].t<=lim){

			if((double)(lim-b[i].t)*b[i].v>disy[1]){

				Maxy[2]=Maxy[1];disy[2]=disy[1];

				disy[1]=(double)(lim-b[i].t)*b[i].v;Maxy[1]=i;

			}

			else if(((double)(lim-b[i].t)*b[i].v>disy[2])) Maxy[2]=i,disy[2]=(double)(lim-b[i].t)*b[i].v;

		}

		if(disx[2]+disy[2]>=L) return 0;

	}

	if(!Maxx[1] || !Maxy[1]) return 1;

	if(disx[1]+disy[1]<L) return 1;

	if(disx[2]+disy[2]>=L) return 0;

	ans[tmp][0]=Maxx[1];ans[tmp][1]=Maxy[1];now=lim;

	return 0;

}

int main(){

	n=rd(),L=rd(),k=rd();double l,r,mid;

	for(register int i=1;i<=n;i++)

		a[i].t=rd(),a[i].v=rd();

	for(register int i=1;i<=n;i++)

		b[i].t=rd(),b[i].v=rd();

	for(register int i=1;i<=k;i++){

		l=now;r=1e9+2e8;

		while(r-l>=eps){

			mid=(l+r)/2;

			if(check(i,mid)) l=mid+eps;

			else r=mid-eps;

		}

		visx[ans[i][0]]=1;visy[ans[i][1]]=1;

		out(ans[i][0]),putchar(' '),out(ans[i][1]),putchar('\n');

	}

	return 0;

}

T3

传送门

解题思路

　　状压\(dp\)，考场上脑抽了写了个\(2^{3^{质因数}}\)级别的垃圾做法。。正解十分玄学，前\(6\)位三进制状压表示每个质因数出现的次数，后\(21\)为二进制状压表示哪两个质因数不能同时出现，然后用\(map\)来存状态。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<map>

#define int long long

using namespace std;

typedef long long LL;

const int MOD = 1e9+7;

const int poww[8] = {1,3,9,27,81,243,729,2187};

LL n;

int ans,a[55],cnt,num[55],ban[55];

map<int,int> mp;

map<int,int>::iterator it;

inline void init(){

	int x=n;

	for(LL i=2;i*i<=x;i++){

		if(x%i) continue;

		a[cnt]=i;

		while(!(x%i)) x/=i,num[cnt]++;

		cnt++;

	}

	if(x!=1) a[cnt]=x,num[cnt++]=1;

}

int get_new(int S,int now){

	int ret=S,bit=1;

	for(int i=0;i<cnt;i++){

		if((now&(1<<i)) && S/bit%3<2) ret+=bit;

		bit*=3;

	}

	for(int i=0;i<cnt;i++)

		for(int j=i+1;j<cnt;j++){

			if((now&(1<<i)) && ((S/poww[j])%3>0) && (!((S/bit)&1))) ret+=bit;

			else if((now&(1<<j)) && ((S/poww[i])%3>0) && (!((S/bit)&1))) ret+=bit;

			bit<<=1;

		}

	return ret;

}

inline int get_num(int S){

	int ret=1;

	for(int i=0;i<cnt;i++)

		if(S&(1<<i)) ret*=num[i],ret%=MOD;

	return ret;

}

signed main(){

	scanf("%lld",&n);int kk=0;

	init();it=mp.insert(make_pair(0,1)).first;

	while(it!=mp.end()){kk++;

		ans+=it->second;ans%=MOD;

		int tmp=it->first,now=0,tot=0,flag,k;

		for(int i=0;i<cnt;i++){

			if(tmp%3<2) now|=(1<<i);

			tmp/=3;

		}

		for(int i=0;i<cnt;i++)

			for(int j=i+1;j<cnt;j++){

				if(tmp&1) ban[++tot]=(1<<i)|(1<<j);

				tmp>>=1;

			}

		for(int i=now;i;i=(i-1)&now){

			flag=false;

			for(int j=1;j<=tot;j++)

				if((ban[j]|i)==i) {flag=true;break;}

			if(flag) continue;

			k=get_new(it->first,i);

			if(mp.find(k)==mp.end()) mp.insert(make_pair(k,0));

			mp[k]+=it->second*get_num(i)%MOD;mp[k]%=MOD;

		}

		it++;

	}

	printf("%lld\n",(ans-1+MOD)%MOD);

	return 0;

}

巴特西

2018.12.26 考试(哈希，二分，状压dp)

T1

解题思路

代码

T2

解题思路

代码

T3

解题思路

代码

最新文章

热门文章