[C++知识库]SCOI2010

生成字符串

这题实际是数论？可以考虑把 $1$ 的个数和 $0$ 的个数的和看做 $x$，差看做 $y$，那向右上走表示选择 $1$ ,向右下走表示选择 $0$，这道题就表示为从 $(0,0)$ 走到 $(n+m,n?m)$，其中 $m$ 步选择向右下走，总方案数即为 ${\mathrm{C}}_{n+m}^m$，那么考虑限制条件，经过 $y=?1$ 的方案就是 $1$ 比 $0$ 少的方案，而根据对称性，从 $(0,0)$ 经过 $y=?1$ 到 $(n+m,n?m)$ 相当于从 $(?2,0)$ 走到 $(n+m,n?m)$。这个方案数即为${\mathrm{C}}_{n+m}^{m?1}$ ，所以答案即为
${\mathrm{C}}_{n+m}^m?{\mathrm{C}}_{n+m}^{m?1}$，组合数可以用逆元搞定。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,p=20100403;
int n,m,jc[N],ni[N];
int qpow(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=1ll*ret*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return ret;
}
int C(int x, int y) {
    int z=1ll*jc[x]*ni[y]%p;
    return 1ll*z*ni[x-y]%p;
}
int main() {
    jc[0]=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+m;i++) jc[i]=1ll*jc[i-1]*i%p;
    ni[n+m]=qpow(jc[n+m],p-2);
    for(int i=n+m-1;i>=0;i--)
        ni[i]=1ll*ni[i+1]*(i+1)%p;
    return printf("%d\n",(C(n+m,m)-C(n+m,m-1)+p)%p),0;
}

序列操作

更新中。。。(haibuhui)

连续攻击游戏

不多说了,看代码。

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
    T ch=getchar();x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}
template<typename T>inline void prt(T x){
    if(x>9) prt(x/10);
    putchar(x%10|48);
}
int a,b;
int n;
bool c[10005];
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        read(a),read(b);
        if(b<a) a^=b,b^=a,a^=b;
        if(c[a]) c[b]=1;
        else c[a]=1;
    }
    for(int i=1;i<=10001;++i)
        if(!c[i]){
            prt(i-1);
            return 0;
        }
}

传送带

明显这题的最优路线应是 $AE+EF+FD$，其中 $E$ 在 $AB$ 上，$F$ 在 $CD$ 上。设 $F(X,Y)$ 为 $X$ 到 $Y$ 的距离。答案就是 $$\frac{AE}{P}+\frac{EF}{R}+\frac{FD}{Q}$$这个方程有两个未知数，不好求最小值。不妨假设其中一个已知（这里为 $E$），那对于 $FD$ 而言只要求出一个满足 $\frac{EF}{R}+\frac{FD}{Q}$ 最小的值就行了。
不妨设 $FD$ 为 $x$，我们很明显可以根据 $C$ 和 $D$ 的坐标求出 $F$ 的坐标，都是一个 $x$ 带点系数和常数，最终的式子是一个关于 $x$ 的单峰函数（可以自己解解），那对于单峰函数，我们三分就可以求出最优的 $FD$。既然 $FD$ 都三分了，为什么 $AE$ 不一起三分呢 ? 综上此题是一个三分套三分。
但其实我这道题不是三分做的，所以待会没有三分代码，我想的是，既然只有 $AE,FD$ 两个变量，为什么不暴力枚举呢？所以我的做法是暴力枚举 $AE,FD$ 的长度，虽然分少了可能精度不够，分多了可能会 $TLE$，但我分了 $3500$ 份就 $AC$ 了。
暴力代码

#include<bits/stdc++.h>
using namespace std;
#define Re register
int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,P,Q,R;
double Ex,Ey,Fx,Fy;
double Lab,Lcd,mab,mcd;
double Xab,Yab,Xcd,Ycd;
double ans=9999999.9;
inline double dis(double A,double B,double C,double D){
	return sqrt((A-C)*(A-C)+(B-D)*(B-D));
}
inline double get(double i,double j){
	Ex=i*Xab+Ax;
	Ey=i*Yab+Ay;
	Fx=j*Xcd+Dx;
	Fy=j*Ycd+Dy;
	return sqrt(i*Xab*i*Xab+i*Yab*i*Yab)/P+dis(Ex,Ey,Fx,Fy)/R+sqrt(j*Xcd*j*Xcd+j*Ycd*j*Ycd)/Q;
}
int main(){
//	freopen("tran.in","r",stdin);
//	freopen("tran.out","w",stdout);
	scanf("%d%d%d%d%d%d%d%d%d%d%d",&Ax,&Ay,&Bx,&By,&Cx,&Cy,&Dx,&Dy,&P,&Q,&R);
	Xab=(Bx-Ax),Xcd=(Cx-Dx);
	Yab=(By-Ay),Ycd=(Cy-Dy);
	mab=1.0/3500.0,mcd=1.0/3500.0;
	for(Re int i=0;i<=3500;i++)
		for(Re int j=0;j<=3500;j++)
			ans=min(ans,get(i*mab,j*mcd));
//	find(1079);
	printf("%.2lf",ans);
}

幸运数字

