2020-2021:teams:wangzai_milk:cf2100-2800泛做1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/04 19:41] zars19 |
2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/05 15:24] (当前版本) zars19 [1332E - Height All the Same] |
||
|---|---|---|---|
| 行 536: | 行 536: | ||
| ====== 1388E - Uncle Bogdan and Projections ====== | ====== 1388E - Uncle Bogdan and Projections ====== | ||
| - | 给 $x $轴以上的若干水平线段。现可以指定一个向量让所有线段沿该方向投影到 $x $轴上，投影不可以重叠，宽度定义为投影最右端横坐标减去最左端横坐标，问可能的最小宽度。 | + | 给 $x$ 轴以上的若干水平线段。现可以指定一个向量让所有线段沿该方向投影到 $x$ 轴上，投影不可以重叠，宽度定义为投影最右端横坐标减去最左端横坐标，问可能的最小宽度。 |
| 如果纵坐标全部相同，直接垂直投影即可。否则我们可以在使得某个投影与投影相切的时候取到最小宽度。对任意两个纵坐标不同的线段，我们可以算出两个投影相切的角度，从而得到一段不可行的区间。扫描线得出全局的可行投影角度区间。 | 如果纵坐标全部相同，直接垂直投影即可。否则我们可以在使得某个投影与投影相切的时候取到最小宽度。对任意两个纵坐标不同的线段，我们可以算出两个投影相切的角度，从而得到一段不可行的区间。扫描线得出全局的可行投影角度区间。 | ||
| - | 而要在合理时间内得到取若干角度时投影的最大最小横坐标，可以用一个叫Convex Hull Trick的做法。设 $\theta $为投影线与 $x $轴正方向的夹角， $(x,y) $投影在横坐标 $x-\frac y{tan(\theta)} $的位置。以 $-\frac 1{tan(\theta)} $为自变量，则 $y_i $为斜率， $x_i $为截距。若干直线只会在一个凸包上取得最大值，我们先求出这个凸包，之后对于每个 $-\frac 1{tan(\theta_i)} $可以二分。最小值同理。 | + | 而要在合理时间内得到取若干角度时投影的最大最小横坐标，可以用一个叫Convex Hull Trick的做法。设 $\theta$ 为投影线与 $x$ 轴正方向的夹角， $(x,y)$ 投影在横坐标 $x-\frac y{tan(\theta)}$ 的位置。以 $-\frac 1{tan(\theta)}$ 为自变量，则 $y_i$ 为斜率， $x_i$ 为截距。若干直线只会在一个凸包上取得最大值，我们先求出这个凸包，之后对于每个 $-\frac 1{tan(\theta_i)}$ 可以二分。最小值同理。 |
| <hidden><code cpp> | <hidden><code cpp> | ||
| 行 642: | 行 642: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | <\code><\hidden> | + | </code></hidden> |
| + | \\ | ||
| + | |||
| + | ====== 1332E - Height All the Same ====== | ||
| + | |||
| + | $n\times m$ 的网格，位置 $(i,j)$ 上有 $a_{i,j}$ 个方块，每次操作可以在某位置加两个方块，或者在两个相邻位置各加一个方块，目标是使得所有位置高度一致。问在 $a_{i,j}\in[l,r]$ 的条件下，能达成目标的方案有多少。 | ||
| + | |||
| + | 一个观察是重要的只是所有位置上方块数量的奇偶性，同一个位置加两个方块这一操作不改变奇偶性，而使得所有位置奇偶性一致后必能用这个操作达成目标。 | ||
| + | |||
| + | 另一个观察是，我们必能改变且仅改变任意一对格子的奇偶性（这是因为两个位置间必有一条路径，沿路径每次翻转相邻两个就好）。 | ||
| + | |||
| + | 当有偶数个奇数或偶数个偶数个时，可以把它们两两配对改变奇偶性达成目标，否则不可以。 | ||
| + | |||
| + | * 当 $n\times m$ 为奇数时，必然是偶数个奇数奇数个偶数/偶数个偶数奇数个奇数，答案是总数 $\mathrm{total}=(r-l+1)^{nm}$ 。 | ||
| + | * 当 $n\times m$ 为偶数时，奇偶都是偶数个可以，奇偶都是奇数个不行。pikmike提供了一个直觉法： | ||
| + | |||
| + | * 当 $r-l+1$ 为偶数时，答案是 $\frac{\mathrm{total}}2$ | ||
| + | * 当 $r-l+1$ 为奇数时，可行将会比不可行多 $1$ 。这是因为 $[l,r]$ 中必定有 $k\in[l,r]且 k\oplus1\notin[l,r]$ 。每一种方案，我们可以选第一个不为 $k$ 的位置给 $a_{i,j}$ 异或 $1$ ，这样可以使可行方案与不可行方案两两配对，除了全部为 $k$ 的一个方案可行。答案 $\frac{\mathrm{total}+1}{2}$ | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define mp make_pair | ||
| + | #define pb push_back | ||
| + | #define pii pair<int,int> | ||
| + | using namespace std; | ||
| + | const ll mod=998244353; | ||
| + | ll n,m,l,r; | ||
| + | ll qpow(ll a,ll b) | ||
| + | { | ||
| + | ll res=1; | ||
| + | while(b) | ||
| + | { | ||
| + | if(b&1)res=res*a%mod; | ||
| + | a=a*a%mod,b>>=1; | ||
| + | } | ||
| + | return res; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%lld%lld%lld%lld",&n,&m,&l,&r); | ||
| + | ll tot=qpow(r-l+1,n*m); | ||
| + | if((n*m)&1)printf("%lld\n",tot); | ||
| + | else if((r-l+1)&1)printf("%lld\n",(tot+1)%mod*qpow(2,mod-2)%mod); | ||
| + | else printf("%lld\n",tot*qpow(2,mod-2)%mod); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| \\ | \\ | ||
2020-2021/teams/wangzai_milk/cf2100-2800泛做1.1596541263.txt.gz · 最后更改: 2020/08/04 19:41 由 zars19
