2017ICPC沈阳区域赛部分题解

周日打的重现赛,感觉要是细心一点说不定就进金牌区了。

A.BBP Formula

B.Bridge

C.Empty Convex Polygons

D.Defense of the Ancients

E.Five-round Show Hand

F.Heron and His Triangle

题目大意:给你一个$n$,让你找出数字大于等于$n$的最小整数$t$,使得以长度为$t-1,t,t+1$的三条边所构成的三角形面积为整数。

首先使用海伦公式化简出三角形面积通项公式:

$p=\frac{t-1+t+t+1}{2}=\frac{3t}{2}$
$p-a=\frac{3t}{2}-(t-1)=\frac{t+2}{2}$
$p-b=\frac{3t}{2}-t=\frac{t}{2}$
$p-c=\frac{3t}{2}-(t+1)=\frac{t-2}{2}$
$S=\sqrt{p*(p-a)*(p-b)*(p-c)}=\sqrt{\frac{3*t^2*(t^2-1)}{16}}$

因此我们只需要找到符合条件的$t$的整数解即可。暴力打出前几项就会发现其通项公式为$f(i+1)=4f(i)-f(i-1)$。由于数据范围较大,因此使用__int128来存储。

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
#include<bits/stdc++.h>

using namespace std;
__int128 res[61];
void print(__int128 x){
if(x==0){
puts("0");
return ;
}
vector<int> ans;
while(x){
ans.push_back(x%10);
x/=10;
}
reverse(ans.begin(),ans.end());
for(int v:ans) printf("%d",v);
puts("");
}
int main(){
res[1]=4;
res[2]=14;
res[3]=52;
for(int i=4;i<=60;i++){
res[i]=res[i-1]*4-res[i-2];
}
int T;
cin>>T;
while(T--){
string s;
cin>>s;
__int128 now=0;
int l=(int)s.length();
for(int i=0;i<l;i++){
now=now*10+s[i]-'0';
}
for(int i=1;i<=60;i++){
if(res[i]>=now){
print(res[i]);break;
}
}
}
return 0;
}

G.Infinite Fraction Path

题目大意:王国有$n$个城市标号为$0到n-1$,每个城市都有一个值$D[i]$,第$i$座城市可以到达第$(i^2+1)\space mod \space n$座城市。每到达一个城市你就会按顺序得到这座城市的$D[i]$值。问你能获得的最大的长度为$n$的数字串为多少。

BFS+剪枝。首先我们的起点一定要尽可能的大,找出所有的起点后计算出每个起点接下来所达到的城市的$D[i]$值,从中挑选出$D[i]$值最大的一部分继续BFS,不符合条件的直接删去。这样能够保证剩下的一部分中所有的目前的前缀完全相同。

由于这个跳转方法是固定的,因此能够猜测出图中每个环的大小不会太大,因此当我们BFS到一定层数之后,就可以直接跳出循环,此时队列中剩下的解均为最优解。

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;
#define ll long long
const int N = 1e6+100;
struct node{
ll start,pos;
};
char s[N];
ll a[N],vis[N];
ll n;
ll cal(ll x){ return (x*x+1)%n; }
ll bfs(){
for(ll i=0;i<n;i++) vis[i]=0;
queue<node>que,mid;
queue<ll>flag;
ll cur=0,num=0;
//计算起点
for(ll i=0;i<n;i++) cur=max(cur,a[i]);
for(ll i=0;i<n;i++) if(a[i]==cur) {
que.push({i,i});
num++;
}
if(num==1) return que.front().start;
ll times=0;
while(!que.empty()){
//判断循环次数
if(num!=que.size()) num=que.size(),times=0;
else if(times>=100000) break;
else times++;
//找出下一步的最优解
cur=0;
while(!que.empty()){
node x=que.front();
mid.push(x);
que.pop();
cur=max(cur,a[cal(x.pos)]);
}
//筛选出最优解
while(!mid.empty()){
if(mid.size()+que.size()==1){
if(mid.size()==1) return mid.front().start;
else return que.front().start;
}
node x=mid.front();
mid.pop();
if(a[cal(x.pos)]==cur && !vis[cal(x.pos)]){//若到达一个点有多条路径,只需保留一条即可
flag.push(cal(x.pos));
vis[cal(x.pos)]=1;
x.pos=cal(x.pos);
que.push(x);
}
}
//清空标记
while(!flag.empty()){
vis[flag.front()]=0;
flag.pop();
}
}
return que.front().start;
}
int main(){
ll T;
scanf("%lld",&T);
for(ll t=1;t<=T;t++){
scanf("%lld",&n);
scanf("%s",s);
for(ll i=0;i<n;i++) a[i]=s[i]-'0';
printf("Case #%d: ",t);

ll ans=bfs();
for(ll i=0;i<n;i++){
printf("%c",s[ans]);
ans=cal(ans);
}
printf("\n");
}
return 0;
}

H.Legends of the Three Kindoms

I.Little Boxes

