好多东西都不熟练……

数论

数论分块「bzoj2956: 模积和」

10.28.2018

 #include<bits/stdc++.h>

 typedef long long ll;

 const int MO = ;

 const int inv6 = ;

 ll n,m,ans,del;

 inline void Add(ll &x, ll y){x = ((x+y)%MO+MO)%MO;}

 ll sum(ll x){return x*(x+)%MO*(*x+)%MO*inv6%MO;}

 ll calc(ll x)

 {

     ll ret = ;

     for (ll i=, j=; i<=x; i=j+)

     {

         j = x/(x/i);

         Add(ret, 1ll*(x/i)*(i+j)*(j-i+)/%MO);

     }

     return ((x%MO*x%MO-ret)+MO)%MO;

 }

 int main()

 {

     scanf("%lld%lld",&n,&m);

     if (n > m) std::swap(n, m);

     ans = calc(n)*calc(m)%MO;

     del = n*m%MO*n%MO;

     for (ll i=, j=; i<=n; i=j+)

     {

         j = std::min(n/(n/i), m/(m/i));

         ll s1 = (sum(j)-sum(i-))*(n/i)%MO*(m/i)%MO;

         ll s2 = (n*(m/i)%MO+m*(n/i)%MO)%MO*((i+j)*(j-i+)/%MO);

         Add(del, (s1-s2)%MO);

     }

     Add(ans, -del);

     printf("%lld\n",ans);

     return ;

 }

图论

点-树链剖分「1036: [ZJOI2008]树的统计Count」

10.24.2018

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 const int INF = 0x3f3f3f3f;

 struct node

 {

     int tot,fa,son,top;

 }a[maxn];

 int n,m;

 char opt[];

 int f[maxn<<][];

 int chTot,chain[maxn],cnVal[maxn],d[maxn],dep[maxn];

 int edgeTot,head[maxn],nxt[maxm],edges[maxm];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void addedge(int u, int v)

 {

     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;

     edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;

 }

 void pushup(int rt)

 {

     f[rt][] = std::max(f[rt<<][], f[rt<<|][]);

     f[rt][] = f[rt<<][]+f[rt<<|][];

 }

 void build(int rt, int l, int r)

 {

     f[rt][] = -INF;

     if (l==r){

         f[rt][] = f[rt][] = cnVal[l];

         return;

     }

     int mid = (l+r)>>;

     build(rt<<, l, mid), build(rt<<|, mid+, r);

     pushup(rt);

 }

 void dfs1(int x, int fa)

 {

     a[x].fa = fa, a[x].tot = ;

     dep[x] = dep[fa]+, a[x].son = -;

     for (int i=head[x]; i!=-; i=nxt[i])

     {

         int v = edges[i];

         if (v!=fa){

             dfs1(v, x);

             a[x].tot += a[v].tot;

             if (a[x].son==-||a[v].tot > a[a[x].son].tot)

                 a[x].son = v;

         }

     }

 }

 void dfs2(int x, int top)

 {

     chain[x] = ++chTot, cnVal[chTot] = d[x], a[x].top = top;

     if (a[x].son==-) return;

     dfs2(a[x].son, top);

     for (int i=head[x]; i!=-; i=nxt[i])

     {

         int v = edges[i];

         if (v!=a[x].son&&v!=a[x].fa) dfs2(v, v);

     }

 }

 void modify(int rt, int l, int r, int pos, int c)

 {

     if (l==r){

         f[rt][] = f[rt][] = c;

         return;

     }

     int mid = (l+r)>>;

     if (pos <= mid) modify(rt<<, l, mid, pos, c);

     else modify(rt<<|, mid+, r, pos, c);

     pushup(rt);

 }

 int queryMx(int rt, int L, int R, int l, int r)

 {

     if (L <= l&&r <= R) return f[rt][];

     int mid = (l+r)>>, ret = -INF;

     if (L <= mid) ret = queryMx(rt<<, L, R, l, mid);

     if (R > mid) ret = std::max(ret, queryMx(rt<<|, L, R, mid+, r));

     return ret;

 }

 int querySm(int rt, int L, int R, int l, int r)

 {

     if (L <= l&&r <= R) return f[rt][];

     int mid = (l+r)>>, ret = ;

     if (L <= mid) ret = querySm(rt<<, L, R, l, mid);

     if (R > mid) ret += querySm(rt<<|, L, R, mid+, r);

     return ret;

 }

 int queryChainMx(int x, int y)

 {

     int ret = -INF;

     while (a[x].top!=a[y].top)

     {

         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);

         ret = std::max(ret, queryMx(, chain[a[y].top], chain[y], , n));

         y = a[a[y].top].fa;

     }

     if (dep[x] > dep[y]) std::swap(x, y);

     ret = std::max(ret, queryMx(, chain[x], chain[y], , n));

     return ret;

 }

 int queryChainSm(int x, int y)

 {

     int ret = ;

     while (a[x].top!=a[y].top)

     {

         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);

         ret += querySm(, chain[a[y].top], chain[y], , n);

         y = a[a[y].top].fa;

     }

     if (dep[x] > dep[y]) std::swap(x, y);

     ret += querySm(, chain[x], chain[y], , n);

     return ret;

 }

 int main()

 {

     memset(head, -, sizeof head);

     n = read();

     for (int i=; i<n; i++) addedge(read(), read());

     for (int i=; i<=n; i++) d[i] = read();

     dfs1(, );

     dfs2(, );

     build(, , n);

     m = read();

     while (m--)

     {

         scanf("%s",opt);

         int x = read(), y = read();

         if (opt[]=='C') modify(, , n, chain[x], y);

         else if (opt[]=='M')

             printf("%d\n",queryChainMx(x, y));

         else printf("%d\n",queryChainSm(x, y));

     }

     return ;

 }

