停课第三天，距离NOIP2018还有10天。
愈发觉得时间的不够用了。
可能是膜多了.jpg
昨天金庸先生去世了。感慨良多。再看着QQ空间中折射出的周围人的打闹，又是一种强烈的不真实感。
昨天打了三场模拟赛，一场有一定难度，两场是信心赛——即便如此我也没有取得很好的成绩。比如说，一个字母打错了，之类的。
晚上做NOIP2017，时间复杂度确实是丧题，如果真实比赛我就凉了；逛公园非常难写，以至于我丧失信心放弃治疗。
我的应试能力有很大的欠缺。
lp1654 OSU!
真是棒到不行!OSU!
首先，我们可以知道，对于长度为\(x\)的线段，在其后加上一个新的长度为1的线段，新线段的价值是\((x+1)^3\)
那么，价值的差便是：
$$3*x^2+3*x+1$$
而这样的贡献必须要当前点被选中才可行的。似乎可以得到：
$$f_{i}=f_{i-1}*(1-p_{i})+(f_{i-1}^3+3*f_{i-1}^2+3*f_{i-1}+1)*p_{i}$$
但仔细观察就可以发现这样显然是错误的。
这是因为，平方的期望不等于期望的平方。
因此，对于平方的期望，以及一次方的期望，我们应当另外维护两个函数\(g,u\)，分别表示平方的期望和一次方的期望。
那么：
$$g_{i}=(g_{i-1}+2*u_{i-1}+1)*p_{i}$$
$$u_{i}=(u_{i-1}+1)*p_{i}$$
于是：
$$f_{i}=f_{i-1}+(3*g_{i-1}+3*u_{i-1}+1)*p_{i}$$
问题得解。
这一题还是很有思维难度的。
#include<iostream>
#include<cstdio>
using namespace std;
int n;
double p[100005],u[100005],g[100005],f[100005];
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lf",&p[i]);
}
u[0]=g[0]=f[0]=0;
double ans=0;
for(int i=1;i<=n;++i){
u[i]=(u[i-1]+1)*p[i];
g[i]=(g[i-1]+2*u[i-1]+1)*p[i];
f[i]=f[i-1]+(3*g[i-1]+3*u[i-1]+1)*p[i];
ans+=f[i];
}
printf("%.1lf",f[n]);
}
int main(){
init();
return 0;
}CF148D Bag of mice
看到\(w,b \le 1000\)，我们可以大胆猜想复杂度是\(w*b\)的（大雾）
那么我们设\(f[i][j]\)表示，包里还剩下\(i\)只白老鼠，\(j\)只黑老鼠的时候，轮到公主抽，赢的期望。
仔细看了看题意（之前题意看错了，瞎想半天，淦。），我们可以发现，公主输会发生在两种情况下：
一：包里没有白老鼠了；二：公主抽到了黑老鼠而龙抽到了白老鼠。
同时，对于一个局面，公主胜利的概率有两部分；
一：公主抽到了白球。二：公主的状态转移到的状态抽到了白球。
我们分类讨论。
首先，依据公主抽到白球的概率是\(\frac{i}{i+j}\)，我们可以知道：
$$f_{i,j}+=\frac{i}{i+j}$$
然后，用填表法，我们发现，公主抽到了黑老鼠且龙抽到黑老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}$$
在这种情况下，跑出一只白老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}$$
跑出一只黑老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
所以得到转移方程：
$$f_{i,j}=\frac{j}{i+j}*\frac{j-1}{i+j-1}+f_{i-1,j-2}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}+$$
$$f_{i,j-3}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
于是填表法可得解。
#include<iostream>
#include<cstdio>
using namespace std;
int w,b;
double f[1005][1005];
void init(){
scanf("%d%d",&w,&b);
for(int i=1;i<=w;++i){
for(int j=1;j<=b;++j){
f[i][j]=0;
}
}
for(int i=1;i<=w;++i){
f[i][0]=1;
}
for(int i=1;i<=b;++i){
f[0][i]=0;
}
for(int i=1;i<=w;++i){
for(int j=1;j<=b;++j){
f[i][j]+=(double)i/(i+j);
if(j>=2){
f[i][j]+=f[i-1][j-2]*(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2);
}
if(j>=3){
f[i][j]+=f[i][j-3]*(double)j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2);
}
}
}
printf("%.9lf",f[w][b]);
}
int main(){
init();
return 0;
}
sp1026 Favorite Dice
开始学习期望DP。
这是一道期望DP入门题。
首先我们设\(f[i]\)表示，已经取了\(i\)种数，距离取完的期望回合数。
根据概率的基本定理，我们可以知道，已经取了\(k\)种以后，下一种取到的是未取到过的概率是\(\frac{n-k}{n} \)；而取到的是取过的概率是\(\frac{k}{n}\)
我们很容易可以知道，已经取了\(i\)种数，下一次取可能有两种情况：
一：取到的是一种新的数。
二：取到的是已经取到过的数。
但无论如何都要再取一次才有造成状态改变的空间。
故而我们得到方程：
$$ f_{i}=\frac{n-i}{n}*f_{i+1}+\frac{i}{n}*f_{i}+1 $$
即：
$$ n*f_{i}=(n-i)*f_{i+1}+i*f_{i}+n $$
从而得到：
$$ f_{i}=\frac{(n-i)*f_{i+1}+n}{n-i} $$
等价于：
$$ f_{i}=f_{i+1}+\frac{n}{n-i} $$
于是我们得到了逆向的递推方程。
然后是边界条件。很显然，\(f_{n}=0\)，这是因为，已经取到\(n\)种以后，就意味着已经取完了。
#include<iostream>
#include<cstdio>
using namespace std;
double f[1005];
int n;
void init(){
scanf("%d",&n);
f[n]=0;
for(int i=n-1;i>=0;--i){
f[i]=f[i+1]+(double)n/(n-i);
}
printf("%.2lf\n",f[0]);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}
停课第二天。
停课第二天，距离NOIP2018还有11天。
停课的喜悦感弱了很多。
对可能取得的成绩充满担忧。
今天做了什么事呢？
打了两场校内模拟赛。赛中做出的有3题。事实上还有一题也写了正解，但是没写特判被叉成10分。难受。（凉心出题人）
然后是学了一下基础的概率与期望。
收获有，但没有想象中那么大。
lp2161 SHOI2009 会场预约
这一题据说被放在了线段树这个模块下面。
我想了很久很久。想到了一种做法。但是一写就感觉很麻。
想着想着，算了一下复杂度，然后大喊一声，MADE！
仔细一想，询问2E5，值域1E5。大力上分块啊，\(O(Nsqrt(M))\approx 6E7\)不满。搞什么线段树啊，真是的。
好的，那么大力上分块。
具体应该要怎么分块呢？
对于每一块，我们定义一种标记。
如果标记是0，说明这个块是空的，那么就可以直接修改；
如果标记是一个正整数，说明这个块被该正整数完全包含，也可以直接修改，并将该标记指的数放入删除集合；
如果标记是-1，说明这个块里面包含多个询问。此时同样暴力修改。
为什么这样做的复杂度是对的呢？首先，如果一个块，如果它包含多个询问，那么要么它包含的是整个询问，要么它包含的是询问的一段。
因此，对于一个询问，它最多只可能被暴力修改两次。
所以这种做法是可行的。
不过分块写起来还是挺麻的。调了半天没调出来，然后看到了一个神仙做法，就抄过来了：
具体来说，就是把Set当作红黑树用。
太猛了。
#include<cmath>
#include
#include
#include<cstring>
#include<set>
using namespace std;
#define MAXN 100000
int n;
struct data{
int l,r;
bool operator <(const data &A)const{
return (this->l==A.l)?(this->l<A.r):(this->l<A.l);
}
};
set<data> st;
void init(){
scanf("%d",&n);
char ch[5];
int l,r,ans;
for(int i=1;i<=n;++i){
cin>>ch;
if(ch[0]=='B'){
printf("%lld\n",st.size());
}else{
scanf("%d%d",&l,&r);
data X=(data){l,r};
ans=0;
set<data>::iterator it=st.lower_bound(X);
while(1){
it=st.lower_bound(X);
if(it->l<=X.r&&X.l<=it->r){
++ans;
st.erase(it);
continue;
}
it=st.lower_bound(X);
if(it!=st.begin()){
--it;
if(it->l<=X.r&&X.l<=it->r){
++ans;
st.erase(it);
continue;
}
}
break;
}
st.insert(X);
printf("%d\n",ans);
}
}
}
int main(){
init();
return 0;
}
//大力分块的假做法，直到现在都不懂bug在哪里。第k块表示k*blck~(k+1)*blck-1的值。
int n,cnt=0,blck,L[200005],R[200005],rst,TOP;
int V[317],v[100005];
char ch[4];
bool bo[200005];
inline void prpr(){
blck=sqrt(MAXN);
rst=MAXN%blck;
TOP=MAXN-rst;
memset(V,0,sizeof(V));
memset(v,0,sizeof(v));
memset(bo,0,sizeof(bo));
}
int rt=0;
inline void delB(const int &l,const int &r,const int &x){
for(int i=l;i<=r;++i){
if(V[i]==x){
V[i]=0;
}
}
}
inline void delb(const int &l,const int &r,const int &x){
for(int i=l;i<=r;++i){
if(v[i]==x){
v[i]=0;
}
}
}
inline void del(const int &x){
bo[x]=0;
++rt;--cnt;
int l=L[x],r=R[x];
if(r/blck-1<(l/blck+1)){
delb(l,r,x);
return;
}
delB(l/blck+1,r/blck-1,x);
delb(l,(l/blck+1)*blck-1,x),delb((r/blck)*blck,r,x);
}
inline void addb(const int &l,const int &r,const int &x){
for(int i=l;i<=r;++i){
if(V[i/blck]!=x){
V[i/blck]=-1;
}
if(!bo[v[i]]){
v[i]=x;
}else{
del(v[i]);
v[i]=x;
}
}
}
inline void clr(const int &x){
for(int i=x*blck;i<(x+1)*blck;++i){
if(bo[v[i]]){
del(v[i]);
}
}
}
inline void addB(const int &l,const int &r,const int &x){
for(int i=l;i<=r;++i){
if(!V[i]){
V[i]=x;
}else if(V[i]>0){
if(bo[V[i]]){
del(V[i]);
}
V[i]=x;
}else{
clr(i);
V[i]=x;
}
}
}
inline int add(const int &l,const int &r,const int &x){
rt=0;
if(r/blck-1<(l/blck+1)){
addb(l,r,x);
return rt;
}
addB(l/blck+1,r/blck-1,x);
addb(l,(l/blck+1)*blck-1,x),addb((r/blck)*blck,r,x);
return rt;
}
void init(){
prpr();
scanf("%d",&n);
int l,r;
for(int i=1;i<=n;++i){
cin>>ch;
if(ch[0]=='B'){
printf("%d\n",cnt);
}else{
bo[i]=1;++cnt;
scanf("%d%d",&l,&r);
printf("%d\n",add(l-1,r-1,i));
L[i]=l-1,R[i]=r-1;
}
}
}
int main(){
init();
return 0;
}
停课了。
停课第一天，距离NOIP2018还有12天。
复赛的压力依然很大，不过却又轻松了一些，大抵是不用两头顾之故吧。
翘作业真爽.jpg
那么，停课的今天，做了哪些事呢？
首先是打了两场校内模拟赛。大概是做出了三题半吧。主要是第二场是个大水赛，但即便如此大水赛我也没有AK，甚至矩阵加速没推出来。
第一场非常的麻。考了一道题答题，驱使我现场学Python（读音问题还被笑了），而期望DP依然是我的薄弱点，我甚至只能无穷等比缩放数列求和然后上一个极限来得30分——当然最后FE了。
自己做的题倒没有多少。一是巩固了博弈论，二是尝试写了一个数据结构麻题。我看到题目第一眼想到的是线段树（事实上就是为了学线段树才写这一题的），但是想了想觉得分块似乎更好写（当我没说）一点。然后就调了半个晚上。然后百度一下看到了一个神仙做法，就是直接上stl::set，然后用set的红黑树结构来当作平衡树用，然后只要短短四十行就能写完。
所以本质上我是用平衡树A了这一题，尽管是STL的。
lp2197 NIM游戏
图文无关，因为空和白玩的游戏中没有一个是ICG类的。
NIM游戏是一类经典的博弈论题目。
众所周知，NIM游戏的结果就是把所有的答案异或起来即可。为什么可以这么做呢？
我们定义，对于一个「均衡组合博弈（ICG）」 ，我们定义两种局面状态：P（先手必败）和N（先手必胜）。
首先我们可以知道，在ICG中，博弈是一定会终止的；同时，终止局面是P局面。如果说一个局面的所有子局面都是N局面或者P局面，那么这个局面也一定是N局面或者P局面：这是因为N局面和P局面存在性质：
一个局面是P局面，当且仅当它的所有子局面都是N局面；一个局面是N局面，当且仅当它的所有子局面中存在一个是P局面。
这也就意味着，对于任何一种状态，我们都可以判定它是N状态还是P状态。
那么，初始状态的N-P性是可以判断的。
如何计算一个局面的N-P性呢？
我们定义一种运算，使得：
P局面经过这种运算只能变成N局面；
N局面经过这种运算可以变成P局面。
当我们用一个数列描述一个局面后，我们惊讶地发现：异或——这里指的是将局面中的每一个子部分异或起来——是满足这个性质的。
我们定义，异或值为零的局面是必败局面；异或值非0的局面是必胜局面。
我们将描述这个局面的数列异或起来，如果它等于零，那么任意一种「减少」操作——导致它的一个值减少的，一定会导向一种P局面；
而对于一种P局面，依据按位异或的特性，一定可以通过减少最大的数，来变更想变更的任意一位。
故而，我们发现，对于任意一种局面，我们可以用异或运算来判断它的N-P性。
事实上，两者之间并不存在那么直接的数学上的对应关系。可以将NIM游戏理解为一个数学模型。
这是一种指代关系。换句话说，为了更方便地处理它，
我们可以将这个局面转化为数学模型，而异或运算刚好满足其性质——这并不是说异或运算本身就是这个局面的变化。
当理解这一点之后，异或的意义就很显然了。
#include<iostream>
#include<cstdio>
using namespace std;
int n,a[10005];
void init(){
scanf("%d",&n);
int x=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
x^=a[i];
}
if(x){
puts("Yes");
}else{
puts("No");
}
return;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}
Lucas定理
首先给出关于Lucas定理的简要证明：
定义：
$$ a=a_{k}*p^{k}+a_{k-1}*p^{k-1}+…+a_{1}*p+a_{0}=\sum_{i=1}^{k}a_{i}^p{i} $$
$$ b=b_{k}*p^{k}+b_{k-1}*b^{k-1}+…+b_{1}*p+b_{0}=\sum_{i=1}^{k}b_{i}^p{i} $$
求证：
$$ C_{a}^{b}=C_{a_{k}}^{b_{k}}*C_{a_{k-1}}^{b_{k-1}}…C_{a_{0}}^{b_{0}} $$
首先我们证明引理一：
$$ (1+x)^p≡1+x^p\ (mod\ p) $$
根据组合数基本性质，我们有：
$$\forall j\in [1,p-1],C_{p}^{j}=\frac{p}{j}*C_{p-1}^{j-1}≡0(mod\ p) $$
$$∴(1+x)^p≡\sum_{i=1}^{p}C_{p}^{i}*x^i≡1+x^p(mod\ p) $$
于是我们得到结论：
$$(1+x)^a≡\prod_{i=1}^{k}(1+x)^{p^k*a_{k}}≡\prod_{i=1}^{k}(1+x^{p^{k}})^{a_{k}}(mod\ p)\ (1)$$
根据进制的基本性质和幂的基本性质，我们有：
$$b=\sum_{i=1}^{k}b_{i}^p{i},x^b=\prod_{i=1}^{k}x^{p^k*b_{i}}$$
并且我们知道，用上述方法表示\(p\)进制数，是完全等价的。即，两者的集合构成双射。
故而我们比较\((1)\)式展开后左右各项，可以得到：
$$\forall b\in [1,a],C_{a}^{b}≡\prod_{i=1}^{k}C_{a_{i}}^{b_{i}}(mod\ p)$$
证毕。
故而对于实际处理问题，只需要逆向秦九韶即可。
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,p,inv[100005],fac[100005];
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
//y取x
inline long long C0(long long x,long long y){
return ((x>y)?0:(x?fac[y]*inv[x]*inv[y-x]%p:1))%p;
}
//模p意义下的y取x
inline long long C(long long x,long long y){
return ((x>y)?0:((y>=p)?C(x/p,y/p)*C0(x%p,y%p):C0(x%p,y%p)))%p;
}
void init(){
scanf("%lld%lld%lld",&n,&m,&p);
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<=p;++i){
fac[i]=fac[i-1]*i%p;
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=2;i<=p;++i){
inv[i]*=inv[i-1];
inv[i]%=p;
}
printf("%lld\n",C(n,n+m)%p);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}
CF1073
CF1073A
一道水题。
首先从题意可知，当连续两个字符不同的时候，这样的字符串就是合法的。
所以找第一组两个不同的字符即可。
CF1073B
没什么好说的，依照题意大力模拟即可。
CF1073C
有一定难度的水题，但是我考场上没 调 出 来！
其实很容易可以想到，因为当长度为\(len\)的可行，长度为\(len+1\)的也一定可行。
所以考虑二分答案。
如何检验呢？其实就是将一连串的移动移除了，然后考虑它前面的部分加上后面的部分，再加上长度为len的移动序列，要怎样才能走到终点。
因此我们可以预处理曼哈顿距离前缀和。于是可以\(O(1)\)检验。
这题就做完了。
但是，我调了一个多小时——
因为我的Abs函数写挂了！！！！！
于是就从开心上分场变成了掉分场。
缺省源能写挂也是很厉害。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073A
*/
int n;
char ch[1005];
inline void pt(const char &a,const char &b){
puts("YES");
putchar(b),putchar(a);
}
void init(){
scanf("%d",&n);
cin>>ch;
int nw=0;
for(int i=0;i<n;++i){
if(!i){
nw=ch[i];
}
if(ch[i]!=nw){
pt(ch[i],nw);
return;
}
}
puts("NO");
}
int main(){
init();
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073B
*/
int n,a[200005],b[200005];
bool bckt[200005];
priority_queue< int,vector<int>,greater<int> > q;
void init(){
scanf("%d",&n);
memset(bckt,0,sizeof(bckt));
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int cnt=0,p=1;
for(int i=1;i<=n;++i){
scanf("%d",&b[i]);
cnt=0;
if(bckt[b[i]]){
printf("0 ");
continue;
}
while(a[p]!=b[i]&&p<=n){
bckt[a[p]]=1;
++cnt;
++p;
}
if(a[p]==b[i]){
bckt[a[p]]=1;
++cnt;
++p;
}
printf("%d ",cnt);
}
}
int main(){
init();
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073C
有一定难度的水题，但是我考场上没 调 出 来！
其实很容易可以想到，因为当长度为$lated len$的可行，长度为\(len+1\)的也一定可行。
所以考虑二分答案。
如何检验呢？其实就是将一连串的移动移除了，然后考虑它前面的部分加上后面的部分，再加上长度为len的移动序列，要怎样才能走到终点。
因此我们可以预处理曼哈顿距离前缀和。于是可以\(O(1)\)检验。
这题就做完了。
但是，我调了一个多小时——
因为我的Abs函数写挂了！！！！！
于是就从开心上分场变成了掉分场。
缺省源能写挂也是很厉害。
*/
int n;
char ch[200005];
int X,Y,smx[200005],smy[200005];
inline bool cckk(const int &s,const int &t,const int &len){
int dx=X-(smx[n]-smx[t])-smx[s-1],dy=Y-(smy[n]-smy[t])-smy[s-1];
if(((dx+dy)&1)!=(len&1)){
return 0;
}
if((Abs(dx)+Abs(dy)>len)){
return 0;
}
return 1;
}
inline bool chck(const int &len){
for(int i=1;i-1+len<=n;++i){
if(cckk(i,i+len-1,len)){
return 1;
}
}
return 0;
}
void init(){
scanf("%d",&n);
cin>>ch+1;
scanf("%d%d",&X,&Y);
smx[0]=smy[0]=0;
for(int i=1;i<=n;++i){
if(ch[i]=='U'){
smy[i]=smy[i-1]+1;
smx[i]=smx[i-1];
}else if(ch[i]=='D'){
smy[i]=smy[i-1]-1;
smx[i]=smx[i-1];
}else if(ch[i]=='L'){
smx[i]=smx[i-1]-1;
smy[i]=smy[i-1];
}else if(ch[i]=='R'){
smx[i]=smx[i-1]+1;
smy[i]=smy[i-1];
}
}
int l=0,r=n+1,mid;
while(l<r){
mid=(l+r)>>1;
if(chck(mid)){
r=mid;
}else{
l=mid+1;
}
}
if(l>n){
puts("-1");
}else{
printf("%d",l);
}
}
int main(){
init();
return 0;
}
lp1290 欧几里德的游戏
这是一道基础的复杂博弈论题——我到现在都不是很能理解。
其实我也不太懂SG函数，我就口chao胡xi一下这题的做法吧。
对于\(x,y st: x<y\)，我们定义对于x,y的SG函数SG(S)，其中S是一个局面。 我们定义关于一个局面S的后继S’，使得S’可以从S转移得到。 所以我们定义一个集合T，包含了局面S的所有后继的SG值。 对于必败局面，我们令它的SG值为0，否则为1。 则\(SG(S)=mex(T)\)，其中mex表示最小的不在集合中的非负整数。 所以， $$SG(x,y)=mex(SG(x,y-x),SG(x,y-2*x),$$
$$SG(x,y-3*x)…SG(x,y%x))$$ 我们又知道，对于其中的每一个SG函数，递推式都是成立的。 所以事实上，当\(x/y>1时，SG(x,y)=1\)，这是因为当\(x/y==1\)始终是等于\(!(SG(y%x,x))\)
所以事实上\(SG(x,y)\)只取决于\(SG(x,y%x)\)的值。
#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int a,b;
inline bool SG(int x,int y){
if(!x){
return 0;
}
if(y/x==1){
return !SG(y%x,x);
}else{
return 1;
}
}
void init(){
scanf("%d%d",&a,&b);
bool bo=SG(Min(a,b),Max(a,b));
if(bo){
puts("Stan wins");
}else{
puts("Ollie wins");
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}
NOIP2018 考场信息公布
NOIP2018 考场信息公布了，我好像是在本校考。主场作战到底是优势还是劣势呢？
lp1288 取数游戏
事实上这是一道结论题。
首先，如果双方足够聪明，那么他们都不会回头。
这是因为，如果先手方往一个方向走，在背后留下了一个必败局面，那么后手方一定不会回头。
而如果先手方往一个方向走，在背后留下了一个必胜局面，那么他一定会选择破坏了这条边。
所以游戏必然成是链。
我们首先考虑边数为2的情况。此时先手必胜，这是因为如果先手足够聪明，那么他一定会选择把这整条边拿掉。此时后手输了。
而，对于边数是3的情况，先手必败。这是因为，先手无论取任何数，都会使得情况转化为边数为2的情况，那么后手可以走一步然后断绝通向必胜局面的路。
故而我们得知，如果起始点的两端有一条链的边数为偶，则先手必胜；否则后手必胜。
#include<iostream>
#include<cstdio>
using namespace std;
int n,a[20];
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i){
if(!a[i]){
if(!(i&1)){
puts("YES");
return;
}
break;
}
}
for(int i=1;i<=n;++i){
if(!a[n-i+1]){
if(!(i&1)){
puts("YES");
return;
}
break;
}
}
puts("NO");
return;
}
int main(){
init();
return 0;
}
lp1199 NOIP2009 三国游戏
首先我们定义最优配对：最优配对指的是，对于一个武将而言，与他默契值最高的武将。
其次我们定义次优配对，次优配对指的是，对于一个武将而言，与他默契值次高的武将。
那么我们知道，无论如何，人类能够选取的一定只能是一组次优配对，而不可能是一组最优配对。
当然人类一定可以取到次优配对中的最大值。这是因为电脑的操作一定会用于破坏人类取到最优配对，因此取到次优配对一定是可能的。
如果人类想要胜利，就必须防止电脑取到最优配对中比次优配对最大值更大的那些值。我们定义这样的值为「危险值」
如果危险值存在，那么组成它的两个部分一定都互为最优配对：证明如下。
如果组成危险值的两个部分不互为最优配对，那么危险值一定是两者中一者关于另一者的最优配对。
我们不妨设定甲武将是乙的最优配对，该配对是危险值，那么乙武将必须存在一个最优配对，使得该配对的值大于危险值。
这时候乙武将的次优配对一定大于等于危险值，但是这与危险值的定义矛盾。所以组成危险值的两个部分一定互为最优配对。
故而，我们发现，危险值一定是一种最优配对。
那么，当我们优先取得足以构成次优配对中的最大值的两个武将以后，电脑已经控制的一个武将总是不能构成危险值。
这是因为组成危险值的两个武将一定互为最优配对，而电脑已经控制的仅为其中的一个武将，并且与该武将构成最优配对的武将控制在玩家手中。
当游戏进行三步时，玩家已经控制了次优配对中的最大值，并且电脑不控制任何危险值，此时可以将游戏转化为
「电脑先手且必须控制危险值」的情况。
由于危险值总是需要由一组互为最优配对的武将构成，容易证明无论电脑如何选择，玩家都可以破坏危险值的构成。
因此，总是有解，且解总为次优配对中的最大值。
当然这一题还有一个实现难点在于读入，这里就不再细说。
#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
/*
lp1199 三国游戏
*/
int n,f[505][505];
void init(){
scanf("%d",&n);
int mx,lmx,ans=0,x;
for(int i=1;i<n;++i){
for(int j=i+1;j<=n;++j){
scanf("%d",&f[i][j]);
f[j][i]=f[i][j];
}
}
/*
for(int i=1;i<n;++i){
for(int j=1;j<n;++j){
printf("%d ",f[i][j]);
}
puts("");
}
*/
for(int i=1;i<=n;++i){
mx=0,lmx=0;
for(int j=1;j<=n;++j){
x=f[i][j];
if(mx<x){
lmx=mx;
mx=x;
}else{
lmx=Max(lmx,x);
}
}
ans=Max(ans,lmx);
}
puts("1");
printf("%d",ans);
}
int main(){
init();
return 0;
}
你本该做的事。
准备掉分。
过于真实。
CF1072
CF1072A
一道简单题。
可以不断地切割成子问题。
然后统计计算即可。
CF1072B
一道猜结论题。
我们猜测，对于\([0,3]\)当\(t_i\)确定的时候，\(t_i | t_{i+1}==a_i\)与\(t_i \& t_{i+1}==b_i\)可以推导出唯一确定的\(t_{i+1}\)
证明很复杂，但是正确性很显然。
那么依据这个结论，可以简单\(DFS\)，从而得出结果。
CF1072C
一道复杂题。
它再一次警醒了我——
你tm不会二分。
做法很显然，因为答案显然具有单调性，所以二分\(k\)，然后\(O(n)\)检验即可。
检验的时候贪心地排布即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072A
*/
int w,h,k;
void init(){
int ans=0;
scanf("%d%d%d",&w,&h,&k);
while(k){
ans+=((w<<1)+(h<<1)-4);
--k;
h-=4,w-=4;
}
printf("%d",ans);
}
int main(){
init();
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072B
*/
int n,a[100005],b[100005],t[100005];
void init(){
scanf("%d",&n);
for(int i=1;i<n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<n;++i){
scanf("%d",&b[i]);
}
for(int i=0;i<=4;++i){
if(i==4){
puts("NO");
return;
}
t[1]=i;
for(int j=1;j<n;++j){
for(int k=0;k<=4;++k){
if(k==4){
goto loop;
}
if((t[j]|k)==a[j]&&(t[j]&k)==b[j]){
t[j+1]=k;
break;
}
}
if(j==n-1){
puts("YES");
for(int i=1;i<=n;++i){
printf("%d ",t[i]);
}
return;
}
}
loop:;
}
}
int main(){
init();
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072C
*/
bool bo[100005];
int a,b,at,bt,al[50005],bl[50005];
inline bool chck(int k){
memset(bo,0,sizeof(bo));
int nw=k,att=0,btt=0;
at=0,bt=0;
while(nw){
if(att+nw<=a){
att+=nw;
bo[nw]=1;
al[at++]=nw;
}
--nw;
}
nw=k;
while(nw){
if((!bo[nw])&&(btt+nw<=b)){
btt+=nw;
bo[nw]=1;
bl[bt++]=nw;
}
--nw;
}
for(int i=1;i<=k;++i){
if(!bo[i]){
return 0;
}
}
return 1;
}
void init(){
scanf("%d%d",&a,&b);
int l=0,r=100000,mid,ans=0;
while(l<=r){
mid=((l+r)>>1);
if(chck(mid)){
ans=Max(ans,mid);
l=mid+1;
}else{
r=mid-1;
}
}
chck(ans);
printf("%d\n",at);
for(int i=0;i<at;++i){
printf("%d ",al[i]);
}
puts("");
printf("%d\n",bt);
for(int i=0;i<bt;++i){
printf("%d ",bl[i]);
}
puts("");
}
int main(){
init();
return 0;
}
我好菜啊。
校内模拟赛被学弟爆踩。
lp1792 国家集训队 种树
首先拿到题面很容易可以想到的是状压DP，状态转移方程很容易可以推出来。
但是这么做的复杂度是\(O(n^2)\)的，只能拿到50分。
我们深入地考虑这一题的性质，我们发现，对于这个环，如果取用了上面的某一个点，那么这个点的两个邻点都不可取。
贪心地依据权值从大到小考虑，如果一个点的两个邻点加起来都不如它大的话，那么取邻点中的任意一个都不如取这个点。
如果这个点的两个邻点加一起比它大，那就考虑两种情况，一种情况是选择这个点，一种情况是选择这个点的两个邻点。
（很容易可以知道，如果两个邻点只选一个，那是一定没有选这个点优的。）
我们考虑先取了这个点，再转变为取这个点的两个邻点的情况。这种情况下，总权值就会减去这个点的权值，并且加上这个点的两个邻点的权值。
我们考虑一个有趣的性质。如果一个点的两个邻点都选取了，那么影响到的“不可被选取区域”的大小，是和三个都选是相同的。
因此，我们考虑究竟应该选取这个点还是这个点的两个邻点。我们考虑每当挖去一个点的时候，都把它的两个邻点标记为消失。
这时候对不可选取区域的影响已经确定了，因此只要确定对对权值的影响。
那么我们考虑建一个虚点，替代在贪心选取的那个点以及两个相邻的位置。这个虚点的权值相当于邻点的权值和减去原点的权值。
对于这个虚点，我们把它当做这个环上本来就存在的一个点来处理即可。
所以可以考虑用堆+双向链表来维护。
顺便提一句，这是一道三倍经验题，它的亲人们：
lp3620 APIO/CTSC2007 数据备份，lp1484 种树
前者只要差分一下，边转点，改大小判断以后的边界，再改一下单调队列；后者只要判一下负数情况。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,a[200005],l[200005],r[200005],nw,nw2;
bool ext[200005];
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
q.push((pii){a[i],i});
ext[i]=0;
}
if(m>(n>>1)){
puts("Error!");
return;
}
for(int i=2;i<=n;++i){
l[i]=i-1;
}
l[1]=n;
for(int i=1;i<n;++i){
r[i]=i+1;
}
r[n]=1;
long long ans=0;
for(int i=1;i<=m;++i){
while(!q.empty()&&ext[q.top().second]){
q.pop();
}
nw=q.top().second;
ans+=q.top().first;
ext[l[nw]]=1,ext[r[nw]]=1;
nw2=a[l[nw]]+a[r[nw]]-q.top().first;
a[nw]=nw2;
l[nw]=l[l[nw]],r[nw]=r[r[nw]];
r[l[nw]]=nw,l[r[nw]]=nw;
q.pop();
q.push((pii){nw2,nw});
}
printf("%lld",ans);
}
int main(){
init();
return 0;
}顺便贴一下后面两题的代码：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,a[500005],l[500005],r[500005],nw,nw2;
bool ext[500005];
//lp1484 种树
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
q.push((pii){a[i],i});
ext[i]=0;
}
if(m>(n>>1)){
puts("Error!");
return;
}
for(int i=1;i<=n;++i){
l[i]=i-1;
}
for(int i=1;i<=n;++i){
r[i]=i+1;
}
long long ans=0;
for(int i=1;i<=m;++i){
while(!q.empty()&&ext[q.top().second]){
q.pop();
}
if(q.top().first<0){
break;
}
nw=q.top().second;
ans+=q.top().first;
ext[l[nw]]=1,ext[r[nw]]=1;
nw2=a[l[nw]]+a[r[nw]]-q.top().first;
a[nw]=nw2;
l[nw]=l[l[nw]],r[nw]=r[r[nw]];
r[l[nw]]=nw,l[r[nw]]=nw;
q.pop();
q.push((pii){nw2,nw});
}
printf("%lld",ans);
}
int main(){
init();
return 0;
}#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m,a[100005],l[100005],r[100005],nw,nw2;
bool ext[100005];
//lp3620 APIOCTSC2007 数据备份
typedef pair<int,int> pii;
priority_queue< pii,vector<pii>,greater<pii> > q;
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
ext[i]=0;
}
for(int i=n;i>=1;--i){
a[i]-=a[i-1];
}
for(int i=1;i<n;++i){
a[i]=a[i+1];
q.push((pii){a[i],i});
}
a[0]=a[n]=0x3f3f3f3f;
if(m>(n>>1)){
puts("Error!");
return;
}
for(int i=1;i<n;++i){
l[i]=i-1;
}
for(int i=1;i<n;++i){
r[i]=i+1;
}
long long ans=0;
for(int i=1;i<=m;++i){
while(!q.empty()&&ext[q.top().second]){
q.pop();
}
nw=q.top().second;
ans+=q.top().first;
ext[l[nw]]=1,ext[r[nw]]=1;
nw2=a[l[nw]]+a[r[nw]]-q.top().first;
a[nw]=nw2;
l[nw]=l[l[nw]],r[nw]=r[r[nw]];
r[l[nw]]=nw,l[r[nw]]=nw;
q.pop();
q.push((pii){nw2,nw});
}
printf("%lld",ans);
}
int main(){
init();
return 0;
}
lp3084 USACO13OPEN 照片 Photo
传说这一题可以用差分约束，不过我个人的第一眼想法是\(DP\)。
首先我们令\(f_{i}\)为，第\(i\)个奶牛有斑点，\(DP\)到第\(i\)个奶牛，此时最多有多少只奶牛。
我们可以发现两点：一个区间最多有1个有斑点的奶牛，且一个区间最少有1个有斑点的奶牛。
对于当前的点，我们很容易可以知道，所有覆盖当前点的区间，在其他的地方都不能有有斑点的奶牛。
这也就等价于，转移是必须从包含\(f_{i}\)的所有区间中的左端点的最小值开始转移的。
与此同时，我们还必须明白，因为每个区间最少有一个有斑点的奶牛，因而为了保证满足提议，转移点到\(f_{i}\)之间的所有区间不能有空的。
这也就等价于，所有不包含\(f_{i}\)（当然显然区间右端点要小于\(i\)）的区间，它们的左端点中的最大值必须要小于转移点。这样才能上述性质。
此时我们只需要预处理出包含点i且左端点最小的区间，以及右端点小于\(i\)且左端点最大的区间。我们分别用\(e_{i}\)和\(s_{i}\)表示。
对于读入的每一组\(a,b\)，我们做如下处理：
使用\(a\)来更新\(s_{b+1}\)。这是因为，从\(a\)开始的区间必然不包含\(b+1\)，因此可以这样更新。
使用\(a-1\)来更新\(e_{b}\)。这是因为，从\(a\)开始的区间必然包含\(b\)。
故，更新方法为：
$$ s_{b+1}=Max(s_{b+1},a),e_{b}=Min(e_{b},a-1); $$
然后，对于这样更新得到的结果，我们贪心地处理。
对于\(s\)，我们发现，所有对于点\(i-1\)合法的区间——也就是右端点小于\(i-1\)的区间，一定不包含\(i\)。所以得到：
$$ s_{i}=Max(s_{i},s_{i-1}); $$
对于\(e\)，我们发现，所有对于点\(i+1\)最优的区间——也就是包含\(i+1\)且左端点最小的区间，一定包含\(i\)，否则它对于\(i\)一定不会更优。所以得到：
$$ e_{i}=Min(e_{i+1},e_{i}); $$
由是我们得到了DP需要的两个辅助数组，从而可以开始\(DP\)。
但这个时候我们可以发现，这样子动态确定最大值，如果使用暴力枚举，需要的复杂度是\(O(n)\)的，对于\(2E5\)的数据，通过会很困难。
这时候考虑优化，不过很容易可以发现是单调队列优化。
于是问题得解。
交上去WA10。
这是什么原因呢？
仔细研究一下，发现还是细节的问题。对于-1的特判没有清楚。
修改之后AC。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,m,f[200005],s[200005],e[200005];
struct data{
int v;
int id;
};
deque<data> q;
inline void psh(int i){
data x=(data){f[i],i};
while(!q.empty()&&q.back().v<x.v){
q.pop_back();
}
q.push_back(x);
}
inline int gt(const int &i){
while(!q.empty()&&q.front().id<s[i]){
q.pop_front();
}
return q.empty()?-1:q.front().v;
}
void init(){
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=n+1;++i){
e[i]=i-1;
}
for(int i=1;i<=m;++i){
scanf("%d%d",&a,&b);
s[b+1]=Max(s[b+1],a),e[b]=Min(e[b],a-1);
}
for(int i=2;i<=n+1;++i){
s[i]=Max(s[i],s[i-1]);
}
for(int i=n;i>=1;--i){
e[i]=Min(e[i+1],e[i]);
}
f[0]=0;
psh(0);
int j=1,nw;
for(int i=1;i<=n+1;++i){
while(j<=e[i]&&j<=n){
psh(j);
++j;
}
nw=gt(i);
f[i]=(nw==-1)?-1:nw+(int)(i<=n);
}
printf("%d",f[n+1]);
}
int main(){
init();
return 0;
}ARC098 D Xor Sum2
一道简单双指针题。
首先猜结论：\(x\ xor\ y==x+y\)当且仅当\(x\&y==x+y\)
那么，令函数\(f_l\)表示，以\(l\)为左端点最远能拓展到的右端点。
我们可以发现，\(f_{l+1}\)也一定至少能拓展到这个点。
这时候我们则可以在固定左端点的同时移动右端点。每一次移动，从这个右端点到这个左端点之间所有的左端点构成的区间都是合法的。
统计即可得解。
#include<iostream>
#include<cstdio>
using namespace std;
int n,a[200005];
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
long long ans=0,nw=0;
int l=1,r=1;
while(r<=n){
while((!(nw&a[r]))&&r<=n){
nw|=a[r++];
ans+=(r-l);
}
nw^=a[l++];
}
printf("%lld",ans);
}
int main(){
init();
return 0;
}