4
25
2016
0

SXOI2016题解&&代码~

其实SXOI2014&SXOI2015也有写一些,不过还没整理..今后不能再有这个毛病了

 

T1 过桥(bridge)

sol1:搜索可过

dfs(n,cur)前n个人过桥所需的时间。n个人最多不会超过n组,枚举每组有哪些人即可。

a[i]表示第i组总重,a[i]>W时i++,a[i]==0表示实际组数<i

注意剪枝:

/***dfs(int p,int cur)***/
if (cur>=ans) return;
if (p==n+1){ans=cur;return;}

还可保证之后的得到的答案一定比之前的优,故直接赋值即可。

动态规划竟然比搜索慢,高一学弟好腻害,自己再不用心一定会被拍在沙滩上

sol2:状态压缩dp

Dp[S] :已过桥的人的集合为S,所用的最少时间
 
预处理出所有可能集合的过桥时间tim,总重量sum
 
Dp[S]=min{dp[s1]+tim[s2]}
(sum[s2] ≤ W 且 s1 ∪ s2 = s, s1 ∩ s2 = ∅)
 
const int N=20,M=65536;
int W,n,t[N],w[N];
int bin[M],tim[M],sum[M],f[M];
int main()
{
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	W=getint();	n=getint();
	F(i,1,n) t[i]=getint(),w[i]=getint();
	
	bin[0]=1;
	F(i,1,N) bin[i]=bin[i-1]<<1;
	
	memset(tim,0,sizeof(tim));
	memset(sum,0,sizeof(sum));
	F(i,0,bin[n]-1)
		F(j,1,n)if(i&bin[j-1]){
			tim[i]=max(tim[i],t[j]);
			sum[i]+=w[j];
		}
		
	memset(f,127,sizeof(f));
	f[0]=0;
	F(i,1,bin[n]-1)
		for(int j=i;j;j=i&(j-1)){
			if(sum[j]<=W) f[i]=min(f[i],f[i^j]+tim[j]);
		}
	printf("%d\n",f[bin[n]-1]);
	return 0;
}

 


T2 序列(sequence)

令G(0)=0,F(0)=0
可以发现G(n) = F(1)G(n-1) + F(2)G(n-2) + ... + F(n)G(0)
G(n)-G(n-1) = (F(1)-F(0))*G(n-1) + (F(2)-F(1))*G(n-2) + (F(3)-F(2))*G(n-3) + ... + (F(n)-F(n-1))*G(0)
= G(n-1) + 0 + F(1)G(n-2) + F(2)G(n-3) + ... + F(n-2)G(0)
= G(n-1) + G(n-2)
所以 G(n)=2G(n-1)+G(n-2)

考场上我打表找规律的..
这个叫做广义斐波那契数列,事实上线性递推式均可以用矩阵乘法加速,在O(logn)时间内求第n项。
矩阵很好构造,类似 poj3070
#define MOD 1000000007
typedef long long LL;
LL n;int m;
const int M=3;
inline LL getlong()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct matrix{
	LL f[M][M];
	void init(){memset(f,0,sizeof(f));}
	friend matrix operator *(const matrix &a,const matrix &b){
		matrix c;
		F(i,0,m-1) F(j,0,m-1){
			c.f[i][j]=0;
			F(k,0,m-1) c.f[i][j]=(c.f[i][j]+a.f[i][k]*b.f[k][j])%MOD;
		}
		return c;
	}
}t,ans;
void matrix_pow()
{
	F(i,0,m-1) ans.f[i][i]=1;
	ans.f[0][1]=ans.f[1][0]=0;
	while(n){
		if(n&1) ans=ans*t;
		t=t*t;
		n>>=1;
	}
}	
int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	n=getlong();m=2;
	t.init();ans.init();
	t.f[0][0]=0;
	t.f[0][1]=t.f[1][0]=1;
	t.f[1][1]=2;
	matrix_pow();
	printf("%lld\n",ans.f[0][1]);
	return 0;
}

 


T3 字符串(string)

sol:暴力的做法是枚举每两个串拼接后得到的串,判断是否是回文串.判断回文串通用做法是hash.

但是没有利用一个重要条件:给出的串均为回文串.——拼接后的新串是回文串当且仅当两串相同或一个是另一个的前缀子串

Trie的使用就很巧妙了!每次在trie中找到一个串,都要判断它的前缀子串(之前经过的单词节点所代表的串)是否可与它组成回文串.

