您的位置: 首页  >  IT文章  >  NOIWC前的交流题目汇总

NOIWC前的交流题目汇总

分类: IT文章 • 2022-04-22 19:14:33

RT

2018.12.27

i207M：BZOJ 4695 最假女选手

以维护最大值为例，记录最大值和严格次大值和最大值的出现次数，然后取min的时候递归到小于最大值但大于次大值修改，这个就是最重要的地方，剩下的就是码码码调调调

  1 #include<cstdio>
  2 #include<cctype> 
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 const int N=500005,M=2000005,inf=1e9;
  7 int maxx[M],smax[M],cnt1[M];
  8 int mini[M],smin[M],cnt2[M];
  9 int a[N],laz[M]; long long val[M];
 10 int n,m,f,op,t1,t2,t3;
 11 void read(int &x)
 12 { 
 13     x=0,f=0; char ch=getchar();
 14     while(!isdigit(ch))
 15         f|=ch=='-',ch=getchar();
 16     while(isdigit(ch))
 17         x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
 18     x=f?-x:x;
 19 }
 20 void write(long long x)
 21 {
 22     if(x>9) write(x/10);
 23     putchar(x%10|48);
 24 }
 25 void w(long long x)
 26 {
 27     if(x<0) putchar('-'),x=-x;
 28     write(x),puts("");
 29 }
 30 void Pushup(int nde)
 31 {
 32     int ls=2*nde,rs=2*nde+1;
 33     val[nde]=val[ls]+val[rs];
 34     if(maxx[ls]==maxx[rs])
 35         maxx[nde]=maxx[ls],smax[nde]=max(smax[ls],smax[rs]),cnt1[nde]=cnt1[ls]+cnt1[rs];    
 36     else
 37     {
 38         if(maxx[ls]<maxx[rs]) swap(ls,rs);
 39         maxx[nde]=maxx[ls],smax[nde]=max(smax[ls],maxx[rs]),cnt1[nde]=cnt1[ls];
 40     }
 41     if(mini[ls]==mini[rs])
 42         mini[nde]=mini[ls],smin[nde]=min(smin[ls],smin[rs]),cnt2[nde]=cnt2[ls]+cnt2[rs];    
 43     else
 44     {
 45         if(mini[ls]>mini[rs]) swap(ls,rs);
 46         mini[nde]=mini[ls],smin[nde]=min(smin[ls],mini[rs]),cnt2[nde]=cnt2[ls];
 47     }
 48 }
 49 void Apply(int nde,int l,int r,int tsk,int opt)
 50 {
 51     if(!opt)
 52     {
 53         maxx[nde]+=tsk,smax[nde]+=tsk;
 54         mini[nde]+=tsk,smin[nde]+=tsk;
 55         laz[nde]+=tsk,val[nde]+=1ll*tsk*(r-l+1);
 56     }
 57     else if(opt==1)
 58     {
 59         val[nde]+=1ll*(tsk-mini[nde])*cnt2[nde];
 60         mini[nde]=tsk,maxx[nde]=max(maxx[nde],tsk);
 61         if(mini[nde]==maxx[nde])
 62         {
 63             val[nde]=1ll*tsk*(r-l+1);
 64             cnt1[nde]=cnt2[nde]=r-l+1;
 65             smax[nde]=-inf,smin[nde]=inf;
 66         }
 67         else smax[nde]=max(smax[nde],tsk);
 68     }
 69     else if(opt==2)
 70     {
 71         val[nde]-=1ll*(maxx[nde]-tsk)*cnt1[nde];
 72         maxx[nde]=tsk,mini[nde]=min(mini[nde],tsk);
 73         if(mini[nde]==maxx[nde])
 74         {
 75             val[nde]=1ll*tsk*(r-l+1);
 76             cnt1[nde]=cnt2[nde]=r-l+1;
 77             smax[nde]=-inf,smin[nde]=inf;
 78         }
 79         else smin[nde]=min(smin[nde],tsk);
 80     }
 81 }
 82 void Release(int nde,int l,int r)
 83 {
 84     int mid=(l+r)/2,ls=2*nde,rs=2*nde+1;
 85     if(laz[nde])
 86     {
 87         Apply(ls,l,mid,laz[nde],0);
 88         Apply(rs,mid+1,r,laz[nde],0),laz[nde]=0;
 89     }
 90     if(mini[ls]<mini[nde]&&smin[ls]>mini[nde]) Apply(ls,l,mid,mini[nde],1);
 91     if(mini[rs]<mini[nde]&&smin[rs]>mini[nde]) Apply(rs,mid+1,r,mini[nde],1);
 92     if(maxx[ls]>maxx[nde]&&smax[ls]<maxx[nde]) Apply(ls,l,mid,maxx[nde],2);
 93     if(maxx[rs]>maxx[nde]&&smax[rs]<maxx[nde]) Apply(rs,mid+1,r,maxx[nde],2);
 94 }
 95 void Create(int nde,int l,int r)
 96 {
 97     if(l==r)
 98     {
 99         maxx[nde]=mini[nde]=val[nde]=a[l];
100         smax[nde]=-inf,smin[nde]=inf,cnt1[nde]=cnt2[nde]=1;
101     }
102     else
103     {
104         int mid=(l+r)/2,ls=2*nde,rs=2*nde+1;
105         Create(ls,l,mid),Create(rs,mid+1,r),Pushup(nde); 
106     }
107 }
108 void Add(int nde,int l,int r,int nl,int nr,int tsk)
109 {
110     if(l>nr||r<nl)
111         return ;
112     else if(l>=nl&&r<=nr)
113         Apply(nde,l,r,tsk,0);
114     else
115     {
116         int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; Release(nde,l,r);
117         Add(ls,l,mid,nl,nr,tsk),Add(rs,mid+1,r,nl,nr,tsk),Pushup(nde);
118     }
119 }
120 void Maxi(int nde,int l,int r,int nl,int nr,int tsk)
121 {
122     if(l>nr||r<nl||mini[nde]>=tsk)
123         return ;
124     else if(l>=nl&&r<=nr&&smin[nde]>tsk)
125         Apply(nde,l,r,tsk,1);
126     else
127     {
128         int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; Release(nde,l,r);
129         Maxi(ls,l,mid,nl,nr,tsk),Maxi(rs,mid+1,r,nl,nr,tsk),Pushup(nde);
130     }
131 }
132 void Mini(int nde,int l,int r,int nl,int nr,int tsk)
133 {
134     if(l>nr||r<nl||maxx[nde]<=tsk)
135         return ;
136     else if(l>=nl&&r<=nr&&smax[nde]<tsk)
137         Apply(nde,l,r,tsk,2);
138     else
139     {
140         int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; Release(nde,l,r);
141         Mini(ls,l,mid,nl,nr,tsk),Mini(rs,mid+1,r,nl,nr,tsk),Pushup(nde);
142     }
143 }
144 long long Query(int nde,int l,int r,int nl,int nr,int opt)
145 {
146     if(l>nr||r<nl)
147     {
148         if(!opt) return 0;
149         else if(opt==1) return -inf;
150         else if(opt==2) return inf;
151     }
152     else if(l>=nl&&r<=nr)
153     {
154         if(!opt) return val[nde];
155         else if(opt==1) return maxx[nde];
156         else if(opt==2) return mini[nde];
157     }
158     else
159     {
160         int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; Release(nde,l,r);
161         if(!opt) return Query(ls,l,mid,nl,nr,opt)+Query(rs,mid+1,r,nl,nr,opt);
162         else if(opt==1) return max(Query(ls,l,mid,nl,nr,opt),Query(rs,mid+1,r,nl,nr,opt));
163         else if(opt==2) return min(Query(ls,l,mid,nl,nr,opt),Query(rs,mid+1,r,nl,nr,opt));
164     }
165 }
166 int main()
167 {
168     read(n); register int i; 
169     for(i=1;i<=n;i++) read(a[i]);
170     Create(1,1,n),read(m);
171     for(i=1;i<=m;i++)
172     {
173         read(op),read(t1),read(t2);
174         if(op==1) read(t3),Add(1,1,n,t1,t2,t3);
175         else if(op==2) read(t3),Maxi(1,1,n,t1,t2,t3);
176         else if(op==3) read(t3),Mini(1,1,n,t1,t2,t3);
177         else if(op==4) w(Query(1,1,n,t1,t2,0));
178         else if(op==5) w(Query(1,1,n,t1,t2,1));
179         else if(op==6) w(Query(1,1,n,t1,t2,2));
180     }
181     return 0;
182 }
View Code

