2017年多校联训9 部分题解

前端之家收集整理的这篇文章主要介绍了2017年多校联训9 部分题解前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

1002. Ch’s gift

首先考虑序列上的问题。

a 是一个二维数组,如果第 i 位置的值为 j ,就在 ai,j 加上 j 。那么某个询问 x,y,a,b 的答案就是子矩阵的和。如果一开始就把二维前缀和算出来的话就可以回答 O(1) ,答案等于 (Sum(y,b)Sum(y,a1))(Sum(x,b)Sum(x,a1))

考虑到 a,b 的范围非常大,可以把所有询问离散化。当然就算离散化,预处理二维前缀和还是不行的,我们发现前缀和相当于把 [a,b] 拆成 [1,b][1,@H_647_404@a1@H_403_410@] ,联想到扫描线,把 a,b 这一维的每个区间拆成两条线,用扫描线从小到大扫这一维, x,y 这一维直接预处理一下前缀和每次 O(1) 查就行了。

再搬到树上,直接套一个树链剖分就行了,树状数组就能维护。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const int MAXN=1e5+5;
  6. struct Edge {
  7. int to,next;
  8. } edge[MAXN*2];
  9. int head[MAXN],tot;
  10. int top[MAXN],fa[MAXN];//父亲节点
  11. int deep[MAXN];//深度
  12. int num[MAXN];//num[v] 表示以v为根的子树的节点数
  13. int p[MAXN];//p[v]表示v对应的位置
  14. int fp[MAXN];//fp和p数组相反
  15. int son[MAXN];//重儿子
  16. int pos;
  17. int v[MAXN*3];
  18.  
  19. void init()
  20. {
  21. tot = 0;
  22. memset(head,-1,sizeof(head));
  23. pos = 1;
  24. memset(son,sizeof(son));
  25. }
  26.  
  27. void addedge(int u,int v)
  28. {
  29. edge[tot].to = v;
  30. edge[tot].next = head[u];
  31. head[u] = tot++;
  32. }
  33.  
  34. void dfs1(int u,int pre,int d)
  35. {
  36. deep[u] = d;
  37. fa[u] = pre;
  38. num[u] = 1;
  39. for(int i = head[u]; i != -1; i = edge[i].next) {
  40. int v = edge[i].to;
  41. if(v != pre) {
  42. dfs1(v,u,d+1);
  43. num[u] += num[v];
  44. if(son[u] == -1 || num[v] > num[son[u]])
  45. son[u] = v;
  46. }
  47. }
  48. }
  49.  
  50. void getpos(int u,int sp)
  51. {
  52. top[u] = sp;
  53. p[u] = pos++;
  54. fp[p[u]] = u;
  55. if(son[u] == -1) return;
  56. getpos(son[u],sp);
  57. for(int i = head[u]; i != -1; i = edge[i].next) {
  58. int v = edge[i].to;
  59. if( v != son[u] && v != fa[u])
  60. getpos(v,v);
  61. }
  62. }
  63.  
  64. inline int lowbit(int x)
  65. {
  66. return x&(-x);
  67. }
  68.  
  69. ll c[MAXN];
  70. ll sum(int i)
  71. {
  72. ll s = 0;
  73. while(i > 0) {
  74. s += c[i];
  75. i -= lowbit(i);
  76. }
  77. return s;
  78. }
  79.  
  80. void add(int i,int val)
  81. {
  82. while(i <MAXN) {
  83. c[i] += val;
  84. i += lowbit(i);
  85. }
  86. }
  87.  
  88. ll query(int u,int v)
  89. {
  90. int f1 = top[u],f2 = top[v];
  91. ll res=0;
  92. while(f1 != f2) {
  93. if(deep[f1] < deep[f2]) {
  94. swap(f1,f2);
  95. swap(u,v);
  96. }
  97. res+=sum(p[u])-sum(p[f1]-1);
  98. u = fa[f1];
  99. f1 = top[u];
  100. }
  101. if(deep[u] > deep[v]) swap(u,v);
  102. res+=sum(p[v])-sum(p[u]-1);
  103. return res;
  104. }
  105.  
  106. struct Query {
  107. int u,v,val,zf,id;
  108. bool operator <(const Query &R) {
  109. return val<R.val;
  110. }
  111. } q[MAXN*2];
  112. int a[MAXN];
  113. struct Node {
  114. int iv,id;
  115. bool operator <(const Node &R) {
  116. return iv<R.iv;
  117. }
  118. } ia[MAXN];
  119. ll ans[MAXN];
  120.  
  121. int main()
  122. {
  123. int n,m;
  124. while (scanf("%d%d",&n,&m)!=EOF) {
  125. init();
  126. int vtot=0;
  127. for (int i=1;i<=n;i++) {
  128. scanf("%d",&a[i]);
  129. v[++vtot]=a[i];
  130. }
  131. for (int i=1;i<n;i++) {
  132. int x,y;
  133. scanf("%d%d",&x,&y);
  134. addedge(x,y);
  135. addedge(y,x);
  136. }
  137. dfs1(1,0,0);
  138. getpos(1,1);
  139. for (int i=1;i<=m;i++) {
  140. int s,t,b;
  141. scanf("%d%d%d%d",&s,&t,&a,&b);
  142. q[i+i-1]={s,a-1,i};
  143. q[i+i]={s,b,1,i};
  144. v[++vtot]=a-1;
  145. v[++vtot]=b;
  146. }
  147. m<<=1;
  148. sort(v+1,v+vtot+1);
  149. vtot=unique(v+1,v+vtot+1)-v-1;
  150. for (int i=1;i<=m;i++) {
  151. q[i].val=lower_bound(v+1,v+vtot+1,q[i].val)-v;
  152. }
  153. for (int i=1;i<=n;i++) {
  154. ia[i].iv=lower_bound(v+1,a[i])-v;
  155. ia[i].id=i;
  156. }
  157. sort(q+1,q+1+m);
  158. sort(ia+1,ia+n+1);
  159. memset(ans,sizeof(ans));
  160. int j=1;
  161. for (int i=1;i<=m;i++) {
  162. while (j<=n&&ia[j].iv<=q[i].val) {
  163. add(p[ia[j].id],a[ia[j].id]);
  164. ++j;
  165. }
  166. ans[q[i].id]+=q[i].zf*query(q[i].u,q[i].v);
  167. }
  168. m>>=1;
  169. for (int i=1;i<=m;i++) {
  170. printf("%lld%c",ans[i]," \n"[i==m]);
  171. }
  172. }
  173. return 0;
  174. }

