MrBird_to_fly-CSDN博客

原创 CF 932G 回文树

关于log个border的dp，把等差数列的border的贡献和记录在最长的回文节点上。 #include <bits/stdc++.h>using namespace std;typedef long long ll;const int mod=1e9+7;const int maxn=1000007;char str[maxn];struct PAM{ in...

2018-10-31 19:32:55 354

原创 Hdu 4656 任意模数FFT

UOJ 模板题提交记录http://uoj.ac/submission/290654需要高超的推公式技巧。使用了叉姐的一份板子，侵删。#include &lt;bits/stdc++.h&gt;using namespace std;// double 精度对$10^9+7$ 取模最多可以做到$2^{20}$const int MOD = 1e6+3;const double P...

2018-10-07 21:36:55 411

51nod 1135题目描述求小于1e9的素数p的原根#include &amp;amp;lt;bits/stdc++.h&amp;amp;gt;using namespace std;int pi[40];int tot=0;int power(int x,int n,int p){ int base=x; int ans=1; while(n){ if(n&amp;amp;amp;1){ ans=1ll

2018-09-20 15:31:13 811

原创 Bzoj 3122 离散对数

题目描述HINT这题的p是素数。。。尼玛想半天不会。。。会合数版本的请联系我#include <bits/stdc++.h>using namespace std;typedef long long ll;map<ll,int>mp;void exgcd(ll a, ll b, ll &x, ll &y){ if(b==0){ x=1,...

2018-09-19 21:22:40 244

原创 SPOJ MOD 离散对数

题目描述求方程A^X=B%C的最小非负整数解，这里的C不一定是素数。#include <bits/stdc++.h>using namespace std;typedef long long ll;//A^X=B%Cunordered_map<ll,int>mp;ll exbsgs(ll a,ll b,ll c){ if(c==1)return 0; ll...

2018-09-19 20:07:24 418

原创 Hdu 6184 三元环计数

题目描述给一个2e5点2e5边的无向图，求子图 { V=(A,B,C,D) E=(AB,BC,CD,DA,AC) } 的数量。HINT考虑把所有边定向，从度数小的点往度数大的点连，这样每个点的出度都小于sqrt(2e5)。#include &lt;bits/stdc++.h&gt;using namespace std;typedef long long ll;const int ...

2018-09-19 20:03:28 411 1

原创可持久化线段树练习题

Bzoj 2653 题目描述：一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。其中a &lt; b &lt; c &lt; d。位置也从0开始标号。我会使用一些方式强制你在线。#include &lt;...

2018-09-16 21:49:27 728

原创回文树练习题

Tsinsen A1280 问题描述　　顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。　　输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。#include &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;bits/stdc++.h&amp;amp;amp;a

2018-09-08 18:13:11 741

原创 CF 815C 树形背包

翻zzq的blog过程中发现了一个题一类有依赖的树形背包dp方法。搜题过程中搜到了某场打过的CF的某个题，尴尬的是这题还T着。于是尝试使用blog中的思路dp，发现可能不太行(也可能是我太菜了)，但是回忆起jls说的树形dp优化，发现zzq的做法可能年代有点久远，好像被完爆了啊。#include <bits/stdc++.h>using namespace std;typede...

2018-08-24 17:16:16 256

原创长链剖分 Vijos 巴蜀中学 lxhgww的奇思妙想

lxhgww的奇思妙想长链剖分求K级祖先模板题。疯狂爆栈。。把dfs都加了个inline就过了。。这可能是信仰的力量吧。。#include <bits/stdc++.h>using namespace std;const int maxn=300005;struct edge{ int to,next;}e[maxn<<1];int head[...

2018-08-24 15:06:10 251

原创 LOJ 6235 洲阁筛

尝试理解Min_25筛失败，绝望地用洲阁筛切了个板题。#include &amp;lt;bits/stdc++.h&amp;gt;using namespace std;typedef long long ll;const int LIM=400000,P=30000;ll sqr;bool vis[LIM];int prime[P],sum[LIM],last[LIM&amp;lt;&amp;lt;1],cnt...

2018-08-23 20:16:57 603

原创牛客网暑期ACM多校训练营（第十场）

jls场 A 签到#include <bits/stdc++.h>using namespace std;const long long mod=998244353;int n,m,t,c,l,r;long long a[100007],sum[100007];long long cal(long long a, long long b){ long...

2018-08-21 13:56:29 272

原创牛客网暑期ACM多校训练营（第九场）

毕姥爷场 A FWT#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mod=1e9+7;const int inv2=500000004;ll power(ll n,ll p){ ll ans=1; ll base=n; while(p){...

2018-08-21 13:39:26 257

原创牛客网暑期ACM多校训练营（第八场）

YJZ场，持续自闭。 B oeis#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mod=998244353;ll power(ll n,ll p){ ll ans=1; ll base=n; while(p){ if(p&a...

