周报2

补题1:[蓝桥杯2013国AC]网络寻路
题意：找出包含四个结点的路径条数，源结点和终结点可以相同，但中间节点必须不同。

做法：dfs暴力搜简单易想，但是会TLE。另一种巧妙的做法，枚举每一条边(最多1e5条)，固定每一条边，ans+=(du[u]-1)*(du[v]-1)*2;即为答案。一条边固定两个端点，剩下两个端点在相互配对，又因为有正反向，所以乘2。

void solve(){           //D  补题，较为巧妙的想法,枚举每一条边，两个端点的度数相乘再乘二(正反向); 时间复杂度o(m)
    int n,m,ans=0;
    cin>>n>>m;
    int du[10004]={0};
    vector<pair<int,int>> edge;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        du[u]++,du[v]++;
        edge.emplace_back(u,v);
    }
    for(auto e:edge){
        ans+=(du[e.first]-1)*(du[e.second]-1)*2;
    }
    cout<<ans<<endl;
}

补题2:[蓝桥杯2022国B]搬砖

题意：n块砖，重量为w，价值为i。从这些砖中选一些出来从下到上堆成一座塔，并且对于塔中的每一块砖来说，它上面所有砖的重量和不能超过它自身的价值。这样堆成的塔的总价值（即塔中所有砖块的价值和）最大是多少。

做法：找到排序方法，01背包，从上往下dp。

for(int i=1;i<=n;i++){      //排序后从上往下第i个物品
        for(int j=arr[i].w+arr[i].v;j>=arr[i].w;j--){     
            //j是可放重量;j从arr[i].w+arr[i].v开始是因为这样可以保证符合条件的上一个物品可以被取到，到arr[i].w止是再小就不能放i物品了
            //样例:2 10-9 20-11
            dp[j]=max(dp[j],dp[j-arr[i].w]+arr[i].v);
            ans=max(dp[j],ans);
        }
    }

补题3:[蓝桥杯2014省AB]

题意：给定一个n*m的矩阵，每个格子都有价值不等的物品。入口在左上角，出口在右下角。只能往右或往下走。走过某个格子时，如果那个格子中的宝贝价值比手中任意宝贝价值都大，则可以拿起它(也可以不拿)。有多少种不同的行动方案能获得k 件宝贝。

过程：暴力dfs-->记忆化搜索(AC)-->dp。。。

补题4:Setsuna的K数列

int mod=1e9+7;
void solve(){           //D  想到了是k进制相关，就是没发现K数列本质就是每一个K进制位只能取0或1，即第n个数就是把n表示成二进制然后按K进制还原即可
    int n,k;
    cin>>n>>k;
    int ans=0,cur=1;
    while(n){
        if(n&1) ans=(ans+cur)%mod;
        cur=cur*k%mod;
        n>>=1;
    }
    cout<<ans<<endl;
}

反思：赛时一直在找规律，找规律，期间也发现了K进制这个特点。的确是有些规律，但是陷进一个错误的思维里面。就是没发现K数列本质就是每一个K进制位只能取0或1，即第n个数就是把n表示成二进制然后按K进制还原即可。

补题5:剪绳子

题意：在0到10的数轴上，输入有两种操作：A x；C x；A是询问x所在的线段多长；C是从x点剪开数轴。Cx不会是0或10；Ax不会是Cx中出现过的，但是可能是0或10；对于每一次A询问，输出长度。

做法有两种：                                                                                                                                                                                                                                                                                第一种是STL+二分：维护一个set，里面存的是操作中C的点。遇到A时，通过二分在set中找到第一个>=x的数，和第一个>x的数。因为没有比10大的数，特判一下A 10的情况即可。

void solve(){       //L 剪绳子--STL  法①并查集  法②set--巧妙
    cout<<fixed<<setprecision(5);
    int n;
    cin>>n;
    set<double> st;
    st.insert(0),st.insert(10);  //两个端点
    char op;
    double num;
    while(n--){
        cin>>op>>num;
        if(op=='A'){
            auto pos1=lower_bound(st.begin(),st.end(),num); //第一个>=num的pos
            auto pos2=upper_bound(st.begin(),st.end(),num); //第一个>num的pos
            if(pos2==st.end()) cout<<10-*(--pos1)<<endl;   //特例！！
            else cout<<(*pos2)-*(--pos2)<<endl;
        }
        if(op=='C') st.insert(num);
    }
}

第二种是并查集：这个方法比较麻烦，写了一下而且最终也没能AC。因为输入有五位小数，可以把他们都扩大1e5倍，成为一个整数。先要把输入的数据全部读入保存。  并且用map把Cx的端点都标记一下。再从0到1000000，遍历，把线段分为各自集合，并且记录每个集合大小。接着再倒着遍历存了所有输入数据的数组，遇到Ax直接输出cnt[find(x)]。遇到Cx则Union(x-1,x);不知道是因为精度还是什么问题，写的代码只有60分;但是最主要这题收获的是要有这种把小数变正数，再使用并查集的想法，还有逆向思维的。

补题6:XOR-distance

题意：给出三个正数a,b,r；找出0<=x<=r，| (aXORx) - b(XOR)x |的最小值。

做法：这题是挺好的位运算练习题。a,b异或同一个数字，转到二进制其实就是找一个数字，这个数字要满足区间范围，而且从高位到低位给这个数字x填数。是填0还是1，取决于a,b在该位的二进制值。有个很重要的细节！！！就是1<<64会溢出，需要写成1ll<<64！！使用 (1ll<<k) 来计算一个大于 int 范围的位运算值。

void solve(){           //C  应该从高位到低位检查，而不是从低位到高位
//    bitset<20> arr=a;  //从低位到高位存的
//    bitset<20> brr=b;
//    string str1=arr.to_string();  //str1是高位到低位的
//    string str2=brr.to_string();
//    cout<<str1<<endl<<str2<<endl;
//    str1=str1.substr(str1.find('1'));  //去除多余的0
//    str2=str2.substr((str2.find('1')));
//    cout<<str1<<endl<<str2<<endl;
//    for(int i=0;i<19;i++) cout<<arr[i];
//    cout<<endl;
//    for(int i=0;i<19;i++) cout<<brr[i];
    int a,b,r;
    cin>>a>>b>>r;
    if(a>b) swap(a,b);  //lit小big大
    bitset<64> aa=a,bb=b;
    string lit,big;
    lit=aa.to_string(),big=bb.to_string();
    int take=0;
    for(int i=0;i<=63;i++){
        if(lit[i]==big[i]) continue;
        //int cur=(1<<(63-i));--wrong!!
        int cur=(1ll<<(63-i));                          //位运算的细节！！！ 1<<64是不行的！！  需要1ll<<64
        if(lit[i]=='0' && cur+take<=r && b-a>=2*cur){
            b-=cur,a+=cur;
            take+=cur;
        }
    }
    cout<<b-a<<endl;
}