VJ SWPU-ACM省赛集训赛ONE J Right turn

【类型】

模拟

【Tip】

我的代码感觉上很对…然而莫名其妙总WA.然后把代码改成网上搜的题解的思路,A了…

我一开始的思路是floyd判圈法,若会碰到同一个路障第二次,则一定无法逃出去.

这个思路是错的,因为有可能在同一个点转的方向不同,所以如果经过同一个点两次有可能逃出去.

但每个点最多只能经过三次,第四次时一定是一个圈.所以判断是否经过一个点四次就好了.依然是floyd判圈法.不过要判四次.

然后成型代码如下.

【WA Code1】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf("%lld",&(N))
#define SII(N,M) scanf("%d %d",&(N),&(M))
#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<"="<<(x)<<endl;
#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,bool> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(1){
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>X){
                    if(mp[make_pair(Just[i],Y)]) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]=true;
                    flag=1;
                    X=Just[i]-1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<Y){
                    if(mp[make_pair(X,Just[i])]) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]=true;
                    Y=Just[i]+1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<X){
                    if(mp[make_pair(Just[i],Y)]) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]=true;
                    flag=1;
                    X=Just[i]+1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    if(mp[make_pair(X,Just[i])]) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]=true;
                    Y=Just[i]-1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }
    }
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf("%d%d",&node.first,&node.second);
            mp[node]=false;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        map<int,vector<int> >::iterator it;
        for(it=EdgeX.begin();it!=EdgeX.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        for(it=EdgeY.begin();it!=EdgeY.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        if(floyd()){
            printf("%d\n",step);
        }else{
            printf("-1\n");
        }
    }
    return 0;
}

【简单修改后AC代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%lld”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,int> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(1){
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>X){
                    if(mp[make_pair(Just[i],Y)]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]++;
                    flag=1;
                    X=Just[i]-1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<Y){
                    if(mp[make_pair(X,Just[i])]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]++;
                    Y=Just[i]+1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<X){
                    if(mp[make_pair(Just[i],Y)]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]++;
                    flag=1;
                    X=Just[i]+1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    if(mp[make_pair(X,Just[i])]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]++;
                    Y=Just[i]-1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }
    }
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf(“%d%d”,&node.first,&node.second);
            mp[node]=0;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        map<int,vector<int> >::iterator it;
        for(it=EdgeX.begin();it!=EdgeX.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        for(it=EdgeY.begin();it!=EdgeY.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        if(floyd()){
            printf(“%d\n”,step);
        }else{
            printf(“-1\n”);
        }
    }
    return 0;
}

【跟着题解AC Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%lld”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,bool> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(step<=4*N+1){
        int tmpx=-INF,tmpy=-INF;
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size();
            rep(i,si){
                if(Just[i]>X){
                    tmpy=Y;
                    if(tmpx!=-INF) tmpx=min(tmpx,Just[i]);
                    else tmpx=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
    //            if(mp[make_pair(tmpx,Y)]) return false;
     //           mp[make_pair(tmpx,Y)]=true;
                X=tmpx-1;
                step++;
                t=(t+1)%4;
            }

        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]<Y){
                    tmpx=X;
                    flag=1;
                    if(tmpy!=-INF) tmpy=max(tmpy,Just[i]);
                    else tmpy=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
  //              if(mp[make_pair(X,tmpy)]) return false;
 //               mp[make_pair(X,tmpy)]=true;
                Y=tmpy+1;
                step++;
                t=(t+1)%4;
            }
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]<X){
                    flag=1;
                    tmpy=Y;
                    if(tmpx!=-INF) tmpx=max(tmpx,Just[i]);
                    else tmpx=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
 //               if(mp[make_pair(tmpx,Y)]) return false;
 //               mp[make_pair(tmpx,Y)]=true;
                X=tmpx+1;
                step++;
                t=(t+1)%4;
            }
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    tmpx=X;
                    flag=1;
                    if(tmpy!=-INF) tmpy=min(tmpy,Just[i]);
                    else tmpy=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
 //              if(mp[make_pair(X,tmpy)]) return false;
  //              mp[make_pair(X,tmpy)]=true;
                Y=tmpy-1;
                step++;
                t=(t+1)%4;
            }
        }
    }
    return false;
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf(“%d%d”,&node.first,&node.second);
//            mp[node]=false;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        if(floyd()){
            printf(“%d\n”,step);
        }else{
            printf(“-1\n”);
        }
    }
    return 0;
}

VJ SWPU-ACM省赛集训赛ONE E Rectangle

【Tip】

枚举长的长度,则对于长有N-i+1种情况.

然后得出宽的取值范围为[1,tmp=(K-i)<M?(K-i):M].防溢出.

画图知在宽的取值范围内情况分别为:M,M-1,M-2…M-tmp+1.共tmp项.

用等差数列求和公式得出该长下的宽的情况个数.

乘积累加.

【Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%lld”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int N,M,K;
ll ans;
int main(){
    while(~SIII(N,M,K)){
        K>>=1;
        ans=0;
        for(int i=1;i<=N && K-i>0;++i){
            ll tmp=(K-i)<M?(K-i):M;
            ll sumC=N-i+1;
            ll sumK=(M+M-tmp+1)*tmp/2;
            ans+=sumC*sumK;
        }
        printf(“%lld\n”,ans);
    }
    return 0;
}

VJ SWPU-ACM省赛集训赛ONE A Easy Math

【Tip】

直觉只要有一个不是平方根就输出No,直觉是对的…

可以当做结论?

【Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%lld”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int N;
int main(){
    while(~SI(N)){
        bool flag=true;
        ll num;
        while(N–){
            SI(num);
            ll t=sqrt(num);
            if(t*t!=num)
                flag=false;
        }
        printf(flag?”Yes\n”:”No\n”);
    }
    return 0;
}