c/c++语言开发共享长乐国庆集训Day3

T1 动态逆序对 题目 【题目描述】 给出一个长度为n的排列a(1~n这n个数在数列中各出现1次)。每次交换两个数,求逆序对数%2的结果。 逆序对:对于两个数a[i],a[j](i<j),若a[i]>a[j],则(a[i],a[j])为1个逆序对。 【输入格式】 第一行一个正整数n。 接下来一行n个 …


t1 动态逆序对

题目

【题目描述】

给出一个长度为n的排列a(1~n这n个数在数列中各出现1次)。每次交换两个数,求逆序对数%2的结果。

逆序对:对于两个数a[i],a[j](i<j),若a[i]>a[j],则(a[i],a[j])为1个逆序对。

【输入格式】

第一行一个正整数n。

接下来一行n个数,表示给出的排列a。

接下来一行一个正整数q。

接下来q行,每行两个正整数i,j,表示交换a[i]和a[j]。

【输出格式】

输出共q行,表示每次交换后的逆序对数%2的结果。

【输入样例】

4  1 2 3 4  2  1 2  1 2

【输出样例】

1  0

【数据规模】

对于60%的数据:n,q≤100;

对于80%的数据:n,q≤1000;

对于100%的数据:n,q≤100000。

解析

先求出初始序列的逆序对总数对2取余的结果。

每次交换a[i]与a[j](i<j),对于a[k]的影响如下:

  • 若k<i,a[k]依旧在a[i]与a[j]前面,所以a[k]与a[i]、a[j]产生的逆序对数不变;
  • 若k>j,同上,逆序对数不变;
  • 若i<k<j,如果a[i]<a[k],则逆序对数+1,否则-1,;如果a[j]>a[k],则逆序对数+1,否则-1,

而我们只需求出逆序对数对2取余的结果,可以发现,逆序对个数的奇偶性与k无关。

事实上,只需在每次交换位置时,令逆序对总数对2取余的结果^1即可(i=j时则不变)。

code

#include <algorithm>  #include <iostream>  #include <cstring>  #include <string>  #include <cstdio>  #include <cmath>  using namespace std;  inline int read()  {      int num=0,w=1;      char ch=getchar();      while(ch<'0'||ch>'9')      {          if(ch=='-') w=-1;          ch=getchar();      }      while(ch>='0'&&ch<='9')      {          num=(num<<1)+(num<<3)+ch-'0';          ch=getchar();      }      return num*w;  }  int n,q,a[100100],f[100100],temp;  void add(int x,int y)  {      for(;x<=n;x+=(x&-x)) f[x]+=y;  }  int ask(int x)  {      int ans=0;      for(;x;x-=(x&-x)) ans+=f[x];      return ans;  }  int main()  {      //freopen("lyk.in","r",stdin);      //freopen("lyk.out","w",stdout);      n=read();      for(int i=1;i<=n;i++) a[i]=read();      q=read();      for(int i=n;i>=1;i--)      {          temp+=ask(a[i]-1);          add(a[i],1);      }      temp&=1;      for(int i=1;i<=q;i++)      {          int x=read(),y=read();          if(x!=y) temp^=1;          cout<<temp<<endl;      }      return 0;  }

 

 

 

 

 

t2 树的统计

题目

【题目描述】

给出一棵n个点的满二叉树,根节点为1,第i个点的左右子节点分别为第2i,2i+1个点,第i个点的权值为a[i]。

有m个询问。对于每个询问给出x,d,求到点x的距离为d的所有点的点权和。如果不存在符合条件的点,输出0。

两点距离即两点间最短路径的边数。

保证最终答案在int范围内。

【输入格式】

第一行两个正整数n,m。

接下来n行每行一个正整数,第i行的数表示a[i]。

接下来m行每行两个整数x,d,表示一个询问。

【输出格式】

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

【输入样例】

7 3  13  7  2  9  5  6  8  1 3  4 2  3 1

【输出样例】

0  18  27

【数据规模】

对于80%的数据,n≤1023,m≤1000。

对于100%的数据,n≤131071,m≤100000,n=2t-1,1≤t≤17,a[i]≤30000。

解析

对于每个询问,用dfs搜索与点x距离为d的点,进行统计即可。

注意每个点之间的关系,访问父亲是x<<1,左儿子是x>>1,右儿子是x>>1+1,要特判一下左右儿子编号不能大于n,否则会re。

code

#include <algorithm>  #include <iostream>  #include <cstring>  #include <string>  #include <cstdio>  #include <cmath>  #include <queue>  using namespace std;  inline int read()  {      int num=0,w=1;      char ch=getchar();      while(ch<'0'||ch>'9')      {          if(ch=='-') w=-1;          ch=getchar();      }      while(ch>='0'&&ch<='9')      {          num=(num<<1)+(num<<3)+ch-'0';          ch=getchar();      }      return num*w;  }  const int n=131073;  int n,m,a[n],dd,ans;  void dfs(int x,int d,int from)  {      if(d>dd) return ;      if(d==dd)      {          ans+=a[x];          return ;      }      int y=x>>1;      if(y>=1&&y!=from) dfs(y,d+1,x);      y=x<<1;      if(y<=n&&y!=from) dfs(y,d+1,x);      if(y+1<=n&&y+1!=from) dfs(y+1,d+1,x);  }  int main()  {      //freopen("dream.in","r",stdin);      //freopen("dream.out","w",stdout);      n=read(),m=read();      a[1]=read();      for(int i=2;i<=n;i++) a[i]=read();      for(int i=1;i<=m;i++)      {          int x=read();          dd=read(),ans=0;          dfs(x,0,0);          cout<<ans<<endl;      }      return 0;  }

 

 

 

 

 

