hihocoder编程练习赛19 A 题目要求 描述
输入
输出
样例输入
样例输出
参考AC代码 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
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 10000 + 50;
int n, m , k;
char a[55][55];
char g[120][850];
char t[120][850];
int c, r;
bool check(int gi, int gj){
if (gi + r > 120) return false ;
if (gj + c > 850) return false ;
int p,q,i,j;
for (i = gi,p=0; p < r; p++,i++)
for (j = gj,q=0; q < c; q++,j++)
if (g[i][j] != t[p][q]) return false ;
return true ;
}
int main
//freopen("input.txt" , "r" , stdin);
ios::sync_with_stdio(false );
cin.tie(0);cout.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
for (int i = 0; i < 120; i++)
for (int j = 0; j < 850; j++){
g[i][j] = a[i%n][j%m];
}
for (int i = 0; i < k; i++){
cin >> r >> c;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
cin >> t[i][j];
bool fg = false ;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (t[0][0] == g[i][j])
if (check(i,j)){
fg = true ;
break ;
}
}
if (fg ){
break ;
}
}
if (fg ) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
思路 把原地摊扩充
B 题目要求 描述
输入
输出
样例输入
样例输出
参考AC代码 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
using namespace std;
int temp[10];
void run
queue<int> q;
map<int,int> step;
int s;
cin>>s;
q.push(s);
step[s] = 0;
int len=0;
while (!q.empty()){
int t = q.front();
int now = step[t];
q.pop();
len = 0;
while ( t>0 ){
temp[len++] = t%10;
t/=10;
}
int a, b[8];
for (int i=0; i<len-1; i++){
int cnt=0;
a = temp[i] + temp[i+1]*10;
for (int j=0; j<len; j++){
if ( j==i || j==i+1 ) continue ;
b[cnt++] = temp[j];
}
for (int pos=0; pos<=cnt; pos++){
int next = 0;
for (int j=cnt; j>=0; j--){
if ( j<cnt ) next = next*10 + b[j];
if (pos==j) next = next*100 + a;
}
if ( !step.count(next) ){
q.push(next);
step[next] = now+1;
}
}
}
}
int t=0;
for (int i=1; i<=len; i++){
t = t*10 + i;
}
if (!step.count(t)) step[t] = -1;
cout<<step[t]<<endl;
}
int main
int T;
cin>>T;
while (T--) run();
return 0;
}
思路 bfs暴力枚举
D 题目要求 描述
输入
输出
样例输入
样例输出
参考AC代码 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
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while (y){if (y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int deep[maxn],f[maxn],anc[maxn][25];
vector<int>e[maxn];
void dfs(int x,int fa){
anc[x][0]=f[x];
for (int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
for (int i=0;i<e[x].size();i++){
int next=e[x][i];
if (next!=fa){
f[next]=x;
deep[next]=deep[x]+1;
dfs(next,x);
}
}
}
int lca(int x,int y){
if (deep[x]<deep[y]) swap(x,y);
for (int i=20;i>=0;i--) if (deep[anc[x][i]]>=deep[y]) x=anc[x][i];
if (x==y) return x;
for (int i=20;i>=0;i--) if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return f[x];
}
bool check
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
int t1=lca(x1,y1);
int t2=lca(x2,y2);
if (lca(t1,t2)==t1){
if (lca(t2,x1)==t2 || lca(t2,y1)==t2) return true ;
}
if (lca(t1,t2)==t2){
if (lca(t1,x2)==t1 || lca(t1,y2)==t1) return true ;
}
return false ;
}
int main
// freopen("input.txt" ,"r" ,stdin);
// freopen("ouput.txt" ,"w" ,sdout);
ios::sync_with_stdio(false );
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while (t--){
int n,m;
cin>>n>>m;
for (int i=0;i<=n;i++) e[i].clear();
for (int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].pb(v);
e[v].pb(u);
}
mm(f,0);
mm(anc,0);
mm(deep,0);
deep[1]=1;
dfs(1,0);
for (int i=1;i<=m;i++){
if (check()) cout<<"YES" <<endl;
else cout<<"NO" <<endl;
}
}
return 0;
}
思路 x1和y1的lca为t1
