A：二分答案，从左往右考虑每个人，选尽量靠左的钥匙即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define int long long

#define N 2010

#define M 2010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,p,a[N],b[M];

bool flag[M];

bool check(int k)

{

	memset(flag,0,sizeof(flag));

	for (int i=1;i<=n;i++)

	{

		bool f=0;

		for (int j=1;j<=m;j++)

		if (!flag[j]&&abs(a[i]-b[j])+abs(p-b[j])<=k)

		{

			flag[j]=1;

			f=1;

			break;

		}

		if (!f) return 0;

	}

	return 1;

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),m=read(),p=read();

	for (int i=1;i<=n;i++) a[i]=read();

	for (int i=1;i<=m;i++) b[i]=read();

	sort(a+1,a+n+1);sort(b+1,b+m+1);

	int l=0,r=2000000000,ans=0;

	while (l<=r)

	{

		int mid=l+r>>1;

		if (check(mid)) ans=mid,r=mid-1;

		else l=mid+1;

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：暴力，每次找到下一张被扔出去的牌并累加距离（即翻几张牌后会翻到）即可，距离用树状数组维护。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,a[N],id[N],tree[N];

ll ans;

bool cmp(const int&x,const int&y)

{

	return a[x]<a[y]||a[x]==a[y]&&x<y;

}

void add(int k,int x){while (k<=n) tree[k]+=x,k+=k&-k;}

int query(int k){int s=0;while (k) s+=tree[k],k-=k&-k;return s;}

int dis(int x,int y)

{

	if (x<=y) return query(y)-query(x);

	else return query(n)+query(y)-query(x);

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

	for (int i=1;i<=n;i++) id[i]=i,a[i]=read();

	sort(id+1,id+n+1,cmp);

	for (int i=1;i<=n;i++) add(i,1);

	int last=0;

	for (int i=1;i<=n;i++)

	{

		int t=i;

		while (t<n&&a[id[t+1]]==a[id[i]]) t++;

		int p=i;

		for (int j=i+1;j<=t;j++) if (dis(last,id[j])<dis(last,id[p])) p=j;

		ans+=dis(last,id[p]),add(id[p],-1),last=id[p];

		for (int j=p+1;j<=t;j++)

		ans+=dis(last,id[j]),add(id[j],-1),last=id[j];

		for (int j=i;j<p;j++)

		ans+=dis(last,id[j]),add(id[j],-1),last=id[j];

		i=t;

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：不考虑d是某数因子的特殊情况的话，相当于要求nd-Σai mod d<=k，最大化d。而ai mod d=ai-⌊ai/d⌋*d，众所周知⌊ai/d⌋只有sqrt(ai)种取值。在所有⌊ai/d⌋都不变的一段区间内，最大的d可以很容易的算出来。于是暴力找出所有区间分割点（包括每个数的因数，因为不满足上述式子），对分割点暴力验证，区间内直接算出最大取值判一下是否合法即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 110

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,a[N],t;

ll k,d,b[10000010];

void print(ll x){cout<<x;exit(0);}

bool check(ll x)

{

	ll s=0;

	for (int i=1;i<=n;i++)

	if (a[i]%x) s+=x-a[i]%x;

	return s<=k;

}

ll check(ll l,ll r)

{

	if (l>r) return -1;

	ll s=n,tot=0;

	for (int i=1;i<=n;i++) s+=a[i]/l,tot+=a[i];

	tot+=k;

	if (tot/s>=l) return min(tot/s,r);

	else return -1;

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	cin>>n>>k;

	for (int i=1;i<=n;i++) cin>>a[i];

	for (int i=1;i<=n;i++)

	{

		for (int j=1;j*j<=a[i];j++)

		if (a[i]%j==0)

		{

			b[++t]=j;

			if (j*j<a[i]) b[++t]=a[i]/j;

		}

		for (int j=1;j<=a[i];j++)

		{

			b[++t]=j;

			j=a[i]/(a[i]/j);

		}

	}

	sort(b+1,b+t+1);

	t=unique(b+1,b+t+1)-b-1;b[++t]=1000000000000ll;

	for (int i=t;i>=2;i--)

	{

		if (check(b[i])) print(b[i]);

		if (check(b[i-1]+1,b[i]-1)>0) print(check(b[i-1]+1,b[i]-1));

	}

	cout<<1;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：容易想到设f[i]为i层满二叉树的答案，由f[i-1]转移。但考虑一下容易发现无法处理由某子树走到根再走回该子树的情况。这个转移需要知道选两条不相交路径的方案数。要求出这个似乎又要知道选更多条不相交路径的方案数。

　　那么自然的有设f[i][j]为i层满二叉树无序选j条不相交路径的方案数。看起来第二维状态是指数级别的，不过先不管这个。

　　考虑转移。显然其中至多只有一条路径经过根。

　　如果没有路径经过根，方案数为Σf[i-1][x]*f[i-1][j-x]。

　　如果根是一个孤立路径，方案数为Σf[i-1][x]*f[i-1][j-x-1]。

　　如果根是路径端点，方案数为Σf[i-1][x]*f[i-1][j-x]*2*j。

　　如果根是由某子树走上去再走下来的，方案数为f[i-1][x]*f[i-1][j-x+1]*2*C(j+1,2)。

　　和最开始的想法相同，求f[i][j]至多只会用到f[i-1][j+1]。最终我们要求f[n][1]，我们中间需要用到的第二维状态并不会超过n。于是状态数n2，复杂度O(n3)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 410

#define P 1000000007

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,f[N][N];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

	f[1][0]=1;f[1][1]=1;

	for (int i=2;i<=n;i++)

		for (int j=0;j<=n;j++)

			for (int x=0;x<=j+1;x++)

			{

				if (j>=x) inc(f[i][j],1ll*(2*j+1)*f[i-1][x]%P*f[i-1][j-x]%P%P);

				if (j>x) inc(f[i][j],1ll*f[i-1][x]*f[i-1][j-x-1]%P);

				inc(f[i][j],1ll*f[i-1][x]*f[i-1][j-x+1]%P*(j+1)%P*j%P);

			}

	cout<<f[n][1];

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　

最新文章

  1. 基于ZooKeeper的Dubbo注册中心
  2. SVN 远程无法联通
  3. LoadRunner ---思考时间设置
  4. Android系统分区理解及分区目录细解
  5. asp.net中调用命令行
  6. Android开发：第五日番外——过时的函数和被横杠的函数
  7. Ubuntu 修改IP地址网关
  8. ios tweak之binary not signed (use ldid -S)问题解决
  9. ExtJS中动态设置TextField的readOnly属性
  10. 关于git的一些理论知识
  11. [bzoj1819] [JSOI]Word Query电子字典
  12. jsp 条件查询、列表分页
  13. win10 安装docker
  14. js 阻止事件执行
  15. Perl的die和warn函数
  16. grep -A -B -C 显示抓取的前后几行参数
  17. liuyan
  18. angularjs也支持script形式的template
  19. js json转字符串
  20. Android-openFileInput openFileOutput

热门文章

  1. Intellij IDEA创建的Web项目配置Tomcat并启动Maven项目
  2. storm自定义分组与Hbase预分区结合节省内存消耗
  3. new、getInstance()、newInstance()、Class.forName()
  4. java高精度学习笔记
  5. threading模块，python下的多线程
  6. C++诡异异常处理
  7. Pseudo Registers
  8. C#设计模式之4：装饰者模式
  9. Linux 下面 PG 的 uuid-ossp 包安装办法
  10. vue的地图插件amap