还有一天就考 noip 了,十分慌张。
考前最后一场模拟赛由 yjq 出题,感谢他的指导

如果来生

(e.pas/c/cpp)
【背景描述】
给定 N 个 1 到 N 的数, 重复以下操作:
设当前剩下 k 个数, 找到所有等于 k 的数, 把这些数全部删掉。
直到没有数或者不能再删数。
你想知道至少要修改这 N 个数中的多少个(修改之后每个数仍然必须从 1 到 N), 使得可以删完这 N 个数。
我们还有 M 次修改操作, 每一次修改会把第 Xi 个数变成 Yi, 每次修改完之后你都要对当前序列回答这个问题。 每次询问的操作不会真正实现,即对后面的询问没有影响。

【输入格式】
第一行两个整数 N,M。
接下来一行 N 个整数, 第 i 个整数表示给出的第 i 个数。
接下来 M 行, 每行两个整数 Xi, Yi 意义如题目所说。

【输出格式】
M 行, 每行一个整数表示答案

【样例输入】
2 2
1 1
2 2
2 1

【样例输出】
0
1

【数据规模】
对于 15% 的数据,N, M ≤ 6.
对于 35% 的数据,N, M ≤ 20.
对于 55% 的数据,N, M ≤ 200。
对于 75% 的数据,N, M ≤ 2000.
对于 100% 的数据,N, M ≤ 200000.

用 a 数组记录每个数出现的次数,开一个数组 b 来存储每个数被覆盖的次数。每个数 i 可以分别覆盖 max(1,i-a[i]+1) 到 i 的所有的数一次。于是不难发现 123456 和 333556 的本质是一样的。如果一个数被覆盖过至少一次,那么就是可以直接不修改而通过;如果一个数没有被覆盖过,那么必须有一个其它的数被修改,修改次数+=1。在每次修改的时候直接判断有没有数的被覆盖情况改变即可。

#include<bits/stdc++.h>
#define maxx 200017
using namespace std;
int a[maxx],b[maxx],c[maxx],n,m,sum;//a[i]->number of i   b[i]->i's be covered times   c[i]->number on i
inline int read(){
    int X=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
void nekopara(int x,int y){
    int cat=sum;
    if(c[x]-a[c[x]]+1>=1&&b[c[x]-a[c[x]]+1]==1)
        cat--;
    if(c[x]-a[c[x]]+1>=1)
        b[c[x]-a[c[x]]+1]--;
    a[c[x]]--;
    if(y-a[y]>=1&&!b[y-a[y]])
        cat++;
    if(y-a[y]>=1)
        b[y-a[y]]++;
    a[y]++;
    c[x]=y;
    sum=cat;    
}
int main(){
    freopen("e.in","r",stdin);
    freopen("e.out","w",stdout);
    n=read(),m=read();
    a[0]='w'+'x'+'h';
    for(int i=1;i<=n;++i)
        c[i]=read(),a[c[i]]++;
    for(int i=1;i<=n;++i)
        for(int j=i;j>=i-a[i]+1&&j>=0;j--)
            b[j]++;
    for(int i=1;i<=n;++i)
        if(b[i])
            sum++;
    for(int i=1,x,y;i<=m;++i){
        scanf("%d%d",&x,&y);
        int z=c[x];
        nekopara(x,y),printf("%d\n",n-sum);
        nekopara(x,z);
    }
}

还能遇见你

(f.pas/c/cpp)
【背景描述】
不想让各位在考前觉得难受,这道题就用来讲聊聊天吧。
其实认识你们也才一年多,我也只比你们大两届,说不定还没大到两岁。
我很想很想帮你们走的更远,更好,退一万步说不要有人因为 OI 反而路变窄了。
我也真的很想很想你们之中有人能补上学校这几年一切的一切的遗憾。
现在你们真的要代表整个学校,去面对接下来一年的旅途。可能我还是太幼稚了吧,竟然有点莫名的想哭。
也许你们已经知道,后面的路会更难走,坡会更陡,对于你们来说,我只能算一个过客,最多只能告诉你这个坡在哪里,你要往哪里走,但是之后,就只能靠你们自己了。
各位,保重。
这道题,送各位上路。

【输入格式】

【输出格式】
你期望的 NOIP 分数

【样例输出】
580

看了最后题过后真的很心酸……
本蒟蒻也只能打一个极其水的代码来向 yjq 致敬了

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("f.in","r",stdin);
    freopen("f.out","w",stdout);
    cout<<"300";
    return 0;
}

[]

分类: 文章

7 条评论

konnyakuxzy · 2017年12月10日 12:57 上午

啊,一直忘了膜这篇博客啊!今天逛博客才想起来。
这是

本博客第一篇非长沙市一中学生写的博客

啊!

太强了%%%%%

现在看起这篇博客不由自主想起了联赛前几天我还信心满满的样子。

唉,还念啊。

    vanilla · 2017年12月10日 10:18 上午

    我国庆还到长沙来训练了的呢

      konnyakuxzy · 2017年12月10日 11:52 上午

      (dalao 能回复我真是太不胜感激了!毕竟博主太弱,站也就冷清。。。)
      Orz 太强了,我可能还没有机会去外省/校集训就退役了呢。。。
      唉我现在还是太弱了。
      话说您有自己的站吗?加个友链呗 dalao?

        vanilla · 2017年12月10日 11:54 上午

        讲真我自己在树莓派上搭的站崩掉几次了
        ……
        只能用 csdn 了 http://blog.csdn.net/vanillayi

          konnyakuxzy · 2017年12月10日 12:05 下午

          友链已加!
          树莓派。。。
          您不会是树莓派搞个站再端口映射一下吧。。。
          那估计慢出人命
          其实如果是html的站(如hexo)的话,用github挺好的。
          我是wordpress->香港虚拟主机+cloudflareCDN 加速,效果感觉挺好的。

          vanilla · 2017年12月10日 12:09 下午

          强啊强

          konnyakuxzy · 2017年12月10日 12:14 下午

          突然发现回复嵌套了 5 层。
          我要写读书笔记了(唉,还不如杀了我)
          先撤退了~

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注