NOIp膜你题   Day2

duliu 出题人：ZAY   

 题解

这就是一道组合数问题鸭！！！  可是泥为什么没有推出式子！！

首先我们知道的是 m 盆花都要摆上，然后他们的顺序不定（主人公忘记了）

所以初步得到一个排列数 P( m,m ) ， 即 Pmm

那么我们就还剩下 n-m 个空位置，这些空位置都是不可以放花的，于是我们逆向思维一下：

n-m  个位置不放花，也就是可以在这些位置周围插空放花，把这些位置隔开，那么就可以把m盆花放到 n-m+1 个空里，由于这是对于空位置来说的，没有顺序可言，每个都是一毛一样的，所以得到一个组合数  C（n-m+1 ， m） , 即 Cn-m+1m

所以 ans = P( m,m ) * C( n-m+1 ， m )

= m! * (n-m+1)! / [ m! * (n-m+1 - m)! ]

化简一下就是下面

=（n-m+1）*（n-m+1-1）*......*（n-2m+2）

注意

ans 要开 long long , 试过毒了，数据不开 long long 会炸

代码

#include<bits/stdc++.h>

using namespace std;

int type,n,m,p;

long long ans=;

int main()

{

    freopen("ilove.in","r",stdin);

    freopen("ilove.out","w",stdout);

    scanf("%d%d%d%d",&type,&n,&m,&p);

    if(n==&&m==)  { printf("1\n");   return ; }

    int a=n-m+,b=n-m-m+;

    for(int i=a;i>=b;i--)

      ans=(ans%p*i%p)%p;

    printf("%ld\n",ans);

    return ;

}

看看出题人的题解

一般这种数数题，也就是求方案数，有两种解决方案：DP&组合数学

1.DP

2.组合数学

Ps：插空法就是我上面题解里面提到的

题解

注意到根据题目规定的走法，在进入一个节点以后，必须遍历完它的整个子树， 否则一旦离开这个节点，再也无法进入这棵子树，从而导致该节点的某个孩子没能放 上石子，导致这个节点不能放上石子。

同时又有每个节点放上石子以后，它的子树的 石子可以全部取回。设在节点 u 放石子需要有 ansu 个石子，则放完 u 以后可以取回 ansu-wu 个石子。

因为你准备了ansu个石子，u点需要wu个石子放上，那么放完之后，他的子树上的石子就可以取回来了，也就是ansu-wu个，这些也就是节点u的孩子所需石子数和。

于是考虑影响问题答案的显然是从 u 进入每个孩子的顺序，由于最多有两个孩 子，直接比较一下就可以知道先进入哪个孩子更优秀了。时间复杂度 O(n)

代码

#include <cstdio>

#include <vector>

#include <algorithm>

const int maxn = ;

int n;

int MU[maxn], ans[maxn];    //MU也就是W

std::vector<int>son[maxn];

void dfs(const int u);

bool cmp(const int &_a, const int &_b);

int main() {

  freopen("yin.in", "r", stdin);

  freopen("yin.out", "w", stdout);

  scanf("%d", &n);

  for (int i = , x; i <= n; ++i) {

    scanf("%d", &x);

    son[x].push_back(i);

  }

  for (int i = ; i <= n; ++i) {

    scanf("%d", MU + i);

    //数组名+一个东西  这是指针的写法

    //相当于scanf("%d",&MU[i]);

  }

  dfs();

  for (int i = ; i < n; ++i) {

    printf("%d ", ans[i]);

  }

  printf("%d\n", ans[n]);

  return ;

}

