2019牛客暑期多校训练营（第六场）C E H G

C Palindrome Mouse

E Androgynos

参考https://blog.csdn.net/birdmanqin/article/details/98479219这位大佬的。构造题也没什么好说的。。。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,m,mp[N][N],ans[N];

int main()
{
    int T,cas=0; cin>>T;
    while (T--) {
        scanf("%d",&n);
        printf("Case #%d: ",++cas);
        if (n%4==2 || n%4==3) { puts("No"); continue; }
        puts("Yes");
        m=n; n=n-n%4;
        memset(mp,0,sizeof(mp));
        for (int i=1;i<=m/2;i++)
            for (int j=i+1;j<=m/2;j++)
                mp[i][j]=mp[j][i]=1;
        for (int i=1;i<=n/4;i++)
            for (int j=1+n/2;j<=n/4+n/2;j++)
                mp[i][j]=mp[j][i]=1;
        for (int i=n/4+1;i<=n/2;i++)
            for (int j=n/4+n/2+1;j<=n;j++)
                mp[i][j]=mp[j][i]=1;
        
        for (int i=1;i<=n/2;i++) ans[i]=(n+1)-i;
        for (int i=n/2+1;i<=n;i++) ans[i]=i-n/2;
        ans[n+1]=n+1;
        
        if (m%4==1) {
            for (int i=1;i<=n/2;i++) mp[m][i]=mp[i][m]=1;
        }            
        
        for (int i=1;i<=m;i++) {
            for (int j=1;j<=m;j++) printf("%d",mp[i][j]);
            puts("");
        }
        printf("%d",ans[1]);
        for (int i=2;i<=m;i++) printf(" %d",ans[i]);
        puts("");
    }    
    return 0;
}

View Code

G Is Today Friday?

题意：输入n个字符串表示的日期串，问是否存在一种0-9到A-J的映射使得n个日期串都是星期五。

解法：直接暴力0-9到A-J的全排列即可，加了剪枝复杂度也不知道怎么算了反正能过qwq。然后是关于日期的几个小知识点（判断y/m/d是否合法，蔡勒公式判断y/m/d是星期几）。

然后注意输入之后日期去重减少计算量。然后要用C++14提交才能通过不知道为什么。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,p[12];
string st[N];

int getday(int y,int m,int d) {  //蔡勒公式O(1)判断日期 星期几 
    if(m==1||m==2)    m+=12,y-=1;
    int c=y/100;y=y%100;
    int week=(y+y/4+c/4-2*c+26*(m+1)/10+d-1)%7;
    return (week+7)%7;
}

int calc(int t,int &y,int &m,int &d) {  //计算得到年月日 
    for (int i=0;i<4;i++) y=y*10+p[st[t][i]-'A'+1];
    for (int i=5;i<7;i++) m=m*10+p[st[t][i]-'A'+1];
    for (int i=8;i<10;i++) d=d*10+p[st[t][i]-'A'+1];
}

int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int check(int y,int m,int d) { //判断日期的合法性 
    if((y%4==0&&y%100!=0)||y%400==0) moth[2]=29; else moth[2]=28;
    if((1600<=y and y<= 9999)&&(m>=1 and m<=12)&&(d>=1 and d<=moth[m]))    return 1;
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    int T,cas=0; cin>>T;
    while (T--) {
        cin>>n; for (int i=1;i<=n;i++) cin>>st[i];
        sort(st+1,st+n+1);
        n=unique(st+1,st+n+1)-(st+1);  //去重 
        bool ans=0;
        for (int i=1;i<=10;i++) p[i]=i-1;
        do{
            bool ok=1;
            for (int i=1;i<=n;i++) {
                    int y=0,m=0,d=0;
                    calc(i,y,m,d);
                    if (!check(y,m,d) || getday(y,m,d)!=5) { ok=0; break; }
                }
            if (ok) ans=1;    
            if (ans) break;
                
        }while(next_permutation(p+1,p+10+1));
        printf("Case #%d: ",++cas);
        if (ans) for (int i=1;i<=10;i++) printf("%d",p[i]);
        else printf("Impossible");
        puts("");
    }
    return 0;
}

View Code

H Train Driver

