2023河南萌新联赛第（四）场：河南大学

B：序列的与和

D:幂运算

E：平均数

J：异次元抓捕

K：奖励关

M：找孙子

B：序列的与和

WY是一个序列大师，他喜欢研究一些和序列相关的操作。时间长了，WY对某一些特定的序列产生了感情，换句话说，WY喜欢和这些特定的序列打交道。比如说WY最近就迷上了这样一类序列：

我们规定序列的与和定义为序列中所有元素按位与得到的结果。
- 如序列 [1,2,3] ：其与和结果为1&2&3=0.
若一个序列与和的结果，其二进制表示形式下包含 k 个 1 ，WY则会认为这是他喜欢的序列

现在WY的手里有一个序列了，他想知道，这个的序列的非空子序列中有多少个他喜欢的序列。由于WY已经非常熟悉这类序列了，所以他想考考你，看看你是否能解决这个问题。

子序列定义为：从原序列中去除几个（可以为零个）元素后得到的序列。

输入：
第一行两个正整数， n 和 k ：
分别表示序列元素个数 n ，以及WY喜欢的序列类型的与和，在其二进制形式下包含 1 的个数 k。
第二行 n个数，表示给定的序列元素 ai。
数据范围：
1<=n<=20,0<=k<=20,0<=ai<=2^64-1.
输出：
对于每个测试样例输出一个数字，表示你统计的满足要求的子序列的个数。

示例1

输入

3 6
2 4 1

输出

说明

对于样例，其子序列有：

[2]：其与和为10（二进制）,仅包含一个1，不为6，所以对答案贡献为零

[2,4]：与和为 0 ,同理，贡献为零。

[2,1]：与和结果0

[2,4,1]：与和结果0

[4]：与和结果100

[4,1]：与和结果0

[1]：与和结果1

综上，答案为0。

思路：深度优先搜索，直接遍历就行了，（比赛时候一直在想子序列公式，吐了）

int a[30],sum=0,n,k;
void find(int x,int y)
{
	if(__builtin_popcount(y)==k)//统计该数在二进制下1的个数
	sum++;
	for(int i=x+1;i<=n;i++)
	find(i,y&a[i]);
}
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	find(i,a[i]);
	cout<<sum<<endl;
	return ;
}

D:幂运算

小 T 最近在学习离散数学，书上有一句话:

n 个命题变项只能生成 2^2^n 个真值不同的命题公式。

现在小 T 想要知道，对于两个给定的正整数 n, p, n 个命题变项在模 p 意义下能生成多少个真值不同的命题公式？

形式化的说，对于两个给定的正整数 n, p：计算 2^2^n mod p的值

取模运算的定义为a mod b=a−⌊a/b⌋×b

数据保证 1≤n≤1e6,1≤p≤2 31−1

输入描述:
一行，两个正整数 n, p
输出描述:
一行，一个整数表示2^2^n mod p

示例1

输入

3 1223

输出

思路：从2开始直接一直翻倍取模n次就行（看写的少，没开，原来是个水题。。。。。）

void solve()
{
	int n,p,sum=2;
	cin>>n>>p;
	while(n--)
	{
		sum=(sum*sum)%p;
	}
	cout<<sum<<endl;
	return ;
}

E：平均数

小 A 是一个刚上大学的大一新生，作为新时代的年轻人，聚餐自然不会像 80 后一样抢着请客，而是优先考虑 AA

现在有一次聚餐，一共消费了 S 元，在座共有 n 人，因为大家觉得 1.99 这样的金额不够整，看上去很不爽，所以大家都只会出整数金额的钱

为了尽可能公平，不妨设第 i 个人给了 ai元，你需要使 an这个数列的方差尽可能小，同时满足 ∑i=1 nai=S

给定 n, S, 要求你给出一个不下降序列 an 在满足∑i=1nai=S 的情况下使得这个数列的方差尽可能小

对于所有数据，保证1≤n≤1e6,1≤S≤1e18

输入描述:
第一行，两个正整数 n, S
输出描述:
一行， n 个整数表示 ai, 中间用空格隔开

示例1

输入

7 30

输出

4 4 4 4 4 5 5

思路：直接s/n算出每个人的最低花费，s%n从后往前每人加上1，直到s%n减为零（签到）

void solve()
{
	int n,aa,b,s,c;
	cin>>n>>s;
	aa=s/n;
	c=n-1;
	for(int i=0;i<n;i++)
	a[i]=aa;
	b=s%n;
	while(b--)
	{
		a[c]++;
		c--;
	}
	for(int i=0;i<n;i++)
	cout<<a[i]<<" ";
	return ;
}

J：异次元抓捕

在一个时间空间都无穷大的二维的平行宇宙中（为了简化问题，用网格表示空间）

小y因为偷取宝物被发现，开始了逃亡之旅，

小y可以在以自身为中心的边长为（2∗k+1) 的正方形网格中任意移动(1≤k≤1e5)（注意不可以不移动）

