4 Pure_W

尚未进行身份认证

博主很懒=w=

等级
TA的排名 4w+

三维偏序下求最长“上升”序列的分治做法讲解

Part 0​ 首先,做一个人畜无害的假设:箱子之间的三维长度彼此不同。约定每个箱子的三维用 xyzxyzxyz 表示。Part 1​ 让我们从一个 dpdpdp 做法讲起:​ 记 f[i]f[i]f[i] 表示第 iii 个箱子最多能做几层套娃,那么假如能装进第 iii 个箱子的那些箱子(记为 jjj)的 f[j]f[j]f[j] 都已经被正确计算了[1]^{[1]}[1],那么有 f[...

2020-04-13 01:32:21

Codeforces Round #528 (Div. 1, based on Technocup 2019 Elimination R D. Rock-Paper-Scissors Champion

https://codeforces.com/contest/1086/problem/D因为每次只修改一个位置,很容易想到去确认每次造成的变化。但是实际上最后都绕不过一个问题,怎么判断一个人是否可以成为冠军。那么相当于在不动这个人的情况下,要把两边的克制它的人清掉。换句话说(以剪刀为例),某一侧有石头,那么那一侧就要有布。那么对应的不能成为冠军的剪刀就是最左边的石头到最左边的布之间的(要...

2019-01-03 12:24:32

[Codeforces] Round #528 div1C div2E

https://codeforces.com/contest/1086/problem/C贪心匹配,只有三种状态:压上界,压下界,不压界(出解)#include<bits/stdc++.h>using namespace std;#define N 1000005int n,k;char a[N],b[N],c[N];int go[30];bool use[30];...

2018-12-24 08:22:54

[51nod] 2388 首都

https://www.51nod.com/Challenge/Problem.html#!#problemId=2388曼哈顿距离与切比雪夫距离互转#include<bits/stdc++.h>using namespace std;#define N 100005int n;long long sum[2][2],ans,dis,x[N],y[N],X[N],Y[N]...

2018-12-24 08:20:08

[51nod] 1663 01游戏

https://www.51nod.com/Challenge/Problem.html#!#problemId=1663很显然,两个人的策略都是从前往后取,先手取1,后手取0影响答案的因素只有:0数量,1数量,?数量,最后一个0和1的位置,最后两个?的位置#include<bits/stdc++.h>using namespace std;char s[100005];...

2018-12-20 19:41:03

gym 101981E 2018ICPC南京区域赛 Problem E. Eva and Euro coins

k个相同字符相邻是没有意义的,可以消去具体解释:k个1可以变成0k个0可以把其后方紧邻的1搬到前面贪心处理两个串,判断是否相等#include<stdio.h>#define N 1000005int stk[N][2],top,n,k;char a[N],b[N];inline void solve(char s[]){ stk[top=0][0]=-1;...

2018-12-03 19:35:49

Codeforces 2C - Commentator problem

可以用数学方法做初试爬山#include<stdio.h>#include<cmath>const int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};inline double sqr(double x){return x*x;}const double eps=1e-6;double x[3],y[3],r[3],X,Y;in...

2018-12-02 09:49:07

gym 101981H 2018ICPC南京区域赛 H Huge Discount

有趣的题目 thx to ZJU很容易注意到如果有一个数多于一半,那么只能剩它考虑其他情况,发现答案只可能是0和1那么就可以拿0开刀了,判断是否存在一个0使得序列可以只消剩0(包含这个0)这个判断可以转化为,这个0左右分别可以消成全0序列(1和2的个数不超过一半)做的时候从右向左扫,可以直接统计右侧的情况,左侧的情况开个线段树维护一下#include<bits/stdc++.h...

2018-11-22 15:03:56

gym 101981K 2018ICPC南京区域赛 K Kangaroo Puzzle

训练的时候用的做法是选一个点追所有人但是cjb的这个做法实在是太过分了(雾随个50000的串就能过#include<bits/stdc++.h>using namespace std;int main(){ srand(time(0)); char t[]={'U','D','L','R'}; for (int i=0;i<50000;i++) putchar...

2018-11-22 14:54:52

Codeforces Round 520 div2

开了场VP,头上充满buffA读错题,题意只找一段,wa一发找到最长的连续子串就好(补0和1001)#include<bits/stdc++.h>using namespace std;int n,ans,a[1005];int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf(&

2018-11-16 18:39:13

Codeforces 1076E E. Vasya and a Tree

这是一个静态问题按DFS走,进入一个子树时把子树根上挂的修改激活,离开子树时撤销这样所有的修改和查询都是对于深度的QvQ:递归三参数栈爆炸了#include<bits/stdc++.h>using namespace std;#define M 524288#define N 300005typedef long long ll;int L,R,aim,n,m,to...

2018-11-15 11:35:17

Codeforces 1076D Educational Codeforces Round 54 (Rated for Div. 2) D. Edge Deletion

考虑到每条边最多只能使一个点进入最短路图,所以答案就是构建一棵不超过k条边的最短路树注意不要搞出森林#include<bits/stdc++.h>using namespace std;#define N 300005typedef long long ll;int Q[N],tot,s[N],ans;bool vis[N],op[N];ll dis[N];str...

2018-11-15 08:27:45

UVALive 8275 M - Annual Congress of MUD 2017中国台湾花莲区域赛

网络流很显然,问题是直接暴力搞边数会爆炸注意到本质不同的人(起终点不同)只有不到四百种,以此建点#include<stdio.h>#include<algorithm>#include<cstring>#define cint const int &#define inf 2333333#define N 505using namespa...

2018-11-14 22:12:50

Gym 100151E 2011-2012 ACM-ICPC, NEERC, Southern Subregional Contest E. Berland Chess

如果可以记忆化搜索,切勿写剪枝爆搜#include<stdio.h>#include<cstring>#include<queue>#include<algorithm>using namespace std;#define For(i,a,b) for (int i=a;i<=b;++i)#define Void inline ...

2018-11-08 21:13:33

Gym 100151C 2011-2012 ACM-ICPC, NEERC, Southern Subregional Contest C. Dice Tower

相对面总和为7,中间所有骰子被吃了一个相对面,最顶上和最底下任选一面被吃(对只有一个骰子不成立)n个骰子最大可以表示的值可以算出,相对的,可以算出要求值对应的n,再检查一下是否大于n最小可以表示的值#include<stdio.h>int main(){ freopen("input.txt","r",stdin); freopen("output.txt...

2018-11-08 21:11:56

Gym - 100109L 2012-2013 ACM-ICPC, NEERC, Southern Subregional Contest L - Preparing Problem

先算出完成时间,再加上溢出时间#include<bits/stdc++.h>using namespace std;int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int a,b,n,l,r; scanf("%d%d%d",&a

2018-11-05 09:21:40

Gym - 100109F 2012-2013 ACM-ICPC, NEERC, Southern Subregional Contest F - Dumbbells

直接暴力限定每种质量物品个数然后求价值前k大的质量#include<bits/stdc++.h>using namespace std;#define N 4005#define mp(a,b) make_pair(a,b)#define fi first#define se secondpair<int,int> p[N];int n,k,id[N],...

2018-11-05 09:20:08

Gym - 100886D 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest D - Catenary

题目中有一句很迷幻的话:这是对双曲余弦函数的离散模拟翻译成人话就是长成下图这样的图形就别考虑了,总体上还是和双曲余弦函数图像比较像的双曲余弦函数在这种情况下也可以叫悬链线,很容易可以查到相关资料(不过对于这题没啥帮助)根据题目的需求,把图形翻转一下得到向上垂的图形因为铰链连接的木棍,在连接点上力的方向不一定沿杆的方向,所以需要对力的方向进行分析下图黑色是木棍,红色是力的方向记从x轴...

2018-11-03 01:03:44

Gym - 100886F 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest F - Empty Vessels

所有的操作都可以转化为向最大的杯子里倒一整杯的水(模意义下完全背包)#include<bits/stdc++.h>using namespace std;#define For(i,a,b) for (int i=a;i<=b;++i)int fm[20005],a[11],A,id,mod,n;queue<int> Q;void output(in...

2018-11-01 14:30:44

Gym - 100886B 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest B - Game on Bipartite

题目有很强的结论,看代码应该可以知道结论是什么但是想了两天还是没有想到一个严格的证明大概思路:首先边的奇偶影响答案(走过去优就继续拓展,不优就走回来)转化为01问题考虑消元的过程中,对面的一个点会发生什么如果这个点可以成为主元,说明从这个点出发一定会有奇数长度的路径(即便是双方交替进行)↑感性认识一下感觉非常有道理,然而并不会证(sad然后基于这个结论就可以做了,把其他所有点的出边...

2018-10-31 19:29:33

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。