题意：给定无向图，第一个人在A集合选一个点，第二个人在B集合选一个点，第三个人在全集里选择一个点。然后问“三人到某一点集合的最小距离”的期望。

解法：这道题有意思，学到了新姿势。

观察到AB点集大小很小，所以可以枚举A点和B点，然后分别以A/B点为起点求到全图的最短路d1,d2，那么d[i]=d1[i]+d2[i]就是AB两点到某个点集合的最短路，然后我们在这基础上考虑到第三个点集合最短，那么因为此时我们把AB两点的计算结果计算出来了，就相当于变成了求两点最短路，不过是起点有多个(全图都是起点)的最短路而已，直接bfs就行了。

但是用优先队列的dfs会超时，我们要想办法优化。从每条边都是长度1考虑，我们熟知如果队列原本是有序的边长定长那么新加入的结点加入到队尾之后也是有序的，但是要注意到此题有多个起点，而起点并不是只相差一层的关系，所以队头拓展出来的结点有可能比队列中的元素小！怎么处理？这里用到一个比较奇妙的办法：用两个队列，一个队列拓展出来的放到另一个的队列尾，这样能保证有序。至于为什么只能感谢理解了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,m,na,nb,A[N],B[N];
LL sum,ans;
vector<int> G[N];

int d1[30][N],d2[30][N],d[N];
queue<int> q;
void bfs(int s,int dis[]) {
    dis[s]=0; q.push(s);
    while (!q.empty()) {
        int x=q.front(); q.pop();
        for (int i=0;i<G[x].size();i++) {
            int y=G[x][i];
            if (dis[y]>dis[x]+1) {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
}

queue<int> q1,q2;
int c[N],rk[N];
void solve(int s1,int s2) {
    int Max=0;
    for (int i=1;i<=n;i++) d[i]=d1[s1][i]+d2[s2][i],Max=max(Max,d[i]);
    for (int i=1;i<=Max;i++) c[i]=0;
    for (int i=1;i<=n;i++) c[d[i]]++;
    for (int i=1;i<=Max;i++) c[i]+=c[i-1];
    for (int i=1;i<=n;i++) rk[c[d[i]]--]=i;
    
    for (int i=1;i<=n;i++) q1.push(rk[i]);
    while (!q1.empty() || !q2.empty()) {
        int x;
        if (q1.size()&&(q2.empty() || d[q1.front()]<=d[q2.front()])) {
            x=q1.front(); q1.pop();
            for (int i=0;i<G[x].size();i++) {
                int y=G[x][i];
                if (d[y]>d[x]+1) {
                    d[y]=d[x]+1;
                    q2.push(y);
                }
            }
        } else {
            x=q2.front(); q2.pop();
            for (int i=0;i<G[x].size();i++) {
                int y=G[x][i];
                if (d[y]>d[x]+1) {
                    d[y]=d[x]+1;
                    q1.push(y);
                }
            }
        }
    }
    for (int i=1;i<=n;i++) ans+=d[i]; 
}

int main()
{
    int T,cas=0; cin>>T;
    while (T--) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) G[i].clear();
        sum=ans=0;
        for (int i=1;i<=m;i++) {
            int x,y; scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        scanf("%d",&na); for (int i=1;i<=na;i++) scanf("%d",&A[i]);
        scanf("%d",&nb); for (int i=1;i<=nb;i++) scanf("%d",&B[i]);
        
        for (int i=1;i<=na;i++) {
            for (int k=1;k<=n;k++) d1[i][k]=0x3f3f3f3f; bfs(A[i],d1[i]);
        }
        for (int j=1;j<=nb;j++) {
            for (int k=1;k<=n;k++) d2[j][k]=0x3f3f3f3f; bfs(B[j],d2[j]);
        }
        for (int i=1;i<=na;i++)
            for (int j=1;j<=nb;j++)
                solve(i,j);

        sum=n*na*nb;    
        LL g=__gcd(ans,sum);
        ans/=g; sum/=g;
        if (sum==1) printf("Case #%d: %lld
",++cas,ans);
        else printf("Case #%d: %lld/%lld
",++cas,ans,sum);    
    }
    return 0;
}

View Code