好多东西都不熟练……

 

数论

数论分块「」

10.28.2018

1 #include
      
        2 typedef long long ll; 3 const int MO = 19940417; 4 const int inv6 = 3323403; 5  6 ll n,m,ans,del; 7  8 inline void Add(ll &x, ll y){x = ((x+y)%MO+MO)%MO;} 9 ll sum(ll x){
    return x*(x+1)%MO*(2*x+1)%MO*inv6%MO;}10 ll calc(ll x)11 {12     ll ret = 0;13     for (ll i=1, j=0; i<=x; i=j+1)14     {15         j = x/(x/i);16         Add(ret, 1ll*(x/i)*(i+j)*(j-i+1)/2%MO);17     }18     return ((x%MO*x%MO-ret)+MO)%MO;19 }20 int main()21 {22     scanf("%lld%lld",&n,&m);23     if (n > m) std::swap(n, m);24     ans = calc(n)*calc(m)%MO;25     del = n*m%MO*n%MO;26     for (ll i=1, j=0; i<=n; i=j+1)27     {28         j = std::min(n/(n/i), m/(m/i));29         ll s1 = (sum(j)-sum(i-1))*(n/i)%MO*(m/i)%MO;30         ll s2 = (n*(m/i)%MO+m*(n/i)%MO)%MO*((i+j)*(j-i+1)/2%MO);31         Add(del, (s1-s2)%MO);32     }33     Add(ans, -del);34     printf("%lld\n",ans);35     return 0;36 }
      

图论

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

10.24.2018

