头像

cht

欢迎大佬来访~~~~


访客:44442

离线:17小时前



cht
9天前

看本题发题解的人比较少,水一发。

这道题比较考验搜索,但主要还是考验代码能力。

这里就按y总的讲了。

  1. 先搜行列里确定多的
  2. 先搜数多的

这里可以用lowbit运算加上预处理幂,用二进制优化的方法来进行剪枝。(一道中等题肯定不是随随便便就能过的

总体思路就是这样,贴代码。

再剩下的看注释吧

#include<bits/stdc++.h>
using namespace std;
const int N = 9;
int ones[1 << N], Log[1 << N];//因为是和2进制有关的,存幂和1,需要开1 << N
int row[N], col[N], cell[5][5];//行列和九宫格
int g[N][N];//存整个图
int ans = -1;//防止最后特判
inline int lowbit(int x)
{
    return x & -x;//lowbit运算,二进制优化
}
void init()
{
    for(int i = 0; i < N; i ++) Log[1 << i]  = i;//把所有的幂初始化
    for(int i = 0; i < (1 << N); i ++)
        for(int j = i; j; j -= lowbit(j))
            ones[i] ++;//算出lowbit,预处理提高运行效率
    for(int i = 0; i < N; i ++) row[i] = col[i] = cell[i / 3][i % 3] = (1 << N) - 1;//初始化3个记录

}
inline int get_scorl(int x, int y)
{
    return min(min(x, 8 - x), min(y, 8 - y)) + 6;//看题目
}
inline void drow(int x, int y, int t)
{
    int s = 1;
    if(t > 0)
    {
        g[x][y] = t;//若t有数直接记录
    }
    else s = -1, t = -t, g[x][y] = 0;//否则先讲t取反,然后需要将s变成-1方便后续改变整个数独的二进制
    t --;
    //改变二进制
    row[x] -= s << t;
    col[y] -= s << t;
    cell[x / 3][y / 3] -= s << t;
}
inline int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];//这个是需要返回对应的位置
}
inline void dfs(int cnt, int scorl)//最重要的dfs
{
    if(!cnt) 
    {
        ans = max(ans, scorl);//如果没有空格直接return
        return ;
    }
    int x, y;
    int mins = 10000;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            if(!g[i][j])
            {
                int state = get(i, j);//get出来
                if(ones[state] < mins)
                {
                    mins = ones[state];//更新最小
                    x = i, y = j;
                }
            }
    //对最小进行爆搜
    for(int i = get(x, y); i ; i -= lowbit(i))
    {
        int t = Log[lowbit(i)] + 1;
        drow(x, y, t);
        dfs(cnt - 1, scorl + get_scorl(x, y) * t);
        drow(x, y, -t);//不要忘记回溯(
    }
}
int main()
{
    init();
    int cnt = 0;
    int scorl = 0;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
        {
            int x;
            cin >> x;
            if(x > 0)
            {
                drow(i, j, x);//这些东西没啥好说的,算分值,把输入画进g数组
                scorl += x * get_scorl(i, j);
            }
            else cnt ++;
        }
    dfs(cnt, scorl);
    cout << ans << endl;
    return 0;
}
毒瘤死了

