杂好题汇总

拼搏现实的明天。 2024-04-17 05:58 81阅读 0赞

## 1、hdu 6705 path ##

## 题意：有向图求第k大路径（权值和），每条边可以走无数次。 ##

## 分析：因为k很小，所以应该是预处理出前k大路径，首先想到的是贪心，大致想法是用一个优先队列弹出前k个，无奈后面没想明白，看了题解才恍然大悟。首先把每个点出边按权值排序，每个点权值最小的出边最有可能是前k大，n个点中出边最小的一定是最小的，确定完之后还要考虑这个点和其他点组成路径，要保证最小，只能和这条边的出点的权值最小的出边相连，还有一种情况，就是从起点走后一大的边到达出点，有点绕，画个图就很容易理解了。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 5e4+5;
    int t,n,m,q,qu[N],ans[N],qmx;
    vector<pair<int,int> > g[N];
    
    struct nd {
        int u,len,id;
        bool operator < (const nd &b) const {
            return len > b.len;
        }
    };
    
    void bfs() {
        priority_queue<nd> pq;
        for(int i=1;i<=n;i++)
            if(g[i].size()) pq.push({i,g[i][0].first,0});
        int cnt=0;
        while(!pq.empty()) {
            nd tp = pq.top();
            pq.pop();
            ans[++cnt] = tp.len;
            if(cnt == qmx) break;
            if(tp.id + 1 < g[tp.u].size())
                pq.push({tp.u, tp.len-g[tp.u][tp.id].first+g[tp.u][tp.id+1].first, tp.id+1});
            int v = g[tp.u][tp.id].second;
            if(g[v].size())
                pq.push({v, tp.len+g[v][0].first, 0});
        }
        for(int i=1;i<=q;i++) printf("%d\n",ans[qu[i]]);
    }
    
    int main(){
        scanf("%d",&t);
        while(t--) {
            qmx = 0;
            scanf("%d%d%d",&n,&m,&q);
            for(int i=1;i<=m;i++) {
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                g[u].push_back({w,v});
            }
            for(int i=1;i<=n;i++)
                sort(g[i].begin(),g[i].end());
            for(int i=1;i<=q;i++)
                scanf("%d",&qu[i]),qmx=max(qmx,qu[i]);
            bfs();
            for(int i=1;i<=n;i++) g[i].clear();
        }
    	return 0;
    }

## 2、2018-2019 XIX Open Cup, Grand Prix of Korea L .Timsort ##

## 题意：给定长度为N的数组a\[\]，Q次询问，每次给出长度L，让你按照规定跑。 每次从当前位置出发，一直跑不降序列，或者下降序列。跑完后，如果大于等于L，从下一个位置继续开始，否则要凑齐长度L，同时累计凑数的个数（不好的元素）。注意最后一段长度可以小于L，但是要累计不好的元素，因为这个还wa了一发。 ##

## 分析：我们可以从后往前预处理出每一个元素不降或者下降延伸到的最右端的位置。然后暴力查询计数就好了。计算的结果可以保存下来，如果下次有相同的询问直接输出，所以最坏情况下的复杂度为n/1+n/2+...+n/n~=nlogn，可以跑的很快。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e6+5;
    int n,q,a[N],r[N],ans[N],b[N];
    
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int fg = (a[n]<a[n-1]) ? 1 : -1,R=n;
        r[n]=r[n-1]=n;
        for(int i=n-1;i>1;i--) {
            if(a[i]<a[i-1]) {
                if(fg==1) r[i-1]=R;
                else fg=1,R=i,r[i-1]=R;
            }else {
                if(fg==-1) r[i-1]=R;
                else fg=-1,R=i,r[i-1]=R;
            }
        }
        scanf("%d",&q);
        while(q--) {
            int x;
            scanf("%d",&x);
            if(ans[x]) printf("%d %d\n",ans[x],b[x]);
            else {
                for(int i=1;i<=n;) {
                    if(n-i+1<x) {
                        ans[x]++;
                        b[x]+=n-r[i];
                        break;
                    }
                    if(x<=r[i]-i+1) i=r[i]+1,ans[x]++;
                    else ans[x]++,b[x]+=(i+x-1-r[i]),i+=x;
                }
                printf("%d %d\n",ans[x],b[x]);
            }
        }
    	return 0;
    }

## 3、ACM Amman Collegiate Programming Contest (2018) A. Careful Thief ##