1 #include
     
        2 const int maxn = 30035;  3 const int maxm = 60035;  4 const int INF = 0x3f3f3f3f;  5   6 struct node  7 {  8     int tot,fa,son,top;  9 }a[maxn]; 10 int n,m; 11 char opt[13]; 12 int f[maxn<<2][2]; 13 int chTot,chain[maxn],cnVal[maxn],d[maxn],dep[maxn]; 14 int edgeTot,head[maxn],nxt[maxm],edges[maxm]; 15  16 int read() 17 { 18     char ch = getchar(); 19     int num = 0; 20     bool fl = 0; 21     for (; !isdigit(ch); ch=getchar()) 22         if (ch=='-') fl = 1; 23     for (; isdigit(ch); ch=getchar()) 24         num = (num<<1)+(num<<3)+ch-48; 25     if (fl) num = -num; 26     return num; 27 } 28 void addedge(int u, int v) 29 { 30     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot; 31     edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot; 32 } 33 void pushup(int rt) 34 { 35     f[rt][1] = std::max(f[rt<<1][1], f[rt<<1|1][1]); 36     f[rt][0] = f[rt<<1][0]+f[rt<<1|1][0]; 37 } 38 void build(int rt, int l, int r) 39 { 40     f[rt][1] = -INF; 41     if (l==r){ 42         f[rt][1] = f[rt][0] = cnVal[l]; 43         return; 44     } 45     int mid = (l+r)>>1; 46     build(rt<<1, l, mid), build(rt<<1|1, mid+1, r); 47     pushup(rt); 48 } 49 void dfs1(int x, int fa) 50 { 51     a[x].fa = fa, a[x].tot = 1; 52     dep[x] = dep[fa]+1, a[x].son = -1; 53     for (int i=head[x]; i!=-1; i=nxt[i]) 54     { 55         int v = edges[i]; 56         if (v!=fa){ 57             dfs1(v, x); 58             a[x].tot += a[v].tot; 59             if (a[x].son==-1||a[v].tot > a[a[x].son].tot) 60                 a[x].son = v; 61         } 62     } 63 } 64 void dfs2(int x, int top) 65 { 66     chain[x] = ++chTot, cnVal[chTot] = d[x], a[x].top = top; 67     if (a[x].son==-1) return; 68     dfs2(a[x].son, top); 69     for (int i=head[x]; i!=-1; i=nxt[i]) 70     { 71         int v = edges[i]; 72         if (v!=a[x].son&&v!=a[x].fa) dfs2(v, v); 73     } 74 } 75 void modify(int rt, int l, int r, int pos, int c) 76 { 77     if (l==r){ 78         f[rt][0] = f[rt][1] = c; 79         return; 80     } 81     int mid = (l+r)>>1; 82     if (pos <= mid) modify(rt<<1, l, mid, pos, c); 83     else modify(rt<<1|1, mid+1, r, pos, c); 84     pushup(rt); 85 } 86 int queryMx(int rt, int L, int R, int l, int r) 87 { 88     if (L <= l&&r <= R) return f[rt][1]; 89     int mid = (l+r)>>1, ret = -INF; 90     if (L <= mid) ret = queryMx(rt<<1, L, R, l, mid); 91     if (R > mid) ret = std::max(ret, queryMx(rt<<1|1, L, R, mid+1, r)); 92     return ret; 93 } 94 int querySm(int rt, int L, int R, int l, int r) 95 { 96     if (L <= l&&r <= R) return f[rt][0]; 97     int mid = (l+r)>>1, ret = 0; 98     if (L <= mid) ret = querySm(rt<<1, L, R, l, mid);  99     if (R > mid) ret += querySm(rt<<1|1, L, R, mid+1, r);100     return ret;101 }102 int queryChainMx(int x, int y)103 {104     int ret = -INF;105     while (a[x].top!=a[y].top)106     {107         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);108         ret = std::max(ret, queryMx(1, chain[a[y].top], chain[y], 1, n));109         y = a[a[y].top].fa;110     }111     if (dep[x] > dep[y]) std::swap(x, y);112     ret = std::max(ret, queryMx(1, chain[x], chain[y], 1, n));113     return ret;114 }115 int queryChainSm(int x, int y)116 {117     int ret = 0;118     while (a[x].top!=a[y].top)119     {120         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);121         ret += querySm(1, chain[a[y].top], chain[y], 1, n);122         y = a[a[y].top].fa;123     }124     if (dep[x] > dep[y]) std::swap(x, y);125     ret += querySm(1, chain[x], chain[y], 1, n);126     return ret;127 }128 int main()129 {130     memset(head, -1, sizeof head);131     n = read();132     for (int i=1; i
     

打挂地方已标注。

边-树链剖分「bzoj2238: Mst」

10.28

1 #include
      
         2 const int maxn = 50035;  3 const int maxm = 100035;  4 const int INF = 0x3f3f3f3f;  5   6 struct Edge  7 {  8     int u,v,w,id;  9     bool vis; 10     Edge(int a=0, int b=0, int c=0):u(a),v(b),w(c) {} 11 }ev[maxm],edges[maxm]; 12 struct node 13 { 14     int tot,son,top,fa; 15 }a[maxn]; 16 int n,m,q,cnt,ans; 17 int dep[maxn],fa[maxn],chain[maxn],chTot,f[maxn<<2]; 18 int edgeTot,head[maxn],nxt[maxm]; 19 bool evis[maxm]; 20  21 int read() 22 { 23     char ch = getchar(); 24     int num = 0; 25     bool fl = 0; 26     for (; !isdigit(ch); ch=getchar()) 27         if (ch=='-') fl = 1; 28     for (; isdigit(ch); ch=getchar()) 29         num = (num<<1)+(num<<3)+ch-48; 30     if (fl) num = -num; 31     return num; 32 } 33 bool cmp1(Edge a, Edge b) 34 { 35     return a.w < b.w; 36 } 37 bool cmp2(Edge a, Edge b) 38 { 39     return a.id < b.id; 40 } 41 int get(int x){
    return x==fa[x]?x:fa[x]=get(fa[x]);} 42 void addedge(int u, int v, int c) 43 { 44     ans += c, fa[fa[u]] = fa[v]; 45     edges[++edgeTot] = Edge(u, v, c), nxt[edgeTot] = head[u], head[u] = edgeTot; 46     edges[++edgeTot] = Edge(v, u, c), nxt[edgeTot] = head[v], head[v] = edgeTot; 47 } 48 void dfs1(int x, int fa) 49 { 50     a[x].tot = 1, a[x].son = a[x].top = -1; 51     a[x].fa = fa, dep[x] = dep[fa]+1; 52     for (int i=head[x]; i!=-1; i=nxt[i]) 53     { 54         int v = edges[i].v; 55         if (v!=fa){ 56             dfs1(v, x), a[x].tot += a[v].tot; 57             if (a[x].son==-1||a[a[x].son].tot < a[v].tot) a[x].son = v; 58         } 59     } 60 } 61 void dfs2(int x, int top) 62 { 63     a[x].top = top, chain[x] = ++chTot; 64     if (a[x].son==-1) return; 65     dfs2(a[x].son, top); 66     for (int i=head[x]; i!=-1; i=nxt[i]) 67     { 68         int v = edges[i].v; 69         if (v!=a[x].son&&v!=a[x].fa) dfs2(v, v); 70     } 71 } 72 void build(int rt, int l, int r) 73 { 74     f[rt] = INF; 75     if (l==r) return; 76     int mid = (l+r)>>1; 77     build(rt<<1, l, mid), build(rt<<1|1, mid+1, r); 78 } 79 void Min(int &x, int y){x = x>y?y:x;} 80 void pushdown(int rt) 81 { 82     Min(f[rt<<1], f[rt]), Min(f[rt<<1|1], f[rt]); 83 } 84 void modify(int rt, int L, int R, int l, int r, int c) 85 { 86     if (L > R) return; 87     if (L <= l&&r <= R){ 88         f[rt] = std::min(f[rt], c); 89         return; 90     } 91     int mid = (l+r)>>1; 92     pushdown(rt); 93     if (L <= mid) modify(rt<<1, L, R, l, mid, c); 94     if (R > mid) modify(rt<<1|1, L, R, mid+1, r, c); 95 } 96 int query(int rt, int L, int R, int l, int r) 97 { 98     if (L > R) return INF; 99     if (L <= l&&r <= R) return f[rt];100     int mid = (l+r)>>1, ret = INF;101     pushdown(rt);102     if (L <= mid) Min(ret, query(rt<<1, L, R, l, mid));103     if (R > mid) Min(ret, query(rt<<1|1, L, R, mid+1, r));104     return ret;105 }106 void modifyChain(int x, int y, int c)107 {108     while (a[x].top!=a[y].top)109     {110         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);111         modify(1, chain[a[y].top], chain[y], 1, n, c);112         y = a[a[y].top].fa;113     }114     if (dep[x] > dep[y]) std::swap(x, y);115     modify(1, chain[x]+1, chain[y], 1, n, c);116 }117 int queryChain(int x, int y)118 {119     int ret = INF;120     while (a[x].top!=a[y].top)121     {122         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);123         Min(ret, query(1, chain[a[y].top], chain[y], 1, n));124         y = a[a[y].top].fa;125     }126     if (dep[x] > dep[y]) std::swap(x, y);127     Min(ret, query(1, chain[x]+1, chain[y], 1, n));128     return ret;129 }130 int main()131 {132     memset(head, -1, sizeof head);133     n = read(), m = read();134     for (int i=1; i<=n; i++) fa[i] = i;135     for (int i=1; i<=m; i++)136         ev[i].u = read(), ev[i].v = read(), ev[i].w = read(), ev[i].id = i;137     std::sort(ev+1, ev+m+1, cmp1);138     for (int i=1; i<=m; i++)139         if (get(ev[i].u)!=get(ev[i].v)){140             int u = ev[i].u, v = ev[i].v;141             ev[i].vis = evis[ev[i].id] = 1, cnt++, addedge(u, v, ev[i].w);142             if (cnt==n-1) break;143         }144     if (cnt!=n-1){145         q = read();146         while (q--) puts("Not connected");147         return 0;148     }149     dfs1(1, 0);150     dfs2(1, 1);151     build(1, 1, n);152     for (int i=m; i; i--)153         if (!ev[i].vis) modifyChain(ev[i].u, ev[i].v, ev[i].w);154     std::sort(ev+1, ev+m+1, cmp2);155     for (q=read(); q; q--)156     {157         int cse = read();158         if (!evis[cse]) printf("%d\n",ans);159         else{160             int cnt = queryChain(ev[cse].u, ev[cse].v);161             if (cnt!=INF) printf("%d\n",ans-ev[cse].w+cnt);162             else puts("Not connected");163         }164     }165     return 0;166 }
      

