$$ZROI week2$$

首先考虑最少的拐点肯定是那种螺旋形状的，然后手玩几个数据发现和列数（行数）有关，且每增加1就是上一个状态加2，直接\(O(1)\)公式即可

吐槽：为啥\(n,m\)不给成\(10^{18}\)次方？？

一眼就能看出双向搜索，首先打了个暴力企图对拍，先交了上去，\(WA?\)，发现和本地输出不一样，搞这个搞了半个小时还是没搞出为什么，然后我用其他的\(IDE\)测发现还是这个毛病，我的双向搜索就没敢交，也不知道改了哪里一个暴力就交过了。

最终得了60分。

• 巧妙的思路：由于贡献是一定的，所以考虑预处理出贡献，一遍\(dfs\)即可。
• 正解的思路：双向搜索，二分查找统计贡献。

想了一会儿想了个线段树的办法，然后疯狂写，一个半小时过去，死了

考虑一个对称中心\(T\)，统计出至少多少个字母对称就会产生一个贡献，显然信息量是\(O(N)\)的，这个统计完了之后可以用线段树区间加和区间\(max\)去求解。

然后就死了

事实证明我的方法还是对的

正解就是把线段树统计换成一些奇奇怪怪的，例如前缀和一类的东西。

当我写到这个题已经没时间了（10min），想了一会儿想出了正解，对于每条边建立两个点，链内同向，链间反向，在\(LCA\)处统计贡献即可。

懒得写了

还是敲了一手暴力交了上去，本想再拿点分发现没时间了。

正解其实和我思路差不多，考虑把没有贡献的地方缩成一个点，然后快速幂计算即可。

会的总是拿不上分有点难受，希望下次更加努力。

作业

题目大意：有\(n\)个物品，\(m\)块钱，给定每个物品的价格，求买物品的方案数

范围：\(n \leq 40,m \leq 10^{18}\)

题解：

如果直接凑是\(2^{40}\)的复杂度，发现贡献是可以合并的，考虑双向搜索，每一半用\(2^{20}\)去搞，最后合并起来即可。

