A-细胞分裂

题目描述

CB不光是ACM大佬，同时也是生物领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。
CB博士手里现在有N种细胞，编号从1~N，一个第i种细胞经过1秒钟可以分裂为Si个同种细胞（Si为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入MM个试管，形成MM份样本，用于实验。CB博士的试管数MM很大，普通的计算机的基本数据类型无法存储这样大的MM值，但万幸的是，MM总可以表示为m1m_1的m2m_2次方，即M=m1m2M=m_1^{m_2} ，其中m1,m2m_1,m_2 均为基本数据类型可以存储的正整数。
注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4个细胞，Hanks博士可以把它们分入2个试管，每试管内2个，然后开始实验。但如果培养皿中有5个细胞，博士就无法将它们均分入2个试管。此时，博士就只能等待一段时间，让细胞们继续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。
为了能让实验尽早开始，CB博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入M个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细胞培养，可以使得实验的开始时间最早。

输入描述

每组输入数据共有三行。
第一行有一个正整数NN，代表细胞种数。
第二行有两个正整数m1，m2m_1，m_2，以一个空格隔开，m1m2{m_1}^{m_2}即表示试管的总数MM。
第三行有N个正整数，第i个数Si表示第i种细胞经过1秒钟可以分裂成同种细胞的个数。
对于所有的数据，有1≤N≤10000，1≤m1≤30000，1≤m2≤10000，1≤Si≤20000000001≤N≤10000，1≤m_1≤30000，1≤m_2≤10000，1≤S_i≤2000000000。

输出描述

每组输出共一行，为一个整数，表示从开始培养细胞到实验能够开始所经过的最少时间（单位为秒）。
如果无论CB博士选择哪种细胞都不能满足要求，则输出整数-1。

示例1

输入
2
24 1
30 12
输出
2
说明
下面是对样例数据的解释：
第1种细胞最早在3秒后才能均分入24个试管，而第2种最早在2秒后就可以均分（每试管14424=6\frac{144}{24}=6 个）。故实验最早可以在2秒后开始。

思路

此题需要一些数论知识。
假设某一种细胞的个数为ss，存在正整数ctct使得$s^{ct}\bmod {{m_1}^{m_2}}=0$。我们将ss和m1m_1分解质因数，就如样例中的第二种情况：(2×2×3)2 mod (2×2×2×3)1=0{(2\times 2\times 3)}^2\bmod {(2\times 2 \times 2 \times 3)}^1=0。m1m_1和ss的质因子种类必须完全相同，否则不可能均分；且scts^ct每一种质因子的个数必须不小于m1m2{m_1}^{m_2}中对应质因子的个数；满足上述条件的ctct使得m1m2∣sct{m_1}^{m_2}|s^{ct}。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstring>
#include<algorithm>
#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
const int N=300006;
int prime_factor[N],num[N],s[N>>1];
int cnt;
int n,m1,m2;
int ans;
void init()
{
    memset(num,0,sizeof(num));
    cnt=0;
    ans=inf;
}
void divide(int x)//分解质因数
{
    int i;
    for(i=2;i*i<=x;i++)
    {
        if(!(x%i))
        {
            prime_factor[++cnt]=i;
            while(!(x%i))
            {
                x=x/i;
                num[i]++;
            }
            num[i]*=m2;
        }
    }
    if(x!=1) 
    {
        prime_factor[++cnt]=x;
        num[x]=m2;
    }
}
int solve()
{
    init();
    cin>>m1>>m2;
    divide(m1);
    int i;
    for(i=1;i<=n;i++) cin>>s[i];
    int step=1;
    next:for(i=step;i<=n;i++)//防止goto死循环，整活step。 
    {
        int j;
        int res=0;
        for(j=1;j<=cnt;j++)
        {
            if(s[i]%prime_factor[j]) 
            {
                step=++i;
                goto next;
            }
            else
            {
                int temp=s[i];
                int ct=0;
                while(!(temp%prime_factor[j]))//统计s[i]质因子prime_factor[j]的个数
                {
                    temp=temp/prime_factor[j];
                    ct++;
                }
                /*
                    对质因子prime_factor[j]取模，至少需要的天数为
                    num[prime_factor[j]]/ct+(num[prime_factor[j]]%ct!=0)
                */
                res=max(num[prime_factor[j]]/ct+(num[prime_factor[j]]%ct!=0),res);
            }
        }
        ans=min(res,ans);//更新答案
    }   
    if(ans==inf) ans=-1;//没有更新过
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n) cout<<sol？ve()<<endl;
    return 0;
}

