首页 > 代码库 > 2017Summmer_上海金马五校 F题，G题，I题，K题

2017Summmer_上海金马五校 F题，G题，I题，K题

2024-10-25 05:55:02   210人阅读

以下题目均自己搜

F题  A序列

一开始真的没懂题目什么意思，还以为是要连续的子串，结果发现时序列，简直智障，知道题意之后，好久没搞LIS，有点忘了，复习一波以后，直接双向LIS，处理处两个数组L和R，然后对整个数组扫一遍对于每一个下标取m=min(L[i],R[i]);用ans取2*m-1中的最大值。LIS用nlogn的算法实现，二分用的是lower_bound()，直接看代码。

//Author: xiaowuga
#include <bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N=500003; 
using namespace std;
typedef long long LL;
int dp[N];
int L[N],R[N];
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int n;
    int a[N];
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        memset(dp,inf,sizeof(dp));
        for(int i=0;i<n;i++){
            int pos=lower_bound(dp,dp+n,a[i])-dp;
            dp[pos]=a[i]; 
            L[i]=pos+1;
        }
       
        memset(dp,inf,sizeof(dp));
        for(int i=n-1;i>=0;i--){
            int pos=lower_bound(dp,dp+n,a[i])-dp;
            dp[pos]=a[i];
            R[i]=pos+1;
        }
         for(int i=0;i<n;i++) cout<<L[i]<<" "; cout<<endl;
          for(int i=0;i<n;i++) cout<<R[i]<<" "; cout<<endl;
        int ans=minn;
        int tmp;
        for(int i=0;i<n;i++){
            int tmp=min(L[i],R[i]);
            ans=max(tmp*2-1,ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

G题 战斗

暴力阶乘题，因为n<10，所以暴力枚举全排列所有的出战顺序，然后模拟和电脑去打就好了，复杂度n*n！。不要真的老实的的每一次攻击的去模拟，万一两个两个怪兽都是1000的血1的攻击力，一次枚举，十个怪兽就是10000的计算计算量，而你的枚举量可能高达10！三百多万啊，绝逼超时GG，所以直接除找到每组队长的怪兽需要各自攻击对方几次才会死，然后取最小值，将hp减去攻击次数*攻击力，得到怪兽战后的状态，对于hp<=0的我们就换人。还有不要确切的计算具体要攻击多少次，因为有的时候比如你是9的hp，5的五的攻击力，9/5=1，实际上要攻击两次才会死攻击次数是hp/at+1。然后如果双方的hp变成10，10/5=2，刚好死亡攻击次数恰好是hp/at，这个时候如果用%取判断了话，是会超时的，因为%与运算是比较慢的。所以我们用一个while循环，模拟最后一次攻击，将会比算出这个具体的攻击次数速度要快。这就是我为什么一开始超时的原因，还有一个优化就是要枚举的时候都要复制一遍双方的怪兽信息，因为只有当前的怪兽有用，所以我们用一个值来存就好了，如果你用结构体，每次就有一个攻击实际上不用复制但是复制了，实际上浪费了时间，面对10！的枚举量，也会慢很多，然后就是边打边复制，这样有的时候电脑其实一只怪兽就团灭你了，但是你却多复制了其他怪兽同样浪费时间。

最后还有一个逆天优化：就是我们每次记住上一次枚举出场的顺序，如果电脑两只怪兽就把你团灭了，那么如果你下一次枚举前两只怪兽出场顺序没有发生改变，那么电脑还是可以用两只怪兽把你团灭，无论你后面的怪兽如何出出站，压倒性的实力。这样的枚举是无用的，如果对他的战斗进行模拟，又会有大量的复制会是无用功，而且对于字典序全排列，大多数的枚举的前几位都和上一次枚举基本是一样的。这就给我们启发，使我们可以快速的跳过一下无用的枚举，将n*n！的复杂度，优化成n！，加快了近十倍的速度。大概只需要100ms就可以ac，当然后还有2^n复杂度的做法，那个就更快了，需要用到状态压缩dp，本人目前不会。

//Author: xiaowuga
#include <bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N=11; 
using namespace std;
typedef long long L;
struct M{
    int at,hp,pos;
    bool operator <(const M &m) const{
        return at<m.at;
    }
}me[N],co[N];
M cm[N],mm[N];
int main() {
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d%d",&co[i].hp,&co[i].at);
        for(int i=0;i<n;i++) {scanf("%d%d",&me[i].hp,&me[i].at);}
        int flag=0,flag2=0;
        int c1=0,c2=0,m;
        sort(me,me+n);
        do{
            if(flag2){
                if(c1==0) break;
                else{
                    int ifsame=1;
                    for(int i=0;i<=c1;i++){
                        if(me[i].at!=mm[i].at) {ifsame=0;break;}
                    }
                    if(ifsame) continue;
                 }
            }
            flag2=1;
            c1=0;c2=0;
            cm[0]=co[0]; mm[0]=me[0];
            while(c1<n&&c2<n){
                m=min(cm[c1].hp/mm[c2].at,mm[c2].hp/cm[c1].at);
                cm[c1].hp-=m*mm[c2].at;
                mm[c2].hp-=m*cm[c1].at;
                while(cm[c1].hp>0&&mm[c2].hp>0){
                    cm[c1].hp-=mm[c2].at;
                    mm[c2].hp-=cm[c1].at;
                }
                if(cm[c1].hp<=0) {c1++;cm[c1]=co[c1];}
                if(mm[c2].hp<=0) {c2++;mm[c2]=me[c2];}
            }
            if(c1==n&&c2<n) {flag=1;break;}
        }while(next_permutation(me,me+n));
        if(flag) printf("YES\n");
        else printf("NO\n");    
    }
    return 0;
}

 

I题   丢史蒂芬妮

博弈xjb搜题，博弈论知识不好，别人告诉我怎么搜的。xjb搜了一波，就过了，不是特别理解。直接代码吧！

//Author: xiaowuga
#include<cstdio>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N=505; 
using namespace std;
typedef long long L;
int vis1[N]={0};
int num=0;
int primnum_list[N];
void make_primnum(){
    for(int i=2;i<N/2;i++)
        for(int j=2*i;j<N;j+=i){
            vis1[j]=1;
        }
    for(int i=2;i<N;i++){
        if(vis1[i]==0) primnum_list[num++]=i;
    } 
}
int mat[N][N]={0},vis[N][N]={0};
int dfs(int x,int y){
    if(vis[x][y]) return mat[x][y];
    vis[x][y]=1;
    for(int i=0;i<num;i++){
        int t=primnum_list[i];
        if(x-t>0) mat[x][y] |=!(dfs(x-t,y));
        if(y>t>0) mat[x][y] |=!(dfs(x,y-t));
        if(x-t>0&&y-t>0) mat[x][y] |=!(dfs(x-t,y-t));
    }
    return mat[x][y];
}
int main() {
    make_primnum();
    for(int i=1;i<=500;i++)
       for(int j=1;j<=500;j++){
            mat[i][j]=dfs(i,j);
       }
    int T;
    scanf("%d",&T);
   while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(mat[n][m]) printf("Sora\n");
        else printf("Shiro\n");
   } 
    return 0;
}

 

