头像

冷瞳丶Nemsis




离线:10个月前


最近来访(1)
用户头像
998


冷瞳丶Nemsis
2020-09-05 05:44
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {

        int n = nums.size();

        for(auto i : nums){
            if(i < 0 || i >= n) return -1;
        }

        for(int i = 0 ; i < n ; ++ i){
            while(nums[nums[i]] != nums[i]) swap(nums[nums[i]] , nums[i]);

            if(nums[i] != i) return nums[i];
        }
        return -1;
    }
};



冷瞳丶Nemsis
2020-04-18 05:49

题目描述

blablabla

样例

blablabla

也可以查看这里

今天终于是把这个汉诺塔弄懂了,以前就是直接抄了抄代码。。。。
思路:
在进行操作的时候,可以分为三个步骤:
(假设有i个盘子,定义dp[k]为k个盘子通过其他两个柱子移动到第三个柱子上移动的最小次数)
1.将A柱字上的前j个盘子通过B、D两个柱字转移到C柱子上,或者通过C、D柱子转移到B柱子上,都是一样的。此时要动
dp[j]次。

2.将A柱字剩下的i-j个盘子通过B柱子移动到D上,此时不能借助C柱子,因为C柱子上第一个盘子比任何一个盘子都要小。注意,此时是一个经典汉诺塔问题,即此时只有三个柱子,经典汉诺塔问题的最小步骤是
(2 ^ k - 1)次,k是盘子数目,那么对于此刻来说就是(2 ^ (i - j)) - 1次。至于为什么经典汉诺塔的最小步骤是
(2 ^ k - 1)次,可以参考这个视频

3.最后我们要将C柱子上的j个盘子通过A、B柱子移动到D柱子上,次数也是dp[j]

因此dp[i] = 2 * dp[j] + ((1 << (i - j)) - 1)。我们只需要枚举i的同时枚举j,找到最小的那一个即可

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
const int INF = 0x3f3f3f3f;

int dp[N];

int main(void)
{
    dp[1] = 1;
    for(int i = 2 ; i <= 12 ; ++ i)
    {
        int minv = INF;
        for(int j = 1 ; j < i ; ++ j)
            minv = min(minv , 2 * dp[j] + (1 << (i - j)) - 1);
        dp[i] = minv;
    }

    for(int i = 1 ; i <= 12 ; ++ i)
        cout << dp[i] << endl;

    return 0;
}


活动打卡代码 AcWing 166. 数独

冷瞳丶Nemsis
2019-09-27 09:55
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9;

int ones[1 << N] , mp[1 << N];
int row[N] , col[N] , cell[3][3];
char str[100];

inline int lowbit(int x)
{
    return x & -x;
}

void init()
{
    for(int i = 0 ; i < N ; ++i) row[i] = col[i] = (1 << N) - 1;

    for(int i = 0 ; i < 3 ; ++i)
        for(int j = 0 ; j < 3 ; ++ j)
            cell[i][j] = (1 << N) - 1;
}

inline int get(int x , int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
    if(cnt == 0) return true;

    int minv = 10;
    int x , y;

    for(int i = 0 ; i < N ; ++ i)
        for(int j = 0 ; j < N ; ++ j)
            if(str[i * 9 + j] == '.')
            {
                int t = ones[get(i , j)];
                if(t < minv)
                {
                    minv = t;
                    x = i , y = j;
                }
            }

    for(int i = get(x , y) ; i ; i -= lowbit(i))
    {
        int t = mp[lowbit(i)];

        row[x] -= 1 << t;
        col[y] -= 1 << t;
        cell[x / 3][y / 3] -= 1 << t;
        str[x * 9 + y] = '1' + t;
        if(dfs(cnt - 1)) return true;

        row[x] += 1 << t;
        col[y] += 1 << t;
        cell[x / 3][y / 3] += 1 << t;
        str[x * 9 + y] = '.';
    }


    return false;
}
int main(void)
{
    for(int i = 0 ; i < N ; ++ i) mp[1 << i] = i;
    for(int i = 0 ; i < 1 << N ; ++ i)
    {
        int s = 0;
        for(int j = i ; j ; j -= lowbit(j)) s ++;
        ones[i] = s;
    }

    while(scanf("%s",str) != EOF && str[0] != 'e')
    {
        init();

        int cnt = 0;
        for(int i = 0 , k = 0 ; i < N ; ++ i)
        {
            for(int j = 0 ; j < N ; ++ j , ++ k)
            {
                if(str[k] != '.')
                {
                    int t = str[k] - '1';
                    row[i] -= 1 << t;
                    col[j] -= 1 << t;
                    cell[i / 3][j / 3] -= 1 << t;
                }
                else cnt ++;
            }
        }

        dfs(cnt);

        printf("%s\n",str);
    }
    return 0;
}