AubRain：CF993E Nikita and Order Statistics

转换成01序列变成了子区间和问题，然后对值域上的序列反过来做卷积

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=800005,M=40;
 7 const double pai=acos(-1);
 8 struct cpx
 9 {
10     double x,y;
11 }a[N],b[N];
12 cpx operator + (cpx c1,cpx c2)
13 {
14     return (cpx){c1.x+c2.x,c1.y+c2.y};
15 }
16 cpx operator - (cpx c1,cpx c2)
17 {
18     return (cpx){c1.x-c2.x,c1.y-c2.y};
19 }
20 cpx operator * (cpx c1,cpx c2)
21 {
22     double x1=c1.x,x2=c2.x,y1=c1.y,y2=c2.y;
23     return (cpx){x1*x2-y1*y2,x1*y2+x2*y1};
24 }
25 double Sin[M],Cos[M];
26 int rev[N],lgg[N];
27 int n,x,m,nm,rd,sum;
28 void write(long long x)
29 {
30     if(x>9) write(x/10);
31     putchar(x%10|48);
32 }
33 void Prework()
34 {
35     scanf("%d%d",&n,&x),a[0].x=1;
36     for(int i=1;i<=n;i++)
37     {
38         scanf("%d",&rd);
39         sum+=rd<x,a[sum].x+=1;
40     }
41     for(int i=0;i<=n;i++)
42         b[n-i].x=a[i].x;
43     nm=n,n*=2,m=1,lgg[1]=0; while(m<=n) m<<=1;
44     for(int i=1;i<=m;i++)
45         rev[i]=(rev[i>>1]>>1)+(i&1)*(m>>1);
46     for(int i=2;i<=m;i++)
47         lgg[i]=lgg[i>>1]+1;
48     for(int i=1;i<=24;i++)
49         Sin[i]=sin(2*pai/(1<<i)),Cos[i]=cos(2*pai/(1<<i));
50 }
51 void Trans(cpx *c,int t)
52 {
53     for(int i=0;i<m;i++)
54         if(rev[i]>i) swap(c[rev[i]],c[i]);
55     for(int i=2;i<=m;i<<=1)
56     {
57         int len=i>>1;
58         cpx omg={Cos[lgg[i]],Sin[lgg[i]]*t};
59         for(int j=0;j<m;j+=i)
60         {
61             cpx ori={1,0},tmp;
62             for(int k=j;k<j+len;k++,ori=ori*omg)
63                 tmp=ori*c[k+len],c[k+len]=c[k]-tmp,c[k]=c[k]+tmp;
64         }
65     }
66     if(t==-1) for(int i=0;i<=m;i++) c[i].x/=m;
67 }
68 long long Round(double x)
69 {
70     return (long long)(x+0.5);
71 }
72 int main()
73 {
74     Prework();
75     Trans(a,1),Trans(b,1);
76     for(int i=0;i<=m;i++) a[i]=a[i]*b[i];
77     Trans(a,-1);
78     write(Round((a[nm].x-nm-1)/2)),putchar(' ');
79     for(int i=nm+1;i<=n;i++)
80         write(Round(a[i].x)),putchar(' ');
81     return 0;
82 }
View Code

