牛客练习赛62

A
根据Ramsey定理可知，n≥6的话，三边同色的三角形，直接输出yes
否则就n^3暴力check

#include<bits/stdc++.h>
using namespace std;
int a[15][15];
int main(){
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        memset(a,0,sizeof a);
        for(int i=1;i<=m;i++){
            int x,y;cin>>x>>y;
            if(n<6){
                a[x][y]=a[y][x]=1;
            }
        }
        if(n<6){
            int flag=0;
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    for(int k=j+1;k<=n;k++){
                        int q=a[i][j]+a[j][k]+a[k][i];
                        if(q==0 || q==3){
                            flag=1;
                        }
                    }
                }
            }
            if(flag) cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }
        else cout<<"yes"<<endl;
    }
    return 0;
}

B
从t时刻中选取(x+y)个时刻，然后走到(x,y)需要选择x个时刻向上走，所以答案就是
n^2打表后 O(1)查询即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll c[5005][5005];
int main()
{
    for(int i=0;i<=5000;i++){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<=i;j++) (c[i][j]=c[i-1][j-1]+c[i-1][j])%=mod;
    }
    int n;cin>>n;
    while(n--){
        int x,y,t;
        cin>>x>>y>>t;
        if(x+y>t) cout<<0<<endl;
        else cout<<c[t][x+y]*c[x+y][y]%mod<<endl;
    }
   return 0;
}

C
考虑一下，如果以x为根的子树内，有两个及两个以上的点染色了，那么x这个点就需要染色。




减去1的意思是dp[son][0]包括空集的情况，所以要减去，最后加1是整体都是白色为空集的情况

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct node{
    int to,ne;
}e[1<<21];
int h[1<<20],tot;
void add(int x,int y){
    e[tot].to=y;
    e[tot].ne=h[x];
    h[x]=tot++;
}
ll dp[1<<20][2];
void dfs(int x,int f){
    ll one=1,zero=0;
    for(int i=h[x];~i;i=e[i].ne){
        int to=e[i].to;
        if(f==to) continue;
        dfs(to,x);
        one=one*(dp[to][0]+dp[to][1])%mod;
        zero=(zero+dp[to][0]+dp[to][1]-1)%mod;
    }
    dp[x][0]=zero+1;
    dp[x][1]=one;
}
int main(){
    ios::sync_with_stdio(0);
    memset(h,-1,sizeof h);
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        add(x,y),add(y,x);
    }
    dfs(1,-1);
    cout<<(dp[1][0]+dp[1][1])%mod<<endl;
    return 0;
}

D
考虑一下，把a后面拼接个b，我们需要知道a和b的值以及b的长度，a拼接b后的值为 a*10^(len)+b
因为p只有200，那么对于一个数而言，最多只有p^2种情况，值取模p后范围为[0,p-1]，10^(len)取模p后范围[0,p-1]
那么我们维护一个偏序对
其中x表示当前拼接的数值取模p的结果，y为10^(len)取模p的结果，len为拼接到现在的长度。
那么把每个偏序对作为一个节点，把输入的n个点作为起始点，跑最短路即可。

#include<bits/stdc++.h>
using namespace std;
int d[205];
struct node{
    int x,y;
    int len;
    friend bool operator<(const node &a,const node &b){
        return a.len>b.len;
    }
}a[105];
int main(){
    memset(d,0x3f,sizeof d);
    int n,p;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        int sum=0,q=1;
        for(auto it:s) sum=(sum*10+it-'0')%p,q=q*10%p;
        a[i]={sum,q,s.size()};
        d[sum]=min(d[sum],a[i].len);
    }
    priority_queue<node> q;
    for(int i=1;i<=n;i++) q.push(a[i]);

    while(!q.empty()){
        node now=q.top();q.pop();
        for(int i=1;i<=n;i++){
            node next;
            next.x=(now.x*a[i].y%p+a[i].x)%p;
            next.y=(now.y*a[i].y)%p;
            if(d[next.x]>now.len+a[i].len){
                next.len=now.len+a[i].len;
                d[next.x]=next.len;
                q.push(next);
            }
        }
    }
    if(d[0]==d[200]) cout<<-1;
    else cout<<d[0];

    return 0;
}