B-A题

题目描述

A要去B的城市游玩，A在城市1居住，B在城市X居住，现在有一些神奇的传送门和一些奇神的传送门。
已知，神奇的传送门可以从编号小的城市传送往编号大的城市，奇神的传送门可以从编号大的城市传送往编号小的城市，但是在某些城市没有某种传送门。
那么已知数组aa，其中aia_i代表着城市i是否有神奇的传送门(ai=1a_i=1代表有，ai=0a_i=0代表没有)，以及数组bb，其中bib_i代表着城市i是否有奇神的传送门。
神奇的海螺想知道A能不能去B的城市玩。

输入描述

多组测试样例。
每组测试样例的第一行有两个数字N和X，代表了城市的数量和B的居住地址（2<=N<=1000,2<=X<=1000）（2 <= N <= 1000 ,2 <= X <= 1000）
第二行给出数组aa，第三行给出数组bb。

输出描述

可行，则输出YES。
否则，输出NO。

示例1

输入
5 3
1 1 1 1 1
1 1 1 1 1
5 4
1 0 0 0 1
0 1 1 1 1
5 2
0 1 1 1 1
1 1 1 1 1
输出
YES
YES
NO
说明
第二组样例路线:1->5->4

思路1

由题意，X比1大，所以a[1]必须为1，否则不能到达。如果X有神奇传送门，那么就能从1直接到达，如果没有，就要找一个比X还大并且两个门都有的城市作为中转站。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<string>
#include<iostream>
using namespace std;
string solve(int n,int x)
{
    const int N=1002;
    bool a[N],b[N];
    int i;
    for(i=1;i<=n;i++) cin>>a[i];
    for(i=1;i<=n;i++) cin>>b[i];
    string ans;
    if(!a[1]) return "NO";//不能到编号大的城市
    else
    {
        if(a[x]) return "YES";//有神奇传送门，直接过去
        else if(!b[x]) return "NO";//根本没有通道
        else //有奇神传送门，需要中转。
        {
            for(i=x+1;i<=n;i++)
            {
                if(a[i]&&b[i]) 
                {
                    return "YES";
                }
            }
            return "NO";
        }
    }
}
int main()
{
    int n,x;
    while(cin>>n>>x) cout<<solve(n,x)<<endl;
    return 0;
}

思路2

建图，DFS一遍看是否连通。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1002;
bool vis[N],can[N];
vector<int>mp[N];
bool ok;
int x,n;
int a[N],b[N];
void init()
{
	vector<int>e[N];
	swap(e,mp);
	ok=false;
	memset(vis,0,sizeof(vis));
	memset(can,true,sizeof(can));
}
void dfs(int now,int x)
{
	if(now==x)
	{
		ok=true;
		return;
	}
	int i;
	for(i=0;i<mp[now].size();i++)
	{
        if(ok) return;
		if(!vis[mp[now][i]]&&can[mp[now][i]])
		{
			vis[mp[now][i]]=true;
			dfs(mp[now][i],x);
			vis[mp[now][i]]=false;
		}
	}
    can[now]=false;//用来剪枝，如果循环结束ok为false，说明now不能到达终点。
}
void solve()
{
	int i,j;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=n;i++) cin>>b[i];
	for(i=1;i<=n;i++)
	{
		if(a[i])
		{
			for(j=i+1;j<=n;j++)
			{
				if(a[j]) mp[i].push_back(j);
			}
		}
		if(b[i])
		{
			for(j=1;j<=i-1;j++)
			{
				if(b[j]) mp[i].push_back(j);
			}
		}
	}
	dfs(1,x);
	if(ok) puts("YES");
	else puts("NO");
}
int main()
{
	while(cin>>n>>x)
	{
		init();
		solve();
	}
	return 0;
}

思路3

建图，BFS一遍看是否连通。复杂度较DFS更低。