evis开成maxn一发RE

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

10.24.2018

1 #include
      
        2 const int maxn = 503; 3 const int maxm = 6003; 4  5 struct Edge 6 { 7     int y,val; 8     Edge(int a=0, int b=0):y(a),val(b) {} 9 }edges[maxm];10 int T,n,m,w;11 bool vis[maxn];12 int dis[maxn],edgeTot,head[maxn],nxt[maxm];13 14 int read()15 {16     char ch = getchar();17     int num = 0;18     bool fl = 0;19     for (; !isdigit(ch); ch=getchar())20         if (ch=='-') fl = 1;21     for (; isdigit(ch); ch=getchar())22         num = (num<<1)+(num<<3)+ch-48;23     if (fl) num = -num;24     return num;25 }26 void addedge(int u, int v, int c)27 {28     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;29 }30 bool dfs(int x)31 {32     vis[x] = 1;33     for (int i=head[x]; i!=-1; i=nxt[i])34     {35         int v = edges[i].y;36         if (dis[v] > dis[x]+edges[i].val){37             dis[v] = dis[x]+edges[i].val;38             if (vis[v]||dfs(v)){39                 vis[x] = 0;40                 return 1;41             }42         }43     }44     vis[x] = 0;45     return 0;46 }47 int main()48 {49     T = read();50     while (T--)51     {52         memset(head, -1, sizeof head);53         memset(dis, 0, sizeof dis);54         edgeTot = 0, n = read(), m = read(), w = read();55         for (int i=1; i<=m; i++)56         {57             int u = read(), v = read(), c = read();58             addedge(u, v, c), addedge(v, u, c);59         }60         for (int i=1; i<=w; i++)61         {62             int u = read(), v = read(), c = read();63             addedge(u, v, -c);64         }65         bool fl = 0;66         for (int i=1; i<=n; i++)67             if (dfs(i)){68                 puts("YES"), fl = 1;69                 break;70             }71         if (!fl) puts("NO");        72     }73     return 0;74 }
      

