2011 Multi-University Training Contest 7 - Host by ECNU

2023-08-28 17:44:10

AC: F I. rank 40/88.

开场看了F发现是个简单的DP，随便写了一下WA,,,发现把样例倒着输就过不了了。。。原来是忘了最后的时候开始上课的话可能上不了多久。。。

想到一个简洁的状态方程，然后以为是单调队列优化，突然发现好像只需要求个最小值就行了。。。改改AC了。。

看榜发现I过了很多，看了一下就是个同色三角形裸题。。A了然后就没有然后了。。。

看了一下B。第一感觉KMP，感觉通配符的情况不大好处理。。。没学AC自动机。。。

C。求多边形的对称轴。。。但是枚举对称轴好像会TLE？不敢写。。。赛后发现数据水暴力也能过？另外标称是后缀数组。。膜。。。

D。感觉好像是化一化公式应该能看出什么性质？

H。树形DP？ J。dance link？

B.Wildcard(贪心+hash)

这题很骚。。就是bzoj 3507的原题。然后唯一不同的是，这题是判断通配符串是否为目标串的子串。。。

把通配符串两端各加一个*就变成了bzoj 3507...

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

char str[N], ss[N];

int hs[N], shs[N], xing[], pos, bg, ed;

struct Node{int x, len; bool flag;}node[];

int get_hash(int l, int r){return shs[r]-shs[l-]*hs[r-l+];}

bool check(int be, int L){

    int sum=;

    FOR(i,,L) if (node[i].flag) sum+=node[i].x; else sum+=node[i].len;

    if (be+sum>ed+) return false;

    FOR(i,,L) {

        if (node[i].flag) be+=node[i].x;

        else {

            if (get_hash(be,be+node[i].len-)!=node[i].x) return false;

            be+=node[i].len;

        }

    }

    return true;

}

bool sol(){

    int num, sum, l, cnt, ll;

    FOR(i,,pos) {

        if (xing[i]-xing[i-]<=) continue;

        sum=num=l=ll=cnt=;

        FOR(j,xing[i-]+,xing[i]-) {

            if (str[j]=='?') {

                ++num;

                if (l) node[++cnt].x=sum, node[cnt].len=l; node[cnt].flag=, sum=l=;

            }

            else {

                sum=sum*MOD+str[j]; ++l;

                if (num) node[++cnt].x=num, node[cnt].flag=, num=;

            }

        }

        if (l) node[++cnt].x=sum, node[cnt].len=l; node[cnt].flag=, sum=l=;

        if (num) node[++cnt].x=num, node[cnt].flag=, num=;

        while (bg<=ed&&!check(bg,cnt)) ++bg;

        if (!check(bg,cnt)) return false;

        FOR(i,,cnt) if (node[i].flag) ll+=node[i].x; else ll+=node[i].len;

        bg+=ll;

    }

    return true;

}

int main ()

{

    hs[]=; FO(i,,N) hs[i]=hs[i-]*MOD;

    while (~scanf("%s%s",ss+,str+)) {

        pos=; bg=; ed=strlen(ss+);

        for (int i=; ss[i]; ++i) shs[i]=shs[i-]*MOD+ss[i];

        int l=, r=strlen(str+);

        str[]='*'; str[++r]='*';

        int flag=;

        while (str[l]!='*'&&l<=r&&bg<=ed) {

            if (str[l]=='?'||str[l]==ss[bg]) ++l, ++bg;

            else {flag=; break;}

        }

        while (str[r]!='*'&&l<=r&&bg<=ed) {

            if (str[r]=='?'||str[r]==ss[ed]) --r, --ed;

            else {flag=; break;}

        }

        if (flag) {puts("NO"); continue;}

        FOR(i,l,r) if (str[i]=='*') xing[++pos]=i;

        if (pos==&&bg<=ed) {puts("NO"); continue;}

        puts(sol()?"YES":"NO");

    }

    return ;

}

D.Trigonometric Function(数学)

这题要放在高中我一定写的出来。。。

cos(na)化出来是一堆cos(a)和sin(a),sin(na)也是差不多。由余弦定理有cos(A)=(b^2+c^2-a^2)/(2*a*b).这tm显然是有理数。

那么只需要判断sinA,sinB,sinC是不是有理数即可。因为sinA=sqrt(1-cosA*cosA).化简这个式子然后就只需要判断一个东西是不是完全平方数就行了。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int main ()

