第14届浙江省赛By Tusimple

【网赛链接】

第14届浙江省赛By Tusimple

【A】

#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(“%d”,&(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,a1,T;
int Kobayashi[4]={1,0,1,-1},Kscore;
int Tohru[4]={0,1,1,-1},Tscore;
int main(){
    while(~SI(N)){
        while(N–){
            SI(T);
            Kscore=0;
            Tscore=0;
            rep(i,T){
                SI(a1);
                Kscore+=Kobayashi[a1-1];
                Tscore+=Tohru[a1-1];
            }
            if(Kscore>Tscore)
                puts(“Kobayashi”);
            else if(Tscore>Kscore)
                puts(“Tohru”);
            else
                puts(“Draw”);
        }
    }
    return 0;
}

【B】

#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(“%d”,&(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 ;
const int maxn=20000+10;
int T,N,fk,Orz,flag,cnt;
int score[maxn],scomp[maxn];
int main(){
    while(~SI(T)){
        while(T–){
            fill(score,score+4000,0);
            Orz=flag=0;
            SI(N);
            if(N>13 || N<10){
                rep(i,N){
                    SI(fk);
                }
                puts(“No”);continue;
            }
            rep(i,N){
                SI(fk);
                if(fk<=0){
                    flag=1;
                }else{
                    score[fk]++;
                }
                scomp[i]=fk;
            }
            if(flag){
                puts(“No”);
            }else{
                if(score[1]<2){
                    puts(“No”);
                    continue;
                }else{
                    sort(scomp,scomp+N);
                    rez(i,1,N-2){
                        if(scomp[i]-scomp[i-1]>2){
                            puts(“No”);
                            flag=1;
                            break;
                        }
                    }
                    if(!flag) puts(“Yes”);
                }
            }
        }
    }
    return 0;
}

【C】

#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(“%d”,&(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 T,n,q,c;
map<string,int> mp;
map<string,int>::iterator ite;
map<int,vector<string> > res;
string st;

inline int readt(int N){
    int ans=0,tit;
    rep(i,N){
        SI(tit);
        ans+=(1<<N-i-1) & (tit<<N-i-1);
    }
    return ans;
}

int main(){
    SI(T);
    while(T–){
        //测试数据可能出现重复的名字和情况,所以要初始化
        mp.clear();
        res.clear();
        SII(n,q);
        SI(c);
        rep(i,c){
            cin>>st;
            mp[st]=0;
        }
        rep(i,q){
            int nu;
            SI(nu);
            rep(j,nu){
                cin>>st;
                mp[st]+=(1<<q-i-1);
            }
        }
        for(ite=mp.begin();ite!=mp.end();ite++){
            res[ite->second].push_back(ite->first);
        }
        rep(i,n){
            int index=readt(q);
            if(res.find(index)==res.end()){
                puts(“Let’s go to the library!!”);
            }else{
                vector<string>& t=res[index];
                if(t.size()>1){
                    puts(“Let’s go to the library!!”);
                }else{
                    cout<<t[0]<<“\n”;
                }
            }
        }
    }
    return 0;
}

【D】

因为样例用的是m=3…所以我就一直卡在z>=3……然后比赛结束以后发现了…好亏啊

#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(“%d”,&(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 ;

struct Star{
    int left,right;
    bool operator<(const Star MM) const{
        return left<MM.left;
    }
}A[500],B[500];
int n,m,x,y,T,s,e;

int main(){
    SI(T);
    while(T–){
        SII(n,m);SII(x,y);
        rep(i,x){
            SII(s,e);
            A[i].left=s;
            A[i].right=e;
        }
        rep(i,y){
            SII(s,e);
            B[i].left=s;
            B[i].right=e;
        }
        sort(A,A+x);
        sort(B,B+y);
        int ans=0;
        rep(i,x){
            s=A[i].left;
            e=A[i].right;
            int z=0;
            rep(j,y){
                if(B[j].left>A[i].right) break;
                z+=(min(B[j].right,A[i].right)-max(A[i].left,B[j].left)+1);
                    if(z>=m){
                        ans+=z-m+1;
                        z=0;
                    }else{
                        z=0;
                    }
            }
        }
        printf(“%d\n”,ans);
    }
    return 0;
}

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

第六届山东省ACM/ICPC J Single Round Math

【类型】

java大整数瞎搞,话说占用内存好高啊.

【题目链接】

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3260.html

【Code】

import java.util.*;
import java.math.*;
public class J{
    public static void main(String args[]){
        Scanner cin=new Scanner(System.in);
        int T;
        BigInteger a,b,c=new BigInteger(“11”),d=new BigInteger(“0”);
        T=cin.nextInt();
        while((T–)!=0){
            a=cin.nextBigInteger();
            b=cin.nextBigInteger();
            if(a.compareTo(c)<0 || b.compareTo(c)<0) System.out.println(“NO”);
            else if(a.compareTo(b)!=0) System.out.println(“NO”);
            else if(d.compareTo(a.remainder(c))==0) System.out.println(“YES”);
            else System.out.println(“NO”);
        }
    }
}

