2020 Lenovo Cup USST Campus Online Invitational Contest
前言
所以题面里面的Setsuna应该是雪菜吧！？是的吧。。的吧。。
训练情况
训练时出现的问题
开局开A，贡献一发罚时（忘记答案要对最大值取min，我是sb）
F题挺有意思的，我本来想直接复读样例然后就GG了（没读懂样例就上手的下场）。
部分题解
F Fake Algorithm
题意
把(n)个数分成若干组，组内互质，问最少要分几组。题目给了一个贪心的假算法（顺序遍历，若当前数字未被分组，则组数+1，然后按顺序向后遍历，把能放进去的直接放进去），你需要构造一组输入和对应的解使得你分的组数恰好比贪心的少(k)，不要求你分的也是最少的。(1leq k leq 7) 。要求给出的输出满足(1leq n leq 300 , 1leq a_i leq {10}^{18})
题解
其实我已开始以为这算法没有问题QAQ。然后康了康样例，发现算法确实是错的QAQ（mdzz）。。
感觉直接把样例复读(K)遍就行了，然后光荣的WA了一发。
然后只能乖乖做题了QAQ。
我的做法跟题解有点不一样，然而我也说不清QAQ。。具体看代码吧。。。
总之就是前tot个数在假算法中一定是两个一组（这个是排起来的）。。
然后后tot个数一定都只能一个一组（因为后tot个数中质数个数都超过一半）。。所以假算法答案是(3*tot/2)
然而前tot个数与后tot个数能一一对应最终组成tot组。令(k=tot/2)就做完了~
(Code)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL P=998244353;
int n,m,K;
int cnt=0;
LL p[30];
bool check(int x){
for(int i=2;i<=sqrt(x);++i){
if(x%i==0) return 0;
}
return 1;
}
int tot=0;
bitset<15> f[100],E;
int main(){
scanf("%d",&K);
for(int i=2;cnt<K*2+1;++i){
if(check(i)){
p[cnt]=i;++cnt;
}
}
for(int i=0;i<K;++i){
++tot;
int j=i;
for(int o=1;o<=K;++o,j=(j+1)%(K*2+1)){
f[tot][j]=1;
}
++tot;
for(int o=1;o<=K;++o,j=(j+1)%(K*2+1)){
f[tot][j]=1;
}
}
for(int i=0;i<15;++i){
if(i<(K*2+1)) E[i]=1;
else E[i]=0;
}
for(int i=1;i<=tot;++i){
f[i+tot]=f[i]^E;
}
cout<<tot+tot<<" "<<tot<<endl;
for(int j=1;j<=tot+tot;++j){
LL num=1;
for(int i=0;i<(K+K+1);++i){
if(f[j][i]) num=num*p[i];
}
cout<<num<<" ";
}
cout<<endl;
for(int i=1;i<=tot;++i) cout<<i<<" ";
for(int i=1;i<=tot;++i) cout<<i<<" ";
cout<<endl;
return 0;
}
K K-Shift Array
题意
(n)长数组,(m)个操作，每次选择一个区间，使每(k leq 3)个数为一组，循环左移一格，或者询问区间和。(1leq n,m leq) (2) ( imes) ({10}^{5})。
题解
训练的时候一直想着用什么数组结构能实现轮换。。然而一点办法都没有。。
题解是用多颗平衡树，开多颗树这是我没想到的QAQ（其实是人傻）
我们开出(lcm(1...k))个平衡树，分别代表下标对(lcm(1...k))取模后得到的几组数。
每次修改就在每棵树中拆出范围内的几个数，然后轮换就相当于交换颗树。
询问就是在每棵树询问区间内的数。
然后就是(O(lcm(1...k)mlogn))。
(Code)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+10;
const int INF=1e9;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(LL x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
int has=0,sz=0,root[6];
inline int HAS(){return has>0?has=has*109%100003:has=107;}
struct Treap{
int ch[2],rnd,v,siz;
LL s;
Treap(int vv=0){ch[0]=ch[1]=0;v=vv;s=vv;siz=1;rnd=HAS();}
}tr[N];
#define pa pair<int,int>
inline void update(int x){
tr[x].siz=tr[tr[x].ch[0]].siz+tr[tr[x].ch[1]].siz+1;
tr[x].s=tr[tr[x].ch[0]].s+tr[tr[x].ch[1]].s+(LL)tr[x].v;
}
int Merge(int x,int y){
if(!x) return y;
if(!y) return x;
//pushdown(x);pushdown(y);
if(tr[x].rnd<tr[y].rnd){
tr[x].ch[1]=Merge(tr[x].ch[1],y);update(x);return x;
}
else{
tr[y].ch[0]=Merge(x,tr[y].ch[0]);update(y);return y;
}
}
pa Split(int x,int k){
if(!x) return pa(0,0);
pa y;
if(tr[tr[x].ch[0]].siz>=k){
y=Split(tr[x].ch[0],k);
tr[x].ch[0]=y.second;update(x);y.second=x;
}
else{
y=Split(tr[x].ch[1],k-tr[tr[x].ch[0]].siz-1);
tr[x].ch[1]=y.first;update(x);y.first=x;
}
return y;
}
int Getkth(int x,int v){
if(!x) return 0;
return tr[x].v>=v?Getkth(tr[x].ch[0],v):Getkth(tr[x].ch[1],v)+tr[tr[x].ch[0]].siz+1;
}
inline int Findkth(int k,int wh){
pa x=Split(root[wh],k-1);
pa y=Split(x.second,1);
int ans=y.first;
root[wh]=Merge(Merge(x.first,ans),y.second);
return tr[ans].v;
}
inline void Insert(int v,int wh){
Treap e(v);tr[++sz]=e;
root[wh]=Merge(root[wh],sz);
}
int n,Q;
int a[N];
int b[6][3];
int main(){
tr[0].siz=0;
scanf("%d%d",&n,&Q);
for(int i=0;i<6;++i) root[i]=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
Insert(a[i],i%6);
}
int op,l,r,K;
pa x,y;
while(Q--){
scanf("%d",&op);
if(op==1){
scanf("%d%d%d",&l,&r,&K);
for(int i=0;i<6;++i){
if(i>0){
x=Split(root[i],(r+6-i)/6);
y=Split(x.first,(l-1+6-i)/6);
}
else {
x=Split(root[i],(r)/6);
y=Split(x.first,(l-1)/6);
}
b[i][0]=y.first;b[i][1]=y.second;b[i][2]=x.second;
}
if(K==2){
swap(b[l%6][1],b[(l+1)%6][1]);
swap(b[(l+2)%6][1],b[(l+3)%6][1]);
swap(b[(l+4)%6][1],b[(l+5)%6][1]);
}
if(K==3){
swap(b[l%6][1],b[(l+1)%6][1]);
swap(b[(l+1)%6][1],b[(l+2)%6][1]);
swap(b[(l+3)%6][1],b[(l+4)%6][1]);
swap(b[(l+4)%6][1],b[(l+5)%6][1]);
}
for(int i=0;i<6;++i){
root[i]=Merge(b[i][0],Merge(b[i][1],b[i][2]));
}
}
else{
LL ans=0;
scanf("%d%d",&l,&r);
for(int i=0;i<6;++i){
if(i>0){
x=Split(root[i],(r+6-i)/6);
y=Split(x.first,(l-1+6-i)/6);
}
else {
x=Split(root[i],(r)/6);
y=Split(x.first,(l-1)/6);
}
b[i][0]=y.first;b[i][1]=y.second;b[i][2]=x.second;
ans+=tr[b[i][1]].s;
root[i]=Merge(b[i][0],Merge(b[i][1],b[i][2]));
}
printf("%I64d
",ans);
}
}
return 0;
}
部分放弃补的题
I Immortal Trees
题意
数树题。(n)个点，每个点有度数限制，有一些边必须选，求把它补成一个生成树的方案数。(1leq n leq 60)。
题解
大概就是用prufer序列来DP，效率应该是(O(n^4))，但不知道为什么总是WA on 36，我吐了。。
代码放下面，要是有人知道我哪里错了可以联系我。。。
(Code)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL P=998244353;
const int N=3e5+10;
const int INF=1e9;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(LL x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,m,K;
struct edge{int l,r;}e[150];
bool cmp(edge x,edge y){return x.l<y.l||(x.l==y.l&&x.r<y.r);}
int fa[150];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
vector<int> ve[150];
int du[150],L[150],R[150];
LL G[65][65][65][65];
LL C[150][150];
LL F[150][150];
void add(LL &x,LL y){
x+=y;if(x>=P)x-=P;
}
int main(){
C[0][0]=1;
for(LL i=1;i<=100;++i){
C[i][0]=1;
for(LL j=1;j<=i;++j){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
}
}
scanf("%d%d%d",&n,&m,&K);
if(n==1){
while(1);
//puts("1");
return 0;
}
for(int i=1;i<=m;++i){
scanf("%d%d",&e[i].l,&e[i].r);
if(e[i].l>e[i].r)swap(e[i].l,e[i].r);
}
int tt=0,u,v,op;
for(int i=1;i<=n;++i){
L[i]=1;
R[i]=n-1;
}
for(int i=1;i<=K;++i){
scanf("%d%d%d",&op,&u,&v);
if(op==0){
L[u]=max(L[u],v);
}
else {
R[u]=min(R[u],v);
}
}
if(m>0){
tt=1;
sort(e+1,e+1+m,cmp);
for(int i=2;i<=m;++i) if(e[tt].l!=e[i].l||e[tt].r!=e[i].r) e[++tt]=e[i];
m=tt;
}
for(int i=1;i<=m;++i){
++du[e[i].l];
++du[e[i].r];
}
for(int i=1;i<=n;++i){
if(L[i]>R[i]){
puts("0");return 0;
}
L[i]-=du[i];
L[i]=max(L[i],0);
R[i]-=du[i];
if(R[i]<0){
puts("0");return 0;
}
}
for(int i=1;i<=n;++i) fa[i]=i;
bool flag=0;
for(int i=1;i<=m;++i){
u=find(e[i].l);v=find(e[i].r);
if(u>v) swap(u,v);
if(u==v) {flag=1;break;}
fa[v]=u;
}
if(flag){puts("0");return 0;}
//if(flag==0&&m==n-1){puts("1");return 0;}
//cout<<"y"<<endl;
for(int i=1;i<=n;++i)fa[i]=find(i);
//for(int i=1;i<=n;++i) cout<<fa[i]<<" ";puts("");
tt=0;
for(int i=1;i<=n;++i)
if(fa[i]==i){
++tt;
for(int j=1;j<=n;++j) if(fa[j]==i) ve[tt].push_back(j);
//for(int j=0;j<ve[tt].size();++j) cout<<ve[tt][j]<<" ";puts("");
}
//for(int i=1;i<=n;++i) cout<<L[i]<<" "<<R[i]<<endl;
for(int i=1;i<=tt;++i){
for(int j=0;j<=n+1;++j){
G[i][j][0][0]=1;
for(int k=0;k<ve[i].size();++k){
for(int o=0;o<=j;++o){
if(!G[i][j][k][o]) continue;
for(int p=L[ve[i][k]];p<=R[ve[i][k]];++p){
if(o+p<=j){
add(G[i][j][k+1][o+p],G[i][j][k][o]*C[j-o][p]%P);
}
else break;
}
}
}
}
}
if(tt==1){
puts("1");return 0;
}
//if(tt>30) while(1);
//for(int i=1;i<=n;++i) cout<<G[i][1][ve[i].size()][1]<<endl;
F[0][0]=1;
for(int i=0;i<tt;++i){
for(int j=0;j<=tt-2;++j){
//cout<<i<<" "<<j<<" "<<F[i][j]<<endl;
if(!F[i][j]) continue;
for(int k=0;k<=tt-2-j;++k){
//cout<<i<<" "<<j<<" "<<k<<" "<<C[tt-2-j][k]<<" "<<G[i+1][k+1][ve[i+1].size()][k+1]<<endl;
add(F[i+1][j+k],F[i][j]*C[tt-2-j][k]%P*G[i+1][k+1][ve[i+1].size()][k+1]%P);
}
}
}
cout<<(F[tt][tt-2]%P+P)%P<<endl;
return 0;
}