{

    LL a, b, c, n, m, k;

    int T;

    scanf("%d",&T);

    while (T--) {

        scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&n,&m,&k);

        LL A=*b*b*c*c-(b*b+c*c-a*a)*(b*b+c*c-a*a);

        LL B=*a*a*c*c-(a*a+c*c-b*b)*(a*a+c*c-b*b);

        LL C=*a*a*b*b-(a*a+b*b-c*c)*(a*a+b*b-c*c);

        LL a1=(LL)sqrt(A), b1=(LL)sqrt(B), c1=(LL)sqrt(C);

        if (a1*a1==A&&b1*b1==B&&c1*c1==C) puts("YES");

        else puts("NO");

    }

    return ;

}

F.Sleeping(DP)

将第0分钟设置为睡觉，第n+1分钟也设置为睡觉。那么题目就是求选出n个睡觉的时刻。使得它们两两间隔要么为0，要么大于l。

然后状态dp[i][j]表示前i分钟睡了j次且第i分钟在睡觉时可以浪费的最少技能点。

那么有dp[i][j]=max(dp[i-1][j-1],dp[i-k][j-1])+a[i],(k>=l+1);

最后统计一下睡觉次数>=m浪费的最少技能点就行了。复杂度O(n^2).

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int a[N], dp[N][N];

int main ()

{

    int n, m, l;

    while (~scanf("%d%d%d",&n,&m,&l)) {

        int sum=, ans=INF;

        FOR(i,,n+) FOR(j,,n+) dp[i][j]=INF;

        FOR(i,,n) scanf("%d",a+i), sum+=a[i];

        a[n+]=; dp[][]=;

        FOR(j,,n+) {

            int mi=INF;

            FOR(i,j-,n+) {

                if (i-l->=) mi=min(mi,dp[i-l-][j-]);

                dp[i][j]=min(mi+a[i],dp[i-][j-]+a[i]);

            }

        }

        FOR(i,m,n) ans=min(ans,dp[n+][i+]);

        printf("%d\n",sum-ans);

    }

    return ;

}

H.Replica Placement(树形DP)

求满足树上每个点要求的最小代价。可以用树形DP来求出。实际上一个点的副本只与它最近的祖先有关系。那么我们可以从根dfs并记录当前的距离。

如果距离可以满足点的限制，那么有两种选择，第一种这个点不作为副本，第二种这个点作为副本。但是这样dfs会超时。因为没有保存已经求出的东西。

令dp[x][y]表示x节点以y节点为副本的最小代价。那么之后就好搞了。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Node{int q, s;}node[N];

struct Edge{int p, next, w;}edge[N];

int head[N], cnt=, root, dp[N][N];

void add_edge(int u, int v, int w){

    edge[cnt].p=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;

}

void init(){mem(head,); mem(dp,-); cnt=;}

int dfs(int x, int w, int fa){

    if (~dp[x][fa]) return dp[x][fa];

    int res=;

    for (int i=head[x]; i; i=edge[i].next) {

        int v=edge[i].p;

        if (node[v].q<w+edge[i].w) res+=(dfs(v,,v)+node[v].s);

        else res+=min(dfs(v,w+edge[i].w,fa),dfs(v,,v)+node[v].s);

    }

    return dp[x][fa]=res;

}

int main ()

{

    int T, n, fa, s, q, w;

    T=Scan();

    while (T--) {

        init();

        n=Scan();

        FOR(i,,n) {

            fa=Scan(); node[i].q=Scan(); node[i].s=Scan(); w=Scan();

            if (fa) add_edge(fa,i,w);

            else root=i;

        }

        printf("%d\n",dfs(root,,root));

    }

    return ;

}

I.Triple(补集思想)

如果把数字看成点，两个数字如果互质则连一条红边，否则连一条蓝边。那么题目就是问同色三角形有多少个。

考虑补集。那么就是求非同色三角形的个数。

对于每个顶点，统计从这个顶点出发的两条边颜色都不一样的种数。然后对于所有顶点的种数/2就是非同色三角形的个数。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int a[N], num[N];

int gcd(int x, int y){return x==?y:gcd(y%x,x);}

int main ()

{

    int T, n;

    scanf("%d",&T);

    while (T--) {

        mem(num,);

        scanf("%d",&n);

        LL ans=n*(n-)*(n-)/, res=;

        FOR(i,,n) scanf("%d",a+i);

        FOR(i,,n) FOR(j,i+,n) if (gcd(a[i],a[j])!=) ++num[i], ++num[j];

        FOR(i,,n) res+=num[i]*(n--num[i]);

        printf("%lld\n",ans-res/);

    }

    return ;

}

J.Sudoku(Dancing Links)

学完之后就是模板题了。求n阶数独的解的存在性，判断下多解就行了。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