回文串判断直接s1+s2==s2+s1,不须考虑每个串内部顺序.

统计个数时注意是有序的,然后减去重复的情况就可以了

这道题在bzoj上交是AC的,可最后测试的结果只有90分,就当攒人品了...

所以搬运阿当的代码吧

#define maxn 2000005
#define base 233
int n,tot=1;
int l[maxn],cnt[maxn],num[maxn],t[maxn][26];
ll ans;
ull ha[maxn],p[maxn];
char ch[maxn];
string s[maxn];
int main()
{
	p[0]=1;F(i,1,2000000) p[i]=p[i-1]*base;
	n=read();
	F(i,1,n)
	{
		l[i]=read();
		scanf("%s",ch);s[i]=ch; //字符串这样读入更快 
//		cin>>s[i]; //TLE
		int now=1;ull tmp=0;
		F(j,0,l[i]-1)
		{
			int x=s[i][j]-'a';
			if (!t[now][x]) t[now][x]=++tot;
			now=t[now][x];
			tmp=tmp*base+(ull)(x+1);
		}
		cnt[now]++;num[now]=i;ha[i]=tmp;
	}
	F(i,1,n)
	{
		int now=1;
		F(j,0,l[i]-1)
		{
			now=t[now][s[i][j]-'a'];
			if (cnt[now]&&ha[num[now]]*p[l[i]]+ha[i]==ha[i]*p[l[num[now]]]+ha[num[now]]) ans+=cnt[now];
		}
	}
	ans=ans*2-n;
	printf("%lld\n",ans);
	return 0;
}

 


T4 最大值

sol:令b[]数组记录a[]前缀最大值,则可以知道b[]单调不降

考虑修改一个数时,只对x位置及之后的b[]产生影响

y>0,用线段树维护b[]数组的 值与区间和,区间修改即可得到70%

但是y的正负对x位置及之后的前缀最大值影响是不同的!

100%: 线段树维护区间最大值mx、区间最大值的和sum、左子区间对右子区间最大值的影响sp

单点修改后,找到影响最远的位置pos,计算sp并用sp更新sum.

tmp表示右子区间没有被影响的最大值.

int n,pos;
ll tmp,a[maxn];
struct seg{ll sum,mx,sp;}t[4*maxn];
inline void get(int k,int l,int r,ll x)
{
   if(l==r){pos=l;tmp+=t[k].sum;return;}
   else if(t[k<<1].mx<x)get(rch,x);
   else{
   	 tmp+=t[k<<1|1].sum+t[k].sp;
   	 get(lch,x);
   }
}
inline void pushup(int k,int l,int r)
{
   int x=k<<1,y=k<<1|1;
   t[k].mx=max(t[x].mx,t[y].mx);
   if(t[x].mx>t[y].mx)t[k].sp=t[x].mx*(r-mid)-t[y].sum;
   else
   {
   	 tmp=0;
   	 get(rch,t[x].mx);
   	 t[k].sp=t[x].mx*(pos-1-mid)-(t[y].sum-tmp);
   }
   t[k].sum=t[x].sum+t[y].sum+t[k].sp;
}
inline void change(int k,int l,int r,int x)
{
   if(!x||x>n)return;
   if(l==r){t[k].sum=t[k].mx=a[l];return;}
   if(x<=mid)change(lch,x);else change(rch,x);
   pushup(k,l,r);
}
inline void build(int k,int l,int r)
{
	if(l==r){t[k].sum=t[k].mx=a[l];return;}
	build(lch);build(rch);
	pushup(k,l,r);
}
inline void print(ll x)//输出优化!
{
   if(x<10){putchar('0'+x);return;}
   print(x/10);putchar('0'+x%10);
}
int main()
{
   freopen("max.in","r",stdin);
   freopen("max.out","w",stdout);
   n=read();
   for1(i,n)a[i]=read();
   build(1,1,n);
   print(t[1].sum);printf("\n");
   int T=read();
   while(T--)
   {
   	 int x=read(),y=read();
   	 a[x]+=y;
   	 change(1,1,n,x);
   	 print(t[1].sum);printf("\n");
   }
   return 0;
}
 
 
Category: 比赛 | Tags: 线性代数 动态规划 线段树 搜索 Trie树 回文串 | Read Count: 215

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com