CCF-NOIP-2018 提高组(复赛) 模拟试题(一)

T1 帽子戏法

问题描述

小 Y 有一个n*n*n的“帽子立方体” ，即一个!层的立方体，每层的帽子都
可以排成!×!的矩阵。 “帽子立方体”中的每一个帽子都有一个颜色，颜色共 26
种，用 26 个大写字母来表示。
现在，小 Y 邀请小 F 来表演她的帽子戏法。小 F 会 2 种帽子戏法：

  1. 指定一个长方体形状的区域，将指定区域内的所有帽子全部变成指定的
    颜色。
  2. 指定一个长方体形状的区域，将指定区域内所有指定颜色帽子全部变成
    绿色（用大写字母G表示） 。
    小 Y 很喜欢绿色， 所以初始时立方体内的所有帽子都是绿色的。 不仅如此，
    小 Y 还会时不时地提出问题：他会指定一个长方体形状的区域，并询问在这个
    区域内有多少绿色的帽子。
    小 Y 的帽子琳琅满目，请你来帮他数一数吧！

输入格式

第一行 2 个正整数n,Q，分别描述立方体的大小、以及小 F 表演帽子戏法和
小 Y 提问的总次数。
接下来Q行，每行第一个数op(0 ≤ op ≤ 2)表示这次询问或帽子戏法的类型。
若op = 0，表示这是小 Y 的一个提问，接下来 6 个正整数描述询问指定的
区域。
若op = 1，接下来 6 个正整数表示帽子戏法指定的区域，之后一个大写字母
/%0表示小 F 会把指定区域内的所有帽子都变成col颜色。
若op = 2， 接下来 6 个正整数表示帽子戏法指定的区域， 表示小 F 会把指定
区域内的所有帽子都变成绿色。
描述一个区域的方法为：用 6 个整数x_0,y_0,z_0,x_1,y_1,z_1 表示从第x_0层至第x_1
层，从第y_0行至第y_1行，从第z_0列至第z_1列的区域（层、行、列编号的范围都是
1…n） 。

输出格式

对于每个询问，输出一行一个整数表示答案。

样例

样例输入
3 5
1 2 2 2 3 3 3 B
1 1 3 2 3 3 2 R
0 1 1 1 3 3 3
2 3 3 3 3 3 3 B
0 2 1 3 3 3 3
样例输出
18
3

数据范围

对于 10%的数据，保证n=1。
对于另外 10%的数据，保证只有询问操作，即保证op=0。
对于 30%的数据，保证n≤ 5，Q ≤ 10。
对于 100%的数据，保证n ≤ 40，Q ≤ 200。

题解

看一下数据范围就应该知道是暴力的吧。maxn*maxn*maxn*maxQ=12800000，排除每一次查询、更改操作全部为最大操作的情况可知，O(n^3)可解
贴出代码

#include<bits/stdc++.h>
#define maxn 405
using namespace std;
int n,q,ans;
int x1,z1,x2,y2,z2;
int y01,cmd;
char cas;
char a[maxn][maxn][maxn];
int main(){
    //freopen("hat.in","r",stdin);
    //freopen("hat.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(register int i=0;i<=n;i++){
        for(register int j=0;j<=n;j++){
            for(register int k=0;k<=n;k++)a[i][j][k]='G';
        }
    }
    while(q--){
        cin>>cmd;
        if(cmd==0){
            ans=0;
            cin>>x1>>y01>>z1>>x2>>y2>>z2;
            //cout<<x1<<" "<<y01<<" "<<z1<<" "<<x2<<" "<<y2<<" "<<z2<<endl;
            for(register int i=x1;i<=x2;i++){
                for(register int j=y01;j<=y2;j++){
                    for(register int k=z1;k<=z2;k++){
                        //cout<<"now:"<<i<<" "<<j<<" "<<k<<" "<<a[i][j][k]<<endl;
                        if(a[i][j][k]=='G')ans++;
                    }
                }
            }
            cout<<ans<<endl;
        }
        else if(cmd==1){
            cin>>x1>>y01>>z1>>x2>>y2>>z2;
            //cout<<x1<<" "<<y01<<" "<<z1<<" "<<x2<<" "<<y2<<' '<<z2<<endl;
            cin>>cas;
            for(register int i=x1;i<=x2;i++){
                for(register int j=y01;j<=y2;j++){
                    for(register int k=z1;k<=z2;k++){
                        a[i][j][k]=cas;
                    }
                }
            }
        }
        else if(cmd==2){
            cin>>x1>>y01>>z1>>x2>>y2>>z2;
            //cout<<x1<<" "<<y01<<" "<<z1<<" "<<x2<<" "<<y2<<' '<<z2<<endl;
            cin>>cas;
            for(register int i=x1;i<=x2;i++){
                for(register int j=y01;j<=y2;j++){
                    for(register int k=z1;k<=z2;k++){
                        if(a[i][j][k]==cas){
                            a[i][j][k]='G';
                            //cout<<i<<" "<<j<<" "<<k<<" "<<a[i][j][k]<<endl;
                        }
                    }
                }
            }
        }
    }
    return 0;
}

