201409第2次
第 1 题 相邻数对
题目链接: 相邻数对
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 | #include<iostream>
using namespace std;
const int N=10010;
int a[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int t;
cin>>t;
a[t]++;
}
int ans=0;
for(int i=1;i<10000;i++){
if(a[i]&&a[i+1]){
ans++;
}
}
cout<<ans;
return 0;
}
|
第 2 题 画图
题目链接: 画图
TAG: 模拟
思路:
二维数组a[i][j]表示左下角下标为(i,j)的格子是否被涂色，1为是，0为否。然后按题意模拟即可
代码:
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 | #include<iostream>
using namespace std;
const int N=110;
int a[N][N];
int main(){
int n;
cin>>n;
while(n--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
for(int i=x1;i<x2;i++){
for(int j=y1;j<y2;j++){
a[i][j]=1;
}
}
}
int ans=0;
for(int i=0;i<=100;i++){
for(int j=0;j<=100;j++){
if(a[i][j]==1){
ans++;
}
}
}
cout<<ans;
return 0;
}
|
第 3 题 字符串匹配
题目链接: 字符串匹配
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 | #include<iostream>
using namespace std;
bool check(char a,char b,int opt){
if(opt)return a==b;
if((a>'Z'&&b>'Z')||(a<'a'&&b<'a'))return a==b;
if(a>'Z')return a-'a'+'A'==b;
else return a-'A'+'a'==b;
}
int main(){
string s;
int opt,q,n,m;
cin>>s>>opt>>q;
n=(int)s.size();
while(q--){
string t;
cin>>t;
m=(int)t.size();
if(m<n)continue;
bool ok=true;
for(int i=0;i<=m-n;i++){
ok=true;
for(int j=0;j<n;j++){
if(!check(s[j],t[i+j],opt)){
ok=false;
break;
}
}
if(ok)break;
}
if(ok)cout<<t<<"\n";
}
return 0;
}
|
第 4 题 最优配餐
题目链接: 最优配餐
TAG: 多源最短路 BFS
思路:
将多源最短路转化为单源最短路，然后BFS即可。
代码:
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 | #include<bits/stdc++.h>
using namespace std;
using ll=long long;
using PII=pair<int,int>;
const int N=1010;
int n,m,k,d;
bool g[N][N];
int dist[N][N];
queue<PII> q;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct Node{
int x,y,c;
}node[N*N];
void bfs(){
while(!q.empty()){
PII t=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=t.first+dx[i],ny=t.second+dy[i];
if(nx<1||nx>n||ny<1||ny>n||g[nx][ny])continue;
if(dist[nx][ny]>dist[t.first][t.second]+1){
dist[nx][ny]=dist[t.first][t.second]+1;
q.push({nx,ny});
}
}
}
}
int main(){
memset(dist,0x3f,sizeof dist);
cin>>n>>m>>k>>d;
while(m--){
int x,y;
cin>>x>>y;
dist[x][y]=0;
q.push({x,y});
}
for(int i=0;i<k;i++){
cin>>node[i].x>>node[i].y>>node[i].c;
}
while(d--){
int x,y;
cin>>x>>y;
g[x][y]=true;
}
bfs();
ll ans=0;
for(int i=0;i<k;i++){
ans+=dist[node[i].x][node[i].y]*node[i].c;
}
cout<<ans;
return 0;
}
|
第 5 题 拼图
题目链接: 拼图
TAG: 状压DP 快速幂 矩阵乘法
思路:
使用矩阵乘法优化快速幂求解即可。
代码:
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 | #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=130,mod=1e9+7;
ll n;
int m;
int w[N][N];
void dfs(int x, int y, int u){
if(u==m)w[x][y]++;
else if(x>>u&1)dfs(x,y,u+1);
else{
if(u&&!(y>>u&1)&&!(y>>u-1&1))
dfs(x,y+(1<<u)+(1<<u-1),u+1);
if(u+1<m&&!(y>>u&1)&&!(y>>u+1&1))
dfs(x,y+(1<<u)+(1<<u+1),u+1);
if(u+1<m&&!(x>>u+1&1)){
if(!(y>>u&1))dfs(x,y+(1<<u),u+2);
if(!(y>>u+1&1))dfs(x,y+(1<<u+1),u+2);
}
}
}
void mul(int c[][N],int a[][N],int b[][N]){
static int tmp[N][N];
memset(tmp,0,sizeof tmp);
for(int i=0;i<1<<m;i++)
for(int j=0;j<1<<m;j++)
for(int k=0;k<1<<m;k++)
tmp[i][j]=(tmp[i][j]+(ll)a[i][k]*b[k][j])%mod;
memcpy(c,tmp,sizeof tmp);
}
int main(){
cin>>n>>m;
for(int i=0;i<1<<m;i++)dfs(i,0,0);
int res[N][N]={0};
res[0][(1<<m)-1]=1;
while(n){
if(n&1)mul(res,res,w);
mul(w,w,w);
n>>=1;
}
cout<<res[0][(1<<m)-1]<<"\n";
return 0;
}
|
最后更新:
2022-12-19 10:18:04