2018年12月30&31日

小结：昨天由于做的题目比较少，所以就和今天写在一块了，昨天学习了差分约束和树上差分，当然树上差分是用线段树来维护的，今天重点整理了博客\(233\)，然后做了几个题。

一. 完成的题目：

洛谷P3275，洛谷P4878，洛谷P2294，洛谷P3258，洛谷P3038，洛谷P1262，洛谷P5159，洛谷P4113

二.

1.当日完成题目数：8道。

2. 未完成6个题目的原因：

3. 复习的知识点：树链剖分，线段树，差分约束，tarjan，数论，树状数组

4.不会题目：洛谷P5160

三：

1. 洛谷P3275 [SCOI2011]糖果

题目描述

幼儿园里有\(N\)个小朋友，\(lxhgww\)老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，\(lxhgww\)需要满足小朋友们的\(K\)个要求。幼儿园的糖果总是有限的，\(lxhgww\)想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入输出格式

输入格式：

输入的第一行是两个整数\(N\)，\(K\)。接下来K行，表示这些点需要满足的关系，每行\(3\)个数字，\(X\)，\(A\)，\(B\)。如果\(X=1\)， 表示第\(A\)个小朋友分到的糖果必须和第\(B\)个小朋友分到的糖果一样多；如果\(X=2\)， 表示第\(A\)个小朋友分到的糖果必须少于第\(B\)个小朋友分到的糖果；如果\(X=3\)， 表示第\(A\)个小朋友分到的糖果必须不少于第\(B\)个小朋友分到的糖果；如果\(X=4\)， 表示第\(A\)个小朋友分到的糖果必须多于第\(B\)个小朋友分到的糖果；如果\(X=5\)， 表示第\(A\)个小朋友分到的糖果必须不多于第\(B\)个小朋友分到的糖果；

输出格式：

输出一行，表示\(lxhgww\)老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出\(-1\)。

输入输出样例

输入样例#1：

5 7

1 1 2

2 3 2

4 4 1

3 4 5

5 4 5

2 3 5

4 5 1

输出样例#1：

11

说明

【数据范围】

对于\(30\%\)的数据，保证 \(N \leq 100\)

对于\(100\%\)的数据，保证 \(N \leq 100000\)

对于所有的数据，保证 \(K \leq 100000\)，\(1 \leq X \leq 5\)，\(1 \leq A, B \leq N\)

思路：考虑差分约束，对于给出的第一种关系，我们就建一条双向的边权为\(0\)的边，然后第二种情况，\(A\)比\(B\)小，而且要严格小于，那就相当于是\(d[B]-d[A]>=1\)，然后剩余的三种就跟前两种类似了，就不必多说了，然后跑最短路的时候，我们以\(0\)为起点，向其它的点建一条权值为\(0\)的边，然后无解就是存在负环或建边的时候起点等于终点。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<queue>

#define ll long long

#define maxn 100007

using namespace std;

int num,n,k,head[maxn],dis[maxn],vis[maxn],in[maxn];

ll ans;

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

struct node {

  int v,w,nxt;

}e[300007];

inline void ct(int u, int v, int w) {

  e[++num].v=v;

  e[num].w=w;

  e[num].nxt=head[u];

  head[u]=num;

}

inline int spfa() {

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

  queue<int>q;

  q.push(0),dis[0]=0,vis[0]=1,in[0]=1;

  while(!q.empty()) {

    int u=q.front();q.pop();

    vis[u]=0;

    for(int i=head[u];i;i=e[i].nxt) {

      int v=e[i].v;

      if(dis[v]<dis[u]+e[i].w) {

        dis[v]=dis[u]+e[i].w;

        if(!vis[v]) {

          vis[v]=1;

          in[v]++;

          if(in[v]>n) return -1;

          q.push(v);

        }

      }

    }

  }

  return 0;

}

int main() {

  n=qread(),k=qread();

  for(int i=1,p,u,v;i<=k;++i) {

    p=qread(),u=qread(),v=qread();

    if(p==1) ct(u,v,0),ct(v,u,0);

    if(p==2) {

      if(u==v) {

        printf("-1\n");

        return 0;

      }

      ct(u,v,1);

    }

    if(p==3) ct(v,u,0);

    if(p==4) {

      if(u==v) {

        printf("-1\n");

        return 0;

      }

      ct(v,u,1);

    }

    if(p==5) ct(u,v,0);

  }

  for(int i=n;i>=1;--i) ct(0,i,1);

  if(spfa()) {

    printf("-1\n");

    return 0;

  }

  for(int i=1;i<=n;++i) ans+=dis[i];

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

  return 0;

}

