2019牛客多校第5场

训练记录

辣鸡lfw和傻逼byf互相表演，都没看出直接暴力跑B得快速幂是1e6*1e6的复杂度，写了一万年，lfw还因为搞错了a,b顺序半天过不了样例，10次方的快速幂byf自己讲课的课件上有，然后别的队看着他课件写得，他自己不会，需要好好复习。导致后面很多很水的题没写。难顶，以后不要3个人同时做一道题。

题解

比赛链接：https://ac.nowcoder.com/acm/contest/885#question

A digits 2

输出n遍n

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n;
 5 
 6 int main()
 7 {
 8     int t;
 9     scanf("%d",&t);
10     for(int i=1;i<=t;i++)
11     {
12         scanf("%d",&n);
13         for(int j=1;j<=n;j++)
14             printf("%d",n);
15         puts("");
16     }
17     return 0;
18 }
View Code

B generator 1

题解：https://blog.csdn.net/liufengwei1/article/details/98115711

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int size=1e6+5;
 5 char n[size];
 6 int x0,x1,a,b;
 7 typedef long long LL;
 8 LL mod;
 9 struct mat
10 {
11     int m[3][3];
12     mat(){for(int i=0;i<3;i++)for(int j=0;j<3;j++) m[i][j]=0;}
13     friend mat operator*(mat x,mat y)
14     {
15         mat ans;
16         for(int i=1;i<=2;i++)
17         {
18             for(int j=1;j<=2;j++)
19             {
20                 for(int k=1;k<=2;k++)
21                 {
22                     ans.m[i][k] = (ans.m[i][k]+1LL*x.m[i][j]*y.m[j][k])%mod;
23                 }
24             }
25         }
26         return ans;
27     }
28 };
29 inline mat quick_pow(mat a,int b)
30 {
31     mat ans;
32     ans.m[1][1]=1;ans.m[2][2]=1;
33     while(b)
34     {
35         if(b&1) ans=ans*a;
36         a=a*a;
37         b>>=1;
38     }
39     return ans;
40 }
41 int main()
42 {
43     scanf("%d%d%d%d",&x0,&x1,&a,&b);
44     scanf("%s%lld",n,&mod);
45     mat ori;
46     int len =strlen(n);
47     ori.m[1][2]=1,ori.m[2][1]=b;ori.m[2][2]=a;
48     mat ans;
49     ans.m[1][1]=1;ans.m[2][2]=1;
50     for(int i=len-1;i>=0;i--)
51     {
52         ans=ans*quick_pow(ori,n[i]-'0');
53         ori=quick_pow(ori,10);
54     }
55     printf("%lld
",(1LL*x0*ans.m[1][1]+1LL*x1*ans.m[1][2])%mod);
56 }
View Code

C generator 2

https://blog.csdn.net/baiyifeifei/article/details/98263274

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int quick_pow(int a,int b,int mod)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=1LL*ans*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return ans;
}
LL n;
int x0,a,b,p;
LL v;
#define int long long
unordered_map<LL,LL> mp;
int loop,up;
void pre_BSGS(int p,int b)
{
    mp.clear();
    up=ceil(pow(p,2.0/3));
    int t=1;
    for(int i=0;i<=up;i++) 
    {
        if(i==up) loop=t;
        mp[t]=i;
        t=1LL*t*b%p;
    }
}
int BSGS(int B,int N,int P)
{
    int m=ceil(pow(p,1.0/3));
    int obj=quick_pow(N,P-2,P);
    for(int i=1;i<=m;i++)
    {
        obj=1LL*obj*loop%P;
        if(mp.count(obj))
        {
            return 1LL*i*up-mp[obj];
        }
    }
    return -1;
}
#undef int
int main()
{
    int t;
    int q;
//    freopen("c.in","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%d%d%d%d",&n,&x0,&a,&b,&p);
        LL ab_apo=1LL*b*quick_pow(a-1,p-2,p)%p;
        LL x0ab_apo=(x0+ab_apo)%p;
        LL o_b=quick_pow(b,p-2,p);
        pre_BSGS(p,a);
        scanf("%d",&q);
        while(q--)
        {
            scanf("%lld",&v);
            if(a==1)
            {
                LL ans=(1LL*(v-x0)*o_b%p+p)%p;
                printf("%lld
",ans<n?ans:-1);
                continue;
            }
            if(a==0)
            {
                if(x0==v) puts("0");
                else if(b==v) puts("1");
                else puts("-1");
                continue;
            }
            v=(v+ab_apo)%p;
            v=1LL*v*quick_pow(x0ab_apo,p-2,p)%p;
            LL ans=BSGS(a,v,p);
            printf("%d
",ans<n?ans:-1);
        }
    }
}
View Code

D generator 3

unsolved

E independent set 1

题解：https://blog.csdn.net/liufengwei1/article/details/98207215

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n,m,sum;
 5 int e[27],mi[27];
 6 char dp[1<<26];
 7 
 8 inline void prework()
 9 {
10     scanf("%d%d",&n,&m);
11     int u,v;
12     for(int i=1;i<=m;i++)
13     {
14         scanf("%d%d",&u,&v);
15         e[v]|=(1<<u);
16         e[u]|=(1<<v);
17     }
18     mi[0]=1;
19     for(int i=1;i<=n;i++)
20         mi[i]=mi[i-1]*2;
21     int s=(1<<n)-1;
22     for(int i=0;i<n;i++)
23         e[i]=s^(e[i]|mi[i]);
24 }
25 
26 inline void mainwork()
27 {
28     int s=(1<<n)-1;
29     int x,id;
30     for(int i=1;i<=s;i++)
31     {
32         x=i&-i;id=log2(x);
33         dp[i]=max(dp[i^x],(char)(dp[i&e[id]]+1));
34         sum+=dp[i];
35     }
36 }
37 
38 inline void print()
39 {
40     printf("%d",sum);
41 }
42 
43 int main()
44 {
45     prework();
46     mainwork();
47     print();
48     return 0;
49 }
View Code

F maximum clique 1

https://blog.csdn.net/baiyifeifei/article/details/98263347

做法1（二分图匹配）

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
const int maxm=5e5+5;
typedef pair<int,int> pii;
int head[maxn],to[maxm];
int nxt[maxm];
int a[maxn];
inline int lowbit(int x){return x&(-x);}
int n;
bool vis[maxn];
bool color[maxn];
int tot;
int un,vn;
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    to[tot]=v;nxt[tot]=head[u];
    head[u]=tot++;
}
int linker[maxn];
bool used[maxn];
bool dfs(int u)
{
    for(int i=head[u];i!=-1;i=nxt[i])
    {
        int v=to[i];
        if(!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }
        }
    }
    return false;
}
int hungary()
{
    int res=0;
    memset(linker,-1,sizeof(linker));
    for(int u=1;u<=un;u++)
    {
        if(color[u]!=0) continue;
        memset(used,0,sizeof(used));
        if(dfs(u)) res++;
    }
    return res;
}
 
