SUST_2018 焦作站亚洲区域赛校内选拔赛 题解

SUST_2018 焦作站亚洲区域赛校内选拔赛

A、高速        by yoyo

tag:图论、最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//最短路
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 0x3f3f3f3f;
const int maxn = 1e5+7;
int t,n,m,cnt;
int dis[maxn]; //当前该点到原点最短距离
bool vis[maxn]; //是否访问过
int head[maxn]; //点集
struct EDGE{
int next,to,w,l,r; //上一条边,下一个点,权值,左值,右值
}edge[2*maxn]; //边集
struct NODE{
int u,dis;
NODE(){}
NODE(int u,ll w):u(u),dis(w){}
bool operator <(const NODE &a)const{
return dis>a.dis;
}
}node[2*maxn]; //点集加最短距离
void add(int u, int v, int w, int l,int r){ //构建边集
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].l = l;
edge[cnt].r = r;
head[u] = cnt;
cnt++;
}
void init(){ //初始化
cnt = 0;
memset(head,-1,sizeof(head));
memset(dis,maxx,sizeof(dis));
memset(vis,false,sizeof(vis));
}
void read(){ //读入数据
int u,v,w,l,r;
scanf("%d%d",&n,&m);
for(int i = 0;i < m; i++){
scanf("%d%d%d%d%d",&u,&v,&w,&l,&r);
add(u,v,w,l,r);
add(v,u,w,l,r);
}
}
void init_data(int kk){ //初始化数据
vis[kk] = false;
dis[kk] = maxx;
}
int solve(int s){
priority_queue<NODE>q; //储存最短距离
q.push(NODE(s,0)); //读入原点
while(!q.empty()){ //队列为空则无法到达
int kk = q.top().u; //储存当前最短距离下标
int minD = q.top().dis; //储存当前最短距离
q.pop();
if(kk==n) //若下标为目标值,return
return minD;
vis[kk] = true; //该点是否访问
for(int l = head[kk]; l!=-1; l=edge[l].next){ //松弛边
if(!vis[edge[l].to]&&minD<=edge[l].r&&minD>=edge[l].l&&minD + edge[l].w < dis[edge[l].to]){
dis[edge[l].to] = minD + edge[l].w;
q.push(NODE(edge[l].to,dis[edge[l].to])); //将松弛后的边压入队列
}
}
init_data(kk); //初始化数据
}
return 0;
}
int main(){
scanf("%d",&t);
while(t--){
init(); //初始化
read(); //读入
printf("%d\n",solve(1)); //解决方案
}
return 0;
}

B、Outlook        by 紫芝

tag:计算几何、最短路

本题可以看出是计算几何 + 最短路问题,最重要的只是对图进行建模。
所以我们考虑在图上抠出特殊点,来跑最短路。
特殊点包括墙的两端之类的。
但是由于某些原因,此题并没有完成。

C、千年老二        by yoyo