2. 洛谷P4878 [USACO05DEC]layout布局

题目描述

正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。\(FJ\) 有编号为 \(1\dots N\) 的 \(N\) 头奶牛 \((2\le N\le 1000)\)。开始时，奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 \(M_L\)​ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 \(M_D\)​ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 \((1≤M_L​, M_D\le 10^4)\)

请计算：如果满足上述所有条件，\(1\) 号奶牛和 \(N\) 号奶牛之间的距离最大为多少。

输入输出格式

输入格式

第一行：三个整数 \(N, M_L, M_D\)​，用空格分隔。

第 \(2\dots M_L+1\) 行：每行三个整数 \(A, B, D\)，用空格分隔，表示 \(A\) 号奶牛与 \(B\) 号奶牛之间的距离须 \(\le D\)。保证 \(1\le A<B\le N\), \(1\le D\le 10^6\).

第 \(M_L+2\dots M_L+M_D+1\) 行：每行三个整数 \(A, B, D\)，用空格分隔，表示 \(A\) 号奶牛与 \(B\) 号奶牛之间的距离须 \(\ge D\)。保证 \(1\le A<B\le N\), \(1\le D\le 10^6\).

输出格式

一行，一个整数。如果没有合法方案，输出 \(-1\). 如果有合法方案，但 \(1\) 号奶牛可以与 \(N\) 号奶牛相距无穷远，输出\(-2\). 否则，输出 \(1\) 号奶牛与 \(N\) 号奶牛间的最大距离。

输入输出样例

输入样例#1：

4 2 1

1 3 10

2 4 20

2 3 3

输出样例#1：

27

思路：

做这道题之前，大家应该先学习一下差分约束。

给大家推荐个博客：不是我的……

然后回到这个题目上来，首先这道题有负环的出现，那显然不能用\(dijkstra\)了，那就把解法锁定为\(spfa\)。

对于给出的前\(M_L\)种关系：

就是这个样子：\(d[B]-d[A] \leq D\)

后\(M_D\)种关系是：\(d[B]-d[A] \geq D\),即\(d[A]-d[B] \leq -D\)

那对于第一种关系，根据差分约束，我们需要建从\(A\)到\(B\)，边权为D的边，对于第二种关系，我们就需要建从\(B\)到\(A\)，边权为\(-D\)的边。

这样建完图跑直接调用\(spfa(1)\)就可以得\(70\)分了，那为什么不能\(AC\)

呢？

因为我们差分约束时的起点是\(0\)，所以我们要先跑一遍\(spfa(0)\),并建一条从0到\(i(1 \leq i \leq n)\)的边权为0的边，为什么呢？

难道不应该是\(d[0]-d[i] \leq 0\)么？这样不是应该从i到0的边么？但是，有没有想过，如果你这样建，那你以0为起点跑spfa有意义么？0没法到达任何一个点，所以，我们需要建一条从0到i的边的边权为0的边。这样这题就能AC啦！

自己整理的题解

下面是我丑陋(学长说的)的代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<cstring>

#include<queue>

#define maxn 1007

using namespace std;

int num,n,m,p,head[maxn],dis[maxn],vis[maxn],in[maxn];

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

struct node {

  int v,w,nxt;

}e[20007];

inline void ct(int u, int v, int w) {

  e[++num].v=v;

  e[num].w=w;

  e[num].nxt=head[u];

  head[u]=num;

}

const int inf=0x3f3f3f3f;

inline void spfa(int s) {

  memset(dis,0x3f,sizeof(dis));

  memset(vis,0,sizeof(vis));

  memset(in,0,sizeof(in));

  queue<int>q;

  q.push(s),vis[s]=1,in[s]=1;

  dis[s]=0;

  while(!q.empty()) {

    int u=q.front();

    q.pop();vis[u]=0;

    for(int i=head[u];i;i=e[i].nxt) {

      int v=e[i].v;

      if(dis[v]>dis[u]+e[i].w) {

        dis[v]=dis[u]+e[i].w;

        if(!vis[v]) {

          vis[v]=1;

          in[v]++;

          if(in[v]>n) {

            printf("-1\n");

            exit(0);

          }

          q.push(v);

        }

      }

    }

  }

}