t3 宣传栏

题目

【题目描述】

有一个大型的矩形宣传栏,高和宽分别为h和m。宣传栏是用来张贴告示的地方,最初,宣传栏是空的,但此后告示将一张一张的被放上去。

有n张告示,每张告示的高都是一个单位长度,第i张贴上的告示宽度为w[i]。

每次张贴时,总是将告示贴在可以张贴且最高的地方,如果有多个可行的地方,则选择最左边张贴。

给定宣传栏的高和宽,你的任务是找出每个告示张贴在第几行。

【输入格式】

第一行为三个整数,h,m和n(1≤m≤109;1≤h≤n≤200000),表示宣传栏的尺寸和张贴的告示个数。

接下来n行表示w[i](1≤w[i]≤109)。

【输出格式】

每行一个整数表示答案。如果第i个告示没地方贴,输出-1。

【输入样例】

3 5 5  2  4  3  3  3

【输出样例】

1  2  1  3  -1

【数据规模】

对于20%的数据,n=1。

对于40%的数据,n,m≤500。

对于70%的数据,n≤2000。

对于90%的数据,n≤50000。

对于100%的数据,n≤200000。

解析

用c[i]表示第i行还剩多少长度。

用线段树维护c[i]的区间最大值即可。

code

#include <algorithm>  #include <iostream>  #include <cstring>  #include <string>  #include <cstdio>  #include <cmath>  #include <queue>  using namespace std;  inline int read()  {      int num=0,w=1;      char ch=getchar();      while(ch<'0'||ch>'9')      {          if(ch=='-') w=-1;          ch=getchar();      }      while(ch>='0'&&ch<='9')      {          num=(num<<1)+(num<<3)+ch-'0';          ch=getchar();      }      return num*w;  }  int h,m,n,c[800100];  int w;  void build(int p,int l,int r)  {      c[p]=m;      if(l==r) return ;      int mid=(l+r)>>1;      build(p*2,l,mid),build(p*2+1,mid+1,r);  }  int ask(int p,int l,int r)  {      if(l==r)      {          c[p]-=w;          return l;      }      int mid=(l+r)>>1;      if(c[p*2]>=w)      {          int temp=ask(p*2,l,mid);          c[p]=max(c[p*2+1],c[p*2]);          return temp;      }      else      {          int temp=ask(p*2+1,mid+1,r);          c[p]=max(c[p*2+1],c[p*2]);          return temp;      }  }  int main()  {      //freopen("billboard.in","r",stdin);      //freopen("billboard.out","w",stdout);      h=read(),m=read(),n=read();      build(1,1,h);      for(int i=1;i<=n;i++)      {          w=read();          if(w>c[1])          {              cout<<"-1"<<endl;              continue;          }          cout<<ask(1,1,h)<<endl;      }      return 0;  }

 

 

 

 

 

t4 种树

题目

【题目描述】

你要在一条无穷长的马路上种树。

你想种3种树,分别是草莓树,西瓜树,土豆树。

给定3个正整数a,b,c,你可以选择3个整数x,y,z,然后:

  • 在位置 … , x-2a , x-a , x , x+a , x+2a , … 分别种1棵草莓树。
  • 在位置 … , y-2b , y-b , y , y+b , y+2b , … 分别种1棵西瓜树。
  • 在位置 … , z-2c ,z-c , z , z+c , z+2c , … 分别种1棵土豆树。

你想要最大化最近的两棵树的距离,请你输出这个最大距离。

【输入格式】

每个测试点多组测试数据。

每组数据输入一行a,b,c。

没给出数据组数,你可以这样输入:

while (scanf(“%d%d%d”, &a, &b, &c) == 3)

{

       ……

}

【输出格式】

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

【输入样例】

1 5 8  3 3 6  2000 2000 2000  999 999 999  233 233 233  100 100 100  40 30 20

【输出样例】

0  1  666  333  77  33  5

【数据规模】

对于100%的数据,1≤a,b,c≤2000。

解析

先用solve函数求出三树两两之间最小距离的最小值,然后再找到最大的即可。

证明过程比较麻烦,本蒟蒻数论不太好,就不给出详细证明了。

code

#include <algorithm>  #include <iostream>  #include <cstring>  #include <string>  #include <cstdio>  #include <cmath>  #include <queue>  using namespace std;  int a,b,c,x,y,z,ans;  int gcd(int x,int y)  {      if(y==0) return x;      return gcd(y,x%y);  }  int solve(int a,int b,int x,int y)  {      int g=gcd(a,b);      int t=(x-y)%g;      if(t<0) t+=g;      return min(t,g-t);  }  int main()  {      while(cin>>a>>b>>c)      {          ans=0;          for(y=0;y<b;y++)              for(z=0;z<c;z++)              {                  int temp;                  temp=min(solve(a,b,0,y),min(solve(b,c,y,z),solve(a,c,0,z)));                  ans=max(ans,temp);              }          cout<<ans<<endl;      }      return 0;  }

 

www.ctvol.com true Article c/c++语言开发共享长乐国庆集训Day3

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/601585.html

(0)
上一篇 2021年5月10日 上午12:28
下一篇 2021年5月10日 上午12:31

精彩推荐