第六届山东省ACM/ICPC B Lowest Unique Price

【类型】

set,映射

【Tip】

题目上给的数据范围是 x∈[1,106]

但是我写代码时把映射空间开到100000才A了过去.?????? WTF??

另外,一开始我用map动态搜索,输出时遍历查找最少价值为一次的结果,果不其然,TLE.

所以改成了set动态更新第一个节点.即最小点.实现不需要遍历直接插入瞎搞的算法.

PS:真心搞不懂为啥映射数组要开10W啊???????

【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(“%d”,&(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 reg[100000];
char readchar(){
char c=getchar();
while(c!=’b’ && c!=’q’ && c!=’c’) c=getchar();
return c;
}

int main(){
int T;
scanf(“%d”,&T);
while(T–){
set<int> se;
cle(reg,0);
int N;
SI(N);
rep(i,N){
char a;
int b;
a=readchar();
if(a==’b’){
SI(b);
reg[b]++;
if(reg[b]==1) se.insert(b);
else se.erase(b);
}
if(a==’c’){
SI(b);
if(reg[b]>0){
reg[b]–;
if(reg[b]==1) se.insert(b);
else se.erase(b);
}
}
if(a==’q’){
if(se.empty()) puts(“none”);
else printf(“%d\n”,*(se.begin()));
}
}

}
return 0;
}

第六届山东省ACM/ICPC A Nias and Tug-of-War

【类型】

重载小于号,排序

【题目链接】

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3251.html

【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(“%d”,&(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 ;

struct star{
    double height,weight;
    bool operator<(const star A)const{
        return height<A.height;
    }
}person[200];

int main(){
    int T,N;
    double ansr=0.0,ansb=0.0;
    scanf(“%d”,&T);
    while(T–){
        ansr=0.0,ansb=0.0;
        scanf(“%d”,&N);
        rep(i,N)
            scanf(“%lf %lf”,&person[i].height,&person[i].weight);
        sort(person,person+N);
        int con=1;
        rep(i,N){
            if(con==1){
                con=0;
                ansr+=person[i].weight;
            }else{
                con=1;
                ansb+=person[i].weight;
            }
        }
        if(ansb>ansr)
            printf(“blue\n”);
        else if(ansr>ansb)
            printf(“red\n”);
        else   printf(“fair\n”);
    }
    return 0;
}

第七届山东省ACM/ICPC K Reversed Words

【Tip】

我太菜辣,没有1A  ……F**k

【Code】

#include<bits/stdc++.h>
using namespace std;
char str[10000];
int main(){
    int T;
    scanf(“%d\n”,&T);
    while(T–){
        int star=-1;
        gets(str);
        int len=strlen(str);
        for(int i=0;i<len+1;++i){
            if(str[i]==’ ‘ || str[i]==’\0′ || str[i]==’\n’){
                for(int j=i-1;j>star;–j)
                    putchar(str[j]);
                star=i;
                if(str[i]==’ ‘)putchar(str[i]);
            }
        }
        putchar(‘\n’);
    }
    return 0;
}

第七届山东省ACM/ICPC H Memory Leak

【类型】

模拟,感受一下什么叫绝望吧…

【Tip】

F**k!…..QNMD鲁棒性….QAQ

后记…发现自己的代码可以过…但是忘了关freopean..所以才WA…尴尬//= // =//

【Code】

鲁棒形比我好,一点的,代码.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int T;
char name[10010],stri[10010];
int num;
struct Star{
    char s[2000];
    char contain[10010];
    int ind;
    bool has_end;
};
Star S[10010];
int main(){
 //   #ifndef DEF
 //    freopen(“in.txt”,”r”,stdin);
 //    freopen(“out.txt”,”w”,stdout);
 //  #endif // DEF
    scanf(“%d”,&T);
        while(T–){
            char op[100],def[10100];
            num=0;
            while(scanf(“%s”,op)){
                if(op[3]==’u’){
                    scanf(“%*s”);
                    break;
                }
                if(op[3]==’r’){
                    while(scanf(“%s”,def)){
                        int flag=1,star_num=0,ind_num=0,len=strlen(def);
                        for(int i=0;i<len;++i){
                            if(flag==1 && def[i]!='[‘){
                                S[num].s[star_num++]=def[i];
                            }
                            if(def[i]=='[‘){
                                S[num].s[star_num]=0;
                                flag=2;
                                continue;
                            }
                            if(flag==2 && def[i]!=’]’){
                                ind_num=ind_num*10+(def[i]-‘0’);
                            }
                            if(def[i]==’]’){
                                S[num].contain[0]=0;//初始化
                                S[num].has_end=true;
                                S[num].ind=ind_num;
                                star_num=0;
                                ind_num=0;
                                num++;
                                continue;
                            }
                        }
                        if(def[len-1]==’;’) break;
                    }
                }
                if(op[3]==’s’){
                    scanf(“%s%*c”,name);
                    gets(stri);
                    int index=num;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    int len=strlen(stri);
                    if(len>=S[index].ind){
                        S[index].has_end=false;
                        stri[S[index].ind]=0;//’\0′
                    }else S[index].has_end=true;
                    strcpy(S[index].contain,stri);
                }
                if(op[3]==’t’){
                    scanf(“%s”,name);
                    int index=num;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    for(int i=index;i<num;++i){
                        printf(“%s”,S[i].contain);
                        if(S[i].has_end) break;
                    }
                    printf(“\n”);
                }
            }
        }
    return 0;
}

我的代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int T;
char name[10010],stri[10010];
int num=0;
struct Star{
    char s[2000];
    char contain[10010];
    int ind;
    bool has_end;
};
Star S[10010];
int main(){
//   #ifndef DEF  //<-F**k U
  //   freopen(“in.txt”,”r”,stdin);
  //   freopen(“out.txt”,”w”,stdout);
 //  #endif // DEF
    scanf(“%d”,&T);
        while(T–){
            char op[10],def[10100];
            num=0;
            while(scanf(“%s”,op)){
                scanf(” “);
                if(op[3]==’u’){
                    scanf(“%*s”);
                    break;
                }
                if(op[3]==’r’){
                    int flag=1,star_num=0,ind_num=0;
                    gets(def);
                    for(int i=0,start=0;def[i]!=’\0′;++i){
                        if(def[i]==’ ‘ || def[i]==’,’) continue;
                        if(flag==1 && def[i]!='[‘){
                            S[num].s[star_num++]=def[i];
                        }else if(def[i]=='[‘){
                            S[num].s[star_num]=0;
                            flag=2;
                        }else if(flag==2 && def[i]!=’]’){
                            ind_num=ind_num*10+(def[i]-‘0’);
                        }else if(def[i]==’]’){
                            S[num].contain[0]=0;//初始化
                            S[num].has_end=true;
                            S[num].ind=ind_num;
                            star_num=0;
                            ind_num=0;
                            num++;
                            flag=1;
                        }else if(def[i]==’;’)
                            break;
                    }
                }
                if(op[3]==’s’){
                    scanf(“%s%*c”,name);
                    gets(stri);
                    int index;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    int len=strlen(stri);
                    if(len>=S[index].ind){
                        S[index].has_end=false;
                        stri[S[index].ind]=0;//’\0′
                    }else S[index].has_end=true;
                    strcpy(S[index].contain,stri);
                }
                if(op[3]==’t’){
                    scanf(” “);
                    gets(name);
                    int index;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    for(int i=index;i<num;++i){
                        printf(“%s”,S[i].contain);
                        if(S[i].has_end) break;
                    }
                    printf(“\n”);
                }
            }
        }
    return 0;
}

