2018中国大学生程序设计竞赛 - 网络选拔赛 解题报告(部分)

题目链接http://acm.hdu.edu.cn/listproblem.php?vol=55(6438-6447)

1001 Buy and Resell

  • 用一个小顶堆维护当前还未卖出的东西,每次遇到一个东西弹出价格最小的去买卖,但这样不一定最优,所以我们每次把当前这个东西的压入小顶堆两次,第一次表示还未卖出,第二次表示这一次交易可以再把这个东西卖出去,相当于一个反悔的操作,比如第一次是13,我们把收益2加到答案里,如果碰到5然后把3弹出来做交易就相当于5只做了一个中间的跳板,另外其实这个最小交易次数是没用的,因为我们只要不让无效交易发生,就已经是最小交易次数,时间复杂度O(nlogn)
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
struct Node{
    int val,used;
    bool operator<(const Node&rhs)const{
        if (val==rhs.val) return used<rhs.used;
        return val>rhs.val;
    }
};
int T,n,x,cnt,i;
ll ans;
priority_queue<Node>Q;
int main(){
    for (read(T);T--;){
        read(n);
        while (!Q.empty()) Q.pop();
        for (ans=cnt=0,i=1;i<=n;i++){
            read(x);
            if (Q.empty()||Q.top().val>=x){
                Q.push((Node){x,0});
            }
            else{
                Node cur=Q.top();Q.pop();
                ans+=x-cur.val;
                if (!cur.used) cnt+=2;
                Q.push((Node){x,0});
                Q.push((Node){x,1});
            }
        }
        printf("%lld %d\n",ans,cnt);
    }
    return 0;
}

1002 Congruence equation

  • 待补

1003 Dream

  • 很明显这个限制条件就是让我们去求原根,把原根求出来以后我们把所有的加法重新定义为0就可以满足所有限制条件了,无论怎么加等式两边都是0
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2000+10;
int T,p,g,i,j,add[N][N],mul[N][N];
vector<int>fac;
int fexp(int a,int n){
    int res=1;
    while (n){
        if (n&1) res=1LL*res*a%p;
        a=1LL*a*a%p;
        n>>=1;
    }
    return res;
}
int main(){
    for (read(T);T--;){
        read(p);
        if (p==2){
            printf("0 1\n");
            printf("1 0\n");
            printf("0 0\n");
            printf("0 1\n");
            continue;
        }
        fac.clear();
        for(i=0;i<=p-1;i++)for(j=0;j<=p-1;j++)add[i][j]=mul[i][j]=0;
        int m=sqrt(p-1+0.5),tmp=p-1;
        for (i=2;i<=m&&tmp>1;i++){
            if (tmp%i==0){
                fac.push_back(i);
                while (tmp%i==0) tmp/=i;
            }
            if (tmp>1) fac.push_back(tmp);
        }
        for (g=2;g<=p-1;g++){
            bool flag=0;
            for (i=0;i<(int)fac.size();i++){
                int x=fac[i];
                if (fexp(g,(p-1)/x)==1){
                    flag=1;
                    break;
                }
            }
            if (!flag) break;
        }
        // cout<<g<<endl;
        mul[0][g]=1;
        tmp=1;
        for (i=1;i<=p-1;i++){
            int pre=tmp;
            tmp=1LL*tmp*g%p;
            mul[pre][g]=tmp;
        }
        //write
        for (i=0;i<=p-1;i++){
            for (j=0;j<=p-1;j++){
                printf("%d%c",add[i][j],j==p-1?'\n':' ');
            }
        }
        for (i=0;i<=p-1;i++){
            for (j=0;j<=p-1;j++){
                printf("%d%c",mul[i][j],j==p-1?'\n':' ');
            }
        }
    }
    return 0;
}

1004 Find Integer

  • 费马大定理可知n>2时无解,且易知n==0时无解,n==1时解很好构造,n==2时,a^2=(c-b)(c+b),我们让a^2=x\times y,如果a是偶数则x==2,y==a^2/2,如果a是奇数则x==1,y==a^2,这样即可。
#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
int T,n,a,b,c;
int main(){
    for (read(T);T--;){
        read(n),read(a);
        if (n>2||n==0) puts("-1 -1");
        else if (n==1) printf("%d %d\n",a,2*a);
        else{
            if (a&1){
                if (a==1) puts("-1 -1");
                else{
                    printf("%d %d\n",(a*a-1)/2,(a*a+1)/2);
                }
            }
            else{
                if (a==2) puts("-1 -1");
                else printf("%d %d\n",(a/2)*(a/2)-1,(a/2)*(a/2)+1);
            }
        }
    }
    return 0;
}