2018-08-21 13:32:56 278

原创牛客网暑期ACM多校训练营（第七场）

zscoder场 A 签到#include<bits/stdc++.h>using namespace std;int n,p[500000];void find(int n){ if(n<0) return; int x=1; while(x<=n) x<<=1; for(int i=n; i...

2018-08-21 13:28:14 208

原创 FFT&&FNT模板

UOJ 34 终于把板子更新到正常的版本了。FFT :#include &lt;bits/stdc++.h&gt;using namespace std;const double pi=acos(-1.0);typedef complex&lt;double&gt;E;int n,m,x,L,mn;int R[1&lt;&lt;18];E a[1&lt;&lt

2018-08-18 20:44:32 316

原创 2018 Multi-University Training Contest 5

A 学习了一下题解，好像很牛逼啊，这个ll爆得也很灵性，tls牛逼啊。#include <bits/stdc++.h>using namespace std;typedef unsigned long long ll;ll one=1;char buf[30000003];ll rdp=0;inline ll read(){ ll ret=0; whi...

2018-08-07 17:11:52 180

原创 2018 Multi-University Training Contest 3

A 从后往前单调队列求最小值。队尾的是A，队列长度是B。#include &amp;lt;bits/stdc++.h&amp;gt;using namespace std;typedef long long ll;char buf[30000003];int rdp=0;inline int read(){ int ret=0; while(buf[rdp]&amp;gt;='0'&amp;amp...

2018-08-07 15:40:36 158

原创 2018 Multi-University Training Contest 2

D 签到。#include <bits/stdc++.h>using namespace std;int main(){ int n; while(cin>>n){ cout<<"Yes\n"; }}E 手玩一个构造方案出来。发现43不够，就47取左上角。#include <bits/s...

2018-08-07 15:10:37 163

原创 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛

A 由于小数点之后只有一位，可以随机一下。#include&lt;bits/stdc++.h&gt;using namespace std;const int canshu=10;int cs;int t,n;double x;struct node{ double x,y; int num;}a[10005];int tot;bool cmp(n...

2018-08-07 14:32:06 227

原创牛客网暑期ACM多校训练营（第六场）

A 签到。#include<bits/stdc++.h>using namespace std;const int N=(1<<15)+1;int t,n;bool vis[N][15],lose[N];int num[N][15];int main(){ scanf("%d",&t); for(int tt=1; tt<...

2018-08-07 14:15:04 157

原创牛客网暑期ACM多校训练营（第五场）

怎么大家都这么强啊。。。完全打不过啊。。。 A 二分答案check一下。#include<bits/stdc++.h>using namespace std;const int N=100005;const double eps=1e-6;int n,k,s[N],c[N];double tmp[N];double ans;int main(){ scan...

2018-08-02 20:54:32 170

原创 2018 Multi-University Training Contest 4

太尼玛难了，告辞。 A x是k-magic数：小于x的正整数有超过K个因子多于x。重要结论：一个数如果是k-magic数，那么它的倍数也是k-magic数。发现非k-magic数很少——枚举k最大时的所有非k-magic数。一开始知道1是非k-magic数。从小到大枚举质数。对于每个质数p，将已知的数乘以p的幂加入数列直到超出上限，然后筛掉全部k-magic数（按数字从小到大维...

2018-08-02 00:10:13 210

原创牛客网暑期ACM多校训练营（第四场）

打得头皮发麻。。。 A 比赛的时候维护了每个phi的取模，卡常卡过了。听说有O(n+log2n)O(n+log2n)O(n+log^2n)的牛逼算法，就学习了一下。#include &amp;amp;lt;bits/stdc++.h&amp;amp;gt;using namespace std;typedef long long ll;ll mod[30]={1000000007,1000000006,5...

2018-07-28 22:48:08 361 2

原创 2018 Multi-University Training Contest 1

hdu这边做得好像更惨一点，感觉苟进rk10基本没希望啊。 A 签到。#include &lt;bits/stdc++.h&gt;using namespace std;int main(){ int T; scanf("%d",&amp;T); while(T--){ int n; scanf("%d",&amp

2018-07-27 10:56:52 136

原创牛客网暑期ACM多校训练营（第三场）

solo打得头皮发麻。一个下午全在贴板，药丸。 A 折半一下，前缀最值搞搞就完了。#include <bits/stdc++.h>using namespace std;typedef long long ll;int w[40][4],v[40];int m[4];struct node{ ll sta,sum; void init(){ ...

2018-07-27 10:41:24 341

原创牛客网暑期ACM多校训练营（第二场）

A 签到#include &amp;lt;bits/stdc++.h&amp;gt;using namespace std;const long long mod=1e9+7;long long q,k;long long dp[100003][2];int main(){ scanf(&quot;%lld%lld&quot;,&amp;amp;q,&amp;amp;k);

2018-07-22 19:46:50 553 3

原创牛客网暑期ACM多校训练营（第一场）