ps: 可持久化线段树可以在线回答,等写出来了更新

1005. FFF at Valentine

强连通缩点加拓扑序判分叉,不多说了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1010;//点数
  5. const int MAXM = 50010;//边数
  6. struct Edge {
  7. int fr,to,next;
  8. } eg[MAXM];
  9. int head[MAXN],tot;
  10. int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc
  11. int Index,top;
  12. int scc;//强连通分量的个数
  13. bool Instack[MAXN];
  14. int T,n,m;
  15. bool g[MAXN][MAXN];
  16. int in[MAXN];
  17. vector<int> G[MAXN];
  18.  
  19. void Tarjan(int u)
  20. {
  21. int v;
  22. Low[u] = DFN[u] = ++Index;
  23. Stack[top++] = u;
  24. Instack[u] = true;
  25. for(int i = head[u]; i != -1; i = eg[i].next) {
  26. v = eg[i].to;
  27. if( !DFN[v] ) {
  28. Tarjan(v);
  29. if( Low[u] > Low[v] )Low[u] = Low[v];
  30. } else if(Instack[v] && Low[u] > DFN[v])
  31. Low[u] = DFN[v];
  32. }
  33. if(Low[u] == DFN[u]) {
  34. scc++;
  35. do {
  36. v = Stack[--top];
  37. Instack[v] = false;
  38. Belong[v] = scc;
  39. } while( v != u);
  40. }
  41. }
  42.  
  43. void solve(int N)
  44. {
  45. memset(DFN,sizeof(DFN));
  46. memset(Instack,false,sizeof(Instack));
  47. Index = scc = top = 0;
  48. for(int i = 1; i <= N; i++)
  49. if(!DFN[i])
  50. Tarjan(i);
  51. }
  52.  
  53. void init()
  54. {
  55. tot = 0;
  56. memset(head,sizeof(head));
  57. }
  58.  
  59. bool bad()
  60. {
  61. queue<int> Q;
  62. for (int i=1;i<=scc;i++) {
  63. if (!in[i]) {
  64. Q.push(i);
  65. }
  66. }
  67. while (!Q.empty()) {
  68. if (Q.size()>1) {
  69. return true;
  70. }
  71. int u=Q.front();
  72. Q.pop();
  73. for (int v:G[u]) {
  74. if (--in[v]==0) {
  75. Q.push(v);
  76. }
  77. }
  78. }
  79. return false;
  80. }
  81.  
  82. int main()
  83. {
  84. scanf("%d",&T);
  85. while (T--) {
  86. scanf("%d%d",&m);
  87. init();
  88. for (int i=1;i<=m;i++) {
  89. int x,y;
  90. scanf("%d%d",&x,&y);
  91. eg[tot]={x,head[x]};
  92. head[x]=tot++;
  93. }
  94. solve(n);
  95. memset(g,sizeof(g));
  96. memset(in,sizeof(in));
  97. for (int i=1;i<=scc;i++) {
  98. G[i].clear();
  99. }
  100. for (int i=0;i<m;i++) {
  101. int x=Belong[eg[i].fr];
  102. int y=Belong[eg[i].to];
  103. if (x!=y) {
  104. if (!g[x][y]) {
  105. g[x][y]=1;
  106. G[x].push_back(y);
  107. in[y]++;
  108. }
  109. }
  110. }
  111. if (bad()) {
  112. puts("Light my fire!");
  113. } else {
  114. puts("I love you my love and our love save us!");
  115. }
  116. }
  117. return 0;
  118. }