1005 GuGu Convolution

  • 居然把二项式定理忘了。。。详细见这里https://www.zybuluo.com/yang12138/note/1262396,找递推式的归纳方法要学会运用,同时要注意这里B是不用取模的。。。坑了好久。读题还是要仔细。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
int T,a,b,i,P;
ll n;
const int G=2;
struct matrix{
    #define MS(x,y) memset(x,y,sizeof(x))
    #define MC(x,y) memcpy(x,y,sizeof(x))
    int v[G][G];
    void O(){MS(v,0);}
    void E(){MS(v,0);for(int i = 0; i < G; ++i)v[i][i] = 1; }
    void print(){
        for (int i=0;i<G;i++){
            for (int j=0;j<G;j++){
                printf("%d ",v[i][j]);
            }
            puts("");
        }
    }
    matrix operator*(const matrix &b)const{
        matrix c;c.O();
        for (int k=0;k<G;k++){
            for (int i=0;i<G;i++)if(v[i][k]){
                for (int j=0;j<G;j++){
                    c.v[i][j]=(c.v[i][j]+(ll)v[i][k]*b.v[k][j])%P;
                }
            }
        }
        return c;
    }
    matrix operator+(const matrix &b)const{
        matrix c;c.O();
        for (int i=0;i<G;i++){
            for (int j=0;j<G;j++){
                c.v[i][j]=(v[i][j]+b.v[i][j])%P;
            }
        }
        return c;
    }
    matrix operator^(ll p)const{
        matrix y; y.E();
        matrix x; memcpy(x.v,v,sizeof(v));
        while (p){
            if (p&1) y=y*x;
            x=x*x;
            p>>=1;
        }
        return y;
    }
};
int main(){
    for (read(T);T--;){
        read(a),read(b),read(n),read(P);
        matrix mat;
        mat.v[0][0]=mat.v[1][1]=a%P,mat.v[0][1]=b%P;
        mat.v[1][0]=1%P;
        mat=mat^(n-1);
        int A=(1LL*mat.v[1][0]*a%P+mat.v[1][1])%P,B=1;
        int m=sqrt(b+0.5);
        for (i=2;i<=m;i++){
            if (b%i==0){
                int cnt=0;
                while (b%i==0){
                    cnt++;
                    b/=i;
                    if (!(cnt&1)) A=1LL*A*i%P;
                }
                if (cnt&1) B=B*i;
            }
        }
        if (b>1) B=B*b;
        printf("%d %d %d\n",1,A,B);
    }
    return 0;
}

1006 Neko and Inu

  • 过的人太少不补了。

1007 Neko's loop

  • 读完题大概就知道要怎么做了,无非分三种情况,一种是环上走了一圈如果收益大于0,则我们让它一直走下去,然后设环长是len,则会有m\bmod len的长度留下来,我们要做的就是在环上找一段长度不超过这个的最大子段和,将环倍长然后单调队列优化DP即可;第二种是如果收益小于0,则我们肯定不会走完这一圈,所以又是转化为第一种后半部分的问题;第三种就是第一种情况你可能直接走剩余部分不一定会最优,你需要留出一圈来跑DP,然后其余就一圈一圈的走,分清楚情况就好做了。
#include <bits/stdc++.h>
#define PB emplace_back
#define MP make_pair
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2e4+10;
int T,n,m,k,i,j,cnt,len,cas=1,q[N],a[N];
ll s,res,ans,sum[N];
bool vis[N];
int main(){
    for (read(T);T--;){
        read(n),read(s),read(m),read(k);
        for (i=1;i<=n;i++) read(a[i]),vis[i-1]=0;
        for (ans=0,i=1;i<=n;i++)if(!vis[i-1]){
            res=cnt=len=0;
            sum[++len]=a[i];
            res+=a[i];
            vis[i-1]=1;
            int pre=i-1;
            for (;;){
                int nxt=pre+k>=n?pre+k-n:pre+k;
                if (vis[nxt]) break;
                vis[nxt]=1;
                sum[++len]=a[nxt+1];
                res+=a[nxt+1];
                pre=nxt;
            }
            cnt=len;
            int limit;
            if (res>=0LL) res=res*(m/len),limit=m%len;
            else res=0LL,limit=min(m,len);
            for (j=1;j<=len;j++) sum[++cnt]=sum[j];
            for (j=1;j<=cnt;j++) sum[j]+=sum[j-1];
            int l=1,r=1;
            ll t=0;
            for (q[1]=0,j=1;j<=cnt;j++){
                while (l<=r && q[l]<j-limit) l++;
                t=max(t,sum[j]-sum[q[l]]);
                while (l<=r && sum[q[r]]>=sum[j]) r--;
                q[++r]=j;
            }
            ans=max(ans,res+t);

            if (m>=len){
                int l=1,r=1,limit=len;
                ll t=0,tmp=sum[len]*((m-len)/len);
                for (q[1]=0,j=1;j<=cnt;j++){
                    while (l<=r && q[l]<j-limit) l++;
                    t=max(t,tmp+sum[j]-sum[q[l]]);
                    while (l<=r && sum[q[r]]>=sum[j]) r--;
                    q[++r]=j;
                }
                ans=max(ans,t);
            }
        }
        printf("Case #%d: %lld\n",cas++,max(0LL,s-ans));
    }
    return 0;
}

