您的位置: 首页  >  IT文章  >  2017 多校联合训练 6 题解

2017 多校联合训练 6 题解

分类: IT文章 • 2025-01-19 12:05:37

Problem 1001

对于每个询问，根据后缀{前缀插入到AC自动机内

然后每个单词写2遍，中间用{隔开，统计有那几个前缀和后缀

最后对于每个前缀和后缀 输出方案数

注意：单词可能有重复，可以用vector记录一下end数组

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<queue>
  6 #include<string>
  7 #define next nxt
  8 #define end ed
  9 using namespace std;
 10 int next[1200001][27],fail[1200001],dep[1200001];
 11 vector<int> end[1200001];
 12 int root,len;
 13 int newnode(){
 14     for(int i=0;i<27;i++)
 15         next[len][i]=-1;
 16     end[len].clear();
 17     len++;
 18     return len-1;
 19 }
 20 void clear(){
 21     len=0;
 22     root=newnode();
 23     return;
 24 }
 25 void insert(char s[],int num){
 26     int ls=strlen(s);
 27     int now=root;
 28     for(int i=0;i<ls;i++){
 29         if(next[now][s[i]-'a']==-1)
 30             next[now][s[i]-'a']=newnode();
 31         now=next[now][s[i]-'a'];
 32         dep[now]=i+1;
 33     }
 34     end[now].push_back(num);
 35 }
 36 void build(){
 37     queue<int>q;
 38     int i;
 39     fail[root]=root;
 40     for(i=0;i<27;i++){
 41         if(next[root][i]==-1)
 42             next[root][i]=root;
 43         else{
 44             fail[next[root][i]]=root;
 45             q.push(next[root][i]);
 46         }
 47     }
 48     while(!q.empty()){
 49         int now=q.front();
 50         q.pop();
 51         for(i=0;i<27;i++){
 52             if(next[now][i]==-1)
 53                 next[now][i]=next[fail[now]][i];
 54             else{
 55                 fail[next[now][i]]=next[fail[now]][i];
 56                 q.push(next[now][i]);
 57             }
 58         }
 59     }
 60     return;
 61 }
 62 int vis[1000010];
 63 void  ask(char c[],int n,int num){
 64     bool flag1=false;
 65     int lc=num;
 66     int now=root;
 67     int i;
 68     for(i=0;i<lc;i++){
 69         now=next[now][c[i]-'a'];
 70         int temp=now;
 71         while(temp!=root){
 72             if(end[temp].size()&&dep[temp]<=n){
 73                 flag1=1;
 74                 for (auto u:end[temp])
 75                     vis[u]++;
 76             }
 77             temp=fail[temp];
 78         }
 79     }
 80 }
 81 char s[2000001],t[2000001],ss[2000001],tt[2000001];
 82 char *si[100010];
 83 int n,m,le[100010],le2[100010];
 84 int main(){
 85     int i,j;
 86     int _;
 87     scanf("%d",&_);
 88     while(_--){
 89         scanf("%d%d",&n,&m);
 90         clear();
 91         for (i=1,j=0;i<=n;i++)
 92         {
 93             si[i]=ss+j;
 94             scanf("%s",si[i]);
 95             le[i]=strlen(si[i])+1;
 96             j+=le[i];
 97             strcpy(ss+j,si[i]);
 98             ss[j-1]='z'+1;
 99             j+=le[i];
100             
101             le2[i]=strlen(si[i]);
102         }
103         for(i=1;i<=m;i++)
104         {
105             s[0]='z'+1;
106             scanf("%s%s",s+1,t);
107             strcat(t,s);
108             insert(t,i);
109         }
110         build();
111         memset(vis,0,sizeof(vis));
112         int ans=0;
113         //for(i=1;i<=m;i++){
114         for (i=1;i<=n;i++)
115         {
116             //strcpy(tt,si[i].c_str());
117             ask(si[i],le[i],le2[i]);
118         }
119         //}
120         for (i=1;i<=m;i++)
121             printf("%d
",vis[i]);
122     }
123     return 0;
124 }
View Code

Problem 1002

这里不总是在中垂线上的点取到最小值

通过观察可发现，当两个点离半径的距离到一定的程度时答案保持不变

算出这个距离即可

另外要注意这两个点可能会重合

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<string>
  8 #include<vector>
  9 #include<map>
 10 #include<set>
 11 #include<queue>
 12 using namespace std;
 13 const double eps=1e-7;
 14 #define y1 jkhjk
 15 #define y2 erjkf
 16 #define y3 jkdfhdw
 17 #define y4 jkhjkff
 18 #define y5 kjhkk
 19 int _;
 20 double r,x1,y1,x2,y2;
 21 int main()
 22 {
 23     scanf("%d",&_);
 24     while (_--)
 25     {
 26         scanf("%lf",&r);
 27         scanf("%lf%lf",&x1,&y1);
 28         scanf("%lf%lf",&x2,&y2);
 29         if (x1==0&&y1==0)
 30         {
 31             printf("%.9f
",r*2);
 32             continue;
 33         }
 34         if (fabs(x1-x2)<=eps&&fabs(y1-y2)<=eps)
 35         {
 36             double rest=r-sqrt(x1*x1+y1*y1);
 37             printf("%.9f
",rest*2);
 38             continue;
 39         }
 40         double x3=(x1+x2)/2;
 41         double y3=(y1+y2)/2;
 42         if (fabs(y1-y2)<=eps)
 43         {
 44             double x4=x3;
 45             double y4=sqrt(r*r-x3*x3);
 46             double x5=x3;
 47             double y5=-sqrt(r*r-x3*x3);
 48             double x6,y6,x7,y7;
 49             double bili=sqrt(x1*x1+y1*y1)/r;
 50             x6=x1/bili;
 51             y6=y1/bili;
 52             x7=x2/bili;
 53             y7=y2/bili;
 54             double dist=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
 55             double pp=sqrt(x1*x1+y1*y1);
 56             double ans=9999999;
 57             double sita=(dist/(2*pp));
 58             //cout<<sita<<endl;
 59             sita=sqrt(1.0-sita*sita);
 60             if (sqrt(x1*x1+y1*y1)>=r*sita-eps)
 61                 ans=sqrt((x7-x6)*(x7-x6)+(y7-y6)*(y7-y6));
 62             ans=min(ans,sqrt((x4-x1)*(x4-x1)+(y4-y1)*(y4-y1))*2);
 63             ans=min(ans,sqrt((x5-x1)*(x5-x1)+(y5-y1)*(y5-y1))*2);
 64             printf("%.9f
",ans);
 65 
 66         }
 67         else
 68         {
 69             double k;
 70             if (x1==x2) k=0;
 71             else
 72                 k=(x2-x1)/(y1-y2);
 73             double a=1+k*k;
 74             double b=2*k*y3-2*k*k*x3;
 75             double c=k*k*x3*x3-2*k*x3*y3+y3*y3-r*r;
 76             double det=b*b-4*a*c;
 77             double x4=(-b+sqrt(det))/(2*a);
 78             double y4=k*(x4-x3)+y3;
 79             double x5=(-b-sqrt(det))/(2*a);
 80             double y5=k*(x5-x3)+y3;
 81             double x6,y6,x7,y7;
 82             double bili=sqrt(x1*x1+y1*y1)/r;
 83             x6=x1/bili;
 84             y6=y1/bili;
 85             x7=x2/bili;
 86             y7=y2/bili;
 87             double dist=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
 88             double pp=sqrt(x1*x1+y1*y1);
 89             double ans=9999999;
 90             double sita=(dist/(2*pp));
 91             sita=sqrt(1.0-sita*sita);
 92             if (sqrt(x1*x1+y1*y1)>=r*sita-eps)
 93                 ans=sqrt((x7-x6)*(x7-x6)+(y7-y6)*(y7-y6));
 94             ans=min(ans,sqrt((x4-x1)*(x4-x1)+(y4-y1)*(y4-y1))*2);
 95             ans=min(ans,sqrt((x5-x1)*(x5-x1)+(y5-y1)*(y5-y1))*2);
 96             printf("%.9f
",ans);
 97         }
 98     }
 99     return 0;
100 }
View Code

Problem 1003

hnqw1214:

将A数组按照从大到小排序

对于每个下标i

暴力找到最大的不被i整除的数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<string>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #include<queue>
12 using namespace std;
13 int _,n,a[100010],id[100010];
14 inline bool cmp(int x,int y)
15 {
16     return a[x]>a[y];
17 }
18 int main()
19 {
20     scanf("%d",&_);
21     while (_--)
22     {
23         scanf("%d",&n);
24         int i,j;
25         for (i=1;i<=n;i++)
26         {
27             scanf("%d",&a[i]);
28             id[i]=i;
29         }
30         sort(id+1,id+n+1,cmp);
31         for (i=2;i<=n;i++)
32         {
33             int p=0;
34             for (j=1;j<=n;j++)
35                 if (id[j]%i)
36                 {
37                     p=a[id[j]];
38                     break;
39                 }
40             if (i<n) printf("%d ",p);
41             else printf("%d
",p);
42         }
43     }
44     return 0;
45 }
View Code

cxhscst2:

预处理出ST表。

一个数的答案被很多区间影响

比如4的答案就是[1, 3], [5, 7], [9, 11]这些区间的最小值中的最小值。

区间个数总和数为nlogn。

ST表分段查询即可。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 1e5 + 10;

vector <int> v[N];
int cnt = 0;
int f[N][19];
int a[N];
int n;
int ans[N];
int s, t;
int T;

inline int solve(int l, int r){
	int k = (int)log2((double)(r - l + 1));
	return max(f[l][k], f[r - (1 << k) + 1][k]);
}

void ST(){
	rep(i, 1, n) f[i][0] = a[i];
	rep(j, 1, 20) rep(i, 1, n)
		if ((i + (1 << j) - 1) <= n) f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}


int main(){

	rep(i, 2, 100000){
		for (int j = i; j <= 2e5 + 3; j += i) v[i].push_back(j), ++cnt;
	}

	scanf("%d", &T);
	while (T--){
		scanf("%d", &n);
		rep(i, 1, n) scanf("%d", a + i);
		memset(f, 0, sizeof f);
		ST();
		memset(ans, 0, sizeof ans);
		rep(i, 2, n){
			s = 1;
			for (auto u : v[i]){
				t = u - 1;
				if (s > n) break;
				t = min(t, n);
				ans[i] = max(ans[i], solve(s, t));
				s = u + 1;
			}
		}

		rep(i, 2, n - 1) printf("%d ", ans[i]); printf("%d
", ans[n]);
	}		

	return 0;
}

Problem 1006

考虑每个独立块。

Bob只有在每个独立块大小为2的时候才能赢。

所以当n为奇数的时候直接输出Alice

于是这个问题转化成了树上最大匹配问题。

我们求一遍树上最大匹配，结果为tmp。如果tmp <= k + 1则符合题意，Bob赢。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 1010;

int f[N][2];
vector <int> v[N];
int n, k;
int T;

void dfs(int x){
	for (auto u : v[x]){
		dfs(u);
		int mx = max(f[u][0], f[u][1]);
		f[x][0] += mx;
	}

	for (auto u : v[x]){
		int t = f[x][0] - max(f[u][0], f[u][1]) + f[u][0] + 1;
		f[x][1] = max(f[x][1], t);
	}
}


int main(){

	scanf("%d", &T);
	while (T--){
		scanf("%d%d", &n, &k);
		rep(i, 0, n + 1) v[i].clear();
		rep(i, 2, n){
			int x; scanf("%d", &x);
			v[x].push_back(i);
		}

		if (n & 1){ puts("Alice"); continue; }

		memset(f, 0, sizeof f);
		dfs(1);
		int tmp = max(f[1][0], f[1][1]);
		if (tmp * 2 == n && tmp <= k + 1) puts("Bob");
		else puts("Alice");
	}


	return 0;
}

Problem 1008

枚举一下中心向外延伸

如果和超过了一定的值就弹掉中间的位置

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int inf=(1<<30)-1;
 4 const int maxn=100010;
 5 #define REP(i,n) for(int i=(0);i<(n);i++)
 6 #define FOR(i,j,n) for(int i=(j);i<=(n);i++)
 7 typedef long long ll;
 8 int m;
 9 int T;
10 char s[maxn];
11 int mx=0;
12 
13 void cal(int x,int y)
14 {
15     int l=0,r=0,sum=0;
16     while(y-r>x+r){
17         sum+=abs(s[x+r]-s[y-r]);
18         r++;
19         if(y-l-l-x+1<=2*mx)break;
20         while(sum>m){
21             sum-=abs(s[x+l]-s[y-l]);
22             l++;
23         }
24         mx=max(mx,r-l);
25     }
26 }
27 int main()
28 {
29     scanf("%d",&T);
30     while(T--)
31     {
32         scanf("%d",&m);
33         scanf("%s",s);
34         mx=0;
35         int n=strlen(s);
36         for(int i=n-1;i>0;i--) cal(0,i);
37         for(int i=1;i<n-1;i++) cal(i,n-1);
38         printf("%d
",mx);
39     }
40     return 0;
41 }
View Code

Problem 1011

直接统计即可

不过要判断一下韦恩图的每个部分都是非负数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<string>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #include<queue>
12 using namespace std;
13 int _,n;
14 int a[8];
15 int main()
16 {
17     scanf("%d",&_);
18     while (_--)
19     {
20         scanf("%d",&n);
21         int ans=0;
22         int i,j;
23         for (i=1;i<=n;i++)
24         {
25             int tot=0;
26             bool can=true;
27             for (j=1;j<=7;j++)
28                 scanf("%d",&a[j]);
29             tot+=a[7];
30             if (a[6]>=a[7])
31                 tot+=a[6]-a[7];
32             else
33             {
34                 can=false;
35                 continue;
36             }
37             if (a[5]>=a[7])
38                 tot+=a[5]-a[7];
39             else
40             {
41                 can=false;
42                 continue;
43             }
44             if (a[4]>=a[7])
45                 tot+=a[4]-a[7];
46             else
47             {
48                 can=false;
49                 continue;
50             }
51             if (a[3]>=a[5]+a[6]-a[7])
52                 tot+=a[3]-(a[5]+a[6]-a[7]);
53             else
54             {
55                 can=false;
56                 continue;
57             }
58             if (a[2]>=a[4]+a[5]-a[7])
59                 tot+=a[2]-(a[4]+a[5]-a[7]);
60             else
61             {
62                 can=false;
63                 continue;
64             }
65             if (a[1]>=a[4]+a[6]-a[7])
66                 tot+=a[1]-(a[4]+a[6]-a[7]);
67             else
68             {
69                 can=false;
70                 continue;
71             }
72             if (can) ans=max(ans,tot);
73         }
74         printf("%d
",ans);
75     }
76     return 0;
77 }
View Code

相关推荐