1006. Senior Pan

这题主要是题意有点不清楚。。。大小为 k 的端点集合,题目的意思是起点终点不能是同一个【不过也是有道理的。。。

拆点,加超级源超级汇,再跑一下dij 。这个限制可以每个点维护一下被谁松弛过,比如现在想用 i 松弛 j ,如果 j 松弛过 i ,直接不让松弛就行了。一个点被松弛的次数小于总点数,复杂度也就是多个 logn ,具体表现可能比20次dij好一点吧。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<ll,int> PLI;
  6. const int N=100010;
  7. struct Edge {
  8. int go,next;
  9. } eg[N*5];
  10. int last[N<<1],tot;
  11. ll d[N<<1];
  12. int vis[N<<1],st[N];
  13. set<int> re[N<<1];
  14. int T,m,k,cas=0;
  15.  
  16. namespace fastIO {
  17. #define BUF_SIZE 100000
  18. //fread -> read
  19. bool IOerror = 0;
  20. inline char nc() {
  21. static char buf[BUF_SIZE],*p1 = buf + BUF_SIZE,*pend = buf + BUF_SIZE;
  22. if(p1 == pend) {
  23. p1 = buf;
  24. pend = buf + fread(buf,BUF_SIZE,stdin);
  25. if(pend == p1) {
  26. IOerror = 1;
  27. return -1;
  28. }
  29. }
  30. return *p1++;
  31. }
  32. inline bool blank(char ch) {
  33. return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  34. }
  35. inline void read(int &x) {
  36. char ch;
  37. while(blank(ch = nc()));
  38. if(IOerror)
  39. return;
  40. for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
  41. }
  42. #undef BUF_SIZE
  43. };
  44.  
  45. void dij(int S)
  46. {
  47. priority_queue< PLI,vector<PLI>,greater<PLI> > q;
  48. memset(d,0x3f,sizeof(d));
  49. memset(vis,sizeof(vis));
  50. d[S]=0; q.push(PLI(d[S],S));
  51. while (!q.empty()){
  52. PLI tmp=q.top();
  53. q.pop();
  54. int u=tmp.second;
  55. if (vis[u]) continue;
  56. vis[u]=1;
  57. for (int i=last[u];i!=-1;i=eg[i].next) {
  58. int &v=eg[i].go;
  59. // printf("%d %d\n",v);
  60. if (u<=n&&v>n&&st[v-n]) {
  61. if (re[u+n].find(v-n)!=re[u+n].end()) continue;
  62. }
  63. if (d[v]>d[u]+eg[i].val) {
  64. re[v].insert(u);
  65. d[v]=d[u]+eg[i].val;
  66. q.push(PLI(d[v],v));
  67. }
  68. }
  69. }
  70. }
  71.  
  72. void addedge(int x,int y,int z)
  73. {
  74. eg[tot]={y,z,last[x]};
  75. last[x]=tot++;
  76. }
  77.  
  78. int main()
  79. {
  80. fastIO::read(T);
  81. while (T--) {
  82. fastIO::read(n);
  83. fastIO::read(m);
  84. tot=0;
  85. memset(last,sizeof(last));
  86. for (int i=1;i<=m;i++) {
  87. int x,z;
  88. fastIO::read(x);
  89. fastIO::read(y);
  90. fastIO::read(z);
  91. addedge(x,n+y,z);
  92. }
  93. fastIO::read(k);
  94. memset(st,sizeof(st));
  95. int S=0,T=n+n+1;
  96. for (int i=1;i<=k;i++) {
  97. int x;
  98. fastIO::read(x);
  99. st[x]=1;
  100. addedge(S,x,0);
  101. addedge(n+x,T,0);
  102. }
  103. for (int i=1;i<=n;i++) {
  104. addedge(n+i,i,0);
  105. }
  106. for (int i=0;i<=n+n+1;i++) {
  107. re[i].clear();
  108. }
  109. dij(S);
  110. printf("Case #%d: %lld\n",++cas,d[T]);
  111. }
  112. return 0;
  113. }

1008. Numbers