每次小y移动过后，追捕者会在空间中放下一个障碍物，拦截小y，（一个障碍物会占领一个1*1的网格）（障碍物不会出现在小y脚下)）

由于小y有着高超的身法，小y可以在移动过程中越过障碍物，但是不能停留在有障碍物的地方。

（如图当k=1的时候，蓝色网格为小y的可移动范围）

小y和追捕者都聪明绝顶，小y知道所有障碍物的位置，追捕者也知道小y的位置
并且两者都会选择最优的策略，
如果最后小y被障碍物围住而无法再次移动，就会被抓住。
你需要判断小y是否会被抓住
如果小y会被抓住，输出YES
否则，输出NO
输入描述:
第一行包含一个正数t(1≤t≤1e5)——问题询问次数
每次询问输入一个整数k
输出描述:
对于每个测试用例
如果会被抓住，输出YES
否则，输出NO

示例1：

输入：

2
1
617

输出：

YES
NO

思路：k==1时能抓到，输出YES，否则输出NO。

void solve()
{
    int k;
    cin>>k;
    if(k==1)
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    return ;
}

K：奖励关

有一个可以无限重生的boss，开始时boss有1点生命值，当boss被击败后（血量小于等于0时），玩家可以获得1点积分，此后boss会复活并且血量翻倍(第一次复活是2，第二次是4，第三次是8，依次类推，复活之后boss满血)，再次击败boss后可以再次获得1点积分。
boss不会行动，初始时玩家攻击力为1，玩家可以行动 n 个回合，对于每一个回合玩家可以选择下面三种操作的一个。
操作1：攻击对boss攻击，boss降低的血量等于玩家的当前攻击力
操作2：攻击强化攻击力永久 × 2
操作3：蓄力下次攻击时，攻击力 × 8，可以叠加（两次蓄力后可以 × 64,但是攻击之后增益消失），只对第一次攻击有收益

示例：执行5次操作，分别为22311，那么第一次的攻击时攻击力是32，第二次的攻击时攻击力是4
输入描述:
第一行一个正整数 T(T≤105) 代表多组询问
接下来 T 行，每行一个正整数n(n≤1e9)代表此轮可以进行的操作数
输出描述:
T行，每行一个整数，输出玩家选择最优的操作方案可以获得的最大积分数

示例1

输入

2
1
3

输出

1
2

备注:
当前攻击力等于 2^(i+3× j ),i表示已执行操作2的次数，jjj表示当前攻击与上一次攻击间隔间的操作3的次数

思路：仔细思考会发现，蓄力的收益在n较小时和强化一样，但是在n较大时强化的收益远远大于蓄力带来的，所以直接一直强化即可。

void solve()
{
    int n,a=1,b=1,sum=0;
    cin>>n;
    cout<<(n+1)/2<<endl;
    return ;
}

M：找孙子

ym 刚刚被他的儿子冷落了，他现在想要找他的孙子诉诉苦

给定一个有向无环图，请你找出对于每个节点，对于其作为爷爷节点时，存在多少对爷爷-孙子关系

爷爷-孙子关系的定义是，如果在有向无环图中存在有向边 (x, y)(x,y) 和 (y, z)(y,z), 那么称 zz 是 xx 的孙子，有序对组 [(x, y), (y, z)] 称为一个爷爷-孙子关系

请注意：对于相同的一对爷爷，孙子节点，可能存在不同的中间节点，使得爷爷-孙子关系数量大于一
输入描述:
第一行输入两个正整数 nn, mm, 数据保证 1<=n<=1e6,1≤m≤2×1e6
接下来 mm 行，每行两个正整数 uu, vv 表示存在一条有向边 (u, v)
数据保证不存在重边和自环
输出描述:
输出一行 nn 个数字，用空格分隔开，第 ii 个数字表示编号为 ii 的节点的孙子数量
示例1

输入

输出

3 1 0 6 0

思路：分别用一维vector容器来遍历，二维vector容器储存孙节点个数（想着二维数组内存过不了，二维vector居然能过）

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    int n,m;
    cin>>n>>m;
    vector<vector<int>> graph(n + 1);
    vector<int> grandchildren_count(n + 1, 0);
    for (int i=0;i<m;i++) 
	{
        int u,v;
        cin>>u>>v;
        graph[u].push_back(v);
    }
    for (int i=1;i<=n;i++) {
        for (int j:graph[i]) {
            for (int k:graph[j]) {
                grandchildren_count[i]++;
            }
        }
    }
    for (int i=1;i<=n;i++) {
        cout<<grandchildren_count[i]<<" ";
    }
    return 0;
}

今日推荐音乐：温柔—五月天

下一篇：背包问题（模板）

文章出处登录后可见！

已经登录？立即刷新

2023河南萌新联赛第（四）场：河南大学

B：序列的与和

D:幂运算

E：平均数

J：异次元抓捕

K：奖励关

M：找孙子

相关推荐