Preface
这场据说题挺毒的?但实际打的时候感觉也还好,3h 就出了 7 个题,然后被 H 卡飞了
赛后发现是没有观察到构造的解的性质,把 Dinic 换成匈牙利就过了,只能说对 flow 的理解不够
B. 腊肠披萨
神秘 string 题,被徐神开场一眼秒了,虽然中间我和祁神上去写了三个签到,但徐神还是在 1h 不到的时候拿下了这题一血
#include <bits/stdc++.h>
constexpr int $n = 3000006;
int l, c, p;
int go[$n][26], fail[$n], O = 0;
int tag[$n], qu[$n], ans[$n], popipa[$n];
std::vector<std::pair<int, int>> hkr[$n];
std::vector<int> ch[$n];
void add(int &a, int b) {
if((a += b) >= p) a -= p;
}
void dfs(int cur) {
static int curans = 0;
std::vector<std::pair<int, int>> cache;
for(auto [k, v]: hkr[cur]) {
cache.emplace_back(k, popipa[k]);
add(curans, (p + v - popipa[k]) % p);
popipa[k] = v;
}
// std::cerr << cur << ' ' << curans << char(10);
ans[cur] = curans;
for(auto ch: ch[cur]) dfs(ch);
for(auto [k, v]: cache) {
add(curans, (p + v - popipa[k]) % p);
popipa[k] = v;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin >> l >> c >> p;
for(int i = 0; i < l; ++i) {
std::string s; std::cin >> s;
hkr[0].emplace_back(i, 1);
int cur = 0;
for(int j = 0, b2 = 1; j < s.size(); ++j) {
int u = s[j] - 'a';
if(!go[cur][u]) go[cur][u] = ++O;
cur = go[cur][u];
b2 = int64_t(b2) * c % p;
hkr[cur].emplace_back(i, b2);
}
// std::cerr << "tag[" << i << "] = " << cur << char(10);
tag[i] = cur;
}
int ql = 0, qr = 0;
for(int i = 0; i < 26; ++i) if(go[0][i]) qu[qr++] = go[0][i];
while(ql < qr) {
int cur = qu[ql++];
for(int i = 0; i < 26; ++i)
if(go[cur][i])
fail[go[cur][i]] = go[fail[cur]][i],
qu[qr++] = go[cur][i];
else
go[cur][i] = go[fail[cur]][i];
}
for(int i = 1; i <= O; ++i) ch[fail[i]].emplace_back(i);
dfs(0);
int fans =0;
for(int i = 0; i < l; ++i) add(fans, ans[tag[i]]);// std::cerr << ans[tag[i]] << char(i == l - 1 ? 10 : 32);
std::cout << fans << char(10);
return 0;
}
C. DFS 序
很套路的一个题
考虑一个点儿子子树内的操作不影响当前点儿子的顺序选择,因此对每个点考虑求出其儿子的最优排序即可
对于两个儿子节点 \(i,j\),令 \(sz,sum\) 分别表示其子树的大小以及子树内 \(w\) 之和,则由交换法不难证明,\(i\) 放置于 \(j\) 前当且仅当 \(sz_i\times sum_j>sz_j\times sum_i\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,w[N],dfn[N],sum[N],idx,sz[N],x; vector <int> v[N];
inline void DFS1(CI now=1,CI fa=0)
{
sz[now]=1; sum[now]=w[now]; for (auto to:v[now])
DFS1(to,now),sz[now]+=sz[to],sum[now]+=sum[to];
}
inline void DFS2(CI now=1,CI fa=0)
{
dfn[now]=++idx;
auto cmp=[&](CI x,CI y)
{
return sz[x]*sum[y]>sz[y]*sum[x];
};
sort(v[now].begin(),v[now].end(),cmp);
for (auto to:v[now]) DFS2(to,now);
}
signed main()
{
scanf("%lld",&n);
for (RI i=1;i<=n;++i) scanf("%lld",&w[i]);
for (RI i=2;i<=n;++i) scanf("%lld",&x),v[x].push_back(i);
DFS1(); DFS2(); int ans=0;
//for (RI i=1;i<=n;++i) printf("%lld%c",dfn[i]," \n"[i==n]);
for (RI i=1;i<=n;++i) ans+=dfn[i]*w[i];
return printf("%lld",ans),0;
}
E. 循环赛
神秘猜结论题,经过徐神的观察,先推出了 \(z=1\) 的情况以及很多时候答案都是 \(n\)
但后面根据样例发现当 \(z\) 较大时答案会减小,列出一些小 Case 后很容易找到规律
#include <bits/stdc++.h>
using llsi = long long signed int;
int main() {
std::ios::sync_with_stdio(false);
llsi T; std::cin >> T; while(T--) {
llsi n, z; std::cin >> n >> z;
if(z == 1) std::cout << 1 + !(n & 1) << char(10);
else {
llsi thres = n / 2 + 1;
if(z <= thres) std::cout << n << char(10);
else std::cout << n - (z - thres) * 2 << char(10);
}
}
return 0;
}
F. 图
神秘构造题,从 \(n-1\) 想到生成树就很简单了
考虑建立 \(\lceil\frac{m}{n-1}\rceil\) 棵生成树,对于每条边,我们贪心地将它加入编号最小且不连通的生成树中
不难发现如果在加完这 \(m\) 条边后,第 \(\lceil\frac{m}{n-1}\rceil\) 棵树中任意相连的两点都是合法的点对,构造答案的话就在每棵树上搜索一下即可
判断一条边加在哪棵树中可以直接二分,复杂度 \(O(m\log m\times \alpha(n))\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,m,x,y;
struct DSU
{
vector <int> fa,pre; vector <vector <int>> G;
vector <pair <int,int>> E;
inline void init(CI n)
{
fa.resize(n); pre.resize(n); G.resize(n); E.clear();
for (RI i=0;i<n;++i) G[i].clear(),pre[i]=-1,fa[i]=i;
}
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline bool query(CI x,CI y)
{
return getfa(x)==getfa(y);
}
inline void merge(CI x,CI y)
{
//printf("(%d,%d)\n",x,y);
fa[getfa(x)]=getfa(y);
E.push_back({x,y});
G[x].push_back(y); G[y].push_back(x);
}
inline void findpath(CI now,CI tar,vector <int>& path)
{
if (now==tar)
{
for (int x=tar;x!=n;x=pre[x]) path.push_back(x);
reverse(path.begin(),path.end());
return;
}
for (auto to:G[now]) if (pre[to]==-1) pre[to]=now,findpath(to,tar,path);
}
}D[N];
int main()
{
//freopen("F.in","r",stdin);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&m);
int tot=(m+n-2)/(n-1);
for (RI i=1;i<=tot;++i) D[i].init(n);
for (RI i=1;i<=m;++i)
{
scanf("%d%d",&x,&y); --x; --y;
int l=1,r=tot,ret=tot+1;
while (l<=r)
{
int mid=l+r>>1;
if (!D[mid].query(x,y)) ret=mid,r=mid-1; else l=mid+1;
}
if (ret<=tot) D[ret].merge(x,y);
}
if (D[tot].E.empty()) { puts("-1"); continue; }
auto [u,v]=D[tot].E.back();
printf("%d %d\n",u+1,v+1);
for (RI i=1;i<=tot;++i)
{
vector <int> path;
D[i].pre[u]=n;
D[i].findpath(u,v,path);
printf("%d ",path.size());
for (auto x:path) printf("%d ",x+1);
putchar('\n');
}
}
return 0;
}
G. Menji 和 gcd
经典根号分治
考虑枚举答案是否能为 \(d\),则需要满足 \(\lfloor\frac{R}{d}\rfloor-\lfloor\frac{L-1}{d}\rfloor\ge 2\),可以枚举 \(10^6\) 以内的 \(d\)
否则当 \(d>10^6\) 时,\(\lfloor\frac{R}{d}\rfloor\) 的值很小,可以经典除法分块搞一下
单组数据复杂度 \(O(\sqrt R)\)
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int S=1e6;
int t,L,R;
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld%lld",&L,&R); int ans=1;
for (RI i=1;i<=S;++i)
if ((R/i)-((L-1)/i)>=2) ans=i;
for (RI l=1,r;l<=R;l=r+1)
{
r=R/(R/l); int tmp=R/r;
if (tmp-((L-1)/r)>=2) ans=max(ans,r);
}
printf("%lld\n",ans);
}
return 0;
}
H. 小班课
感觉关键点全想到了,但就是没搞清楚 Dinic 求出的解的性质导致挂飞了
首先不难发现答案上界就是最大匹配,因此尝试构造一组达到该上界的解
一个关键的观察是一定存在某个匹配,使得某个人选到了他意向度最高的课程,此时可以直接把这个人丢进答案中,并将对应课程容量减 \(1\),当某个课程容量为 \(0\) 时就直接将其删掉,然后递归处理即可
这种做法的正确性需要找出的匹配具有一定性质时才是对的,匈牙利由于其每次增广的性质天然符合要求,因此可以得到正确的解
但比赛的时候发病了用了 Dinic 去找然后挂飞了,只能说理解不足啊
PS:其实一个更显然的做法就是用费用流来强制先选优先度低的边,然后用一个拓扑排序构造答案即可
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cassert>
#define RI register int
#define CI const int&
using namespace std;
const int N=505,INF=1e9;
int T,n,m,b[N],valid[N],mat[N],val[N*N],pre[N*N],rb[N],L[N],R[N],vis[N*N]; vector <int> v[N],a[N];
inline bool find(CI now,CI idx)
{
for (auto to:v[now]) if (vis[to]!=idx)
{
vis[to]=idx;
if (!pre[to]||find(pre[to],idx))
return pre[to]=now,1;
}
return 0;
}
int main()
{
//freopen("1.in","r",stdin);
for (scanf("%d",&T);T;--T)
{
scanf("%d%d",&n,&m);
for (RI i=1;i<=n;++i) valid[i]=1,v[i].clear(),mat[i]=0;
int idx=0;
for (RI i=1;i<=m;++i)
{
scanf("%d",&b[i]);
L[i]=idx+1;
for (RI j=1;j<=b[i];++j) val[++idx]=i;
R[i]=idx;
}
for (RI i=1;i<=n;++i)
{
int x; scanf("%d",&x); a[i].resize(x);
for (RI j=0;j<a[i].size();++j)
{
scanf("%d",&a[i][j]);
for (RI k=L[a[i][j]];k<=R[a[i][j]];++k)
v[i].push_back(k);
}
}
for (RI i=1;i<=idx;++i) pre[i]=vis[i]=0;
int flow=0;
for (RI i=1;i<=n;++i) flow+=find(i,i);
printf("%d\n",flow);
for (RI i=1;i<=idx;++i)
if (pre[i]) ++rb[mat[pre[i]]=val[i]];
//for (RI i=1;i<=n;++i) printf("%d%c",mat[i]," \n"[i==n]);
vector <int> ans;
for (RI k=1;k<=n;++k)
{
bool find=0;
for (RI i=1;i<=n;++i)
{
if (!valid[i]) continue;
bool flag=1;
for (auto x:a[i])
{
if (x==mat[i]) break;
if (rb[x]>0) { flag=0; break; }
}
if (flag)
{
ans.push_back(i); valid[i]=0;
--rb[mat[i]]; find=1; break;
}
}
assert(find==1);
}
for (auto x:ans) printf("%d ",x); putchar('\n');
}
return 0;
}
I. 不等式
神秘签到题,我题目都没看
#include<bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
const int lim = (int)1e9;
const int N = 2e5+5;
int n, m, A[N], deg[N];
vector<pii> vec[N];
vector<int> G[N];
int que[N], ed=-1, fr=0;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=1; i<=m; ++i) {
int x, y, z; cin >> x >> y >> z;
vec[x].push_back({y, z});
G[y].push_back(x), G[z].push_back(x);
deg[x] += 2;
}
for (int i=1; i<=n; ++i) A[i] = -1;
for (int i=1; i<=n; ++i) if (deg[i]==0) que[++ed] = i;
bool ok = true;
while (fr<=ed) {
int x = que[fr++];
A[x] = 1;
for (auto [y, z] : vec[x]) A[x] = max(A[x], A[y]+A[z]);
if (A[x]>lim) {ok=false; break;}
for (auto v : G[x]) {
--deg[v];
if (0==deg[v]) que[++ed] = v;
}
}
int ans = 0;
for (int i=1; i<=n; ++i) {
ans += A[i];
if (-1==A[i] || ans > lim) {ok=false; break;}
}
if (!ok) cout << -1 << '\n';
else cout << ans << '\n';
return 0;
}
J. 另一个计数问题
感觉和今年第一场网络赛的 B 思路一模一样,根据经典套路发现除了 \([\frac{n}{2}+1,n]\) 的质数都是孤点外,剩下的所有点都是相连的
因此手玩一下式子会发现只要知道 \([\frac{n}{2}+1,n]\) 内所有质数之和以及质数的平方和即可,上 Min_25 筛板子即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353, inv2 = (MOD+1)/2, inv3 = (MOD+1)/3, inv6 = (MOD+1)/6;
void inc(int &x, int a){if ((x+=a)>=MOD) x-=MOD;}
void dec(int &x, int a){if ((x-=a)<0) x+=MOD;}
void mul(int &x, int a){x=1LL*x*a%MOD;}
namespace Min25 {
const int $N = 1e6+5;
bool isp[$N]; int pri[$N], totp;
int sp1[$N], g1[$N];
int sp2[$N], g2[$N];
int $n, Sqr, tot, w[$N], ind1[$N], ind2[$N];
void initPri(int n) {
isp[1] = 1;
for (int i=1; i<=n; ++i) {
if (!isp[i]) {
pri[++totp] = i;
sp1[totp] = (sp1[totp-1] + i)%MOD;
sp2[totp] = (sp2[totp-1] + 1LL*i*i)%MOD;
}
for (int j=1; j<=totp&&pri[j]*i<=n; ++j) {
isp[i*pri[j]] = 1;
if (i%pri[j]==0) break;
}
}
}
void initMin25(int n) {
tot = 0;
$n = n;
Sqr = sqrtl(n);
initPri(Sqr);
for (int i=1; i<=n; ) {
int j = n/(n/i);
w[++tot] = n/i;
g1[tot] = w[tot]%MOD;
g2[tot] = g1[tot]*(g1[tot]+1)%MOD*(2*g1[tot]+1)%MOD*inv6%MOD;
g1[tot] = g1[tot]*(g1[tot]+1)%MOD*inv2%MOD;
dec(g2[tot], 1); dec(g1[tot], 1);
if (n/i<=Sqr) ind1[n/i]=tot;
else ind2[n/(n/i)]=tot;
i=j+1;
}
for (int i=1; i<=totp; ++i) {
for (int j=1; j<=tot&&pri[i]*pri[i]<=w[j]; ++j) {
int k = w[j]/pri[i]<=Sqr ? ind1[w[j]/pri[i]] : ind2[n/(w[j]/pri[i])];
dec(g1[j], pri[i]*(g1[k]-sp1[i-1]+MOD)%MOD);
dec(g2[j], pri[i]*pri[i]%MOD*(g2[k]-sp2[i-1]+MOD)%MOD);
}
}
}
}using namespace Min25;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n; int nn=n%MOD;
int sum=(nn+2)*(nn-1+MOD)%MOD*inv2%MOD;
initMin25(n);
int sp=(g1[1]%MOD-g1[2]%MOD+MOD)%MOD,sp2=(g2[1]%MOD-g2[2]%MOD+MOD)%MOD;
// initMin25(n/2);
// sp=(sp-g1[1]%MOD+MOD)%MOD;
// sp2=(sp2-g2[1]%MOD+MOD)%MOD;
int ans=(sum*sum%MOD-(nn*(nn+1)%MOD*(2*nn+1)%MOD*inv6%MOD-1+MOD)%MOD+MOD)%MOD*inv2%MOD;
ans=(ans-sp*sum%MOD+sp2+MOD)%MOD;
ans=(ans+(sp*sp%MOD-sp2+MOD)%MOD*inv2%MOD)%MOD;
cout<<ans<<endl;
// printf("tot=%lld g0=%lld g1=%lld\n", tot, g1[1], g2[1]);
// printf("w:"); for (int i=1; i<=tot; ++i) printf("%lld ", w[i]); puts("");
// printf("g1:"); for (int i=1; i<=tot; ++i) printf("%lld ", g1[i]); puts("");
return 0;
}
Postscript
感觉今天久违地前期贼顺但是后期牢底坐穿了,鉴定为 THU 出题是这样的
标签:std,Provincial,now,Contest,int,Programming,ans,include,MOD From: https://www.cnblogs.com/cjjsb/p/18444858