void dfs(const int u) {

  for (auto v : son[u]) {  //遍历u的所有子节点

    dfs(v);

  }

  std::sort(son[u].begin(), son[u].end(), cmp);

  //按照差值不升序排序

  int _ret = ;

  //此时U节点的所有子节点已经算出来了，准备计算U节点

  for (auto v : son[u]) {  //叶节点没有儿子就不会for循环

    if (_ret >= ans[v]) //上一个子节点收回的石子足够摆当前节点，就摆上

    {

      _ret -= ans[v];   //ret摆完之后更新

    }

    else

    {

      ans[u] += ans[v] - _ret;  //收回的石子不够放了，往上补

      _ret = ans[v] - MU[v];

      //遍历完U的儿子V节点对应的子树后，收回除了 U的儿子v以外所有节点上的石头

    }

  }

  ans[u] += std::max(, MU[u] - _ret);

  //深搜，会先到达所有叶节点，并且所有叶节点的ans=w[i]

}

inline bool cmp(const int &_a, const int &_b) {

  return (ans[_a] - MU[_a]) > (ans[_b] - MU[_b]);

}

题解

1.可以通过前4个任务点的代码QWQ

因为我们看到每封信最多只会有30个字符对吧，那么每次询问给出一个询问区间的时候，我们就可以比对每一位的字符

比如我们比对到了第 i 位，询问区间从头到尾枚举看一看，对于这一位，有几个0，几个1，几个？

如果既有0又有1，那么显然是无解的

如果只有0和？，那么这一位只可以为0，也就是？只能被填成0

如果只有1和？，同上

如果全是？，那么既可以填0，又可以填1，也就是有2种方案

我们把所有位都枚举了一遍，那么可能会出现结果：无解，有唯一解，有解但不唯一；对于最后一种情况显然是？的数目影响的，乘法分布原理 2cnt  , cnt表示？的数目

代码

45‘代码   后边超时辣

#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

using namespace std;

string s[],s1;

int n,m,q;

int qus,num,l,r;

long long ans=;

int main()

{

    freopen("lin.in","r",stdin);

    freopen("lin.out","w",stdout);

    scanf("%d%d%d",&n,&m,&q);

    if(q==) return ;

    for(int i=;i<=m;i++)

      cin>>s[i];

    for(int i=;i<=q;i++)

    {

        ans=;

        scanf("%d",&qus);

        if(qus==)

        {

            scanf("%d%d",&l,&r);

            int flag=,cnt=;

            for(int j=;j<n;j++)

            {

                if(flag==) break;

                bool glf=;

                char mp;

                mp=s[l][j];

                if(mp!='?') glf=;

                else glf=;

                for(int k=l+;k<=r;k++)

                {

                    if(s[k][j]!='?')

                    {

                        if(mp=='?')

                        {

                            glf=;

                            mp=s[k][j];

                            continue;

                        }

                        if(mp!='?'&&mp!=s[k][j])

                        {

                            flag=;

                            continue;

                        }

                    }

                    else if(s[k][j]=='?')

                    {

                        if(glf==) glf=;

                    }

                }

                if(mp!='?') glf=;

                cnt+=glf;

            }

            if(flag==) {printf("0\n");}

            else

             {

                 ans=pow(,cnt);

                printf("%ld\n",ans);

             }

        }

        if(qus==)

        {

            scanf("%d",&num);

            cin>>s1;

            s[num]=s1;

        }

    }

    return ;

}

我百分之200的错误都是因为脑残，下面这个是整理了一下（貌似并不可以多得分）

#include<bits/stdc++.h>

using namespace std;

int n,m,q;

string s[],s1;

int opt,l,r,pos;

inline int read()

