5.13训练的一些题解

hdu5307

一般来说一类要求满足整数等式关系才进行答案贡献的问题

没有思路的话可以考虑生成函数转化

题解是构造级数(∑i*x^si)(∑x^(-si-1))-(∑x^si)(∑(i-1)x^(-si-1)

则x^S次方前面的系数就正好是(i-j+1)，而这个式子是可以用fft快速展开的，非常巧妙

另外要注意的是，次数可能是负数所以都可以整体+Sn

同时S=0的时候需要单独考虑

还有做ftt的时候手写复数操作会比直接用complex快不少

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 typedef long long ll;
  5 typedef long double ld;
  6 const ld pi=acos(-1);
  7 struct po{
  8     ld x,y;
  9     friend po operator +(po a,po b)
 10     {
 11         return (po){a.x+b.x,a.y+b.y};
 12     }
 13     friend po operator -(po a,po b)
 14     {
 15         return (po){a.x-b.x,a.y-b.y};
 16     }
 17     friend po operator *(po a,po b)
 18     {
 19         return (po){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
 20     }
 21     void init()
 22     {
 23         x=y=0;
 24     }
 25 } a[400010],b[400010];
 26 ld ans[100010];
 27 int s[100010],r[400010],n;
 28 
 29 void fft(po *a,int n,int f)
 30 {
 31     for (int i=0; i<n; i++)
 32         if (i<r[i]) swap(a[i],a[r[i]]);
 33     for (int i=1; i<n; i<<=1)
 34     {
 35         po p=(po){cos(pi/i),sin(pi/i)*f};
 36         for (int j=0; j<n; j+=i<<1)
 37         {
 38             po w=(po){1,0};
 39             for (int k=0; k<i; k++)
 40             {
 41                 po u=a[j+k],v=w*a[j+k+i];
 42                 a[j+k]=u+v;
 43                 a[j+k+i]=u-v;
 44                 w=w*p;
 45             }
 46         }
 47     }
 48 }
 49 
 50 void calc(int m,int f)
 51 {
 52     int n=1,l=0;
 53     for (; n<=m*2; n<<=1) l++;
 54     for (int i=0; i<n; i++)
 55         r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
 56     fft(a,n,1); fft(b,n,1);
 57     for (int i=0; i<=n; i++) a[i]=a[i]*b[i];
 58     fft(a,n,-1);
 59     for (int i=1; i<=m; i++)
 60         ans[i]+=a[i+m].x/n*f;
 61     for (int i=0; i<=n; i++)
 62     {
 63          a[i].init();
 64          b[i].init();
 65     }
 66 }
 67 
 68 int main()
 69 {
 70     int cas;
 71     scanf("%d",&cas);
 72     while (cas--)
 73     {
 74         scanf("%d",&n);
 75         s[0]=0; ll s0=0,c=0;
 76         for (int i=1; i<=n; i++)
 77         {
 78             int x;
 79             scanf("%d",&x);
 80             s[i]=s[i-1]+x;
 81             if (!x)
 82             {
 83                 ++c;
 84                 s0+=c*(c+1)/2;
 85             }
 86             else c=0;
 87         }
 88         for (int i=1; i<=s[n]; i++) ans[i]=0;
 89         for (int i=1; i<=n; i++)
 90         {
 91             a[s[i]].x+=i;
 92             b[-s[i-1]+s[n]].x+=1;
 93         }
 94         calc(s[n],1);
 95         for (int i=1; i<=n; i++)
 96         {
 97             a[s[i]].x+=1;
 98             b[-s[i-1]+s[n]].x+=i-1;
 99         }
100         calc(s[n],-1);
101         printf("%lld
",s0);
102         for (int i=1; i<=s[n]; i++)
103             printf("%lld
",(ll)(ans[i]+0.5));
104     }
105 }

View Code

hdu5306

非常涨姿势的题目

由于区间取最小值不能简单的打tag，所以要考虑一些写操作

一种写法是http://www.shuizilong.com/house/archives/hdu-5306-gorgeous-sequence/

维护每个区间内有多少个结点，已被子树中的tag影响

然后每次区间取min就要在处理区间内的子树节点清除比当前修改值大的节点

据说通过均摊分析可以证明是O(nlogn)

还有一种jiry线段树，是维护最大值，严格次大值的做法……

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 typedef long long ll;
  5 struct node{int c,mx,tg,l,r; ll s;} tr[1000000*4];
  6 int n,m;
  7 void up(int i)
  8 {
  9     int l=i*2,r=i*2+1;
 10     tr[i].s=tr[l].s+tr[r].s;
 11     tr[i].c=tr[l].c+tr[r].c;
 12     tr[i].mx=max(tr[l].mx,tr[r].mx);
 13 }
 14 
 15 void cov(int i,int len,int w)
 16 {
 17     if (tr[i].tg&&tr[i].tg<=w) return;
 18     tr[i].tg=w;
 19     tr[i].s+=(ll)(len-tr[i].c)*w;
 20     if (tr[i].c<len) tr[i].mx=w;
 21     tr[i].c=len;
 22 }
 23 
 24 void push(int i,int l,int r)
 25 {
 26     if (!tr[i].tg) return;
 27     int m=(l+r)>>1;
 28     cov(i*2,m-l+1,tr[i].tg);
 29     cov(i*2+1,r-m,tr[i].tg);
 30 }
 31 
 32 void build(int i,int l,int r)
 33 {
 34     tr[i].tg=0;
 35     if (l==r)
 36     {
 37         scanf("%d",&tr[i].tg);
 38         tr[i].c=1;
 39         tr[i].mx=tr[i].s=tr[i].tg;
 40         return;
 41     }
 42     int m=(l+r)>>1;
 43     build(i*2,l,m);
 44     build(i*2+1,m+1,r);
 45     up(i);
 46 }
 47 
 48 void dfs(int i,int l,int r,int w)
 49 {
 50     if (tr[i].mx<=w) return;
 51     if (tr[i].tg>=w) tr[i].tg=0; 
 52     if (l==r)
 53     {
 54         tr[i].mx=tr[i].s=tr[i].tg;
 55         tr[i].c=(tr[i].tg!=0);
 56         return;
 57     }
 58     push(i,l,r);
 59     int m=(l+r)>>1;
 60     dfs(i*2,l,m,w);
 61     dfs(i*2+1,m+1,r,w);
 62     up(i);
 63 }
 64 
 65 void work(int i,int l,int r,int x,int y,int w)
 66 {
 67     if (tr[i].mx<=w) return;
 68     if (x<=l&&y>=r)
 69     {
 70         dfs(i,l,r,w);// 清理其他大于w的标记
 71         cov(i,r-l+1,w);
 72         return;
 73     }
 74     int m=(l+r)>>1;
 75     push(i,l,r);
 76     if (x<=m) work(i*2,l,m,x,y,w);
 77     if (y>m) work(i*2+1,m+1,r,x,y,w);
 78     up(i);
 79 }
 80 
 81 int askmx(int i,int l,int r,int x,int y)
 82 {
 83     if (x<=l&&y>=r) return tr[i].mx;
 84     int m=(l+r)>>1,s=0;
 85     push(i,l,r);
 86     if (x<=m) s=max(s,askmx(i*2,l,m,x,y));
 87     if (y>m) s=max(s,askmx(i*2+1,m+1,r,x,y));
 88     return s;
 89 }
 90 
 91 ll asks(int i,int l,int r,int x,int y)
 92 {
 93     if (x<=l&&y>=r) return tr[i].s;
 94     int m=(l+r)>>1; ll s=0;
 95     push(i,l,r);
 96     if (x<=m) s+=asks(i*2,l,m,x,y);
 97     if (y>m) s+=asks(i*2+1,m+1,r,x,y);
 98     return s;
 99 }
100 
101 int main()
102 {
103     int cas;
104     scanf("%d",&cas);
105     while (cas--)
106     {
107         scanf("%d%d",&n,&m);
108         build(1,1,n);
109         for (int i=1; i<=m; i++)
110         {
111             int ch,l,r;
112             scanf("%d%d%d",&ch,&l,&r);
113             if (ch==0)
114             {
115                 int x;
116                 scanf("%d",&x);
117                 work(1,1,n,l,r,x);
118             }
119             else {
120                 if (ch==1) printf("%d
",askmx(1,1,n,l,r));
121                 else printf("%lld
",asks(1,1,n,l,r));
122             }
123         }
124     }
125 }

View Code

hdu5304

求含有n条边的连通图个数

显然这是一个只含单环的图，我们只要穷举所有可能的环及方案数

然后把那个环缩点，这样就等价成了求生成树的个数，这是可以用基尔霍夫矩阵做的

找环可以用状压dp，设f[i][st]表示当前在i，路径走过点的集合为st

对于环，我们都是以编号最小的点为起点，这样每个环只会被统计两次

然后就是缩点求生成树的个数，图G生成树的个数是基尔霍夫矩阵（=度数矩阵[G]-邻接矩阵[G]）的任何一个n-1阶主子式的行列式的绝对值。

行列式用高斯消元求即可

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 const int mo=998244353;
  5 typedef long long ll;
  6 int c[20][20];
  7 int s[300010],f[20][300010],a[20][20],b[20],n,m;
  8 void inc(int &a,int b)
  9 {
 10     a+=b;
 11     if (a>mo) a-=mo;
 12 }
 13 
 14 ll quick(ll x,int y)
 15 {
 16     ll s=1;
 17     while (y)
 18     {
 19         if (y&1) s=s*x%mo;
 20         x=x*x%mo;
 21         y>>=1;
 22     }
 23     return s;
 24 }
 25 
 26 ll gauss(int n)
 27 {
 28     int f=1; ll ans=1;
 29     for (int i=1; i<=n; i++)
 30     {
 31         if (c[i][i]==0)
 32         {
 33             f=-f;
 34             int j=i+1;
 35             while (j<=n&&c[j][i]==0) j++;
 36             if (j>n) return 0;
 37             for (int k=i; k<=n; k++)
 38                 swap(c[i][k],c[j][k]);
 39         }
 40         ans=ans*c[i][i]%mo;
 41         ll x=quick(c[i][i],mo-2);
 42         for (int j=i+1; j<=n; j++)
 43         {
 44             ll t=x*c[j][i]%mo;
 45             for (int k=i; k<=n; k++)
 46                 c[j][k]=(c[j][k]-t*c[i][k]%mo)%mo;
 47         }
 48     }
 49     ans=(ans+mo)%mo;
 50     if (f==1) return ans;
 51     else return mo-ans;
 52 }
 53 
 54 void get()
 55 {
 56     memset(s,0,sizeof(s));
 57     memset(f,0,sizeof(f));
 58     for (int i=1; i<=n; i++) f[i][1<<(i-1)]=1;
 59     for (int st=1; st<(1<<n); st++)
 60     {
 61         int b;
 62         for (int i=1; i<=n; i++)
 63             if (st&(1<<(i-1))) {b=i;break;}
 64         for (int i=b; i<=n; i++)
 65             if (f[i][st])
 66             {
 67                 for (int j=b+1; j<=n; j++)
 68                     if (a[i][j]&&((st&(1<<(j-1)))==0)) inc(f[j][st|(1<<(j-1))],f[i][st]);
 69                 if (a[i][b]) inc(s[st],f[i][st]);
 70             }
 71     }
 72 }
 73 
 74 int main()
 75 {
 76     while (scanf("%d%d",&n,&m)!=EOF)
 77     {
 78         memset(a,0,sizeof(a));
 79         for (int i=1; i<=m; i++)
 80         {
 81             int x,y;
 82             scanf("%d%d",&x,&y);
 83             a[x][y]=a[y][x]=1;
 84         }
 85         get();
 86         int ans=0,inv=quick(2,mo-2);
 87         for (int st=1; st<(1<<n); st++)
 88         {
 89             if (!s[st]) continue;
 90             memset(b,0,sizeof(b));
 91             memset(c,0,sizeof(c));
 92             int t=1;
 93             for (int j=1; j<=n; j++)
 94                 if (st&(1<<(j-1))) b[j]=1; else b[j]=++t;
 95             if (t>=n-1) continue;
 96             for (int i=1; i<n; i++)
 97                 for (int j=i+1; j<=n; j++)
 98                     if (b[i]!=b[j]&&a[i][j])
 99                     {
100                         c[b[i]][b[i]]++;
101                         c[b[j]][b[j]]++;
102                         c[b[i]][b[j]]--;
103                         c[b[j]][b[i]]--;
104                     }
105             inc(ans,gauss(t-1)*s[st]%mo);
106             //cout <<"*"<<s[st]<<" "<<st<<" "<<endl;
107         }
108         printf("%d
",1ll*ans*inv%mo);
109     }
110 }

View Code

hdu5309

不难想到二分答案，关键是怎么验证和怎么求方案

注意到如果在第i秒嗑药，那么不管前面怎么操作，第i秒后血量

首先求出b[i]，表示在i点嗑药后能坚持到哪一秒，b[]具有单调性可以O(n)求出，顺便我们可以判断出两种poor的情形

下面在二分答案y的验证最小嗑药间隔len的时候，令d[]表示从i到n秒可以磕几次药

然后如果d[i]>d[i+1]，那么第i秒可以嗑药由此可以转移

最后只要判断d[1]是否大于d[b[0]+1]即可，因为初始最多支撑到第b[0]秒，要保证这段区间里磕了药

输出方案时由于我们已经判断出每一秒是否能嗑药了，显然我们只要从第一个能嗑药的时候往下一次找即可

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int inf=1e9+7;
 6 int nex[500010],d[500010],b[500010],q[500010],a[500010],n,m,k,t;
 7 bool check(int l)
 8 {
 9     d[n]=0;
10     for (int i=n-1; i; i--)
11         if (b[i]>n) d[i]=d[i+1]+1;
12         else if (b[i]-i<l) d[i]=d[i+1];
13         else d[i]=d[i+1]+(d[i+l]>d[b[i]+1]);
14     return d[1]>d[b[0]+1];
15 }
16 
17 void work()
18 {
19     for (int i=0,j=0; i<n; i++)
20     {
21         while (j<=n&&i*k+a[j]>0) j++;
22         b[i]=(j>n)?inf:j-1;
23         if (b[i]<=i)
24         {
25             puts("Poor Hero!");
26             return;
27         }
28     }
29     if (b[0]>n||b[b[0]]>n)
30     {
31         puts("Poor JRY!");
32         return;
33     }
34     int l=1,r=n,ans=n;
35     while (l<=r)
36     {
37         int mid=(l+r)>>1;
38         if (check(mid))
39         {
40             ans=mid;
41             l=mid+1;
42         }
43         else r=mid-1;
44     }
45     check(ans);
46     printf("%d
",ans);
47     nex[n]=0;
48     for (int i=n-1; i; i--)
49         nex[i]=(d[i]>d[i+1])?i:nex[i+1];
50     int t=0,x=nex[1];
51     while (x)
52     {
53         q[++t]=x;
54         if (b[x]>n) break;
55         if (x+ans<n) x=nex[x+ans]; else break;
56     }
57     printf("%d
",t);
58     for (int i=1; i<=t; i++)
59     {
60         printf("%d",q[i]);
61         if (i!=t) printf(" "); else puts("");
62     }
63 }
64 
65 int main()
66 {
67     while (scanf("%d%d%d",&n,&m,&k)!=EOF)
68     {
69         a[0]=m;
70         for (int i=1; i<=n; i++)
71         {
72             scanf("%d",&a[i]);
73             a[i]=a[i-1]-a[i];
74         }
75         work();
76     }
77 }

View Code