赛后总结（1）

· · 个人记录

这次考得不错，考了180。总算是稳住了阵脚（手动滑稽）。

第一题

题意分析

判断是否有数超过

\frac{n}{4}

如果有，就把这些数按从小到大输出,否则，输出“No number.”（注意！有个点，我就是因为没加点才 90的）。

思路

一个双重map搞定。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> a;
int b[10001];
map<int,bool> c;
int n,tot=0;
signed main(){
    freopen("find.in","r",stdin);
    freopen("find.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        int x;
        scanf("%lld",&x);
        a[x]++;
        if(a[x]*4>n&&!c[x]){//避免重复输出
            b[++tot]=x;
            c[x]=true;
        }
    }
    sort(b+1,b+tot+1);
    if(tot>0){
        for(int i=1;i<=tot;++i)
            printf("%lld\n",b[i]);
    }
    else
        printf("No number.\n");
    return 0;
}

第二题

题意分析

判断从l到r有多少个因数，再把它们加起来。

思路

错误方法：暴力，70分。我很好奇50分是怎么拿的

正解：类似于前缀和，sum(i)表示前i个数的因数之和。l到r就是sum(r)-sum(l-1)，代码简单真·O(n)算法。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans,l,r;
int e(int x){
    int sum=0;
    for(int i=1;i<=x;++i)
        sum+=x/i;//巧算前x的因数个数和
    return sum; 
}
signed main(){
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",e(r)-e(l-1));
    return 0;
}

第三题

题意分析

没什么可分析的

思路

错误方法：写了个贪心，直接取除了最后一个的一半，因为最后一分钟如果跑了疲劳值就不会为0，如果总数%2==0那就再取一个。竟然还能拿十分，不可思议。

正解：dp，有两种情况，跑或休息，如果跑，动态转移方程为：f[i][j]=max(f[i][j],f[i-1][j-1]+d[i])；如果休息，还有两种情况，第一种是休息i-j分钟，动态转移方程为：f[i][0]=max(f[i][0],f[i-1][j])第二种是疲劳值为0就在休息，类似于还没跑就休息，动态转移方程为：f[i][0]=max(f[i][0],f[i-1][0])。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[100001],f[10001][501];//f[i][j]表示前i分钟，疲劳值为j时跑的最大值
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    f[0][0]=0;
    for(int i=1;i<=n;++i){
        f[i][0]=max(f[i][0],f[i-1][0]);
        for(int j=1;j<=min(m,i);++j){
            f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);
            f[i][0]=max(f[i][0],f[i-j][j]);
        }
    }
    printf("%d\n",f[n][0]);
    return 0;
}

第四题

题意分析

有p条边，每条边强化都有一个花费L_i。从1-n有k条边可以免费，剩下的边只要付剩下的最大值就行了。这福利真好，我也要

思路

说实话，我这辈子都没想到用二分，还是太年轻了

咳，二分一个v，如果花费大于v，就利用免单特权。

代码

终于到了最后一题代码了，快吐了

#include<bits/stdc++.h>
using namespace std;
struct f{
    int w,to,next;
}e[20005];
int head[1005],dis[1005];
bool vis[1005];
int n,p,k,l,mid,r,cnt,val,minn,maxw,beg,a,b,c;
inline void add(int u,int v,int w){
    e[++cnt].w=w;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
inline int check(int ans){
    for(int i=2;i<=n;++i)
        dis[i]=0x3f3f3f3f;
    for(int i=1;i<=n;++i)
        vis[i]=0;
    for(int i=1;i<=n;++i){
        minn=0x3f3f3f3f;
        beg=0;
        for(int j=1;j<=n;++j){
            if(!vis[j]&&dis[j]<minn){
                minn=dis[j];
                beg=j;
            }
        }
        if(beg==0)
            break;
        vis[beg]=1;
        for(int j=head[beg];j;j=e[j].next){
            int y=e[j].to;
            int p=(e[j].w>ans?1:0);
            if(!vis[y]&&p+dis[beg]<dis[y])
                dis[y]=p+dis[beg];
        }
    }
    return dis[n];
}
int main(){
    scanf("%d%d%d",&n,&p,&k);
    for(int i=1;i<=p;++i){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
        maxw=max(maxw,c);
    }
    if(check(maxw)==0x3f3f3f3f)
        printf("-1");
    else{
        l=0;r=maxw;
        while(l<r){
            mid=(l+r)/2;
            if(k<check(mid))
                l=mid+1;
            else
                r=mid;
        }
        printf("%d\n",l);
    }
    return 0;
}

一百七十多行字，确定不点个赞吗？

感谢@吴思诚 找到的错误