代码3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1002;
bool vis[N];
vector<int>mp[N];
bool ok;
int x,n;
int a[N],b[N];
void init()
{
	vector<int>e[N];
	swap(e,mp);
	ok=false;
	memset(vis,0,sizeof(vis));
}
void bfs(int x)
{
	queue<int>q;
	q.push(1);
	int i;
	while(!q.empty())
	{
		int now=q.front();
		for(i=0;i<mp[now].size();i++)//所有相连节点入队
		{
			if(vis[mp[now][i]]) continue;
			else
			{
				if(mp[now][i]==x)
				{
					ok=1;
					return;
				} 
				else
				{
					q.push(mp[now][i]);
					vis[mp[now][i]]=1;
				}			
			}
		}
		q.pop();//根节点出队
	}
}
void solve()
{
	int i,j;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=n;i++) cin>>b[i];
	for(i=1;i<=n;i++)
	{
		if(a[i])
		{
			for(j=i+1;j<=n;j++)
			{
				if(a[j]) mp[i].push_back(j);
			}
		}
		if(b[i])
		{
			for(j=1;j<=i-1;j++)
			{
				if(b[j]) mp[i].push_back(j);
			}
		}
	}
	bfs(x);
	if(ok) puts("YES");
	else puts("NO");
}
int main()
{
	while(cin>>n>>x)
	{
		init();
		solve();
	}
	return 0;
}

C-均分糖果

题目描述

有NN堆糖果，编号分别为1，2，...，N1，2，...，N。每堆上有若干个，但糖果总数必为NN的倍数。可以在任一堆上取若干个糖果，然后移动。
移动规则为：在编号为11的堆上取的糖果，只能移到编号为22的堆上；在编号为NN的堆上取的糖果，只能移到编号为N−1N-1的堆上；其他堆上取的糖果，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上糖果数都一样多。
例如N=4，4堆糖果数分别为：
①　9　②　8　③　17　④　6
移动3次可达到目的：
从③取4个糖放到④（9 8 13 10）->从③取3个糖放到②（9 11 10 10）->从②取1个糖放到①（10 10 10 10）。

输入描述

每个测试文件包含多组测试数据，每组输入的第一行输入一个整数N（1<=N<=100）N（1<=N<=100），表示有NN堆糖果。
接下来一行输入NN个整数A1A2...AnA_1 A_2...A_n，表示每堆糖果初始数，1<=Ai<=100001<=A_i<=10000。

输出描述

对于每组输入数据，输出所有堆均达到相等时的最少移动次数。

示例1

输入
4
9 8 17 6
输出
3

思路