void colormaker(int u,int col)
{
    vis[u]=true;
    color[u]=col;
    for(int i=head[u];i!=-1;i=nxt[i])
    {
        if(vis[to[i]]) continue;
        colormaker(to[i],~col);
    }
}
vector<int> ans;
queue<pii> q;
void planfinder()
{
    ans.clear();
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        if(!color[i]) continue;
        if(linker[i]!=-1) continue;
        if(vis[i]) continue;
        while(!q.empty()) q.pop();
        q.push(pii(i,0));
        while(!q.empty())
        {
            int v=q.front().first;
            int sw=q.front().second;
            vis[v]=true;
            q.pop();
            for(int j=head[v];j!=-1;j=nxt[j])
            {
                if(vis[to[j]]) continue;
                if(sw==0) {if(linker[to[j]]!=v) q.push(pii(to[j],1));}
                else {if(linker[to[j]]==v||linker[v]==to[j]) q.push(pii(to[j],0));}
            }
        }
    }
    memset(used,0,sizeof(used));
    for(int i=1;i<=n;i++) if((vis[i]&&(!color[i]))||(!vis[i]&&color[i])) used[i]=true;          
}
int main()
{
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int sign=a[i]^a[j];
            if(sign==lowbit(sign))
            {
                addedge(i,j);
                addedge(j,i);
            }
        }
    }
    memset(color,0,sizeof(color));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])colormaker(i,0);
    }
    un=vn=n;
    printf("%d
",n-hungary());
    planfinder();
    for(int i=1;i<=n;i++)
    {
        if(!used[i])
        printf("%d ",a[i]);
    }
}
View Code