int main() {

  n=qread(),m=qread(),p=qread();

  for(int i=1,u,v,d;i<=m;++i) {

    u=qread(),v=qread(),d=qread();

    ct(u,v,d);

  }

  for(int i=1,u,v,d;i<=p;++i) {

    u=qread(),v=qread(),d=qread();

    ct(v,u,-d);

  }

  for(int i=1;i<=n;++i) ct(0,i,0);

  spfa(0);

  spfa(1);

  if(dis[n]==inf) {

    printf("-2\n");

    return 0;

  }

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

  return 0;

}

3. 洛谷P2294 [HNOI2005]狡猾的商人

题目描述

输入输出格式

输入格式：

从文件\(input.txt\)中读入数据，文件第一行为一个正整数\(w\)，其中\(w < 100\)，表示有\(w\)组数据，即\(w\)个账本，需要你判断。每组数据的第一行为两个正整数\(n\)和\(m\)，其中\(n < 100，m < 1000\)，分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本。接下来的\(m\)行表示刁姹偷看\(m\)次账本后记住的\(m\)条信息，每条信息占一行，有三个整数\(s\)，\(t\)和\(v\)，表示从第\(s\)个月到第\(t\)个月（包含第\(t\)个月）的总收入为\(v\)，这里假设\(s\)总是小于等于\(t\)。

输出格式：

输出文件\(output.txt\)中包含\(w\)行,每行是\(true\)或\(false\),其中第\(i\)行为\(true\)当且仅当第\(i\)组数据，即第\(i\)个账本不是假的；第\(i\)行为\(false\)当且仅当第i组数据，即第\(i\)个账本是假的。

输入输出样例

输入样例#1：

2

3 3

1 2 10

1 3 -5

3 3 -15

5 3

1 5 100

3 5 50

1 2 51

输出样例#1：

true

false

思路：题目中的条件可以转化为\(v \leq d[t]-d[s] \leq v\)，这就是这个题目中唯一的约束条件，然后对于每组询问建边，跑\(spfa\)即可，如果说在第i组询问中存在负环，说明第\(i\)本账本是假的，输出\(false\)，否则输出\(true\)。

代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<cstring>

#include<queue>

#define maxn 100007

using namespace std;

int num,t,n,m,head[maxn],dis[maxn],vis[maxn],in[maxn];

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

struct node {

  int v,w,nxt;

}e[200007];

inline void ct(int u, int v, int w) {

  e[++num].v=v;

  e[num].w=w;

  e[num].nxt=head[u];

  head[u]=num;

}

inline bool spfa() {

  memset(dis,0x3f,sizeof(dis));

  memset(vis,0,sizeof(vis));

  memset(in,0,sizeof(in));

  queue<int>q;

  q.push(0),vis[0]=1,in[0]=1,dis[0]=0;

  while(!q.empty()) {

    int u=q.front();

    q.pop(),vis[u]=0;

    for(int i=head[u];i;i=e[i].nxt) {

      int v=e[i].v;

      if(dis[v]>dis[u]+e[i].w) {

        dis[v]=dis[u]+e[i].w;

        if(!vis[v]) {

          vis[v]=1;

          in[v]++;

          if(in[v]>n) return 1;

          q.push(v);

        }

      }

    }

  }

  return 0;

}

int main() {

  t=qread();

  while(t--) {

    n=qread(),m=qread();

    memset(head,0,sizeof(head));

    num=0;

    for(int i=1,u,v,w;i<=m;++i) {

      u=qread(),v=qread(),w=qread();

      ct(u-1,v,w),ct(v,u-1,-w);

    }

    if(spfa()) printf("false\n");

    else printf("true\n");

  }

  return 0;

}

4. P3258 [JLOI2014]松鼠的新家

题目描述

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有\(n-1\)根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。

松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去\(a_1\)，再去\(a_2\)，......，最后到\(a_n\)，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。

维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间\(a_n\)是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入输出格式

输入格式：

第一行一个整数\(n\)，表示房间个数第二行\(n\)个整数，依次描述\(a_1-a_n\)

接下来\(n-1\)行，每行两个整数\(x\)，\(y\)，表示标号\(x\)和\(y\)的两个房间之间有树枝相连。

输出格式：

一共\(n\)行，第\(i\)行输出标号为\(i\)的房间至少需要放多少个糖果，才能让维尼有糖果吃。