A 推了推发现成了原题，直接度了一发随便改改就过了原题参考 https://blog.csdn.net/MIECZ/article/details/80591212#define IN_LB() freopen(&quot;C:\\Users\\acm2018\\Desktop\\in.txt&quot;,&quot;r&quot;,stdin)#define OUT_LB() freopen(&quot;C:\\U

2018-07-19 18:12:59 264

原创补题（队内训练）

http://icpc.njust.edu.cn/Contest/6258/I/ Tree DP 读题 Code: #include <bits/stdc++.h>using namespace std;int n,x,y;vector<int>g[50008];int dp[50008][2];int v[50008];int tag[50008];...

2018-07-02 16:11:15 251

原创 CF 600E 树上众数启发式合并

顺便实现了在每次增减1的情况下，数组最大值的维护。#include &lt;bits/stdc++.h&gt;using namespace std;typedef long long ll;struct edge{ int to,next;}e[200003];int head[100003];int cnt;void init(){ memset(head...

2018-07-01 18:16:32 372

原创补题（2016-2017区域赛）

写在前面：有些事很艰难，但必须去做。比如模拟以前经历过的困境，尝试再次置身其中。假如连过去的问题都无法解决，又凭什么让自己相信，当全新的问题出现时，能做得更好呢？2016 ICPC Dalian, by Avalon Board: http://board.acmicpc.info/icpc2016/dlmu_onsite.php Solved Now: 10/11Prob...

2018-07-01 16:55:21 657

原创 Hdu 5992 KD-Tree

2016 ICPC Qingdao K#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll INF=1ll<<60;struct node{ int d[3],ma[3],mi[3],l,r,id;}T[200003];int rt,n,m,cmp_d;i...

2018-06-30 19:45:07 232

原创 Bzoj 2648 KD-Tree

信仰剪枝喜+1#include <bits/stdc++.h>using namespace std;const int INF=1e9+7;struct node{ int d[2],ma[2],mi[2],l,r;}T[1000003];int rt,n,m,cmp_d;inline bool cmp(node a,node b){ return a...

2018-06-30 19:40:19 157

原创 2018 Google Code Jam Round 2

A. Falling Balls#include <bits/stdc++.h>using namespace std;char g[105][105];int a[105];int main(){ int T; scanf("%d",&T); for(int tt=1;tt<=T;tt++){ int n; ...

2018-05-20 16:37:27 1134

原创 CF 467D 强连通分量缩点DP

缩点之后按拓扑序在DAG上做一下DP。注意SUMLEN可能会爆INT。#include <bits/stdc++.h>using namespace std;map<string,int>mp;int tot=0;int n,m;string s[200003];struct edge{ int to,next;}e[200003];int ...

2018-05-08 17:28:52 345

原创 Poj 2942 点双联通分量

王桂平的图论书上把这题错误地归类为边双联通分量，于是WA到生活不能自理。主要区别在于这样的图：显然按照每个点经过一次的环来算的话，这个图并不能构成环，所以每个点经过一次的环应该包含于点双联通分量内部。而每条边经过一次的环包含于边双联通分量内部。#include <iostream>#include <cstdio>#include <cstring...

2018-05-08 14:31:38 258

原创 Hdu 2242 边双联通分量

垃圾blog太多，实在难以卒读，于是掏出书系统学习了下，发现边双联通分量无非就是把桥删了，讲了一大堆，毛用没有。上次抄了个假板子搞的怀疑人生，遂口胡一遍算法，自己手撸了一个，希望从此BCC变成SB题。#include <bits/stdc++.h>using namespace std;struct edge{ int to,next;}e[40003];int...

2018-05-07 15:14:08 238

原创 CF 947D 细节讨论

传送门这题挂了一大波人，包括T神，直接结果就是CF万年不变的榜首终于换了人。233 现在看来，如果当时再仔细一点就黄了，可惜。回到正题：首先很明显的是： B->AC->AAB->AAAC->C C->AB->AAC->AAAB->B于是B和C本质上是等价的，可以把所有的C替换成B，得到： A->BB B->AB A...

2018-03-12 13:42:35 371

原创 Zoj 4009 线段树

题意：给定模数99971，在区间上维护两个操作，一个是区间所有数三方，还有一个是区间求和。（均是在取模意义下的操作）做法：注意到348≡1mod99970348≡1mod999703^{48}\equiv 1\mod 99970，则由Fermat小定理，有a348≡amod99971a348≡amod99971a^{3^{48}}\equiv a\mod 99971。于是对于任何一个数，做48...

2018-03-10 22:06:52 300

原创 2017 ACM-ICPC ECL-FINAL 部分代码

以下代码均为现场代码，注释不存在的 A#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mod=1e9+7;ll power(ll n,ll p){ ll ans=1; ll base=n; while(p){ if(p&1){

2017-12-18 15:06:52 1677

空空如也

空空如也