数据强横如斯，我人没了。。。

$T1$没开够$long \ long$一分不剩。（算的时候用了，输出的时候忘了）

快乐。而且点分治还写挂了。改成$long \ long$也会$T40$。

不过，这是第一次考场上写点分治，差不多算是写出来了，可喜可贺（虽然还是锅了

$T2$写了个线段树，写的有点像$ODT$（也不像），在随机数据下大概是两个$log$的，然而数据很不讲道理，蹭了个下线$20$就走了

T3全场最高也就10分这就没啥好说的。

不开$long \ long$真的会见祖宗啊，出数据的还会让你一分都没有的见祖宗啊。。。

长记性。。。但愿吧。。。

 

T1：小A的树

大意：树，输出前$k$长的树上路径。$n,k \le 2 \times 10^5$

树上路径——点分治啊。

极其草率的路径合并，用上《淘金》或者《超级钢琴》的逐步扩展的套路复杂度就对了。

记录每条路径的来源，同一子树的要跳过。

然后俩优先队列各干各的活就行了。一些明显的最优性剪枝写一写，跑的还挺快的。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define S 200005
 4 #define ll long long
 5 #define For() for(int i=fir[p];i;i=l[i])if(to[i]!=fa&&!al[to[i]]) 
 6 priority_queue<ll,vector<ll>,greater<ll> >q;
 7 priority_queue<pair<ll,int> >Q;
 8 int C,tsz,bst,sz[S],n,k,t,fir[S],to[S<<1],v[S<<1],l[S<<1],ec,K,pt[S],nxt[S];
 9 bool al[S]; pair<ll,int>a[S];ll r[S],qtop;
10 void link(int a,int b,int w){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=w;}
11 void Cent(int p,int fa=0){
12     int msz=0;sz[p]=1;
13     For()Cent(to[i],p),sz[p]+=sz[to[i]],msz=max(msz,sz[to[i]]);
14     msz=max(msz,tsz-sz[p]); if(msz<bst)C=p,bst=msz;
15 }
16 void dfs(int p,int fa,ll d,int o){
17     a[++t]=make_pair(d,o);
18     For()dfs(to[i],p,d+v[i],o);
19 }
20 void DaC(int p,int fa=0){
21     t=0; al[p]=1;
22     For()dfs(to[i],0,v[i],i);
23     a[++t]=make_pair(0,0);
24     sort(a+1,a+1+t); reverse(a+1,a+1+t);
25     a[t+1].second=-2;
26     for(int i=1;i<=t;++i){
27         nxt[i]=i+1;
28         while(a[nxt[i]].second==a[i].second)nxt[i]++;
29     }
30     if(a[1].first*2<=qtop)return;
31     for(int i=1;i<t;++i)if(a[i].first+a[nxt[i]].first>qtop)Q.push(make_pair(a[i].first+a[pt[i]=nxt[i]].first,i));
32     while(Q.size()&&Q.top().first>qtop){
33         ll x=Q.top().first;int id=Q.top().second;Q.pop();
34         q.pop(),q.push(x);qtop=q.top();
35         pt[id]++;if(a[pt[id]].second==a[id].second)pt[id]=nxt[pt[id]];
36         if(pt[id]!=t+1&&a[id].first+a[pt[id]].first>qtop)Q.push(make_pair(a[id].first+a[pt[id]].first,id));
37     }while(Q.size())Q.pop();
38     xxx:For()tsz=bst=sz[to[i]],Cent(to[i]),DaC(C);
39 }
40 int read(){
41     register int p=0;register char ch=getchar();
42     while(!isdigit(ch))ch=getchar();
43     while(isdigit(ch))p=(p<<3)+(p<<1)+ch-'0',ch=getchar();
44     return p;
45 }
46 int main(){//freopen("tree20.in","r",stdin);freopen("my.out","w",stdout);
47     cin>>n>>K;
48     for(int i=1,a,b,w;i<n;++i)a=read(),b=read(),w=read(),link(a,b,w),link(b,a,w);
49     for(int i=1;i<=K;++i)q.push(0);
50     tsz=bst=n;Cent(1);DaC(C); int z=0;
51     while(q.size())r[++z]=q.top(),q.pop(); while(z)printf("%lld\n",r[z]),z--;
52 }