K题   购买装备

第一眼尼玛不是一个背包dp吗？还是0-1背包，结果native了，10000的物品，一亿的预算，背包的复杂度更本跑不出来，所以我们采用贪心的思路。

我们首先要把问题分开去思考，这样有助于我们思考，而不会因为问题整体比较比较复杂，从而在思考上停滞不前，应该要把问题什么事主要问题什么是次要问题，题目中次要问题，实在主要问题的限制之下，也就是在购买尽量多的物品的情况下，物品中属性最小的值尽量大。首先是购买尽量多的物品，由于每个物品只能买一次，所以买便宜的物品，剩下的钱更多，也就可以买更多的物品，所以贪心对价格排序得到最大可以购买的数量m，但是这不一定是最小属性最大的。所以我们接着看后半部分的问题，问题就变成了在n个物品里面选m个其中属性最小的的物品的值要尽量大，标准的最小值最大化的套路。对属性排序，二分枚举属性，在大于等于当前枚举的最小属性中，对价格排序取 前m个，判断是否小于等于预算，这个是学长的做法，我也想过。但是每次复制一遍再排序，所以觉得没可行，所以没敢试。谁知学长用了特殊姿势。用了nth_element()这个库函数，使用m次，直接排序复杂度nlogn，减去复制的过程防止复杂度上升到n^2logn，从而使复杂度变为nlognlogn，这个复杂度可以满足题目的数据量。但是我想到是另一个种方法，前面和学长一样得到m的最大购买数量，然后对属性排序（从大到小），取前m个元素判断是否满足预算（枚举下标为m-1的元素为最小属性），不满足则枚举下标为m的元素为最小属性，从前m+1个元素里取m个最便宜的看一下，是否满足预算，不满足再次往后枚举，直到满足要求，我也需要复制一遍再排序，然而我想到用优先队列优化，建立一个大小为m的优先队列，计算一个堆的价格总和，然后每次枚举我们把堆顶元素pop，将枚举的元素插入，计算总价格的改变值，判断是否满足要求，直到满足要求位置。由于删除和插入的操作复杂度都是logn，所以总体的复杂度是nlogn，以下是我的代码

//Author: xiaowuga
#include <bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N= 1e5+10;
using namespace std;
typedef long long L;
priority_queue<long long, vector<long long>,less<long long> >q;
struct equip{
    long long a,b;
}oj[N];
bool cmp1(equip x,equip y){
    return x.b<y.b;
}
bool cmp2(equip x,equip y){
    return x.a>y.a;
}
int main() {
    long long T,n,m;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&m);
        for(int i=0;i<n;i++) scanf("%lld%lld",&oj[i].a,&oj[i].b);
        sort(oj,oj+n,cmp1);
        long long sum=0,k=0;
        for(int i=0;i<n;i++){
            if(sum+oj[i].b<=m){sum+=oj[i].b;k++;}
            else break;
        }
        sort(oj,oj+n,cmp2);
        sum=0;
        while(!q.empty()) q.pop();
        for(int i=0;i<k;i++){
            q.push(oj[i].b);
            sum+=oj[i].b;
        }
        if(sum<=m) {printf("%lld %lld\n",k,oj[k-1].a);continue;}
        for(int i=k;i<n;i++){
            sum=sum-q.top()+oj[i].b;
            if(sum<=m){ printf("%lld %lld\n",k,oj[i].a); break; }
            q.pop();q.push(oj[i].b);
        }
    } 
    return 0;
}

继续补题，这个随笔将会在最近持续更新，尽量把金马五校的题补完吧！！！

2017Summmer_上海金马五校 F题，G题，I题，K题


联系
我们