比赛链接

B

思路: 10X10的格子,D=0表示水平放置一艘长度为L的船,反之竖直放置。每个格子最多只能有一艘船,且这些船不能到边界之外。问你这个输入是否合法。模拟放置过程,检查是否被放置到格子外,之后在检查每个格子是否至多一条船即可。

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

//team lots of balloons
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int _,n,m;
int R,C,L,D;
int a[15][15];
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);

cin>>n;
bool f=1;
while(n--)
{

cin>>D>>L>>R>>C;
if(D==0)
{
for(int j=C;j<=C+L-1;j++)
{
a[R][j]++;
if(R>10||j>10||R<1||j<1)
{
f=0;
}
}
}
else
{
for(int i=R;i<=R+L-1;i++)
{
a[i][C]++;
if(C>10||i>10||C<1||i<1)
{
f=0;
}
}
}
}
for(int i=1;i<=10;i++)
{
for(int j=1;j<=10;j++)
{
if(a[i][j]>=2)
{
f=0;
break;
}
}
}
if(f)
{
cout<<"Y"<<endl;
}
else
{
cout<<"N"<<endl;
}

return 0;
}


F

思路: 认真读题的模拟题,知道谁发球就好。

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

//team lots of balloons
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int _,n,m;
int da[2];
int xiao[2];
int fa;
string s;
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
cin>>s;
n=s.length();
for(int i=0;i<n;i++)
{
if(s[i]=='S')
{
xiao[fa]++;
if((xiao[fa]>=5&&xiao[fa]-xiao[!fa]>=2)||xiao[fa]>=10)
{
da[fa]++;
xiao[fa]=xiao[!fa]=0;
}
}
else if (s[i]=='R')
{
xiao[!fa]++;
if((xiao[!fa]>=5&&xiao[!fa]-xiao[fa]>=2)||xiao[!fa]>=10)
{
da[!fa]++;
xiao[fa]=xiao[!fa]=0;
}
fa=!fa;
}
else
{
if(da[0]==2)
{
cout<<da[0]<<" (winner) - "<<da[1]<<endl;
}
else if ( da[1]==2)
{
cout<<da[0]<<" - "<<da[1]<<" (winner)"<<endl;
}
else
{
if(fa==1)
{
cout<<da[0]<<" ("<<xiao[0]<<") - "<<da[1]<<" ("<<xiao[1]<<"*)"<<endl;
}
if(fa==0)
{
cout<<da[0]<<" ("<<xiao[0]<<"*) - "<<da[1]<<" ("<<xiao[1]<<")"<<endl;
}
}
}
}
return 0;
}


L

思路: 从格子里面找到字符串,不过这个字符串的顺序可以打乱,我是用两个数组去存字母,如果当前状态某一个字母数量超过了目标字符串,就退出这次查询,如果查完一个长度与目标字符串相等的串就可以确定一个答案,就给这些位置打上tag,这里的tag也是有很多个,方便之后统计。因为数据范围小,我们可以暴力的实现水平,竖直和两条对角线上的查询。最后做个对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
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233

//team lots of balloons
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int _,n,m;
int L,C,N;
int tong[30];
int tong2[30];
string s[50];
int OK[45][45][25];
string sss;
void left(int len,int hang,int bianhao)
{
bool f=0;
int j=0;
for(int i=0;i<=C;i++)
{
f=0;
memset(tong2,0,sizeof(tong2));
for(j=0;j<len;j++)
{
if(i+j>=C)
{
break;
}
tong2[s[hang][i+j]-'A']++;
if(tong2[s[hang][i+j]-'A']>tong[s[hang][i+j]-'A'])
{
//memset(tong2,0,sizeof(tong2));
break;
}
if(j==len-1)
{
f=1;
}
}
if(f)
{

for(j=0;j<len;j++)
{
// cout<<hang<<" "<<i+j<<" "<<bianhao<<endl;
OK[hang][i+j][bianhao]=1;
}
}

}
}
void down(int len,int lie,int bianhao)
{
bool f=0;
int j=0;
for(int i=0;i<=L;i++)
{
f=0;
memset(tong2,0,sizeof(tong2));
for(j=0;j<len;j++)
{
if(i+j>=L)
{
break;
}
tong2[s[i+j][lie]-'A']++;
if(tong2[s[i+j][lie]-'A']>tong[s[i+j][lie]-'A'])
{

break;
}
if(j==len-1)
{
f=1;
}
}
if(f)
{
//memset(tong2,0,sizeof(tong2));
for(j=0;j<len;j++)
{
//cout<<i+j<<" "<<lie<<" "<<bianhao<<endl;
OK[i+j][lie][bianhao]=1;
}
}

}
}

