test

201904

Posted by JU on April 2, 2019

smoj520

P1

$\text{yy}$ 一下可以发现,最优策略肯定是:

$\text{1.}$ 在一个区间反复横跳

$\text{2.}$ 向右换一个区间

$\text{3.}$ 重复 $\text{1,2}$

因为切换区间时经过的权值和肯定是负的,所以如果不按上述策略,则会导致重复经过这些负的区间.

于是 $\text{dp}$ :

$sum$ :区间权值和

$s[i]$ :以 $\text{i}$ 结尾的最大权值后缀和

$f[i]$ :到达 $\text{i}$ 位置时所用最小移动次数

$g[i]$ :在满足 $f$ 的同时,能获得的最大权值

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
#define pr(p) printf("%lld\n",p)
const long long oo=1000000000000000000;
const int N=110;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (LL &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
LL up (LL A,LL B) { return (LL)(A/B)+!!(A%B); }
LL a[N],sum[N][N],w[N],s[N],f[N],g[N];
int main()
{
	// freopen ("2843.in","r",stdin);
	// freopen ("2843.out","w",stdout);
	LL T; sc(T);
	while (T--)
	{
		LL n,k; sc(n),sc(k);
		for (int i=1; i<=n; i++)
			sc(a[i]);
		for (int i=1; i<=n; i++)
			for (int j=i; j<=n; j++)
				sum[i][j]=sum[i][j-1]+a[j];
		for (int i=1; i<=n; i++)
		{
			s[i]=-oo;
			for (int j=1; j<=i; j++)
				if (sum[j][i]> s[i]) s[i]=sum[j][i];
		}
		f[1]=1,g[1]=a[1];
		LL ans=max (0LL,(k-f[1])*s[1]+g[1]);
		for (int i=2; i<=n; i++)
		{
			f[i]=oo,g[i]=-oo;
			for (int j=1; j< i; j++)
			{
				LL s1=sum[j+1][i],c=0;
				if (s1+g[j]< 0)
				{
					if (s[j]> 0) c=up (-(s1+g[j]),s[j]*2)*2;
					else continue;
				}
				if (f[j]+c> k) continue;
				if (f[j]+c==f[i]) g[i]=max (g[i],g[j]+c*s[j]+s1);
				if (f[j]+c< f[i]) f[i]=f[j]+c,g[i]=g[j]+c*s[j]+s1;
			}
			if (g[i]>=0&&f[i]<=k) ans=max (ans,(k-f[i])*s[i]+g[i]);
		}
		pr(ans);
	}

	return 0;
}

P2

$\text{yy}$ 一下:

$\text{1.}$ $F$ 和 $S$ 的数量尽量接近

$\text{2.}$ $F+S$ 最大不会超过 $2\lceil\sqrt{n}\rceil$

于是硬核模拟:

$\text{1.}$ 当当前金币数 $\text{>=price}$ ,且雇佣更多人更优,就不断增加 $\text{F,S}$ 中较小的一个

$\text{2.}$ 否则一次性增加到金币数 $\text{>=price}$

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef __int128 LL;
typedef double db;
inline void sc (LL &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
inline void pr(LL x)
{
    if (x< 0)
    {
	putchar('-');
	x=-x;
    }
    if (x> 9) pr(x/10);
    putchar(x%10+'0');
}
LL up (LL A,LL B) { return (LL)(A/B)+!!(A%B); }
int main()
{
	// freopen ("2844.in","r",stdin);
	// freopen ("2844.out","w",stdout);
	LL T; sc(T);
	while (T--)
	{
		LL a,b,p,s; sc(a),sc(b),sc(p),sc(s);
		if (a< b) swap (a,b);
		if (1LL*a*b> s) { pr(1LL); continue; }
		LL ans=up (s,a*b),cur=0,sum=0;
		bool fg=0;
		while (1)
		{
			while (sum>=p)
			{
				LL g1=up (s-sum,a*b),g2=up (s-sum+p,a*(b+1));
				if (cur+min (g1,g2)> ans) { fg=1; break; }
				ans=cur+min (g1,g2);
				if (g2> g1) { fg=1; break; }
				++b;
				sum-=p;
				if (a< b) swap (a,b);
				if (b>=1000000) { fg=1; break; }
			}
			if (fg) break;
			if (sum>=s) break;
			LL q=up (p-sum,a*b);
			sum+=q*a*b;
			cur+=q;
		}
		pr(ans);
	}

	return 0;
}

P3

$\text{dp}$

$f[i]$ 表示桌上有 $\text{i}$ 个,手上有 $\text{1}$ 个时,距离游戏结束剩余轮数的期望

易得 $f[0]=f[2*n]=0$

所求的为 $f[n]$

转移:

\[f[i]=\frac{1}{2}(f[i+1]+1)+\sum_{j=2}^{ma}\frac{1}{2^j}(f[i-2^{j-1}+2]+j)+\frac{ma}{2^{ma}}\]

有 $\frac{1}{2^j}$ 的概率进行 $j-1$ 次操作二,再进行一次操作一.

设

\[s=\sum_{j=2}^{ma}\frac{1}{2^j}(f[i-2^{j-1}+2]+j)\]

则

\[\frac{1}{2}(f[i+1]+1)=f[i]-s-\frac{ma}{2^{ma}}\]

化简后

\[f[i+1]=2(f[i]-s-\frac{ma}{2^{ma}})+1\]

其中

\[ma=\log_{2}{i}+1\]

可以发现,每个 $f[i]$ 都是 $\sum_{j=0}^{i-1}a[j]*f[j]+B$ ,所有用到的未知数( $f$ )都是一次项.

而且,还可以知道,当 $f[1]$ 确定,所有的 $f$ 都确定了.

有一个问题,可能当 $f[1]=x$ 时, $f[n*2]!=0$.

可以设每个 $ f[i]=a_i*x+b_i $ ,转移到 $f[n*2]$ 后算出 $x$ (就是 $f[1]$ ),再计算 $f[n]$ 即可.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=2510000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
int ksm (int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
int x[N],y[N],lo[N],mi[N],inv[N];
int main()
{
	//freopen ("2845.in","r",stdin);
	//freopen ("2845.out","w",stdout);
	lo[0]=-1;
	for (int i=1; i<=200000; i++)
		lo[i]=lo[i>>1]+1;
	mi[0]=inv[0]=1;
	for (int i=1; i<=20; i++)
		mi[i]=mi[i-1]*2,inv[i]=ksm (mi[i],mod-2);
	int G; sc(G);
	while (G--)
	{
		memset (x,0,sizeof (x)),memset (y,0,sizeof (y));
		int n; sc(n);
		x[1]=1;
		for (int i=1; i<=n*2-1; i++)
		{
			int ma=lo[i]+1;
			int sx=0,sy=0;
			for (int j=2; j<=ma; j++)
			{
				sx=(sx+1LL*inv[j]*(x[i-mi[j-1]+2]))%mod;
				sy=(sy+1LL*inv[j]*(y[i-mi[j-1]+2]+j))%mod;
			}
			x[i+1]=(2LL*(x[i]-sx)%mod+mod)%mod;
			y[i+1]=((2LL*(y[i]-sy-1LL*ma*inv[ma]%mod)%mod-1)%mod+mod)%mod;
		}
		int X=(1LL*-y[n*2]*ksm (x[n*2],mod-2)%mod+mod)%mod;
		int ans=(1LL*x[n]*X%mod+y[n])%mod;
		pr(ans);
	}

	return 0;
}

P4

$\text{1.}$ 一个方案合法,当且仅当操作完成后,每格与其相邻格子(共 $\text{9}$ 格)的异或和为 $\text{1}$ (黑色为 $\text{1}$ )

于是有一个 $O(\frac{n^3m^3}{64})$ 的 $\text{bitset}$ 瓜丝消元

$\text{2.}$ 当从上到下,从左到右枚举时,处于一堆格子的 $\text{(x+1,y+2)}$ 位置的格子颜色已确定.即当 $\text{(a-1,b-2)}$ 存在时, $\text{(a,b)}$ 可以直接确定.

(“一堆格子”指某个格子 $\text{(x,y)}$ 及其相邻格子)

$\text{3.}$ 因此,前两行和前一列的格子可以随便取(作为未知数),并用它们表示出所有格子,但取值后可能无解.

$\text{4.}$ 在计算每个 $\text{(x+1,y+2)}$ 格子时,需要用掉 $\text{(x,y)}$ 对应的方程,而最后两行和最后一列是没有 $\text{(x+1,y+2)}$ 格子的,可以把这些点列成方程,解出自由元的个数 $\text{ans}$ ,答案即为 $2^{ans}$ .

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <bitset>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=500;
const int mod=123456789;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
int mi[N];
const int dx[8]={2,1,-1,-1,1,-2,-2,2},dy[8]={1,2,-2,2,-2,-1,1,-1};
int n,m;
bitset <N> b[N][N],a[N];
bool check (int x,int y) { return 1<=x&&x<=n&&1<=y&&y<=m; }
int main()
{
	//freopen ("2847.in","r",stdin);
	//freopen ("2847.out","w",stdout);
	mi[0]=1;
	for (int i=1; i< N; i++)
		mi[i]=mi[i-1]*2%mod;
	int G; sc(G);
	while (G--)
	{
		int num=0; sc(n),sc(m);
		memset (a,0,sizeof (a));
		memset (b,0,sizeof (b));
		for (int i=1; i<=n; i++)
			for (int j=1; j<=m; j++)
				if (i<=2||j==1) b[i][j][++num]=1;
		num=0;
		for (int i=1; i<=n; i++)
			for (int j=1; j<=m; j++)
			{
				int x=i+2,y=j+1;
				if (x<=n&&y<=m)
				{
					b[x][y]^=b[i][j];
					for (int k=1; k< 8; k++)
					{
						int ax=i+dx[k],ay=j+dy[k];
						if (check (ax,ay)) b[x][y]^=b[ax][ay];
					}
				}
				else
				{
					a[++num]^=b[i][j];
					for (int k=0; k< 8; k++)
					{
						int ax=i+dx[k],ay=j+dy[k];
						if (check (ax,ay)) a[num]^=b[ax][ay];
					}
				}
			}
		int ans=0,cur=1;
		for (int i=1; i<=num; i++)
		{
			int k=cur;
			while (!a[k][i]&&k<=num) ++k;
			if (k> num) ++ans;
			else
			{
				swap (a[cur],a[k]);
				for (int j=cur+1; j<=num; j++)
					if (a[j][i]) a[j]^=a[cur];
				++cur;
			}
		}
		pr(mi[ans]);
	}
	return 0;
}
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：201904”
CATALOG
    FRIENDS