发布于

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，时间复杂度确实是丧题，如果真实比赛我就凉了；逛公园非常难写，以至于我丧失信心放弃治疗。

我的应试能力有很大的欠缺。