//×óÉϵ½ÓÒÏÂ
void leftdown(int len,int hang,int lie,int bianhao)
{
bool f=0;
int i=0;
memset(tong2,0,sizeof(tong2));
for(i=0;i<len;i++)
{
if(hang+i>=L||lie+i>=C)
{
break;
}
tong2[s[hang+i][lie+i]-'A']++;
if(tong2[s[hang+i][lie+i]-'A']>tong[s[hang+i][lie+i]-'A'])
{
break;
}
if(i==len-1)
{
f=1;
}
}
if(f)
{
//memset(tong2,0,sizeof(tong2));
for(int j=0;j<len;j++)
{
// cout<<hang+j<<" "<<lie+j<<" "<<bianhao<<endl;
OK[hang+j][lie+j][bianhao]=1;
}
}
}
//ÓÒÉϵ½×óÏÂ
void rightdown(int len,int hang,int lie,int bianhao)
{
bool f=0;
int i=0;
memset(tong2,0,sizeof(tong2));
for(i=0;i<len;i++)
{
if(hang+i>=L||lie-i<0)
{
break;
}
tong2[s[hang+i][lie-i]-'A']++;
if(tong2[s[hang+i][lie-i]-'A']>tong[s[hang+i][lie-i]-'A'])
{
break;
}
if(i==len-1)
{
f=1;
}
}
if(f)
{
//memset(tong2,0,sizeof(tong2));
for(int j=0;j<len;j++)
{
//cout<<hang+j<<" "<<lie-j<<" "<<bianhao<<endl;
OK[hang+j][lie-j][bianhao]=1;
}
}

}
void cal(string ss,int bianhao)
{
memset(tong,0,sizeof(tong));
int len = ss.length();
for(int i=0;i<len;i++)
tong[ss[i]-'A']++;

for(int i=0;i<L;i++)
{
left(len,i,bianhao);
}
// cout<<endl;
for(int i=0;i<C;i++)
{

down(len,i,bianhao);
}
//cout<<endl;
for(int i=0;i<L;i++)
{
for(int j=0;j<C;j++)
{
leftdown(len,i,j,bianhao);
}
}
//cout<<endl;
for(int i=0;i<L;i++)
{
for(int j=C-1;j>=0;j--)
{
rightdown(len,i,j,bianhao);
}
}
//cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin>>L>>C;
for(int i=0;i<L;i++)
{
cin>>s[i];
}
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>sss;
cal(sss,i);
}
int te=0;
int ans=0;
//cout<<"ANS"<<endl;
for(int i=0;i<L;i++)
{
for(int j=0;j<C;j++)
{
te=0;
for(int k=1;k<=N;k++)
{
if(OK[i][j][k])
{
te++;
}
}
if(te>=2)
{
//cout<<i<<" "<<j<<endl;
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}



N

思路:从2开始枚举所有质数prime,记录每个N-NODE的入度du[i]。从小到大遍历每个M-NODE我们考虑任意一个与它有关的N-NODE的值为a[i],那么a[i]的最小质因子一定是这个M-NODE的值,这个质因子是可以枚举出来的。特别的,当du[i]=1时,M-NODE的值就是a[i]。注意的是每次确定M-NODE的值,都要对所有的以这个点为顶点的边都处理掉。

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int m,n,k,t;
ll a[1005];
vector<int >vec[1005];
int edge[1005][1005];
ll ans[1005];
int du[1005];
int u,v;
ll temp;
ll prime=2;
ll quickmi(ll a,ll p)
{
ll ans=1;
while(p)
{
if(p&1)
ans*=a;
a*=a;
p>>=1;
}
return ans;
}
void work(int u ,ll pri)
{
for(int j=0;j<vec[u].size();j++)
{
while(edge[u][vec[u][j]])
{
a[vec[u][j]]/=pri;
edge[u][vec[u][j]]--;
du[vec[u][j]]--;
}
}
}
int main()
{
cin>>m>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(!(a[i]&1))
{
ans[1]=2;
}
}

for(int i=1;i<=k;i++)
{
cin>>u>>v>>t;
vec[u].push_back(v);
edge[u][v]=t;
du[v]+=t;
}
int i=1;

if(ans[1]==2)
{
work(1,2);
prime=3;
i=2;
}
for(;i<=m;i++)
{

u=vec[i][0];
if(du[ u ]==1)
{
ans[i]=a[u];
work(i,ans[i]);
prime=ans[i]+1;

continue;
}
while(prime*prime<=1e15)
{
if( a[u] % quickmi(prime,edge[i][u]) ==0 )
{
ans[i]=prime;
work(i,ans[i]);
prime++;
break;
}
prime++;
}

}
for(int j=1;j<=m;j++)
{
cout<<ans[j]<<" ";
}
cout<<"\n";



}


写在最后
N题和A题应该会在20号之前补上。