输入输出样例

输入样例#1：

5

1 4 5 3 2

1 2

2 4

2 3

4 5

输出样例#1：

1

2

1

2

1

说明

\(2 \leq n \leq 300000\)

思路：考虑树链剖分+线段树，我们自己手玩样例可以发现，我们按题目中给出的结点访问顺序进行路径修改，最后把每条路径的起点的点权\(-1\)(除了起始结点)，就是答案了，然后就是一个树链剖分的裸题了。

代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

#define maxn 300007

#define ls rt<<1

#define rs rt<<1|1

using namespace std;

int n,m,head[maxn],d[maxn],son[maxn],siz[maxn],id[maxn],w[maxn];

int num,cnt,sum[maxn<<2],top[maxn],fa[maxn],lazy[maxn<<2];

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

struct node {

  int v,nxt;

}e[maxn<<1];

inline void ct(int u, int v) {

  e[++num].v=v;

  e[num].nxt=head[u];

  head[u]=num;

}

inline void pushdown(int rt) {

  if(lazy[rt]) {

    sum[ls]+=lazy[rt],sum[rs]+=lazy[rt];

    lazy[ls]+=lazy[rt],lazy[rs]+=lazy[rt];

    lazy[rt]=0;

  }

}

void modify(int rt, int l, int r, int L, int R, int val) {

  if(L>r||R<l) return;

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

    sum[rt]+=val;

    lazy[rt]+=val;

    return;

  }

  pushdown(rt);

  int mid=(l+r)>>1;

  modify(ls,l,mid,L,R,val),modify(rs,mid+1,r,L,R,val);

}

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

  if(l==r) return sum[rt];

  int mid=(l+r)>>1;

  pushdown(rt);

  if(L<=mid) return query(ls,l,mid,L);

  else return query(rs,mid+1,r,L);

}

void dfs1(int u) {

  siz[u]=1;

  for(int i=head[u];i;i=e[i].nxt) {

    int v=e[i].v;

    if(v!=fa[u]) {

      d[v]=d[u]+1;

      fa[v]=u;

      dfs1(v);

      siz[u]+=siz[v];

      if(siz[v]>siz[son[u]]) son[u]=v;

    }

  }

}

void dfs2(int u, int t) {

  id[u]=++cnt;

  top[u]=t;

  if(son[u]) dfs2(son[u],t);

  for(int i=head[u];i;i=e[i].nxt) {

    int v=e[i].v;

    if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

  }

}

void cal(int x, int y) {

  int fx=top[x],fy=top[y];

  while(fx!=fy) {

    if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);

    modify(1,1,cnt,id[fx],id[x],1);

    x=fa[fx],fx=top[x];

  }

  if(id[x]>id[y]) swap(x,y);

  modify(1,1,cnt,id[x],id[y],1);

}

int main() {

  n=qread();

  for(int i=1;i<=n;++i) w[i]=qread();

  for(int i=1,u,v;i<n;++i) {

    u=qread(),v=qread();

    ct(u,v);ct(v,u);

  }

  dfs1(1),dfs2(1,1);

  int now=w[1];

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

    cal(now,w[i]);

    now=w[i];

    modify(1,1,cnt,id[now],id[now],-1);

  }

  for(int i=1;i<=n;++i) printf("%d\n",query(1,1,cnt,id[i]));

  return 0;

}

5. 洛谷P3038 牧草种植Grass Planting

思路：

首先，这道题的翻译是有问题的(起码现在是)，查询的时候应该是查询某一条路径的权值，而不是某条边(坑死我了)。

与平常树链剖分题目不同的是，这道题目维护的是边权，而不是点权，那怎么办呢？好像有点棘手诶，这是一种非常经典的题型，我们可以发现，一个点最多只有一个父亲！！！那，我们显然就可以用这个点的点权去代替它与它父亲之间的边权！！！然后这道题不就成了树链剖分水题了嘛？刚开始边权都是\(0\)，那我们就根据题目给的边建边权为\(0\)的边。

\(nonono\)，还有一个坑点就是在路径查询和修改的时候，两点的\(LCA\)的点权是不能算在其中的，因为它的点权是\(LCA\)与\(LCA\)父亲之间边的边权，注意这几个问题，那这题就真的是水题了！

自己整理的题解

具体实现看代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

#define maxn 100007

#define ls rt<<1