ywy_c_asm：HNOI 2010 物品调度

第一问比较难，最暴力的做法是对每个位置$O(n)$枚举，然后发现$x*d$在模剩余系下会出环，于是用并查集优化，然后O(能过)(网上原来的题解都是这么写的)

可惜ztb随手卡了，数据是 1 100000 1 1 100000 100000 100000，解决方法是把环们也用并查集连起来或者用set找

第二问把所有环找出来，有空位的环答案是len-1，没有空位就把空位移过去再移出来，答案是len+1

 1 #include<set>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=100005;
 7 int T,n,q,p,m,d,s,g,emp,cnt,ans;
 8 int aset[N],pos[N],vis[N],c[N];
 9 set<pair<int,int> > st;
10 set<pair<int,int> >::iterator it; 
11 int Gcd(int a,int b)
12 {
13     return b?Gcd(b,a%b):a;
14 }
15 int Finda(int x)
16 {
17     return x==aset[x]?x:aset[x]=Finda(aset[x]);
18 }
19 void Init()
20 {
21     memset(vis,0,sizeof vis),st.clear();
22     scanf("%d%d%d%d%d%d",&n,&s,&q,&p,&m,&d);
23     for(int i=1;i<n;i++) c[i]=(1ll*c[i-1]*q+p)%m;
24     for(int i=0;i<n;i++) aset[i]=i,c[i]%=n;
25     g=Gcd(d,n),emp=s%g,cnt=n/g,ans=0;
26     for(int i=0;i<g;i++)
27         if(i==emp) 
28         {
29             aset[pos[0]=s]=Finda((s+d)%n);
30             if(cnt>1) st.insert(make_pair(i,cnt-1));
31         }
32         else st.insert(make_pair(i,cnt));
33 }
34 int main()
35 {
36     scanf("%d",&T);
37     while(T--)
38     {
39         Init();
40         for(int i=1;i<n;i++)
41         {
42             it=st.lower_bound(make_pair(c[i]%g,0));
43             if(it!=st.end())
44             {
45                 int ps=it->first,ct=it->second;
46                 st.erase(it); if(ct>1) st.insert(make_pair(ps,ct-1));
47                 pos[i]=Finda((ps+c[i]-c[i]%g)%n),aset[pos[i]]=Finda((pos[i]+d)%n); 
48             }
49             else
50             {
51                 it=st.begin(); int ps=it->first,ct=it->second;
52                 st.erase(it); if(ct>1) st.insert(make_pair(ps,ct-1));
53                 pos[i]=Finda((ps+(c[i]/g+1)*g)%n),aset[pos[i]]=Finda((pos[i]+d)%n);
54             }
55         }
56         for(int i=0;i<n;i++)
57             if(!vis[i])
58             {
59                 int nw=i,len=0;
60                 while(!vis[nw]) 
61                     len++,vis[nw]=true,nw=pos[nw];
62                 if(!i) ans+=len-1;
63                 else if(len>1) ans+=len+1;
64             }
65         printf("%d
",ans);
66     }
67     return 0;
68 }
View Code

Newwen：洛谷 4299 首都

LCT维护子树大小，用并查集维护重心，每次连起来之后根据重心的性质新的重心一定在旧的重心连成的链上，然后把这条链拎出来在(Splay)上面走即可

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=100005,inf=1e9;
  6 int fth[N],son[N][2],siz[N],rev[N];
  7 int val[N],aset[N],sizz[N],stk[N];
  8 int n,m,t1,t2,top,xrr; 
  9 char op[5];
 10 int Finda(int x)
 11 {
 12     return x==aset[x]?x:aset[x]=Finda(aset[x]);
 13 }
 14 void Pushup(int nde)
 15 {
 16     int lson=son[nde][0],rson=son[nde][1];
 17     siz[nde]=siz[lson]+siz[rson]+sizz[nde]+1;
 18 }
 19 void Release(int nde)
 20 {
 21     if(rev[nde])
 22     {
 23         int &lson=son[nde][0],&rson=son[nde][1];
 24         swap(lson,rson),rev[lson]^=1,rev[rson]^=1,rev[nde]^=1;
 25     }
 26 }
 27 bool Nottop(int nde)
 28 {
 29     int fa=fth[nde];
 30     return son[fa][0]==nde||son[fa][1]==nde;
 31 }
 32 void Rotate(int nde)
 33 {
 34     int fa=fth[nde],gr=fth[fa],isl=nde==son[fa][0];
 35     if(Nottop(fa)) son[gr][fa==son[gr][1]]=nde;
 36     fth[nde]=gr,fth[fa]=nde,fth[son[nde][isl]]=fa;
 37     son[fa][isl^1]=son[nde][isl],son[nde][isl]=fa;
 38     Pushup(fa),Pushup(nde);
 39 }
 40 void Splay(int nde)
 41 {
 42     stk[top=1]=nde;
 43     for(int i=nde;Nottop(i);i=fth[i])
 44         stk[++top]=fth[i];
 45     while(top) Release(stk[top--]);
 46     while(Nottop(nde))
 47     {
 48         int fa=fth[nde],gr=fth[fa];
 49         if(Nottop(fa))
 50             Rotate(((son[fa][0]==nde)==(son[gr][0]==fa))?fa:nde);
 51         Rotate(nde);
 52     }
 53 }
 54 void Access(int nde)
 55 {
 56     int mem=nde,lst=0;
 57     while(nde)
 58     {
 59         Splay(nde),sizz[nde]+=siz[son[nde][1]]-siz[lst];
 60         son[nde][1]=lst,Pushup(nde),lst=nde,nde=fth[nde];
 61     }
 62     Splay(mem);
 63 }
 64 void Turnroot(int nde)
 65 {
 66     Access(nde),rev[nde]^=1;
 67 }
 68 int Getroot(int nde)
 69 {
 70     Access(nde);
 71     while(son[nde][0])
 72         nde=son[nde][0];
 73     return nde;
 74 }
 75 void Split(int x,int y)
 76 {
 77     Turnroot(x),Access(y);
 78 }
 79 void Link(int x,int y)
 80 {
 81     Turnroot(x);
 82     if(Getroot(y)!=x) 
 83         sizz[y]+=siz[x],fth[x]=y,Pushup(y);
 84 }
 85 int Change(int nde)
 86 {
 87     int sum1=0,sum2=0,ret=inf,oe=siz[nde]%2,haf=siz[nde]/2;
 88     while(nde)
 89     {
 90         Release(nde);
 91         int lson=son[nde][0],rson=son[nde][1];
 92         int nsm1=sum1+siz[lson],nsm2=sum2+siz[rson];
 93         if(nsm1<=haf&&nsm2<=haf)
 94         {
 95             if(oe) {ret=nde; break;}
 96             else ret=min(ret,nde);
 97         }
 98         if(nsm1<=nsm2) sum1+=siz[lson]+sizz[nde]+1,nde=rson;
 99         else sum2+=siz[rson]+sizz[nde]+1,nde=lson;
100     }
101     Splay(ret);
102     return ret;
103 }
104 void Linka(int x,int y)
105 {
106     int fx=Finda(x),fy=Finda(y);
107     Link(x,y),Split(fx,fy); int newc=Change(fy);
108     aset[fx]=aset[fy]=aset[newc]=newc,xrr^=fx^fy^newc;
109 }
110 int main()
111 {
112     scanf("%d%d",&n,&m);
113     for(int i=1;i<=n;i++)
114         xrr^=i,aset[i]=i;
115     while(m--)
116     {
117         scanf("%s",op);
118         if(op[0]=='X')
119             printf("%d
",xrr);
120         else if(op[0]=='A')
121             scanf("%d%d",&t1,&t2),Linka(t1,t2);
122         else 
123         {
124             scanf("%d",&t1);
125             printf("%d
",Finda(t1));
126         }
127     }
128     return 0;
129 }
View Code

2018.12.29

shadowice1984：ZJOI 2018 线图

怪不得ZJOI 2018被骂，谁**考试的时候写这种题啊=。=

(本题未被制杖博主实现，同时这都是框架，具体实现......算了orz shadowice1984)

手玩发现(雾 k阶线图里原图中大小为$k+1$的联通块会合成一个点

我们考虑这样求答案：①拆联通块 ②数联通块 ③算联通块的贡献

①拆联通块

其实就是在枚举有根树(无根树也一样，但是据说有根树好写)

考虑用欧拉序+树哈希，因为爆搜可得本质不同的合法有根树只有1k多一点，所以问题不大

②数联通块

DP，设$dp(i,j)$表示$i$的子树当中匹配当前树当中$j$的子树有多少种方案，然后用一个临时数组存一下来转移

发现会重，因为被算了同一层的点数的阶乘，然后把这个去掉才对

③算联通块的贡献

这里我得先说思路，思路是玩四阶线图的公式(需要图的具体形态，然后得出一个答案)然后暴力跑五阶之后套公式(有毒

一阶线图：边数

二/三阶线图：枚举点

四阶线图：枚举边

具体的不推了

咕咕咕

制杖的ydnhaha的交流题目的解题

X_stream：CF724E Goods transportation

首先可以很容易的建出一张网络流图：把城市拆点，原点向每个城市连购买量的边，每个城市向后面的城市连c的边，每个城市再向汇点连卖出量的边，然后跑最大流

发现图太大了建不出来，考虑用其他方法求。首先转化为最小割，然后设$dp[i][j]$表示前$i$个点最终有$j$个点未与源点分割，然后$n^2$dp即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=10005;
 6 long long n,c,x,ans=1e18;
 7 long long p[N],q[N],dp[2][N];
 8 int main()
 9 {
10     scanf("%lld%lld",&n,&c);
11     for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
12     for(int i=1;i<=n;i++) scanf("%lld",&q[i]);
13     memset(dp,0x3f,sizeof dp),dp[1][0]=0;
14     for(int i=1;i<=n;i++,x^=1)
15     {
16         memset(dp[x],0x3f,sizeof dp[x]);
17         for(int j=0;j<=i;j++)
18         {
19             dp[x][j]=min(dp[x][j],dp[x^1][j]+p[i]+c*j);
20             if(j) dp[x][j]=min(dp[x][j],dp[x^1][j-1]+q[i]);
21         }
22     }
23     for(int i=0;i<=n;i++) ans=min(ans,dp[x^1][i]);
24     printf("%lld",ans);
25     return 0;
26 }
View Code

*Miracle*：AT2764 Sightseeing Plan

首先我们可以求点到点的方案数，然后我们把一个点到一个矩形的方案求个和(容斥)发现是个类似点到点的组合数。

也就是说现在我们可以O(1)求点到矩形的方案数。我们可以在中间枚举一个点，然后求到两边的方案数乘起来，但是这是$n^2$的，考虑优化

我们考虑那个点到矩形组合数的另一个意义，即点到点的方案。那我们可以分开枚举中间矩形的两条邻边上的点，每个对点间都有很多路径，我们定义路径的权值等于点数然后分开求和即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=2000005,M=2e6;
 6 const long long mod=1e9+7;
 7 long long fac[N],inv[N],xx[10],yy[10],ans;
 8 long long qpow(long long x,long long k)
 9 {
10     if(k==1) return x;
11     long long tmp=qpow(x,k/2);
12     return k%2?tmp*tmp%mod*x%mod:tmp*tmp%mod;
13 }
14 void Prework()
15 {
16     register int i; fac[0]=inv[0]=1;
17     for(i=1;i<=M;i++) fac[i]=fac[i-1]*i%mod;
18     inv[M]=qpow(fac[M],mod-2);
19     for(i=M-1;i;i--) inv[i]=inv[i+1]*(i+1)%mod;
20     for(i=1;i<=6;i++) scanf("%lld",&xx[i]);
21     for(i=1;i<=6;i++) scanf("%lld",&yy[i]);
22 }
23 long long C(int a,int b)
24 {
25     return fac[a]*inv[b]%mod*inv[a-b]%mod;
26 }
27 long long Ca(int x1,int y1,int x2,int y2,int x3,int y3)
28 {  
29     long long ret=0,lx1=x3-x2-1,lx2=x2-x1,ly1=y3-y2-1,ly2=y2-y1;
30     for(int i=x1;i<=x2;i++) ret+=C(ly1+x3-i,ly1)*C(ly2-x1+i,ly2)%mod*(ly2-x1+i+1)%mod,ret%=mod;
31     for(int i=y1;i<=y2;i++) ret+=C(lx1+y3-i,lx1)*C(lx2-y1+i,lx2)%mod*(lx2-y1+i+1)%mod,ret%=mod;
32     return ret;
33 }
34 long long Cal(int x1,int y1,int x2,int y2)
35 {
36     long long ret=0;
37     ret+=Ca(x1,y1,xx[4],yy[4],x2,y2);
38     ret-=Ca(x1,y1,xx[3]-1,yy[4],x2,y2);
39     ret-=Ca(x1,y1,xx[4],yy[3]-1,x2,y2);
40     ret+=Ca(x1,y1,xx[3]-1,yy[3]-1,x2,y2);
41     return (ret%mod+mod)%mod;
42 }
43 long long Calc(int x,int y)
44 {
45     long long ret=0;
46     ret+=Cal(x,y,xx[6]+1,yy[6]+1);
47     ret-=Cal(x,y,xx[5],yy[6]+1); 
48     ret-=Cal(x,y,xx[6]+1,yy[5]);
49     ret+=Cal(x,y,xx[5],yy[5]);
50     return (ret%mod+mod)%mod;
51 }
52 int main()
53 {
54     Prework();
55     ans+=Calc(xx[2],yy[2]);
56     ans-=Calc(xx[1]-1,yy[2]);
57     ans-=Calc(xx[2],yy[1]-1);
58     ans+=Calc(xx[1]-1,yy[1]-1);
59     printf("%lld",(ans%mod+mod)%mod);
60     return 0;
61 }
View Code

2018.12.31

i207M：CF666E

广义后缀自动机+线段树合并

咕咕咕，现在还写不动，先加入字符串题单里

AubRain：Nowcoder 272D Where are you

此题出现了各种做法，下面按我认为的优秀程度升序排序

所有算法都先对边升序排序

有毒的标算：每次把一个权值的边都扔进去，对它们形成的联通块跑Tarjan，感觉非常不好写

zyz&ztb的做法：在最小生成树上差分，枚举非树边，对每个点用某个数据结构维护有哪些边被删了，最后DFS一遍统计答案

Winniechen&Suika的做法：枚举非树边，直接在最小生成树上暴力跳，跳完之后用并查集把儿子连到父亲上去，因为边权排过序了所以没问题

像我这种不会想写数据结构肯定写最后一种了2333

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=1000005;
 6 struct a
 7 {
 8     int x,y,val;
 9 }mst[N];
10 bool cmp(a xx,a yy)
11 {
12     return xx.val<yy.val;
13 }
14 int n,m,www,cnt,ans;
15 int p[N],noww[2*N],goal[2*N],val[2*N],idx[2*N];
16 int aset[N],used[N],evl[N],eid[N],exi[N],far[N],dep[N];
17 int Finda(int x)
18 {
19     return x==aset[x]?x:aset[x]=Finda(aset[x]);
20 }
21 void Link(int f,int t,int v,int d)
22 {
23     noww[++cnt]=p[f],p[f]=cnt;
24     goal[cnt]=t,val[cnt]=v,idx[cnt]=d;
25 }
26 void DFS(int nde,int fth,int dth)
27 {
28     far[nde]=fth,dep[nde]=dth;
29     for(int i=p[nde];i;i=noww[i])
30         if(goal[i]!=fth)
31         {
32             evl[goal[i]]=val[i];
33             eid[goal[i]]=idx[i];
34             DFS(goal[i],nde,dth+1);
35         }
36 }
37 int main()
38 {
39     scanf("%d%d%d",&n,&m,&www),cnt=1;
40     for(int i=1;i<=m;i++)
41         scanf("%d%d%d",&mst[i].x,&mst[i].y,&mst[i].val);
42     sort(mst+1,mst+1+m,cmp);
43     for(int i=1;i<=n;i++) aset[i]=i;
44     for(int i=1,j=0;i<=m&&j<=n-2;i++)
45     {
46         int tx=mst[i].x,ty=mst[i].y,va=mst[i].val;
47         int fx=Finda(tx),fy=Finda(ty);
48         if(fx!=fy) 
49         {
50             Link(tx,ty,va,i),Link(ty,tx,va,i);
51             j++,used[i]=true,exi[i]=true,aset[fx]=fy;
52         }
53     }
54     DFS(1,0,1);
55     for(int i=1;i<=n;i++) aset[i]=i;
56     for(int i=1;i<=m;i++)
57         if(!used[i])
58         {
59             int tx=mst[i].x,ty=mst[i].y,va=mst[i].val;
60             while(Finda(tx)!=Finda(ty))
61             {
62                 if(dep[tx]<dep[ty]) swap(tx,ty);
63                 if(evl[tx]==va) exi[eid[tx]]=false;
64                 aset[Finda(tx)]=Finda(far[tx]),tx=Finda(far[tx]);
65             }
66         }
67     for(int i=1;i<=m;i++) ans+=exi[i];
68     printf("%d",ans);
69     return 0;
70 }
View Code

ywy_c_asm：不知道在哪看到的题

给你一个序列a：$a[1]=1,a[2n]=-a[n],a[2n-1]=-1^{n+1}a[n]$

多次询问某一项或前缀和，询问项不超过long long

直接打表找规律

看到这种每次从n推出来2*n和2*n±1的应该向二叉树上想，我们直接在二叉树上$dp$就可以了

Youngneal：LOJ 541 七曜圣贤

建议出题人重修语文，我反正没看出来魔理沙哪聪明了，那个序列的描述方法感觉更**麻烦了

另外这是什么啊↓

inline int read(int &x){scanf("%d",&x);return x;}//=。=？？？

不过题还不错

要求维护一个集合，支持插入/删除并丢进另一个集合/找回另一个集合里最早出现的数，每次操作之后询问集合的mex

可能一开始没什么头绪，但是有一个部分分可以带来一些启示：d=1的时候mex显然是单调的，直接模拟即可

但是我们发现因为有删除这个操作mex不是单调的，所以需要拿某个东西维护丢出去的最小的红茶和原本的mex取min做答案，还有这个数据范围明显要我们$O(n)$做......

我们发现如果有一个编号大的红茶在一个编号小的红茶之前被丢出去了，那么它会被先捡回来，不会产生贡献，所以用一个单调队列维护上面那个东西即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define uint unsigned int
 5 using namespace std;
 6 const int N=2000005,mod=998244353;
 7 struct str
 8 {
 9     uint seed,noww,ans; 
10     int n,a,b,c,d,tea,mex,hd1,tl1,hd2,tl2;
11     int p[N],out[N],inc[N],deq[N],que[N];
12     uint Rand()
13     {
14         seed^=seed<<13;
15         seed^=seed>>17;
16         seed^=seed<<5;
17         return seed;
18     }
19     void Init()
20     {
21         scanf("%d%u%d%d%d%d",&n,&seed,&a,&b,&c,&d);
22         memset(inc,0,sizeof inc),memset(out,0,sizeof out);
23         for(int i=1;i<=n;i++) p[i]=(Rand()%c)?Rand()%b:-1;
24         for(int i=0;i<=a;i++) inc[i]=true;
25         ans=0,mex=a+1,hd1=hd2=0,tl1=tl2=-1;
26     }
27     void Answer(int num)
28     {
29         ans^=1ll*num*(num+7)%mod*noww%mod;
30     }
31     void Update()
32     {
33         noww=(hd1<=tl1)?min(mex,deq[hd1]):mex;
34     }
35     bool Check()
36     {
37         if(hd2<=tl2&&!d)
38         {
39             if(hd1<=tl1&&deq[hd1]==que[hd2]) hd1++;
40             out[que[hd2++]]=false,Update(); return true;
41         }
42         return false;
43     }
44     void Trans()
45     {
46         for(int i=1;i<=n;i++)
47         {
48             tea=p[i],noww=0;
49             if(~tea)
50             {
51                 if(!inc[tea]) 
52                 {
53                     inc[tea]=true;
54                     while(inc[mex]) mex++;
55                     Update();
56                 }
57                 else if(inc[tea]&&!out[tea]&&!d)
58                 {
59                     out[tea]=true,que[++tl2]=tea;
60                     while(hd1<=tl1&&tea<=deq[tl1]) tl1--; 
61                     deq[++tl1]=tea,Update();
62                 }
63                 else if(Check());
64             }
65             else if(Check()); 
66             Answer(i);
67         }
68     }
69     void Output()
70     {
71         printf("%u
",ans);
72     }
73 }Q;
74 int T;
75 int main()
76 {
77     scanf("%d",&T);
78     while(T--)
79         Q.Init(),Q.Trans(),Q.Output();
80     return 0;
81 }
View Code

2019.1.8

shadowice1984的题因为过于毒瘤并没有讲完就被打断了=。=

我的

X_stream：NOI 2008 糖果雨

(开始口胡)

看起来是个某数据结构维护函数的东西

容易想到云朵的运动以len*2为周期，以二元组$(lt,rt)$存储每一朵云，表示在(周期的)$lt$时刻这朵云到达区间的左端点，$rt$就是这朵云的长度。这样我们就将云抽象成了平面上的点。

这样画一画可以发现我们每次询问是询问一个被一个坐标轴截掉的五边形里的点数，因为是被截成五边形我们现把它补成平行四边形，然后发现边的斜率是±1，再类似切比雪夫距离转曼哈顿距离那样转成矩形，用二维树状数组维护即可

注意边界(树状数组下标不能为零，还有r==len时的特殊情况)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=2005,M=1e6+6;
 6 struct a
 7 {
 8     int lt,rt;
 9 }cld[M];
10 int bit[2][N][2*N];
11 int n,t,l,r,c,d,op,mx1,mx2,len,ans;
12 void Change(int o,int x,int y,int z)
13 {
14     x++,y++;
15     for(int i=x;i<=mx1;i+=i&-i)
16         for(int j=y;j<=mx2;j+=j&-j)
17             bit[o][i][j]+=z;
18 }    
19 int Query(int o,int x,int y)
20 {
21     int ret=0;
22     x=min(x+1,mx1),y=min(y+1,mx2);
23     if(x>0&&y>0)
24         for(int i=x;i;i-=i&-i)
25             for(int j=y;j;j-=j&-j)
26                 ret+=bit[o][i][j];
27     return ret;
28 }
29 int Ask(int o,int x1,int y1,int x2,int y2)
30 {
31     int ret=0; x1--,y1--;
32     ret+=Query(o,x2,y2);
33     ret-=Query(o,x1,y2);
34     ret-=Query(o,x2,y1);
35     ret+=Query(o,x1,y1);
36     return ret;
37 }
38 int main()
39 {
40     scanf("%d%d",&n,&len);
41     mx1=len*2,mx2=mx1*2;
42     for(int i=1;i<=n;i++)
43     {
44         scanf("%d",&op);
45         if(op==1)
46         {
47             scanf("%d%d%d%d%d",&t,&c,&l,&r,&d);
48             int ll=(t-d*l+mx1)%mx1,rr=r-l;
49             cld[c].lt=ll,cld[c].rt=rr;
50             Change(0,ll,ll+rr,1),Change(1,ll,rr-ll+mx1,1);
51         }
52         else if(op==2)
53         {
54             scanf("%d%d%d",&t,&l,&r),ans=0,t%=mx1;
55             ans+=Ask(0,t,l+t,r+t,mx2),ans+=Ask(0,0,l+t-mx1,r+t-mx1-(r==len),mx2);
56             ans+=Ask(1,t-r+mx1+(r==len),l-t,mx1,mx2),ans+=Ask(1,t-r,l-t+mx1,t-1,mx2);
57             printf("%d
",ans);
58         }
59         else if(op==3)
60         {
61             scanf("%d%d",&t,&c);
62             int ll=cld[c].lt,rr=cld[c].rt;
63             Change(0,ll,ll+rr,-1),Change(1,ll,rr-ll+mx1,-1);
64         }
65     }
66     return 0;
67 }
View Code

*Miracle*：PKUWC 2018 随机算法

首先转化成计数问题

设$dp[i][j]$表示$i$这个集合“被考虑过”，其独立集大小为$j$的方案数，其中“被考虑过”表示这个集合里所有的点要么在已经在独立集里要么和独立集相连。转移是记录每个点的连通性lnk，枚举没有“被考虑过”的点$k$转移

$dp[i|lnk[k]][j+1]+=dp[i][j]*P(n-siz[i]-1,siz[i-(lnk[k]&i)])$

比较好理解的转移，其中$siz[i]$表示i集合中的点数，P是排列，因为跑不满所以$O(n^22^n)$可以卡过

更好的做法是再开一个数组记录某个状态下独立集的大小，当点数被更新时重置计数为零即可，省掉一维，复杂度$O(n2^n)$比较正确

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=20,S=(1<<N)+N,mod=998244353;
 6 int lnk[N],fac[N],inv[N],dp[S],mx[S],siz[S],n,m,t1,t2,all;
 7 void exGCD(int a,int b,int &x,int &y)
 8 {
 9     if(!b) x=1,y=0;
10     else exGCD(b,a%b,y,x),y-=a/b*x;
11 }
12 int Inv(int x)
13 {
14     int xx,yy;
15     exGCD(x,mod,xx,yy);
16     return (xx%mod+mod)%mod;
17 }
18 int P(int a,int b)
19 {
20     return 1ll*fac[a]*inv[a-b]%mod;
21 }
22 void Prework()
23 {
24     scanf("%d%d",&n,&m),all=(1<<n)-1;
25     for(int i=1;i<=m;i++)
26     {
27         scanf("%d%d",&t1,&t2),t1--,t2--;
28         lnk[t1]|=1<<t2,lnk[t2]|=1<<t1;
29     }
30     fac[0]=inv[0]=1;
31     for(int i=1;i<=n;i++)
32         fac[i]=1ll*fac[i-1]*i%mod;
33     inv[n]=Inv(fac[n]);
34     for(int i=n-1;i;i--)
35         inv[i]=1ll*inv[i+1]*(i+1)%mod;
36     for(int i=0;i<n;i++) lnk[i]|=1<<i;
37     for(int i=0;i<=all;i++)
38         for(int j=i;j;j-=j&-j) siz[i]++;
39     dp[0]=1;
40 }
41 int main()
42 {
43     Prework();
44     for(int i=0;i<=all;i++)
45         if(dp[i])
46             for(int j=0;j<n;j++)
47                 if(!(i&(1<<j)))
48                 {
49                     int news=i|lnk[j];
50                     if(mx[news]<mx[i]+1) 
51                         mx[news]=mx[i]+1,dp[news]=0;
52                     if(mx[news]==mx[i]+1)
53                         dp[news]=(dp[news]+1ll*dp[i]*P(n-siz[i]-1,siz[lnk[j]-(lnk[j]&i)]-1)%mod)%mod;
54                 }
55     printf("%lld",1ll*dp[all]*inv[n]%mod);
56     return 0;
57 }
View Code

相关推荐