Description

机器人刚刚探查归来，探险队员们突然发现自己的脚下出现了一朵朵白云，把他们托向了空中。一阵飘飘然的感觉过后，队员们发现自己被传送到了一座空中花园。
“远道而来的客人，我们是守护Nescafe之塔的精灵。如果你们想拜访护法和圣主的话，就要由我们引路。因此，你们是不是该给我们一点礼物呢T_T？”
队员们往远处一看，发现花园中有 $N$ 个木箱，$M$ 条柔软的羊毛小路，每条小路的两个端点都是木箱，并且通过它需要 $t_i$ 的时间。队员们需要往每个木箱中放一份礼物，不过由于精灵们不想让花园被过多地踩踏，因此运送礼物的任务最多只能由两位探险队员完成。
两位探险队员同时从 $1$ 号木箱出发，可以在任意木箱处结束运送。运送完毕时，每只木箱应该被两位队员中至少一人访问过。运送任务所用的时间是两人中较慢的那个人结束运送任务的时间。请问这个时间最快是多少呢？

Input

第一行两个正整数 $N$、$M$。 接下来 $M$ 行每行三个整数 $x_i$、$y_i$、$t_i$，表示 $x_i$ 和 $y_i$ 之间有一条用时为 $t_i$ 的小路，小路是双向的。

Output

输出所需的最短时间。

Sample

Input copy

6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10

Output copy

40

数据范围：

$30\%$ $9 \le N \le 10$
$70\%$ $17 \le N \le 18，1 \le t_i \le 1000，1 \le x_i,y_i \le N$
两个木箱之间最多只有一条小路，不会有自己到自己的小路，保证所有木箱是连通的。

20251107-NOIP-模拟赛

题目概述

A. trape

背景

一个平面上有许多点，LYH 需要在这个平面上画一个等腰梯形，LYH 希望在这个梯形的点尽可能得多，LYH 让你帮她求梯形内最大点数。（点在梯形边上也算梯形内）

题目描述

给出 M 个点，求用一个上底长 $25$、下底长 $75$、高 $50$ 的等腰梯形最多能框住的点数。

输入格式

第一行两个正整数 N, M，N 表示横坐标在 [-N, N]，纵坐标在 [-N, N] 的平面大小，M 表示点数。
接下来 M 行，每行两个整数 x, y，为各个点的横纵坐标。

输出格式

一行一个正整数为最大点数。

样例

输入

100 4
0 0
75 0
25 50
50 50

输出

4

数据范围

• 60% N <= 150
• 80% M <= 300
• 90% M <= 3000
• 100% N <= 2500, M <= 10000, -N <= x, y <= N

限制

• 2s
• 128M

B. Candies(candies)

题目描述

小 W 有 $N$ 堆糖果，每堆有 $a_i$ 个。现在，他要把这 $N$ 堆糖果分别分给 $N$ 个小朋友。为了使每个小朋友被分到的糖果数尽量均匀，小 W 每次会按顺序执行以下操作： 1. 找到糖果数量最多的糖果堆（如果多于一个，则随机选择一个），从中取出一颗糖果； 2. 在剩下各堆糖果中(包含前面取出糖果的那堆)找到糖果数量最少的糖果堆（如果多于一个，则随机选择一个），将刚刚取出的糖果放入这堆糖果中。

现在，小 W 想请你帮他计算，$K$ 次操作后，最终被分到糖果最多的小朋友与最少的小朋友，他们得到的糖果数之差（即操作后糖果最多的糖果堆中的糖果数与糖果最少的糖果堆中的糖果数之差）。

输入输出格式

输入格式

从文件 candies.in 中读入数据。

输入包含多组测试数据。

第一行包含一个正整数 $T$ ，表示该测试点的测试数据组数。

对于每组测试数据，第一行包含两个正整数 $N,K$ ，表示糖果的堆数和小 W 要进行的操作次数；第二行包含 $N$ 个正整数 $a_i$ ，表示每堆糖果初始时的糖果数。

输出格式

输出到文件 candies.out 中。

对于每个测试数据，输出一行包含一个正整数，表示该组测试数据的答案。

