Test question solution on October 14 (simulation + hash + XOR + 01BFS + state pressure + expected DP)

Multiple measurements do not empty, burst two lines of tears QAQ

T1 mahjong

Main idea of the title: given the cards of three colors, the points of each card are $1-9 $. Specify a set of face as: 1 Three cards 2 Same color 3 The number of points is the same or increases in sequence (e.g. 555 or 678). It is now given that $n $is $13 $or $14 $, and the requirements for $14 $cards are: 3 sets of face and two identical cards; If there are $13 $cards and one card is short of Hu, this card is called listening. If $n=13 $, all possible listening cards should be output. If not, line feed directly; If $n=14 $outputs $0 / 1 $, it indicates whether the card can be played.

First consider the case of $n=14 $: take out the same two cards and see if the remaining $12 $cards can form three groups of face; If $n=13 $, directly enumerate the listening cards, and then judge whether you can play Hu cards.

code:

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,tp,vis[15];
int hh[1505],top;
string s;
struct node
{
    int num,color,h;
}a[15],tmp[15],ans[200];
inline bool cmp(node x,node y){
    if (x.color==y.color) return x.num<y.num;
    return x.color<y.color;
}
inline bool judge(int x,int y,int z)
{
    if (tmp[x].h==tmp[y].h&&tmp[y].h==tmp[z].h) return 1;
    if (tmp[x].color==tmp[y].color&&tmp[y].color==tmp[z].color){
        if (tmp[x].num+1==tmp[y].num&&tmp[y].num+1==tmp[z].num) return 1;
    }
    return 0;
}
inline bool solve()
{
    for (int i=1;i<=14;i++)
    {
        tp=0;memset(vis,0,sizeof(vis));
        if (hh[a[i].h]<2) continue;
        int num=hh[a[i].h]-2;
        for (int j=1;j<=14;j++)
            if (a[j].h==a[i].h){
                if (num>0) num--,tmp[++tp]=a[j];
            }else tmp[++tp]=a[j];
        sort(tmp+1,tmp+tp+1,cmp);
        int j;
        for (j=1;j<=tp;j++)
        {
            if (vis[j]) continue;
            int flag=0;
            for (int k=j+1;k<=tp;k++)
            {
                if (!vis[k])
                for (int l=k+1;l<=tp;l++)
                    if (!vis[l]){
                        if (judge(j,k,l)){
                            vis[j]=vis[k]=vis[l]=1;
                            flag=1;break;
                        }
                    }
                if (flag) break;
            }
            if (!flag) break;
        }
        if (j>tp) return 1;
    }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&T);
    while(T--)
    {
        top=0;
        for (int i=1;i<=n;i++)
        {
            cin>>s;
            a[i].num=s[0]-'0';a[i].color=(int)s[1];
            a[i].h=a[i].num*100+a[i].color;hh[a[i].h]++;
        }
        if (n==14) {
            printf("%d\n",solve());
            memset(hh,0,sizeof(hh));
            continue;
        }
        for (int i=1;i<=13;i++)
        {
            if (a[i].num<9)
            {
                a[14]=a[i];a[14].num++;a[14].h+=100;
                hh[a[14].h]++;
                int flag=solve();
                if (flag&&hh[a[14].h]<=4) ans[++top]=a[14];
                hh[a[14].h]--;
            }
            if (a[i].num>1)
            {
                a[14]=a[i];a[14].num--;a[14].h-=100;
                hh[a[14].h]++;
                int flag=solve();
                if(flag&&hh[a[14].h]<=4) ans[++top]=a[14];
                hh[a[14].h]--;
            }
            a[14].num=a[i].num;a[14].color=a[i].color;
            a[14].h=a[i].h;hh[a[14].h]++;
            if (solve()&&hh[a[14].h]<=4) ans[++top]=a[14];hh[a[14].h]--;
            a[14].num=a[14].h=a[14].color=0;
        }
        sort(ans+1,ans+top+1,cmp);
        memset(hh,0,sizeof(hh));
        for (int i=1;i<=top;i++)
            if (!hh[ans[i].h]){
                hh[ans[i].h]=1;
                printf("%d%c ",ans[i].num,(char)ans[i].color);
            }
        memset(hh,0,sizeof(hh));
        cout<<endl;
    }
}

 