第七届山东省ACM/ICPC F Feed the monkey

【类型】

DP

【题目链接】

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1761/pid/3565

【题解】

用dp[i][j][k][t]表示剩余i个第一种物品,j个第二种物品,k个第三种物品.以第t种物品为结尾的安排饲养表的种数.

递归的思想来合并所有的情况,不过是减了所有的重复枝.

【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(“%d”,&(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 ;
const ll mod=1000000007;
const int maxn=55;
ll dp[maxn][maxn][maxn][4];
int N1,N2,N3,D1,D2,D3,T;

int main(){
    while(~SI(T)){
        while(T–){
            cle(dp,0);
            SIII(N1,N2,N3);
            SIII(D1,D2,D3);
            red(i,N1,0) red(j,N2,0) red(k,N3,0){
                rez(s,1,min(i,D1)){
                    if(i==N1 && j==N2 && k==N3)
                        dp[i-s][j][k][0]=(dp[i-s][j][k][0]+1)%mod;
                    else
                        dp[i-s][j][k][0]=((dp[i-s][j][k][0]+dp[i][j][k][1])%mod+dp[i][j][k][2])%mod;
                }
                rez(s,1,min(j,D2)){
                    if(i==N1 && j==N2 && k==N3)
                        dp[i][j-s][k][1]=(dp[i][j-s][k][1]+1)%mod;
                    else
                        dp[i][j-s][k][1]=((dp[i][j-s][k][1]+dp[i][j][k][0])%mod+dp[i][j][k][2])%mod;
                }
                rez(s,1,min(k,D3)){
                    if(i==N1 && j==N2 && k==N3)
                        dp[i][j][k-s][2]=(dp[i][j][k-s][2]+1)%mod;
                    else
                        dp[i][j][k-s][2]=((dp[i][j][k-s][2]+dp[i][j][k][0])%mod+dp[i][j][k][1])%mod;
                }
            }
            ll ans=0;
            ans=((dp[0][0][0][0]+dp[0][0][0][1])%mod+dp[0][0][0][2])%mod;
            printf(“%lld\n”,ans);
        }
    }
    return 0;
}