总结
寄掉啦,\(50+30+100+8\)。
T1 组队 (team)
分析
很简单的题目,通过充分发扬人类智慧,设 \(x\) 为二元组 \((i,j)\) 满足 \(i<j, a_i = a_j\) 的数量,则答案为 \(2^x - 1\)。
代码
没有。
T2
话外
世界奇观:、
附:题面
组队 (team)
题目描述
穗织镇上共有 \(n\) 个种族的秽神,第 \(i\) 个种族的秽神数量为 \(2^{ai}\),且对任意数 \(z\),最多只能找到两个种族 \(i, j\) ,使得 \(a_i = a_j = z\)。令 \(k = max\{a_i\}\),[丛雨]想知道一共有多少种方法组合出一支数量为 \(2^{k+1}\) 的秽神队伍,注意不一定需要用到所有种族。
输入格式
第一行一个数字 \(n\);
第二行 \(n\) 个数字,即 \(a_i\)。
输出格式
一个数字表示方案数,由于答案可能很大,答案对 \(998244353\) 取模。
样例 #1
样例输入 #1
6
0 1 2 3 4 4
样例输出 #1
1
提示
对于 \(30\%\) 的数据,满足 \(n \le 20, a_i \le n\)。
对于再 \(20\%\) 的数据,满足所有种族的秽神数量两两不同。
对于再 \(20\%\) 的数据,能且只能找到一对 \(i, j\),使得 \(a_i = a_j\)。
对于 \(100\%\) 的数据,满足 \(n \le 10^5, a_i \le 10^9\)。
卡牌 (uno)
题目描述
[丛雨]喜欢和朋友们玩一种桌游卡牌(其实就是 UNO
)。这种卡牌共分四种颜色:红色、绿色、蓝色及黄色,每种颜色各有写着 \(0−9\) 的数字牌和功能牌:skip
(跳牌)、reverse
(反转出牌方向)。另有一些转色牌,不属于任何颜色。
游戏开始时,丛雨、[芳乃]、[茉子]每人从牌堆抽出 \(N\) 张牌,由丛雨第一个出牌,出牌顺序由丛雨决定。丛雨可以将任意牌作为第一张牌打出,接下来所有人出牌遵守以下规则:
- 按照丛雨规定的出牌顺序轮流出牌,必须出一张且只能出一张。若无符合规则的手牌可出,三人游戏失败。
- 若打出非转色牌,则所打出的牌要么颜色与上一张牌相同,要么数字与上一张牌相同(数字牌),要么功能与上一张牌相同(功能牌)。若为功能牌,执行对应功能:
skip
:跳过下家出牌,由下家的下家打出下一张牌(由于只有 \(3\) 个人参加,下家的下家就是上家)。reverse
:将原本顺时针的出牌顺序变为逆时针,或相反,并由变化后的下家(原来的上家)打出下一张牌。- 若打出转色牌,则无论上一张牌是什么都可以打出,且出牌者可决定下家应出哪种颜色的牌。
- 首先出完手牌的人胜出。而丛雨认为如果三个人能接连打出最后一张手牌,那么应该算
共赢
。
给出三人的手牌,请帮丛雨判断有没有 共赢
的可能性。
输入格式
第一行一个数字 \(T\) 表示测试组数,接着有 \(T\) 组数据按如下格式输入。
第一行一个整数 \(n\) ,表示每个人的手牌数。
接下来三行,每行分别描述了丛雨、芳乃、茉子的手牌。
描述方法是输入 \(n\times 2\) 个整数,每两个相邻的整数表示一张牌。
第一个整数表示颜色,用 \(0, 1, 2, 3\) 表示红,黄,绿,蓝,若为 \(4\) 则为转色牌。第二个整数为数值或功能,\(10\) 表示 skip
,\(11\) 表示 reverse
。对于转色牌,第二个整数无效。
输出格式
对于每组测试数据,若有可能共赢,输出 Y
,否则输出 N
,每次输出后换行。
样例 #1
样例输入 #1
3
1
0 10
0 11
0 0
2
0 0 1 2
1 1 3 2
0 1 2 2
3
0 10 2 0 3 11
2 10 3 0 1 0
1 10 3 1 4 0
样例输出 #1
Y
Y
Y
提示
对于 \(20\%\) 的数据,满足 \(n = 1\)。
对于再 \(20\%\) 的数据,只有数字牌。
对于再 \(20\%\) 的数据,只有数字牌和转色牌。
对于 \(100\%\) 的数据,满足 \(n \le 6, T \le 10\)。
午饭 (lunch)
题目描述
[丛雨]来到一家餐馆吃午饭。菜单里 \(4\) 道菜,价格分别为 \(a_1, a_2, a_3, a_4\) 元,还有 \(3\) 道甜品,价格分别为 \(b_1, b_2, b_3\) 元。丛雨需要点一道菜和一道甜品,但丛雨又不想花费太多钱,请你帮帮她找出最小需要花费多少元。
输入格式
第一行包括四个整数 \(a_1, a_2, a_3, a_4\),表示每道菜的价格。
第二行包括三个整数 \(b_1, b_2, b_3\),表示每道甜品的价格。
输出格式
输出一行一个整数,表示丛雨最少需要花费多少元。
样例 #1
样例输入 #1
7 1 6 7
5 4 9
样例输出 #1
5
提示
对于 \(100\%\) 的数据,满足 \(1 \le a_1, a_2, a_3, a_4, b_1, b_2, b_3 \le 1000\)。
集合 (set)
题目描述
给定一个平面点集,求有多少子集满足,按照 \(y\) 降序排序后,对每个 \(j\) 都满足 \(x_{j - 2} < x_j < x_{j - 1}\) 或者 \(x_{j - 1} < x_j < x_{j - 2}\) 。
输入格式
第一行一个整数 \(n\),表示点的个数。
接下来 \(n\) 行,每行两个整数 \(x_i\), \(y_i\),表示第 \(i\) 个点的坐标。
输出格式
一行一个整数表示答案对 \(10^9+7\) 取模后的结果。
样例 #1
样例输入 #1
4
2 2
3 1
1 4
4 3
样例输出 #1
14
提示
对于 \(8\%\) 的数据,满足 \(1 \le n \le 18\)。
对于 \(20\%\) 的数据,满足 \(1 \le n \le 100\)。
对于 \(52\%\) 的数据,满足 \(1 \le n \le 1500\)。
对于 \(72\%\) 的数据,满足 \(1 \le n \le 4000\)。
对于 \(100\%\) 的数据,满足 \(1 \le n \le 6000\),\(0 \le |xi|,|yi| \le 10^9\)。\(x_i\) 互不相同,
\(y_i\) 互不相同。