const int MaxN=N*N*N+, MaxM=N*N*+, maxnode=MaxN*+MaxM+;

int n, Pn;

char g[][], G[][], gg[][];

int to_char(int x){return x<?x+'':x-+'A';}

struct DLX{

    int n, m, size;

    int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode];

    int H[MaxN], S[MaxM], ansd, ans[MaxN];

    void init(int _n, int _m){

        n=_n; m=_m;

        FOR(i,,m) S[i]=, U[i]=D[i]=i, L[i]=i-, R[i]=i+;

        R[m]=; L[]=m; size=m;

        FOR(i,,n) H[i]=-;

    }

    void Link(int r, int c){

        ++S[Col[++size]=c]; Row[size]=r; D[size]=D[c]; U[D[c]]=size; U[size]=c; D[c]=size;

        if (H[r]<) H[r]=L[size]=R[size]=size;

        else R[size]=R[H[r]], L[R[H[r]]]=size, L[size]=H[r], R[H[r]]=size;

    }

    void remove(int c){

        L[R[c]]=L[c]; R[L[c]]=R[c];

        for (int i=D[c]; i!=c; i=D[i]) for (int j=R[i]; j!=i; j=R[j]) U[D[j]]=U[j], D[U[j]]=D[j], --S[Col[j]];

    }

    void resume(int c){

        for (int i=U[c]; i!=c; i=U[i]) for (int j=L[i]; j!=i; j=L[j]) ++S[Col[U[D[j]]=D[U[j]]=j]];

        L[R[c]]=R[L[c]]=c;

    }

    int Dance(int d){

        if (R[]==) {

            FO(i,,d) G[(ans[i]-)/Pn/Pn][(ans[i]-)/Pn%Pn]=to_char((ans[i]-)%Pn+);

            return ;

        }

        int c=R[];

        for (int i=R[]; i!=; i=R[i]) if (S[i]<S[c]) c=i;

        remove(c);

        int res=;

        for (int i=D[c]; i!=c; i=D[i]) {

            ans[d]=Row[i];

            for (int j=R[i]; j!=i; j=R[j]) remove(Col[j]);

            res+=Dance(d+);

            if (res>=) return ;

            for (int j=L[i]; j!=i; j=L[j]) resume(Col[j]);

        }

        resume(c);

        return res;

    }

}dlx;

void place(int &r, int &c1, int &c2, int &c3, int &c4, int i, int j, int k){

    r=(i*Pn+j)*Pn+k; c1=i*Pn+j+; c2=Pn*Pn+i*Pn+k;

    c3=Pn*Pn*+j*Pn+k; c4=Pn*Pn*+((i/n)*n+(j/n))*Pn+k;

}

int main ()

{

    while (~scanf("%d",&n)) {

        Pn=n*n;

        FO(i,,Pn) scanf("%s",g[i]);

        dlx.init(Pn*Pn*Pn,Pn*Pn*);

        int r, c1, c2, c3, c4;

        FO(i,,Pn) FO(j,,Pn) FOR(k,,Pn) if (g[i][j]=='.'||g[i][j]==to_char(k)) {

            place(r,c1,c2,c3,c4,i,j,k);

            dlx.Link(r,c1); dlx.Link(r,c2); dlx.Link(r,c3); dlx.Link(r,c4);

        }

        int ans=dlx.Dance();

        if (ans==) {puts("No Solution"); continue;}

        else if (ans==) {puts("Multiple Solutions"); continue;}

        int flag=;

        FO(i,,Pn) FO(j,,Pn) gg[i][j]=G[i][j];

        FO(i,,Pn) {

            FO(j,,Pn) {

                if (g[i][j]=='.') continue;

                char tmp=g[i][j]; g[i][j]='.';

                dlx.init(Pn*Pn*Pn,Pn*Pn*);

                FO(i,,Pn) FO(j,,Pn) FOR(k,,Pn) if (g[i][j]=='.'||g[i][j]==to_char(k)) {

                    place(r,c1,c2,c3,c4,i,j,k);

                    dlx.Link(r,c1); dlx.Link(r,c2); dlx.Link(r,c3); dlx.Link(r,c4);

                }

                ans=dlx.Dance();

                g[i][j]=tmp;

                if (ans==) {puts("Not Minimal"); flag=; break;}

            }

            if (!flag) break;

        }

        if (flag) {

            FO(i,,Pn) {FO(j,,Pn) putchar(gg[i][j]); putchar('\n');}

        }

    }

    return ;

}
上一篇：[技巧篇]03.关于MyBatis的简单批量处理


下一篇：RedHat6/Centos6.5安装mongodb