201409第2次

视频题解

第 1 题相邻数对¶

TAG: 桶 哈希

思路:

开一个数组作为桶即可

代码:

#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为否。然后按题意模拟即可

代码:

#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: 模拟 字符串

思路:

简单的模拟题，按题意模拟即可

代码:

#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即可。

代码:

#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 快速幂 矩阵乘法

思路:

使用矩阵乘法优化快速幂求解即可。

代码:

#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;
}

201409第2次

第 1 题 相邻数对¶

第 2 题 画图¶

第 3 题 字符串匹配¶

第 4 题 最优配餐¶

第 5 题 拼图¶

评论