BestCoder Round #73(div.2)

BestCoder Round #73(div.2)

比赛链接：​​click here​​

Rikka with Chess

问题描述

一个n \times mn×m的黑白相间的棋盘，每次可以选择一个矩形把其中的所有格子反色。问把所有格子变成一种颜色时的最少操作次数。

输入描述

第一行一个整数 T(T \leq 10)T(T≤10) 表示数据组数。每组数据有一行, 两个正整数 n,m(n \leq 10^9, m \leq 10^9)n,m(n≤109,m≤109)。

输出描述

对于每组数据输出一行一个整数，代表最少需要的操作次数。

输入样例

3 1 2 2 2 3 3

输出样例

1 2 2

【思路】：

代码：

/*Problem:BC#73 Rikka with ChessAuthor :javaherongweiRuntime:0msLanguage: G++Result :Accepted*/#includeint main(){ int i,j,k,t,n,m,ans; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); printf("%d\n",n/2+m/2); } return 0;}

Rikka with Graph

问题描述

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：给出一张 nn 个点 n+1n+1

输入描述

第一行一个整数表示数据组数 T(T \leq 30)T(T≤30)。每组数据的第一行是一个整数 n(n \leq 100)n(n≤100)。接下来 n+1n+1 行每行两个整数 u,vu,v

输出描述

对每组数据输出一行一个整数表示答案。

输入样例

1 3 1 2 2 3 3 1 1 3

输出样例

9

【思路】：

代码：

/*Problem:BC#73 Rikka with GraphAuthor :javaherongweiRuntime:296msLanguage: G++Result :Accepted*/#pragma comment(linker,"/STACK:102400000,102400000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include

Rikka with Array

问题描述

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：有一个长度为 nn 的数组 AA（下标为 11 到 nn），A_iAi 为 ii 的二进制表示中的1的个数，例如 A[1]=1, A[3]=2, A[10]=2A[1]=1,A[3]=2,A[10]=2。现在勇太想知道数组 AA 中满足 A[i]>A[j]A[i]>A[j] 的数对 (i,j)(1 \leq i < j \leq n)(i,j)(1≤i

输入描述

第一行一个整数表示数据组数 T(T \leq 10)T(T≤10)。每组数据第一行一个整数表示 n(n \leq 10^{300})n(n≤10300)

输出描述

对于每组数据输出一行一个整数表示答案，因为答案可能很大，你只需要输出答案对 998244353998244353

输入样例

1 10

输出样例

7

Hint

当 n=10n=10 的时候，数组 AA 为 1,1,2,1,2,2,3,1,2,21,1,2,1,2,2,3,1,2,2。答案为7。

【思路】：

待补~~

Rikka with Sequence

问题描述

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：有一个长度为 nn 的整数数组 AA，AA中每一个数都在区间 [1,m][1,m] 中。现在你需要加入最少数量的数使得 AA 的平均数小于等于中位数（加入的数可以是实数）。加入的数必须在 [1,m][1,m]

输入描述

第一行一个整数 T(T \leq 1000)T(T≤1000) 表示数据组数，其中 n > 100n>100 的数据不超过 55 组。每组数据第一行两个整数 n,m(n \leq 10^5,m \leq 10^9)n,m(n≤105,m≤109)。接下来一行 nn 个整数描述数组 AA。

输出描述

对于每组数据输出一行两个数，第一个数表示最少添加的数字的数量，第二个数表示最小的平均数（保留三位小数）。

输入样例

1 3 5 1 2 5

输出样例

1 3.000

Hint

只需要加入数字 4.0004.000

【思路】：

这是一道没什么思维含量的题，但是细节比较多。

1.总数是奇数，中位数是原来给出的数。

2.总数是奇数，中位数是加入的数。

3.总数是偶数，中位数是原来给出的两个数的平均数。

4.总数是偶数，中位数是一个加入的数和一个比它大的原来给出的数的平均数。

5.总数是偶数，中位数是一个加入的数和一个比它小的原来给出的数的平均数。

6.总数是偶数，中位数是两个新加入的数的平均数。

待补~~

Rikka with Phi

问题描述

给出一个长度为nn的数组AA，接下来有mm次操作。1 \; l \; r1lr 对所有区间[l,r][l,r]中的整数ii，把A_iAi变成\varphi(A[i])φ(A[i])(指欧拉函数)2 \; l \; r \; x2lrx 对所有区间[l,r][l,r]中的整数ii，把A[i]A[i]变成xx3 \; l \; r3lr 询问[l,r][l,r]的区间和。

输入描述

第一行一个整数 T(T \leq 100)T(T≤100) 表示数据组数，其中 n > 10^5n>105 的数据不超过 22 组。每组数据第一行两个整数 n,m(n \leq 3 \times 10^5, m \leq 3 \times 10^5)n,m(n≤3×105,m≤3×105)。接下来一行 nn 个整数描述数组 AA。接下来mm行, 每行若干个整数表示一次操作。保证在任意时刻 1 \leq A[i] \leq 10^71≤A[i]≤107。

输出描述

对于每一次询问输出一行，代表这个询问操作的答案。

输入样例

1 10 10 56 90 33 70 91 69 41 22 77 45 1 3 9 1 1 10 3 3 8 2 5 6 74 1 1 8 3 1 9 1 2 10 1 4 9 2 8 8 69 3 3 9

输出样例

80 122 86

【思路】：

待补~~（平衡树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、​​Treap​​​等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的​​数列​​，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。）

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。