头像

nut96




离线:2天前


最近来访(7)
用户头像
阿兔
用户头像
Unique_80
用户头像
yhq_9
用户头像
HH123_
用户头像
lycckky
用户头像
心影


nut96
2天前

(一)在状压dp中,对于二进制状态,我们可以通过多种方式提取,改变,以下是操作规则
1.取出整数n在二进制下表示下的第k位 :(n >> k) & 1
2.取出整数n在二进制表示下的第0~k - 1位(后k位):n & ((1 << k) - 1)
3.把整数n在二进制表示下的第k位取反 :n xor (1 << k)
4.把整数n在二进制表示下的第k位赋值1 :n | (1 << k)
5.把整数n在二进制表示下的第k位赋值0 :n & (~(1 << k))
也可以用bitset实现.
(二)lowbit的实现:
n & (~n + 1):推导:~后面的的0都变成1,最后一个1变成0,+1变成1000…
获取每一位1:n = n - lowbit(n)
(三)成对变换
通过计算可以发现,对于非负整数n:
n为偶数时,n xor 1等于n + 1,
n为奇数时,n xor 1等于n - 1,
0与1,1与2,2与3,..n与n + 1构成”成对变换”.
(四)如果进行位运算的时候不进位,那么每一位就是相互独立的,就可以分成每一位分别解决




nut96
2天前
//将b转化成二进制数,a * b = a * (100100...1) = a * 2^(k-1) + a * 2^(k-4) + ... + a * 2^0
//= a * 2^0 + ... + 2^(k-4) + 2^(k-1),类比快速幂,对a进行预处理
int mul(int a, int b, int p)
{
    int res = 0;
    while(b)
    {
        if(b & 1)   res = (res + a) % p;
        b >>= 1;
        a = a * 2 % p;
    }
    return res;
}



nut96
2天前
//先进行预处理(反复平方法),在对指数进行讨论,再将预处理的结果更新到答案
int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while(k)
    {
        if(k & 1)   res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}


活动打卡代码 AcWing 115. 给树染色

nut96
6天前
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1030;
struct Node
{
    int sz, p, s;//sz表示合并后的节点的节点个数,p表示当前节点的父节点,s表示当前的节点的总权值(这一项是用来计算结果的)
    double avg; //表示合并后的节点的平均权值
}node[N];

int n, root;

int find()
{
    double avg = 0;
    int res = 0;
    for(int i = 1; i <= n; i++)
        if(i != root && avg < node[i].avg)
        {
            avg = node[i].avg;
            res = i;
        }
    return res;
}
signed main()
{
    int ans = 0;
    cin >> n >> root;
    //对所有节点的大小,权值,平均权值进行初始化, 对ans进行初始化
    for(int i = 1; i <= n; i++)
    {
        auto &nd = node[i];
        cin >> nd.s;
        nd.sz = 1;
        nd.avg = nd.s;
        ans += nd.s;
    }

    //对所有节点(除根节点以外的点)的父节点进行初始化
    for(int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        node[b].p = a;
    }

    //嵌套两层循环,外层n-1次循环表示合并节点的次数,由于有n个节点,所以要合并n-1次
    for(int i = 0; i < n - 1; i++)
    {
        //找到当前平均权值最大的节点
        int t = find(), f = node[t].p;
        //更新答案
        ans += node[t].s * node[f].sz;
        //找到权值最大的节点以后要删除当前的节点,等价于,下次找最大权值最大的点不会再次找到他
        node[t].avg = -1;
        //将找到的节点和其父节点合并
        for(int j = 1; j <= n; j++)
            if(node[j].p == t)
                node[j].p = f;
        node[f].sz += node[t].sz;
        node[f].s  += node[t].s;
        node[f].avg = (double)node[f].s / node[f].sz;
    }

    cout << ans << '\n';
}



nut96
6天前

求一个字符串的最长回文子串长度
manacher利用了回文的性质,达到线性时间.
首先加一个小优化,在每两个字符之和头尾加没有出现的符号,这里我们使用”^”,”@”和”#”,这样可以使得字符串的长度为奇数,这样就不用讨论回文串长度时奇数还是偶数的问题了

abcde->^#a#b#c#d#e#@

记p[i]表示i能向两边推的最大距离(包括i)的最大距离,求出的最大值就是p[i] - 1,增加字符优化以后回文子串的长度是2*p[i] - 1,那么没增加字符就是p[i] - 1.

