AtCoder Beginner Contest 070|Elena|8.12|#471

打了场beginner的AtCoder，也是我第一次打AtCoder，虽然AK了，但是由于手速慢+撒比，才#471…

比赛链接：https://beta.atcoder.jp/contests/abc070

T1.题意：给一个三位数，判断是否回文

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 int read()
 8 {
 9     int f=1,x=0; char c=getchar();
10     while (c>'9'||c<'0') {if (c=='-') f=-1; c=getchar();}
11     while (c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
12     return x*f;
13 }
14 int main()
15 {
16     int N=read();
17     int a,b,c;
18     a=N%10,c=N/100;
19     if (a==c) printf("Yes
");
20     else printf("No
");
21     return 0;
22 }

T2.题意：给两个区间，计算两个区间交错长度

如 20 40 10 50 答案就是20，数据很小，怎么写都行。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 int read()
 8 {
 9     int f=1,x=0; char c=getchar();
10     while (c>'9'||c<'0') {if (c=='-') f=-1; c=getchar();}
11     while (c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
12     return x*f;
13 }
14 int A,B,C,D;
15 int main()
16 {
17     A=read(); B=read(); C=read(); D=read(); int c=0;
18     if (A>B) {
19         int t=A;
20         A=B;
21         B=t;
22     }
23     if (C>D) {
24         int t=C;
25         C=D;
26         D=t;
27     }
28     for (int i=A; i<=B; i++)
29     if (i>=C && i<=D) c++;
30     if (c!=0) c--;
31     printf("%d
",c);
32     return 0;
33 }

T3.题意：求N个数的最小公倍数

注意使用long long，数据达到10^18，但是我们只要开一个long long的S，然后for (int i=2; i<=N; i++) 读入A 再 S=S/gcd(S,A)*A 就可以得到1-i的最小公倍数，而且由于除的早，所以不会

爆long long。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 long long read()
 8 {
 9     long long f=1,x=0; char c=getchar();
10     while (c>'9'||c<'0') {if (c=='-') f=-1; c=getchar();}
11     while (c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
12     return x*f;
13 }
14 long long gcd(long long A,long long B)
15 {
16     if (A%B==0) return B;
17     return gcd(B,A%B);
18 }
19 long long ANS;
20 long long A,B,N,S;
21 int main()
22 {
23     N=read();S=read();
24     for (int i=2; i<=N; i++) {
25         A=read();
26         S=S/gcd(S,A)*A;
27     }
28     printf("%lld
",S);
29     return 0;
30 }

T4.题意：给一棵有N个节点的树，再给每两个节点之间的距离，给出一个点K，再给一个点Q表示Q次询问，接下来输入Q组X和Y，对于每组X和Y，输出X到Y经过K的最短距离。

盲目地拼老命DFS或最短路会挂得特别难看…

因为要求经过K点，我们可以换个思路：强制K为根，然后DFS一遍，求出根（K）到其他节点的最短路径，对于每次询问，再输出DIS[X]+DIS[Y]就可以了。因为只要DFS一次而且每个节

点只访问一次，所以不会TLE。对于树，我仍然拿边表存储。

当然更多的大佬选择了LCA。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<cstdlib>
 5 using namespace std;
 6 int head[101000],NUM_EDGE;
 7 bool BOOK[101000];
 8 long long DIS[101000];
 9 struct edge
10 {
11     int TO;
12     int NEXT;
13     int DIS;
14 }EDGE[201000];
15 void ADD(int FROM,int TO,int DIS)
16 {
17     EDGE[++NUM_EDGE].NEXT=head[FROM];
18     EDGE[NUM_EDGE].TO=TO;
19     EDGE[NUM_EDGE].DIS=DIS;
20     head[FROM]=NUM_EDGE;
21 }
22 int read()
23 {
24     int x=0,f=1; char c=getchar();
25     while (c>'9'||c<'0') {if (c=='-') f=-1; c=getchar();}
26     while (c>='0'&&c<='9') {x=x*10+(c-'0'); c=getchar();}
27     return x*f;
28 }
29 void DFS(int X) {
30     for (int i=head[X]; i; i=EDGE[i].NEXT)
31     if (BOOK[EDGE[i].TO]==0) {
32         BOOK[EDGE[i].TO]=1;
33         DIS[EDGE[i].TO]=DIS[X]+EDGE[i].DIS;
34         DFS(EDGE[i].TO);
35     }
36 }
37 int N,Q,K,U,V,W,X[101000],Y[101000],INF=111199999,MIN;
38 int main()
39 {
40     N=read();
41     for (int i=1; i<=N-1; i++) {
42         U=read(); V=read(); W=read();
43         ADD(U,V,W); ADD(V,U,W);
44     }Q=read(); K=read();
45     BOOK[K]=1;
46     DFS(K);        
47     for (int i=1; i<=Q; i++) {
48         X[i]=read(); Y[i]=read(); printf("%lld
",DIS[X[i]]+DIS[Y[i]]);
49     }
50     return 0;
51 }