View Code

 

T2：小B的序列

大意：序列，支持区间按位与/或上某个数，查询区间最大值。$n ,q \le 2 \times 10^5$

哭了，福建人干什么了就要被吃了

区间与和区间或，这个操作看起来好像会使序列趋于统一，所以好像大概是个复杂度正确的乱搞。

小清新线段树啊。

好像做过多数的暴力线段树好像都是维护$min,max$,然后如果$min,max$差值不大就可以直接不递归了。

然而这道题是位运算，所以维护$min,max$是不合适的，我们维护$or,and$。

发现如果对于一次修改，整个区间内的$and,or$对于这个修改的变化量是相同的(减少或增加的量)，那么就可以直接区间加了。

所以就这么暴力。没了。

时间复杂度的话，不会势能分析，大概口胡。

大概可以理解为：对于一次区间与操作，我们考虑它的所有0位。

它操作区间内所有数的这一位就都变成了0，也就是都一样了，那么也就是这段区间上这一位的势能直接被清空了。

同时在两个端点处，所在的所有区间的这一位的势能可能会增加，最多是$2log$点。

而对于所有的1位，这一位上不会产生任何变化，不会因为这一位而递归下去，也不会产生势能变化。

所以每次其实只是收获了已充能的0位上的势能，并且在最多$log$位上各充入$2log$势能。

最开始所有位上的势能大概也就是$nlog^2n$的所以总复杂度就是$O(nlog^2n)$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define S 200005
 4 int n,a[S],q,mx[S<<2],lz[S<<2],And[S<<2],Or[S<<2];
 5 #define lc p<<1
 6 #define rc p<<1|1
 7 #define md (cl+cr>>1)
 8 void up(int p){mx[p]=max(mx[lc],mx[rc]);And[p]=And[lc]&And[rc];Or[p]=Or[lc]|Or[rc];}
 9 void down(int p){lz[lc]+=lz[p];lz[rc]+=lz[p];mx[lc]+=lz[p];mx[rc]+=lz[p];And[lc]+=lz[p];And[rc]+=lz[p];Or[lc]+=lz[p];Or[rc]+=lz[p];lz[p]=0;}
10 void build(int p=1,int cl=1,int cr=n){
11     if(cl==cr){mx[p]=And[p]=Or[p]=a[cl];return;}
12     build(lc,cl,md); build(rc,md+1,cr); up(p);
13 }
14 void OR(int l,int r,int w,int p=1,int cl=1,int cr=n){
15     if(l<=cl&&cr<=r&&(w|Or[p])-Or[p]==(w|And[p])-And[p]){
16         int d=(w|Or[p])-Or[p];
17         lz[p]+=d;Or[p]+=d;And[p]+=d;mx[p]+=d;
18         return;
19     }
20     if(lz[p])down(p);
21     if(l<=md)OR(l,r,w,lc,cl,md); if(r>md)OR(l,r,w,rc,md+1,cr); up(p);
22 }
23 void AND(int l,int r,int w,int p=1,int cl=1,int cr=n){
24     if(l<=cl&&cr<=r&&(w&Or[p])-Or[p]==(w&And[p])-And[p]){
25         int d=(w&Or[p])-Or[p];
26         lz[p]+=d;Or[p]+=d;And[p]+=d;mx[p]+=d;
27         return;
28     }
29     if(lz[p])down(p);
30     if(l<=md)AND(l,r,w,lc,cl,md); if(r>md)AND(l,r,w,rc,md+1,cr); up(p);
31 }
32 int ask(int l,int r,int p=1,int cl=1,int cr=n){
33     if(l<=cl&&cr<=r)return mx[p];
34     if(lz[p])down(p);
35     return max(l<=md?ask(l,r,lc,cl,md):0,r>md?ask(l,r,rc,md+1,cr):0);
36 }
37 int main(){
38     cin>>n>>q;
39     for(int i=1;i<=n;++i)scanf("%d",a+i);
40     build();
41     for(int o,x,y,w;q--;){
42         scanf("%d%d%d",&o,&x,&y);
43         if(o==3)printf("%d\n",ask(x,y));
44         else if(o==1)scanf("%d",&w),AND(x,y,w);
45         else scanf("%d",&w),OR(x,y,w);
46     }
47 }

