NOIP模拟题 2015.8.16 T3
题解：考场上面肉眼感觉这题可以用线段树或者平衡树，但是很关键的问题就是打标记怎么打，我还naive以为这里的T2车跟一般的修改标记没什么很大区别，一般都可以先修改后加减，修改的时候把子树的加减标记也同时改变就不会有问题。但是这里的仔细想想两个操作都是会互相造成影响的，按上面那样打标记是会出现问题的。不过由于输出只有一个数并且数据还是比较良心还算骗到了50分。比暴力还是好点。后来看题解好像要用分块，并且在块上打了四个标记，标程也非常蛋疼，反正并没有看懂= =。而且题解里面还抽逼说什么维护的东西太多线段树是打不了这个的标记的，但是其实线段树平衡树相关还是可以维护这些的。维护的标记不变，但是顺序改为一个节点先下传加减再修改，下传加减的时候把子树的修改加减标记同时修改就可以了，脑补感觉是对的（你是想在我的博客里面找证明这种东西么【斜眼*ei】），而且也过了这道题= =
我是用splay写的，反正每次就暴力找已经废掉的节点删掉，这是n log n的，不过貌似线段树写也差不多的样子，但是好像由于不能删节点好像还要多打点标记的说
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define INF 0x7f7f7f7f
#define m3(x,y,z) min(min(x,y),z)
int c[N][2],fa[N],gf,mi[N],ad[N],xg[N],n,m;
int t[N],sum[N],li[N],ri,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;
}
inline void Update(int x)
{
mi[x]=m3(t[x],mi[c[x][0]],mi[c[x][1]]);
sum[x]=sum[c[x][0]]+sum[c[x][1]]+1;
}
int Set_up(int x,int y)
{
if (x>y) return 0;
int i=x + y >> 1,j=!i?n+2:i;
mi[j]=t[j];sum[j]=1;
if (x==y) return j;
c[j][0]=Set_up(x,i-1);c[j][1]=Set_up(i+1,y);
fa[c[j][0]]=j;fa[c[j][1]]=j;
Update(j);return j;
}
inline void xgj(int x)
{
if (!x||!xg[x]) return;
t[x]=max(t[x],xg[x]);xg[c[x][0]]=max(xg[c[x][0]],xg[x]);
xg[c[x][1]]=max(xg[c[x][1]],xg[x]);
mi[x]=max(mi[x],xg[x]);xg[x]=0;
}
inline void adj(int x)
{
if (xg[c[x][0]]) xg[c[x][0]]+=ad[x];
if (xg[c[x][1]]) xg[c[x][1]]+=ad[x];
if (!x||!ad[x]) return;
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];
mi[x]+=ad[x];ad[x]=0;
}
void Rotate(int x)
{
int i=fa[x],j=fa[i],k=c[i][0]==x;
if (j) c[j][c[j][1]==i]=x;else gf=x;
if (c[x][k]) fa[c[x][k]]=i;
c[i][!k]=c[x][k];fa[i]=x;
c[x][k]=i;fa[x]=j;
Update(i);
return;
}
inline void Down(int x)
{adj(x);xgj(x);}
void Up(int x)
{if (fa[x]) Up(fa[x]);Down(x);Down(c[x][0]);Down(c[x][1]);}
void Splay(int x)
{
Up(x);
while (fa[x])
{
if (fa[fa[x]])
Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]);
Rotate(x);
}
Update(x);
return;
}
int Fdown(int x,int y)
{
if (!x) return 0;int k;
if (x==n+2||x<y) {k=Fdown(c[x][1],y);return k?k:x;}
else return Fdown(c[x][0],y);
}
int Fup(int x,int y)
{
if (!x) return 0;int k;
if (x!=n+2&&x>y) {k=Fup(c[x][0],y);return k?k:x;}
else return Fup(c[x][1],y);
}
void Form(int x,int y)
{
int k=Fdown(gf,x),l=Fup(gf,y);
Splay(l);fa[c[l][0]]=0;
Splay(k);Update(gf=fa[c[l][0]=k]=l);
}
void FIT(int x)
{
Down(x);
if (mi[x]>0) return;
if (t[x]<=0) li[++ri]=x;
FIT(c[x][0]);FIT(c[x][1]);
}
inline int Delete(int x)
{
while (c[x][0]||c[x][1]) Rotate(c[x][0]?c[x][0]:c[x][1]);
c[fa[x]][c[fa[x]][1]==x]=0;return fa[x];
}
void up(int x)
{
Down(c[x][0]);Down(c[x][1]);Update(x);
if (fa[x]) up(fa[x]);
}
int main()
{
freopen("road.in","r",stdin);freopen("road.out","w",stdout);
n=Read();m=Read();
for (int k=Read(),i=1;i<=n;i++) t[i]=k;mi[0]=INF;
gf=Set_up(0,n+1);fa[0]=c[0][0]=c[0][1]=0;
while (m--)
{
int k=Read(),q=Read(),w=Read(),e=Read();
if (k==1)
{
Form(q,w);
if (sum[c[c[gf][0]][1]]!=w-q+1) continue;
ad[c[c[gf][0]][1]]=-e;adj(c[c[gf][0]][1]);
if (mi[c[c[gf][0]][1]]<=0) FIT(c[c[gf][0]][1]);
Update(c[gf][0]);Update(gf);ans++;
while (ri--) up(Delete(li[ri+1]));ri++;
} else
if (k==2)
{
Form(q,w);
ad[c[c[gf][0]][1]]=e;adj(c[c[gf][0]][1]);
Update(c[gf][0]);Update(gf);
} else
{
Form(q,w);
xg[c[c[gf][0]][1]]=e;xgj(c[c[gf][0]][1]);
Update(c[gf][0]);Update(gf);
}
}
cout <<ans<<endl;
return 0;
}
NOIP模拟题 2015.8.10 T3
Day10考的时候T1很快就水完了，T2早早弃疗，反正有70分暴力，T3怎么看怎么像SB题，于是考前1h就检查完不管了
不过有人质疑了T3题意，我才发现我TM也看错了。
题解：
所以做这道题只有半个+h，很明显看得出这是树状数组搞一搞就可以了，但是卧榻马并不会这种东西= =，一般都是用线段树。于是本来还打算临时推一下怎么搞这个东西。然后发现其实线段树就可以搞了。首先建一棵有2k个节点的线段树，每次染色就是直接区间加值，每次询问节点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:
题解：做这套题睡了2h+，所以考的比较hehe，当然就算再给我2h+我也不一定做得出这个题。
这道题喜闻乐见的要推式子：
定义Sn代表n个人两两颜色相异的时候的答案，通过计算可得Sn=(n3-3*n2+2n)/6
先设n>=m，然后将考虑将m个黑球插进来，定义Ai代表第i个黑球插到了第Ai个白球的的后面，我们假设Ai单调不减
简单容斥可得：ans=Sn+m-Sn-Sm-所有的黑球对所有的白球对的贡献-所有的白球对所有的黑球对的贡献，
倒数第二个东西就是Σi=1 to m Ai*(n-Ai)
最后一个东西就是Σi=1 to m-1 Σj=i+1 to m Aj-Ai-1，然后这东西明显是可以拆出来的
最后两个东西相加得到：Σi=1 to m (n-2*i-m-1)2-[Ai-(n+2*i-m-1)/2]2
这东西系数是负的，所以后面那个和平方要最小。
所以我们分类讨论当n-m为奇数，Ai后面那个东西总是能取到0，因为(n+2*i-m-1)/2总是大于等于1，小于等于n-1。这样的话就可以直接算了，并且方案数是1
当n-m为偶数的时候，后面那个和平方最优取值应该是0.25，此时Ai有两个最优取值，并且由于i每次增大1，所以Ai取较大的那个，而Ai-1取较小的那个的时候也不会违反假设。所以答案还是可以直接算，然后方案数是2m，这个快速幂一下就好了
为了能过我们还要优化一下，前面那个m个常数的和平方是可以化简的，化简成：(3n2m-3m3-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:
题解：这场好像水了前两题然后这题想着想着就睡着了= =
可以分块操作，设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;
}
