【BZOJ 2461】 Beijing2011 符环

傻逼dp


http://paste.ubuntu.com/15549737/

记一场奇怪的BC


【前因】
 大概在BC#75的时候,一只KPM说要出题,思考了一下,手上有一道可以当E题的题没有出出来过,就果断找KPM入坑了。



 于是在KPM大爷的带领下,很快找到管理员确认了出题的要求和具体格式,然后分了一下锅,我负责BE,KPM负责ACD。这使得我花了一个晚上的时间思考B题该出什么,最后决定出了一道傻逼送分题。KPM大爷的三道题都坑点满满(此处应该有题面),但貌似C和D搞反了顺序?


 一开始我和KPM都以为pretest和systemtest的数据应该有很多组,结果我每道题各造了20组压压惊,压了个包发现数据有500M,吓得我坐在了地上。...


【BZOJ 4332】分零食

一种简单的思想是dp[i][j]表示前i个人,获得j个糖时所有情况的积的和,复杂度O(M^2)不可过


假如没有“所有没有糖的人都要在最后连续的一段”的限制,是一道倍增FFT的裸题


现在加入这个限制,没有关系,我们还是倍增FFT,用F[i][j],表示前i个人,获得j个糖,且每个人都有糖的时候所有情况的积的和,G[i][j]表示前i个人,至少有一个在最后的人没有获得糖的时候,所有情况的积的和。


倍增FFT进行转移,复杂度O(MlgMlgM)


代码:http://paste.ubuntu.com/15471029/


20160321


(听说某氪同学怒斥我不写博客,所以就假装写一发


上午考试,AK欢乐赛?


没想到图论的考试这么基础,简直是科普向。第一题就是喊你找找桥边嘛,第二题就是看你会不会网络流。第三题?第三题和BZOJ 2049有区别么。


所以无聊了好久,看着某氪同学在那里纠结第二题?黑爷爷竟然也不会第二题?吓得我赶紧再拍了一万组。


然后就水了个300走人。某GG也是300,胖子第一题挂了一个点真是2333


果然下雨天最适合写题了。既然心里知道打不了球,也不会那么浮躁了。


雨敲在窗户上的声音还是挺好听的,只是为什么和每天早上楼上的老师倒水的声音那么像?


所以林可好强林可跪烂


【BZOJ 4418】 扇形面积并

考虑对于每个分出来的区域算合法的半径长度,答案即所有半径长度的平方和


考虑差分,线段树上二分,复杂度O(NlgN+M)


代码:


#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>
#include <iostream>
using namespace std;


int n, m, k;


const int MAXN = 100010;


struct Opt {...

【BZOJ 4416】 阶乘字符串

n>21时无解


考虑n<=21的情况,用dp[S]表示利用S里面的字符可以到的最远的位置,预处理nxt[i][j]表示i后面第一个j字符出现的位置进行转移,复杂度O(N*2^N)



代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>


using namespace std;


int T,n;


const int MAXN = 1<<21;
int...

【BZOJ 4419】 SHOI2013 发微博

Solution:

考虑枚举每条边的贡献,一条边(x,y,l,r)表示x,y这条边在l到r时间内出现过,对y的贡献是x在这段时间内发的微博数,对x贡献同理。


考虑用前缀和进行优化,倒过来做,加入一条边的时候加入反序前缀和,不然减去反序前缀和,发微博就使x点的前缀和++


代码:


#include <cstdio>
#define N 500010
using namespace std;
int x[N],y[N],v[N],n,m,i;char S[10],t[N];long long s[N];
int main() {
  for (scanf("...

【BZOJ 4414】 数量积

记f[i] = 第i个fibonacci数,f[0] = f[1] =1;
观察可得Vi·Vj = f[(i+j)*2-1]


求出前n<<2个fibonacci数计算贡献即可


复杂度O(N)


代码:
#include <cstdio>
#include <algorithm>


using namespace std;
int C,M,n;
int cnt = 0;
int ans[2000010],tp = 0;
int main() {
#ifdef YJQ_LOCAL
  freopen...

【BZOJ 4155】Humble Captains

  • 第一问水水的最小割,从来没有写得如此愉快。
    假设两个集合A,B
    第二问等价于min($| \sigma_i [i in A] D[i] - \sigma_i [i in B] D[i] |$),01背包就好了

  • #include<cstdio>


    #include<bitset>


    using namespace std;


    const int N=40010,inf=~0U>>2;


    struct edge{int t,f;edge*nxt,*pair;}*g[N],*d[N],pool[240000],*cur=pool;


    int...

【BZOJ】4209 西瓜王

观察到求出区间第K大,如果奇数个数和偶数个数都是偶数,则输出前K大的和,否则要么奇数多一个,要么偶数多一个,主席树SB题


代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>
#include <cctype>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif


using...

© yjq_1999 | Powered by LOFTER