样例输入和输出

样例输入 1

2
4 100
1 1 10 10
4 3
2 2 2 2

样例输出 1

1
0

数据范围

对于 $10\%$ 的数据，$N\leq 500, K\leq 40000, a_i\leq 500$ ；

对于 $30\%$ 的数据，$N\leq 1000, K\leq 1.5\times 10^5, a_i\leq 1000$ ；

对于 $50\%$ 的数据， $N\leq 10000, K\leq 2\times 10^7, a_i\leq 10^5$ ；

对于 $100\%$ 的数据，$1\leq N\leq 10^5, 1\leq K \leq 1\times 10^{15}, 1\leq a_i\leq 10^9$ 。

B. Game(game)

题目描述

Alice 和 Bob 在玩一个游戏，Alice 和 Bob 各自控制着自己的队伍 A 和 B，假设军队中的人分布在一个一维数轴上。现在 Alice 和 Bob 每回合都可以做出一个行进指令：

以 Alice 为例，她可以让 A 队伍中的每个人都向前或向后移动 x 的距离，同理 Bob 也可以操作 B 队伍，进行一次行进。

现在告诉你战场的初始情况，即两个队伍中的人在数轴上的分布（但是我们并不知道每个人属于哪个阵营），以及经过一个回合后队伍中人的位置(只有一个回合)，你需要求出 Alice 和 Bob 所做的行进指令是什么。

输入输出格式

输入格式

从文件 game.in 中输入数据。

第一行一个数$ n $，代表两个队伍中的人的总和。

第二行$ n $个整数，第$ i $个整数代表第$ i $ 个人的初始位置 $ x_i $。

第三行 $n$ 个整数，第$ i $个整数代表一个回合后各个人的位置 $y_i$。

$x_i $和 $y_i$ 不一定对应同一个人的位置。

数据保证不会有两个人处于同一个位置。

输出格式

输出到文件 game.out 中。

第一行一个数$ n$，代表两个队伍中的人的总和。

第二行$ n $个整数，第 $i$ 个整数代表第 $i$ 个人的初始位置 $x_i$。

第三行 $n $个整数，第$ i $个整数代表一个回合后第$i$个人的位置$ y_i$。

数据保证不会有两个人处于同一个位置。

样例输入和输出

样例输入 1

5
1 2 3 4 5
70 71 0 1 72

样例输出 1

67 -1

Alice 控制初始的$3,4,5$三个位置，操作后为$70,71 ,72$。

Bob 控制初始的$1, 2$两个位置，操作后为$0, 1$。

输出两个距离代表一个可能的行进指令。数据保证至少存在一个解。

数据范围

对于$ 30\% $的数据，$n≤100$;

对于 $70\%$ 的数据，$n≤1000$;

对于 $100\%$ 的数据，$n≤70000, 0≤x_i, y_i≤100000$。

C.Rcomb (rcomb)

题目描述

$Na$老师有$N$张卷子排成一列，第$i$张卷子有其难度$V_i$，由于$X$爷的出现，$Na$老师需要将这些卷子合并为$1$张 每次$Na$老师以相等的概率随机选择两张相邻卷子，消耗两张卷子难度和的体力，得到一张难度为两张卷子难度和的卷子，求$Na$老师需要消耗的体力期望值。

输入输出格式

输入格式

第一行：一个整数$N$。

第二行：$N$个整数$V_1、V_2、...、V_N$。

输出格式

只有一行，一个小数，表示(小数点后保留3位)表示$Na$老师需要消耗的体力期望值。

样例输入和输出

样例输入 1

2
1 1

样例输出 1

2.000

样例输入 2

4
1 2 3 4

样例输出 2

21.667

数据范围

对于 $20\%$ 的数据 $N \leq10$;

对于$ 40\%$ 的数据 $N\leq100$;

对于$ 80\%$ 的数据 $N\leq5000$;

对于 $100\% $的数据 $1\leq N \leq 500000 , 1 \leq V_i \leq 10000$.

E. 红蓝(redblue)

题目描述

