考试总结 2018-6-12
分类:
IT文章
•
2022-06-15 14:13:00
这次考试我能不能说还算满意。。
第一题是寻找和最小的两个因子，输出二倍的和。那肯定是在根号两边了，图省事就写了个
虽然也正确，但是不是最好的解法。如果从根号s+1向下循环的话肯定比向上走%起来快，于是丢了10分。被称为灵魂A题。。。难过
![]()
1 #include <cstdio>
2 #include <iostream>
3 #include <cmath>
4 #include <string>
5 #include <cstring>
6 #include <algorithm>
7 using namespace std;
8 inline void write(int x)
9 {
10 if(x>9) write(x/10);
11 putchar(x%10+'0');
12 }
13 inline int read()
14 {
15 int x=0;
16 char ch=getchar();
17 while(ch>'9'||ch<'0')
18 ch=getchar();
19 while(ch>='0'&&ch<='9')
20 {
21 x=(x<<1)+(x<<3)+ch-'0';
22 ch=getchar();
23 }
24 return x;
25 }
26 int t,s,i,f;
27 int main()
28 {
29 //freopen("123.in","r",stdin);
30 //freopen("123.out","w",stdout);
31
32 for(t=read();t>0;t--)
33 {
34 s=read();
35 for(f=int(sqrt(double(s)))+1;;f--)
36 if(s%f==0)break;
37 write((f+s/f)*2);
38 putchar(10);
39 }
40 }
t1
第二题也比较简单，毕竟找回文串这种东西，很快的打出了正解。但是我在一个循环中把不应该等零的地方写错了
于是果断的零分，数据还是很强的。
我在下面弄了3000个问号也没检查出来错误，很迷。
![]()
1 #include <cstdio>
2 #include <iostream>
3 #include <cmath>
4 #include <string>
5 #include <cstring>
6 #include <algorithm>
7 using namespace std;
8 inline void write(int x)
9 {
10 if(x>9) write(x/10);
11 putchar(x%10+'0');
12 }
13 inline int read()
14 {
15 int x=0;
16 char ch=getchar();
17 while(ch>'9'||ch<'0')
18 ch=getchar();
19 while(ch>='0'&&ch<='9')
20 {
21 x=(x<<1)+(x<<3)+ch-'0';
22 ch=getchar();
23 }
24 return x;
25 }
26 int i,f,n,ans;
27 int o[3100];
28 int main()
29 {
30 //freopen("123.in","r",stdin);
31 //freopen("123.out","w",stdout);
32 ans=n=read();
33 for(i=1;i<=n;i++)
34 {
35 o[i]=int(getchar());
36 }
37 for(i=2;i<n;i++)//处理奇数个的
38 {
39 for(f=1;i-f>=1&&i+f<=n;f++)
40 {
41 if(o[i-f]==o[i+f]||o[i-f]==63||o[i+f]==63)
42 {
43 ans++;
44 /*for(int j=i-f;j<=i+f;j++)
45 cout<<char(o[j]);
46 cout<<endl;*/
47 }
48 else break;
49 }
50 }
51 for(i=1;i<=n;i++)//处理偶数个
52 {
53 for(f=1;i-f+1>0&&i+f<=n;f++)
54 {
55 if(o[i-f+1]==o[i+f]||o[i-f+1]==63||o[i+f]==63)
56 {
57 ans++;
58 /*for(int j=i-f+1;j<=i+f;j++)
59 cout<<char(o[j]);
60 cout<<endl;*/
61 }
62 else break;
63 }
64 }
65 write(ans);
66 }
t2
如果以后都像这个代码里把情况输出来检查就好了，说到底还是自己不注意、不认真。
第三第四题是我不擅长的图论，题解中的LCA啥的都看不懂。总之把第三题写了一个dfs的版本想拿50分(自己都不知道应该算是哪种算法，只知道是个dfs)，本来不抱任何希望，但还真的拿到了50分。
![]()
1 #include <cstdio>
2 #include <iostream>
3 #include <cmath>
4 #include <string>
5 #include <cstring>
6 #include <algorithm>
7 using namespace std;
8 inline void write(int x)
9 {
10 if(x>9) write(x/10);
11 putchar(x%10+'0');
12 }
13 inline int read()
14 {
15 int x=0;
16 char ch=getchar();
17 while(ch>'9'||ch<'0')
18 ch=getchar();
19 while(ch>='0'&&ch<='9')
20 {
21 x=(x<<1)+(x<<3)+ch-'0';
22 ch=getchar();
23 }
24 return x;
25 }
26 int i,f,m,n;
27 int x,y,a,b;
28 int o[1030],fenmu[5100][50100];
29 int fenzi[5010][5010];
30 bool flag[5010],neng[5010][5010];
31 void yuefen()
32 {
33 for(f=2;f<=a&&f<=b;f++)
34 {
35 while(a%f==0&&b%f==0)
36 a=a/f,b=b/f;
37 }
38 }
39 void dfs(int nowx,int nowy)
40 {
41 flag[nowy]=1;
42 fenzi[nowy][x]=fenzi[x][nowy]=fenzi[x][nowx]+o[nowy];
43 fenmu[nowy][x]=fenmu[x][nowy]=fenmu[x][nowx]+fenmu[nowx][nowy];
44 if(nowy==y) return;
45 for(int j=1;j<=n;j++)
46 {
47 if(flag[j]==0&&neng[nowy][j])
48 dfs(nowy,j);
49 if(fenzi[x][y]!=0)return;
50 }
51 }
52 int main()
53 {
54 //freopen("123.in","r",stdin);
55 //freopen("123.out","w",stdout);
56 n=read();
57 for(i=1;i<=n;i++)
58 o[i]=read();
59 for(i=1;i<n;i++)
60 {
61 x=read();
62 y=read();
63 neng[x][y]=neng[y][x]=1;
64 fenzi[x][y]=fenzi[y][x]=o[x]+o[y];
65 fenmu[x][y]=fenmu[y][x]=read();
66 }
67 m=read();
68 for(i=1;i<=m;i++)
69 {
70 x=read();
71 y=read();
72 if(x==y)
73 {
74 putchar(49);
75 putchar(47);
76 putchar(48);
77 putchar(10);
78 continue;
79 }
80 if(fenzi[x][y]==0)
81 {
82 memset(flag,0,sizeof(flag));
83 dfs(0,x);
84 }
85 a=fenzi[x][y];b=fenmu[x][y];
86 yuefen();
87 write(a);
88 putchar(47);
89 write(b);
90 putchar(10);
91 }
92 }
t3
![]()
1 #include<bits/stdc++.h>
2 using namespace std;
3 inline int read(){
4 int a=0,t=1; char ch=getchar();
5 while (ch<'0' || ch>'9'){
6 if (ch=='-') t=-1; ch=getchar();
7 }
8 while (ch>='0' && ch<='9'){
9 a=a*10+(ch-'0'); ch=getchar();
10 }
11 return a*t;
12 }
13 inline long long readll(){
14 long long a=0,t=1; char ch=getchar();
15 while (ch<'0' || ch>'9'){
16 if (ch=='-') t=-1; ch=getchar();
17 }
18 while (ch>='0' && ch<='9'){
19 a=a*10+(ch-'0'); ch=getchar();
20 }
21 return a*t;
22 }
23 struct edge_arr{
24 int to,l,next;
25 }edge[200005];
26 int head[100005],num=0;
27 inline void lianshi(int u,int v){
28 edge[++num].to=v; edge[num].next=head[u]; head[u]=num;
29 }
30 inline void lianshil(int u,int v,int l){
31 edge[++num].to=v; edge[num].l=l; edge[num].next=head[u]; head[u]=num;
32 }
33 struct arr{
34 int n,l;
35 };
36 inline arr make_arr(int n,int l){
37 arr e; e.n=n; e.l=l; return e;
38 }
39 long long mod;
40 long long n,dist[100005][105],m;
41 bool vis[100005][105];
42 queue<arr>q;
43 inline void spfa(){
44 for (int i=1;i<=n;i++){
45 for (int j=0;j<mod;j++){
46 dist[i][j]=2147483647; vis[i][j]=false;
47 }
48 }
49 dist[1][0]=0; q.push(make_arr(1,0));
50 int now,nows;
51 while (!q.empty()){
52 now=q.front().n; nows=q.front().l; q.pop(); vis[now][nows]=false;
53 for (int i=head[now];i;i=edge[i].next){
54 if (dist[edge[i].to][(nows+edge[i].l)%mod]>(dist[now][nows]+edge[i].l)){
55 dist[edge[i].to][(nows+edge[i].l)%mod]=(dist[now][nows]+edge[i].l);
56 if (!vis[edge[i].to][(nows+edge[i].l)%mod]){
57 vis[edge[i].to][(nows+edge[i].l)%mod]=true;
58 q.push(make_arr(edge[i].to,(nows+edge[i].l)%mod));
59 }
60 }
61 }
62 }
63 }
64 int main(){
65 n=read(),m=read(); mod=2147483647;
66 for (int i=1;i<=m;i++){
67 int u=read(),v=read(),l=read();
68 lianshil(u,v,l); lianshil(v,u,l);
69 if (u==1 || v==1) mod=min(mod,2ll*l);
70 }
71 //printf("%lld
",mod); return 0;
72 int q=read();
73 if (mod==2147483647){
74 for (int i=1;i<=q;i++){
75 int p=read();
76 printf("AKTang!
");
77 }
78 return 0;
79 }
80 spfa();
81 for (int i=1;i<=q;i++){
82 int p=read();
83 if (dist[n][p%mod]<=p) printf("AWaDa!
");
84 else printf("AKTang!
");
85 }
86 return 0;
87 }