打挂地方已标注。

边-树链剖分「bzoj2238: Mst」

10.28

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 const int INF = 0x3f3f3f3f;

 struct Edge

 {

     int u,v,w,id;

     bool vis;

     Edge(int a=, int b=, int c=):u(a),v(b),w(c) {}

 }ev[maxm],edges[maxm];

 struct node

 {

     int tot,son,top,fa;

 }a[maxn];

 int n,m,q,cnt,ans;

 int dep[maxn],fa[maxn],chain[maxn],chTot,f[maxn<<];

 int edgeTot,head[maxn],nxt[maxm];

 bool evis[maxm];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 bool cmp1(Edge a, Edge b)

 {

     return a.w < b.w;

 }

 bool cmp2(Edge a, Edge b)

 {

     return a.id < b.id;

 }

 int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}

 void addedge(int u, int v, int c)

 {

     ans += c, fa[fa[u]] = fa[v];

     edges[++edgeTot] = Edge(u, v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;

     edges[++edgeTot] = Edge(v, u, c), nxt[edgeTot] = head[v], head[v] = edgeTot;

 }

 void dfs1(int x, int fa)

 {

     a[x].tot = , a[x].son = a[x].top = -;

     a[x].fa = fa, dep[x] = dep[fa]+;

     for (int i=head[x]; i!=-; i=nxt[i])

     {

         int v = edges[i].v;

         if (v!=fa){

             dfs1(v, x), a[x].tot += a[v].tot;

             if (a[x].son==-||a[a[x].son].tot < a[v].tot) a[x].son = v;

         }

     }

 }

 void dfs2(int x, int top)

 {

     a[x].top = top, chain[x] = ++chTot;

     if (a[x].son==-) return;

     dfs2(a[x].son, top);

     for (int i=head[x]; i!=-; i=nxt[i])

     {

         int v = edges[i].v;

         if (v!=a[x].son&&v!=a[x].fa) dfs2(v, v);

     }

 }

 void build(int rt, int l, int r)

 {

     f[rt] = INF;

     if (l==r) return;

     int mid = (l+r)>>;

     build(rt<<, l, mid), build(rt<<|, mid+, r);

 }

 void Min(int &x, int y){x = x>y?y:x;}

 void pushdown(int rt)

 {

     Min(f[rt<<], f[rt]), Min(f[rt<<|], f[rt]);

 }

 void modify(int rt, int L, int R, int l, int r, int c)

 {

     if (L > R) return;

     if (L <= l&&r <= R){

         f[rt] = std::min(f[rt], c);

         return;

     }

     int mid = (l+r)>>;

     pushdown(rt);

     if (L <= mid) modify(rt<<, L, R, l, mid, c);

     if (R > mid) modify(rt<<|, L, R, mid+, r, c);

 }

 int query(int rt, int L, int R, int l, int r)

 {

     if (L > R) return INF;

     if (L <= l&&r <= R) return f[rt];

     int mid = (l+r)>>, ret = INF;

     pushdown(rt);

     if (L <= mid) Min(ret, query(rt<<, L, R, l, mid));

     if (R > mid) Min(ret, query(rt<<|, L, R, mid+, r));

     return ret;

 }

 void modifyChain(int x, int y, int c)

 {

     while (a[x].top!=a[y].top)

     {

         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);

         modify(, chain[a[y].top], chain[y], , n, c);

         y = a[a[y].top].fa;

     }

     if (dep[x] > dep[y]) std::swap(x, y);

     modify(, chain[x]+, chain[y], , n, c);

 }

 int queryChain(int x, int y)

 {

     int ret = INF;

     while (a[x].top!=a[y].top)

     {

         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);

         Min(ret, query(, chain[a[y].top], chain[y], , n));

         y = a[a[y].top].fa;

     }

     if (dep[x] > dep[y]) std::swap(x, y);

     Min(ret, query(, chain[x]+, chain[y], , n));

     return ret;

 }

 int main()

 {

     memset(head, -, sizeof head);

     n = read(), m = read();

     for (int i=; i<=n; i++) fa[i] = i;

     for (int i=; i<=m; i++)

         ev[i].u = read(), ev[i].v = read(), ev[i].w = read(), ev[i].id = i;

     std::sort(ev+, ev+m+, cmp1);

     for (int i=; i<=m; i++)

         if (get(ev[i].u)!=get(ev[i].v)){

             int u = ev[i].u, v = ev[i].v;

             ev[i].vis = evis[ev[i].id] = , cnt++, addedge(u, v, ev[i].w);

             if (cnt==n-) break;

         }

     if (cnt!=n-){

         q = read();

         while (q--) puts("Not connected");

         return ;

     }

     dfs1(, );

     dfs2(, );

     build(, , n);

     for (int i=m; i; i--)

         if (!ev[i].vis) modifyChain(ev[i].u, ev[i].v, ev[i].w);

     std::sort(ev+, ev+m+, cmp2);

     for (q=read(); q; q--)

     {

         int cse = read();

         if (!evis[cse]) printf("%d\n",ans);

         else{

             int cnt = queryChain(ev[cse].u, ev[cse].v);

             if (cnt!=INF) printf("%d\n",ans-ev[cse].w+cnt);

             else puts("Not connected");

         }

     }

     return ;

 }