#define rs rt<<1|1

using namespace std;

int n,m,head[maxn],d[maxn],son[maxn],siz[maxn],id[maxn],w[maxn];

int num,cnt,sum[maxn<<2],lazy[maxn<<2],top[maxn],fa[maxn],a[maxn];

char s[3];

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

struct node {

  int v,w,nxt;

}e[maxn<<1];

inline void ct(int u, int v, int w) {

  e[++num].v=v;

  e[num].w=w;

  e[num].nxt=head[u];

  head[u]=num;

}

inline void pushup(int rt) {

  sum[rt]=sum[ls]+sum[rs];

}

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

  if(l==r) {

    sum[rt]=a[l];

    return;

  }

  int mid=(l+r)>>1;

  build(ls,l,mid);

  build(rs,mid+1,r);

  pushup(rt);

}

inline void pushdown(int rt, int len) {

  if(lazy[rt]) {

    sum[ls]+=(len-(len>>1))*lazy[rt];

    sum[rs]+=(len>>1)*lazy[rt];

    lazy[ls]+=lazy[rt],lazy[rs]+=lazy[rt];

    lazy[rt]=0;

  }

}

void modify(int rt, int l, int r, int L, int R, int val) {

  if(L>r||R<l) return;

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

    sum[rt]+=(r-l+1)*val;

    lazy[rt]+=val;

    return;

  }

  pushdown(rt,r-l+1);

  int mid=(l+r)>>1;

  modify(ls,l,mid,L,R,val),modify(rs,mid+1,r,L,R,val);

  pushup(rt);

}

int csum(int rt, int l, int r, int L, int R) {

  if(L>r||R<l) return 0;

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

  pushdown(rt,r-l+1);

  int mid=(l+r)>>1;

  return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R);

}

void dfs1(int u) {

  siz[u]=1;

  for(int i=head[u];i;i=e[i].nxt) {

    int v=e[i].v;

    if(v!=fa[u]) {

      d[v]=d[u]+1;

      fa[v]=u;

      w[u]=e[i].w;

      dfs1(v);

      siz[u]+=siz[v];

      if(siz[v]>siz[son[u]]) son[u]=v;

    }

  }

}

void dfs2(int u, int t) {

  id[u]=++cnt;

  top[u]=t;

  a[cnt]=w[u];

  if(son[u]) dfs2(son[u],t);

  for(int i=head[u];i;i=e[i].nxt) {

    int v=e[i].v;

    if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

  }

}

void cal(int x, int y) {

  int fx=top[x],fy=top[y];

  while(fx!=fy) {

    if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);

    modify(1,1,cnt,id[fx],id[x],1);

    x=fa[fx],fx=top[x];

  }

  if(id[x]>id[y]) swap(x,y);

  modify(1,1,cnt,id[x]+1,id[y],1);

}

int query(int x, int y) {

  int fx=top[x],fy=top[y],ans=0;

  while(fx!=fy) {

    if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);

    ans+=csum(1,1,cnt,id[fx],id[x]);

    x=fa[fx],fx=top[x];

  }

  if(id[x]>id[y]) swap(x,y);

  ans+=csum(1,1,cnt,id[x]+1,id[y]);

  return ans;

}

int main() {

  n=qread(),m=qread();

  for(int i=1,u,v;i<n;++i) {

    u=qread(),v=qread();

    ct(u,v,0);ct(v,u,0);

  }

  dfs1(1);dfs2(1,1);build(1,1,n);

  for(int i=1,u,v;i<=m;++i) {

    scanf("%s",s);

    u=qread(),v=qread();

    if(s[0]=='P') cal(u,v);

    else printf("%d\n",query(u,v));

  }

  return 0;

}

6. 洛谷P1262 间谍网络

题目描述

由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果\(A\)间谍手中掌握着关于\(B\)间谍的犯罪证据，则称\(A\)可以揭发\(B\)。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有\(n\)个间谍(\(n\)不超过\(3000\))，每个间谍分别用\(1\)到\(3000\)的整数来标识。

请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。

输入输出格式

输入格式：

第一行只有一个整数\(n\)。

第二行是整数\(p\)。表示愿意被收买的人数，\(1≤p≤n\)。

接下来的\(p\)行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过\(20000\)。

紧跟着一行只有一个整数\(r\)，\(1≤r≤8000\)。然后\(r\)行，每行两个正整数，表示数对\((A, B)\)，\(A\)间谍掌握\(B\)间谍的证据。

