题解 - HJWJBSR's Blog - 贼爷我真的错了。。

NOIP模拟题 2015.8.10 T3

Day10考的时候T1很快就水完了，T2早早弃疗，反正有70分暴力，T3怎么看怎么像SB题，于是考前1h就检查完不管了

不过有人质疑了T3题意，我才发现我TM也看错了。

题解：

所以做这道题只有半个+h，很明显看得出这是树状数组搞一搞就可以了，但是卧榻马并不会这种东西= =，一般都是用线段树。于是本来还打算临时推一下怎么搞这个东西。然后发现其实线段树就可以搞了。首先建一棵有2^k个节点的线段树，每次染色就是直接区间加值，每次询问节点t就从[t,t]这个节点一直往上走，如果当前节点是父亲的左儿子就把当前的节点的区间的右端点权值加入答案，正确性感觉还是比较显然的。于是考场上面还算是搞出来了，事后想想这性质还是蛮屌的= =

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1000050
int t[N*3],ad[N*3],M,n,m;char b[20];
inline int Read()
 {
	 int x=0;char y;
	 do y=getchar(); while (y<'0'||y>'9');
	 do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
	 return x;
 }
inline void adj(int x,int y,int z)
 {int j=z << 1;if (!ad[z]) return;t[z]+=ad[z];if (x!=y) ad[j]+=ad[z],ad[j+1]+=ad[z];ad[z]=0;}
void Modify(int x,int y,int z,int o,int p)
 {
	 int i=x + y >> 1,j=z << 1;
	 adj(x,y,z);
	 if (x==o&&y==p) {ad[z]++;return;}
	 if (o<=i) Modify(x,i,j,o,min(i,p));
	 if (p>i) Modify(i+1,y,j+1,max(o,i+1),p);
	 if (p==y) t[z]++;
 }
int Query(int x,int y,int z,int o)
 {
	 int i=x + y >> 1,j=z << 1;
	 adj(x,y,z);
	 if (x==y) return t[z];
	 if (o<=i) return t[z]+Query(x,i,j,o);else return Query(i+1,y,j+1,o);
 }
int main()
 {
	 freopen("array.in","r",stdin);freopen("array.out","w",stdout);
	 n=Read();m=Read();
	 M=1 << 20;
	 while (m--)
	  {
		  int k,l;
		  scanf("%s",b);
		  if (b[0]=='C') k=Read(),l=Read(),Modify(1,M,1,k,l);else
			 printf("%d\n",Query(1,M,1,Read()));
	  }
	 return 0;
 }

NOIP模拟题 2015.8.9 T3

这是破神蒯的一个sxbk的原题，在一个叫做Bayan的比赛的2014年shortcutB题

题面：有n个白球的和m个黑球，要求将他们排成一列使得每对异色球之间的人数之和最小，并求方案数模10^9+7。

n,m<=100w，T组数据，T<=100

输入格式：第一行一个T，然后T行每行两个n和m

输出格式：T行每行两个答案

Sample Input:

3 1

4 1

3 2

4 2

Sample Output:

1 2

2 1

4 1

8 4

题解：做这套题睡了2h+，所以考的比较hehe，当然就算再给我2h+我也不一定做得出这个题。

这道题喜闻乐见的要推式子：

定义S_n代表n个人两两颜色相异的时候的答案，通过计算可得S_n=(n³-3*n²+2n)/6

先设n>=m，然后将考虑将m个黑球插进来，定义A_i代表第i个黑球插到了第A_i个白球的的后面，我们假设A_i单调不减

简单容斥可得：ans=S_n+m-S_n-S_m-所有的黑球对所有的白球对的贡献-所有的白球对所有的黑球对的贡献，

倒数第二个东西就是Σ_{i=1 to m} A_i*(n-A_i)

最后一个东西就是Σ_{i=1 to m-1}Σ_{j=i+1 to m}A_j-A_i-1，然后这东西明显是可以拆出来的

最后两个东西相加得到：Σ_{i=1 to m}(n-2*i-m-1)²-[A_i-(n+2*i-m-1)/2]²

