讨论主页 >> 话题详情
avatar
第九届北京化工大学程序设计竞赛网络同步赛简略题解 发表于2015-05-10 12:47

我们是弱校,我还有其他两个出题人的水平也不高,题目中出现的一些问题,请谅解,多多吐槽,多多交流。

A       A Math Game

       由于这道题H和A[i]给的比较大,dp的空间开不下,而n比较小,只有40,所以可以把所给的数分成20、20两部分,用dfs或者直接状态压缩从0至2^(n/2)循环来搞出每组所有可能的和(dfs+剪枝应该比循环快),然后用在第二部分找(H-第一部分的可能和)就可以了。卡了一下map和set。可以用hash或者二分来找。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define MAXN 40
using namespace std;
int N,H,A[50],d[50],a1[1050000],n1,n2,cnt;
bool flag;
bool Check(int x){
    int L=0,R=cnt-1;
    while(L<=R){
        int mid=(L+R)>>1;
        if(a1[mid]==x) return 1;
        if(a1[mid]<x) L=mid+1;
        else R=mid-1;
    }
    return 0;
}
void dfs(int sum,int deep,int n,bool on){
    if(deep==n){
        if(on) a1[cnt++]=sum;
        else flag=Check(H-sum);
        return;
    }
    for(int i=0;i<2;i++){
        int t=sum+i*d[deep];
        if(t>H) return;
        dfs(t,deep+1,n,on);
        if(flag) return;
    }
}
int main(){
    while(~scanf("%d%d",&N,&H)){
        flag=0;
        cnt=0;
        for(int i=0;i<N;i++)
            scanf("%d",A+i);
        n1=(N>>1),n2=N-n1;
        for(int i=n1;i<N;i++)
            d[i-n1]=A[i];
        dfs(0,0,n2,1);
        sort(a1,a1+cnt);
        for(int i=0;i<n1;i++)
            d[i]=A[i];
        dfs(0,0,n1,0);
        if(flag) puts("Yes");
        else puts("No");
    }
    return 0;
}

B        Sequence

       其实这道题是从BestCoder上扒的,数据也小了很多。

       只须关注连续两项之差就行了,直接搞一个存前后两项差的串,然后跑一遍AC自动机就可以了。注意当原序列长度只有1的时候要特判一下。节点整数用map存就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define MAXN 101010
#define TP long long
using namespace std;
template<class T>
struct AC_AUTO{
    map<T,int>mp[MAXN];
    typename map<T,int> :: iterator it;
    int fail[MAXN],end[MAXN],Q[MAXN],head,tail,root,cnt;
    void init(){
        cnt=0;
        root=newnode();
    }
    int newnode(){
        mp[cnt].clear();
        end[cnt++]=0;
        return cnt-1;
    }
    void insert(T s[],int n){
        int now=root;
        for(int i=0;i<n;i++){
            if(!mp[now].count(s[i])) mp[now][s[i]]=newnode();
            now=mp[now][s[i]];
        }
        end[now]++;
    }
    void build(){
        head=tail=0;
        fail[root]=root;
        for(it=mp[root].begin();it!=mp[root].end();++it){
            fail[it->second]=root;
            Q[tail++]=it->second;
        }
        while(head!=tail){
            int now=Q[head++];
            end[now]+=end[fail[now]];
            for(it=mp[now].begin();it!=mp[now].end();++it){
                int x=fail[now],flag=0;
                while(x!=root){
                    if(mp[x].count(it->first)){
                        fail[it->second]=mp[x][it->first];
                        flag=1;
                        break;
                    }
                    x=fail[x];
                }
                if(x==root && mp[x].count(it->first)){
                    fail[it->second]=mp[x][it->first];
                    flag=1;
                }
                if(!flag) fail[it->second]=root;
                Q[tail++]=it->second;
            }
        }
    }
    TP query(T s[],int n){
        TP ret=0;
        int now=root;
        for(int i=0;i<n;i++){
            int x=now,flag=0;
            while(x!=root){
                if(mp[x].count(s[i])){
                    now=mp[x][s[i]];
                    flag=1;
                    break;
                }
                x=fail[x];
            }
            if(x==root && mp[x].count(s[i])){
                now=mp[x][s[i]];
                flag=1;
            }
            if(!flag) now=root;
            ret+=end[now];
        }
        return ret;
    }
};
AC_AUTO<int> ac;
int s[MAXN],p[MAXN];
int n,m,q;
int main(){
    while(~scanf("%d%d",&n,&m)){
        int pre;
        scanf("%d",&pre);
        for(int i=1;i<n;i++){
            int x;
            scanf("%d",&x);
            s[i-1]=x-pre;
            pre=x;
        }

        ac.init();
        TP ans=0;
        for(int i=0;i<m;i++){
            int c;
            scanf("%d%d",&c,&pre);
            for(int j=1;j<c;j++){
                int x;
                scanf("%d",&x);
                p[j-1]=x-pre;
                pre=x;
            }
            if(c==1) ans+=n;
            else ac.insert(p,c-1);
        }
        ac.build();
        ans+=ac.query(s,n-1);
        printf("%lld\n",ans);
    }
}