## 题意：数轴上有1e9个点，有n(1e5)个区间，每个区间内所有点有一个相同的值ai，你可以从任意一个点开始取连续的k个数，使得这个区间的所有位置的权值加起来最大，输出最大权值， 所有区间不重叠。   分析：取法一定是起点在某个区间的起点或者终点在某个区间的终点，直接枚举区间起点利用二分找到相应终点求出一个最优解，再通过直接枚举区间终点利用二分找到相应起点来求出另一个最优解，取二者最小值即可。   代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=1e6+5;
    struct nd{
        ll l,r,v;
    }p[N];
    ll t,m,k,sum[N],R[N],L[N];
     
    bool cmp(nd a,nd b) {
        return a.l<b.l;
    }
     
    int main(){
        scanf("%lld",&t);
        while(t--){
            scanf("%lld%lld",&m,&k);
            for(int i=1;i<=m;i++)
                scanf("%lld%lld%lld",&p[i].l,&p[i].r,&p[i].v);
            sort(p+1,p+1+m,cmp);
            for(int i=1;i<=m;i++){
                sum[i]=sum[i-1]+p[i].v*(p[i].r-p[i].l+1);
                R[i]=p[i].r;
                L[m-i+1]=-p[i].l;
            }
            ll ans=0;
            for(int i=1;i<=m;i++){
                int xx=lower_bound(R+1,R+1+m,p[i].l+k-1)-R;
                ll s=sum[xx-1]-sum[i-1];
                if(xx<=m) s+=(max(0ll,min(p[i].l+k-1,R[xx])-p[xx].l+1))*p[xx].v;
                ans=max(s,ans);
            }
            for(int i=m;i>=1;i--){
                int xx=lower_bound(L+1,L+1+m,-p[i].r+k-1)-L;
                ll s=sum[i]-sum[m-(xx-1)];
                if(xx<=m) s += max(0ll,(min(-p[i].r+k-1,L[xx])-(-p[m-xx+1].r)+1))*p[m-xx+1].v;
                ans=max(s,ans);
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

## 4、HDU 6719 Strassen ##

## 题意：我们只有两种方法计算两个n×n的矩阵的乘积，第一种为定义法，需要n^3次乘法和(n−1)\*n^2次加法。第二种为Strassen分治法，仅当n为偶数时可以使用，需要18(n/2)\*(n/2)次加法以及再计算7次大小为(n/2)×(n/2)的矩阵的乘积。这7次更小矩阵的乘积也可以选择两种方法之一计算。现假设计算机计算一次加法需要a单位时间，计算一次乘法需要b单位时间，其他任何操作不花费时间，问计算两个n×n的矩阵的乘积至少需要多少时间。输出答案模10^9+7的余数。 ##

## 分析：水题，大数用\_\_128int的话更方便。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int mo=1e9+7;
    typedef __int128 lll;
    int t,a,b;
    long long n;
    
    lll calc(lll n) {
        lll ans=n*n*n*b+(n-1)*n*n*a;
        if(n%2==0)
        ans=min(ans,18*(n/2)*(n/2)*a+7*calc(n/2));
        return ans;
    }
    
    int main(){
        scanf("%d",&t);
        while(t--) {
            scanf("%lld%d%d",&n,&a,&b);
            printf("%d\n",int(calc(n)%mo));
        }
        return 0;
    }

## 5、Codeforces 1136D Nastya Is Buying Lunch ##

## 题意：给你和一个数组（是一个排列）和一些二元组，二元组(x, y)表示如果x正好在y前面而且相邻，那么x和y可以交换位置，问最后一个元素最多可以向前移动多少步？ ##

## 分析：思维题，没想出来，看了题解才懂。从后往前遍历当前序列，统计当前数后面有多少个数可以与之交换，如果交换的数个数大于等于当前数到最后一个数的距离（cnt\[a\[i\]\]>=n-i-ans），答案+1。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e6+5;
    int n,m,a[N],u,v,cnt[N];
    vector<int> g[N];
    
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) {
            cin>>u>>v;
            g[v].push_back(u);
        }
        for(auto it:g[a[n]])
            cnt[it]++;
        int ans = 0;
        for(int i=n-1;i>=1;i--) {
            if( cnt[a[i]] >= n-i-ans ) ans++;
            else {
                for(auto it:g[a[i]])
                    cnt[it]++;
            }
        }
        cout<<ans<<endl;
    	return 0;
    }