这东西系数是负的，所以后面那个和平方要最小。

所以我们分类讨论当n-m为奇数，A_i后面那个东西总是能取到0，因为(n+2*i-m-1)/2总是大于等于1，小于等于n-1。这样的话就可以直接算了，并且方案数是1

当n-m为偶数的时候，后面那个和平方最优取值应该是0.25，此时A_i有两个最优取值，并且由于i每次增大1，所以A_i取较大的那个，而A_i-1取较小的那个的时候也不会违反假设。所以答案还是可以直接算，然后方案数是2^m，这个快速幂一下就好了

为了能过我们还要优化一下，前面那个m个常数的和平方是可以化简的，化简成：(3n²m-3m³-3m)/12

然后还有第一问是要用long double，输出用long long，后面的要取模。然后就没了

en窝不会LaTeX所以这些东西都看起来很丑请不要介意（好吧其实也没人看吧）

然后其实代码也很丑，这虽然是一般设定不过还是说一下好了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
#define M 1000000007
long double ans;ll t,n,m;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
ll Quick_Power(ll x,int y)
 {
 	ll z=1;
 	while (y)
 	 {
 	 	if (y&1) z=z*x%M;
 	 	y >>= 1;
 	 	x=x*x%M;
 	 }
 	return z;
 }
inline long double Calc(ll x)
 {return (x*x*x-3*x*x+2*x)/6;}
inline long double calc()
 {long double x=n,y=m;return (3*x*x*y+y*y*y-y)/12;}
inline void Solve1()
 {printf("%lld 1\n",(ll)(ans+0.5));}
inline void Solve2()
 {
 	ans+=0.25*m;
 	printf("%lld %lld\n",(ll)(ans+0.5),Quick_Power(2,m));
 }
int main()
 {
 	freopen("love.in","r",stdin);freopen("love.out","w",stdout);
 	t=Read();
 	while (t--)
 	 {
 	 	n=Read();m=Read();
 	 	if (n<m) swap(n,m);
 	 	ans=Calc(n+m)-Calc(n)-Calc(m);
 	 	ans-=calc();
 	 	if ((n-m)&1) Solve1();else Solve2();
 	 }
 	return 0;
 }

NOIP模拟题 2015.8.10 T2

题解：考场上面没想出来= =，其实是每次操作相当于在u+k,v这个格子放上1然后一直按杨辉三角往上推，于是ai,j,k代表第i行第j列这个数还要往下推k层，然后就直接递推了= =这样就是n^3的，时限只有2s还真是sxbk。

然后还get了一个东西（其实是语法没学好）unsigned int，这东西必须要用%u输入输出

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 505
unsigned int a[N][N][N];
int n,m,p;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
int main()
 {
 	freopen("num.in","r",stdin);freopen("num.out","w",stdout);
 	n=Read();m=Read();p=Read();
 	while (p--)
 	 {
 	 	int q=Read(),w=Read(),e=Read();
 	 	a[q+e][w][e]++;
 	 }
 	for (int i=n;i>=1;i--)
 	 for (int j=1;j<=m;j++)
 	  for (int k=0;k<=500;k++)
 	    a[i][j][k]+=a[i+1][j][k+1]+a[i][j-1][k+1];
 	for (int i=1;i<=n;i++)
 	 {
 	    for (int j=1;j<=m;j++)
 	      printf("%u ",a[i][j][0]);
 	    printf("\n");
 	 }
 	return 0;
 }

NOIP模拟题 2015.8.6 T3

输入格式：第一行一个n为操作数，后面n行每行一个字符串和一个数x，前面为add时就是加进来x，del则为减去x，否则是查询x

输出格式：对于每个cnt输出一行答案

Sample Input:

add 11

cnt 15

add 4

add 0

cnt 6

del 4

cnt 15

Sample Output:

题解：这场好像水了前两题然后这题想着想着就睡着了= =