题目大意:四个数求和。

直接计算即可,由于数据范围超过$long long$,因此需要__int128去计算。

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;
void print(__int128 x){
if(x==0){
puts("0");
return ;
}
vector<int> ans;
while(x){
ans.push_back(x%10);
x/=10;
}
reverse(ans.begin(),ans.end());
for(int v:ans) printf("%d",v);
puts("");
}
int main(){
int T;
scanf("%d",&T);
while(T--){
long long a[5];
__int128 ans=0;
for(int i=1;i<=4;i++){
scanf("%lld",&a[i]);
ans+=a[i];
}
print(ans);
}
return 0;
}

J.New Self-describing Sequence

K.Rabbits

题目大意:$n$只兔子在河边玩耍,他们处在一条数轴上,每个兔子都有一个不重复的坐标,每只最外层的兔子都能够跳进其他任意两个相邻的兔子中间的空间(同一格子中只能有一只兔子),问$n$只兔子总共能走的步数最多为多少。

走的最多的一只兔子一定为最左或最右边的一只兔子。对于第一只兔子,他能够移动第二只到第$n$只任意一个位置,但是只有移动到第二只后第一个空格处为最优解,接下来就可以以同样的方法连续的遍历第二只到第$n$只之间所有位置,同理移动第n只也是一样的方法。因此移动的步数即为所有的空格数减去第一只到第二只或第$n-1$只到第$n$只之间的空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>

using namespace std;
int a[10000+10];
int main(){
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
//所有空格数减去两只兔子间的空格数
printf("%d\n",(a[n]-a[1]+1-n)-min((a[2]-a[1]-1),a[n]-a[n-1]-1));
}
return 0;
}

L.Tree

题目大意:给你一个有$n$个节点的树。有$k$种颜料可以将每个节点染色。定义$E_i$为染第$i$种颜色的节点所形成的最小生成树的边集(可以为空)。问$E_1 \bigcap E_2 \bigcap … \bigcap E_k$的边的数量为多少。

随便找一个根节点,可以形成一个树,对于每个节点,若它所在的的子树的节点个数大于等于$k$且这棵子树之外点的个数也大于等于$k$,那么连接这个节点的边一定能够被染色,因此只需要一次DFS计算出字数大小然后循环判断即可。

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
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
vector<int> G[N];
int siz[N];
void dfs(int u,int fa){
siz[u]=1;
for(int v:G[u]){
if(v==fa) continue;
dfs(v,u);
siz[u]+=siz[v];
}
}
int u,v;
int main(){
int T;scanf("%d",&T);
while(T--){
int n,k;
int ans=0;
int u,v;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=n-1;i++){
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++){
if(siz[i]>=k&&n-siz[i]>=k) ans++;
}
printf("%d\n",ans);
}
return 0;
}

M.Wandering Robots

题目大意:在一个$n*n$的方格中,有$k$个障碍物,清洁机器人从$(0,0)$出发,以相同的概率走到相邻的任意一个可达格子或者留在原地。问无穷步之后,清洁机器人所在的位置$(x,y)$满足$x+y \geq n-1$的概率为多少(输出答案格式为$p/q$)。

从$x+y \geq n-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
#include<bits/stdc++.h>
using namespace std;

map<pair<int, int>, bool> vis;
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T, kase = 1;
cin >> T;
while (T--) {
int n, k, x, y;
vector<pair<int, int> > v;
cin >> n >> k;
int up = 9 + 2 * ( n-2) * 4 + (n-1)*(n-2)/2*5, down = 12 + 4 * ( n-2) * 4 + (n-2)*(n-2)*5;
for(int i = 1; i <= k; ++i) {
cin >> x >> y; x++; y++;
vis[{x,y}] = 1;
v.push_back({x, y});
if(x == 1 && y == n) up -= 3, down -= 3;
else if(x == 1 && y == 1) down -= 3;
else if(x == n && y == 1) up -= 3, down -= 3;
else if(x == n && y == n) up -= 3, down -= 3;
else if(x == 1 || y == 1) down -= 4;
else if(x == n || y == n) up -= 4, down -= 4;
else if(x + y >= n + 1) up -= 5, down -= 5;
else down -= 5;
}
for(pair<int, int> p: v){
x = p.first, y = p.second;
if(x + 1 <= n && vis[{x+1,y}] == 0) {
down--;
if(x + 1 + y >= n + 1) up--;
}
if(x-1 >= 1 && vis[{x-1,y}] == 0) {
down--;
if(x - 1 + y >= n + 1) up--;
}
if(y-1 >= 1 && vis[{x,y-1}] == 0) {
down--;
if(x + y - 1 >= n + 1) up--;
}
if(y + 1 <= n && vis[{x,y+1}] == 0) {
down--;
if(x + y + 1 >= n + 1) up--;
}
}
int g = __gcd(up, down);
up /= g; down /= g;
cout << "Case #" << kase++ << ": ";
cout << up << "/" << down << endl;
vis.clear();
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------