Ryan_<

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)

#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;
}