T2 最大队列

问题描述

给定一个长度为n的排列（共包含n个整数，每个数取值范围1和n之间，且每个正整数出现并只出现一次）。借助一个栈，依次将这个排列的每个元素进栈，并在合适的时候出栈，可以得到不同的出栈序列。不同的操作会带来不同的出栈序列，请你求出在所有可能的方案中，字典序最大的出栈序列。

输入格式

输入数据共包括两行。
第一行包含一个正整数n，表示给定的排列的长度。
第二行包含n个正整数，描述给定的序列。

输出格式

仅一行，共n个整数，表示你计算出的出栈序列。

样例

样例输入1
4
4 2 1 3
样例输出1
4 3 1 2
样例输入2
10
4 5 1 2 6 10 7 8 3 9
样例输出2
10 9 3 8 7 6 2 1 5 4

数据范围

所有测试点的数据规模与约定如上

题解

先说说自己的错误思路。先将所有数据排序，然后为了让字典序尽量大则每次选取当前没有被选取的最大值。同时我们维护一个上一次选取的数的位置lastp，若lastp的值比当前我们要出栈的元素的位置的值要小我们则直接让当前元素出栈，否则我们从将lastp到当前位置i的所有元素全部出栈。在一定程度上这样的思路是正确的，但是我们如果这样做就考虑漏了一种情况，即当我们先输出元素比我们从lastp输出到i时中间值的字典序要小，则整体字典序会比正确答案偏小。
上40分代码

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int n;
int a[maxn];
struct edge{
    int a;
    int flag;
}E[maxn];
bool cmp(edge a,edge b){
    if(a.a!=b.a)return a.a>b.a;
    return a.flag<b.flag;
}
set<int> save;
int lastp=-1;
int out[maxn],note=1;
//map<int,int> jump;
int main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    n=read();
    //cout<<n<<endl;
    for(register int i=1;i<=n;i++){
        a[i]=read();
        //cout<<a[i]<<" ";
        E[i].a=a[i];
        E[i].flag=i;
    }
    sort(E+1,E+1+n,cmp);
    for(register int i=1;i<=n;i++){
        if(save.count(E[i].a))continue;
        if(lastp<E[i].flag){
            out[note]=E[i].a;
            save.insert(E[i].a);
            note++;
            lastp=E[i].flag;
        }
        else{
            for(register int j=lastp-1;j>=E[i].flag;j--){
                if(save.count(a[j]))continue;
                out[note]=a[j];
                note++;
                save.insert(a[j]);
                //jump[j]=max(jump[j],lastp-1);
            }
            lastp=E[i].flag;
        }
    }
    for(register int i=1;i<note;i++){
        printf("%d",out[i]);
        if(i!=note-1)printf(" ");
    }
    return 0;
}

