杂题选讲 DAY1

T1 【FJOI2016】建筑师

题面:

H【FJOI2016】建筑师
时间限制 : - MS 空间限制 : - KB 评测说明 : 1s 256m
问题描述

小 Z 是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 n 个建筑，每个建筑的高度是 1 到 n 之间的一个整数。

小 Z 有很严重的强迫症，他不喜欢有两个建筑的高度相同。另外小 Z 觉得如果从最左边（所有建筑都在右边）看能看到 A个建筑，从最右边（所有建筑都在左边）看能看到 B 个建筑，这样的建筑群有着独特的美感。现在，小 Z 想知道满足上述所有条件的建筑方案有多少种？

如果建筑 i 的左(右)边没有任何建造比它高，则建筑 i 可以从左(右)边看到。两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。

输入格式

第一行一个整数 T，代表 T 组数据。
接下来 T 行，每行三个整数 n,A,B

输出格式

对于每组数据输出一行答案 mod10^9+7。

样例输入 1

2
3 2 2
3 1 2

样例输出 1

2
1

样例输入 2

5
1 1 1
2 1 1
4 3 1
10 2 2
8 6 4

样例输出 2

1
0
3
219168
0

提示

对于 10% 的数据 ： 1≤n≤10
对于 20% 的数据 ： 1≤n≤100
对于 40% 的数据 ： 1≤n≤50000, 1≤T≤5
对于 100%的数据 ：1≤n≤50000, 1≤A,B≤100, 1≤T≤200000

题解:

由于高度为\(N\)的建筑物肯定不会被挡住,将这个建筑作为分水岭,将左右两边分开为\(A+B-1\)个部分;

显然我们需要考虑将这\(N-1\)个人放在\(A+B-2\)个桌子上,这就是第一类斯特林数;

我们考虑可以将剩下的建筑分为\(A-1\)与\(B-1\)两部分,于是这样的方案数可通过组合数求出;

\(code:\)

#include
#include
#include
#include
#include
#include
#include
#include
#define reint register int
#define ll long long
#define rell register ll
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
    if(flag) x=-x;
}

const int mod=1e9+7;
inline ll mul(ll a,ll b){return a*b

T2 【CERC2017】旅游指南

题面:

I【CERC2017】旅游指南
时间限制 : 20000 MS 空间限制 : 565536 KB SPJ 评测说明 : 1s,512m
问题描述

给定一张n个点，m条双向边的无向图。

你要从1号点走到n号点。当你位于x点时，你需要花1元钱，等概率随机地买到与x相邻的一个点的票，只有通过票才能走到其它点。

每当完成一次交易时，你可以选择直接使用那张票，也可以选择扔掉那张票然后再花1元钱随机买另一张票。注意你可以无限次扔票。

请使用最佳的策略，使得期望花的钱数最少。

输入格式

第一行包含两个正整数n,m(1<=n,m<=300000)，表示点数和边数。

接下来m行，每行两个正整数u,v(1<=u,v<=n)，表示一条双向边。

输入数据保证无重边、无自环，且1号点一定可以走到n号点。

输出格式

输出一行一个实数，即最少的期望花费，当绝对或者相对误差不超过10^{-6}时视为正确。

样例输入 1

5 8
1 2
1 3
1 4
2 3
2 4
3 5
5 4
2 5

样例输出 1

4.1111111111

样例输入 2

4 4
1 2
1 3
2 4
3 4

样例输出 2

3.0000000000

题解:

好题啊!妙啊!

我们设定状态F[i]为从i点到终点所花钱数最少的期望,那么显然可以得到:

\(F[p]=\frac{\sum\ min(F[p],F[x_i])}{deg[p]}+1;\)

移项得:

\(deg[p]*F[p]=\sum min(F[p],F[x_i])+deg[p];\)

我们设在取最小值的过程中使用了\(a\)次\(F[x_i]\),那么:

\(deg[p]*F[p]=(deg[p]-a)*F[p]+a*F[x_i]+deg[p];\)

\(F[p]*a=F[x]*a+deg[p];\)

\(F[p]=\frac{a*F[x]+deg[p]}{a};\)

初始状态\(F[N]=0\),因为我们默认最开始所有的取最小处都是选择的\(F[x]\),所以所得期望一定大于等于结果,通过小值去更新,即可使其接近或等于答案,这个贪心的过程我们注意到类似于迪杰斯特拉;

\(code:\)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define reint register int
#define ll long long
#define ld double
#define rell register ll
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
    if(flag) x=-x;
}