T2 tree

Main idea of the topic: given a tree with $n $nodes, sideband weight, $M $group query. Each time you ask whether one of all permutations composed of edge weights on the $(x,y) $path is a palindrome sequence$ n\leq 10^6,m\leq 10^7$.

The most intuitive idea must be to maintain the prefix XOR and from the root to the child nodes, but the XOR may conflict, so it needs to be maintained by hash. However, I wrote and hung up several times in the middle... It's best to turn on ull and module a large prime number.

%%%jzp taught me how to write a hash table

code:

#include<bits/stdc++.h>
typedef unsigned long long U;
using namespace std;const U B=793999;
const int N=1e6+5,K=1e6+7,M=N<<1;
int Rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Hash{
    int hd[K],t,V[N],nx[N];U W[N];
    void add(U x){
        int y=x%K;
        nx[++t]=hd[y];W[hd[y]=t]=x;
    }
    bool find(U x){
        int y=x%K;
        for (int i=hd[y];i;i=nx[i])
            if (W[i]==x) return 1;
        return 0;
    }
}hs;
int a,b,m,n,t,hd[N],V[M],W[M],nx[M],c,e[N],ans;
U g[N],h[M];
void add(int u,int v,int w){
    nx[++t]=hd[u];V[hd[u]=t]=v;W[t]=w;
}
void dfs(int u,int fa,U lst){
    h[e[u]=++c]=lst;
    for (int i=hd[u];i;i=nx[i])
        if (V[i]!=fa)
            dfs(V[i],u,g[W[i]]),
            h[++c]=g[W[i]];
}
int main(){
    n=Rd(),m=Rd();g[0]=1;hs.add(0);
    for (int i=1;i<=n;i++)
        g[i]=g[i-1]*B,hs.add(g[i]);
    for (int u,v,w,i=1;i<n;i++)
        u=Rd(),v=Rd(),w=Rd(),
        add(u,v,w),add(v,u,w);dfs(1,0,(U)0);
    for (int i=2;i<=c;i++) h[i]^=h[i-1];
    a=Rd();b=Rd();
    for (int x,y;m--;){
        x=a%n+1;y=b%n+1;
        a=666073ll*a%1000000007;
        b=233ll*b%998244353;
        ans+=hs.find(h[e[x]]^h[e[y]]);
    }
    return printf("%d\n",ans),0;
}

T3 transfer
Given $n $points, $m $edges of an undirected graph, each edge has a color. It costs $+ 1 $to walk from one edge to another with different colors. Ask the minimum cost of walking from $1 $to $n $.

Maintain a connected block for each color, with $0 $edges inside; At the same time, the points in the connection block are connected to the original $1 $edge, indicating transfer. Since the edge weight is only $01 $, you can directly $01$BFS.

code:

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=2000005;
int n,m,num,id[N],vis[N],dis[N],q[N],top;
int head[N],cnt;
vector< pair<int,int> >v[N];
struct node{
    int next,to,dis;
}edge[N*2];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void add(int from,int to,int dis)
{
    edge[++cnt]=(node){head[from],to,dis};
    head[from]=cnt;
}
inline void update(int x)
{
    for (int i=head[x];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if (dis[x]+edge[i].dis<dis[to])
        {
            dis[to]=dis[x]+edge[i].dis;
            if (edge[i].dis) q[++top]=to;
            else update(to);
        }
    }
}
int main()
{
    n=num=read();m=read();
    for (int i=1;i<=m;i++)
    {
        int x=read(),y=read(),c=read();
        v[c].push_back(make_pair(x,y));
    }
    for (int i=1;i<=1000000;i++)
        for (int j=0;j<v[i].size();j++)
        {
            int x=v[i][j].first,y=v[i][j].second;
            if (vis[x]!=i) vis[x]=i,id[x]=++num,add(num,x,1),add(x,num,0);
            if (vis[y]!=i) vis[y]=i,id[y]=++num,add(num,y,1),add(y,num,0);
            add(id[x],id[y],0);add(id[y],id[x],0);
        }
    memset(dis,0x3f,sizeof(dis));
    dis[q[top=1]=1]=0;
    for (int i=1;i<=top;i++) update(q[i]);
    printf("%d",dis[n]>=0x3f3f3f3f?-1:dis[n]);
    return 0;
}