复杂度：\(O(2^{20} + 2^{20})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e6 + 10;
ll a[50];
int lim;
int cnt1;
int cnt2;
ll A[MAXN];
ll B[MAXN];
int n;
ll m;
ll ans;
int mid;

void dfs1(int now,ll sum) {
    if(now > mid) {
        A[++cnt1] = sum;
        return;
    }
    dfs1(now + 1,sum);
    if(sum + a[now] <= m) {
        dfs1(now + 1,sum + a[now]);
    }
}

void dfs2(int now,ll sum) {
    if(now > lim) {
        B[++cnt2] = sum;
        return;
    }
    dfs2(now + 1,sum);
    if(sum + a[now] <= m) {
        dfs2(now + 1,sum + a[now]);
    }
}

signed main () {
    scanf("%d %lld",&n,&m);
    for(int i = 1;i <= n; ++i) {
        scanf("%lld",&a[++lim]);
        if(a[lim] > m) --lim;
    }
    mid = lim >> 1;
    dfs1(1,0);
    dfs2(mid + 1,0);
    sort(A + 1,A + cnt1 + 1);
    sort(B + 1,B + cnt2 + 1);
    for(int i = 1,j = cnt2;i <= cnt1; ++i) {
        while(A[i] + B[j] > m and j) --j;
        if(j == 0) break;
        ans += j;
    }
    cout<<ans<<endl;
    return 0;
}

第一眼看到觉得是一个差分约束，第二眼觉得是个并查集。。。

并查集：考虑维护一个到根的路径权值，合并时判断即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int read () {
    int q=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(isdigit(ch)){
        q=q*10+ch-'0';ch=getchar();
    }
    return q*f;
}
int f[MAXN];
int a[MAXN];
int find(int x) {
    if(x == f[x]) {
        a[x] = 0;
        return x;
    }
    int res = find(f[x]);
    a[x] = a[x] + a[f[x]];
    return f[x] = res;
}
int n,m;
int tag;
int main () {
//    freopen("1.in","r",stdin);
//    freopen("ans.out","w",stdout);
    int T = read();
    while(T--) {
        tag = 0;
        n = read(),m = read();
        for(int i = 1;i <= n + 1; ++i) {
            f[i] = i;
        }
        memset(a,0,sizeof a);
        while(m--) {
            int s = read(),t = read(),val = read();
            int l = find(s);
            int r = find(t + 1);
            if(l != r) {
                f[l] = r;
                a[l] = a[t + 1] - a[s] - val;
            }
            else if(a[t + 1] - a[s] != val) tag = 1;
        }
        cout<<(tag == 0 ? "true" : "false")<<endl;
    }
    return 0;
}

差分约束：按照输入的方法建一张图，跑可行的\(spfa\)即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int read () {
    int q=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(isdigit(ch)){
        q=q*10+ch-'0';ch=getchar();
    }
    return q*f;
}

int n,m;

struct edge {
    int to;
    int nxt;
    int w;
}e[MAXN << 1];
int cnt;
int vis[MAXN << 1];
int inq[MAXN << 1];
int dis[MAXN << 1];
int head[MAXN << 1];
void add(int u,int v,int w) {
    e[++cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
    e[cnt].w = w;
}
int spfa(int now) {
    vis[now] = 1;
    inq[now] = 1;
    for(int i = head[now];i;i=e[i].nxt) {
        int y = e[i].to;
        if(dis[y] > dis[now] + e[i].w) {
            dis[y] = dis[now] + e[i].w;
            if(inq[y] or spfa(y) == 0) return 0;
        }
    }
    inq[now] = 0;
    return 1;
}
int tag;
int T;
int main () {
    //freopen("1.in","r",stdin);
    //freopen("ans.out","w",stdout);
    T = read();
    while(T--) {
        n = read(),m = read();
        cnt = 0;
        memset(inq,0,sizeof inq);
        memset(vis,0,sizeof vis);
        memset(head,0,sizeof head);
        memset(dis,0x3f,sizeof dis);
        for(int i = 1;i <= m; ++i) {
            int x = read(),y = read(),z = read();
            add(x ,y - 1,z);
            add(y - 1, x , z);
        }
        tag = 0;
        for(int i = 0;i <= n; ++i) {
            if(!vis[i]) {
                dis[i] = 0;
                cout<<spfa(i)<<endl;
                if(spfa(i) == 0) {
                    puts("false");
                    tag = 1;
                    break;
                }
            }
        }
        if(!tag) puts("true");
    }
    return 0;
}

吐槽：\(map\)定义的\(vis\)数组难道不能标记？

本意就是相当于将一些数划分成两个相等的集合，这里集合相等表示集合的数之和相等，数可以不划分完。

直接处理是\(3^n\)的，为什么？

对于每个数有三种情况：选到左边，选到右边，不选。

直接暴力的话就是\(3^{20}\)，显然是不行的。

考虑折半搜索，先处理一半的数据，再在另一半中找和，判断状态是否相同加和即可。

注意不要算0.

upd : 注意判重

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1 << 22;
int n;
int a[41];
int vis[MAXN];
int ans;
vector<int>v[MAXN];
map<int,int> mp;
map <int ,int > jud;
int cnt;
#define mid n / 2
void dfs1(int now,int sum,int sta) {
    if(now > mid) {
        if(!mp.count(sum)) {
            mp[sum] = ++cnt;
        }
        v[mp[sum]].push_back(sta);
        return;
    }
    dfs1(now + 1,sum + a[now],sta | (1 << (now - 1)));
    dfs1(now + 1,sum - a[now],sta | (1 << (now - 1)));
    dfs1(now + 1,sum,sta);
}

void dfs2(int now,int sum,int sta) {
    if(now > n) {
        if(!mp.count(sum)) {
            return;
        }
        int res = mp[sum];
        if(jud[res] == 0) {
            sort(v[res].begin(),v[res].end());
            v[res].resize(unique(v[res].begin(),v[res].end()) - v[res].begin());
            jud[res] = 1;
        }
        for(int i = 0;i < v[res].size(); ++i) {
            if(!vis[v[res][i] | sta]) {
                ans ++;
            }
            vis[v[res][i] | sta] = 1;
        }
        return;
    }
    dfs2(now + 1,sum + a[now],sta | (1 << (now - 1)));
    dfs2(now + 1,sum - a[now],sta | (1 << (now - 1)));
    dfs2(now + 1,sum,sta);
}

int main () {
    cin >> n;
    for(int i = 1;i <= n; ++i) {
        cin >> a[i];
    }
    dfs1(1,0,0);
    dfs2(mid+1,0,0);
    cout<<ans - 1<<endl;
    return 0;
}

区间修改和查询

树状数组维护即可，对于开根操作暴力即可，数据比较水…

或者写个线段树维护单点开根的\(tag\)。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define lowbit(x) x & -x
#define int long long
const int MAXN = 3e6 + 10;
int c[MAXN];
int a[MAXN];
int num[MAXN];
int n;
int m;
int read () {
    int q=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(isdigit(ch)) {
        q=q*10+ch-'0';ch=getchar();
    }
    return q*f;
}
void add(int x,int k) {
    for(int i = x;i <= n;i += lowbit(i)) {
        c[i] += k;
    }return;
}

int ck(int x) {
    int ans = 0;
    for(int i = x;i; i -= lowbit(i)) {
        ans += c[i];
    }
    return ans;
}

int get1(int l,int r) {
    return r - l + 1 - (num[r] - num[l - 1]);
}

void change(int l,int r) {
    if(ck(r) - ck(l - 1) <= get1(l,r)) return;
    for(int i = l;i <= r; ++i) {
        if(a[i] > 1) {
            int tmp = sqrt(a[i]);
            add(i,tmp - a[i]);
            a[i] = tmp;
        }
    }
}
//#include <ctime>

//clock_t st,ed;
signed main () {
    ////freopen("11.in","r",stdin);
    //freopen("ans.out","w",stdout);
    //st = clock();
    n = read();
    for(int i = 1;i <= n; ++i) {
        a[i] = read();
        if(a[i] == 0) {
            num[i] = num[i - 1] + 1;
        }
        else num[i] = num[i - 1];
        add(i,a[i]);
    }
    m = read();
    for(int i = 1;i <= m; ++i) {
        int opt = read(),l = read(),r = read();
        if(opt == 1){
            cout<<ck(r) - ck(l - 1)<<endl;
        }
        if(opt == 2) {
            change(l,r);
        }
    }
//    ed = clock();
//    cout<<(ed - st) / 1000<<endl;
    return 0;
}