C         SJY’s First Task

       出题人用bfs写的,我用dfs也AC了一边。主要是存节点,还有数据的读取,我在每行后面加了个逗号来读的。注意节点可不是1-n。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
#define MAXN 101000
using namespace std;
struct LV{
    int id,u;
    bool operator < (const LV &rhs) const{
        return u<rhs.u;
    }
};LV Leave[MAXN];
struct Node{
    int u,dis;
    Node(int u,int dis):u(u),dis(dis){}
    bool operator < (const Node &rhs) const{
        if(dis==rhs.dis) return u<rhs.u;
        return dis<rhs.dis;
    }
};
vector<int>E[MAXN];
vector<Node>ans[MAXN];
map<int,int>mp;
int K,n,ecnt=0,nmp[MAXN];
int vis[MAXN],IsLeave[MAXN],LeaveId[MAXN],Lcnt=0;
void dfs(int id,int deep,int root){
    vis[id]=root;
    if(deep==K){
        return;
    }
    int sz=E[id].size();
    for(int i=0;i<sz;i++){
        int u=E[id][i];
        if(vis[u]==root) continue;
        vis[u]=root;
        if(IsLeave[u]==1) ans[root].push_back(Node(nmp[u],deep+1));
        dfs(u,deep+1,root);
    }
}

void rd_d(char *a,int &t){
    sscanf(a,"%d",&t);
}
int tr(int x){
    if(mp[x]==0){
        mp[x]=++ecnt;
        nmp[ecnt]=x;
    }
    return mp[x];
}
bool IsDigital(char c){
    if(c>='0' && c<='9') return true;
    else return false;
}
void init(){
    memset(IsLeave,0,sizeof(IsLeave));
    memset(vis,0,sizeof(vis));
    memset(nmp,0,sizeof(nmp));
    memset(LeaveId,0,sizeof(LeaveId));
    mp.clear();
    for(int i=0;i<MAXN;i++){
        ans[i].clear();
        E[i].clear();
    }
}
int main(){
    char str[1000];
    init();
    scanf("%d%d",&K,&n);
    gets(str);
    for(int i=0;i<n;i++){
        gets(str);
        int u;
        rd_d(str,u);
        Leave[Lcnt].u=u;
        u=tr(u);
        IsLeave[u]=1;
        Leave[Lcnt++].id=u;
        int L=strlen(str),p=0;
        str[L]=',';str[++L]=0;
        for(p=0;p<L;p++) if(!IsDigital(str[p])) break;
        while(!IsDigital(str[p])) p++;
        int prex=0;
        for(;p<L;p++){
            int x;
            rd_d(str+p,x);
            x=tr(x);
            E[prex].push_back(x);
            E[x].push_back(prex);
            prex=x;
            while(IsDigital(str[p])) p++;
        }
        E[prex].push_back(u);
        E[u].push_back(prex);
    }
    sort(Leave,Leave+Lcnt);
    for(int i=0;i<Lcnt;i++){
        int u=Leave[i].id;
        vis[0]=u;
        dfs(u,0,u);
        sort(ans[u].begin(),ans[u].end());
        int sz=ans[u].size();
        for(int j=0;j<sz;j++){
            printf("%d %d %d\n",Leave[i].u,ans[u][j].u,ans[u][j].dis);
        }
    }
}

D        Crime

       这题先是判断二分图,用的是染色的方法。即给节点染两种颜色,与其相连的节点颜色不同,然后判断是否矛盾(其相邻节已染色点与其颜色是否相同)。然后是二分图最大匹配,匈牙利算法即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#define MAXN 310
