ZRA班D1
ZJOI2020密码
你有个大素数P,1e15~1e18
然后有个%P意义下的未知数x
每次告诉你的值
但是会给你一个误差!
+-0.01P的范围内(喂喂喂!)
给你50组信息希望你回答出x
,直接枚举 即可,然后check期望O1一下就会出错的
a_1x<=1e11
a_2x<=1e11...
如果认为他们是独立的,因为P为1e18,所以一次指数上会少7种可能
前两个方程中只有1e4个可能的x
其实魔改扩欧能求axmodp在一定范围内最小整数解
考虑分成T块
y=l,l+1....l+T-1....l+2T-1
会发现两块之间是整体加上
所以我们按道理来讲也是每块连续的一段的,包括开头和结尾连续的一段!
....].....[.......这样子...可以二分
std?
我们注意到在某个区间内
当A大的时候很难受,但A很小的时候
eg:
x\in(\lceil \frac kp a \rceil,\lfloor \frac kp+E a \rfloor),k \in 0~A-1$$Error 会发现x的解能写成若干个区间的形式! 所以怎么让a变小? m个方程里面取k个加起来qwq 如果每个误差都是1e16,每个搞一个符号$S_i\in{-1,1}$ $\sum a_i*S_i*x(mod P)$ 其实这样就变成了1e16k的误差 会发现我们扩大了误差范围,但是缩小了A的范围! 现在就是要联立几个方程把前面系数搞得尽量小! meet in middle 随机k个数字成为方程的子集 [0,1]间k个实数两两之间的差期望是$\frac 1 k^2$的!或者1/(k+1)^2 所以我们的k选取1e6就能把A搞到1e6级别! 而AxmodP,A是1e6我们的误差只是1e16~1e17 每次撞出一个区间可以使得剩下的数变少很多,约为90% 也是说我们每次随机5个方程的子集 我们能得到若干个x的取值区间,然后他们求一个交就好了.... 这样整个题都过不了再优化一下就会变得比别人快很多的那种快 怎么卡hash? 1.meet in the middle $(\sum_i a_ibase^i)%P$ 随机根号p个然后自然相撞就会有很多相同的值... 3.tree attack 先把1e5个数字排成一列,值域1e18 然后两两做差,$a_2-a_1,a_4-a_3....$ 他们差值期望是1e13级别的,数字规模/2 那么在这个序列里面递归做下去能找到一个解再原问题也能找到一个解了! 这样做着做着很快就矛盾了.... 大概2000多个就能冲突了! 直接treeattack串长两千都让你完蛋 原问题 $\sum |S_i|<=20$ $a_i$很少,直接treeattack做个两三轮 第二轮放$a_2-a_1,a_3-a_1,a_4-a_1...$ 其余同理,不要求$S_i\in{-1,1}$ 这样最多能有k组呢! 设立阈值m,每次把前m小的拿出来,然后做一轮误差放大两倍而已... 但是前面的系数变小的会很快! 所以每一轮保留的方程多一点就能让这个A下降的很快.... 3.Multi-tree attack 维护m的最小可能的和???每个子集维护了m组可能的相减的方案 这东西能卡多模? 理理思路好像就是 1.联立方程组能让变小就能得到若干值域区间取交 2.多做几次求交 优化:还原,然后所有的方程都和y相关 保留在撞得过程中间的方程,随着数字变少后面a可以放得稍微大一点 ZJOI2020序列 你有一段长度为n的非负数序列 然后你可以每次选择一个区间,把这个区间所有数-1,下标为奇数位置-1,下标为偶数位置-1 最大流=最小割 是因为LP对偶 ~~linear program....~~ 求最大循环费用流.. 上限为v,费用是w 要满足流量平衡,使得流量*费用最大! 给每个点一个标号$h_i$ 使得$min \sum_{u,v\in E}max(h_u-h_v+w(u,v),0)*C_{u,v}$ w是费用C是上限 就是给每个点一个标号使得上面这个式子尽量小 那么如果要求上面那个就是求最大循环费用流 显然可以从 t向s连边,然后$=min\sum{c(u,v)}max(h_u-h_v,0)+\inf * max(h_s-h_t+1,0) <=0$ $h_s>=h_t+1$才能最小化inf啊 $h_s=1,h_t=0$ 相当于把每个点分标0,1然后最小化流量可以看成分配给S,T两个点集,所以是最小割 CF1307G 假设我们做完之后每个点标号$d_i$ 距离标号满足$d_v<=d_u+L_e + x_{u,v}$ 要求在$\sum{x,u,v}<=x$最大化$d_t-d_s$ 我们想向$min\sum{c(u,v)}max(h_u-h_v,0)$去凑 但是$d_t-d_s>=\lambda$ $x_{u,v}>=max(d_v-d_u-l_e,0)$ 我们想要$d_u-d_v<=t$ 所以$\inf max(d_v-d_u+t,0)$ 这个东西就和LP很一致了........ 现在我们把v向u连条$(1,-t)$的边 inf那个就是s到t连边(inf,L)吧... 最大化L,使得最大cost<=x 会发现我们每次增广的权值是单调递减的... $f_i$表示从t到s走i的流量最小花费 整个图的最大流就是$max(iL+f_i)<=x$ $L<=min(x-f_i/i)$ 最多增广n次 回到原题 只有区间-1? 最小值是$1/2\sum{a_i-a_{i+1}}$ $=\sum max{a_{i+1}-a_{i},0}$ $=\sum max{a_i-a_{i+1},0}$ noip题? 然后现在就是要跳着减 $a1...an$ $a1-xi$ $x_i<a_i$ 跳一个$x_i...x_n$ $max(x_i-x_{i-2},0)+max((x_i-x_{i-1})+(a_{i-1}-a_i))$ 最小化这玩意,相当于把$a_i-a_i-1$当做权值... 还有$x_i>=0,x_i<=a_i$ 对于第一个可以设置一个0,$x_0$ $x_i-x_0>=0$ -> $max(x_0-x_i,0)\inf$ 第二个? $+max(x_i-y-a_i,0)\inf$ 每个点连个流量,费用$-a_i,\inf$ 然后循环起来就好了.... 直接求复杂度不太对 考虑状压每个点的流量,每个点只有三条边,是一还是0 还有直接对偶.....但要会手推LP对偶 $h_u-h_v$的分段线性初函数都可以这么做的.... 就是每一段都能拆成一个折线啊 然后每个函数加起来,就是若干个max加起来 左边是$h_u-h_v$,相当于每加一段就是多连了几条边 还有贪心!我命来了 如果$a_1>0,a_2$也大于0 那么从$a_1$出发一定选择连续的区间-1 否则$a_2$也是跳一个-1,就一定可以拆成新形势 a_2出发连续的,a_3开始跳,a_1变得连续 如果$a_1<a_2$直接走下小的 $a_1>a_2 ,min(a_1,a_2)$ 考虑下a_2和a_3? 设一个从1开始时的决策为线段 前面有->跳>为A 跳跳为B $a_3<A+B$ $a_3>=A+B$ $K=A+B-a_3$个线头会被堵住qaq 但是有问题,这K个可能不能都是一个类型的 比如$A<K$,说明我们额外要停掉一些B... 考虑$A_2$现在已经类似于开头的一个位置,那么能连就+1+1,剩下我们再连+2的线段 做完A2后把A3当成1,然后再让答案-K因为我们用free的边了 反正看看下面抄的代码吧还是很不错的.... ```cpp #include<bits/stdc++.h> using namespace std; #define int long long const int MAXN = 1e5 + 7; int A, B, C, D, K, tmpa, tmpb, ans; int n, a[MAXN]; inline void init() { scanf("%lld", &n); for(int i = 1; i <= n; ++i)scanf("%lld", a + i); ans = 0; A = B = C = D = 0; } signed main() { int T; scanf("%lld", &T); while(T-- > 0) { init(); for(int i = 2; i <= n + 1; ++i) { if(a[i] <= A + B) { K = A + B - a[i]; if(B < K)A -= K - B, K -= K - B; if(A < K)B -= K - A, K -= K - A; A -= K, B -= K, D = K, a[i] -= K; } K = min(a[i - 1], a[i] -= A + B); a[i - 1] -= K; a[i] -= K; ans += K; A += K; C += a[i - 1]; ans += a[i - 1]; a[i - 1] = 0; ans -= D; a[i] += D; D = 0; swap(B, C); } printf("%lld\n", ans); } return 0; } ``` ZJOI2020抽卡 你有m张卡,每次从里面抽卡,抽到连续编号为k的卡最少要几轮