事实上，为了将上述情况纳入考虑范围内，我们选择使用在线的算法。我们令当前栈顶的元素为x，并使所有还没有入栈的元素中的最大值y。当x\le y时我们不断入栈，直到情况不满足为止。此时则将y直接扔出去即可。当没有比栈顶元素更大的值时我们就不再入栈，而一直弹出栈顶元素直到满足条件或没有元素位置。由于每次查询最大值时的复杂度为O(n)，遍历一次的复杂度为O(n)，总复杂度则为O(n^2)。
朴素O(n^2)代码如下

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int n;
int a[maxn];
int maxnow;
int getmax(int now){
    int cas=-1;
    for(register int i=now;i<=n;i++)cas=max(cas,a[i]);
    return cas;
}
stack<int> box;
int out[maxn],note=1;
int main(){
    //freopen("1.txt","r",stdin);
    n=read();
    for(register int i=1;i<=n;i++)a[i]=read();
    for(register int i=1;i<=n;i++){
        //cout<<box.top()<<endl;
        if(box.empty()){
            box.push(a[i]);
            continue;
        }
        maxnow=getmax(i);
        if(box.top()>=maxnow){
            out[note]=box.top();
            //cout<<out[note]<<" ";
            box.pop();
            note++;
            i--;
            continue;
        }
        box.push(a[i]);
    }
    while(!box.empty()){
        out[note]=box.top();
        //cout<<out[note]<<" ";
        box.pop();
        note++;
    }
    //cout<<endl;
    for(register int i=1;i<note;i++)printf("%d ",out[i]);
    return 0;
}

当然朴素算法并不能满足n=200000等大数据的要求，因此我们要对算法进行优化。事实上我们可以减少取最大值的次数——我们只在开始时和每一次最大值被pop出栈时才重新取一次最大值

for(register int i=1;i<=n;i++)a[i]=read(),maxnow=max(maxnow,a[i]);
for(register int i=1;i<=n;i++){
        if(i==1){
            box.push(a[i]);
            continue;
        }
        if(box.top()>=maxnow){
            maxnow=getmax(i);
            out[note]=box.top();
            box.pop();
            note++;
            i--;
            continue;
        }
        box.push(a[i]);
    }

完整代码

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int n;
int a[maxn];
int maxnow;
int getmax(int now){
    int cas=-1;
    for(register int i=now;i<=n;i++)cas=max(cas,a[i]);
    return cas;
}
stack<int> box;
int out[maxn],note=1;
int main(){
    //freopen("1.txt","r",stdin);
    n=read();
    for(register int i=1;i<=n;i++)a[i]=read(),maxnow=max(maxnow,a[i]);
    for(register int i=1;i<=n;i++){
        if(box.empty()){
            box.push(a[i]);
            continue;
        }
        if(box.top()>=maxnow){
            maxnow=getmax(i);
            out[note]=box.top();
            //cout<<box.top()<<endl;
            box.pop();
            note++;
            i--;
            continue;
        }
        box.push(a[i]);
    }
    while(!box.empty()){
        out[note]=box.top();
        box.pop();
        note++;
    }
    for(register int i=1;i<note;i++)printf("%d ",out[i]);
    return 0;
}

T3 思考熊的马拉松

题面描述

今年，n只思考熊参加了校园马拉松比赛。马拉松的赛道是环形的，每圈的
长度是:，完成比赛需要跑;圈。
比赛中，甲领先乙很长距离，绕过一圈或多圈后从后面追上了乙的现象叫做
“套圈” 。 套圈现象非常常见， 例如： 跑得比谁都快的S熊可以套某些熊 L-1圈；
U 熊经常进行日常耐力训练，套圈次数和被套圈次数基本持平；而M 作为一只
老年熊，则是被套L-1圈的那种。
与人不同的是， 思考熊在跑步时都是匀速运动。W 熊是这次比赛的计时员，
他统计了参赛的n只熊的速度v_1 ,v_2 ,…,v_n（其中最大的一个是S熊的速度） 。现
在W熊希望你告诉他，当速度最快的S熊到达终点时，场上所有熊中总共发生
了多少次套圈现象。
注意：在S熊刚刚到达终点那一刻，如果甲恰好追上了乙，此时也算作甲将
乙套圈。

输入格式

输入的第一行包含两个整数T,C,分别表示这个测试点的组数和这个测试点的编号。对于测试数据，保证T=10。
每组数据的第一行包含3个正整数n,A,L，分别表示思考熊的只数、跑道每圈的长度和完成比赛所需要的圈数。保证A,L\le 10^8。
第二行包含n个正整数v_1,v_2,...,v_n表示每只思考熊的速度。保证这些数互不相同。

输出格式

输出T行，分别表示每组数据中所有熊发生的套圈总次数。

样例

