[noip模拟赛2017.7.11]

时间:2022-12-20 12:36:56

模拟试题(三)

【试题概览】

题目名称 中位数 敲砖块 单词 邮递员送信
提交文件 median.* brike.* words.* post.*
输入文件 median.in brike.in words.in post.in
输出文件 median.out brike.out words.out post.out
时间限制 1s 1s 1s 1s
空间限制 128MB 128MB 128MB 128MB

中位数

【题目描述】

有一个长度为 N 的数列{A1,A2,…,AN},这 N 个数字恰好是 1..N 的一个排列。你需要统计有多少个 子序列{Ai,Ai+1,…,Aj}满足:i<=j 且 j-i+1 为奇数,序列的中位数为 B。例如{5,1,3}的中位数为 3。

【输入格式】

第一行包含两个正整数 N 和 B。
第二行包含 N 个整数,第 i 个整数为 Ai.

【输出格式】

仅包含一个整数,为满足条件的子序列的个数。

【数据规模】

对于 30%的数据,满足 N<=100;
对于 60%的数据,满足 N<=1000;
对于 100%的数据,满足 N<=100000,1<=B<=N。

【输入样例】

7 4

5 7 2 4 3 1 6

【输出样例】

4

题解

假设比中位数大的数记为1,小的记为-1,那么只需要找到一段和为0,且包含该中位数的区间即可,可以考虑前缀和,那么前缀和相同的i,j区间和一定为0,找到对于点j,有多少个i可以与之匹配即可

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define LL long long
using namespace std;
int n,B,A[100100];
int ans;
int b[100100],s[100100],p;
int trs(int x){return x+100001;}
int rtrs(int x){return x-100001;}
int dt[100100];
int mp[200200];
int main(){
    freopen("median.in","r",stdin);
    freopen("median.out","w",stdout);
    scanf("%d%d",&n,&B);
    for(int i=1;i<=n;i++)
        scanf("%d",&A[i]);
    for(int i=1;i<=n;i++){
        b[i]=b[i-1];s[i]=s[i-1];
        if(A[i]>B)b[i]++;
        if(A[i]<B)s[i]++;
        if(A[i]==B)p=i;
        dt[i]=b[i]-s[i];
    }
    for(int i=0;i<p;i++)mp[trs(dt[i])]++;
    for(int i=p;i<=n;i++)ans+=mp[trs(dt[i])];
    printf("%d",ans);
} 
/*暴力
for(int l=1;l<=n;l++)
    for(int r=l;r<=n;r++){
        if((r-l+1)&1){
        int tmp[100100];
            for(int i=l;i<=r;i++){          
                tmp[i]=A[i];
            }
        sort(tmp+l,tmp+r+1);
        if(tmp[(l+r)/2]==B)
            ans++;
        }
    }
    printf("%d",ans);
*/
/*
7 4
5 7 2 4 3 1 6
*/

敲砖块

【题目描述】

在一个凹槽中放置了 N 层砖块,最上面的一层有 N 块砖,从上到下每层依次减少一块砖。每块砖 都有一个分值,敲掉这块砖就能得到相应的分值,如图所示
14 | 15 | 4 | 3 | 23
---|---|---|---|---
33 | 33 | 76 | 2 |
2 | 13 | 12 |
22 | 23 |
31 |
如果你想敲掉第 i 层的第 j 块砖的话,若 i=1,你可以直接敲掉它;若 i>1,则你必须先敲掉第 i-1 层的第 j 和第 j+1 块砖。
你现在可以敲掉最多 M 块砖,求得分最多能有多少。

【输入格式】

第一行有两个正整数 N 和 M;
接下来的 N 行,描述这 N 层砖块上的分值 A[i,j],满足 0<=A[i,j]<=100。

【输出格式】

仅一行,包含一个整数,为最大的得分。

【数据规模】

对于 20%的数据,满足 1<=N<=10,1<=M<=30;
对于 100%的数据,满足 1<=N<=50,1<=M<=500。

【输入样例】

4 5

2 2 3 4

8 2 7

2 3

49

【输出样例】

19

题解(xjb算法)

玄学混分呐,完全不会统计这题的复杂度,直接搜索外加一个记忆化,各种剪枝优化,混了个AC,有些神犇就直接DP搞定,至今还不只怎么弄。。。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define LL long long
using namespace std;
int n,m,A[55][55];
int sum[55][55];
int dp[55][505][55];
bool f[55][505][55];
int dfs(int cnt,int lft,int from){
    if(f[cnt][lft][from])return dp[cnt][lft][from];
    f[cnt][lft][from]=true;
    if(lft<0)return dp[cnt][lft][from]=-1;
    if(2*lft<from*(from+1))return dp[cnt][lft][from]=-1;
    if(cnt>n)return dp[cnt][lft][from]=0;
    if(lft==0)return dp[cnt][lft][from]=0;
    int rtn=sum[cnt][from],now;
    for(int i=from;i<=n-cnt+1;i++){
        now=sum[cnt][i];
        int k=dfs(cnt+1,lft-i,max(i-1,0));
        if(k==-1)break;
        rtn=max(now+k,rtn);
    }
    return dp[cnt][lft][from]=rtn;
}
int main(){
    freopen("brike.in","r",stdin);
    freopen("brike.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n-i+1;j++)
            scanf("%d",&A[i][j]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n-i+1;j++)
            sum[i][j]=sum[i][j-1]+A[j][i];
    }
    printf("%d\n",dfs(1,m,0));
}