做法2（网络流）

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
const int maxm=4e6+5;
const int inf=0x3f3f3f3f;
struct Edge{
    int to,nxt,cap,flow;
}edge[maxm];
int tol;
int head[maxn];
void init(){
    tol=2;
    memset(head,-1,sizeof(head));
}
inline int lowbit(int x){return x&(-x);}
void AddEdge(int u,int v,int w,int rw=0){
    edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;
    edge[tol].nxt=head[u];head[u]=tol++;
    edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0;
    edge[tol].nxt=head[v];head[v]=tol++;
}
int Q[maxn];
int dep[maxn],cur[maxn],sta[maxn];
bool bfs(int s,int t,int n){
    int front=0,tail=0;
    memset(dep,-1,sizeof(dep[0])*(n+1));
    dep[s]=0;
    Q[tail++]=s;
    while(front<tail){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            if(edge[i].cap>edge[i].flow&&dep[v]==-1){
                dep[v]=dep[u]+1;
                if(v==t) return true;
                Q[tail++]=v;
            }
        }
    }
    return false;
}
int dinic(int s,int t,int n){
    int maxflow=0;
    while(bfs(s,t,n)){
        for(int i=0;i<n;i++) cur[i]=head[i];
        int u=s,tail=0;
        while(cur[s]!=-1){
            if(u==t){
                int tp=inf;
                for(int i=tail-1;i>=0;i--)
                {
                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                }
                maxflow+=tp;
                for(int i=tail-1;i>=0;i--){
                    edge[sta[i]].flow+=tp;
                    edge[sta[i]^1].flow-=tp;
                    if(edge[sta[i]].cap-edge[sta[i]].flow==0) tail=i;
                }
                u=edge[sta[tail]^1].to;
            }
            else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
                sta[tail++]=cur[u];
                u=edge[cur[u]].to;
            }
            else{
                while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to;
                cur[u] = edge [cur[u]].nxt;
            }
        }
    }
    return maxflow;
}
bool color[maxn],vis[maxn];
int n;
int a[maxn];
void dfs2(int v)
{
    vis[v]=true;
    for(int i=head[v];i!=-1;i=edge[i].nxt)
    {
        if(edge[i].cap>edge[i].flow&&!vis[edge[i].to]) dfs2(edge[i].to); 
    }
}
void connect(int u,int v)
{
    if(color[u]>color[v]) swap(u,v);
    AddEdge(u,v,1);
}
int main()
{
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),color[i]=__builtin_popcount(a[i])%2;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int sign=a[i]^a[j];
            if(sign==lowbit(sign))
            {
                connect(i,j);
            }
        }
    }
    int s=0,t=n+1;
    for(int i=1;i<=n;i++)
    {
        if(!color[i]) AddEdge(s,i,1);
        else AddEdge(i,t,1);
    }
    printf("%d
",n-dinic(s,t,t+1));
    memset(vis,0,sizeof(vis));
    dfs2(s);
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) {if(!color[i]) vis[i]=true;else vis[i]=false;}
        else {if(!color[i]) vis[i]=false;else vis[i]=true;}
    }
        
    for(int i=1;i<=n;i++)
    {
        if(vis[i])
        printf("%d ",a[i]);
    }
    puts("");
}
View Code

G subsequence 1

基础DP题，不想写题解= =

 1 #include<bits/stdc++.h>
 2 #define maxl 3010
 3 using namespace std;
 4 
 5 const int mod=998244353;
 6 int n,m,ans;
 7 int f[maxl][maxl][2];
 8 int dp[maxl][maxl];
 9 char s[maxl],t[maxl];
