zhangas

Pay more attention

0%

7.26SDKDACM

Posted on

P1506 拯救oibh总部

题目链接
0是土地 *是墙 洪水从四面八方过来 求未被淹没的土地数量
扫一下边缘一圈，为0可以dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char c[505][505];
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
void dfs(int x,int y){
    if(c[x][y]=='*')return;
    c[x][y]='-';
    for(int i=1;i<=4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
            dfs(xx,yy);
        }
    }
}
int n,m;
int ans;
for(int i=1;i<=n;i++)dfs(i,1),dfs(i,m);
for(int i=1;i<=m;i++)dfs(1,i),dfs(n,i);
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        ans+=c[i][j]=='0'?1:0;
    }
}

B3626 跳跃机器人

题目链接
dp[i]=min(dp[i],dp[i-1]+1);
如果未到右边界才可由dp[i+1]+1转移
为偶数可由dp[i/2]+1转移
奇数可由dp[(i-1)/2]+2转移
如果未到右边界才可由dp[(i+1)/2]+2转移

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[1000005];
for(int i=2;i<=n+1;i++)dp[i]=n;//一定要初始化到N+1 考虑边界的情况
dp[1]=0;
for(int i=2;i<=n;i++){
    dp[i]=min(dp[i],dp[i-1]+1);
    if(i!=n)dp[i]=min(dp[i],dp[i+1]+1);
    if(i%2==0)dp[i]=min(dp[i],dp[i/2]+1);
    else{
        dp[i]=min(dp[i],dp[(i-1)/2]+1);
        if(i!=n)dp[i]=min(dp[i],dp[(i+1)/2]+1);
    }
}
cout<<dp[n];

P2037 电话号码

题目链接
STL模拟问题 set去重+排序 unordered_map映射个数
N<=100000 且 电话号码长度不会超过1000
O(N)*(1000)==1e9可过

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(string s){
    for(int i=0;i<s.szie();i++){
        if(s[i]>='A'&&s[i]<='Z')s[i]=...;
    }
    //处理-
    string ss='';
    for(auto i:s){
        ss+=i;
        if(ss.size()==3)ss+='-';
    }
    set.insert(ss);
    mp[ss]++;
}

P6183 [USACO10MAR] The Rock Game S

题目链接
将状态作为N位二进制表示0就是O 1就是X
求出一种方案使得相邻两种状态恰好有一位不同且无重复状态出现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int vis[1<<15+5];
bool dfs(int e){
    if(!vis[e]){
        //输出e的状态:从左到右输出二进制表示
        //与运算 两者都为1 才为1 否则为0
        for(int i=n-1;i>=0;i++){
            int t=e&(1<<i);
            if(t)cout<<'X';
            else cout<<'O';
        }
        vis[e]=1;
        //取^任意改变一位
        //异或运算 不同为1 相同为0
        for(int i=0;i<=n-1;i++){
            if(dfs(x^(1<<i)))
                return true;
        }
        return true;
    }
    return false;
}
dfs(0);