头像

苏醒


访客:1592

离线:1天前



苏醒
22天前
# 代码的搬运工

先是定义动态规划集合
f[i][0], f[i][1] 分别代表i为根的子树种无白和有一白的数量
如果i是白色的,f[i][0] = 0;

f[i][1] = TT(连乘)( f[k][0](不断开) + f[k][1](断开有白));

i是黑色,f[i][0] = TT(连乘)( f[k][0](不断开) + f[k][1](断开有白) );

f[i][1] = E(连加) (f[j][1] * TT(k != j) ( f[k][0](不断开) + f[k][1](断开有白)));

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, mod = 1e9 + 7;
typedef long long LL;
int color[N];
int f[N][2];
int h[N],e[N],ne[N],idx;
int q[N],mul[N],l[N], r[N];
void add(int a,int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u){
    for(int i = h[u]; ~i; i = ne[i]) dfs(e[i]);
    if(color[u] == 0){
        f[u][1] = 1;
        for(int i = h[u]; ~i;i = ne[i]) f[u][1] = (LL)f[u][1] * (f[e[i]][0] + f[e[i]][1]) % mod;
    }else{
        f[u][0] = 1;
        for(int i = h[u]; ~i;i = ne[i]) f[u][0] = (LL)f[u][0] * (f[e[i]][0] + f[e[i]][1]) % mod;
        int k = 0;
        for(int i = h[u]; ~i;i = ne[i]) q[++k] = e[i];//把紫薯全存进去
        //mul[q[1]] = 1;
        for(int i = 1, p= 1; i <= k;i++) //mul[q[i]] = (LL)mul[q[i-1]] * (f[q[i-1]][0] + f[q[i-1]][1]) % mod;
        {
            mul[i] = p;
            p = (LL)p * (f[q[i]][0] + f[q[i]][1]) % mod;
        }
        for(int i = k,p = 1; i >=1;i--) {
            mul[i] =(LL)mul[i] * p %mod;
            p = (LL) p* (f[q[i]][0] + f[q[i]][1]) % mod;
        }
        // l[0] = r[k+1] = 1;
        // for(int i = 1;i <= k;i++) l[i] = (LL)l[i-1] * (f[q[i]][0] +f[q[i]][1])%mod;
        // for(int i = k;i >= 1;i--) r[i] = (LL)r[i+1] * (f[q[i]][0] +f[q[i]][1])%mod;
        f[u][1] = 0;
        for(int i = 1; i <= k; i++ ){
            f[u][1] = (f[u][1] + (LL) f[q[i]][1] * mul[i] )% mod;
            //f[u][1] = (f[u][1] +(LL)l[i - 1] * r[i+1]% mod * f[q[i]][1] )% mod;
        }

    }
}
int main(){
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i < n;i++){
        int k;
        cin >> k;
        add(k,i);//k是根
    }
    for(int i = 0;i < n;i++) cin >> color[i];
    dfs(0);
    cout << f[0][1];
    return 0;
}



苏醒
22天前

算法1

(合并区间)

同行同列合并区间 并且计算染黑的总数(多于实际)
然后每行每列判断 是否相交,相交则–

时间复杂度

n2

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 10010;
struct Segment{
    int k;//行号或列号
    int l,r;//左右坐标
    bool operator < (const Segment& w)const{//重载 先按行/列,再按左右端点
        if(k != w.k) return k < w.k;
        if(l != w.l) return l < w.l;
        return r < w.r;
    }
};

LL merge(vector<Segment> &q)
{
    vector<Segment> w;//合并的临时对象
    sort(q.begin(),q.end());//nlogn
    LL res = 0;
    for(int i = 0; i < q.size();){//+
        int j = i;
        while(j < q.size() && q[j].k == q[i].k) j++;//相同行/列坐标范围
        int l = -2e9, r = l-1;
         for(int k = i; k < j;k++) {//+,++是On
            if (r < q[k].l) {
                res += r - l + 1;
                if (l != -2e9) w.push_back({q[i].k, l, r});
                l = q[k].l, r = q[k].r;
            } else r = max(q[k].r, r);
        }
        if(l != -2e9) w.push_back({q[i].k, l,r});//做后一组塞进去
        res += r - l + 1;
        i = j;
    }
    q = w;//拷贝回来 直接等于号就行
    return res;
}