下一篇题解更新上一行的题目(



活动打卡代码 AcWing 183. 靶形数独

cht
10天前
#include<bits/stdc++.h>
using namespace std;
const int N = 9;
int ones[1 << N], Log[1 << N];
int row[N], col[N], cell[5][5];
int g[N][N];
int ans = -1;
inline int lowbit(int x)
{
    return x & -x;
}
void init()
{
    for(int i = 0; i < N; i ++) Log[1 << i]  = i;
    for(int i = 0; i < (1 << N); i ++)
        for(int j = i; j; j -= lowbit(j))
            ones[i] ++;
    for(int i = 0; i < N; i ++) row[i] = col[i] = cell[i / 3][i % 3] = (1 << N) - 1;

}
inline int get_scorl(int x, int y)
{
    return min(min(x, 8 - x), min(y, 8 - y)) + 6;
}
inline void drow(int x, int y, int t)
{
    int s = 1;
    if(t > 0)
    {
        g[x][y] = t;
    }
    else s = -1, t = -t, g[x][y] = 0;
    t --;
    row[x] -= s << t;
    col[y] -= s << t;
    cell[x / 3][y / 3] -= s << t;
}
inline int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}
inline void dfs(int cnt, int scorl)
{
    if(!cnt) 
    {
        ans = max(ans, scorl);
        return ;
    }
    int x, y;
    int mins = 10000;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            if(!g[i][j])
            {
                int state = get(i, j);
                if(ones[state] < mins)
                {
                    mins = ones[state];
                    x = i, y = j;
                }
            }
    for(int i = get(x, y); i ; i -= lowbit(i))
    {
        int t = Log[lowbit(i)] + 1;
        drow(x, y, t);
        dfs(cnt - 1, scorl + get_scorl(x, y) * t);
        drow(x, y, -t);
    }
}
int main()
{
    init();
    int cnt = 0;
    int scorl = 0;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
        {
            int x;
            cin >> x;
            if(x > 0)
            {
                drow(i, j, x);
                scorl += x * get_scorl(i, j);
            }
            else cnt ++;
        }
    dfs(cnt, scorl);
    cout << ans << endl;
    return 0;
}



cht
10天前

题目链接 SPOJ4580

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int a[N];
map<int, int> cnt; 
int ans;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            for(int k = 1; k <= n; k ++)
            {
                int tmp = a[i] * a[j] + a[k];
                cnt[tmp] ++;    
            } 
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            for(int k = 1; k <= n; k ++)
            {
                int tmp = (a[i] + a[j]) * a[k];
                if(cnt.count(tmp) != 0) ans += cnt[tmp];
            }
    cout << ans << endl;
    return 0;
}

大佬们能帮忙hack一下吗?



活动打卡代码 AcWing 187. 导弹防御系统

cht
12天前
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, h[N], up[N], down[N], ans;
void dfs(int u, int su, int sd)
{
    if(su + sd >= ans) return;
    if(u == n)
    {
        ans = min(ans, su + sd);
        return;
    }
    int k = 0;
    while(k < su && up[k] >= h[u])k ++ ;
    if(k < su)
    {
        int t = up[k];
        up[k] = h[u];
        dfs(u + 1, su, sd);
        up[k] = t;
    }
    else{
        up[k] = h[u];
        dfs(u + 1, su + 1, sd);
    }
    k = 0;
    while(k < sd && down[k] <= h[u]) k ++ ;
    if(k < sd)
    {
        int t = down[k];
        down[k] = h[u];
        dfs(u + 1, su, sd);
        down[k] = t;
    }
    else{
        down[k] = h[u];
        dfs(u + 1, su, sd + 1);
    }
}
int main()
{
    while (cin >> n, n)
    {
        for (int i = 0; i < n; i ++ ) cin >> h[i];
        ans = n;
        dfs(0, 0, 0);
        cout << ans << endl;
    }
}


新鲜事 原文

cht
13天前
y总教师节快乐~


新鲜事 原文

cht
18天前
最近开启学术潜水模式通知


题目讨论 AcWing 878. 求问

cht
24天前

可能存在负数解吗?



问题 邻接表

cht
25天前

邻接表怎么处理重边呢



活动打卡代码 AcWing 442. 接水问题

cht
25天前
#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
int n, m;
int t[N];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> t[i];
    int cnt = 0;
    int then = m + 1;
    for(;;)
    {
        for(int i = 1; i <= m; i ++)
        {
            t[i] -= 1;
            if(t[i] == 0)
            {
                t[i] = t[then];
                t[then] = 0;
                then ++;
            }   
        } 
        cnt ++;
        if(then > n + m) break;
    }
    cout << cnt;
} 


活动打卡代码 AcWing 433. ISBN号码

cht
25天前
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char line[14];
    cin >> line;
    char x[12] = {"0123456789X"};
    int k = 1;
    int ans = 0;
    for(int i = 0; i < 12; i ++)
    {
        if(line[i] != '-')
        {
            int d = line[i] - '0';
            ans += d * k;
            k ++;
        }
    }
    ans = ans % 11;
    char res = x[ans];
    if(res == line[12]) puts("Right");
    else{
        line[12] = res;
        cout << line;
    }
    return 0;
}