发布于

lp3958 NOIP2017 奶酪

简单结论+并查集+大力模拟
注意并查集不要写挂。
另：记住long double的范围小于long long

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

#define eps 1E-9
long long n,h,r;
inline double clac(const long long &x1,const long long &y1,const long long &z1,const long long &x2,const long long &y2,const long long &z2){
    return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
long long f[1005],x[1005],y[1005],z[1005];
inline long long fa(const long long &x){
    return (f[x]==x)?(x):(f[x]=fa(f[x]));
}
inline void uni(const long long &x,const long long &y){
    (fa(x)==fa(y))?0:f[fa(x)]=fa(y);
}
bool up[1005],dn[1005];
void init(){
    scanf("%lld%lld%lld",&n,&h,&r);
    memset(up,0,sizeof(up));
    memset(dn,0,sizeof(dn));
    for(int i=1;i<=n;++i){
        f[i]=i;
    }
    long long nx,ny,nz;
    for(int i=1;i<=n;++i){
        scanf("%lld%lld%lld",&nx,&ny,&nz);
        x[i]=nx;
        y[i]=ny;
        z[i]=nz;
        if(z[i]<=r){
            dn[i]=1;
        }
        if(h-z[i]<=r){
            up[i]=1;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(fa(i)==fa(j)){
                continue;
            }
            if((double)(r*2)>=clac(x[i],y[i],z[i],x[j],y[j],z[j])){
                uni(i,j);
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(!dn[i]){
            continue;
        }
        for(int j=1;j<=n;++j){
            if(!up[j]){
                continue;
            }
            if(fa(i)==fa(j)){
                puts("Yes");
                return;
            }
        }
    }
    puts("No");
} 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

lp3952 NOIP2017 时间复杂度

魔鬼的大力模拟题。
千万要注意大小写。
注意数字、字符串转化。这个细节困扰了我很久。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
bool usd[30];
//lv==-1:这层循环根本不会被执行。 
struct data{
    int lv;
    int x;
}st[105];
int tp=0,n,slv=0,nlv=0,ans=0;
char ch[105];
inline int cg(){
    int _X=0,_BS=10,i=0;
    while(ch[i]<'0'||ch[i]>'9'){
        ++i;
    }
    while(ch[i]>='0'&&ch[i]<='9'){
        _X*=_BS;
        _X+=((ch[i]-'0'));
        ++i;
    }
    return _X;
}
void init(){
    scanf("%d",&n);
    memset(usd,0,sizeof(usd));
    tp=0,nlv=0;
    int ss,tt;
    cin>>ch;
    if(ch[2]=='1'){
        slv=0;
    }else{
        slv=cg();
    }
    st[0].lv=0;
    st[0].x=-1;
    bool bo=0; 
    for(int i=1;i<=n;++i){
        cin>>ch;
        if(ch[0]=='E'){
            if(!tp){
                bo=1;
            }else{
                nlv=Max(nlv,st[tp].lv);
                usd[st[tp].x]=0;
                --tp;
            }
        }else{
            cin>>ch;
            ++tp;
            if(usd[ch[0]-'a']){
                bo=1;
            }else{
                usd[ch[0]-'a']=1;
                st[tp].x=ch[0]-'a';
            }
            memset(ch,0,sizeof(ch));
            cin>>ch;
            if(ch[0]=='n'){
                ss=100000;
            }else{
                ss=cg();
            }
            memset(ch,0,sizeof(ch));
            cin>>ch;
            if(ch[0]=='n'){
                tt=100000;
            }else{
                tt=cg();
            }
            memset(ch,0,sizeof(ch));
            if(st[tp-1].lv==-1){
                st[tp].lv=-1;
                continue;
            }
            if(ss>tt){
                st[tp].lv=-1;
            }else if(ss==tt||(tt!=100000)){
                st[tp].lv=st[tp-1].lv;
            }else if(tt==100000){
                st[tp].lv=st[tp-1].lv+1;
            }
        }
    }
    if(tp||bo){
        puts("ERR");
        return;
    }
    if(nlv==slv){
        puts("Yes");
    }else{
        puts("No");
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

CF510C

因为维护的是偏序关系，很容易可以发现是拓扑排序裸题。
一个字母写错了调了半天。
可以用堆维护字典序。


#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int in[30],n,len[1005],at=0,ss[30];
bool mp[30][30];
char ch[105][105];
char ans[30];
inline void CMP(const int &A,const int &B){
    int le=Min(len[A],len[B]);
    for(int i=1;i<=le;++i){
        if(ch[A][i]!=ch[B][i]){
            if(!mp[ch[A][i]-'a'][ch[B][i]-'a']){
                mp[ch[A][i]-'a'][ch[B][i]-'a']=1;
                ++in[ch[B][i]-'a'];
            }
            return;
        }
    }
    if(len[A]>len[B]){
        puts("Impossible");
        exit(0);
    }
}
priority_queue< int,vector<int>,greater<int> > q;
inline void srt(){
    for(int i=0;i<26;++i){
        if(!in[i]){
            q.push(i);
        }
    }
    int p;
    while(!q.empty()){
        p=q.top();
        q.pop();
        ans[++at]=p+'a';
        for(int i=0;i<26;++i){
            if(mp[p][i]){
                --in[i];
                if(!in[i]){
                    q.push(i);
                }
            }
        }
    }
    if(at<26){
        puts("Impossible");
        exit(0);
    }
    ans[++at]='\0';
}
void init(){
    scanf("%d",&n);
    memset(mp,0,sizeof(mp));
    memset(in,0,sizeof(in));
    for(int i=1;i<=n;++i){
        cin>>ch[i]+1;
        len[i]=strlen(ch[i]+1);
    }
    for(int i=1;i<n;++i){
        CMP(i,i+1);
    }
    srt(); 
    cout<<ans+1;
}
int main(){
    init();
    return 0;
}

 

发布于

lp4568 JLOI2011 飞行路线

首先看到点数，就考虑拆点。
把每一个点拆成k个点，分别表示已经吃了k次免费午餐的距离。
然后大力跑堆优化dij即可。可以用pair加伪函数套STL。
特别要注意是小根堆。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B)) 

struct ee{
    int v;int w;int nxt;
}e[100005];
int h[10005],et=0,f[10005][12],n,m,k,s,t;
inline void add(const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,h[u]};
    h[u]=et;
}
typedef pair<int,int> pii;
struct cmp{
	bool operator ()(const pii &A,const pii &B){
		return f[A.first][A.second]>f[B.first][B.second];
	}
};
priority_queue<pii,vector<pii>,cmp> q;
void bfs(int s){
    pii p(s,0);
    q.push(p);
    while(!q.empty()){
        p=q.top();
        q.pop();
        for(int i=h[p.first];i;i=e[i].nxt){
            if(f[e[i].v][p.second]>f[p.first][p.second]+e[i].w){
                f[e[i].v][p.second]=f[p.first][p.second]+e[i].w;
                q.push((pii){e[i].v,p.second});
            }
            if(p.second+1<=k){
                if(f[e[i].v][p.second+1]>f[p.first][p.second]){
                    f[e[i].v][p.second+1]=f[p.first][p.second];
                    q.push((pii){e[i].v,p.second+1});
                }
            }
        }
    }
}
void init(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&s,&t);
    memset(f,0x3f,sizeof(f));
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        if(u==v){
            continue;
        }
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=0;i<=k;++i){
        f[s][i]=0;
    }
    bfs(s);
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;++i){
        ans=Min(ans,f[t][i]);
    }
    printf("%d",ans);
    
}
int main(){
    init();
    return 0;
}

 

发布于

停课第三天。

停课第三天，距离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;
}

 

发布于

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;
}