2017 多校联合训练 4 题解

78 阅读 0 评论 52 点赞

我是靠谱客的博主娇气保温杯，最近开发中收集的这篇文章主要介绍2017 多校联合训练 4 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem 1004

直接用数组模拟

为了避免memset

可以一遍正着统计，一遍倒着统计

注意统计的时候不能出现乘除法

不然会T

然后记录一个cnt

cnt大于2e8就跳出

同时有效数字的位数够了也跳出

当然所有的数都不同以及只有2个数相同要特殊处理

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
const double eps=1e-5;
int _,n,a[60010];
int p[60010],q[60010];
int main()
{
scanf("%d",&_);
while (_--)
{
scanf("%d",&n);
int i,j;
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
p[a[i]]=0,q[a[i]]=0;
}
int mx=0,cnt=0;
for (i=1;i<=n;i++)
{
if (q[a[i]])
mx=max(mx,i-q[a[i]]);
else cnt++;
q[a[i]]=i;
}
if (cnt==1)
{
printf("%.9fn",1.0/n);
continue;
}
else if (cnt==2)
{
if (2*(mx-1)<n) printf("%.9fn",2.0/n);
else printf("%.9fn",1.0/(mx-1));
continue;
}
p[a[1]]++;
int fz=1;
double ans=cnt*1.0/n;
cnt=0;
for (i=2;i<=n;i++)
{
int nfz;
if (i&1)
{
if (!p[a[n-i+1]])
fz++;
p[a[n-i+1]]++;
int pre=n;
nfz=fz;
for (j=n-i;j>=1;j--)
{
p[a[pre]]--;
if (!p[a[pre]]) fz--;
if (!p[a[j]]) fz++;
p[a[j]]++;
if (fz<nfz) nfz=fz;
pre--;
cnt++;
if (cnt>2e8) break;
}
}
else
{
if (!p[a[i]]) fz++;
p[a[i]]++;
int pre=1;
nfz=fz;
for (j=i+1;j<=n;j++)
{
p[a[pre]]--;
if (!p[a[pre]]) fz--;
if (!p[a[j]]) fz++;
p[a[j]]++;
if (fz<nfz) nfz=fz;
pre++;
cnt++;
if (cnt>2e8) break;
}
}
double as=nfz*1.0/i;
//cout<<nfz<<" "<<i<<endl;
if (as<ans) ans=as;
if (ans<eps) break;
if (cnt>2e8) break;
}
printf("%.9fn",ans);
}
return 0;
}

View Code

Problem 1005

取

因为一条边可以往返跑2ci

所以如果存在距离为d的方案

那么一定存在距离为d+2w的方案

设f[i][j]为从起点出发到i，距离模2w为j时的最短路

根据f[2][j]解不等式即可

 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 #include<functional>
13 using namespace std;
14 typedef long long ll;
15 typedef pair<ll,int> P;
16 const ll inf=1ll<<62;
17 int _,g[4],st;
18 ll f[4][60001],k;
19 priority_queue<P,vector<P>,greater<P> >q;
20 void upd(int x,int y,ll z)
21 {
22
if (z<f[x][y])
23 
{
24
f[x][y]=z;
25
q.push({z,y<<2|x});
26 
}
27 }
28 int main()
29 {
30
scanf("%d",&_);
31
while (_--)
32 
{
33
scanf("%lld%d%d%d%d",&k,&g[0],&g[1],&g[2],&g[3]);
34
st=min(g[0],g[1])*2;
35
int i,j;
36
for (i=0;i<4;i++)
37
for (j=0;j<st;j++) f[i][j]=inf;
38
upd(1,0,0);
39
while (!q.empty())
40 
{
41
P t=q.top();
42 
q.pop();
43
int x=t.second%4;
44
int y=t.second/4;
45
if (f[x][y]<t.first) continue;
46
upd((x+1)%4,(y+g[x])%st,t.first+g[x]);
47
upd((x+3)%4,(y+g[(x+3)%4])%st,t.first+g[(x+3)%4]);
48 
}
49
ll ans=inf;
50
for (i=0;i<st;i++)
51
if (f[1][i]<k)
52 
{
53
ll sum=f[1][i]+(k-f[1][i])/st*st;
54
while (sum<k) sum+=st;
55
ans=min(ans,sum);
56 
}
57
else
58
ans=min(ans,f[1][i]);
59
printf("%lldn",ans);
60 
}
61
return 0;
62 }

