自适应树游走协议
题目描述：
在计算机网络中，当多个站点试图通过同一个信道同时进行传输时，传输的数据会出现乱码，这称为冲突。自适应树游走协议（Adaptive Tree Walk Protocol**）是一种避免冲突的方法。它将所有使用同一个信道的站点使用一棵完全二叉树组织起来，每个叶子**代表一个站点。
当有站点想要使用信道时，使用深度优先遍历的方法处理冲突：在第一个时隙检查树根，若其所有后代结点中只有唯一的结点请求信道，则直接将信道分配给它；否则依次递归检查左子树、右子树，直到不存在冲突为止。
图中展示了A-H八个共享信道的站点被组织的方式。若某一时刻C、D、H三个站点同时请求信道，则该协议处理冲突如下：
- 第一个时隙检查0号结点，它有三个后代C、D、H均发起了请求，存在冲突。
- 第二个时隙检查0号结点的左儿子，即1号结点。它有两个后代C、D均发起了请求，存在冲突。
- 第三个时隙检查1号结点的左儿子，即3号结点。它没有后代发起请求，不需要继续向下递归检查。
- 第四个时隙检查1号结点的右儿子，即4号结点。它有两个后代C、D发起了请求，存在冲突。
- 第五个时隙检查4号结点的左儿子，即C。它是发起了请求的叶子结点，因此该时隙将信道分配给C。
- 第六个时隙检查4号结点的右儿子，即D。它是发起了请求的叶子结点，因此该时隙将信道分配给D。此时，对1号结点的递归检查已经完成。
- 第七个时隙检查0号结点的右儿子，即2号结点。它只有一个后代H发起请求，因此该时隙将信道分配给H，不需要继续向下递归检查。
处理所有请求共耗费了七个时隙。
作为一名刚刚开始学习计算机的萌新，Miaoyao为自己掌握了这个协议而非常得意。于是，他想要来考考你：给出站点个数n以及一些发起请求的站点编号，他想知道该协议需要几个时隙处理完所有请求。
当然，由于Miaoyao非常菜，他不希望把问题变得太过复杂。因此，他保证n是2的整数幂，即使用二叉树组织起来时，所得到的将会是一棵满二叉树：所有叶子均在同一层。同时，尽管针对这个协议有很多行之有效的优化，但是Miaoyao并没有掌握，他只会按照上面所述的流程逐个检查。
思路1：
用前缀和+差分去实现区间值的查询，然后便于去dfs，有点线段树的感觉，写起来也很简短
#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
//不开longlong见祖宗！
int n, k, x;
int tr[MAX];
int sum[MAX];
int dfs(int l, int r){
if(sum[r] - sum[l - 1] <= 1)return 1;
return 1 + dfs(l, (l + r) / 2) + dfs((l + r) / 2 + 1, r);
}
int main(){
cin>>n>>k;
for(int i = 1; i <= k; ++i){
cin>>x;
++tr[x];
}
for(int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + tr[i];
cout<<dfs(1, n)<<endl;
return 0;
}
思路2:
也就是我在比赛的时候用的方法
先对0到n-2的点做一次预处理，目的是求每个点的子孙中有几个需要分配信道的点，用数字记录下来，然后再去dfs
#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
//不开longlong见祖宗！
int n, k, x;
int tr[MAX];
bool judge(int x){//判断是否出界
if(x >= n * 2 - 1 || x < 0)return false;
else return true;
}
int cnt;
void check(int x){//判断一个节点有几个需要分配信道的子节点
if(!judge(x))return;
if(tr[x] == 1){
++cnt;
return;
}
check(x * 2 + 1);
check(x * 2 + 2);
}
void yuchuli(){
for(int i = 0; i < n - 1; ++i){
cnt = 0;
check(i);
tr[i] = cnt;
}
}
int ans;
void dfs(int x){
if(!judge(x))return;
++ans;
if(tr[x] <= 1)return;
dfs(x * 2 + 1);
dfs(x * 2 + 2);
}
int main(){
cin>>n>>k;
for(int i = 1; i <= k; ++i){
cin>>x;
tr[x + n - 2] = 1;
}
yuchuli();
dfs(0);
cout<<ans<<endl;
return 0;
}
困难的数学题
题目描述：
Miaoyao好不容易从Dzerzhinski的打击中缓过气来。他潜心学习数学，终于小有所成，于是他给你出了一道自认为非常困难的数学题：
给定正整数n，将其分解为若干个不小于k的正整数之和，有多少种方案？（顺序不同的划分也视为不同的方案)
由于答案可能很大，你只需要输出它对109+710^9+7109+7取模的结果即可。
思路：
dp的那个思路我至今无法理解:
f[i] => 组成正整数i的方案数
f[i]对f[i + 1]、f[i + 2] …… 都可以产生贡献，但是为什么递推式子是f[i] = f[i - 1] + f[i - k]？？
所以这里我给出另一种关于组合数的解法
主要利用的是挡板法
对于n，我们就当成n个1，然后分成m组(1<=m<=n/k)
正常的挡板法分成的m块数量要大于等于1
现在是大于等于k，这个时候我们要把k变成1，也就是让每一块都减去k-1，一共m块，就是让n-m * (k-1)，然后再插入m-1个挡板就行
公式为：
这个题还需要进行组合数取模，套个板子即可
#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 1000000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
ll n, k, m, q;
ll ans;
const ll Mod=1e9 + 7;
ll fac[1000100];//存阶乘
ll inv[1000100];//存逆元
ll quick(ll a,int b)//快速幂算法
{
ll ans=1;
while(b)
{
if(b&1)ans=(ans*a)%Mod;
a=a*a%Mod;
b>>=1;
}
return ans;
}
void getfac()
{
fac[0]=inv[0]=1;
for(int i=1;i<=1000000;i++)
{
fac[i]=fac[i-1]*i%Mod;
inv[i]=quick(fac[i],Mod-2);
}
}
ll getans(ll n,ll m)
{
return fac[n]*inv[n-m]%Mod*inv[m]%Mod;
}
int main(){
getfac();
cin>>n>>k;
m = n / k;
for(int i = 1; i <= m; ++i){
q = n - i * (k - 1);
ans += getans(q - 1, i - 1);
// ans += C(p - 1, i - 1);
ans %= mod;
}
ans %= mod;
cout<<ans<<endl;
return 0;
}
平衡的字符串
题目描述：
lhl322告诉Miaoyao，仅仅学好数学是不够的。想要在XCPC中取得好成绩，字符串类的题目就绕不开。于是，Miaoyao又开始研究起字符串来了……
对于一个01串，若其中0的个数与1的个数相同，我们称它是平衡的。
给出由0、1、?三种字符组成的01串。Miaoyao想知道是否存在一种方案，将每个'?'均改变为0或1中的一种，使得所有长度为k的子串都是平衡的。
思路：
首先k为奇数显然无解
其次对于[1,k] [2,k + 1]，其交集是[2,k], 如果这两个串都是平衡的，则s[1]必然等于s[k + 1],其他的也同理
也就是Si = Si + k
于是我们就可以根据下标分成k组，每组只要确定一个元素，那么这个组都必然是这个元素，如果一个组内出现不同的，就说明不符合
再就是要对前k个字符进行判断，只有当1和0的数量都小于等于k/2才行
#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
//不开longlong见祖宗！
int n, k, p;
int num1, num2;
int zero, one;
string s;
int main(){
cin>>n>>k>>s;
if(k % 2 == 1)cout<<"No\n";
else {
for(int i = 0; i < k; ++i){
zero = 0;one = 0;
for(int j = i; j < n; j += k){
if(s[j] == '1')++one;
else if(s[j] == '0')++zero;
}
if(one && zero){
cout<<"No\n";
return 0;
}
if(zero)++num1;
if(one)++num2;
}
if(num1 <= k / 2 && num2 <= k / 2)cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
京公网安备 11010502036488号