{

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int main()

{

    freopen("lin.in","r",stdin);

    freopen("lin.out","w",stdout);

    n=read(); m=read(); q=read();

    for(int i=;i<=m;i++)

      cin>>s[i];

    for(int i=;i<=q;i++)

    {

        opt=read();

        if(opt==)

        {

            pos=read();

            cin>>s1;

            s[pos]=s1;

        }

        else

        {

            l=read();r=read();

            long long ans;

            int flag=,cnt=;

            for(int j=;j<n;j++)

            {

                if(flag==) break;

                int flag0=,flag1=,flag2=;

                for(int k=l;k<=r;k++)

                {

                    if(s[k][j]=='') flag0++;

                    if(s[k][j]=='') flag1++;

                    if(s[k][j]=='?') flag2++;

                }

                if(flag0!=&&flag1!=) { flag=; continue; }

                else if(flag2==(r-l+)) cnt++;

            }

            if(flag==) ans=;

            else ans=pow(,cnt);

            printf("%ld\n",ans);

        }

    }

    return ;

}

当然也可以用按位与维护

2.考虑正解：线段树

代码

忍不了这个指针了

#include <cstdio>

template <typename T>

inline void qr(T &x) {

  char ch = getchar(), lst = ' ';

  while ((ch > '') || (ch < '')) lst = ch, ch=getchar();

  while ((ch >= '') && (ch <= '')) x = (x << ) + (x << ) + (ch ^ ), ch = getchar();

  if (lst == '-') x = -x;

}   //快读 

const int maxn = ;

int n, m, q;

char s[maxn][];   //每封信的内容 

#ifdef ONLINE_JUDGE

int Ans;

#endif

struct Tree {

  Tree *ls, *rs;

  int l, r, x, y;

  bool leg;      //是否合法 

  Tree() {

    ls = rs = NULL;

    l = r = x = y = ;

    leg = true;   //先假定合法

  }

  void pushup() {   //构造a1,a2,b1,b2

    if (!(this->ls->leg && this->rs->leg)) {

      this->leg = false;

    } else {

      if ((this->ls->x & this->rs->x) & (this->ls->y ^ this->rs->y)) {

        this->leg = false;

      } else {

        this->leg = true;

        this->x = this->ls->x | this->rs->x;

        this->y = this->ls->y | this->rs->y;

      }

    }

  }

};

Tree *rot;   //线段树的根 

void ReadStr(char *p);   //指针  快读

void Update(const int x);

void Query(const int l, const int r);

void update(Tree *const u, const int p);  //修改

Tree query(Tree *u, const int l, const int r);   //查询

void build(Tree *const u, const int l, const int r);   //建树 

int main() {

  freopen("lin.in", "r", stdin);

  freopen("lin.out", "w", stdout);

  qr(n); qr(m); qr(q);

  for (int i = ; i <= m; ++i) {

    ReadStr(s[i] + );

  }

  build(rot = new Tree, , m);   //建树

  int opt, l, r;

  while (q--) {

    opt = ; qr(opt);

    if (opt == ) {   //查询

      l = r = ; qr(l); qr(r);

      Query(l, r);

    } else {

      l = ; qr(l);

      ReadStr(s[] + );

      Update(l);   //修改第一个

    }

  }

#ifdef ONLINE_JUDGE   //鬼知道干啥的

  printf("%d\n", Ans);

#endif

  return ;

}

void ReadStr(char *p) {

  do *p = getchar(); while ((*p != '') && (*p != '') && (*p != '?'));

  do *(++p) = getchar(); while ((*p == '') || (*p == '') || (*p == '?'));

  *p = ;

}

void build(Tree *const u, const int l, const int r) {

  if ((u->l = l) == (u->r = r)) {   //当前区间在要建的区间内

    for (int i = ; i <= n; ++i) {

      if (s[l][i] != '?') {

        u->x |=  << i;

        if (s[l][i] == '') {

          u->y |=  << i;

        }

      }

    }

  } else {  //不在

    int mid = (l + r) >> ;

    build(u->ls = new Tree, l, mid);

    build(u->rs = new Tree, mid + , r);

    u->pushup();

  }

}

Tree query(Tree *u, const int l, const int r) {

  if ((u->l > r) || (u->r < l)) return Tree();  //当前区间完全不在查询区间

  if ((u->l >= l) && (u->r <= r)) return *u;  //完全在

  Tree _ret;

  auto ll = query(u->ls, l, r), rr = query(u->rs, l, r);  //否则递归来求

  _ret.ls = &ll; _ret.rs = &rr;

  _ret.pushup();

  return _ret;

}

void Query(const int l, const int r) {

  auto _ret = query(rot, l, r);

  if (!_ret.leg) {  //不合法输出‘0’

#ifndef ONLINE_JUDGE

    puts("");

#endif

  } else {

    int ans = ;

    for (int i = ; i <= n; ++i) if (!(_ret.x & ( << i))) {

      ans <<= ;

    }

#ifdef ONLINE_JUDGE

    Ans ^= ans;

#else

    printf("%d\n", ans);

#endif

  }

}

void update(Tree *u, const int p) {  //修改第p个

  if (u->ls) {  //寻找p

    if (u->ls->r >= p) {  //左子树右端点比p大

      update(u->ls, p);

    } else {

      update(u->rs, p);

    }

    u->pushup();  //把子节点的信息合并到父节点

  } else {

    *u = Tree();

    u->l = u->r = p;

    for (int i = ; i <= n; ++i) {

      if (s[][i] != '?') {

        u->x |=  << i;

        if (s[][i] == '') {

          u->y |=  << i;

        }

      }

    }

  }

}

void Update(const int x) {

  update(rot, x);   //修改

}

拒绝理解Zay的代码

放一只water lift的代码（线段树板子）

#include <bits/stdc++.h>

using namespace std;

template <class T>

inline void read(T &num)

{

    bool flag = ;

    num = ;

    char c = getchar();

    while ((c < '' || c > '') && c != '-')

        c = getchar();

    if (c == '-')

    {

        flag = ;

        c = getchar();

    }

    num = c - '';

    c = getchar();

    while (c >= '' && c <= '')

        num = (num << ) + (num << ) + c - '', c = getchar();

    if (flag)

        num *= -;

}

template <class T>

inline void output(T num)

{

    if (num < )

    {

        putchar('-');

        num = -num;

    }

    if (num >= )

        output(num / );

    putchar(num %  + '');

}

template <class T>

inline void outln(T num)

{

    output(num);

    putchar('\n');

}

template <class T>

inline void outps(T num)

{

    output(num);

    putchar(' ');

}

const int N = , M = ;

int n, m, q;

struct segment

{

    char val[M];

    bool all1[M * ];

    bool all0[M * ];

    void init(int node, int nl, int nr)//这是个正常的线段树的板子（虽然位置好像不大正常）

    {

        if (nl < nr)

        {

            int mid = (nl + nr) >> ;

            init(node * , nl, mid);

            init(node *  + , mid + , nr);

            all1[node] = all1[node * ] & all1[node *  + ];

            all0[node] = all0[node * ] & all0[node *  + ];

        }

        else

        {

            if (val[nl] == '?')

                all1[node] = all0[node] = ;

            else

            {

                all1[node] = val[nl] == '';

                all0[node] = val[nl] == '';

            }

        }

    }

    void modify(int node, int nl, int nr, int x, char va)

    {

        if (val[x] == va)

            return;

        if (nl < nr)

        {

            int mid = (nl + nr) >> ;

            if (x <= mid)

            {

                modify(node * , nl, mid, x, va);

            }

            else

            {

                modify(node *  + , mid + , nr, x, va);

            }

            all1[node] = all1[node * ] & all1[node *  + ];

            all0[node] = all0[node * ] & all0[node *  + ];

        }

        else

        {

            if (va == '?')

                all1[node] = all0[node] = ;

            else

            {

                all1[node] = va == '';

                all0[node] = va == '';

            }

            val[x] = va;

        }

    }

    pair<bool, bool> query(int node, int nl, int nr, int l, int r)

    {

        if (l <= nl && r >= nr)

        {

            return make_pair(all1[node], all0[node]);

        }

        int mid = (nl + nr) >> ;

        bool a1 = true, a0 = true;

        if (l <= mid)

        {

            auto lo = query(node * , nl, mid, l, r);

            a1 &= lo.first;

            a0 &= lo.second;

        }

        if (r >= mid + )

        {

            auto lo = query(node *  + , mid + , nr, l, r);

            a1 &= lo.first;

            a0 &= lo.second;

        }

        return make_pair(a1, a0);

    }

    void dfs(int node, int nl, int nr)

    {

        if (nl < nr)

        {

            int mid = (nl + nr) >> ;

            dfs(node * , nl, mid);

            dfs(node *  + , mid + , nr);

        }

        outps(nl);

        outps(nr);

        outps(all1[node]);

        outln(all0[node]);

    }

} segs[N];

int main()

{

    freopen("lin.in", "r", stdin);

    freopen("lin.out", "w", stdout);

    read(n);

    read(m);

    read(q);

    char ch;

    for (int i = ; i <= m; i++)

    {

        for (int j = ; j <= n; j++)

        {

            do

            {

                ch = getchar();

            } while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t' || ch == '\0');

            segs[j].val[i] = ch;

        }

    }

    for (int i = ; i <= n; i++)

    {

        segs[i].init(, , m);

    }

    while (q--)

    {

        bool opt;

        read(opt);

        if (opt == )

        {

            int l, r;

            read(l);

            read(r);

            int ans = ;

            for (int i = ; i <= n; i++)

            {

                auto lo = segs[i].query(, , m, l, r);

                ans *= (lo.first + lo.second);

            }

            outln(ans);

        }

        else

        {

            int pos;

            read(pos);

            for (int i = ; i <= n; i++)

            {

                do

                {

                    ch = getchar();

                } while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t' || ch == '\0');

                segs[i].modify(, , m, pos, ch);

            }

        }

    }

}

彩蛋：

考试暴露了很多小问题

1.文件的读写

安利一个方法：如何比较自己的代码ans和答案out是否一致（不仅是用在NOIP上，还有NOI，IOI）

（1）键盘按住 shift 键，同时鼠标右键单击

（2）会崩出一个会话框，点击“在此处打开命令窗口”，win10不大一样，好像是f**忘了

（3）就会出现这个东西

不输入cmd 也可以，因为它本身就是cmd

（4）输入  fc  文件1  文件2

如果不同的话

如果相同的话

这样你就可以看看自己的答案对不对，错在哪里QWQ

2.数据分治

也就是对于不同的子任务你可以用不同的方法解决掉，从而骗取更多分数

3.编译&加文件的顺序

大型考试的时候呢,如果你代码一旦进行了修改，那么一定要重新试一遍样例

freopen就不要注释掉啦

4.题目难度和顺序安排不一定有瓜

最新文章

  1. C#最简单例子
  2. 世界上不存在什么RedBSD,SuseBSD或者ArchBSD，Turb...
  3. js各种宽高(3)
  4. VLC的相关文档以及javascript接口
  5. EasyUI easyui-combobox 重复发送请求
  6. Elasticsearch安装详解
  7. es6-promise源代码重点难点分析
  8. log4j２ 标签解析
  9. GetLastError 错误返回码
  10. Hadoop-2.0 目录简介
  11. bat脚本的写法
  12. 【BZOJ1878】【SDOI2009】 HH的项链
  13. [UE4]RepNotify，更新通知
  14. 动手动脑-java重载
  15. IntelliJ IDEA 编译代码报错 找不到符号 符号: 找不到符号包 包
  16. Windows核心编程：第13章 内存体系结构
  17. 使用 istreambuf_iterator 读取文件内容，赋值给 std::string
  18. 重构一段基于原生JavaScript的表格绘制代码
  19. BUAA软工个人作业Week2-代码复审
  20. linux 批量更改文件名 rename 命令

热门文章

  1. 4.IntelliJ Idea 常用快捷键
  2. Mysql学习总结（38）——21条MySql性能优化经验
  3. 洛谷 P3178 BZOJ 4034 [HAOI2015]树上操作
  4. 0918如何利用jmeter为数据库插入测试数据
  5. EularProject 36：2进制和10进制回文数
  6. 文件I/O操作——File类
  7. 面向对象的三大特性之二——继承（含super的使用）
  8. Web前端开发实战6：CSS实现导航菜单结合二级下拉式菜单的简单变换
  9. luogu4012 深海机器人问题 网络流
  10. ASP.NET Razor - C# Variables