相邻两堆AiA_i和Ai+1A_{i+1}成对调整，若不足平均，则补；若高于平均，则扣。
这样能尽可能避免拆数量为平均数的堆，是最优解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;
int solve(int n)
{
    int i;
    int a[102];
    int sum=0,ans=0;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    int average=sum/n;
    for(i=1;i<n;i++)
    {
        a[i+1]=a[i+1]+a[i]-average;//始终是这个式子
        if(a[i]!=average) ans++;          
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    while(cin>>n) cout<<solve(n)<<endl;
    return 0;
}

D-B题

题目描述

有一个连通图 包含 nn 个点 nn 条无向边 其中每个点都与其他的两个点直接相连 (即这是一个环)
现在这个环的边变成了有向边 变成了有向边后得到的有向图不一定是强连通的
(强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径的图)
所以现在给出 n 条有向边和把某条有向边转换方向后的代价, 问要使输入的有向图变成一个强连通图
例如输入
3
1 3 1
1 2 1
3 2 1
表示有一条有向边 1 -> 3 如果把这条边变成 3 -> 1 的代价是 1
表示有一条有向边 1 -> 2 如果把这条边变成 2 -> 1 的代价是 1
表示有一条有向边 3 -> 2 如果把这条边变成 2 -> 3 的代价是 1
对于输入的这个有向图是不存在 2 -> 3 的路径的 所以可以把 有向边 1 -> 2 变为 2 -> 1 这样图中任意两点均相互可达

输入描述

多组测试数据。
第一行给出数字nn，代表顶点数量$ (3 ≤ n ≤ 100）。接下来。 接下来n行给出路径。每行给出三个数字行给出路径。 每行给出三个数字a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ c_i ≤ 100) —代表— 代表a_i指向指向b_i。代价是。代价是c_i$。

输出描述

输出最小代价。

示例1

输入
3
1 3 1
1 2 1
3 2 1
3
1 3 1
1 2 5
3 2 1
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42
输出
1
2
39

思路

一个有向环要成为强连通图就需要从任意一点pp出发，能绕环一圈走回原点。
我们将节点11设为出发点，从该节点开始搜索，若找到与节点nownow连接且没有走过的节点，试情况是否要改变路径的方向。当走了n−1n-1步时，我们就需要走到原点，然后更新代价的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n,mp[N][N];
bool vis[N];
int ans;
void dfs(int now,int step,int w)
{
	vis[now]=1;
	if(step==n-1)
	{
		if(mp[now][1]) ans=min(ans,w);
		else if(mp[1][now]) ans=min(ans,w+mp[1][now]);
	}
	else
	{
		int i;
		for(i=1;i<=n;i++)
		{
            	      if(mp[now][i]&&!vis[i]) 
                      {
                          dfs(i,step+1,w);
                          vis[i]=0;
                      }
            	      else if(mp[i][now]&&!vis[i]) 
                      {
                          dfs(i,step+1,w+mp[i][now]);
                          vis[i]=0;
                      }
		}
	}
}
void init()
{
	memset(mp,0,sizeof(mp));
	memset(vis,0,sizeof(vis));
	ans=0x3f3f3f3f;
}
void solve()
{
	init();
	int i;
	for(i=1;i<=n;i++)
	{
            int u,v,w;
            cin>>u>>v>>w;
            mp[u][v]=w;
	}
	dfs(1,0,0);
	cout<<ans<<endl;
}
int main()
{
	while(cin>>n) solve();
	return 0;
}

E-很简单的题。。。。。。

题目描述

统计某个给定范围[L,R][L, R] 的所有整数中，数字22出现的次数。比如给定范围[2,22][2, 22] ，数字22在数22中出现了11次，在数1212中出现11次，在数2020中出现11次，在数2121中出现11次，在数2222中出现22次，所以数字22在该范围内一共出现了66次。

输入描述

每组输入数据共11行，为两个正整数LL和RR，之间用一个空格隔开。（1≤L≤R≤10000）（1≤L≤R≤10000）

输出描述

每组输出数据共1行，表示数字2出现的次数。

示例1

输入
2 100
输出
20

思路

给一个数pp，知道pp含有几个22，非常容易，只需要对1010取模，拿出最低位的数，再除以1010抛弃最后一位的数，如此循环计数即可。
我们只要统计ii个数2出现的次数，然后做一次前缀和操作，就能在O(1)O(1)内查询[L,R][L,R]区间2出现的次数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;
const int N=10001;
int cnt[N];
void init()
{
    int i;
    for(i=1;i<N;i++)
    {
        int p=i;
        while(p)
        {
            if(p%10==2) cnt[i]++;
            p=p/10;
        }
        cnt[i]=cnt[i]+cnt[i-1];
    }
}
void solve(int l,int r)
{
    init();
    cout<<cnt[r]-cnt[l-1];
}
int main()
{
    int l,r;
    while(cin>>l>>r) solve(l,r);
    return 0;
}

F-最大公约数和最小公倍数问题

题目描述

输入2个正整数x0，y0（2<=x0<100000，2<=y0<=1000000）x_0，y_0（2<=x_0<100000，2<=y_0<=1000000），求出满足下列条件的P，QP，Q的个数。
条件：
①P，QP，Q是正整数；
②要求P，QP，Q以x0x_0为最大公约数，以y0y_0为最小公倍数。
试求：
满足条件的所有可能的两个正整数的个数。

输入描述

每个测试文件包含不超过5组测试数据，每组两个正整数x0x_0和y0（2<=x0<100000，2<=y0<=1000000）y_0（2<=x_0<100000，2<=y_0<=1000000）。

输出描述

对于每组输入数据，输出满足条件的所有可能的两个正整数的个数。
下面是对样例数据的说明：
输入3 60
此时的P Q分别为:
3 60
15 12
12 15
60 3
所以，满足条件的所有可能的两个正整数的个数共4种。

示例1

3 60
4

思路

由于gcd(p,q)=x0,lcm(p,q)=y0gcd(p,q)=x_0,lcm(p,q)=y_0，所以x0y0=pqx_0y_0=pq。我们的任务就是在O(x0y0)O(\sqrt {x_0y_0})内查找所有x0y0x_0y_0的因子ii，并检验gcd(i,x0y0i)gcd(i,\frac{x_0y_0}{i})是否为x0x_0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<algorithm>
using namespace std;
void solve(long long x,long long y)
{
    long long k=x*y;
    long long i;
    long long ans=0;
    for(i=1;i*i<k;i++)
    {
        if(k%i==0)
        {
            long long g=__gcd(i,k/i);
            if(g==x) ans++;
        }
    }
    ans=ans*2;
    if(i*i==k&&x==i) ans++;//完全平方数检验
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long x,y;
    while(cin>>x>>y) solve(x,y);
    return 0;
}

G-毕业生的纪念礼物

题目描述

现在有n个纪念品，每个纪念品都有一个种类r[i]，现在要求对每个毕业生分发三个种类不同的纪念品，现在需要你来计算下共可以发给多少个毕业生？

输入描述

第一行一个整数nn，1≤n≤1000001≤n≤100000，代表纪念品的个数；
第二行包含nn个整数，分别是r[1],r[2],r[3]......r[n]，1≤r[i]≤109r[1], r[2], r[3]......r[n]，1≤r[i]≤10^9，表示每个纪念品所属的种类。

输出描述

输出一个整数，代表最多能够分发给的毕业生人数。

示例1

输入
14
1 1 2 2 3 3 4 4 4 4 5 5 5 5
输出
4

示例2

输入
7
1 2 3 4 5 6 7
输出
2

思路

题目就是说有nn种物品，每一种有r[i]r[i]个，要求每次挑选三种，每种拿一个，问最多能挑选几次。
显然，我们每一次都要选剩余物品数量最多的那三种，这样可以挑选的次数是最多的。每挑选一次就要进行一次排序，因此考虑优先队列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<map>
#include<queue>
#include<iostream>
using namespace std;
void solve()
{
    int r[100002];
    priority_queue<int>now;//STL默认大顶堆
    int i;
    int n;
    cin>>n;
    map<int,int>cnt;
    for(i=1;i<=n;i++)
    {
        cin>>r[i];
        cnt[r[i]]++;//记录每一种物品的个数
    }
    map<int,int>::iterator it;
    //遍历map，把每一种的个数push进队列。
    for(it=cnt.begin();it!=cnt.end();it++) now.push(it->second);
    int ans=0;
    int a,b,c;
    while(now.size()>=3)
    {
    	//选取个数最多的三种
        a=now.top();
        now.pop();
        b=now.top();
        now.pop();
        c=now.top();
        now.pop();
        a--;
        b--;
        c--;
        if(a>0) now.push(a);
        if(b>0) now.push(b);
        if(c>0) now.push(c);
        ans++;
    }
    cout<<ans;
}
int main()
{
    solve();
    return 0;
}

H-毕业生的序列游戏

题目描述

对于三个给定的正整数k,pa,pbk, p_a, p_b, 现在有一个序列构造算法： 在初始条件下，有一个空序列，之后每次你会在该序列的末尾添加一个字母’a’或’b’，添加’a’的概率是papa+pb\frac{p_a}{p_a+p_b}，添加’b’的概率是pbpa+pb\frac{p_b}{p_a+p_b}。当在该序列中有至少k个子序列为"ab"的时候，该构造算法结束。
现在，你需要求出该算法所构造出来的序列中"ab"子序列的期望个数为多少。显然，该结果可以用PQ\frac {P}{Q}来表示，其中PP和QQ互质，并且Q≠0Q≠0，PP和QQ模数为109+710^9+7。你需要打印出PQ mod (109+7)\frac {P}{Q}\bmod (10^9+7)。
注意，子序列是可以不连续的。

输入描述

第一行包含三个整数k，pa，pb（1≤k≤1000，1≤pa，pb≤1000000）k，p_a，p_b（1≤k≤1000，1≤p_a，p_b≤1000000）。

输出描述

输出一个整数。

示例1

输入
1 1 1
输出
2

思路

设dp[i][j]dp[i][j]为当前构造的序列有ii个’a’，jj个子序列"ab"时，出现子序列"ab"的次数的期望。
考虑比当前序列多一个字符的串，若多出的字符为’a’（即dp[i+1][j]dp[i+1][j]），则需要papa+pb\frac {p_a}{p_a+p_b}的概率到达dp[i+1][j]dp[i+1][j]；若多出的字符为’b’（即dp[i][j+i]dp[i][j+i]），则需要pbpa+pb\frac {p_b}{p_a+p_b}的概率到达dp[i][j+i]dp[i][j+i]。
已有字符数量少的字符串理应拥有更大的可能性。
状态转移方程：

dp[i][j]=dp[i+1][j]×papa+pb+dp[i][j+i]×pbpa+pbdp[i][j]=dp[i+1][j]\times \frac {p_a}{p_a+p_b}+dp[i][j+i]\times \frac {p_b}{p_a+p_b}

只需要通过记忆化搜索，递归至最底层，然后自底向上递推即可。
下面来考虑两种极限情况：
①出现无穷多’b’，即一开始的序列是"bbbbbbbbbbb…"这样的，就是不出现’a’，这样的序列是废掉的，显然在第一个’a’之前的所有’b’都没有任何用处，为了结束添加字母，则必定会出现a，所以目标状态一定会出现前缀有一个’a’，没有"ab"的情况，如果求dp[0][0]dp[0][0]必定超时，因此我们转而求dp[1][0]dp[1][0]。
②出现无穷多’a’，即一开始的序列是"ababaaaaaaaaaaaa…b"这样的，就是不出现’b’，这样的序列，当出现一个’b’，就能实现大于等于kk个"ab"子序列的构造。
事实上，只要达到状态dp[i][j]dp[i][j]且i+j⩾ki + j \geqslant k时，增加一个’b’，就能完成大于等于kk个"ab"子序列的构造。那么即使后面一坨’a’也无妨。下面算的就是后面一坨‘a’的情况。
列一个表，表示添加$\xi $个’a’，再添加’b’实现条件的概率。

ξ=0\xi=0 ξ=1\xi =1 ξ=2\xi =2 ξ=...\xi=...
P(ξ)P(\xi) $\frac{{{p_b}}}{{{p_a} + {p_b}}}$ $\frac{{{p_a}}}{{{p_a} + {p_b}}} \frac{{{p_b}}}{{{p_a} + {p_b}}}$ ${\left( {\frac{{{p_a}}}{{{p_a} + {p_b}}}} \right)^2}\frac{{{p_b}}}{{{p_a} + {p_b}}}$ P(ξ)=...P(\xi)=...
"ab"子序列个数 i+ji+j i+j+1i+j+1 i+j+2i+j+2 i+j+...i+j+...

由期望定义，得：

$$ dp[i][j] = \frac{{{p_b}}}{{{p_a} + {p_b}}}{\sum\limits_{\xi = 0}^\infty {(i + j + \xi) (\frac{{{p_a}}}{{{p_a} + {p_b}}})} ^{\xi}} $$

上述无穷级数可用错位相减法求得极限
等式两边同时乘papa+pb\frac {p_a}{p_a+p_b}得：

$$ \frac{{{p_a}}}{{{p_a} + {p_b}}}dp[i][j] = \frac{{{p_b}}}{{{p_a} + {p_b}}}\sum\limits_{\xi = 0}^\infty {(i + j + \xi )} {\left( {\frac{{{p_a}}}{{{p_a} + {p_b}}}} \right)^{\xi + 1}} $$

错位相减得：

$$ \left( {1 - \frac{{{p_a}}}{{{p_a} + {p_b}}}} \right)dp[i][j] = (i + j)\frac{{{p_b}}}{{{p_a} + {p_b}}} + \frac{{{p_b}}}{{{p_a} + {p_b}}}\sum\limits_{\xi = 1}^\infty {{{\left( {\frac{{{p_a}}}{{{p_a} + {p_b}}}} \right)}^\xi }} $$

解得：

$$ dp[i][j] = i + j + \frac{{{p_a}}}{{{p_b}}}(i + j \geqslant k) $$

接下来就是分情况进行记忆化搜索，得到dp[1][0]dp[1][0]
需要注意的是所有概率运算都在模109+710^9+7的意义下进行，即计算逆元。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const int N=1003;
ll k,pa,pb;
ll dp[N][N];
ll quick_pow(ll a,ll b)//快速幂
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
ll inv(ll x)//求逆元
{
	return quick_pow(x,mod-2);
}
ll dfs(ll x,ll y)
{
	if(dp[x][y]) return dp[x][y];
	if(x+y>=k)
	{
		dp[x][y]=(x+y+pa*inv(pb)%mod)%mod;
		return dp[x][y];
	}
	dp[x][y]=(pa*inv(pa+pb)%mod*dfs(x+1,y)%mod+pb*inv(pa+pb)%mod*dfs(x,y+x)%mod)%mod;
	return dp[x][y];
}
void solve()
{
	ios::sync_with_stdio(false);
	cin>>k>>pa>>pb;
	cout<<dfs(1,0);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	solve();
	return 0;
}

I-你的粪坑v1

题目描述

剪刀石头布，谁输谁吃屎。

输入描述

第一行一个整数T，代表测试数据个数。
每个测试数据包括两行数据。
第一行数据为两个字符串A，X1，代表A同学的出拳为X1。
第二行数据为两个字符串B，X2，代表B同学的出拳为X2。
其中A,B是字符串，长度为[0,10]，代表同学名字。
其中X1,X2是字符串，内容为"jiandao",“shitou”,“bu"三者之一。
输出描述:
对每个测试数据，
A同学赢输出"B chishi.”，其中B代表B同学名字，
B同学赢输出"A chishi.“，其中A代表A同学名字，
如果平局，输出"yi qi chi shi.”。
示例1
输入
复制
3
jiang jiandao
wang shitou
jiang bu
wang jiandao
jiang shitou
wang shitou
输出
复制
jiang chishi.
jiang chishi.
yi qi chi shi.
说明
注意空格

思路

模拟一遍剪刀石头布的规则，注意输出末尾的句号和句中的空格。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<string>
#include<iostream>
using namespace std;
void solve()
{
    string a,x1;
    cin>>a>>x1;
    string b,x2;
    cin>>b>>x2;
    if(x1=="jiandao")
    {
        if(x2=="shitou") cout<<a<<' '<<"chishi."<<endl;
        else if(x2=="bu") cout<<b<<' '<<"chishi."<<endl;
        else cout<<"yi qi chi shi."<<endl;
    }
    else if(x1=="shitou")
    {
        if(x2=="jiandao") cout<<b<<' '<<"chishi."<<endl;
        else if(x2=="bu") cout<<a<<' '<<"chishi."<<endl;
        else cout<<"yi qi chi shi."<<endl;
    }
    else if(x1=="bu")
    {
        if(x2=="jiandao") cout<<a<<' '<<"chishi."<<endl;
        else if(x2=="shitou") cout<<b<<' '<<"chishi."<<endl;
        else cout<<"yi qi chi shi."<<endl;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

J-你的粪坑v2

题目描述

一听说这是一场正经比赛，都没人用昵称了？好吧，那就用“你”吧，请自行代入聚聚名字！
这是一道充满味道的题目。
今天举办程序设计比赛，2点30分开始，然而你睡到了2点25分，紧张的你将头发梳成大人模样，敷上一层最贵的面膜，穿着滑板鞋，以飞一般的速度奔向计算机学院准备参加程序设计竞赛！冠军是你的！
然而路上稍不留神，你不小心掉进了一个大粪坑，大粪坑是一个N×NN \times N的方格矩阵，每个方格存在着XX坨粪，一开始你处在A11A_{11}的粪坑位，你可以选择向下移动或者向右移动，目标是逃离大粪坑到达ANNA_{NN}。
此外！！敲重点！！每经过一个粪坑，你会触及粪量XX（粗俗的说法叫做吃shi），而且每更改一次方向，传说中的粪皇会向你丢粪！！
粪皇是个学过二进制的优雅美男子，所以他丢粪也是相当的儒雅随和。第一次他会向你丢11坨，第二次他会向你丢22坨哦，第三次他会向你丢44坨哦！第四次他会向你丢88坨哦！第五次他会向你丢1616坨哦！…，第NN次他会向你丢2N−12^{N-1}坨哦！嘤嘤嘤～～～～～～～
机智的你绝不会向粪皇低头！所以你拿起手中的笔记本，打开Codeblocks，写下#include<bits/stdc++.h>，开始计算如何掉最少的发，吃最少的shi，冲出粪坑，到达计院，拿下冠军！
输入描述:
第一行是一个整数T，代表测试数据个数。
对每个测试数据第一行是一个整数NN，代表粪坑大小为N×N(1≤N≤100)N\times N (1 ≤ N ≤ 100) 。
接下来NN行每行NN个整数，代表粪坑矩阵A中每个粪坑位的粪量(1≤Aij≤100)(1 ≤ A_{ij} ≤ 100)。

输出描述

最少吃shi量

示例1

输入
1
3
1 4 6
1 1 3
6 1 1
输出
10

思路

你当前的状态有五维：

  • 横坐标
  • 纵坐标
  • 转弯的次数
  • 行走的方向
  • 吃屎量

记dp[i][j][k][v]=shidp[i][j][k][v]=shi为处于(i,j)(i,j)位置，已经转弯了kk次，正在朝vv方向走，已经吃了shi坨屎的状态（v=0v=0代表向右，v=1v=1代表向左）。
dp[i][j][k][0]dp[i][j][k][0]的来源有两种：

  • 位于(i,j−1)(i,j-1)处向右走一步到达，与当前方向一致，那么前一个状态是dp[i][j−1][k][0]dp[i][j-1][k][0]
  • 位于(i−1,j)(i-1,j)处向下走一步到达，与当前方向不一致，那么前一个状态是dp[i−1][j][k−1][1]dp[i-1][j][k-1][1]

dp[i][j][k][1]dp[i][j][k][1]的来源有两种：

  • 位于(i−1,j)(i-1,j)处向下走一步到达，与当前方向一致，那么前一个状态是dp[i−1][j][k][1]dp[i-1][j][k][1]
  • 位于(i,j−1)(i,j-1)处向下走一步到达，与当前方向不一致，那么前一个状态是dp[i][j−1][k−1][0]dp[i][j-1][k-1][0]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
void solve()
{
    const int N=102;
    int dp[N][N][12][2];
    memset(dp,0x3f,sizeof(dp));
    int n;
    int a[N][N];
    int i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    dp[1][1][0][0]=dp[1][1][0][1]=a[1][1];
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            for(k=0;k<=min(n,10);k++)
            {
                dp[i][j][k][0]=min(dp[i][j][k][0],dp[i][j-1][k][0]+a[i][j]);
                if(k) 
                dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][1]+a[i][j]+(1<<(k-1)));
                //加上转弯的贡献，第k次转弯吃2^(k-1)坨屎。
                dp[i][j][k][1]=min(dp[i][j][k][1],dp[i-1][j][k][1]+a[i][j]);
                if(k) 
                dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k-1][0]+a[i][j]+(1<<(k-1)));
                //加上转弯的贡献，第k次转弯吃2^(k-1)坨屎。
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(k=0;k<=min(n,10);k++) ans=min({ans,dp[n][n][k][1],dp[n][n][k][0]});
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
}

K-你的Alice

题目描述

今天你Bob和你的Alice进行一场比赛。
有N根棒，你和你的Alice轮流取棒，规定你们每人一次取K个，当不够K个的时候，你们把余下的扔掉并停止游戏。
你比较疼你的Alice，所以Alice先取，问最终Alice能否取得更多？

输入描述

单组测试数据。
包括2个整数N和K，代表有N根棒，以及Alice和Bob每次取K个棒。
1<=N<=1000000000001<=N<=100000000000
1<=k<=1001<=k<=100

输出描述

如果Alice最终拥有更多的棒，输出YES，否则输出NO。（全大写）

示例1

输入
10 4
输出
NO

思路

两人交替拿棒子，一组记为2k2k。如果一直交替着拿，把棒子拿光，那就必定平局了。然而这样交替着拿最多进行n2k\frac{n}{2k}次，然后会剩下left=n mod 2k(0<left<2k)left=n\bmod 2k(0<left<2k)。如果剩下的棒子还有kk个，那么Alice拿了就赢了，否则就是个平局。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
void solve()
{
    long long n,k;
    cin>>n>>k;
    if(n%(2*k)>=k) cout<<"YES";
    else cout<<"NO";
}
int main()
{
    solve();
    return 0;
}