差分约束「poj1201Intervals」

10.26.2018

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

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

1 #include
      
        2 const int maxn = 50035; 3 const int maxm = 200035; 4  5 struct Edge 6 { 7     int y,val; 8     Edge(int a=0, int b=0):y(a),val(b) {} 9 }edges[maxm];10 int n,mx;11 bool stk[maxn];12 std::queue
       
         q;13 int dis[maxn],vis[maxn];14 int edgeTot,head[maxn],nxt[maxm];15 16 int read()17 {18     char ch = getchar();19     int num = 0;20     bool fl = 0;21     for (; !isdigit(ch); ch=getchar())22         if (ch=='-') fl = 1;23     for (; isdigit(ch); ch=getchar())24         num = (num<<1)+(num<<3)+ch-48;25     if (fl) num = -num;26     return num;27 }28 void addedge(int u, int v, int c)29 {30     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;31 }32 void spfa()33 {34     memset(dis, -0x3f3f3f3f, sizeof dis);35     dis[0] = 0, q.push(0);36     while (q.size())37     {38         int tt = q.front();39         q.pop(), stk[tt] = 0;40         for (int i=head[tt]; i!=-1; i=nxt[i])41         {42             int v = edges[i].y, w = edges[i].val;43             if (dis[v] < dis[tt]+w){44                 dis[v] = dis[tt]+w;45                 if (!stk[v]) stk[v] = 1, q.push(v);46             }47         }48     }49 }50 int main()51 {52     memset(head, -1, sizeof head);53     n = read();54     for (int i=1; i<=n; i++)55     {56         int a = read()+1, b = read()+1, c = read();57         mx = std::max(mx, b);58         addedge(a-1, b, c);59     }60     for (int i=0; i
       
      

1 #include
      
        2 const int maxn = 50035; 3 const int maxm = 200035; 4  5 struct Edge 6 { 7     int y,val; 8     Edge(int a=0, int b=0):y(a),val(b) {} 9 }edges[maxm];10 int n,mx;11 bool stk[maxn];12 std::queue
       
         q;13 int dis[maxn],vis[maxn];14 int edgeTot,head[maxn],nxt[maxm];15 16 int read()17 {18     char ch = getchar();19     int num = 0;20     bool fl = 0;21     for (; !isdigit(ch); ch=getchar())22         if (ch=='-') fl = 1;23     for (; isdigit(ch); ch=getchar())24         num = (num<<1)+(num<<3)+ch-48;25     if (fl) num = -num;26     return num;27 }28 void addedge(int u, int v, int c)29 {30     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;31 }32 void spfa()33 {34     memset(dis, 0x3f3f3f3f, sizeof dis);35     dis[mx] = 0, q.push(mx);36     while (q.size())37     {38         int tt = q.front();39         q.pop(), stk[tt] = 0;40         for (int i=head[tt]; i!=-1; i=nxt[i])41         {42             int v = edges[i].y, w = edges[i].val;43             if (dis[v] > dis[tt]+w){44                 dis[v] = dis[tt]+w;45                 if (!stk[v]) stk[v] = 1, q.push(v);46             }47         }48     }49 }50 int main()51 {52     memset(head, -1, sizeof head);53     n = read();54     for (int i=1; i<=n; i++)55     {56         int a = read()+1, b = read()+1, c = read();57         mx = std::max(mx, b);58         addedge(b, a-1, -c);59     }60     for (int i=0; i
       
      

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

11.5.2018

1 #include
      
        2 const int maxn = 50035; 3 const int maxm = 100035; 4 const int maxLog = 23; 5  6 int n,m; 7 int f[maxn][maxLog],sum[maxn],ans; 8 int edgeTot,head[maxn],edges[maxm],nxt[maxm],dep[maxn]; 9 10 int read()11 {12     char ch = getchar();13     int num = 0;14     bool fl = 0;15     for (; !isdigit(ch); ch=getchar())16         if (ch=='-') fl = 1;17     for (; isdigit(ch); ch=getchar())18         num = (num<<1)+(num<<3)+ch-48;19     if (fl) num = -num;20     return num;21 }22 void addedge(int u, int v)23 {24     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;25     edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;26 }27 void dfs(int x, int fa)28 {29     f[x][0] = fa, dep[x] = dep[fa]+1;30     for (int i=head[x]; i!=-1; i=nxt[i])31         if (edges[i]!=fa) dfs(edges[i], x);32 }33 int lca(int u, int v)34 {35     if (dep[u] > dep[v]) std::swap(u, v);36     for (int i=20; i>=0; i--)37         if (dep[u] <= dep[v]-(1<
       
        =0; i--)41         if (f[u][i]!=f[v][i])42             u = f[u][i], v = f[v][i];43     return f[u][0];44 }45 void fnd(int x)46 {47     for (int i=head[x]; i!=-1; i=nxt[i])48         if (edges[i]!=f[x][0])49             fnd(edges[i]), sum[x] += sum[edges[i]];50     if (ans < sum[x]) ans = sum[x];51 }52 int main()53 {54     memset(head, -1, sizeof head);55     n = read(), m = read();56     for (register int i=1; i