struct node{
	int x;
	ld len;
	inline node(int a=0,ld b=0.0)
	{x=a,len=b;}
	inline bool operator<(node a)const
	{return len>a.len;}
};

const int maxn=300002;
int n,m,deg[maxn];
int a[maxn];
vectorG[maxn];
priority_queueq;
ld f[maxn],sum[maxn];
bool book[maxn];
void djs()
{
	f[n]=0.0;q.push(node(n,0.0));
	while(!q.empty())
	{
		int x=q.top().x;q.pop();
		if(book[x]) continue;
		book[x]=1;
//		printf("%d--\n", G[x].size()-1);
		for(reint i=G[x].size()-1;i>=0;i--)
		{
			int p=G[x][i];
			if(book[p]) continue;
			a[p]++;sum[p]+=f[x];
			f[p]=(sum[p]+deg[p])/a[p];
			q.push(node(p,f[p]));
		}
	}
}

int main()
{
	read(n),read(m);
	for(reint i=1;i<=m;i++)
	{
		int x,y;
		read(x),read(y);
		G[x].push_back(y);
		G[y].push_back(x);
		deg[x]++;deg[y]++;
	}
	djs();
	printf("%.10lf",f[1]);
}

T3 【HAOI2017】供给侧改革

题面:

J【HAOI2017】供给侧改革
时间限制 : - MS 空间限制 : - KB 评测说明 : 1s,256m
问题描述

Anihc国提高社会生产力水平.落实好以人民为中心的发展思想。决定进行供给侧结构性改革。

为了提高供给品质.你调查了某个产业近来n个时期的供求关系平衡情况.每个时期的情况都用0或1中的一个数字来表示.于是这就是—个长度为n的01字符串S。为了更好的了解这一些数据.你需要解决一些询问.我们令data(l,r)表示：在字符串S中.起始位置在[l,r]之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。

对于每一个询问L,R.求

ans=∑data(i,R) L≤i

由于你其实根本没有时间调查，所以这些数据都是乱编的，即串S中的每一位都是在0和1之间随机产生的。

输入格式

第一行2个整数n,Q，表示字符串的长度，以及询问个数

接下来一行长度为n的一个01串S

接下来Q行，每行2个整数L,R.一个询问L.R

输出格式

共Q行.每行一个整数.表示对应询问的答案。

样例输入 1

6 3
010110
2 5
1 6
1 2

样例输出 1

4
6
0

样例输入 2

20 20
01010011000001000111
1 3
6 13
5 10
3 6
3 6
6 16
8 18
1 4
11 15
3 13
1 19
7 10
10 13
3 9
4 17
1 18
2 20
1 20
2 19
1 20

样例输出 2

3
22
20
4
4
33
26
5
7
34
59
12
6
10
42
54
56
60
55
60

提示
数据点    n的规模    Q的规模
1    <= 20    <= 20
2    <= 20    <= 20
3    <= 100    <= 100
4    <= 100    <= 100
5    <= 5000    <= 5000
6    <= 5000    <= 5000
7    <= 100000    <= 100000
8    <= 100000    <= 100000
9    <= 100000    <= 100000
10    <= 100000    <= 100000

对于所有的数据保证：n <= 100000,Q<= 100000,1<=L

题解:

未做呢,待补待补;

T4 平衡的队列

题面:

输入格式

第一行，两个空格间隔的整数N和K
接下来N行，每行一个K位二进制整数(已转换成了十进制)，表示第i头奶牛的特征

输出格式

一行，一个整数，表示最大的平衡区间的长度

样例输入

7 3
7
6
7
2
1
4
2

样例输出
提示

样例说明：这个范围是3到6，其中每个特征恰好出现了2次。

题解:

记录每一位上的前缀和,\(Hash\)一下,加上\(map\)看前面有没有一样的;

\(code:\)

#include
#include
#include
#include
#include
#include
#include
#include
#define reint register int
#define mod1 1000000007
#define mod2 998244353
#define ll long long
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
    if(flag) x=-x;
}