T4 game

Given $n $strings with a length of $M $, choose one at random as the answer. A person randomly selects the number in $1-m $each time (the selected number will not be selected again). At this time, he will know the character of the corresponding position of the answer string. Ask the expected number of times$ n\leq 50,m\leq 20$.

zzz forever drop God!!!

Let $bit[i] $represent the set of strings with the same bit as itself, $sta[i] $represent the set of strings with the same bit as itself when the selection status is $I $, $siz[i] $represent how many strings can not be determined after the selection status is $I $.

$bit $can be obtained by enumerating $O(nm) $;

$sta $has transfer: $sta[i]=sta[i-lowbit(i)]\ and\ bit[lowbit(i)+1] $;

For $siz[i] $, if the current $sta [i]= 1 < < (k-1)) $(k is the string of outer enumeration, then $siz[i] + + $.

See code for the above pretreatment; With these preprocessing, we can consider transfer. Let $f[i] $indicate that the position in $I $has been asked and how many times are expected to be asked again. With transfer:

$f[s]=\frac{1}{num_t}\times \sum\limits_{t} \frac{siz[t]}{siz[j]}\times f[t]+1$

Let's talk about the meaning of $\ frac{siz[t]}{siz[j]} $: now I know that the answer is in $siz[j] $. If the answer is random, it has the probability of $\ frac{siz[t]}{siz[j]} $in $siz[t] $, which is my new addition of $1 $to determine the new range; The probability of having $1-\frac{siz[t]}{siz[j]} $is not in $t $, and $siz[j]-siz[t] $is my newly determined string, so the answer is directly determined at this time, and there is no need to transfer.

code:

#include<cstdio>
#include<iostream>
#include<cstring>
#define int long long
#define lowbit(x) x&(-x)
using namespace std;
const int M=2100005;
const int N=55;
double f[M];
int s[N][N],sta[M],bit[N],siz[M],rm[M],n,m;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
signed main()
{
    n=read();m=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) s[i][j]=read();
    for (int i=0;i<m;i++) rm[1ll<<i]=i;
    int all=(1ll<<m)-1;
    for (int i=1;i<=n;i++)
    {
        memset(bit,0,sizeof(bit));
        for (int j=1;j<=n;j++)
            for (int k=1;k<=m;k++)
                if (s[i][k]==s[j][k]) bit[k]|=1ll<<(j-1);
        siz[0]++,sta[0]=(1ll<<n)-1;
        for (int j=1;j<=all;j++)
        {
            int t=lowbit(j);
            sta[j]=sta[j-t]&bit[rm[t]+1];
            if (sta[j]!=(1ll<<(i-1))) siz[j]++;
        }
    }
    for (int j=all;j>=0;j--)
    {
        if (!siz[j]) continue;
        int sz=0;
        for (int k=1;k<=m;k++)
        {
            if ((1ll<<(k-1))&j) continue;
            int t=j|(1ll<<(k-1));
            f[j]+=siz[t]*f[t],sz++;
        }
        f[j]=f[j]/((double)sz*siz[j])+1;
    }
    printf("%.5lf",f[0]);
    return 0;
}

Tags: Algorithm Dynamic Programming Graph Theory

Posted by rubadub on Wed, 11 May 2022 10:19:54 +0300