单词

【题目描述】

有 N 个单词和字符串 T,按字典顺序输出以字符串 T 为前缀的所有单词。

【输入格式】

第一行包含一个正整数 N;
接下来 N 行,每行一个单词,长度不超过 50;
最后一行包含字符串 T。

【输出格式】

按字典顺序升序输出答案。

【数据规模】

对于 60%的数据,满足 1<=N<=1000;
对于 100%的数据,满足 1<=N<=10000 且所有字符均为小写字母。

【输入样例】

6

na

no

ki

ki

ka

ku

k

【输出样例】

ka

ki

ki

ku

题解

这道题告诉了我们,不要用string,会出问题的。
那么就直接套一个STL的sort,自己写个比较函数cmp就搞定,注意不要对字符串直接排序,只对其下标排序即可,不然TLE妥妥的。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define LL long long
using namespace std;

int n;
char w[10010][60];int l[10010];
int r[10010];
bool cmp(int x,int y){
    int len=min(l[x],l[y]);
    for(int i=0;i<len;i++){
        if(w[x][i]==w[y][i])continue;
        return w[x][i]<w[y][i];
    }
    return l[x]<l[y];
}
int main(){
    freopen("words.in","r",stdin);
    freopen("words.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",w[i]),l[i]=strlen(w[i]),r[i]=i;
    scanf("%s",w[0]);
    int len=strlen(w[0]);
    for(int i=0;i<len;i++)
        w[n+1][i]=w[0][i];
    w[n+1][len]='z'+1;w[n+1][len+1]='\0';
    r[n+1]=n+1;r[0]=0;
    l[0]=len;l[n+1]=len+1;
    sort(r,r+n+2,cmp);
    bool flag=false;
    for(int i=0;i<=n+1;i++){
        if(r[i]==n+1)flag=false;
        if(flag)printf("%s\n",w[r[i]]);
        if(r[i]==0)flag=true;
    }
    return 0;
}

邮递员送信

【题目描述】

有一个邮递员要送东西,邮局在结点 1。他总共要送 N-1 样东西,其目的地分别是 2-N。由于这个 城市的交通比较繁忙,因此所有的道路都是单行的,共有 M 条道路,通过每条道路需要一定的时间。 这个邮递员每次只能带一样东西。求送完这 N-1 样东西并且最终回到邮局最少需要多少时间。

【输入格式】

第一行包含一个正整数 N 和 M;
接下来有 M 行,每行三个正整数 U、V、W,表示该条道路为从 U 到 V 的,且通过这条道路需要 W 的时间。满足 1<=U,V<=N,1<=W<=100000,输入保证任意两点都能互相到达。

【输出格式】

包含一个整数,为最少需要的时间

【数据规模】

30%的数据,1<=N<=200;
100%的数据,1<=N<=1000,1<=M<=10000.

【输入样例】

注意:如果有这样的情况:(1109) (1102) (1101)以最小的 w=1 进行存储

5 10

2 3 5

1 5 5

3 5 6

1 2 8

1 3 8

5 3 4

4 1 8

4 5 3

3 5 6

5 4 2

【输出样例】

83

题解

SPFA板子记好,直接建好图和反图,跑SPFA即可。

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define LL long long
using namespace std;
int n,m;LL ans;
LL edge[1010][1010];
LL d[10100];
int b[100100],nt[100100],p[1010],cnt=1;
void add(int x,int y,LL z){
    b[cnt]=y;
    d[cnt]=z;
    nt[cnt]=p[x];
    p[x]=cnt++;
}
LL dis[1010];
bool vis[1010];
queue<int>q;
void spfa(){
    for(int i=1;i<=n;i++)dis[i]=1e17;
    dis[1]=0;
    q.push(1);vis[1]=true;
    while(!q.empty()){
        int k=q.front();q.pop();vis[k]=false;
        for(int i=p[k];i;i=nt[i]){
            int kk=b[i];
            if(dis[kk]>dis[k]+d[i]){
                dis[kk]=dis[k]+d[i];
                if(!vis[kk]){
                    vis[kk]=true;
                    q.push(kk);
                }
            }
        }
    }
}
int main(){
    freopen("post.in","r",stdin);
    freopen("post.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            edge[i][j]=1e17;
    for(int i=1;i<=m;i++){
        int x,y;LL z;
        scanf("%d%d%lld",&x,&y,&z);
        edge[x][y]=min(edge[x][y],z);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j&&edge[i][j]<=100000)
                add(i,j,edge[i][j]);
    spfa();
    for(int i=2;i<=n;i++)
        ans+=dis[i];
    memset(p,0,sizeof(p));
    cnt=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j&&edge[i][j]<=100000)
                add(j,i,edge[i][j]);
    spfa();
    for(int i=2;i<=n;i++)
        ans+=dis[i];
    printf("%lld",ans);
    return 0;
}

/*
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

*/