10 
11 inline void prework()
12 {
13     scanf("%d%d",&n,&m);
14     scanf("%s%s",s+1,t+1);
15     for(int i=0;i<=n;i++)
16         for(int j=0;j<=n;j++)
17         {
18             f[i][j][1]=f[i][j][0]=0;
19             dp[i][j]=0;
20         }
21     for(int i=0;i<=n;i++)
22         f[i][0][0]=1,dp[i][0]=1;
23 }
24 
25 inline void mainwork()
26 {
27     for(int i=1;i<=n;i++)
28     {
29         if(s[i]!='0')
30         {
31             if(s[i]>t[1])
32             {
33                 f[i][1][1]=((f[i-1][1-1][1]+f[i-1][1-1][0])%mod+f[i-1][1][1])%mod;
34                 f[i][1][0]=f[i-1][1][0];
35             }
36             else if(s[i]==t[1])
37             {
38                 f[i][1][1]=(f[i-1][1-1][1]+f[i-1][1][1])%mod;
39                 f[i][1][0]=(f[i-1][1-1][0]+f[i-1][1][0])%mod;
40             }
41             else
42                 f[i][1][1]=f[i-1][1][1],f[i][1][0]=f[i-1][1][0];
43         }
44         else
45             f[i][1][1]=f[i-1][1][1],f[i][1][0]=f[i-1][1][0];
46         for(int j=2;j<=m;j++)
47         {
48             if(s[i]>t[j])
49             {
50                 f[i][j][1]=((f[i-1][j-1][0]+f[i-1][j-1][1])%mod+f[i-1][j][1])%mod;
51                 f[i][j][0]=f[i-1][j][0];
52             }
53             if(s[i]==t[j])
54             {
55                 f[i][j][1]=(f[i-1][j-1][1]+f[i-1][j][1])%mod;
56                 f[i][j][0]=(f[i-1][j-1][0]+f[i-1][j][0])%mod;
57             }
58             if(s[i]<t[j])
59             {
60                 f[i][j][1]=(f[i-1][j-1][1]+f[i-1][j][1])%mod;
61                 f[i][j][0]=f[i-1][j][0];
62             }
63         }
64     }
65     for(int i=1;i<=n;i++)
66     {
67         if(s[i]!='0')
68             dp[i][1]=(dp[i-1][1]+dp[i-1][1-1])%mod;
69         else
70             dp[i][1]=dp[i-1][1];
71         for(int j=2;j<=n;j++)
72             dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;
73     }
74     ans=f[n][m][1];
75     for(int i=m+1;i<=n;i++)
76         ans=(ans+dp[n][i])%mod;
77     
78 }
79 
80 inline void print()
81 {
82     printf("%d
",ans);
83 }
84 
85 int main()
86 {
87     int t;
88     scanf("%d",&t);
89     for(int i=1;i<=t;i++)
90     {
91         prework();
92         mainwork();
93         print();
94     }
95     return 0;
96 }
View Code

H subsequence 2

题解：https://blog.csdn.net/liufengwei1/article/details/98100854

 1 #include<bits/stdc++.h>
 2 #define maxl 100010
 3 using namespace std;
 4  
 5 int n,m;
 6 int pos[26][maxl];
 7 int len,mlen[26];
 8 char ch[10];
 9 char s[maxl];
10 char ans[maxl];
11 bool in[maxl];
12 bool flag;
13  
14 inline void prework()
15 {
16     scanf("%d%d",&n,&m);
17     int cnt0,cnt1;
18     memset(mlen,-1,sizeof(mlen));
19     flag=true;
20     for(int i=1;i<=m*(m-1)/2;i++)
21     {
22         scanf("%s%d",ch,&len);
23         cnt0=cnt1=0;
24         if(len>0)
25         {
26             scanf("%s",s+1);
27             for(int j=1;j<=len;j++)
28             {
29                 if(s[j]==ch[0])
30                 {
31                     cnt0++;
32                     pos[ch[0]-'a'][cnt0]+=cnt1;
33                 }
34                 else
35                 {
36                     cnt1++;
37                     pos[ch[1]-'a'][cnt1]+=cnt0;
38                 }
39             }
40         }
41         if(mlen[ch[0]-'a']==-1)
42             mlen[ch[0]-'a']=cnt0;
43         else if(mlen[ch[0]-'a']!=cnt0)
44             flag=false;
45         if(mlen[ch[1]-'a']==-1)
46             mlen[ch[1]-'a']=cnt1;
47         else if(mlen[ch[1]-'a']!=cnt1)
48             flag=false;
49     }
50 }
51  
52 inline void mainwork()
53 {
54     if(!flag) return;
55     for(int i=0;i<m;i++)
56         for(int j=1;j<=mlen[i];j++)
57         if(pos[i][j]+j<=n)
58         {    
59             if(!in[pos[i][j]+j])
60             {
61                 ans[pos[i][j]+j]='a'+i;
62                 in[pos[i][j]+j]=true;
63             }
64             else
65             {
66                 flag=false;
67                 return;
68             }
69         }
70         else
71         {
72             flag=false;
73             return;
74         }
75     for(int i=1;i<=n;i++)
76     if(!in[i])
77     {
78         flag=false;
79         return;
80     }
81 }
82  
83 inline void print()
84 {
85     if(flag)
86         for(int i=1;i<=n;i++)
87             printf("%c",ans[i]);
88     else
89         puts("-1");
90 }
91  
92 int main()
93 {
94     prework();
95     mainwork();
96     print();
97     return 0;
98 }
View Code

 I three points 1

题解：https://blog.csdn.net/liufengwei1/article/details/98179088

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3  
  4 const double eps=9e-7;
  5  
  6 double w,h;
  7 double a[4];
  8 double b[4];
  9 bool flag;
 10 struct node
 11 {
 12     double x,y;
 13     node(double a=0,double b=0)
 14     {
 15         x=a;y=b;
 16     }
 17     void transxy(double sinb,double cosb)
 18     {
 19         double tx=x,ty=y;
 20         x=tx*cosb-ty*sinb;
 21         y=tx*sinb+ty*cosb;
 22     }
 23 }ans[4];
 24  
 25 inline int sgn(double x)
 26 {
 27     if(x>-eps && x<eps) return 0;
 28     if(x>0) return 1;
 29     else    return -1;
 30 }
 31  
 32 inline void prework()
 33 {
 34     scanf("%lf%lf",&w,&h);
 35     for(int i=1;i<=3;i++)
 36         scanf("%lf",&a[i]),b[i]=a[i];
 37 }
 38  
 39 inline bool jug(double w,double h,double a,double b,double c)
 40 {
 41     double sita1=acos((a*a+c*c-b*b)/(2*a*c));
 42     double sita2=max(a>w?acos(w/a):0.0,c>w?acos(w/c)-sita1:0.0);
 43     ans[1]=node{a*cos(sita2),a*sin(sita2)};
 44     ans[2]=node{0.0,0.0};
 45     ans[3]=node{c*cos(sita1+sita2),c*sin(sita1+sita2)};
 46     for(int i=1;i<=3;i++)
 47     if(ans[i].x<=-eps || ans[i].x>=w+eps || ans[i].y<-eps || ans[i].y>h+eps)
 48         return false;
 49     return true;
 50 }
 51 
 52 inline void mainwork()
 53 {
 54     int rev;
 55     for(rev=0;rev<2;rev++)
 56     {
 57         if(jug(w,h,a[1],a[2],a[3]))
 58             break;
 59         if(jug(w,h,a[1],a[3],a[2]))
 60         {
 61             swap(ans[1],ans[2]);
 62             break;
 63         }
 64         if(jug(w,h,a[2],a[1],a[3]))
 65         {
 66             swap(ans[2],ans[3]);
 67             break;
 68         }
 69         if(jug(w,h,a[2],a[3],a[1]))
 70         {
 71             swap(ans[1],ans[2]);
 72             swap(ans[2],ans[3]);
 73             break;
 74         }
 75         if(jug(w,h,a[3],a[1],a[2]))
 76         {
 77             swap(ans[1],ans[3]);
 78             swap(ans[2],ans[3]);
 79             break;
 80         }
 81         if(jug(w,h,a[3],a[2],a[1]))
 82         {
 83             swap(ans[1],ans[3]);
 84             break;
 85         }
 86         swap(w,h);
 87     }
 88     if(rev)
 89     {
 90         for(int i=1;i<=3;i++)
 91             swap(ans[i].x,ans[i].y);
 92     }
 93 }
 94  
 95 inline void print()
 96 {
 97     for(int i=1;i<=2;i++)
 98         printf("%.9f %.9f ",ans[i].x,ans[i].y);
 99     printf("%.9f %.9f
",ans[3].x,ans[3].y);
100 }
101  
102 int main()
103 {
104     int t;
105     scanf("%d",&t);
106     for(int i=1;i<=t;i++)
107     {
108         prework();
109         mainwork();
110         print();
111     }
112     return 0;
113 }
View Code

J three points 2

unsolved

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/csushl/p/11288983.html