思路很简单，得到所有的合法数字，然后容斥。即$$\sum _{i=1}^n?\frac{R}{x_i}??\sum _{1\le i<j<n}?\frac{R}{lcm(x_i,x_j)}?+\sum _{1\le i<j<k<n}?\frac{R}{lcm(x_i,x_j,x_k)}???+(?1{)}^{n+1}\sum ?\frac{R}{lcm(x_i,x_j?x_n)}?$$ 但直接爆搜肯定是不行的，我们需要加yi点点小剪枝。

1. 对于 $6$ 和 $66$,这种情况，$66$ 肯定没有作用，可以删去。
2. 从最大的合法数字倒着来，更快超出 $R$ 的范围。

其它关于确定合法数字之类的详见代码。

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
	T ch=getchar();x=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
template<typename T>inline void prt(T x){
	if(x>9) prt(x/10);
	putchar(x%10|48);
}
#define ll long long
ll a,b,ans,n;
ll p[3005],cnt=-1;
ll gcd(ll x,ll y){return y==0 ? x:gcd(y,x%y);}
void mak(ll x){
	if(x>b) return ;
	p[++cnt]=x;
	mak((x<<3)+(x<<1)+6);
	mak((x<<3)+(x<<1)+8);
}
void dfs(int x,ll lcm,int num){
	if(x>n){
		if(lcm!=1){
			if(num&1) ans+=((b/lcm)-(a/lcm));
			else ans-=((b/lcm)-(a/lcm));
		}
		return ;
	}
	dfs(x+1,lcm,num);
	ll d=p[x]/gcd(p[x],lcm);
	if(lcm<=b/d) dfs(x+1,lcm*d,num+1);
	return ;
}
signed main(){
	scanf("%lld%lld",&a,&b);a--;
	mak(0);
	sort(p+1,p+cnt+1);
	n=cnt;
	for(int i=1;i<=cnt;++i)
		for(int j=1;j<i;++j)
			if(p[i]%p[j]==0) {p[i]=9999999997,n--;break;}
	sort(p+1,p+cnt+1);
	reverse(p+1,p+n+1);
	dfs(1,1,0);
	prt(ans);
	return 0;
}

股票交易

读完题后，应该很容易想到用动态规划来解。设 $F[i,j]$ 表示第 $i$ 天手上有 $j$ 张股票能赚多少钱，考虑转移。

1. 凭空买，与前面的没有关系，同时也是状态的初值， 其它赋值为无穷小，$F[i,j]=?a{p}_i?j(0\le j\le a{s}_i)$
2. 不做买卖 $F[i,j]=max(F[i,j],F[i?1,j])$
3. 做买卖，这是本题的主要问题，此处以买为例。
   题上虽说至少要隔 $w$ 天，那是哪一天呢？其实就是第 $i?w?1$ 天，因为前面即使更优，也从情况 2：不做买卖转移到了第 $i?w?1$ 天，这样可以省掉一个 $for$ 循环。
   接下来，我们不妨设第 $i?w?1$ 天手上有 $k$ 张，要转移到 $F[i,j]$ (因为是买 $k$ 肯定小于 $j$)。可得方程：
   $$F[i,j]=\max (F[i,j],F[i?w?1,k]?(j?k)\times a{p}_i)$$
   但这样 $O(n{m}^2)$ 肯定要 $TLE$ 怎么办呢？我们不妨将上式拆了$$F[i,j]=\max (F[i,j],F[i?w?1,k]+k\times a{p}_i)?j\times a{p}_i$$可以发现，对于所有的 $j$ 来说，$F[i?w?1,k]+k\times a{p}_i$ 这一部分是不变的，而当 $k$ 在变化时，$?j\times a{p}_i$ 也是不变的。这不就是滑动窗口吗？接着将单调队列的解法套上去就行了。关于单调队列详见代码注释。
   最后对于买来说，$j$ 应该顺序，对于卖 $j$ 应该逆序。

#include<bits/stdc++.h>
using namespace std;
template<typename W>inline void read(W &x){
	W ch=getchar(),tx=1;x=0;
	while(!isdigit(ch)) tx=ch=='-'?-1:tx,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x=tx*x;
}
int n,m,w,ap,bp,as,bs,ans,f[2001][2001];
int l,r,q[2001];
int main(){
	read(n),read(m),read(w);
	memset(f,0xcf,sizeof f);
	for(int i=1;i<=n;++i){
		read(ap),read(bp),read(as),read(bs);
		for(int j=0;j<=as;++j) f[i][j]=-1*j*ap;
		for(int j=0;j<=m;++j) f[i][j]=max(f[i][j],f[i-1][j]);
		if(i<=w) continue;
		l=1,r=0;
		for(int j=0;j<=m;++j){
			while(l<=r && q[l]<j-as) l++;// k>=j-as[i],此处是队头出队
			while(l<=r && f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap) r--;// 保证是单调递减的
			q[++r]=j;
			if(l<=r) f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);
		}
		l=1,r=0;
		for(int j=m;j>=0;--j){
			while(l<=r && q[l]>j+bs) l++;
			while(l<=r && f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp) r--;
			q[++r]=j;
			if(l<=r) f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*bp-j*bp);
		}
	}
	for(int i=0;i<=m;++i) ans=max(ans,f[n][i]);
	printf("%d\n",ans);
	return 0;
}