using namespace std;
map<string,int>name;
int G[MAXN][MAXN],col[MAXN];
int n,m;
int cx[MAXN],cy[MAXN];
bool mk[MAXN];
bool dfs(int now){
    int i;
    for(i=1;i<=n;i++)
        if(G[now][i]){
            if(col[i]==-1){
                col[i]=!col[now];
                bool tem=dfs(i);
                if(tem==0)
                    return 0;
            }
            else if(col[i]==col[now])
                return 0;
        }
    return 1;
}
int path(int u){
    int i;
    for(i=1;i<=n;i++){
        if(G[u][i] && mk[i]==0){
            mk[i]=1;
            if(cy[i]==0 || path(cy[i])){
                cx[u]=i;
                cy[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int maxmatch(){
    int i,j,u,v,sum=0;
    memset(cx,0,sizeof(cx));
    memset(cy,0,sizeof(cy));
    for(i=1;i<=n;i++){
        if(cx[i]==0){
            memset(mk,0,sizeof(mk));
            sum+=path(i);
        }
    }
    return sum;
}
int main(){
    int i,j,u,v;
    while(~scanf("%d%d",&n,&m)){
        memset(G,0,sizeof(G));
        name.clear();
        int ncnt=1;
        for(i=1;i<=m;i++){
            char str1[15],str2[15];
            scanf("%s %s",&str1,&str2);
            string t1=str1,t2=str2;
            if(name[t1]==0) name[t1]=ncnt++;
            if(name[t2]==0) name[t2]=ncnt++;
            int u=name[t1],v=name[t2];
            G[u][v]=G[v][u]=1;
        }
        memset(col,-1,sizeof(col));
        col[1]=1;
        if(dfs(1)==0){
            printf("No\n");
            continue;
        }
        printf("%d\n",maxmatch());
    }
}

E        Use Machine Learning to Find GF

       直接套公式就可以了。其实这道题可以完全消除误差,把X和Y通分就可以了。注意P(0)或者P(1)=0的情况,从概率上看应该是0,所以通分的时候至少在分子上保留一个P(0)或P(1)就可以避免了。通分要用long long。

#include<iostream>
#include<cstdio>
#define MAXE 110
using namespace std;
struct Node{
    int a,b,c,g;
};Node Data[MAXE];
int E,ca,cb,cc,cg,na,nb,nc,ng;
int main(){
    while(cin>>E){
        int a,b,c,g;
        ca=cb=cc=cg=na=nb=nc=ng=0;
        for(int i=0;i<E;i++){
            cin>>a>>b>>c>>g;
            Data[i]=Node{a,b,c,g};
            cg+=g;ng+=(g^1);
        }
        cin>>a>>b>>c;
        for(int i=0;i<E;i++){
            ca+=((Data[i].a^a)^1)*(Data[i].g);na+=((Data[i].a^a)^1)*(Data[i].g^1);
            cb+=((Data[i].b^b)^1)*(Data[i].g);nb+=((Data[i].b^b)^1)*(Data[i].g^1);
            cc+=((Data[i].c^c)^1)*(Data[i].g);nc+=((Data[i].c^c)^1)*(Data[i].g^1);
        }
        long long X=(long long)na*nb*nc*ng*cg*cg*cg,Y=(long long)ca*cb*cc*cg*ng*ng*ng;
        if(X<=Y) puts("Come on guys,you can do it!");
        else puts("Poor guys,you can go back to sleep now..");
    }
    return 0;
}

F        Three Circles in a Triangle

       这道题有个结论:详见http://en.wikipedia.org/wiki/Malfatti_circles。其实就是找这13个圆中最大的3个。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double PI=3.1415926535898;
double GetR_1L2C(double R1,double R2){
    double L=2*sqrt(R1*R2);
    double r1=2*sqrt(R1),r2=2*sqrt(R2);
    return pow(L/(r1+r2),2);
}
double GetR_2L1C(double L,double R){
    double a=1,b=-(2*R+4*R/L*R/L*R),c=R*R;
    double delta=sqrt(b*b-4*a*c);
    double r1=(-b+delta)/2,r2=(-b-delta)/2;
    if(r1>R) return r2;
    return r1;
}
double Get_Area(double a,double b,double c){
    double p=(a+b+c)/2;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
double Get_cos(double a,double b,double c){
    return (b*b+c*c-a*a)/(2*b*c);
}
double Get_hfcos2(double x){
    return (x+1)/2;
}
double CR[20];
int main(){
    double L[3];
    while(~scanf("%lf%lf%lf",&L[0],&L[1],&L[2])){
        int pc=0;
        double S=Get_Area(L[0],L[1],L[2]);
        double inr=2*S/(L[0]+L[1]+L[2]);
        CR[pc++]=inr;
        int ta[3]={0,1,2};
        for(int i=0;i<3;i++){
            double cs=Get_cos(L[ta[0]],L[ta[1]],L[ta[2]]);
            int t=ta[2];
            ta[2]=ta[1];ta[1]=ta[0];ta[0]=t;
            cs=Get_hfcos2(cs);
            cs=sqrt((1-cs)/cs);
            double len=inr/cs;
            double c=GetR_2L1C(len,inr);
            CR[pc++]=c;
            len=c/cs;
            CR[pc++]=GetR_2L1C(len,c);
            CR[pc++]=GetR_1L2C(inr,c);
            CR[pc++]=GetR_1L2C(c,inr);
        }
        sort(CR,CR+pc);
        double Sans=CR[pc-1]*CR[pc-1]*PI+CR[pc-2]*CR[pc-2]*PI+CR[pc-3]*CR[pc-3]*PI;
        double ans=Sans/S*100;
        printf("%.2lf%%\n",ans);
    }
}

G        最小公倍数

        

        一开始被出题人的数据大小吓到了,后来看到时限还是能写的。

        首先是开一个10^8的bool有点吓人,于是我开了个char数组,把每一位都用上了,压缩呀压缩。

然后筛法标记出10^8内的素数。

        注意,当答案ans增大时,一定是当前数的某个质因数的指数超过前面所有数的最大值。而这其中最小的,一定是某素数的n次幂,整理出所有素数的n次幂,然后离线从小到大搞答案即可。因为筛素数只筛到了10000,所以素数还要判断一下1次方的。

        因为模的数是2^32所以用unsigned int 自然溢出就可以了。

        代码写得不太好,快4s了。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100000000
using namespace std;
char IsPrim[MAXN>>3];
struct Add{
    int val,co;
    bool operator < (const Add &rhs)const{
        return val<rhs.val;
    }
};
struct Query{
    int val,id,res;
};
bool cmp1(Query a,Query b){
    return a.val<b.val;
}
bool cmp2(Query a,Query b){
    return a.id<b.id;
}
Add ad[1500];
Query Q[10010];
int adcnt=0;
inline void Set_P(int x){
    int t1=x&7,t2=x>>3;
    IsPrim[t2]|=(1<<t1);
}
inline bool Get_P(int x){
    int t1=x&7,t2=x>>3;
    int ret=IsPrim[t2]&(1<<t1);
    return ret==0;
}
inline void Get_Prime(int x){
    memset(IsPrim,0,sizeof(IsPrim));
    Set_P(0);
    Set_P(1);
    for(int i=2;i*i<x;i++){
        if(!Get_P(i)) continue;
        int j=i*i;
        while(j<MAXN){
            Set_P(j);
            j+=i;
        }
        long long t=i*i;
        while(t<=MAXN){
            ad[adcnt].val=t;
            ad[adcnt++].co=i;
            t=t*i;
        }
    }
}
int main(){
    Get_Prime(MAXN);
    sort(ad,ad+adcnt);
    int T;
    scanf("%d",&T);
    for(int i=0;i<T;i++){
        scanf("%d",&Q[i].val);
        Q[i].id=i;
    }
    sort(Q,Q+T,cmp1);
    int now=0,qi=0;
    unsigned int ans=1;
    for(int i=2;i<MAXN;i++){
         if(Get_P(i))
            ans=(ans*i);
        if(now<adcnt && ad[now].val==i)
            ans=(ans*ad[now++].co);
        while(qi<T && Q[qi].val==i){
            Q[qi++].res=ans;
        }
    }
    sort(Q,Q+T,cmp2);
    for(int i=0;i<T;i++)
        printf("%u\n",Q[i].res);
    return 0;
}

H        密码

        我们可以一位一位的考虑。

        如果原串只有一个数,那只有0,有两个数,看结果串,如果结果串是0,则原串是0 1,若结果串是1,则结果串是1 0……

        对于结果串,只是一个类似于拓扑序的东西。对于第k项,可以直接用0和1来表示是k-1还是k。

我们现在把数一个一个地插入到已排好的序列中。

        dp[i][j]表示i排在第j个位置(j<=i+1),如果结果串中i-1要在i前,那么dp[i][j]就是所有i-1在j为前的和,如果i-1在j后也是一样的。

那么就有了转移方程:

        上述转移方程中涉及到了区间和,可以用前缀和的方法维护,如果用树壮数组什么的可能会增加logn的复杂度,而没完成一步然后在维护一遍只是加常数的复杂度。

        看到这个方程第i层只与i-1层相关,用滚动数组可以省以为空间,不过本题没有卡空间。

        程序中为了方便,用i+1代替了i,即数列是从1到i+1的。

#include<iostream>
#include<cstdio>
#include<cstring>
#define tp int
#define MOD 1000007
#define maxn 1010
using namespace std;
tp dp[maxn][maxn];
char ans[maxn];
int lowb(int t) {return t & (-t) ;}
tp s1[maxn],s2[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            scanf("%d",&ans[i]);
            if(ans[i]==i) ans[i]=0;
            else ans[i]=1;
        }
        n++;
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        memset(dp,0,sizeof(dp));
        dp[1][1]=1;
        for(int i=1;i<maxn;i++)
            s1[i]=1;
        for(int i=2;i<=n;i++){
            memset(s2,0,sizeof(s2));
            for(int j=1;j<=i;j++){
                int st=j,ed=i;
                if(ans[i-2]==0){
                    st=1;
                    ed=j;
                }
                int t=((s1[ed-1]-s1[st-1])%MOD+MOD)%MOD;
                dp[i][j]=t;
                s2[j]=dp[i][j];
            }
            for(int j=0;j<maxn;j++){
                s2[j]=(s2[j]+s2[j-1])%MOD;
                s1[j]=s2[j];
            }
        }
       tp sum=0;
       for(int i=1;i<=n;i++)
            sum=(sum+dp[n][i])%MOD;
        printf("%d\n",sum);
    }
    return 0;
}

I        Can you make a water problem?

        保证下车人数大于上车人数,每站所以人数一定是单调的。只要符合当前人数大于前一站上车人数即可。倒过来想,最后剩0人(不包括司机),到前一站人越多越好。

        如果有两站,下x1上y1和下x2上y2人,y1<y2,如果现所剩人数r,当y1<r<y2时,一定y1是后面一站的,而当r>=y2是这两站之前人数都是r-y1-y2+x1+x2,无所谓好坏。所以y1那站在后面一定不会吃亏。

        所以将数据按y排序,然后判断是否可行就可以了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAXN 100010
using namespace std;
struct Node{
    int x,y;
    bool operator < (const Node &rhs) const{
        return y==rhs.y ? x<rhs.x:y<rhs.y;
    }
};Node A[MAXN];
bool pd(int &r,Node X){
    if(X.y>=r) return 0;
    int b=r-X.y+X.x;
    r=b;
    if(b>X.x)return 1;
    return 0;
}
int n;
bool Gao(){
    int r=1;
    for(int i=0;i<n;i++){
        if(!pd(r,A[i]))
            return 0;
    }
    return 1;
}
int main(){
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++)
            scanf("%d%d",&A[i].x,&A[i].y);
        sort(A,A+n);
        if(Gao()) puts("Yes");
        else puts("No");
    }
}

J        输油管道

        因为这道题主干线是平行于x轴的一条直线,所以和x坐标无关,自动滤掉x。

        考虑只有两个点的情况,主干线一定在两条直线的中部,这样距离和都是一样的。

        如果再加一个点,中间的那个点一定在直线上。再加一个,直线还是在中间。

        总结出,如果有奇数个点,左右点的中位数一定在主干线上。如果有偶数个点,直线一定在中间两点之间。

        直接sort就可以过掉的。由于一开始数据逗比了的原因,我这里写了个类似于随机的快排程序,加输入挂了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<time.h>
#include<cstdlib>
#define MAXN 1000010
using namespace std;
int A[MAXN],n;
void mqsort(int left,int right){
    int l=left,r=right-1;
    int x=rand()%(right-left)+left;
    swap(A[left],A[x]);
    x=A[left];
    while(l<r){
        while(l<r && A[r]>=x) r--;
        if(l<r) A[l++]=A[r];
        while(l<r && A[l]<x) l++;
        if(l<r) A[r--]=A[l];
    }
    A[l]=x;
    if(l<n/2)
        mqsort(l+1,right);
    if(l>n/2)
        mqsort(left,l);
}
template <class T>
inline bool scan_d(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
int main(){
    srand(time(0));
    while(~scanf("%d",&n)){
        int x;
        for(int i=0;i<n;i++){
            scan_d(x);
            scan_d(A[i]);
        }
        mqsort(0,n);
        long long  ans=0;
        for(int i=0;i<n/2;i++)
            ans+=(A[n-i-1]-A[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

题目有点水,出题的时候可能有一些的方没有注意到,望大家多多吐槽啊啊啊啊啊啊啊啊。

没有更多评论
Login
LoginCancel