从小到大取, O(n2logm) n m 级别。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int M=125260;
  5. int a[M];
  6. multiset<int> ss;
  7.  
  8. namespace fastIO {
  9. #define BUF_SIZE 100000
  10. //fread -> read
  11. bool IOerror = 0;
  12. inline char nc() {
  13. static char buf[BUF_SIZE],stdin);
  14. if(pend == p1) {
  15. IOerror = 1;
  16. return -1;
  17. }
  18. }
  19. return *p1++;
  20. }
  21. inline bool blank(char ch) {
  22. return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  23. }
  24. inline void read(int &x) {
  25. char ch;
  26. while(blank(ch = nc()));
  27. if(IOerror)
  28. return;
  29. for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
  30. }
  31. #undef BUF_SIZE
  32. };
  33.  
  34. int main()
  35. {
  36. int m,x;
  37. while (fastIO::read(m),!fastIO::IOerror) {
  38. for (int i=1;i<=m;i++) {
  39. fastIO::read(x);
  40. ss.insert(x);
  41. }
  42. int n=0;
  43. a[++n]=*ss.begin();
  44. ss.erase(ss.begin());
  45. while (!ss.empty()) {
  46. a[++n]=*ss.begin();
  47. ss.erase(ss.begin());
  48. for (int i=1;i<n;i++) {
  49. ss.erase(ss.find(a[i]+a[n]));
  50. }
  51. }
  52. printf("%d\n",n);
  53. for (int i=1;i<=n;i++) {
  54. printf("%d%c",a[i]," \n"[i==n]);
  55. }
  56. }
  57. return 0;
  58. }

1010. Two strings

主要还是题意比较坑。。。匹配.*是要把.先变成某个字符再处理*。。。

队友(wenwenla)写了一种dp,先预处理pattern,dp[i]保存pattern前i个字符为止可以匹配到text的最左和最右,可以证明这个界里面的每一个都是可取的。

具体实现加一维表示最左最右,然后发现第一维可以去掉。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=2510,INF=1<<30;
  5. char a[N],b[N];
  6. int dp[2];
  7. bool mul[N];
  8.  
  9. int main()
  10. {
  11. int T;
  12. scanf("%d",&T);
  13. while (T--) {
  14. scanf("%s",a+1);
  15. scanf("%s",b+1);
  16. int la=strlen(a+1);
  17. int lb=strlen(b+1);
  18. int j=0;
  19. memset(mul,sizeof(mul));
  20. for (int i=1;i<=lb;i++) {
  21. if (b[i]=='*') {
  22. mul[j]=1;
  23. } else {
  24. b[++j]=b[i];
  25. }
  26. }
  27. lb=j;
  28. int flag=0;
  29. dp[0]=dp[1]=0;
  30. for (int i=1;i<=lb;i++) {
  31. if (mul[i]) {
  32. int p=dp[1];
  33. if (p<la&&(b[i]=='.'||b[i]==a[p+1])) {
  34. ++p;
  35. while (p<la&&a[p+1]==a[p]) p++;
  36. }
  37. dp[1]=p;
  38. } else {
  39. int ll=INF,rr=-INF;
  40. for (int j=dp[0]+1;j<=dp[1]+1;j++) {
  41. if (j>la) break;
  42. if (b[i]=='.'||b[i]==a[j]) {
  43. ll=min(ll,j);
  44. rr=max(rr,j);
  45. }
  46. }
  47. if (ll==INF) {
  48. flag=1;
  49. break;
  50. }
  51. dp[0]=ll;dp[1]=rr;
  52. }
  53. }
  54. if (flag||dp[1]!=la) {
  55. puts("no");
  56. } else {
  57. puts("yes");
  58. }
  59. }
  60. return 0;
  61. }

时间0ms,就是容易写错。。。比赛的时候前面WA的都交上去了,最后一次AC的代码却没交上去[cry]。。。而且我们亲眼看到点了submit以后页面跳转了。。。结果连提交记录都没有??

后来有人说了才发现这样直接正则就能过,这题出得真好??

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const char sp[]="(q*|w*|e*|r*|t*|y*|u*|i*|o*|p*|a*|s*|d*|f*|g*|h*|j*|k*|l*|z*|x*|c*|v*|b*|n*|m*)";
  5.  
  6. int main() {
  7. int T;
  8. scanf("%d",&T);
  9. scanf("\n");
  10. while(T--) {
  11. string a,c;
  12. getline(cin,a);
  13. getline(cin,b);
  14. for (int i=0;i<b.length();i++) {
  15. if (i<b.length()-1&&b[i]=='.'&&b[i+1]=='*') {
  16. c+=sp;i++;
  17. } else {
  18. c+=b[i];
  19. }
  20. }
  21. auto re = regex(c);
  22. if(regex_match(a,re)) {
  23. puts("yes");
  24. } else {
  25. puts("no");
  26. }
  27. }
  28. return 0;
  29. }

猜你在找的正则表达式相关文章