const int maxn=1e5+2;
int n,k;
ll hashh[maxn];
int sum[maxn][32];
mapbook;
int main()
{
    read(n),read(k);
    for(reint i=1;i<=n;i++)
    {
        ll x;
        read(x);
        for(int j=0;j>j&1)+sum[i-1][j];
    }
    
//	for(int i=1;i<=n;i++,putchar(10))
//	for(int j=0;j

T5 [JLOI2015 DAY1]有意义的字符串

题面:

L [JLOI2015 DAY1]有意义的字符串
时间限制 : - MS 空间限制 : 165536 KB img评测说明 : 1S
问题描述

img

输入格式

一行三个整数b,d,n。

输出格式

一行一个数表示模7528443412579576937 之后的结果。

样例输入 1

1 5 9

样例输出 1

76

样例输入 2

11 125 6715504

样例输出 2

1499928102740042526

提示

img

题解:

本题面向数据编程=_=;

首先,我们可以发现,原式可以转换为求:

\((\frac{b+\sqrt{d}}{2})^n+(\frac{b-\sqrt{d}}{2})^n-(\frac{b-\sqrt{d}}{2})^n\)

这个式子,我们又观察一下可以发现:

\(X_1=(\frac{b+\sqrt{d}}{2}),X_2=(\frac{b-\sqrt{d}}{2})\)

这是一个二次方程的两个根:

\(X^2+b*X-\frac{b^2-d}{4}=0\)

然后呢,对我们要求的前半部分,是一个整数,后半部分值域为\((-1,0]\),这个由数据范围可得;
我们设:

\(F(n)=X_1^n+X_2^n;\)

那么易得:

\(X_1^n+X_2^n=(X_1+X_2)(X_1^{n-1}+X_2^{n-2})-X_1*X_2^{n-1}-X_2*X_1^{n-1}=(X_1+X_2)(X_1^{n-1}+X_2^{n-2})-(X_1*X_2)(X_1^{n-2}+X_2^{n-2})\)

由韦达定理:

\(X_1+X_2=b,X_1*X_2=\frac{d-b^2}{4};\)

那么我们要求的就变成了:

\(F(n)=F(n-1)*b+F(n-2)*(\frac{d-b^2}{4});\)

这个显然可以用矩阵快速幂优化;

考虑后半部分,我们只要看看它有没有可能做出值为-1的贡献即可(当且仅当\(n\)为奇数,且\(d!=b*b\))

\(code:\)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define reint register int
#define ll long long
#define ld double
#define rell register ll
#define mod 7528443412579576937ul
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
    if(flag) x=-x;
}
inline ll add(ll x,ll y){return x+y>=mod||x+y<0?x+y-mod:x+y;}
inline ll sub(ll x,ll y){return x-y<0?x-y+mod:x-y;}
inline ll mul(ll x,ll y){ll d=(ll)(x*(long double)y/mod+0.5);return sub(x*y,d*mod);}
struct arr{
    ll n,m;
    ll a[21][21];
    ll *operator[](int b){return a[b];}
    inline arr(ll c=0,ll d=0)
    {
        memset(a,0,sizeof(a));
        n=c,m=d;
    }
    arr operator*(arr b) const
    {
        arr c;
        c.n=n;c.m=b.m;
        for(reint i=0;i>=1ul; 
    	}
    	return ans;
	}
};

ll b,d,n;
arr aa,bb;
int main()
{
	read(b),read(d),read(n);
	if(!n) puts("1"),exit(0);
	
	aa=arr(1,2);bb=arr(2,2);
	aa[0][0]=b,aa[0][1]=2;
	bb[0][0]=b,bb[0][1]=1;
	bb[1][0]=(d-b*b)/4,bb[1][1]=0;
	aa*=bb^(n-1);
	printf("%lld",sub(aa[0][0],!(n&1ul)&&(d!=b*b)));
}
杂项题解图论期望矩阵构造

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

面向对象 jvm内存结构 属性 方法 权限修饰符 封装 构造方法 this 包 package

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

0106-105-从中序与后序遍历序列中构造二叉树

HttpURLConnection发送中文乱码问题解决

构造函数

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

1084: [SCOI2005]最大子矩阵

图论---网络流

P7715 「EZEC-10」Shape 题解

标签

一品网 冀ICP备14022925号-6