假设我们现在要求p[i],我们当前能达到的最右端的下标是R,对应的中点是pos,j是i的对称点.
1.i < R:
(1)L~R是回文,p[i] = p[j] (i的最长回文和j的最长回文相同)

(2)j的最长回文跳出L,那么i的最长回文不一定是j的最长回文,但是蓝色部分肯定满足

综上,p[i] = min(p[2*pos-i],R-i)
2.i >= R
后面的情况未知只能暴力处理

//马拉车模板题
#include <bits/stdc++.h>
using namespace std;
string s, str;
const int N = 2e6 + 10;//注意:使用manacher算法时数组要开大点
int p[N];
void add()
{
    str += "^";
    for(int i = 0; i < s.size(); i++)
    {
        str += "#";str += s[i];
    }
    str += "#";str += "@";
}

int manacher()
{
    add();
    int R = 0, mid = 0, ans = -1;
    for(int i = 1; i < str.size(); i++)
    {
        p[i] = i < R ? min(p[2 * mid - i], R - i) : 1; //进行三种情况的判断
        while(str[i + p[i]] == str[i - p[i]])   p[i]++;//进行中心拓展
        if(i + p[i] > R)                               //如果拓展的坐标超过当前的范围,那么就更新右边界 
        {
            R = i + p[i];
            mid = i;
        }
        ans = max(ans, p[i] - 1);
    }
    return ans;
}
int main()
{
    int n = 0;
    while(cin >> s && s != "END")
    {
        //注意:每次使用manacher算法的时候,如果开了全局变量就没必要传参数了,如果要传参数的话也不要传同名的参数名
        str.clear();
        n++;cout << "Case " << n << ": " << manacher() << '\n';
    }
}


活动打卡代码 AcWing 114. 国王游戏

nut96
7天前
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 100010;
int a[N],b[N];

struct P
{
    int a, b;
    bool friend operator <(P A, P B)
    {
        return (A.a * A.b) < (B.a * B.b);
    }
}p[N];

vector<int> mul(vector<int> A, int b)
{
    int t = 0;
    vector<int> C;
    for(int i = 0; i < A.size(); i++)
    {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while(t)    C.push_back(t % 10), t /= 10;
    return C;
}

vector<int> div(vector<int> &A, int b)
{
    vector<int> C;
    int r = 0;
    for(int i = A.size() - 1; i >= 0; i--)
    {
        r = r * 10 + A[i];
        C.push_back(r /b);
        r %= b;
    }

    reverse(C.begin(), C.end());
    while(C.size() > 1 && C.back() == 0)    C.pop_back();
    return C;
}
//比较两个存在vector中数的大小:可以使用C++对vector内置的<,当按照比较的顺序两个元素的字典序不同时,字典序较小的那个元素所在的
//vector就是较小的vector,可以配合rbegin(),rend(),逆迭代器改变vector之间元素比较的顺序,rbegin()是指向vector最后一个元素位置的迭代器
//而rend()是指向vector第一个元素前面一个元素的迭代器
//具体比较的方法就是:先比较长度,长度长的比较大;利用逆迭代器,从高位开始比较,找出较小的vector
vector<int> max_vec(vector<int> a, vector<int> b)
{
    if(a.size() > b.size()) return a;
    if(a.size() < b.size()) return b;
    if(vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend()))   return a;
    return b;
}
int main()
{
    int n;
    cin >> n;

    for(int i = 0; i <= n; i++)  cin >> p[i].a >> p[i].b;
    sort(p + 1, p + n + 1);

    vector<int> lfpd(1, 1);//lfpd表示除自身以外的前面的人的左手的数字的乘积
    vector<int> ans(1, 0);
    for(int i = 0; i <= n; i++)
    {
        if(i)   ans = max_vec(ans, div(lfpd, p[i].b));
        lfpd = mul(lfpd, p[i].a);
    }
    for(int i = ans.size() - 1; i >= 0; i--)    cout << ans[i];
    puts("");

}



nut96
8天前
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 100010;

vector<int> mul(vector<int> &A, vector<int> &B)
{
    vector<int> c;//用于存储答案
    c.resize(A.size() + B.size() + 1);
    for(int i = 0; i < A.size(); i++)
    {
        int t = 0;//t表示进位
        for(int j = 0; j < B.size(); j++)
        {
            c[i + j] += A[i] * B[j] + t;
            t = c[i + j] / 10;
            c[i + j] %= 10;
        }
        //每次进行循环之后的进位
        c[i + B.size()] += t;
    }
    //去除前导0
    while(c.size() > 1 && !c.back())    c.pop_back();
    return c;

}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i--)  A.pb(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--)  B.pb(b[i] - '0');
    vector<int> c = mul(A, B);
    for(int i = c.size() - 1; i >= 0; i--)   cout << c[i];
}


