题目很有趣，我觉得很有必要写一写。
【T1】买
题意：
(n)个人买(m)个物品，第(i)个人买的物品价格必须大于等于(a[i])，美观度必须大于等于(b[i])。
第(i)个物品的价格和美观度分别是(c[i])，(d[i])。
求出要满足所有人的最小花费。
题解：
考虑把两个限制转换成一个限制，即我们对物品按照美观度排序，那么一个人对应的可买就是一段连续的的区间了（不考虑价格），方便处理。
而对于价格最小，在所有的可买物品中，选取大于等于(a[i])的物品，这可以使用平衡树（set）维护。
仔细品味一下，这就是要以美观度，而不是价格排序的原因。
如果把人也按照美观度排序，就可以按顺序添加物品，方便处理。
其实是个贪心，正确性与最优性不难证明。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<set> 5 #define F(i,a,b) for(int i=a;i<=b;++i) 6 #define F2(i,a,b) for(int i=a;i<b;++i) 7 using namespace std; 8 int n,m,a[100001],b[100001],c[100001],d[100001],I[100001],J[100001]; 9 long long ans=0; 10 inline int cmp1(int p1,int p2){return b[p1]>b[p2];} 11 inline int cmp2(int p1,int p2){return d[p1]>d[p2];} 12 multiset<int> s; 13 multiset<int>::iterator iter; 14 void init(){ 15 scanf("%d%d",&n,&m); 16 F(i,1,n) scanf("%d%d",a+i,b+i),I[i]=i; 17 F(i,1,m) scanf("%d%d",c+i,d+i),J[i]=i; 18 std::sort(I+1,I+n+1,cmp1); std::sort(J+1,J+m+1,cmp2); 19 } 20 int main(){ 21 freopen("buy.in","r",stdin); 22 freopen("buy.out","w",stdout); 23 init(); 24 int j=1; 25 F(i,1,n){ 26 while(d[J[j]]>=b[I[i]]) s.insert(c[J[j]]), ++j; 27 iter=s.lower_bound(a[I[i]]); 28 if(iter!=s.end()) ans+=*iter, s.erase(iter); 29 else {puts("-1"); return 0;} 30 } printf("%lld",ans); 31 return 0; 32 }
【T2】加密
题意：
给一个数列(c[1cdots n])，定义变换(A^x(c_i)=sum_{j eq i}A^{x-1}(c_j)\,mod\,98765431;(xgeq 1))，而(A^0(c_i)=c_i)。
求出(A^x(c_i))。
题解：
先推式子，用(sum)表示初始元素的总和，用(now)表示这个元素，有(sum now=sum)，虽然(now)各不相同。
有(x=1)时，(res=sum-now)。
(x=2)时，(res=(n-2)sum+now)。
(x=3)时，(res=(n-1)(n-2)sum+sum-now)。
(x=4)时，(res=(n-1)^2(n-2)sum+(n-2)sum+now)。
(x=5)时，(res=(n-1)^3(n-2)sum+(n-1)(n-2)sum+sum-now)。
(x=6)时，(res=(n-1)^4(n-2)sum+(n-1)^2(n-2)sum+(n-2)sum+now)。
(x=7)时，(res=(n-1)^5(n-2)sum+(n-1)^3(n-2)sum+(n-1)(n-2)sum+sum-now)。
(vdots)
于是有：
当(x=2k+1)是奇数时，(res=[sum_{i=0}^{k-1}[(n-1)^2]^i](n-1)(n-2)sum+sum-now)。
当(x=2k)是偶数时，(res=[sum_{i=0}^{k-1}[(n-1)^2]^i](n-2)sum+now)。
其中(sum_{i=0}^{k-1}[(n-1)^2]^i)部分相同，其实是可以化简的，化简为(frac{(n-1)^{2k}-1}{(n-1)^2-1})。
于是直接计算就做完了，注意求逆元。
1 #include<cstdio> 2 #define Mod 98765431 3 long long n,t,a[50001],sum=0; 4 long long M(long long x,long long y){return x*y%Mod;} 5 int Pow(long long base,long long exp){ 6 long long ans=1; 7 for(;exp;(exp&1)?ans=M(ans,base):(0), base=M(base,base), exp>>=1); 8 return ans; 9 } 10 int main(){ 11 freopen("password.in","r",stdin); 12 freopen("password.out","w",stdout); 13 scanf("%I64d%I64d",&n,&t); 14 for(int i=1;i<=n;++i) scanf("%lld",a+i),sum=(sum+a[i])%Mod; 15 long long W=Pow(n-1,2); 16 long long S=Pow(W,t>>1)-1; 17 if(S<0) S+=Mod; 18 S=M(S,Pow(((W-1)<0)?(W-1+Mod):(W-1),Mod-2)); 19 if(t&1){ 20 S=(M(M(M(n-1,n-2),sum),S)+sum)%Mod; 21 for(int i=1;i<=n;++i) printf("%lld ",(S-a[i]+Mod)%Mod); 22 } 23 else{ 24 S=M(M(n-2,sum),S); 25 for(int i=1;i<=n;++i) printf("%lld ",(S+a[i])%Mod); 26 } 27 return 0; 28 }
【T3】花费
题意：
在一个字符串中添加或删除字母，每个字母的添加与删除费用确定，问把字符串变成回文的，最少花费多少？
题解：
看做字符串与其逆序做匹配，简单的序列DP。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 int n,m,a[4001],b[4001],f[4001][4001],v[256]; 5 char str[4001]; 6 int main(){ 7 freopen("cost.in","r",stdin); 8 freopen("cost.out","w",stdout); 9 scanf("%d%d",&n,&m); 10 scanf("%s",str); 11 for(int i=1;i<=m;++i) b[m-i+1]=a[i]=str[i-1]; 12 for(int i=1,x,y;i<=n;++i) scanf("%s%d%d",str,&x,&y), v[(int)str[0]]=std::min(x,y); 13 memset(f,0x3f,sizeof f); 14 f[0][0]=0; 15 for(int i=1;i<=m;++i) f[i][0]=f[i-1][0]+v[a[i]]/*, printf("%d,%d: %d ",i,0,f[i][0])*/; 16 for(int j=1;j<=m;++j) f[0][j]=f[0][j-1]+v[b[j]]/*, printf("%d,%d: %d ",0,j,f[0][j])*/; 17 for(int Q=1;Q<=m+m;++Q){ 18 for(int i=std::max(1,Q-m);i<=m&&i<Q;++i){ 19 int j=Q-i; 20 f[i][j]=std::min(f[i][j],f[i-1][j]+v[a[i]]); 21 f[i][j]=std::min(f[i][j],f[i][j-1]+v[b[j]]); 22 if(a[i]==b[j]) f[i][j]=std::min(f[i][j],f[i-1][j-1]); 23 // printf("%d,%d: %d ",i,j,f[i][j]); 24 } 25 } 26 printf("%d",f[m][m]/2); 27 return 0; 28 }