evis开成maxn一发RE

SPFA负权环「bzoj1715: [Usaco2006 Dec]Wormholes 虫洞」

10.24.2018

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 struct Edge

 {

     int y,val;

     Edge(int a=, int b=):y(a),val(b) {}

 }edges[maxm];

 int T,n,m,w;

 bool vis[maxn];

 int dis[maxn],edgeTot,head[maxn],nxt[maxm];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void addedge(int u, int v, int c)

 {

     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;

 }

 bool dfs(int x)

 {

     vis[x] = ;

     for (int i=head[x]; i!=-; i=nxt[i])

     {

         int v = edges[i].y;

         if (dis[v] > dis[x]+edges[i].val){

             dis[v] = dis[x]+edges[i].val;

             if (vis[v]||dfs(v)){

                 vis[x] = ;

                 return ;

             }

         }

     }

     vis[x] = ;

     return ;

 }

 int main()

 {

     T = read();

     while (T--)

     {

         memset(head, -, sizeof head);

         memset(dis, , sizeof dis);

         edgeTot = , n = read(), m = read(), w = read();

         for (int i=; i<=m; i++)

         {

             int u = read(), v = read(), c = read();

             addedge(u, v, c), addedge(v, u, c);

         }

         for (int i=; i<=w; i++)

         {

             int u = read(), v = read(), c = read();

             addedge(u, v, -c);

         }

         bool fl = ;

         for (int i=; i<=n; i++)

             if (dfs(i)){

                 puts("YES"), fl = ;

                 break;

             }

         if (!fl) puts("NO");

     }

     return ;

 }

差分约束「poj1201Intervals」

10.26.2018

这个和线性规划相比，要把式子全都化成三角形不等式的形式。

所以小于等于或者大于等于的两种情况自己注意。

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 struct Edge

 {

     int y,val;

     Edge(int a=, int b=):y(a),val(b) {}

 }edges[maxm];

 int n,mx;

 bool stk[maxn];

 std::queue<int> q;

 int dis[maxn],vis[maxn];

 int edgeTot,head[maxn],nxt[maxm];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void addedge(int u, int v, int c)

 {

     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;

 }

 void spfa()

 {

     memset(dis, -0x3f3f3f3f, sizeof dis);

     dis[] = , q.push();

     while (q.size())

     {

         int tt = q.front();

         q.pop(), stk[tt] = ;

         for (int i=head[tt]; i!=-; i=nxt[i])

         {

             int v = edges[i].y, w = edges[i].val;

             if (dis[v] < dis[tt]+w){

                 dis[v] = dis[tt]+w;

                 if (!stk[v]) stk[v] = , q.push(v);

             }

         }

     }

 }

 int main()

 {

     memset(head, -, sizeof head);

     n = read();

     for (int i=; i<=n; i++)

     {

         int a = read()+, b = read()+, c = read();

         mx = std::max(mx, b);

         addedge(a-, b, c);

     }

     for (int i=; i<mx; i++) addedge(i, i+, ), addedge(i+, i, -);

     spfa();

     printf("%d\n",dis[mx]);

     return ;

 }

