2019牛客多校第二场

比赛总结：

看错F题意@byf

要勇于打表找规律

题解(不定更新)

A EddyWalker

B EddyWalker2

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define rep(i,a,n) for (int i=a;i<n;i++)
  4 #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5 #define pb push_back
  6 #define mp make_pair
  7 #define all(x) (x).begin(),(x).end()
  8 #define fi first
  9 #define se second
 10 #define SZ(x) ((int)(x).size())
 11 typedef vector<int> VI;
 12 typedef long long ll;
 13 typedef long long LL;
 14 typedef pair<int,int> PII;
 15 const ll mod=1000000007;
 16 ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
 17 // head
 18  
 19 ll n;
 20 namespace linear_seq {
 21     const int N=10010;
 22     ll res[N],base[N],_c[N],_md[N];
 23  
 24     vector<int> Md;
 25     void mul(ll *a,ll *b,int k) {
 26         rep(i,0,k+k) _c[i]=0;
 27         rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
 28         for (int i=k+k-1;i>=k;i--) if (_c[i])
 29             rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
 30         rep(i,0,k) a[i]=_c[i];
 31     }
 32     int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
 33         ll ans=0,pnt=0;
 34         int k=SZ(a);
 35         assert(SZ(a)==SZ(b));
 36         rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
 37         Md.clear();
 38         rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
 39         rep(i,0,k) res[i]=base[i]=0;
 40         res[0]=1;
 41         while ((1ll<<pnt)<=n) pnt++;
 42         for (int p=pnt;p>=0;p--) {
 43             mul(res,res,k);
 44             if ((n>>p)&1) {
 45                 for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
 46                 rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
 47             }
 48         }
 49         rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
 50         if (ans<0) ans+=mod;
 51         return ans;
 52     }
 53     VI BM(VI s) {
 54         VI C(1,1),B(1,1);
 55         int L=0,m=1,b=1;
 56         rep(n,0,SZ(s)) {
 57             ll d=0;
 58             rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
 59             if (d==0) ++m;
 60             else if (2*L<=n) {
 61                 VI T=C;
 62                 ll c=mod-d*powmod(b,mod-2)%mod;
 63                 while (SZ(C)<SZ(B)+m) C.pb(0);
 64                 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
 65                 L=n+1-L; B=T; b=d; m=1;
 66             } else {
 67                 ll c=mod-d*powmod(b,mod-2)%mod;
 68                 while (SZ(C)<SZ(B)+m) C.pb(0);
 69                 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
 70                 ++m;
 71             }
 72         }
 73         return C;
 74     }
 75     int gao(VI a,ll n) {
 76         VI c=BM(a);
 77         c.erase(c.begin());
 78         rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
 79         return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
 80     }
 81 };
 82  
 83 int main() {
 84     vector<int>v;
 85     int t;
 86     scanf("%d",&t);
 87     int k;LL n;
 88     while(t--)
 89     {
 90         scanf("%d%lld",&k,&n);
 91         if(n==-1)
 92         {
 93             printf("%lld
",2LL*powmod(k+1,mod-2)%mod);
 94             continue;
 95         }
 96         v.clear();
 97         ll ook=powmod(k,mod-2);
 98         v.push_back(1);
 99         for(int i=1;i<=2*k+1;i++)
100         {
101             ll pa=0;
102             for(int j=max(0,i-k);j<i;j++) pa=(pa+1ll*v[j]*ook)%mod;
103             v.push_back(int(pa%mod));
104         }
105         printf("%lld
",1LL * linear_seq::gao(v,n) % mod);
106     }
107 }

View Code

C Go on Strike!

D Kth Minimum Clique

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

 1 #include<bits/stdc++.h>
 2 #define maxl 110
 3 using namespace std;
 4 
 5 int n,k;
 6 long long ans;
 7 long long a[maxl];
 8 int mp[maxl][maxl];
 9 bitset <maxl> b[maxl];
10 char ch[maxl];
11 struct node
12 {
13     long long w;
14     int id;
15     bitset <maxl> s;
16     bool operator > (const node &y)const
17     {
18         return w>y.w;
19     }
20 };
21 priority_queue<node,vector<node>,greater<node> >q;
22 
23 inline void prework()
24 {
25     scanf("%d%d",&n,&k);
26     for(int i=0;i<n;i++)
27         scanf("%lld",&a[i]);
28     for(int i=0;i<n;i++)
29     {
30         scanf("%s",ch);
31         for(int j=0;j<n;j++)
32         {
33             mp[i][j]=ch[j]-'0';
34             b[i][j]=mp[i][j];
35         }
36     }
37 }
38 
39 inline void mainwork()
40 {
41     node d;bitset <maxl> ds;
42     q.push(node{0,0,ds});
43     
44     while(k>0 && !q.empty())
45     {
46         d=q.top();q.pop();
47         k--;
48         if(!k)
49         {
50             ans=d.w;
51             return;
52         }
53         for(int i=d.id;i<n;i++)
54         if(!d.s[i] && (d.s&b[i])==d.s)
55         {
56             d.s[i]=1;
57             q.push(node{a[i]+d.w,i,d.s});
58             d.s[i]=0;
59         }
60     }
61     ans=-1;
62 }
63 
64 inline void print()
65 {
66     printf("%lld",ans);    
67 }
68 
69 int main()
70 {
71     prework();
72     mainwork();
73     print();
74     return 0;
75 }

View Code

E MAZE

F Partition problem

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 int n;
 5 long long ans;
 6 int aa[30],bb[30];
 7 int v[30][30];
 8 long long f[30][1<<18];
 9 long long sum[30];
10 int num[1<<18];
11  
12 inline void prework()
13 {
14     for(int i=0,x=1;i<18;i++,x<<=1)
15         num[x]=i;
16     scanf("%d",&n);
17     for(int i=0;i<2*n;i++)  
18         for(int j=0;j<2*n;j++)
19             scanf("%d",&v[i][j]),sum[i+1]+=v[i][j];
20     for(int i=1;i<=2*n;i++)
21         sum[i]=sum[i-1]+sum[i];
22     int l,s,d;
23     for(int i=0;i<2*n;i++)
24     {
25         l=1<<(min(2*n,18));
26         for(int j=1;j<l;j++)
27         {
28             s=j;
29             while(s)
30             {
31                 d=s&-s;
32                 f[i][j]+=v[i][num[d]];
33                 s-=d;  
34             }
35         }
36     }
37 }
38  
39 inline void dfs(int k,int as,int bs,int acnt,long long w)
40 {
41     if(acnt+2*n-1-k+1<n || k-acnt+2*n-1-k+1<n)
42         return;
43     if(w+sum[2*n]-sum[k+1-1]<ans)  
44         return;
45     if(w>ans)
46         ans=w;
47     if(k>=2*n)
48         return;
49     long long tmp=0;int tas,tbs;
50     if(k>=18)
51     {
52         aa[++aa[0]]=k;
53         tmp=w+f[k][bs];
54         for(int i=1;i<=bb[0];i++)
55             tmp+=v[k][bb[i]];
56         dfs(k+1,as,bs,acnt+1,tmp);
57         aa[aa[0]--]=0;
58          
59         bb[++bb[0]]=k;
60         tmp=w+f[k][as];
61         for(int i=1;i<=aa[0];i++)
62             tmp+=v[k][aa[i]];
63         dfs(k+1,as,bs,acnt,tmp);
64         bb[bb[0]--]=0;
65     }
66     else
67     {
68         dfs(k+1,as|(1<<k),bs,acnt+1,w+f[k][bs]);
69         dfs(k+1,as,bs|(1<<k),acnt,w+f[k][as]);
70     }
71 }
72  
73 inline void mainwork()
74 {
75     dfs(0,0,0,0,0);
76 }
77  
78 inline void print()
79 {
80     printf("%lld",ans);
81 }
82  
83 int main()
84 {
85     prework();
86     mainwork();
87     print();
88     return 0;
89 }

View Code

G Polygons

H Second Large Rectangle

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

  1 #include<bits/stdc++.h>
  2 #define maxl 1010
  3  
  4 using namespace std;
  5  
  6 int n,m,top,mx,mx1,my1,mx2,my2,secmx;
  7 int s[maxl],h[maxl],l[maxl],r[maxl];
  8 int a[maxl][maxl];
  9 char ch[maxl];
 10  
 11 inline void prework()
 12 {
 13     scanf("%d%d",&n,&m);
 14     for(int i=1;i<=n;i++)
 15     {
 16         scanf("%s",ch+1);
 17         for(int j=1;j<=m;j++)
 18             a[i][j]=ch[j]-'0';
 19     }
 20 }
 21  
 22 inline void solve1()
 23 {
 24     mx=0;int tmp;
 25     for(int i=1;i<=m;i++)
 26         h[i]=0;
 27     for(int i=1;i<=n;i++)
 28     {
 29         for(int j=1;j<=m;j++)
 30         if(a[i][j]==1)
 31             h[j]++;
 32         else
 33             h[j]=0;
 34         top=0;
 35         for(int j=1;j<=m;j++)
 36         {
 37             while(top>0 && h[s[top]]>h[j])
 38                 r[s[top]]=j-1,--top;
 39             l[j]=s[top]+1;
 40             s[++top]=j;
 41         }
 42         while(top>0)
 43             r[s[top]]=m,--top;
 44         for(int j=1;j<=m;j++)
 45         if(h[j])
 46         {
 47             tmp=h[j]*(r[j]-l[j]+1);
 48             if(tmp>mx)
 49             {
 50                 mx=tmp;
 51                 mx1=i-h[j]+1;my1=l[j];
 52                 mx2=i;my2=r[j];
 53             }
 54         }
 55     }
 56 }
 57  
 58 inline void solve2()
 59 {
 60     secmx=0;int tmp,tx1,tx2,ty1,ty2;
 61     for(int i=1;i<=m;i++)
 62         h[i]=0;
 63     for(int i=1;i<=n;i++)
 64     {
 65         for(int j=1;j<=m;j++)
 66         if(a[i][j]==1)
 67             h[j]++;
 68         else
 69             h[j]=0;
 70         top=0;
 71         for(int j=1;j<=m;j++)
 72         {
 73             while(top>0 && h[s[top]]>h[j])
 74                 r[s[top]]=j-1,--top;
 75             l[j]=s[top]+1;
 76             s[++top]=j;
 77         }
 78         while(top>0)
 79             r[s[top]]=m,--top;
 80         for(int j=1;j<=m;j++)
 81         if(h[j])
 82         {
 83             tx1=i-h[j]+1;ty1=l[j];
 84             tx2=i;ty2=r[j];
 85             tmp=h[j]*(r[j]-l[j]+1);
 86             if(mx1!=tx1 || my1!=ty1 || mx2!=tx2 || my2!=ty2)
 87                 secmx=max(tmp,secmx);
 88             secmx=max(secmx,(h[j]-1)*(r[j]-l[j]+1));
 89             secmx=max(secmx,h[j]*(r[j]-l[j]));
 90         }
 91     }
 92 }
 93  
 94 inline void mainwork()
 95 {
 96     solve1();
 97     solve2();
 98 }
 99  
100 inline void print()
101 {
102     printf("%d
",secmx);
103 }
104  
105 int main()
106 {
107     prework();
108     mainwork();
109     print();
110     return 0;  
111 }

View Code

I Inside A Rectangle

J Subarray

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

 1 //牛逼网友的J 
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 const int INF = 0x3f3f3f3f;
 6 const int MAXN = 10000000, MAXM = 1000000;
 7  
 8 int l[MAXM + 5], r[MAXM + 5], f[MAXM + 5], g[MAXM + 5];
 9 int sum[MAXN * 3 + 5], b[MAXN * 3 + 5], c[MAXN * 3 + 5];
10  
11 int main() 
12 {
13     int n;
14     scanf("%d",&n);
15     for(int i=1;i<=n;i++)
16         scanf("%d%d",&l[i],&r[i]);
17     f[1]=r[1]-l[1]+1;
18     //f[i]以i段右端点为结尾的能构造出的最大的前缀和
19     for(int i=2;i<=n;i++)
20         f[i]=max(0,f[i-1]-(l[i]-r[i-1]-1))+r[i]-l[i]+1;
21     //0：以i-1段右端点结尾的能构造出的最大的前缀和都不足够跨过[i-1,i]之间的-1
22     //f[i - 1] - (l[i] - r[i - 1] - 1)：跨过之后还剩下多少贡献给这段
23     g[n]=r[n]-l[n]+1;
24     //g[i]以i段左端点为开头的能构造出的最大的前缀和
25     for(int i=n-1;i>=1;i--)
26         g[i]=max(0,g[i+1]-(l[i+1]-r[i]-1))+r[i]-l[i]+1;
27     //ERR1(f, n);
28     //ERR1(g, n);
29     int i=1,base=10000000;
30     ll ans=0;
31     while(i<=n) 
32     {
33         int j=i+1;
34         while(j<=n && g[j]+f[j-1]>=l[j]-r[j - 1]-1) {
35             //说明这个[j-1,j]之间的-1段可以因为两侧的f[j-1]和g[j]足够大而连接起来
36             j++;
37         }
38         j--;
39         //此时j是从i开始最远能够连接到的区间
40         int left=max(0,l[i]-g[i]),right=min(1000000000-1,r[j]+f[j]);
41         //left,right是至少会产生一个贡献的范围
42         //ERR(left, right);
43         int t=i,mi=INF,mx=0;
44         sum[0]=0;
45         for(int k=left;k<=right;k++) 
46         {
47             //统计这一整段可连接区间的前缀和
48             if(k>=l[t] && k<=r[t])
49                 sum[k-left+1]=sum[k-left]+1;
50             else
51                 sum[k-left+1]=sum[k-left]-1;
52             if(k==r[t])
53                 t++;
54             mi=min(mi,sum[k-left+1]+base);
55             mx=max(mx,sum[k-left+1]+base);
56             //b记录前缀和出现过的次数
57             b[sum[k-left+1]+base]++;
58         }
59         //ERR1(sum, right);
60         //b记录前缀和出现过的次数的后缀和
61         for(int k=mx-1;k>=mi;k--)
62             b[k]+=b[k+1];
63         //包含最左侧点的贡献
64         ans+=b[base+1];
65         for(int k=left;k<=right;k++) {
66             t=sum[k-left+1]+base;
67             //t表示k位置sum的值
68             //b[t+1]比t大的值的个数
69             //c[t+1]比在k位置左侧的比t大的值的个数的lazy
70             b[t+1]-=c[t+1]; //把lazy加上去
71             c[t]+=c[t+1]+1; //lazy标记下移
72             c[t+1] = 0; //清空lazy
73             ans+=b[t+1];
74         }
75         for(int k=mi;k<=mx;k++)
76             b[k]=0,c[k]=0;
77         i=j+1;
78     }
79     printf("%lld", ans);
80     return 0;
81 }

View Code