CCF2018-9题解后续代码篇

代码随便写了下，只写了3题，模拟题太麻烦了懒得写，最后一题不会写，只混了点分。解释在上一篇博客。如果看不懂代码，可以留言或者+Q3035536707.这3题就有300分了，另外两题可以混点分，我模拟题混了50分（乱写的。。。），最后一题混了20分（暴力写的）。（如果有需要我写一下模拟题混分（不要想全写出来，太麻烦了）的和暴力混分的留言，如果没有我就不添加了）。

第一题

问题描述

试题编号：	201809-1
试题名称：	卖菜
时间限制：	1.0s
内存限制：	256.0MB
问题描述：	问题描述　　在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。　　第一天，每个商店都自己定了一个价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。　　注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。　　给定第一天各个商店的菜价，请计算第二天每个商店的菜价。输入格式　　输入的第一行包含一个整数n，表示商店的数量。　　第二行包含n个整数，依次表示每个商店第一天的菜价。输出格式　　输出一行，包含n个正整数，依次表示每个商店第二天的菜价。样例输入 8 4 1 3 1 6 5 17 9 样例输出 2 2 1 3 4 9 10 13 数据规模和约定　　对于所有评测用例，2 ≤ n ≤ 1000，第一天每个商店的菜价为不超过10000的正整数。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=1e6+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int a[10000];
int n;

int main() {
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        if(i==0){
            printf("%d ",(a[i]+a[i+1])/2);
        }else if(i==n-1){
            printf("%d\n",(a[i]+a[i-1])/2);
        }else {
            printf("%d ",(a[i]+a[i+1]+a[i-1])/3);
        }
    }
    return 0;
}

第二题

问题描述

试题编号：	201809-2
试题名称：	买菜
时间限制：	1.0s
内存限制：	256.0MB
问题描述：	问题描述　　小H和小W来到了一条街上，两人分开买菜，他们买菜的过程可以描述为，去店里买一些菜然后去旁边的一个广场把菜装上车，两人都要买n种菜，所以也都要装n次车。具体的，对于小H来说有n个不相交的时间段[a1,b1],[a2,b2]...[an,bn]在装车，对于小W来说有n个不相交的时间段[c1,d1],[c2,d2]...[cn,dn]在装车。其中，一个时间段[s, t]表示的是从时刻s到时刻t这段时间，时长为t-s。　　由于他们是好朋友，他们都在广场上装车的时候会聊天，他们想知道他们可以聊多长时间。输入格式　　输入的第一行包含一个正整数n，表示时间段的数量。　　接下来n行每行两个数ai，bi，描述小H的各个装车的时间段。　　接下来n行每行两个数ci，di，描述小W的各个装车的时间段。输出格式　　输出一行，一个正整数，表示两人可以聊多长时间。样例输入 4 1 3 5 6 9 13 14 15 2 4 5 7 10 11 13 14 样例输出 3 数据规模和约定　　对于所有的评测用例，1 ≤ n ≤ 2000, ai < bi < ai+1，ci < di < ci+1,对于所有的i(1 ≤ i ≤ n)有，1 ≤ ai, bi, ci, di ≤ 1000000。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=1e6+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int a[maxn];
int n;

int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        while(l<r){
            a[l++]++;
        }
    }
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        while(l<r){
            a[l++]++;
        }
    }
    int ans=0;
    for(int i=0;i<maxn;i++){
        if(a[i]==2)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

第三题

问题描述

试题编号：	201809-4
试题名称：	再卖菜
时间限制：	1.0s
内存限制：	256.0MB
问题描述：	问题描述　　在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。　　第一天，每个商店都自己定了一个正整数的价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。　　注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。　　给定第二天各个商店的菜价，可能存在不同的符合要求的第一天的菜价，请找到符合要求的第一天菜价中字典序最小的一种。　　字典序大小的定义：对于两个不同的价格序列(a1, a2, ..., an)和(b1, b2, b3, ..., bn)，若存在i (i>=1), 使得ai<bi，且对于所有j<i，aj=bj，则认为第一个序列的字典序小于第二个序列。输入格式　　输入的第一行包含一个整数n，表示商店的数量。　　第二行包含n个正整数，依次表示每个商店第二天的菜价。输出格式　　输出一行，包含n个正整数，依次表示每个商店第一天的菜价。样例输入 8 2 2 1 3 4 9 10 13 样例输出 2 2 2 1 6 5 16 10 数据规模和约定　　对于30%的评测用例，2<=n<=5，第二天每个商店的菜价为不超过10的正整数；　　对于60%的评测用例，2<=n<=20，第二天每个商店的菜价为不超过100的正整数；　　对于所有评测用例，2<=n<=300，第二天每个商店的菜价为不超过100的正整数。　　请注意，以上都是给的第二天菜价的范围，第一天菜价可能会超过此范围。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=300+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n;
int a[maxn];
int dp[305][305][305];  //标记状态
int b[maxn];
int dfs(int pos,int pre) {
    int val;
    if(pos==1) {
        val=2*a[0]-b[0];
        if(val>0&&dp[pos][pre][val]==0) {
            dp[pos][pre][val]=1;
            b[pos]=val;
            if(dfs(pos+1,val))return 1;
        }
        val++;
        if(val>0&&dp[pos][pre][val]==0) {
            dp[pos][pre][val]=1;
            b[pos]=val;
            if(dfs(pos+1,val))return 1;
        }
    } else if(pos==n-1) {
        val=3*a[n-2]-b[n-2]-b[n-3];
        if(val>0&&(val+b[n-2])/2==a[n-1]) {
            b[n-1]=val;
            return 1;
        }
        val++;
        if(val>0&&(val+b[n-2])/2==a[n-1]) {
            b[n-1]=val;
            return 1;
        }
        val++;
        if(val>0&&(val+b[n-2])/2==a[n-1]) {
            b[n-1]=val;
            return 1;
        }
    } else {
        val=3*a[pos-1]-b[pos-2]-b[pos-1];
        if(val>0&&dp[pos][pre][val]==0) {
            dp[pos][pre][val]=1;
            b[pos]=val;
            if(dfs(pos+1,val))return 1;
        }
        val++;
        if(val>0&&dp[pos][pre][val]==0) {
            dp[pos][pre][val]=1;
            b[pos]=val;
            if(dfs(pos+1,val))return 1;
        }
        val++;
        if(val>0&&dp[pos][pre][val]==0) {
            dp[pos][pre][val]=1;
            b[pos]=val;
            if(dfs(pos+1,val))return 1;
        }
    }
    return 0;
}

int main() {
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    for(int i=1; i<=300; i++) {
        b[0]=i;
        if(dfs(1,i)) {
            for(int i=0; i<n; i++) {
                if(i==n-1) {
                    printf("%d\n",b[i]);
                } else printf("%d ",b[i]);
            }
            break;
        }
    }
    return 0;
}