2016 北京 ICPC (部分)

I - A Boring Problem

题目大意

数列求和，其中每一项都是一个子段和的k次幂，例如：

给定原字符串为 “12345”

输出结果：1^k (1+2)^k+2^k (1+2+3)^k+(2+3)^k+3^k…… (1+2+3+4+5)^k+(2+3+4+5)^k+…+5^k

正常思路下，每个输出结果也需分别进行求和，即使用了快速幂，最后复杂度为 n^2log(n) 依然会超时，所以需优化。

将每个输出结果中的每一个加项用二项式定理展开，提取二项式系数，此时由n项变为了k项，复杂度可以降低为n*k，但需进行

大量预处理工作。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

#define M 105
#define N 50005
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define mod 1000000007
long long coef[N][M],sum[N][M],c[M],ss[N][M];
char s[N];
int n,k,t;

int main() {
	scanf("%d",&t);
	while(t--) {
		memset(sum,0,sizeof(sum));
		memset(coef,0,sizeof(coef));
		memset(ss,0,sizeof(ss));
		scanf("%d%d",&n,&k);
		scanf("%s",s+1);

		rep(i,1,n) ss[i][1]=ss[i-1][1]+s[i]-'0',ss[i][0]=1;
		rep(i,2,k) rep(j,1,n) ss[j][i]=(ss[j][i-1]*ss[j][1])%mod;

		c[0]=1;
		rep(i,1,k) c[i]=c[i-1]*(k-i+1)/i%mod;

		sum[0][0]=1;
		rep(i,0,k) rep(j,1,n) sum[j][i]=(long long)(sum[j-1][i]+ss[j][i])%mod;
		rep(i,1,n) rep(j,0,k) {
			coef[i][j]=ss[i][k-j]*c[j]%mod;
			coef[i][j]*=(j%2?-1:1);
		}
		rep(i,0,n-1) {
			long long ans=0;
			rep(j,0,k) {
				ans+=coef[i+1][j]*(sum[i][j])%mod;
				ans%=mod;
			}
			printf("%ld%c",ans,i==n-1?'\n':' ');
		}
	}
	return 0;
}

只不过最后还是tle……其中原因有待进一步分析

E. What a Ridiculous Election

bfs

题目大意：对于一个长度为5的数字序列有三种操作

1.交换相邻的两个数字

2.将某个数字加一（对10取余）

3.将某个数字乘二（对10取余）

其中操作2，3分别能进行3次和2次，操作1可以进行无限多次，目标：在每一个query中，读入目标序列，求出并输出将 12345

变换至目标序列所需最小操作数，如果无法达到目标序列，输出 -1 。

思路：bfs预处理

从 12345 出发找到所有能达到的情况并记录最小操作数；

结果记录在 ans[100000][4][3]中，ans[num][i][j]代表

设计记录一个状态的结构体，括号中为初始状态

{

int num[6]; //到达序列 (1,2,3,4,5)

int op2,op3; //剩余操作2，3个数 (3,2)

int step; //已使用操作总数 (0)

}

bfs函数中，对于队列顶端状态，分别进行操作1，2，3的尝试变为新状态，如果发现对应状态在ans中存储的结果大于当前状态下的step，则进行更新，并将该状态压入队列，最后当队列为空的时候，则已走遍所有可达到状态。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

struct node {
	int num[7];
	int op2;
	int op3;
	int step;
};
int ans[100005][4][4];
int q_num(node t) {
	int sum=0;
	for(int i=1; i<=5; i++){
		sum+=t.num[i];
		sum*=10;
	}
	return sum/10;
}

void bfs(node t) {
	queue<node>q;
	memset(ans,0x3f,sizeof(ans));
	t.op2=3;
	t.op3=2;
	t.step=0;
	q.push(t);
	int n=q_num(t);
	ans[n][t.op2][t.op3]=0;
	while(!q.empty()) {
		node p=q.front();
		q.pop();

		for(int i=2; i<=5; i++) {
			node tp=p;
			swap(tp.num[i-1],tp.num[i]);
			int num=q_num(tp);
			tp.step++;
			if(tp.step>=ans[num][tp.op2][tp.op3])
				continue;
			q.push(tp);
			ans[num][tp.op2][tp.op3]=tp.step;
		}
		if(p.op2>0) {
			for(int i=1; i<=5; i++) {
				node tp=p;
				tp.op2--;
				tp.num[i]=(tp.num[i]+1)%10;
				int num=q_num(tp);
				tp.step++;
				if(ans[num][tp.op2][tp.op3]<=tp.step)
					continue;
				q.push(tp);
				ans[num][tp.op2][tp.op3]=tp.step;
			}
		}
		if(p.op3>0) {
			for(int i=1; i<=5; i++) {
				node tp=p;
				tp.op3--;
				tp.num[i]=(tp.num[i]*2)%10;
				int num=q_num(tp);
				tp.step++;
				if(ans[num][tp.op2][tp.op3]<=tp.step)
					continue;
				q.push(tp);
				ans[num][tp.op2][tp.op3]=tp.step;
			}
		}
	}
}

int main() {
	char test[9];
	node init;
	for(int i=1; i<=5; i++)
		init.num[i]=i;
	bfs(init);

	while(~scanf("%s",test+1)) {
		int query=0;
		for(int i=1; i<=5; i++) {
			query+=(test[i]-'0');
			query*=10;
		}
		query/=10;
		int res=0x3f3f3f3f;
		for(int i=0; i<=3; i++)
			for(int j=0; j<=2; j++)
				res=min(res,ans[query][i][j]);
		if(res==0x3f3f3f3f)
			cout<<-1<<endl;
		else
			cout<<res<<endl;
	}
	return 0;
}