2017 多校联合训练 3 题解

Problem 1003

维护一个链表

链表中记录大于等于x的数

一开始链表中插入所有的数

从小到大枚举x

用双指针从左到右跳k次

做完一个x删除这个节点

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<string>
  8 #include<vector>
  9 #include<map>
 10 #include<set>
 11 #include<list>
 12 #include<queue>
 13 using namespace std;
 14 typedef long long ll;
 15 int n,k,pos[500010];
 16 list<int> s;
 17 list<int>::iterator wz[500010];
 18 int main()
 19 {
 20     int _;
 21     scanf("%d",&_);
 22     while (_--)
 23     {
 24         scanf("%d%d",&n,&k);
 25         s.clear();
 26         int i,j;
 27         int fst=0;
 28         list<int>::iterator ii;
 29         for (i=1;i<=n;i++)
 30         {
 31             int x;
 32             scanf("%d",&x);
 33             pos[x]=i;
 34             s.push_back(i);
 35             if (!fst)
 36             {
 37                 ii=s.begin();
 38                 fst=1;
 39             }
 40             else ii++;
 41             wz[i]=ii;
 42         }
 43         ll ans=0;
 44         for (i=1;i<=n;i++)
 45         {
 46             list<int>::iterator iter,iter2,iter3,iter4,iter5;
 47             iter=iter2=iter4=iter5=wz[pos[i]];
 48             int tot=0;
 49             for (j=1;j<k;j++)
 50             {
 51                 if (iter==s.begin()) break;
 52                 tot++;
 53                 iter--;
 54             }
 55             bool fg=true;
 56             int p=0;
 57             while (tot<k-1)
 58             {
 59                 iter2++;
 60                 iter4++;
 61                 if (iter2==s.end()&&tot<k-1)
 62                 {
 63                     fg=false;
 64                     break;
 65                 }
 66                 tot++;
 67                 p++;
 68             }
 69             if (!fg)
 70             {
 71                 s.erase(iter5);
 72                 continue;
 73             }
 74             for (j=1+p;j<=k;j++)
 75             {
 76                 int pre;
 77                 if (iter==s.begin())
 78                     pre=0;
 79                 else
 80                 {
 81                     iter3=iter;
 82                     iter3--;
 83                     pre=*iter3;
 84                 }
 85                 int succ;
 86                 iter4++;
 87                 if (iter4==s.end()) succ=n+1;
 88                 else succ=*iter4;
 89                 ans+=1ll*(*iter-pre)*(succ-*iter2)*i;
 90                 //cout<<i<<" "<<*iter<<" "<<pre<<" "<<succ<<" "<<*iter2<<endl;
 91                 if (succ==n+1) break;
 92                 iter++;
 93                 iter2++;
 94             }
 95             s.erase(iter5);
 96         }
 97         printf("%lld
",ans);
 98     }
 99     return 0;
100 }

View Code

Problem 1004

用2棵字典树

一棵存j左边的数，即i

一棵存j右边的数，即k

从左到右枚举j

答案加上左边符合条件的i的个数乘右边符合条件的j的个数

同时删除一个k，插入一个i

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<string>
  8 #include<vector>
  9 #include<map>
 10 #include<set>
 11 #include<queue>
 12 using namespace std;
 13 typedef long long ll;
 14 const int len=32;
 15 int _,n,a[5000100];
 16 struct ss
 17 {
 18     int num,num2;
 19     ss *a[2];
 20 };
 21 ss *root,memory[50000010];
 22 int s[35],t=0;
 23 ll sum[35][2];
 24 ss *create()
 25 {
 26     ss *p=&memory[t++];
 27     int i;
 28     for (i=0;i<2;i++)
 29             p->a[i]=NULL;
 30     p->num=0;
 31     return p;
 32 }
 33 void insert(int fg,int tot)
 34 {
 35     int i;
 36     ss *tt,*p=root;
 37     for (i=len-1;i>=0;i--)
 38     {
 39         int pos=s[i];
 40         if (p->a[pos]==NULL)
 41         {
 42             tt=create();
 43             p->a[pos]=tt;
 44         }
 45         if (p->a[!pos]==NULL)
 46         {
 47             tt=create();
 48             p->a[!pos]=tt;
 49         }
 50         ss *p1=p->a[0];
 51         ss *p2=p->a[1];
 52         p=p->a[pos];
 53         sum[i][0]-=1ll*p1->num*p2->num2;
 54         sum[i][1]-=1ll*p1->num2*p2->num;
 55         if (fg==1) p->num2+=tot;
 56         else p->num+=tot;
 57         sum[i][0]+=1ll*p1->num*p2->num2;
 58         sum[i][1]+=1ll*p1->num2*p2->num;
 59 
 60     }
 61 }
 62 ll search()
 63 {
 64     ll ret=0;
 65     int i;
 66     for (i=len-1;i>=0;i--)
 67         ret+=sum[i][s[i]];
 68     //cout<<ret<<endl;
 69     return ret;
 70 }
 71 int main()
 72 {
 73     scanf("%d",&_);
 74     root=create();
 75     while (_--)
 76     {
 77         scanf("%d",&n);
 78         int i,j;
 79         for (i=1;i<=n;i++)
 80             scanf("%d",&a[i]);
 81         for (i=1;i<=n;i++)
 82         {
 83             int l=0;
 84             int x=a[i];
 85             while (x)
 86             {
 87                 s[l++]=(x&1);
 88                 x>>=1;
 89             }
 90             for (j=l;j<len;j++)
 91                 s[j]=0;
 92             insert(1,1);
 93         }
 94         ll ans=0;
 95         for (i=1;i<=n;i++)
 96         {
 97             int l=0;
 98             int x=a[i];
 99             while (x)
100             {
101                 s[l++]=(x&1);
102                 x>>=1;
103             }
104             for (j=l;j<len;j++)
105                 s[j]=0;
106             insert(1,-1);
107             ans+=search();
108             insert(0,1);
109         }
110         printf("%lld
",ans);
111         for (i=1;i<=n;i++)
112         {
113             int l=0;
114             int x=a[i];
115             while (x)
116             {
117                 s[l++]=(x&1);
118                 x>>=1;
119             }
120             for (j=l;j<len;j++)
121                 s[j]=0;
122             insert(0,-1);
123         }
124 
125     }
126     return 0;
127 }

View Code

Problem 1005

答案为 $\sum x = 2 n w[x][f a x ] * m i n(s z x ,$

树形dp一下即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<string>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #include<queue>
12 using namespace std;
13 typedef long long ll;
14 int n,k;
15 ll ans;
16 vector<pair<int,int>> a[1000001];
17 int dfs(int u,int fa)
18 {
19     int siz=1;
20     for (auto v:a[u])
21     {
22         if (v.first==fa) continue;
23         int nsiz=dfs(v.first,u);
24         siz+=nsiz;
25         ans+=1ll*min(nsiz,k)*v.second;
26     }
27     return siz;
28 }
29 int main()
30 {
31     while (~scanf("%d%d",&n,&k))
32     {
33         int i;
34         for (i=1;i<=n;i++)
35             a[i].clear();
36         ans=0;
37         for (i=1;i<n;i++)
38         {
39             int x,y,z;
40             scanf("%d%d%d",&x,&y,&z);
41             a[x].push_back({y,z});
42             a[y].push_back({x,z});
43         }
44         dfs(1,0);
45         printf("%lld
",ans);
46     }
47     return 0;
48 }

View Code

Problem 1006

可以把每一项用二项式定理展开

用FFT优化即可

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int inf=(1<<30)-1;
  4 const int maxn=800010;
  5 #define REP(i,n) for(int i=(0);i<(n);i++)
  6 #define For(i,j,n) for(int i=(j);i<(n);i++)
  7 typedef long long ll;
  8 int n;
  9 int A[maxn<<2], B[maxn<<2];
 10 const int p=998244353;
 11 ll pow(ll a,int b,ll c)
 12 {
 13     ll ans=1;
 14     while(b)
 15     {
 16         if(b&1) ans=1ll*ans*a%c;
 17         a=1ll*a*a%c;
 18         b>>=1;
 19     }
 20     return ans;
 21 }
 22 int Pow(int a,int b){
 23     int res=1;
 24     for (;b;b>>=1,a=1ll*a*a%p) if (b&1) res=1ll*res*a%p;
 25     return res;
 26 }
 27 /*
 28 int A[maxn<<2], B[maxn<<2], C[maxn<<2];
 29 int G[30], nG[30],two[30];
 30 #define MOD P
 31 int quick(int k1,int k2){
 32     int k3=1;
 33     while (k2){
 34         if (k2&1) k3=1ll*k3*k1%MOD;
 35         k2>>=1; k1=1ll*k1*k1%MOD;
 36     }
 37     return k3;
 38 }
 39 void fft(int *x,int n,int fl=1){
 40     for (int i=(n>>1),j=1;j<n;j++){
 41         if (i<j) swap(x[i],x[j]);
 42         int k;
 43         for (k=(n>>1);i&k;i^=k,k>>=1); i^=k;
 44     }
 45     int now=0;
 46     for (int m=2;m<=n;m<<=1){
 47         int w; now++; if (fl==1) w=G[now]; else w=nG[now];
 48         for (int i=0;i<n;i+=m){
 49             int cur=1;
 50             for (int j=i;j<i+(m>>1);j++){
 51                 int u=x[j],v=1ll*x[j+(m>>1)]*cur%MOD;
 52                 x[j]=(u+v)%MOD; x[j+(m>>1)]=(u-v+MOD)%MOD;
 53                 cur=1ll*cur*w%MOD;
 54             }
 55         }
 56     }
 57 }
 58 void FFT(int *x,int *y,int *z,int len){
 59     int g = 3;
 60     int now=(MOD-1)/2,ng=quick(g,MOD-2),l=0;
 61     while (now%2==0){
 62         l++; G[l]=quick(g,now); nG[l]=quick(ng,now); two[l]=quick(1<<l,MOD-2); now>>=1;
 63     }
 64     fft(x,len); fft(y,len);
 65     for(int i = 0; i < len; ++i) z[i] = 1ll*x[i]*y[i]%MOD;
 66     fft(z,len,-1);
 67 }
 68 */
 69 int W[2][maxn];
 70 int rev[maxn];
 71 int c;
 72 void Prepare(int n){
 73     int pw=1,w0=Pow(3,(p-1)/n);
 74     For(i,0,n) W[0][i]=pw,pw=1ll*pw*w0%p;
 75     W[1][0]=1;
 76     For(i,1,n) W[1][i]=W[0][n-i];
 77     int m=0;
 78     for (;(1<<m)<n;m++);m--;
 79     For(i,1,n) rev[i]=(rev[i>>1]>>1)|(i&1)<<m;
 80 }
 81 void FFT(int *A,int n,int f){
 82     For(i,0,n) if (i<rev[i]) swap(A[i],A[rev[i]]);
 83     for (int i=1;i<n;i<<=1)
 84         for (int j=0,t=n/(i<<1);j<n;j+=i<<1)
 85             for (int k=j,l=0;k<j+i;k++,l+=t){
 86                 int x=A[k],y=1ll*W[f][l]*A[k+i]%p;
 87                 A[k]=(x+y>=p?x+y-p:x+y);
 88                 A[k+i]=(x-y+p>=p?x-y:x-y+p);
 89             }
 90     if (f){
 91         int tmp=Pow(n,p-2);
 92         For(i,0,n) A[i]=1ll*A[i]*tmp%p;
 93     }
 94 }
 95 /*
 96 void Prepare(int n){
 97     int pw=1,w0=pow(3,(P-1)/n,P);
 98     for(int i=0;i<n;i++) w[0][i]=pw,pw=1ll*pw*w0%P;
 99     w[1][0]=1;
100     for(int i=1;i<n;i++) w[1][i]=w[0][n-i];
101     int m=0;
102     for (;(1<<m)<n;m++);m--;
103     for(int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|(i&1)<<m;
104     //for(int i=1;i<n;i++) printf("r=%d
",rev[i]);
105 }
106 */
107 /*
108 void FFT(int *A,int n,int f)
109 {
110     for(int i=0;i<n;i++) 
111     if(i<r[i]) swap(a[i],a[r[i]]);
112     for(int i=0;i<n;i++)
113     printf("%d ",a[i]);
114     puts("hh");
115     /*
116     for(int i=1;i<n;i<<=1)
117     {
118         for(int j=0,t=n/(i<<1);j<n;j+=i<<1)
119         for(int k=j,l=0;k<j+i;k++,l+=t){
120             int x=a[k],y=1ll*w[f][l]*a[k+i]%P;
121             a[k]=(x+y>=P?x+y-P:x+y);
122             a[k+i]=(x-y+P>=P?x-y:x-y+P);
123         }
124     }
125     
126     for (int i=1;i<n;i<<=1)
127         for (int j=0,t=n/(i<<1);j<n;j+=i<<1)
128             for (int k=j,l=0;k<j+i;k++,l+=t){
129                 int x=a[k],y=1ll*w[f][l]*a[k+i]%P;
130                 a[k]=(x+y>=P?x+y-P:x+y);
131                 a[k+i]=(x-y+P>=P?x-y:x-y+P);
132             }
133     if(f) {
134         int tt=pow(n,P-2,P);
135         for(int i=0;i<n;i++) a[i]=1ll*a[i]*tt%P;
136     }
137 }*/
138 #define For(i,x,y) for (int i=x;i<y;i++)
139 /*
140 void CC()
141 {
142     int k;
143     for (k=1;k<=n;k<<=1);k<<=1;
144     printf("k=%d
",k);
145     II(k);
146     FFT(a,k,0);
147     FFT(b,k,0);
148     puts("a");For(i,0,k) printf("%d ",a[i]);puts("");
149     puts("b");For(i,0,k) printf("%d ",b[i]);puts("");
150     puts("c");For(i,0,k) a[i]=1ll*a[i]*b[i]%P;
151     for(int i=0;i<k;i++) a[i]=1ll*a[i]*b[i]%P;
152     FFT(a,k,1);
153     
154 }
155 */
156 ll fac[maxn],inv[maxn];
157 void ttt()
158 {
159     fac[0]=1;
160     for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%p; 
161     inv[maxn-1]=pow(fac[maxn-1],p-2,p);
162     for (int i=maxn-1;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
163 }
164 void CC()
165 {
166     int c=1;
167     for(;c<n;c<<=1);c<<=1;
168     Prepare(c);
169     FFT(A,c,0);
170     FFT(B,c,0);
171     For(i,0,c) A[i]=1ll*A[i]*B[i]%p;
172     FFT(A,c,1);
173     For(i,0,n) printf("%d ",1ll*A[i+n-1]*inv[i]%p);
174     puts("");
175 }
176 int main()
177 {    
178     ttt();
179     //for(int i=1;i<=10;i++) printf("%lld %lld
",fac[i],inv[i]);
180     while(~scanf("%d",&n))
181     {
182         ++n;
183         memset(A,0,sizeof(A));
184         memset(B,0,sizeof(B));
185         int k=1;
186         for(int i=0;i<n;i++) {
187             int x;scanf("%d",&x);
188             A[i]=1ll*fac[i]*x%p;
189         }
190         int m;
191         scanf("%d",&m);
192         int t=0;
193         for(int i=0;i<m;i++) 
194         {
195             int x;scanf("%d",&x);
196             t=(t-x+p)%p;
197         }
198         B[0]=1;
199         for(int i=1;i<n;i++)
200         {
201             B[i]=1ll*B[i-1]*t%p;
202         }
203         for(int i=0;i<n;i++)
204             B[i]=1ll*B[i]*inv[i]%p;
205         reverse(B,B+n);
206         CC();
207     }
208     return 0;
209 }

View Code

Problem 1008

所以答案就是 $n^k，快速幂即可.$

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,k;
ll mul(ll a,ll b)
{
    ll ans=0;
    while (b)
    {
        if (b&1) ans=(ans+a)%mod;
        b>>=1;
        a=(a+a)%mod;
    }
    return ans;
}
ll pow_mod(ll a,ll b)
{
    ll ans=1;
    while (b)
    {
        if (b&1) ans=mul(ans,a);
        b>>=1;
        a=mul(a,a);
    }
    return ans;
}
int main()
{
    int ca=0;
    while (~scanf("%lld%lld",&n,&k))
    {
        printf("Case #%d: %lld
",++ca,pow_mod(n,k));
    }
    return 0;
}

View Code