View Code

Problem 1007

度数为1的点匹配方案是唯一的

先拓扑排序去掉所有度数为1的点

剩下的图的每个连痛快是个环

间隔取环上的点


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 typedef long long ll;
 14 const ll mod=998244353;
 15 int _,n,du[600010],p[600100];
 16 bool vis[600010];
 17 vector<pair<int,int>> a[600010];
 18 int get(int x,int y)
 19 {
 20
for (auto u:a[x])
 21
if (u.first==y) return u.second;
 22 }
 23 int main()
 24 {
 25
scanf("%d",&_);
 26
while (_--)
 27 
{
 28
scanf("%d",&n);
 29
int i,j;
 30
for (i=1;i<=2*n;i++)
 31 
a[i].clear();
 32
memset(du,0,sizeof(du));
 33
memset(vis,false,sizeof(vis));
 34
for (i=1;i<=n;i++)
 35
for (j=0;j<2;j++)
 36 
{
 37
int x,y;
 38
scanf("%d%d",&x,&y);
 39
a[i].push_back({x+n,y});
 40
a[x+n].push_back({i,y});
 41
du[i]++;
 42
du[x+n]++;
 43 
}
 44
n<<=1;
 45
queue<int> q;
 46
for (i=1;i<=n;i++)
 47
if (du[i]==1)
 48 
q.push(i);
 49
ll ans=1;
 50
while (!q.empty())
 51 
{
 52
int x=q.front();
 53 
q.pop();
 54
int y;
 55
for (auto u:a[x])
 56
if (!vis[u.first])
 57 
{
 58
y=u.first;
 59
ans=1ll*ans*u.second%mod;
 60
break;
 61 
}
 62
vis[x]=vis[y]=true;
 63
for (auto u:a[y])
 64
if (!vis[u.first])
 65 
{
 66
du[u.first]--;
 67
if (du[u.first]==1)
 68 
q.push(u.first);
 69 
}
 70 
}
 71
for (i=1;i<=n;i++)
 72
if (!vis[i])
 73 
{
 74
vis[i]=true;
 75
int cnt=1;
 76
p[cnt]=i;
 77
int cm=i;
 78
while (true)
 79 
{
 80
bool fg=true;
 81
for (auto u:a[cm])
 82
if (!vis[u.first])
 83 
{
 84
fg=false;
 85
cm=u.first;
 86
break;
 87 
}
 88
if (fg) break;
 89
//cout<<cm<<" ";
 90
vis[cm]=true;
 91
p[++cnt]=cm;
 92 
}
 93
//cout<<endl;
 94
p[cnt+1]=p[1];
 95
ll x=1,y=1;
 96
for (j=1;j<=cnt;j+=2) x=1ll*x*get(p[j],p[j+1])%mod;
 97
for (j=2;j<=cnt;j+=2) y=1ll*y*get(p[j],p[j+1])%mod;
 98
ans=1ll*ans*(x+y)%mod;
 99 
}
100
printf("%lldn",ans);
101 
}
102
return 0;
103 }

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 const char s[10][8][5]=
 14 {{".XX.",
 15
"X..X",
 16
"X..X",
 17
"....",
 18
"X..X",
 19
"X..X",
 20
".XX."},
 21
 22
{"....",
 23
"...X",
 24
"...X",
 25
"....",
 26
"...X",
 27
"...X",
 28
"...."},
 29
 30
{".XX.",
 31
"...X",
 32
"...X",
 33
".XX.",
 34
"X...",
 35
"X...",
 36
".XX.",},
 37
 38
{".XX.",
 39
"...X",
 40
"...X",
 41
".XX.",
 42
"...X",
 43
"...X",
 44
".XX." },
 45
 46
{"....",
 47
"X..X",
 48
"X..X",
 49
".XX.",
 50
"...X",
 51
"...X",
 52
"...."},
 53
 54
{".XX.",
 55
"X...",
 56
"X...",
 57
".XX.",
 58
"...X",
 59
"...X",
 60
".XX.",},
 61
 62
{".XX.",
 63
"X...",
 64
"X...",
 65
".XX.",
 66
"X..X",
 67
"X..X",
 68
".XX.",},
 69
 70
{".XX.",
 71
"...X",
 72
"...X",
 73
"....",
 74
"...X",
 75
"...X",
 76
"...."},
 77
 78
{ ".XX.",
 79
"X..X",
 80
"X..X",
 81
".XX.",
 82
"X..X",
 83
"X..X",
 84
".XX.",},
 85
 86
{ ".XX.",
 87
"X..X",
 88
"X..X",
 89
".XX.",
 90
"...X",
 91
"...X",
 92
".XX.",}
 93 
};
 94 char c[8][22];
 95 void check(int pos)
 96 {
 97
int num,i,j;
 98
for (num=0;num<10;num++)
 99 
{
100
bool ok=true;
101
for (i=0;i<7;i++)
102 
{
103
for (j=pos;j<=pos+3;j++)
104
if (c[i][j]!=s[num][i][j-pos])
105 
{
106
ok=false;
107
break;
108 
}
109
if (!ok) break;
110 
}
111
if (ok)
112 
{
113
printf("%d",num);
114
return;
115 
}
116 
}
117 }
118 int main()
119 {
120
int _;
121
scanf("%d",&_);
122
while (_--)
123 
{
124
int i,j;
125
for (i=0;i<7;i++)
126
scanf("%s",c[i]);
127
check(0);
128
check(5);
129
printf(":");
130
check(12);
131
check(17);
132
printf("n");
133 
}
134
return 0;
135 }

