2017 ZSTU寒假排位赛 #8

　　题目链接：https://vjudge.net/contest/149845#overview。

　　A题，水题。

　　B题，给出 p个第一个人的区间和 q个第二个人的区间，问[l,r]中有多少个整数满足，第二个人的区间范围全部增加这个整数以后和第一个人的区间有交集。以为是个数据结构题，后来才发现p和q的范围才50。那么暴力枚举位移dt，然后对第二个人的区间做差分标记然后看看有没有交集即可。代码如下（我发现数组越界了也能A...）：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <iostream>
 5 #include <map>
 6 #include <vector>
 7 using namespace std;
 8 const int N = 100000 + 5;
 9 const int mod = 1e9 + 7;
10 
11 int p,q,l,r;
12 int a[55],b[55],c[55],d[55];
13 int e[1000+5],f[1000+5];
14 
15 int main()
16 {
17     cin >> p >> q >> l >> r;
18     for(int i=1;i<=p;i++) scanf("%d%d",a+i,b+i);
19     for(int i=1;i<=q;i++) scanf("%d%d",c+i,d+i);
20     for(int i=1;i<=p;i++) e[a[i]]++, e[b[i]+1]--;
21     for(int i=1;i<=1000;i++) e[i] += e[i-1];
22     int ans = 0;
23     for(int dt=l;dt<=r;dt++)
24     {
25         memset(f,0,sizeof f);
26         for(int i=1;i<=q;i++) f[c[i]+dt]++, f[min(d[i]+dt+1, 1001)]--;
27         for(int i=1;i<=1000;i++)
28         {
29             f[i] += f[i-1];
30             if(f[i] > 0 && e[i] > 0)
31             {
32                 ans++;
33                 break;
34             }
35         }
36     }
37     cout << ans << endl;
38     return 0;
39 }

　　C题，任意两个串交换任意前缀，问第一个串能有多少种不同形式。等价于交换任意两个串的两个相同的位置。那么枚举每个位置，看看这个位置在n个串中有多少个不同的字母即可。代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <iostream>
 5 #include <map>
 6 using namespace std;
 7 const int N = 100 + 5;
 8 const int mod = 1e9 + 7;
 9 
10 int n,m;
11 char s[N][N];
12 
13 int main()
14 {
15     cin >> n >> m;
16     for(int i=1;i<=n;i++)
17     {
18         scanf("%s",s[i]+1);
19     }
20     int ans = 1;
21     for(int j=1;j<=m;j++)
22     {
23         map<char,int> M;
24         for(int i=1;i<=n;i++) M[s[i][j]]++;
25         ans = 1LL*ans * M.size() % mod;
26     }
27     cout << ans << endl;
28     return 0;
29 }

　　D题，之前的一场CF做过的，WA了N多发的那题。。

　　E题，给出 m个点，问有多少个点可以到这m个点de最短距离都不超过d。做法是在m个点中找出距离最远的两个点，然后到这两个点的距离都不超过d的点就是可行点。树上找距离最远的两个点就相当于找直径了。从任意一个点出发dfs，找到最远的在m个点中的那个点，作为V，再对那个点dfs，找在m个点中的离V的最远点，作为U。那么U和V就是m个点中距离最远的两个点了。然后再从这两个点开始dfs计算出距离即可。代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <iostream>
 5 #include <map>
 6 #include <vector>
 7 using namespace std;
 8 const int N = 100000 + 5;
 9 const int mod = 1e9 + 7;
10 
11 int n,m,r;
12 bool can[N];
13 int U,V;
14 int max_deep;
15 vector<int> G[N];
16 void dfs(int u,int fa,int deep,int &who)
17 {
18     if(deep > max_deep && can[u])
19     {
20         who = u;
21         max_deep = deep;
22     }
23     for(int i=0;i<G[u].size();i++)
24     {
25         int v = G[u][i];
26         if(v == fa) continue;
27         dfs(v,u,deep+1,who);
28     }
29 }
30 int dis[2][N];
31 void dfs2(int u,int fa,int op)
32 {
33     for(int i=0;i<G[u].size();i++)
34     {
35         int v = G[u][i];
36         if(v == fa) continue;
37         dis[op][v] = dis[op][u] + 1;
38         dfs2(v,u,op);
39     }
40 }
41 
42 int main()
43 {
44     cin >> n >> m >> r;
45     for(int i=1;i<=m;i++)
46     {
47         int x;
48         scanf("%d",&x);
49         can[x] = 1;
50     }
51     for(int i=1;i<n;i++)
52     {
53         int u,v; scanf("%d%d",&u,&v);
54         G[u].push_back(v);
55         G[v].push_back(u);
56     }
57     max_deep = -1;
58     dfs(1,-1,0,U);
59     max_deep = -1;
60     dfs(U,-1,0,V);
61     dfs2(U,-1,0);
62     dfs2(V,-1,1);
63     int ans = 0;
64     for(int i=1;i<=n;i++) if(dis[0][i] <= r && dis[1][i] <= r) ans++;
65     cout << ans << endl;
66     return 0;
67 }