1008 Search for Answer

  • 过的人太少不补了。

1009 Tree and Permutation

  • 考虑i->j贡献的系数,很明显在排列中它们是绑在一起的,所以就相当于一个n-1的排列,所以贡献的系数就是(n-1)!,最后的答案就是(n-1)!\sum_{i=1}^{n}\sum_{j=1}^{n}dis[i][j]
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
const int P=1e9+7;
int n,i,u,v,l,ans,res,sz[N],jc[N];
vector<pair<int,int> >G[N];
inline void up(int&a,int b){a+=b;if(a>=P)a-=P;}
void dfs(int u,int f,int dep){
    sz[u]=1;
    up(ans,dep);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i].first,l=G[u][i].second;
        if (v==f) continue;
        dfs(v,u,(dep+l)%P);
        sz[u]+=sz[v];
    }
    //if (sz[u]==1) up(ans,dep);
}
void dfs(int u,int f){
    up(res,ans);
    //printf("%d=%d\n",u,ans);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i].first,l=G[u][i].second;
        if (v==f) continue;
        int pre=ans;
        ans-=1LL*sz[v]*l%P;
        ans%=P;
        if (ans<0) ans+=P;
        up(ans,1LL*(n-sz[v])*l%P);
        dfs(v,u);
        ans=pre;
    }
}
int main(){
    for (jc[0]=i=1;i<=100000;i++) jc[i]=1LL*jc[i-1]*i%P;
    while (~scanf("%d",&n)){
        for (i=1;i<=n;i++) G[i].clear();
        for (i=1;i<n;i++){
            read(u),read(v),read(l);
            G[u].PB(MP(v,l));
            G[v].PB(MP(u,l));
        }
        ans=0;
        dfs(1,0,0);
        res=0;
        dfs(1,0);
        res=1LL*res*jc[n-1]%P;
        printf("%d\n",res);
    }
    return 0;
}

1010 YJJ's Salesman

  • 我们设dp[i][j]表示在(i,j)这个点可以获得的最大价值,根据题意列出转移方程,即只能有i-1转移过来,即dp[i][j]=max(dp[i-1][k])(k< j),我们对x排序然后离散化y,对其建立一个线段树叶子节点保存dp[j]的值,然后向01背包那样为了不被这一层的值影响到,将y从大到小排序这样更新的时候就不会影响到自己这一层的dp值了,时间复杂度O(nlogn)
#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
struct Node{
    int x,y,val;
    bool operator<(const Node&rhs)const{
        return x^rhs.x?x<rhs.x:y>rhs.y;
    }
}q[N];
int T,n,i,sz,mx[N<<2];
vector<int>vec;
void compress(){
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    sz=(int)vec.size();
}
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
void pushup(int root){mx[root]=max(mx[root<<1],mx[root<<1|1]);}
void build(int root,int l,int r){
    mx[root]=0;
    if (l==r) return;
    int mid=l+((r-l)>>1);
    build(lson);
    build(rson);
}
int query(int root,int l,int r,int L,int R){
    if (L<=l&&r<=R) return mx[root];
    int mid=l+((r-l)>>1);
    int res=0;
    if (L<=mid) res=max(res,query(lson,L,R));
    if (mid<R) res=max(res,query(rson,L,R));
    return res;
}
void update(int root,int l,int r,int pos,int v){
    if (l==r){
        mx[root]=max(mx[root],v);
        return;
    }
    int mid=l+((r-l)>>1);
    if (pos<=mid) update(lson,pos,v);
    else update(rson,pos,v);
    pushup(root);
}
int main(){
    for (read(T);T--;){
        read(n);
        vec.clear();
        for (i=1;i<=n;i++){
            read(q[i].x),read(q[i].y),read(q[i].val);
            vec.PB(q[i].y);
        }
        sort(q+1,q+1+n);
        compress();
        build(1,1,sz);
        for (i=1;i<=n;i++){
            int pos=lower_bound(vec.begin(),vec.end(),q[i].y)-vec.begin();
            if (pos==0){
                update(1,1,sz,pos+1,q[i].val);
                continue;
            }
            int val=query(1,1,sz,1,pos);
            update(1,1,sz,pos+1,val+q[i].val);
        }
        printf("%d\n",mx[1]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注