≥

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 struct Edge

 {

     int y,val;

     Edge(int a=, int b=):y(a),val(b) {}

 }edges[maxm];

 int n,mx;

 bool stk[maxn];

 std::queue<int> q;

 int dis[maxn],vis[maxn];

 int edgeTot,head[maxn],nxt[maxm];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void addedge(int u, int v, int c)

 {

     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;

 }

 void spfa()

 {

     memset(dis, 0x3f3f3f3f, sizeof dis);

     dis[mx] = , q.push(mx);

     while (q.size())

     {

         int tt = q.front();

         q.pop(), stk[tt] = ;

         for (int i=head[tt]; i!=-; i=nxt[i])

         {

             int v = edges[i].y, w = edges[i].val;

             if (dis[v] > dis[tt]+w){

                 dis[v] = dis[tt]+w;

                 if (!stk[v]) stk[v] = , q.push(v);

             }

         }

     }

 }

 int main()

 {

     memset(head, -, sizeof head);

     n = read();

     for (int i=; i<=n; i++)

     {

         int a = read()+, b = read()+, c = read();

         mx = std::max(mx, b);

         addedge(b, a-, -c);

     }

     for (int i=; i<mx; i++) addedge(i, i+, ), addedge(i+, i, );

     spfa();

     printf("%d\n",-dis[]);

     return ;

 }

≤

点树上差分「bzoj4390: [Usaco2015 dec]Max Flow」

11.5.2018

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 const int maxLog = ;

 int n,m;

 int f[maxn][maxLog],sum[maxn],ans;

 int edgeTot,head[maxn],edges[maxm],nxt[maxm],dep[maxn];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void addedge(int u, int v)

 {

     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;

     edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;

 }

 void dfs(int x, int fa)

 {

     f[x][] = fa, dep[x] = dep[fa]+;

     for (int i=head[x]; i!=-; i=nxt[i])

         if (edges[i]!=fa) dfs(edges[i], x);

 }

 int lca(int u, int v)

 {

     if (dep[u] > dep[v]) std::swap(u, v);

     for (int i=; i>=; i--)

         if (dep[u] <= dep[v]-(<<i))

             v = f[v][i];

     if (u==v) return u;

     for (int i=; i>=; i--)

         if (f[u][i]!=f[v][i])

             u = f[u][i], v = f[v][i];

     return f[u][];

 }

 void fnd(int x)

 {

     for (int i=head[x]; i!=-; i=nxt[i])

         if (edges[i]!=f[x][])

             fnd(edges[i]), sum[x] += sum[edges[i]];

     if (ans < sum[x]) ans = sum[x];

 }

 int main()

 {

     memset(head, -, sizeof head);

     n = read(), m = read();

     for (register int i=; i<n; i++) addedge(read(), read());

     dfs(, );

     for (register int j=; j<=; j++)

         for (register int i=; i<=n; i++)

             f[i][j] = f[f[i][j-]][j-];

     for (register int i=; i<=m; i++)

     {

         register int u = read(), v = read(), ger = lca(u, v);

         sum[u]++, sum[v]++, sum[ger]--, sum[f[ger][]]--;

     }

     fnd();

     printf("%d\n",ans);

     return ;

 }

最新文章

  1. sphinx搜索实例
  2. PHPCMS_v9 wap不同列表采用不同模板的方法
  3. [Linux] 查看系统启动时间
  4. C#常用类汇总
  5. mysql 监控工具monyog使用总结
  6. PLSQL Developer Debug
  7. spring 基于XML和注解的两种事务配置方式
  8. C# checked和unchecked详解
  9. 高仿二次元网易GACHA
  10. python3 第十章 - 如何进行进制转化
  11. 从零开始搭建django前后端分离项目 系列二（项目搭建）
  12. OPENQUERY (Transact-SQL)
  13. 日常英语---八、REBOOT - What is the difference? -MapleStory
  14. double
  15. 洛谷.1110.[ZJOI2007]报表统计(Multiset Heap)
  16. CentOS7 彻底关闭 IPV6
  17. 【kuangbin专题】计算几何基础
  18. 开源作业调度框架 - Quartz.NET - 实战使用2
  19. 标准API使用小技巧
  20. shell中交互输入自动化

热门文章

  1. SpringMVC入门 bug集锦X3和SSM原始整合
  2. PAT甲级——1107 Social Clusters (并查集)
  3. IOS字符串截取保留小数点后两位
  4. shell中括号总结: {}, (), (()), [], [[]]
  5. NET Core 2.0 使用支付宝
  6. keil-rtx
  7. 朱晔的互联网架构实践心得S2E7:漫谈平台架构的工作（基础架构、基础服务、基础平台、基础中间件等等）
  8. Git 忽略規則及 .gitignore 規則不生效的辦法
  9. 《移动Web前端高效开发实战》笔记3--代码检查任务
  10. ECSHOP 商品增加新字段的方法