活动打卡代码 AcWing 112. 雷达设备

nut96
8天前
#include <bits/stdc++.h>
#define PDD pair<double, double>
#define fi first
#define se second
using namespace std;
const int N = 1010;
PDD seg[N];
int main()
{
    int n, d, ans = 0;
    cin >> n >> d;
    for(int i = 0; i < n; i ++ )
    {
        int x, y;
        cin >> x >> y;
        if(y > d)
        {
            ans = -1;//非法
            break;
        }
        auto len = sqrt(d * d - y * y);
        seg[i] = {x + len, x - len};
    }
    sort(seg, seg + n);
    double eps = 1e-6, ed = -1e10;
    if(ans != -1)
    {
        for(int i = 0; i < n; i ++ )
        {
            auto t = seg[i];
            if(t.se> ed + eps)
            {
                ans++;
                ed = t.fi;
            }
        }
    }
    cout << ans << '\n';

}


活动打卡代码 AcWing 111. 畜栏预定

nut96
8天前
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

struct SEG
{
    double l, r;
    bool friend operator < (SEG A, SEG B)
    {
        return A.r < B.r;
    }
}seg[N];
int main()
{
    int n, d, ans = 0;
    cin >> n >> d;
    for(int i = 0; i < n; i ++ )
    {
        int x, y;
        cin >> x >> y;
        if(y > d)
        {
            ans = -1;//非法
            break;
        }
        auto len = sqrt(d * d - y * y);
        seg[i] = {x - len, x + len};
    }
    sort(seg, seg + n);
    double eps = 1e-6, ed = -1e10;
    if(ans != -1)
    {
        for(int i = 0; i < n; i ++ )
        {
            auto t = seg[i];
            if(t.l> ed + eps)
            {
                ans++;
                ed = t.r;
            }
        }
    }
    cout << ans << '\n';

}


活动打卡代码 AcWing 110. 防晒

nut96
8天前
//贪心策略:对每头奶牛以minSPF递减的顺序排序,然后对于每头奶牛,在所有可用的防晒霜中挑选SPF值最大的
//证明:(决策包容性)对于每头奶牛,由于挑选防晒霜的时候会同时受minSPF和maxSPF限制,在讨论当前的奶牛的时候,我们要考虑当前的选择会不会对后面的奶牛的选择造成不利的影响
//假如有两瓶不同的防晒霜x, y且SPF[x] < SPF[y],对于b奶牛来说都可以使用.那么后面的奶牛就有可能出现"x,y都能用","x,y都不能用","x能用,y不能用"这三种结果,此时b奶牛肯定是选SPF值大的那瓶
//(范围缩放)每头奶牛对答案的贡献至多是1,即使让当前的奶牛放弃日光浴,留下防晒霜给后面的某一头奶牛使用,对答案的贡献也不会变得更大.所以这个策略是正确的贪心策略
//直觉:让minSPF值高的奶牛用SPF值高的防晒霜
#include <bits/stdc++.h>
#define fi first
#define se second
#define PII pair<int, int>
using namespace std;
const int N = 2510;
PII cows[N];
map<int, int> SPF;

int main()
{
    //n头奶牛,m种防晒霜
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++ )    cin >> cows[i].fi >> cows[i].se;
    sort(cows, cows + n);
    for(int i = 0; i < m; i ++ )    
    {
        int spf, cover;
        cin >> spf >> cover;
        SPF[spf] += cover;//注意这里得使用+=,因为存在防晒值相同的防晒霜
    }

    int ans = 0;
    SPF[0] = SPF[1001] = n;//设置哨兵值
    for(int i = n - 1; i >= 0; i -- )
    {
        auto it = SPF.upper_bound(cows[i].se); it--;//upper_bound是大于一个数的最小的数,返回的迭代器减一就是小于等于的最大的数,lower_bound是大于等于一个数的最大的数,可以用于找寻map的边界值
        if(it->fi >= cows[i].fi)
        {
            ans++;
            (it->se)--;
            if(it->se == 0)   SPF.erase(it);
        }
    }
    cout << ans << '\n';
    return 0;

}