View Code

 

T3：小C的利是

大意：$n \times n$矩阵，每行每列选一个数共$n$个。不能选$-1$。问选出的位置的和是否有可能是$k$的倍数。$n,k \le 100$

发现这个定义和行列式的定义非常像。所以我们考虑用行列式来解。

然而行列式是乘法这题是加法，所以不难想到原根。

然而原根不是很好处理，在这里我们使用$k$次单位根会方便不少。设为$g$.

设$S$表示

既然和$S$是k的倍数，那么大概能想到$g^S \equiv 1$。

于是我们找一个大质数$P=ak+1$。有$g^{ak} \equiv 1 (mod \ P)$

这样，我们构造一种权值，使得是否存在K的倍数，在行列式中得以区分。

怎么让是1的值有贡献，而不是1的值没有贡献呢？

想起数学老师们再三强调的，等比数列的公比是1时不能直接套公式。

如果我们能让非1的排列产生的贡献是$1+x^S+x^{2S}+x^{3S}+...+x^{(k-1){S}} = \frac{1-x^{kS}}{1-x^S} \equiv 0 (mod \ P)$

然后是1的排列随便产生点什么非$0$的贡献就好了。

既然上式是加法，于是我们可以干脆做多次行列式，第一次贡献$1$，第二次$x^S$。。。就好了

所以我们可以发现，对于一个$A_{i,j}=-1$那么直接在行列式矩阵里把它弄成$0$，否则弄成$x^{A_{i,j}}$

其中$x$在$k$轮中分别取$g^0,g^1...g^{k-1}$.这样就符合了上述的条件，同时在取到$1$的排列的时候贡献是$k$而不是0。

（这怎么能想到啊

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,k,a[111][111],P,g,r[111][111],b[111][111],det,x;
 4 bool isp(int p){
 5     for(int i=2;i*i<=p;++i)if(p%i==0)return 0;
 6     return 1;
 7 }
 8 int qp(int b,int t,int a=1){if(t==-1)return 0;for(;t;t>>=1,b=1ll*b*b%P)if(t&1)a=1ll*a*b%P;return a;}
 9 int Gauss(int ret=1){
10     for(int i=1;i<=n;++i){
11         if(!b[i][i])for(int k=i+1;k<=n;++k)if(b[k][i]){swap(b[i],b[k]);ret=P-ret;break;}
12         ret=1ll*ret*b[i][i]%P;
13         for(int j=n,iv=qp(b[i][i],P-2);j>=i;--j)b[i][j]=1ll*b[i][j]*iv%P;
14         for(int j=i+1;j<=n;++j)for(int k=n;k>=i;--k)b[j][k]=(b[j][k]-1ll*b[j][i]*b[i][k]%P+P)%P;
15     }return ret;
16 }
17 int main(){
18     cin>>n>>k;
19     for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%d",&a[i][j]);
20     P=k*317913+1;
21     while(!isp(P))P+=k;
22     for(g=2;g<P;++g)if(qp(g,k)==1)break;
23     for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)r[i][j]=rand()%P;
24     for(int _=0,x=1;_<k;++_,x=1ll*x*g%P){
25         for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)b[i][j]=1ll*qp(x,a[i][j])*r[i][j]%P;
26         det=(det+Gauss())%P;
27     }puts(det%P?"Yes":"No");
28 }

View Code