Codeforces Round 286 Div.2 解题报告

A. Mr. Kitayuta’s Gift

Problem Description

询问向序列中添加一个字符能否变成回文串

Solution

数据量比较小,枚举就行了……当时比较脑残,直接考虑多种情况做的……

源代码:

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<stdio.h>
#include<string.h>
int main()
{

char s[20];
int len,mid;
int flag;
while(scanf("%s",s)!=EOF)
{
flag=0;
len=strlen(s);
mid=len/2;
if(len%2==0)
{
for(int i=0; i<mid; i++)
{
if(s[i]!=s[len-1-i])
{
flag=1;
break;
}
}
}
else
{
for(int i=0; i<mid; i++)
{
if(s[i]!=s[len-1-i])
{
flag=1;
break;
}
}
}
if(flag==0)
{
for(int i=0; i<len; i++)
{
printf("%c",s[i]);
if(i==mid)
{
printf("%c",s[i]);
}
}
printf("\n");
continue;
}
int left=0;
int right=0;
int flag2=0;
int no=0;
if(len%2==0)
{
for(int i=0; i<mid-1; i++)
{
while(s[i]!=s[len-1-right-i])
{
right++;
if(right>1)
{
no=1;
break;
}
}
}
if(no==0)
{
for(int i=len-1; i>=mid-1; i--)
{
printf("%c",s[i]);
}
for(int i=mid; i<len; i++)
{
printf("%c",s[i]);
}
printf("\n");
continue;
}
no=0;
right=0;
for(int i=len-1; i>mid; i--)
{
while(s[i]!=s[len-1+right-i])
{
right++;
if(right>1)
{
no=1;
break;
}
}
}
if(no==0)
{
for(int i=0; i<=mid; i++)
{
printf("%c",s[i]);
}
for(int i=mid-1; i>=0; i--)
{
printf("%c",s[i]);
}
printf("\n");
continue;
}
printf("NA\n");
}
else
{
int z,y,nn;
z=0,y=0;
nn=0;
for(int i=0;i<mid;i++)
{
while(s[i+z]!=s[len-1-i])
{
z++;
if(z>1)
{
nn=1;
break;
}
}
}
if(nn==0)
{
for(int i=0; i<=mid; i++)
{
printf("%c",s[i]);
}
for(int i=mid; i>=0; i--)
{
printf("%c",s[i]);
}
printf("\n");
continue;
}
z=0,y=0;
nn=0;
for(int i=len-1;i>mid;i--)
{
while(s[i-z]!=s[len-1-i])
{
//printf("%c--%c %d %d\n",s[i-z],s[len-1-i],i-z,i);
z++;
if(z>1)
{
nn=1;
break;
}
}
}
if(nn==0)
{
for(int i=len-1; i>mid-1; i--)
{
printf("%c",s[i]);
}
for(int i=mid; i<len; i++)
{
printf("%c",s[i]);
}
printf("\n");
continue;
}
printf("NA\n");
}
}
return 0;
}

B. Mr. Kitayuta’s Colorful Graph

Problem Description

给定一个图及其点和点之间所连线段的编号,接下来询问连接uv点之间相同编号线段的个数

Solution

我是用数位的方法记录点与点之间的线段编号,用图的第三维表示线段编号,每5个编号存在一个数组里,之后跑遍弗洛伊德就好了……头一回这么写,算编号数组的时候WA了一发……详见代码

源代码:

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
#include<stdio.h>
#include<string.h>
int main()
{

int n,m,a,b,c,temp,num,left,q,u,v;
int g[105][105][30];
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(g,0,sizeof(g));
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
num=c/5+1;
left=c%5;
temp=1<<left;
//printf("%d %d %d\n",num,left,temp);
g[a][b][num]|=temp;
g[b][a][num]|=temp;
g[a][b][0]=1;
g[b][a][0]=1;
//printf("%d\n",g[a][b][num]);
}
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
if(g[i][k][0]==1&&i!=k)
{
for(int j=1; j<=n; j++)
{
if(g[k][j][0]==1&&k!=j&&i!=j)
{
//printf("%d %d %d \n",i,j,k);
for(int h=0;h<=21;h++)
{
g[i][j][h]|=g[i][k][h]&g[k][j][h];
//printf("--%d %d %d %d %d\n",i,j,k,h,g[i][j][h]);
}
}
}
}
}
}
scanf("%d",&q);
for(int i=1; i<=q; i++)
{
scanf("%d%d",&u,&v);
int coun=0;
for(int h=1;h<=21;h++)
{
// printf("--%d\n",g[u][v][h]);
int now=g[u][v][h];
while(now!=0)
{
if(now%2==1)
{
coun++;
}
now/=2;
}
}
printf("%d\n",coun);
}
}
return 0;
}

今天这场有点难啊……耗时多了点,不过还是涨了41分……谁让我现在还是绿名呢XD……