int main()
{
    int n;
    cin >> n;
    vector<Segment> rows, cols;

    while (n--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 == x2) cols.push_back({x1,min(y1,y2), max(y1,y2)});
        else rows.push_back({y1, min(x1,x2), max(x1,x2)});
    }

    LL res = merge(rows) + merge(cols);
    for(auto r:rows)
        for(auto c:cols)
            if(r.k >= c.l && r.k <= c.r && c.k >= r.l && c.k <=r.r)//判断是否在范围内//n2
                res--;
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 875. 快速幂

苏醒
1个月前
#include<iostream>
using namespace std;
typedef long long LL;
int myPow(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res =(LL) res * a % p;
        k >>=1;
        a =(LL) a * a % p;
    }

    return res;
}



int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        int a,k, p;
        scanf("%d%d%d",&a,&k,&p);
        printf("%d\n",myPow(a,k,p));
    }
    return 0;
}


活动打卡代码 AcWing 873. 欧拉函数

苏醒
1个月前
#include<iostream>
using namespace std;
//分解质因数 sqrt(n)
int main(){
    int n;
    cin >> n;
    while(n--){
        int a;
        cin >> a;
        int res = a;
        for(int i = 2; i <= a / i;i++)//质因子不过a/i
        {
            if( a % i == 0){
                res = res / i *(i - 1);
                while(a%i == 0) a /= i;

            }
        }
        if(a > 1) res = res / a *(a - 1);
        cout << res<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 125. 耍杂技的牛

苏醒
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50010;
pair<int,int> cows[N];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n ;i++){
        int w,s;
        cin >> w >> s;
        cows[i] = {w+s, w};
    }
    sort(cows, cows + n);
    int res = -2e9, sum = 0;//牛背上的牛总重
    for(int i = 0; i < n; i++){
        int w = cows[i].second, s = cows[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

苏醒
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int a[N];
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n;i++) cin >> a[i];
    sort(a, a+ n);
    int res = 0;
    for(int j = 0;j < n;j++) res += abs(a[j] - a[ n / 2]);
    cout << res;
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

苏醒
1个月前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;

int main(){
    int n;
    cin >> n;
    vector<int> v;
    while(n--) {
        int a;
        cin >>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    long long ans = 0;
    for(int i = 0;i < v.size();i++){
        ans += (v[i] * (v.size() - 1 - i));
    }
    cout <<ans;
    return 0;

}


活动打卡代码 AcWing 148. 合并果子

苏醒
2个月前

每次合并两个就可以了

#include<iostream>
#include<queue>
using namespace std;
// const int 
int main(){
    int n;
    cin >>n;
    priority_queue<int , vector<int>, greater<int> > heap;
    while(n--){
        int x;
        cin >> x;
        heap.push(x);
    }
    int res = 0;
    while(heap.size() > 1){//至少两个数啊
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a+b);
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

苏醒
2个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
struct Range{
    int l,r;
    bool operator< (const Range& w) const{
        return l < w.l;
    }
}range[N];

int main(){
    int st,ed;
    cin >> st >> ed;
    int n;
    cin >> n;
    for(int i = 0; i < n;i++){
        int l,r;
        cin >>l>>r;
        range[i] = {l,r};
    }
    sort(range, range + n);
    bool success = false;
    int res = 0;
    for(int i = 0; i < n; i++){
        int j = i, r = -2e9;
        while(j < n && range[j].l <= st){
            r = max(r, range[j].r);

            j++;

        }
        if(r < st) break;
        res++;

        if(r >= ed) {
            success = true;
            break;
        }
        st = r;
        i = j - 1;//因为j➕到六亲不认了,回退一个
    }

    if(success) cout <<res;
    else cout <<-1;
    return 0;

}



活动打卡代码 AcWing 905. 区间选点

苏醒
2个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
struct Range{
    int l,r;
    bool operator< (const Range& w)const{
        return r < w.r;
    }
}range[N];//按右端点排序;

int main(){
    int n;
    cin >> n;
    int nn = n;
    for(int i = 0;i < n;i++)
    {
        int l,r;
        cin >>l>>r;
        range[i] = {l,r};
    }
    sort(range, range+n);
    int res = 0, ed = -2e9;
    for(int i = 0;i < n;i++)
        if(range[i].l > ed){
            res++;
            ed = range[i].r;
        }
    cout << res;
    return 0;
}