在坐标平面上有 $N$ 个红色点和 $M$ 个蓝色点。给定自然数 $W$ 和 $H$。

第 $i$ 个 ($1 \leq i \leq N$) 红色点的坐标是 $(r_{xi}, r_{yi})$，第 $j$ 个 ($1 \leq j \leq M$) 蓝色点的坐标是 $(b_{xj}, b_{yj})$。

所有点的坐标都是不同的。

我们需要放置一个宽度为 $W$，高度为 $H$ 的矩形，该矩形的边与坐标轴平行，并且它的四个顶点是整数坐标。我们希望最大化矩形内包含的红色点与蓝色点数量之差。

矩形包含点的条件是：如果矩形的左下角坐标为 $(a, b)$，且点的坐标为 $(x, y)$，那么该点包含在矩形内当且仅当满足 $a \leq x \leq a+W$ 且 $b \leq y \leq b+H$。

我们要求得这个差值的最大值，并找到符合这个最大差值的矩形位置。

下图展示了在平面上有 3 个红色点和 4 个蓝色点的情况。为了说明问题，红色点用圆圈表示，蓝色点用三角形表示。

假设 $W = 5$，$H = 3$，那么如果将矩形的左下角放在 $(3, 3)$，矩形内包含 1 个红色点和 3 个蓝色点，这时点的数量差为 2。无论矩形放置在哪里，点的数量差都不会大于 3，因此答案是 2。

输入格式

第一行给出整数 $N$ 和 $M$，以及矩形的宽度 $W$ 和高度 $H$。

接下来的 $N$ 行，每行包含一个红色点的坐标 $(r_{xi}, r_{yi})$。

接下来的 $M$ 行，每行包含一个蓝色点的坐标 $(b_{xj}, b_{yj})$。

输出格式

输出一个整数，表示最大点数差值。然后输出矩形左下角的坐标 $(a, b)$。

如果答案有多个，输出任意一个即可。

输入输出样例 #1

输入 #1

3 4 5 3
3 2
2 5
7 6
1 2
4 3
3 6
7 4

输出 #1

2
3 3

输入输出样例 #2

输入 #2

3 3 4 4
1 1
2 2
3 3
1 3
3 1
4 4

输出 #2

2
-2 -2

说明/提示

约束条件

• $1 \leq N, M \leq 100\,000$
• $1 \leq W, H \leq 10^9$
• $1 \leq r_{xi}, r_{yi} \leq 10^9$ ($1 \leq i \leq N$)
• $1 \leq b_{xj}, b_{yj} \leq 10^9$ ($1 \leq j \leq M$)

子任务

1. （10 分）$1 \leq N, M, W, H, r_{xi}, r_{yi}, b_{xj}, b_{yj} \leq 50$
2. （15分）$1 \leq N, M, W, H, r_{xi}, r_{yi}, b_{xj}, b_{yj} \leq 1\,000$
3. （15 分）$1 \leq N, M \leq 100$
4. （10 分）$1 \leq N, M \leq 1\,000$
5. （50 分）无额外约束条件

一份代码，从周六提交到周一，一直是 Judgement Failed，到底什么问题啊啊啊啊啊啊啊啊

T423，代码如下

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10,P=998244353,MOD=1e9+7;
bool cmpbig(int i,int j)
{
    return i>j;
}
double mylog(int x,int y)
{
    return log(x)/log(y);
}
long long qpow(long long a,long long b,long long mod=LLONG_MAX)
{
    if(b==0)return 1;
    if(b==1)return a;
    return qpow(a,b/2,mod)%mod*qpow(a,b/2,mod)%mod*(b&1?a:1)%mod;
}
int n,a,b,c;
void solve()
{
    a=0,b=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        a+=x*sgn[i]*(1ll<<i);
    }
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        b+=x*sgn[i]*(1ll<<i);
    }
    c=a+b;
    for(int i=0;i<n;i++)
    {
        if(c%2)cout<<1<<' ',c-=sgn[i];
        else cout<<0<<' ';
        c/=2;
    }
    cout<<'\n';
}
signed main()
{
    FAST
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>sgn[i];
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}