Preface
妈的多校都是些什么题啊，一场比赛后三小时全程啥也干不了只能划划水，最后开榜就看手速排名，给他唐完了
这场开场和前期久违地顺利，按难度开了三道签到后队里讨论了下秒出了A的正解
我爬上去摸了会虽然nt错误频发WA了两发，但后面还是成功抢到了A题的一血，同时徐神和祁神坐在下面的时候把E题规律也搞出来了，上去rush了发也是一遍过
然后后面的时间就是看题——不会——看别的题——还是不会的过程了，感觉CDH都有点想法但不知道怎么写
最后一小时祁神出了一个J题相对好写的做法，我看了眼感觉很对就把正在写H的徐神换下来让祁神开J，结果写到比赛结束的时候才刚改完语法错误过编译
那问题来了我在干嘛，答案是摸鱼/研究没写完的国庆作业/打了两把雀，感觉不如早点下班回去睡觉
A. All-Star Game
首先仔细阅读题意后会发现可以把所有人看作点，粉丝关系看作边，这样按照题意连边后就得到了若干个连通块
发现当存在孤立的粉丝节点的时候就是无解，否则此时的答案就是连通块个数减去孤立的选手节点的个数
然后题目还加入了删边加边的操作，一眼就是线段树分治+可撤销并查集，另外再顺手维护下孤立点的个数即可
复杂度\(O(n\log ^2 n)\)，实际跑起来还挺快的说
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#define RI int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=400005;
int n,m,q,x,y,fa[N],sz[N],ans[N]; map <pi,int> rst;
struct ifo
{
int x,y,fx,fy,fay,szx;
}; vector <ifo> stk; int all,fan,player,deg[N];
inline int getfa(CI x)
{
return fa[x]!=x?getfa(fa[x]):x;
}
inline void revoke(CI tmp)
{
while (stk.size()>tmp)
{
int x=stk.back().x,y=stk.back().y;
int fx=stk.back().fx,fy=stk.back().fy;
int fay=stk.back().fay,szx=stk.back().szx;
stk.pop_back(); --deg[x]; --deg[y];
if (deg[x]==0) ++fan;
if (deg[y]==0) ++player;
if (fx==0) continue; ++all;
fa[fy]=fay; sz[fx]=szx;
}
}
class Segment_Tree
{
private:
vector <pi> edge[N<<2];
public:
#define TN CI now=1,CI l=0,CI r=q
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void insert(CI beg,CI end,const pi& it,TN)
{
if (beg<=l&&r<=end) return edge[now].push_back(it); int mid=l+r>>1;
if (beg<=mid) insert(beg,end,it,LS); if (end>mid) insert(beg,end,it,RS);
}
inline void solve(TN)
{
int tmp=stk.size(); for (auto [x,y]:edge[now])
{
++deg[x]; ++deg[y];
if (deg[x]==1) --fan;
if (deg[y]==1) --player;
int fx=getfa(x),fy=getfa(y);
if (fx!=fy)
{
--all; if (sz[fx]<sz[fy]) swap(fx,fy);
stk.push_back((ifo){x,y,fx,fy,fa[fy],sz[fx]});
fa[fy]=fx; sz[fx]+=sz[fy];
} else stk.push_back((ifo){x,y,0,0,0,0});
}
if (l==r)
{
if (fan>0) ans[l]=-1; else ans[l]=all-player; return revoke(tmp);
}
int mid=l+r>>1; solve(LS); solve(RS); revoke(tmp);
}
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
RI i,j; for (scanf("%d%d%d",&n,&m,&q),i=1;i<=n;++i)
for (scanf("%d",&x),j=1;j<=x;++j) scanf("%d",&y),rst[pi(n+y,i)]=0;
for (i=1;i<=q;++i)
{
scanf("%d%d",&x,&y); x+=n; auto it=pi(x,y);
if (rst.count(it)) SEG.insert(rst[it],i-1,it),rst.erase(it); else rst[it]=i;
}
for (auto [it,tim]:rst) SEG.insert(tim,q,it);
for (all=n+m,fan=m,player=n,i=1;i<=n+m;++i) fa[i]=i,sz[i]=1;
for (SEG.solve(),i=1;i<=q;++i) printf("%d\n",ans[i]);
return 0;
}
B. Bon Voyage
做不来一点
C. Cinema
比赛后面一小时看axs激情爆码近200行爆切此题，看来我对状压的理解还是不够深厚啊
D. Disgusting Relationship
好神奇的一个题啊，但就是没发现需要关心的只有\(a_1\)和\(a_p\)，不然感觉有机会做掉这道题的
首先根据祁神比赛时推出的表达式，有：
考虑这个数不能是\(p\)的倍数，那么就要求分子中所有\(p\)因子都要被分母消掉
发现分子中\(p\)因子个数是固定的，那么我们现在要做的就是最大化分母中\(p\)因子的个数
稍微推一下就会发现对于所有\(i'>p\)的\(a_{i'}\)都应该等于\(0\)，否则必然可以通过调整来使得分母中的\(p\)因子个数增加
（当然比赛的时候我们队用了一种更简单且本质的方法发现了有用的取值只有\(a_1\sim a_p\)，这里就不赘述了）
接下来考虑怎么计算方案数，首先我们发现总有一组平凡解为\(a_1=n\)，接下来就考虑怎么把\(a_1\)里的东西拿到\(a_2,\cdots,a_p\)中去，同时保持\(p\)因子的个数不变
不妨先来考虑\(p|n\)的情形，首先可以想到把所有的\(a_1\)都移动到\(a_p\)，算一算会发现此时贡献是不变的，同时一看就会发现此时只能移动到\(a_p\)，移动到其它位置必然会让因子数减少
那如果只是拿一部分放到\(a_p\)中去呢，再开开脑洞会发现所有构成\(p\)的幂次的连续段要一起移动
举个例子，比如当\(n=14,p=2\)时，那么相当于分出\(2,4,8\)三个连续段，其中每个段可以选择要么留在\(a_1\)要么移动到\(a_p\)
因此不难发现可以将\(n\)的\(p\)进制拆分搞出来，则对于除了最低位的每一位\(b_i\)，其贡献就是\(\prod (b_i+1)\)
接下来考虑\(p\nmid n\)的情况，不难发现最低位多出来的\(n\bmod p\)部分其实怎么放都无所谓，因子这部分就是\(n\bmod p\)的整数拆分的贡献
而这个东西有一个很经典的用五边形数来\(O(n\sqrt n)\)预处理的做法，具体可以看这里
然后这题就做完了，复杂度\(O(p\sqrt p+T\log n)\)
#include<cstdio>
#include<iostream>
#define int long long
#define RI int
#define CI const int&
using namespace std;
const int N=100005,mod=1e9+7;
int t,id,n,p,w[N],cnt,f[N];
inline void init(CI n)
{
RI i,j; for (i=1;w[cnt]<n;++i)
w[++cnt]=i*(3*i-1)/2,w[++cnt]=i*(3*i+1)/2;
for (f[0]=i=1;i<=n;++i) for (j=1;w[j]<=i;++j)
(f[i]+=(((j-1)>>1)&1?-1:1)*f[i-w[j]]+mod)%=mod;
}
inline int solve(int x,int ret=1)
{
while (x) (ret*=x%p+1)%=mod,x/=p; return ret;
}
signed main()
{
//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
for (init(100000),scanf("%lld",&t),id=1;id<=t;++id)
scanf("%lld%lld",&n,&p),printf("Case #%lld: %lld\n",id,solve(n/p)*f[n%p]%mod);
return 0;
}
E. Enigmatic Partition
好神奇的一道题，我全程没参与靠队友找规律做出来了
首先可以大力枚举\(a_1,m\)的取值，不难发现此时可以列出此时\(n\)的范围\([a_1\times m+3,a_1\times m+2m-3]\)
然后手玩一下会发现对于这段区间中的\(n\)的贡献是不完全相同的，具体会变成形如
的东西，然后再手玩一下会发现这东西的二阶差分很有规律，然后对奇偶讨论一下就做完了
总复杂度就是枚举\(a_1,m\)的调和级数\(O(n\ln n)\)
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr int $n = 300000 + 6;
llsi f[$n], f1[$n], f2[$n];
void prep(int N = 100000) {
for(int m = 3; m <= N; ++m) for(int a = 1; a <= N; ++a) {
if(N - a * m < 3) break;
llsi L = 3 + a * m, R = a * m + 2 * m - 3;
if(L > R) continue;
llsi M = (L + R) >> 1;
// if(M * 2 != L + R) std::cerr << "WOCAO\n";
f2[L ] += 1; f2[L + 1] += 1;
f2[M + 1] -= 1; f2[M + 2] -= 2; f2[M + 3] -= 1;
f2[R + 3] += 1; f2[R + 4] += 1;
continue ;
if(m & 1) {
// L M R
// 0 0 1 1 2 2 3 2 2 1 1 0 0 0 0
// 0 0 1 1 1 1 1 0 -1 -1 -1 -1 -1 0 0
// 0 0 1 1 0 0 0 -1 -2 -1 0 0 0 1 1
} else {
// L M R
// 0 0 1 1 2 2 3 3 3 2 2 1 1 0 0 0 0
// 0 0 1 1 1 1 1 1 0 -1 -1 -1 -1 -1 -1 0 0
// 0 0 1 1 0 0 0 0 -1 -2 -1 0 0 0 0 1 1
}
}
for(int i = 2; i <= 100000; ++i) f1[i] = f1[i - 2] + f2[i];
for(int i = 2; i <= 100000; ++i) f[i] = f[i - 2] + f1[i];
for(int i = 2; i <= 100000; ++i) f[i] += f[i - 1];
}
int main() {
prep();
std::ios::sync_with_stdio(false);
int T; std::cin >> T;
for(int Case = 1; Case <= T; ++Case) {
int a, b; std::cin >> a >> b;
std::cout << "Case #" << Case << ": " << f[b] - f[a - 1] << char(10);
}
return 0;
}
F. Factorio
什么逆天题目，看着就吓人
G. Game SET
纯签到题，大力\(O(n^3)\)枚举即可，虽然复杂度乍一看很炸裂但因为实际很容易搜出一组解，因此可以跑过
#include<cstdio>
#include<iostream>
#include<string>
#define RI int
#define CI const int&
using namespace std;
const int N=260;
int t,id,n,a[N][4]; string s;
int main()
{
//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
for (scanf("%d",&t),id=1;id<=t;++id)
{
RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i)
{
auto get=[&](string& s)
{
s=""; char ch; while (ch=getchar(),ch!='[');
while (ch=getchar(),ch!=']') s+=ch;
};
get(s); if (s=="one") a[i][0]=0; else if (s=="two") a[i][0]=1; else if (s=="three") a[i][0]=2; else a[i][0]=3;
get(s); if (s=="diamond") a[i][1]=0; else if (s=="squiggle") a[i][1]=1; else if (s=="oval") a[i][1]=2; else a[i][1]=3;
get(s); if (s=="solid") a[i][2]=0; else if (s=="striped") a[i][2]=1; else if (s=="open") a[i][2]=2; else a[i][2]=3;
get(s); if (s=="red") a[i][3]=0; else if (s=="green") a[i][3]=1; else if (s=="purple") a[i][3]=2; else a[i][3]=3;
}
bool flag=0; int posi,posj,posk;
auto check=[&](CI d)
{
if (a[i][d]==3||a[j][d]==3||a[k][d]==3) return true;
if (a[i][d]==a[j][d]&&a[i][d]==a[k][d]) return true;
if (a[i][d]!=a[j][d]&&a[i][d]!=a[k][d]&&a[j][d]!=a[k][d]) return true;
return false;
};
for (i=1;i<=n&&!flag;++i) for (j=i+1;j<=n&&!flag;++j) for (k=j+1;k<=n&&!flag;++k)
if (check(0)&&check(1)&&check(2)&&check(3)) posi=i,posj=j,posk=k,flag=1;
printf("Case #%d: ",id); if (!flag) puts("-1"); else printf("%d %d %d\n",posi,posj,posk);
}
return 0;
}
H. Hard String Problem
徐神看了H，徐神秒了H，徐神上机写H，徐神假了（悲
I. Interesting Computer Game
签到题，把一组关系看作图中的一条边
不难发现对于某个连通分量，若其中存在环则贡献就是该连通分量的大小，否则就是大小减\(1\)
用并查集维护联通关系的时候顺便记录一下是否有环即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI int
#define CI const int&
using namespace std;
const int N=200005;
int t,id,n,x[N],y[N],rst[N],cnt,fa[N],sz[N],vis[N]; bool cyc[N];
inline int getfa(CI x)
{
return x!=fa[x]?fa[x]=getfa(fa[x]):x;
}
int main()
{
//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
for (scanf("%d",&t),id=1;id<=t;++id)
{
RI i; for (scanf("%d",&n),cnt=0,i=1;i<=n;++i)
scanf("%d%d",&x[i],&y[i]),rst[++cnt]=x[i],rst[++cnt]=y[i];
sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
auto find=[&](CI x)
{
return lower_bound(rst+1,rst+cnt+1,x)-rst;
};
for (i=1;i<=n;++i) x[i]=find(x[i]),y[i]=find(y[i]);
for (i=1;i<=cnt;++i) fa[i]=i,sz[i]=1,cyc[i]=vis[i]=0;
for (i=1;i<=n;++i)
{
int u=getfa(x[i]),v=getfa(y[i]);
if (u==v) cyc[u]=1; else fa[v]=u,sz[u]+=sz[v],cyc[u]|=cyc[v];
}
int ans=0; for (i=1;i<=cnt;++i)
{
int x=getfa(i); if (vis[x]) continue;
vis[x]=1; ans+=cyc[x]?sz[x]:sz[x]-1;
}
printf("Case #%d: %d\n",id,ans);
}
return 0;
}
J. Jumping Points
祁神大概已经会了这道题了，但由于我没写过凸包求切线所以后面还是让祁神去写了，说明还是我不够努力（悲
具体的做法等祁神调出来了再更吧，或许有可能也要无限期挖坑了（乐
K. Kabaleo Lite
签到题，不难发现第一问的答案就是\(b_i\)的前缀最小值的最大值，考虑怎么求第二问的答案
不妨把每个位置\(i\)的\(a_i\)替换成原来\(a_i\)的前缀和，\(b_i\)替换成原来\(b_i\)的前缀最小值
考虑如果存在某对位置\(i,j(i<j)\)，因为\(b_i\ge b_j\)，因此如果\(a_i\ge a_j\)就说明\(j\)这个位置就一定没用了
可以从后往前用一个单调栈来维护所有有用的位置，最后扫一遍就可以求出答案了
注意最后的答案可能到\(10^{19}\)级别，需要用__int128（别忘记写__int128输出负数！）
#include<cstdio>
#include<iostream>
#define int long long
#define RI int
#define CI const int&
using namespace std;
const int N=100005;
int t,id,n,a[N],b[N],stk[N],top;
inline void print(__int128 x)
{
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10); putchar(x%10+'0');
}
signed main()
{
//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
for (scanf("%lld",&t),id=1;id<=t;++id)
{
RI i; for (scanf("%lld",&n),i=1;i<=n;++i)
scanf("%lld",&a[i]),a[i]+=a[i-1];
for (i=1;i<=n;++i) scanf("%lld",&b[i]);
for (i=2;i<=n;++i) b[i]=min(b[i-1],b[i]);
int mx=0; for (i=1;i<=n;++i) mx=max(mx,b[i]);
for (top=0,i=n;i>=1;--i)
{
while (top&&a[stk[top]]<=a[i]) --top;
stk[++top]=i;
}
__int128 ans=0; for (i=1;i<=top;++i)
ans+=__int128(a[stk[i]])*(b[stk[i]]-b[stk[i-1]]);
printf("Case #%d: %d ",id,mx); print(ans); putchar('\n');
}
return 0;
}
Postscript
国庆集训结束了，感觉天天被吊打被拉开差距，看来还是我不够努力