View Code

Problem 1012

f[i][j][k]表示只考虑a，b两个数组，上升下降状态是k的方案数

直接暴力枚举会T

这时可以建立辅助数组g和h

g[i][y][z]表示从f[x][y][z]开始，要更新的是i的方案数

h[i][j][z]表示从f[x][y][z]开始，已经经过g，要更新的是j的方案数

这样每次就只有一个变量在动

 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 int mod=998244353;
14 int _,n,m,a[2010],b[2010];
15 int g[2010][2010][2],h[2010][2010][2];
16 int main()
17 {
18
scanf("%d",&_);
19
while (_--)
20 
{
21
scanf("%d%d",&n,&m);
22
int i,j,k;
23
for (i=1;i<=n;i++) scanf("%d",&a[i]);
24
for (i=1;i<=m;i++) scanf("%d",&b[i]);
25
memset(g,0,sizeof(g));
26
memset(h,0,sizeof(h));
27
int ans=0;
28
for (i=1;i<=n;i++)
29
for (j=1;j<=m;j++)
30
for (k=0;k<2;k++)
31 
{
32
if (a[i]==b[j])
33 
{
34
int t=h[i][j][1-k];
35
if (!k) t=(t+1)%mod;
36
if (t)
37 
{
38
ans=(ans+t)%mod;
39
g[i+1][j][k]=(g[i+1][j][k]+t)%mod;
40 
}
41 
}
42
if (g[i][j][k])
43 
{
44
g[i+1][j][k]=(g[i+1][j][k]+g[i][j][k])%mod;
45
if (!k)
46 
{
47
if (a[i]>b[j])
48
h[i][j+1][k]=(h[i][j+1][k]+g[i][j][k])%mod;
49 
}
50
else
51 
{
52
if (a[i]<b[j])
53
h[i][j+1][k]=(h[i][j+1][k]+g[i][j][k])%mod;
54
55 
}
56 
}
57
if (h[i][j][k]) h[i][j+1][k]=(h[i][j+1][k]+h[i][j][k])%mod;
58 
}
59
printf("%dn",ans);
60 
}
61
return 0;
62 }