输出格式：

如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。

输入输出样例

输入样例#1：

3

2

1 10

2 100

2

1 3

2 3

输出样例#1：

YES

110

输入样例#2：

4

2

1 100

4 200

2

1 2

3 4

输出样例#2：

NO

3

思路：

可以看出此题有两种情况:

一是有的罪犯既不能贿赂他也没有罪犯能揭发他，那么此题无解，我们在遍历时打上标记，然后从小到大枚举，只要遇见没有标记的就输出然后退出即可。

二是所有的罪犯都能直接或间接地被能贿赂的罪犯揭发。很明显，也有两种情况，一是没有环，那么资金就是贿赂那个没有入度的罪犯，二是有环，那么资金就是那个环里罪犯所需资金最小的。我们想，如果我们把环里的罪犯缩成一个点，那么全都是前者的情况了。然后就可以\(tarjan\)缩点做了。

代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<cstring>

#include<stack>

#define maxn 3007

using namespace std;

int num,n,m,vis[maxn],cnt,js,head[maxn],dfn[maxn],low[maxn];

int bel[maxn],block[maxn],w[maxn],p,rd[maxn],zrj;

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

struct node {

  int v,nxt;

}e[8007];

const int inf=0x3f3f3f3f;

inline void ct(int u, int v) {

  e[++num].v=v;

  e[num].nxt=head[u];

  head[u]=num;

}

stack<int>q;

void tarjan(int u) {

  dfn[u]=low[u]=++cnt;

  q.push(u),vis[u]=1;

  for(int i=head[u];i;i=e[i].nxt) {

    int v=e[i].v;

    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);

    else if(vis[v]) low[u]=min(low[u],dfn[v]);

  }

  if(dfn[u]==low[u]) {

    int x=-1;js++;

    while(x!=u) {

      x=q.top();q.pop();

      bel[x]=js;

      block[js]=min(block[js],w[x]);

      vis[x]=0;

    }

  }

}

int main() {

  n=qread(),p=qread();

  memset(block,0x3f,sizeof(block));

  memset(w,0x3f,sizeof(w));

  for(int i=1,x,y;i<=p;++i) {

    x=qread(),y=qread();

    w[x]=y;

  }

  m=qread();

  for(int i=1,u,v;i<=m;++i) {

    u=qread(),v=qread();

    ct(u,v);

  }

  for(int i=1;i<=n;++i) if(!dfn[i]&&w[i]!=inf) tarjan(i);

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

    if(!dfn[i]) {

      printf("NO\n%d\n",i);

      return 0;

    }

  }

  for(int u=1;u<=n;++u) {

    for(int i=head[u];i;i=e[i].nxt) {

      int v=e[i].v;

      if(bel[u]!=bel[v]) rd[bel[v]]++;

    }

  }

  for(int i=1;i<=js;++i) if(!rd[i]) zrj+=block[i];

  printf("YES\n%d\n",zrj);

  return 0;

}

7. 洛谷P5159 WD与矩阵

题目背景

WD整日沉浸在矩阵中，无法自拔……

题目描述

WD特别喜欢矩阵，尤其是\(01\)矩阵。

一天，CX给了WD一个巨大的\(n\)行\(m\)列的\(01\)矩阵，WD发现这个矩阵每行、每列的异或值都是\(0\).

CX随后就问道：“WD，你知道有多少\(01\)矩阵每行每列异或值都是\(0\)吗！？”WD当然不会这个问题，于是他来请教你。

由于答案可能很大，输出结果模\(998244353\)的值即可。

输入输出格式

输入格式：

第一行一个数\(T\)，表示数据组数。

接下来\(T\)行每行两个数\(n,m\)，分别表示询问的行数和列数。

输出格式：

共\(T\)行，每行一个数，表示答案\(mod\) \(998244353\)的结果。

输入输出样例

输入样例#1：

2

2 2

2 2018

输出样例#1：

2

851481696

说明

\(subtask1(11pts):~1\le T\le 10,~1\le n,m\le 4\)

\(subtask1(43pts):~1\le T\le 5,~1\le n\le 5,~1\le m\le 1,000\)

\(subtask1(46pts):~1\le T\le 100,000,~1\le n,m\le 10^9\)

思路：