样例输入
1 0
3 2 6
1 2 3
样例输出
8

数据范围

所有测试点的数据规模与约定如上

题解

这是一道数学题，去隔壁请一个数竞大佬来吧。
首先我们已知比赛结束时间t_{end}一定是\frac{L*A}{v_{max}}，则此时为了求出结束时间我们就先将所有熊的速度从大到小排序，然后求t_{end}=\frac{A*L}{v_1}即可知道能跑的最长时间。这时我们知道对于\forall v_1 <v_2都一定有v_2套v_1 k圈的时间是t_k=\frac{A*k}{v_2-v_1}，则我们可以取t_k\le t_{end}为答案。则因此联立方程组后可知，对于我们排序后的数列中\forall v_i和v_j，一定有a_{ij}=\frac{A*abs(v_i-v_j)}{v_{end}}。我们枚举每一个数即可得到答案。复杂度即为O(n^2)。
PS:虽然\forall v都\le 10^8，但是\forall x=abs(v_1-v_2)*L不一定满足x \subseteq (1,10^8)!
贴出该题的部分分解法(50)

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
    register char c=get();register long long f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
long long n,A,L;
long long v[maxn];
bool cmp(long long a,long long b){
    return a>b;
}
long long ans=0;
int main(){
    //freopen("2.txt","r",stdin);
    long long T,C;
    T=read();C=read();
    //cout<<1<<endl;
    while(T--){
        ans=0;
        n=read();A=read();L=read();
        for(register long long i=1;i<=n;i++)v[i]=read();
        if(n==1){
            puts("0");
            continue;
        }
        sort(v+1,v+1+n,cmp);
        for(register long long i=1;i<=n;i++){
            for(register long long j=i+1;j<=n;j++){
                ans+=(L*(v[i]-v[j]))/v[1];
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

紧接着我们继续考虑更加一般的情况。

image

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int MAXN = 100005;
int n;
int64 L,A;
int64 a[MAXN], b[MAXN], c[MAXN];
inline int lowbit(int x) {
    return x & (-x);
}
void insert(int x) {
    for (int i = x; i <= n; i += lowbit(i)) c[i]++;
}
int getsum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}
int main() {
    //freopen ("running.in","r",stdin);
    //freopen ("running.out","w",stdout);
    int T, case_num;
    scanf("%d%d", &T, &case_num);
    while (T--) {
        scanf("%d%lld%lld", &n, &A, &L);
        int64 ans = 0;
        int64 maxv = 0;
        for (int i = 1; i <= n; i++) {
            c[i] = 0;
            scanf("%lld", &a[i]);
            maxv = max(maxv, a[i]);
            a[i] *= L;
        }
        sort(a + 1, a + n + 1);
        reverse(a + 1, a + n + 1);
        for (int i = 1; i <= n; i++) {
            ans += (a[i] / maxv) * (int64) (n - 2 * i + 1);
            a[i] %= maxv;
        }
        for (int i = 1; i <= n; i++) b[i] = a[i];
        sort(b + 1, b + n + 1);
        int m = int(unique(b + 1, b + n + 1) - (b + 1));
        for (int i = 1; i <= n; i++) {
            a[i] = int(lower_bound(b + 1, b + m + 1, a[i]) - b);
            ans -= getsum(a[i] - 1);
            insert(a[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,186评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,858评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,620评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,888评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,009评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,149评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,204评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,956评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,385评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,698评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,863评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,544评论 4赞 335
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,185评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,899评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,141评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,684评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,750评论 2赞 351

推荐阅读更多精彩内容

  • Kotlin基础语法
    标签：kotlinandroidkotlin语法 摘要 如果你真的希望深入的了解kotlin语言，可以查看英文版K...
    活这么大就没饱过阅读 1,331评论 0赞 0
  • 2017-04-05
    这一刻突然让我回到了10年前的感觉，那时候我假装坚强，那时候我违心的做了一件我一辈子都后悔的事情。此刻，难道又是历...
    死亡骑士一阅读 106评论 0赞 0
  • 睡前日记4
    睡前日记记录L.P的每日自我挑战。今天起床时间6点38分，闹钟时间6点10分，以下是挑战内容。 坚持早起4天 坚持...
    丿清欢阅读 124评论 0赞 0