活动打卡代码 AcWing 165. 小猫爬山

冷瞳丶Nemsis
2019-09-25 15:21
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n , m , res = N;
int ans[N] , sum[N];

void dfs(int u , int k)
{
    if(k >= res) return ;

    if(u == n)
    {
        res = min(res , k);
        return ;
    }

    for(int i = 0 ; i < k ; ++ i)
    {
        if(sum[i] + ans[u] <= m)
        {
            sum[i] += ans[u];
            dfs(u + 1 , k);
            sum[i] -= ans[u];
        }
    }
    sum[k] = ans[u];
    dfs(u + 1 , k + 1);
    sum[k] = 0;
}
int main(void)
{
    scanf("%d %d",&n , &m);

    for(int i = 0 ; i < n ; ++ i) scanf("%d" , &ans[i]);

    sort(ans , ans + n);
    reverse(ans , ans + n);

    dfs(0 , 0);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 164. 可达性统计

冷瞳丶Nemsis
2019-09-25 06:32
#include <queue>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30010;

bitset<N>f[N];
int n , m , idx;
int h[N] , ne[N] , t[N] , d[N] , seq[N];

void add(int a , int b)
{
    t[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void topsort()
{
    queue < int > q;

    for(int i = 1 ; i <= n ; ++ i)
        if(!d[i])
            q.push(i);

    int k = 0;

    while(q.size())
    {
        auto p = q.front();
        q.pop();

        seq[++ k] = p;

        for(int i = h[p] ; ~i ; i = ne[i])
        {
            int j = t[i];

            if(-- d[j] == 0)
                q.push(j);
        }
    }
}

int main(void)
{
    scanf("%d %d",&n , &m);

    memset(h , -1 , sizeof h);

    while(m --)
    {
        int a , b;
        scanf("%d %d",&a ,&b);
        add(a , b);
        d[b] += 1;
    }
    topsort();

    for(int i = n ; i ; -- i)
    {
        int j = seq[i];

        f[j][j] = 1;
        for(int p = h[j] ; ~p ; p = ne[p])
            f[j] |= f[t[p]];
    }

    for(int i = 1 ; i <= n ; ++ i)
        cout << f[i].count() << endl;
    return 0;
}


活动打卡代码 AcWing 163. 生日礼物

冷瞳丶Nemsis
2019-09-25 03:12
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef pair <int , int>PII;

int n , m;
bool st[N];
int a[N] , l[N] , r[N];
void remove(int p)
{

    l[r[p]] = l[p];
    r[l[p]] = r[p];
    st[p] = true;
}
int main(void)
{
    cin >> n >> m;
    priority_queue < PII , vector < PII > , greater < PII >> heap;
    int k = 0;
    for(int i = 0 ; i < n ; ++i)
    {
        int x;
        cin >> x;
        if(!x) continue;
        if(!k || a[k] * x < 0) a[++ k] = x;
        else a[k] += x;
    }

    n = k;


    int cnt = 0 , res = 0;

    for(int i = 1 ; i <= n ; ++ i)
    {
        if(a[i] > 0)
        {
            ++ cnt;
            res += a[i];
        }
    }

    for(int i = 1 ; i <= n ; ++i)
    {
        l[i] = i - 1;
        r[i] = i + 1;

        heap.push({abs(a[i]) , i});
    }

    while(cnt > m)
    {
        while(st[heap.top().second]) heap.pop();
        auto t = heap.top();
        heap.pop();

        int v = t.first , p = t.second;
        if(l[p] != 0 && r[p] != n + 1 || a[p] > 0)
        {
            res -= v;
            -- cnt;
            int left = l[p] , right = r[p];
            a[p] += a[left] + a[right];
            heap.push({abs(a[p]) , p});
            remove(left);
            remove(right);
        }
    }
    cout << res << endl;

    return 0;

}


活动打卡代码 AcWing 149. 荷马史诗

冷瞳丶Nemsis
2019-09-25 02:48
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;
typedef pair < LL , LL> PLL;

LL n , m , i , j , k , ans , x;
priority_queue < PLL , vector < PLL > , greater <PLL> > p;

int main(void)
{
    scanf("%lld %lld",&n ,&k);

    for(int i = 1 ; i <= n ; ++ i)
    {
        scanf("%lld" , &x);
        p.push({x , 0});
    }

    while((p.size() - 1) % (k - 1) != 0)
        p.push({0 , 0});

    while((int)p.size() >= k)
    {
        LL deep = -1 , tmp = 0;
        for(j = 1 ; j <= k ; ++ j)
        {
            auto dx = p.top();
            p.pop();
            tmp += dx.first;
            deep = max(deep , dx.second);
        }
        p.push({tmp , deep + 1});
        ans += tmp;
    }
    cout << ans << endl;
    cout << p.top().second << endl;

    return  0;
}


活动打卡代码 AcWing 147. 数据备份

冷瞳丶Nemsis
2019-09-25 02:30
#include <set>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;
typedef pair <LL , int> PLI;

int n , k;
int l[N] , r[N] ;
LL d[N];

void del(int p)
{
    r[l[p]] = r[p];
    l[r[p]] = l[p];
}
int main(void)
{
    cin >> n >> k;
    for(int i = 0 ; i < n ; ++ i) cin >> d[i];

    for(int i = n - 1 ; ~i ; -- i) d[i] -= d[i - 1];

    d[0] = d[n] = 1e15;
    set < PLI > s;

    for(int i = 0 ; i <= n ; ++ i)
    {
        l[i] = i - 1;
        r[i] = i + 1;
        if(i && i < n) s.insert({d[i] , i});
    }

    LL res = 0;

    while(k --)
    {
        auto it = s.begin();
        LL v = it -> first;
        int p = it -> second , left = l[p] , right = r[p];
        s.erase(it);
        s.erase({d[left] , left}) , s.erase({d[right] , right});
        del(left) , del(right);
        res += v;

        d[p] = d[left] + d[right] - d[p];
        s.insert({d[p] , p});
    }
    cout << res << endl;
    return 0;
}



冷瞳丶Nemsis
2019-09-25 00:25
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n , idx , id;
int h[N] , to[N * 2] , ne[N * 2] , w[N * 2] , a[N] , trie[3000010][2];

void add(int i , int j , int k)
{
    w[idx] = k;
    to[idx] = j;
    ne[idx] = h[i];
    h[i] = idx ++;
}

void dfs(int u , int fa , int sum)
{
    a[u] = sum;
    for(int i = h[u] ; i != -1 ; i = ne[i])
    {
        if(to[i] != fa)
            dfs(to[i] , u , sum ^ w[i]);
    }
}

void Insert(int x)
{
    int p = 0;
    for(int i = 30 ; ~i ; -- i)
    {
        int u = (x >> i) & 1;
        if(!trie[p][u]) trie[p][u] = ++ id;
        p = trie[p][u];
    }
}
int query(int x)
{
    int p = 0 , res = 0;
    for(int i = 30 ; ~i ; -- i)
    {
        int u = (x >> i) & 1;
        if(trie[p][!u])
        {
            res += 1 << i;
            p = trie[p][!u];
        }
        else p = trie[p][u];
    }
    return res;
}
int main(void)
{
    cin >> n;
    memset(h , - 1 , sizeof h);

    for(int t = 1 ; t < n ; ++ t)
    {
        int i , j , k;
        scanf("%d %d %d",&i ,&j ,&k);
        add(i , j , k);
        add(j , i , k);
    }

    dfs(0 , -1 , 0);

    for(int i = 0 ; i < n; ++ i) Insert(a[i]);

    int res = 0;

    for(int i = 0 ; i < n ; ++ i) res = max(res , query(a[i]));

    cout << res << endl;
}


活动打卡代码 AcWing 140. 后缀数组

冷瞳丶Nemsis
2019-09-24 15:38
#include <limits.h>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 300010 , base = 131;
typedef unsigned long long ULL;

int n;
int sa[N];
char s[N];
ULL h[N] , p[N];

int Get(int l , int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
int get(int a , int b)
{
    int l = 0 , r = min(n - a + 1 , n - b + 1);
    while(l < r)
    {
        int mid = (l + r + 1 )>> 1;
        if(Get(a , a + mid - 1) != Get(b , b + mid - 1)) r = mid - 1;
        else l = mid;
    }
    return l;
}
bool cmp(int a , int b)
{
    int l = get(a , b);
    int av = a + l  > n ? INT_MIN : s[a + l];
    int bv = b + l > n ? INT_MIN : s[b + l];
    return av < bv;
}
int main(void)
{
    scanf("%s",s + 1);
    n = strlen(s + 1);

    p[0] = 1;
    for(int i = 1 ; i <= n ; ++ i)
    {
        sa[i] = i;
        p[i] = p[i - 1] * base;
        h[i] = h[i - 1] * base + s[i] - 'a' + 1;
    }

    sort(sa + 1, sa + n + 1 , cmp);

    for(int i = 1 ; i <= n ; ++i) printf("%d ",sa[i] - 1);
    puts("");
    for(int i = 1 ; i <= n ; ++ i)
        if(i == 1) printf("0 ");
        else printf("%d ",get(sa[i - 1] , sa[i]));
    puts("");
    return 0;

}