题意是让你求满足n行m列且每行每列异或值都是0的矩阵个数，因为是异或，所以只可能有两个值，\(0\)或\(1\)，那么每行可能的取值就是\(2^n\)，然后最后值是0的情况是就是\(2^{n-1}\)，然后扩展到列上，那么就是\((2^{n-1})^{m-1}\)，然后自己再打打表就发现，显然这个式子是正确的，然后用快速幂求解，计算的过程中记得取模。

自己整理的题解

下面是我简洁的代码：

#include<cstdio>

#include<algorithm>

#include<cmath>

#define ll long long

#define mod 998244353

using namespace std;

ll n,m;

int t;

inline ll fpow(ll a, ll b) {

  if(!b) return 1;

  ll ans=1;

  for(;b;b>>=1,a=(a*a)%mod)

    if(b&1) ans=(ans*a)%mod;

  return ans;

}

int main() {

  scanf("%d",&t);

  while(t--) {

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

    printf("%lld\n",fpow(fpow(2,n-1),m-1));

  }

  return 0;

}

8. 洛谷P4113 [HEOI2012]采花

题目描述

萧薰儿是古国的公主，平时的一大爱好是采花。

今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。

花园足够大，容纳了n朵花，花有c种颜色（用整数1-c表示），且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。

由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了m个行程，然后一一向你询问公主能采到多少朵花（她知道你是编程高手，定能快速给出答案！），最后会选择令公主最高兴的行程（为了拿到更多奖金！）。

输入输出格式

输入格式：

第一行四个空格隔开的整数n、c以及m。接下来一行n个空格隔开的整数，每个数在[1, c]间，第i个数表示第i朵花的颜色。接下来m行每行两个空格隔开的整数l和r（l ≤ r），表示女仆安排的行程为公主经过第l到第r朵花进行采花。

输出格式：

共m行，每行一个整数，第i个数表示公主在女仆的第i个行程中能采到的花的颜色数。

输入输出样例

输入样例#1：

5 3 5

1 2 2 3 1

1 5

1 2

2 2

2 3

3 5

输出样例#1：

2

0

0

1

0

说明

对于\(100\%\)的数据，\(1 ≤ n ≤ 2*10^6\)，\(c ≤ n，m ≤2*10^6\)

本题有两个\(subtask\)

\(subtask1\)保证\(n,m,c \leq 3*10^5\)，占\(100\)分

\(subtask2\)保证\(n,m,c \leq 2*10^6\)，占\(100\)分

思路：这道题目跟HH项链有些相似，唯一的不同在于这道题目要除去区间内只出现过一次的颜色，那么我们就可以利用一个\(nxt\)和一个\(last\)数组来记录一个每一种颜色的前驱和后继状态，即上次和下次出现的位置，没有为\(0\)，然后把询问离线下来，按右端点排一遍序，其实左端点也行，无所谓的，然后用树状数组维护区间和，然后定义一个指针，把\(m\)个询问扫一遍，然后在这个过程中如果说上次的上次已经出现过了，那就把上次的上次那个位置\(-1\)，上次的位置\(+1\)，然后处理出区间和即可。时间复杂度\(nlogn\)。

代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

#define maxn 2000007

#define lb(x) x&(-x)

using namespace std;

int n,m,c,a[maxn],nxt[maxn],last[maxn],w[maxn];

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

inline void add(int x, int w) {

  if(!x) return;

  while(x<=n) {

  	a[x]+=w;

  	x+=lb(x);

  }

}

inline int query(int x) {

  int ans=0;

  while(x) {

  	ans+=a[x];

  	x-=lb(x);

  }

  return ans;

}

struct node {

  int l,r,ans,id;

}e[maxn];

inline bool cmp1(node a, node b) {

  if(a.r!=b.r) return a.r<b.r;

  return a.l<b.l;

}

int main() {

  n=qread(),c=qread(),m=qread();

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

  	w[i]=qread();

  	nxt[i]=last[w[i]];

  	last[w[i]]=i;

  }

  for(int i=1;i<=m;++i) e[i].l=qread(),e[i].r=qread(),e[i].id=i;

  sort(e+1,e+1+m,cmp1);

  int j=1;

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

  	while(j<=e[i].r) add(nxt[nxt[j]],-1),add(nxt[j],1),++j;

	e[e[i].id].ans=query(e[i].r)-query(e[i].l-1);

  }

  for(int i=1;i<=m;++i) printf("%d\n",e[i].ans);

  return 0;

}