可以分块操作，设a[pre][suf]代表集合中前八个二进制位是pre而后八个与suf与运算不变的数个数。然后枚举子集什么的就可以做到插入删除查找都是sqrt(n)的了。然而这题被大爷暴力怒A了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 256
int s[N][N],t;char b[20];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
int main()
 {
 	freopen("subset.in","r",stdin);
 	freopen("subset.out","w",stdout);
 	t=Read();
 	while (t--)
 	 {
 	 	scanf("%s",b);int w=Read();
 	 	if (b[0]!='c')
 	 	 {
 	 	 	int e=b[0]=='d'?-1:1,l=w >> 8,k=N-(w&(N-1))-1;
 	 	 	for (int i=k;i;i=(i-1)&k) s[l][N-i-1]+=e;
 	 	 	s[l][N-1]+=e;
 	 	 }else
 	 	 {
 	 	 	int l=w >> 8,k=w%N,e=s[0][k];
 	 	 	for (int i=l;i;i=(i-1)&l) e+=s[i][k];
 	 	    printf("%d\n",e);
 	 	 }
 	 }
 	return 0;
 }

NOIP模拟题 2015.8.2 T1

题解：考场上面感觉这就是个容斥，于是一直在推式子，一直推到考试结束= =后来讲题才知道这是个DP，设ai,j代表第i轮那个人选数后gcd变成j的概率，然后用j和所有数做一次gcd，然后就可以转移了，但是其中有i个gcd为j的不能转移。然后第二问就可以直接SG搞了，复杂度n^2m

P.S.不知道为毛用SmartC++调试了一下之后代码在sublime里面就不能看了= =

后来手动加空格总算是好了些了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 305
#define M 1050
int n,m,sg[N][M],g[M][M],v[N],b[M],st=0;double s[N][M],ans=0;
inline int Read()
 {
    int x=0;char y;
    do y=getchar(); while (y<'0'||y>'9');
    do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
    return x;
 }
int gcd(int x,int y)
 {
    if (g[x][y])
     return g[x][y];else
       return g[x][y]=(y?gcd(y,x%y):x);
 }
void Down(int x,int y)
 {
    if (!s[x][y]) return;
    int w=0,e=0;double q=s[x][y]/(n-x);
    for (int i=1;i<=n;i++)
     {
      	e=gcd(y,v[i]);
      	if (e==y) w++;else
         if (e!=1) s[x+1][e]+=q;else
           ans+=(x&1)*q;
     }
    s[x+1][y]+=q*(w-x);
 }
void Solve(int x,int y)
 {
    if (!s[x][y]) return;
    int k=0;st++;
    for (int i=1;i<=n;i++)
     {
        if (g[y][v[i]]==y) k++;else
     	  if (g[y][v[i]]!=1) b[sg[x+1][g[y][v[i]]]]=st;
     }
    if (k!=x) b[sg[x+1][y]]=st;
    for (int i=0;i<=n;i++)
     if (b[i]!=st) {sg[x][y]=i;return;}
 }
int main()
 {
    freopen("game.in","r",stdin);freopen("game.out","w",stdout);
    n=Read();
    for (int i=1;i<=n;i++) v[i]=Read();
    s[0][0]=1;Down(0,0);
    for (int i=1;i<n;i++)
     for (int j=1;j<=1000;j++)
       Down(i,j);
    if (n&1)
     for (int i=1;i<=1000;i++) ans+=s[n][i];
    printf("%.9lf ",ans);
    for (int i=n;i>0;i--)
     for (int j=1000;j>=1;j--)
       Solve(i,j);Solve(0,0);
    if (sg[0][0]) puts("1.000000000");else
      puts("0.000000000");
    return 0;
 }

« 上一页 1 2 3 4 5 6 7 8 9 下一页 »

HJWJBSR's Blog

NOIP模拟题 2015.8.10 T3

NOIP模拟题 2015.8.9 T3

NOIP模拟题 2015.8.10 T2

NOIP模拟题 2015.8.6 T3

NOIP模拟题 2015.8.2 T1

HJWJBSR

分类

最新评论

最新留言

Music

链接

RSS

功能