tag:图论、生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//次小生成树
#include<bits/stdc++.h>
using namespace std;
const int L=1e5+7;
const int inf=0x3f3f3f3f;
const int maxn=1000+7;
int father[maxn],n,m,num[maxn],nPos; //父节点(并查集),点数,边数,最小生成树点集,当前访问方位
struct node{
int s,y,w;
}edge[L]; //边集,左端点,右端点,权值
void init(){ //初始化并查集
for(int i=0;i<=n;i++)
father[i]=i;
}
int root(int x){ //并查集,构造父节点
return father[x]==x?x:father[x]=root(father[x]);
}
void unite(int x,int y){ //并查集,合并两个联通图
x=root(x);
y=root(y);
if(x!=y)
father[y]=x;
}
int alike(int x,int y){ //并查集,判断是否为同一连通图
return root(x)==root(y);
}
int cmp(node a,node b){ //sort结构体排序
return a.w<b.w;
}
int secondTree(int pos) //次小生成树
{
init(); //初始化
int sum=0,cnt=0;
for(int i=0;i<m;i++) //对于删去边后的图进行最小生成树运算
{
if(cnt==n-1)
break;
if(i==pos)
continue;
if(!alike(edge[i].s,edge[i].y)){
unite(edge[i].s,edge[i].y);
sum+=edge[i].w;
cnt++;
}
}
return cnt!=n-1?-1:sum; //判断删除边后是否能构成最小生成树
}
int kruskal(){ //最小生成树
init();
sort(edge,edge+m,cmp); //对边进行权值排序
int sum=0,cnt=0;
for(int i=0;i<m;i++) //每次选择最小且未访问过的一条边
{
if(cnt==n-1)
break;
if(!alike(edge[i].s,edge[i].y)){
unite(edge[i].s,edge[i].y);
sum+=edge[i].w;
cnt++;
num[++nPos]=i;
}
}
return cnt!=n-1?-1:sum; //判断边是否大于等于n-1,否则输出-1
}
void read(){ //读入数据
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d%d%d",&edge[i].s,&edge[i].y,&edge[i].w);
}
void solve(){ //解决方案
int Min=inf;
nPos=0;
int mst=kruskal(); //最小生成树值
if(mst==-1) { //没有最小生成树即输出-1
printf("-1\n");
return;
}
for(int i=1;i<=nPos;i++){ //对最小生成树的每条边进行遍历,选择删边后的最小值
int secmst=secondTree(num[i]);
if(secmst!=-1) //若没有次小生成树输出-1
Min=min(Min,secmst);
}
if(Min!=inf&&Min!=mst)
printf("%d\n",Min); //输出结果
else
printf("-1\n");
}
int main(){
int t;
scanf("%d",&t);
while(t--){
read(); //读入数据
solve(); //解决方案
}
return 0;
}
`

D、秋雨绵绵        by 紫芝

tag:高精度、模拟

但是由于数据范围过大,我们用普通乘法会爆精度,因此我们需要用到特殊的乘法 —— 快速乘
然后直接暴力递推相乘即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ksc(ll x,ll y,ll mod)
{
return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;
}
ll m0,m1,c,M,k;
ll a0,a1;
int main()
{
int ca=0;
int T;
scanf("%d",&T);
while(T--){
printf("case #%d:\n",++ca);
scanf("%lld%lld%lld%lld%lld%lld%lld",&a0,&a1,&m0,&m1,&c,&k,&M);
ll ans=ksc(a0,a1,M);
ll a2;
for(int i=2;i<=k;i++)
{
a2=((ksc(m0,a1,M)+ksc(m1,a0,M))%M+c)%M;
ans=ksc(ans,a2,M);
a0=a1;
a1=a2;
}
printf("%lld\n",a2);
printf("%lld\n",ans);
}
return 0;
}

E、RMB 游戏        by 紫芝

tag:简单思维题

简单题,不解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
   #include<stdio.h>
#include<algorithm>
using namespace std;
const int N=2505;
int a[N];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
{
k-=i;
if(k<=0){
printf("%d\n",a[i]);
break;
}
}
}
return 0;
}

F、给力台球厅        by yoyo

tag:图论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//网络流
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f; //无穷大
const int maxn = 60007;
const int maxm = 1000007;
int vis[maxn],d[maxn],pre[maxn],a[maxn],m,n; //是否访问,最短路,前置节点,流量,边集,点集
char mp[107][107]; //台球地图
struct Edge{
int u, v, c, cost, next;
}edge[maxm]; //网络流边集

int s[maxn], cnt; //每个点流量

void init(){ //初始化
cnt = 0;
memset(s, -1, sizeof(s));
}

void add(int u, int v, int c, int cost){ //对两点之间进行单向边建立
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].cost = cost;
edge[cnt].c = c;
edge[cnt].next = s[u];
s[u] = cnt++; //建立单向边
edge[cnt].u = v;
edge[cnt].v = u;
edge[cnt].cost = -cost;
edge[cnt].c = 0;
edge[cnt].next = s[v];
s[v] = cnt++; //建立双向边
}

bool spfa(int ss, int ee,int &flow,int &cost){ //以距离为费用寻找最短路,以最短路为当前增广路
queue<int> q;
memset(d, INF, sizeof d);
memset(vis, 0, sizeof vis); //初始化
d[ss] = 0, vis[ss] = 1, pre[ss] = 0, a[ss] = INF;
q.push(ss);
while (!q.empty()){ //spfa以费用为距离寻找最短路
int u = q.front();q.pop();
vis[u] = 0;
for (int i = s[u]; ~i; i = edge[i].next){ //和当前点相连所有边松弛过程
int v = edge[i].v;
if (edge[i].c>0&& d[v]>d[u] + edge[i].cost){ //松弛过程
d[v] = d[u] + edge[i].cost;
pre[v] = i;
a[v] = min(a[u], edge[i].c); //取最小值
if (!vis[v]){
vis[v] = 1;
q.push(v); //压入待松弛队列
}
}
}
}
if (d[ee] == INF) return 0; //判断是否有最短路,无说明最大流完成
flow += a[ee];
cost += d[ee]*a[ee];
int u = ee;
while (u != ss){ //求当前最短路下的流量和
edge[pre[u]].c -= a[ee];
edge[pre[u] ^ 1].c += a[ee];
u = edge[pre[u]].u;
}
return 1;
}

int MCMF(int ss, int ee){ //最小费用最大流
int cost = 0, flow=0; //初始化
while (spfa(ss, ee, flow, cost)); //寻找增广路径,直到没有增广路径为止
return cost; //返回最大流费用
}

struct point{
int x,y; //球坐标,洞坐标
};

void solve(){
point H[107],P[107]; //建立球集与洞集
int h=0,p=0;
for(int i=0;i<n;i++){ //输入地图
scanf("%s",&mp[i]);
for(int j=0;j<m;j++){
if(mp[i][j]=='#'){ //若为洞则坐标加入洞集
H[h].x=i;
H[h].y=j;
h++;
}
else if(mp[i][j]=='@'){ //若为球则坐标加入球集
P[p].x=i;
P[p].y=j;
p++;
}
}
}
init(); //初始化
for(int i=0;i<h;i++)
for(int j=0;j<p;j++){
int c=fabs(H[i].x-P[j].x)+fabs(H[i].y-P[j].y);
add(i+1,h+j+1,1,c);
} //建立球与洞之间的路径
for(int i=0;i<h;i++) //建立超级源点
add(0,i+1,1,0);
for(int i=0;i<p;i++) //建立超级汇点
add(h+1+i,h+p+1,1,0);
printf("%d\n",MCMF(0,h+p+1)); //最小费用最大流
}

int main(){
while(~scanf("%d%d",&n,&m)){
if(!(m||n))
break;
solve(); //解决方案
}
return 0;
}

G、营救教练计划        by Amon

tag:动态规划、概率DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 一道简单的期望dp~希望大家喜欢~
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn = 1e5 + 10;
double dp[maxn];

int main(int argc, const char * argv[]) {
int n, m, x, y;
while (~scanf("%d%d", &n, &m)) {
// 初始化 dp 数组为0
memset(dp, 0, sizeof(dp));
// 用 map 存储所有的跳跃点
map<int, int> mp;
for (int i = 0; i < m; ++i) {
scanf("%d%d", &x, &y);
mp[x] = y;
}
// dp[i] 存储从第i个位置到 n 需要飞多长时间的数学期望
// n 位置当然是 0 啦
// 注意,n 后面的几个位置也是0
dp[n] = 0;
for (int i = n - 1; i >= 0; --i) {
if (mp.find(i) != mp.end()) {
// 如果 i 位置可以直接飞到后面某个位置,那么他们的期望是相同的
dp[i] = dp[mp[i]];
} else {
// 枚举后面七个位置,注意,n 后面的都是0
// dp[i] = dp[i+1]/7 + dp[i+2]/7 + dp[i+3]/7 + dp[i+4]/7 + dp[i+5]/7 + dp[i+6]/7 + dp[i+7]/7 + 1
double sum = 0;
int num = 0;
for (int j = i + 1; num < 7; ++j, ++num) {
sum += dp[j] + 1;
}
dp[i] = sum / num;
}
}
printf("%.4lf\n", dp[0]);
}
return 0;
}

H、有种放学别走        by huawei

tag:组合数学、卡特兰数

题目中需要找到正 $2N$ 边形中,两个顶点连线且线段互不相交的方案数。实际上就是组合数学中的卡特兰数
但是即便不知道何为卡特兰数,结论也非常明显。
假设正 $2N$ 边形中一个点和另一个点连线,此时的多边形被分为了两个部分,此时方案数为 [左边多边形连线的方案数] * [右边多边形连线的方案数] 。而一个点连线的方案有 $N$ 种。因此我们可以得出递推式:
假设 $F[n]$ 表示 $2n$ 边形连线的方案数,再加上题目的模,即

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
const int maxn = 1010;
typedef long long LL;
const int mod = 19260817;
LL f[maxn], n;
void init() {
f[0] = f[1] = 1;
for (int i = 2; i < maxn; i++) {
for (int j = 0; j < i; j++) {
f[i] = (f[i] + f[j] * f[i - j - 1])%mod;
}
}
}
int main()
{
init();
while (scanf("%lld", &n) != EOF) {
printf("%lld\n", f[n]);
}

return 0;
}

I、单身狗的寻觅        by huawei

tag:贪心

此题是结论明显的贪心题。
结论:对于每一个人,和他前面的人匹配(如果是异性的情况下),否则不匹配。
对于某一个人而言:
1.如果他能匹配前一个异性,那么他匹配了前面的异性,匹配对数 $+1$,如果他不匹配,他被后面匹配,也是对数 $+1$,即匹配前一个人对后续匹配没有不良影响。相反,如果前一个人可以匹配但却去匹配后一个人,可能对后面匹配产生不良影响。
2.如果他前面无法匹配,但可以匹配后一个人,那会在下一轮判断中,被后一个人匹配。
3.如果他完全不能匹配,不匹配对结果完全没有影响。
但是由于题目数据较多,最大为 $10^8$,所以不能使用数组离线解决,但是我们发现此题结果只与前一个人有关,因此我们可以考虑在线算法。
题解的做法使用了栈,更简便的可以直接int last;来记录前一个人的性别。
此题也有更多做法可以挖掘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, x, last;
while (scanf("%d", &n) != EOF) {
last = -1;
int ans = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &x);
if (last == -1) {
last = x;
} else {
if((x%2 + last%2) == 1) {
ans++;
last = -1;
} else {
last = x;
}
}
}
printf("%d\n", ans);
}
return 0;
}

J、共产主义接班人        by huawei

tag:线段树,模拟

首先我们可以简化题目要求,即对于每一天,都需要查询一个小于等于当前爱心指数的最右边的家庭,然后记录个数。
因此我们可以考虑用线段树维护区间家庭操心指数的最小值,查询函数的返回值为最右端的不大于当前爱心指数的家庭编号。即对于每一个树枝节点,我们优先比较右儿子和当前爱心指数的大小,如果右儿子小于等于爱心指数,则说明不大于当前爱心指数的最右的点位于当前区间的右子区间。如果右儿子比爱心指数大,但左儿子小,说明在左边。否则,说明不存在比当前爱心指数小的值。
而且在每一次查询后,已经帮助过的家庭的操心指数要设置为 $INF$,防止重复查询。
接下来就是每天的模拟操作,只需要把每天的帮助家庭户数记录下来,对于每个询问就可以 $O(1)$ 查询了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3fffffff;
const int maxn = 1e5 + 10;
LL a[maxn], segtree[maxn << 4], n, m, c, cnt, num, day;
LL b[maxn], ans[maxn];

void pushup(int now) {
segtree[now] = min(segtree[now << 1], segtree[(now << 1)|1]);
}

void build_tree(int l, int r, int now) {
if (l == r) {
segtree[now] = a[l];
return;
}
int mid = (l + r)/2;
build_tree(l, mid, now << 1);
build_tree(mid + 1, r, (now << 1)|1);
pushup(now);
}

int query(int l, int r, int tar, int now) {
if (l == r) {
segtree[now] = INF;
return l;
}
int mid = (l + r)/2, ans = -1;
if (segtree[(now << 1)|1] <= tar) ans = query(mid + 1, r, tar, (now << 1)|1);
else if (segtree[now << 1] <= tar) ans = query(l, mid, tar, now << 1);
pushup(now);
return ans;
}

int main()
{
int T;
scanf("%d", &T);
while (T--) {
memset(segtree, 0, sizeof segtree);
memset(ans, 0, sizeof ans);
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
cnt = num = day = 0;
scanf("%lld %lld %lld", &n, &m, &c);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
build_tree(1, n, 1);
while (num < n) {
cnt += c; day++;
int k = query(1, n, cnt, 1);
while (k != -1) {
ans[day]++;
cnt -= a[k];
k = query(1, n, cnt, 1);
}
num += ans[day];
}
for (int i = 0; i < m; i++) {
scanf("%lld", &c);
printf("%lld\n", c > day? 0 : ans[c]);
}
}

return 0;
}

K、66..6        by Amon

tag:数论。欧拉函数、欧拉定理

设输入的数字为 $p$,即题目的要求得一个长度为 $x$ 的 $66…6$,使得 $66…6 = kp\ (k\in Z)$。
可以发现,长度为 $x$ 的 $66…6$ 可以表示为 $\frac{6(10^x - 1)}{9}$。
所以我们可以得到式子

为了可以继续化简,我们假设 $g = gcd(6,9p)$,两边同除 $g$。得

此时$\frac{6}{g}$ 与 $\frac{9kp}{g}$ 互质,式子可简化为
即求解
根据欧拉定理可知,最小的 $x$ 存在于 $\varphi(\frac{9kp}{g})$ 的因子中,接下来的任务就是枚举所有 $\varphi(\frac{9kp}{g})$ 的因子,从而找到一个最小的 $x$ 满足 $10^x ≡ 1\ (mod\ \frac{9kp}{g})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// sustoj 1908
#include <cstdio>
#include <cmath>
#include <time.h>
#include <cstdlib>
using namespace std;
typedef long long LL;

// 求解欧拉函数
LL phi(LL x) {
LL ans = x;
for (LL i = 2; i * i <= x; ++i) {
if (x % i == 0) {
ans = ans / i * (i - 1);
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
ans = ans / x * (x - 1);
}
return ans;
}

// 快速乘
LL multi(LL a, LL b, LL mod) {
LL ret = 0;
while (b) {
if (b & 1) {
ret = (ret + a) % mod;
}
a = (a << 1) % mod;
b >>= 1;
}
return ret;
}

// 快速幂
LL fastpow(LL a, LL b, LL p) {
LL ans = 1;
while (b) {
if (b & 1) {
ans = multi(ans, a, p);
}
a = multi(a, a, p);
b >>= 1;
}
return ans;
}

// 求解最大公约数
LL gcd(LL a, LL b) {
return b == 0 ? a : gcd(b, a % b);
}

int main() {
LL p;
int ca = 1;
while (~scanf("%lld", &p) && p) {
printf("Case %d: ", ca++);
p /= gcd(p, 6);
// p 和 6 有最大公约数,先约去这个数,此时原题变为了 111...111 可以被 p 整除
p *= 9;
// 此时原题变为了 999...999 可以被 p 整除,即 100...000 - 1 可以被 p 整除
// 也就是说,100...000 % p 余 1,求最少有多少个 0
// 已知以下定理:
// 若正整数 a, p 互质,则满足 a ^ x ≡ 1 (mod p) 的最小的正整数 x0, 是 φ(p) 的约数(因子)。
// φ(p) 为 欧拉函数,即 10^x ≡ 1 (mod p) 的最小的正整数解是 φ(p) 的因子

if (gcd(p, 10) == 1) {
// 互质
LL ans = phi(p); // 欧拉函数
LL i = 0;
int f = 0;
LL tmp = sqrt(ans);

// 下面这样求主要是将 O(n) 变为 O(根号n)
// ans = φ(p),求 ans 的因子
for (i = 1; i * i <= ans; ++i) {
// 解在 1 - sqrt(ans) 内
if (ans % i == 0) {
if (fastpow(10, i, p) == 1) {
f = 1;
break;
}
}
}
if (f) {
printf("%lld\n", i);
} else {
// 解在 sqrt(ans) - ans 内
for (i = tmp; i >= 1; --i) {
if (ans % (ans / i) == 0) {
if (fastpow(10, ans / i, p) == 1) {
break;
}
}
}
printf("%lld\n", ans / i);
}

} else {
// 不互质,则无解
printf("-1\n");
}
}
return 0;
}