Preface
都给我丑完了这怎么办啊， 被血虐了苦路西
这场本来前面感觉都还可以，但是当中期看了眼C的题意后准备开C后就不对劲了起来
最后1h扔掉一直T的C题去做H，结果因为被卡自然溢出的Hash一直挂到比赛结束，直接红温
感觉这场策略问题挺大的，比如没有跟榜去写更加简单的E题（比赛的时候题目都没看），以及没有考虑到自然溢出会被卡的那么惨（原来卡自然溢出的数据怎么调seed都是木大的）
嘛不过就当长个教训了的说，由于今天晚上10：30还有三小时的CF，所以B题就留着以后补了
A. Division
Prob
给定\(p,q\)，求一个最大的\(x\)使得\(x|p\and q\nmid x\)
\(p\le 10^{18},q\le 10^9\)
Tutorial
首先不难发现当\(q\nmid p\)时答案就是\(p\)，否则我们考虑令\(t=\frac{p}{q}\)
考虑最后答案的\(x\)满足存在一个\(y\)，使得\(x\times y=p=q\times t\)，由于要让\(x\)最大且不为\(q\)的倍数，那么很容易想到只要在某个质因数\(p_i\)下，我们让\(x\)关于\(p_i\)的次数比\(q\)小\(1\)，就能在满足要求的前提下最大化\(x\)
说起来可能有点抽象，但手玩一下发现是很显然的
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,p,q;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
if (scanf("%lld%lld",&p,&q),p%q) { printf("%lld\n",p); continue; }
int ret=1,t=p/q,rs=t,tmp=q; for (RI i=2;i*i<=tmp;++i) if (tmp%i==0)
{
while (tmp%i==0) tmp/=i; int cur=q/i,coef=1;
while (t%i==0) t/=i,coef*=i; ret=max(ret,cur*(rs/coef));
}
if (tmp!=1)
{
int cur=q/tmp,coef=1;
while (t%tmp==0) t/=tmp,coef*=tmp; ret=max(ret,cur*(rs/coef));
}
printf("%lld\n",ret);
}
return 0;
}
B. Logistical Questions
Prob
给出一个\(n\)个点，点权为\(a_i\)的树，每条边有边权，同时定义\(x,y\)之间的距离为\(dist(x,y)\)
令\(f(x)=\sum_{y=1}^n a_y\times dist(x,y)^{\frac{3}{2}}\)，求使得\(f(x)\)最小的\(x\)
\(n\le 2\times 10^5\)
Tutorial
先坑着，是道找性质+点分治的题，3000分感觉还是挺神的
C. Lucky Array
Prob
定义一个数\(x\)是good的当且仅当\(x\)的所有数位在十进制下都是\(4\)或者\(7\)
给出一个长度为\(n\)的序列，要对其进行\(m\)次操作，每次操作为：
- 区间加上某数\(c\)，其中\(c\ge 1\)，保证任何时候序列中的所有数均\(\le 10000\)
- 区间询问good的数的个数
\(n,m\le 10^5\)
Tutorial
首先观察到数的可能值域很小，因此我们跑个暴力发现\([1,10000]\)内good的数只有\(30\)个
这就允许我们用暴力一点的方法，枚举每个good的数，求出最后等于它的数的个数，最后累加即可
设枚举的good数为\(lim\)，则显然若一个数在某时刻\(>lim\)了则它一定不会产生任何贡献了
那么我们不妨在这种情况下暴力把这个点删掉，由于删掉一个点最多会影响\(O(\log n)\)个点，因此复杂度是有保障的
而最后询问的时候我们只关心所有值恰好为\(lim\)的数的个数，用经典套路转化一下，不难发现只要记录一下区间最大值和最大值的个数即可
那么这题就做完了，复杂度\(O(30\times n\log n)\)，但是由于我的线段树不知道为什么常数一般是别人的好几倍（主要是用class套结构体），所以只能卡着原题的时限过去
实际实现的时候还有一个优化就是记录下当前第一个大于每个数的good数是什么，可以大大优化常数
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int t,rst[N],cnt,n,m,a[N],opt[N],ans[N],l[N],r[N],c[N],lim; char s[10];
class Segment_Tree
{
private:
struct segment
{
pi mx; int tag;
}node[N<<2];
#define MX(x) node[x].mx
#define T(x) node[x].tag
#define TN CI now=1,CI l=1,CI r=n
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline pi merge(const pi& A,const pi& B)
{
if (A.fi>B.fi) return A; else
if (A.fi<B.fi) return B; else
return pi(A.fi,A.se+B.se);
}
inline void pushup(CI now)
{
MX(now)=merge(MX(now<<1),MX(now<<1|1));
}
inline void apply(CI now,CI mv)
{
T(now)+=mv; MX(now).fi+=mv;
}
inline void pushdown(CI now)
{
if (T(now)) apply(now<<1,T(now)),apply(now<<1|1,T(now)),T(now)=0;
}
public:
inline void build(TN)
{
T(now)=0; if (l==r) return (void)(MX(now)=pi(a[l]<=lim?a[l]:-1e9,1));
int mid=l+r>>1; build(LS); build(RS); pushup(now);
}
inline void modify(CI beg,CI end,CI mv,TN)
{
if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);
if (beg<=mid) modify(beg,end,mv,LS); if (end>mid) modify(beg,end,mv,RS); pushup(now);
}
inline pi query(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return MX(now); int mid=l+r>>1; pi ret=pi(-1e9,0); pushdown(now);
if (beg<=mid) ret=merge(ret,query(beg,end,LS)); if (end>mid) ret=merge(ret,query(beg,end,RS)); return ret;
}
inline void rebuild(TN)
{
if (MX(now).fi<=lim) return; if (l==r) return (void)(MX(now)=pi(-1e9,1));
int mid=l+r>>1; pushdown(now); rebuild(LS); rebuild(RS); pushup(now);
}
#undef MX
#undef T
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
auto calc=[&](int x)
{
while (x>0)
{
if (x%10!=4&&x%10!=7) return 0;
x/=10;
}
return 1;
};
RI i,j; for (i=1;i<=10000;++i) if (calc(i)) rst[++cnt]=i;
//for (printf("%d\n",cnt),i=1;i<=cnt;++i) printf("%d%c",rst[i]," \n"[i==cnt]);
for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=m;++i)
if (scanf("%s%d%d",s+1,&l[i],&r[i]),s[1]=='a') scanf("%d",&c[i]),opt[i]=1;
for (j=1;j<=cnt;++j)
{
for (lim=rst[j],SEG.build(),i=1;i<=m;++i)
if (opt[i]) SEG.modify(l[i],r[i],c[i]),SEG.rebuild(); else
{
pi tmp=SEG.query(l[i],r[i]);
if (tmp.fi==lim) ans[i]+=tmp.se;
}
}
for (i=1;i<=m;++i) if (!opt[i]) printf("%d\n",ans[i]);
return 0;
}
D. Is It a Cat?
Prob
不想翻译了总之是个签到题
Tutorial
我发现我完全没有在所有题目中一眼看出签到题的能力的说
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int t,n,a[N],b[N]; char s[N];
int main()
{
//reopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; bool flag=1; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
if (s[i]=='m'||s[i]=='M') a[i]=1; else
if (s[i]=='e'||s[i]=='E') a[i]=2; else
if (s[i]=='o'||s[i]=='O') a[i]=3; else
if (s[i]=='w'||s[i]=='W') a[i]=4; else flag=0;
if (!flag) { puts("NO"); continue; }
for (i=1;i<=n;++i) b[i]=a[i];
for (sort(b+1,b+n+1),i=1;i<=n;++i)
if (a[i]!=b[i]) flag=0;
if (unique(b+1,b+n+1)-b-1<4) flag=0;
puts(flag?"YES":"NO");
}
return 0;
}
E. Merge Sort
Prob
给定\(n,k\)，构造一个长为\(n\)的排列\(a_n\)，使得对这个序列调用归并排序时调用函数的次数恰好为\(k\)
\(n\le 10^5,k\le 2\times 10^5\)
Tutorial
原来是个丁真题，比赛的时候吊死在C和H上了题目都没看
首先因为除了第一次外面的调用外，里面的调用一定是一次调用两次的，因此若\(2|k\)则无解
否则我们总是贪心地让外面大的区间要进行交换，比如现在又区间\(1,2,3,4,5,6\)，如果要让它需要调用归并排序并且满足两个子区间都还是保持有序
我们只需要交换两个子区间相邻的元素即可，即将其变成\(1,2,4,3,5,6\)，然后递归处理即可
注意一下由于这里它的区间定义是左闭右开，而且下标从\(0\)开始，简直和我是完全的反面，所以要特别注意的说
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,k,a[N];
inline void solve(CI l,CI r)
{
if (!k||r-l<=1) return; k-=2; int mid=l+r>>1;
swap(a[mid-1],a[mid]); solve(l,mid); solve(mid,r);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d",&n,&k),i=0;i<n;++i) a[i]=i+1;
if (k%2==0) return puts("-1"),0; --k; solve(0,n);
if (k) return puts("-1"),0;
for (i=0;i<n;++i) printf("%d ",a[i]);
return 0;
}
F. Guess the K-th Zero (Easy version)
Prob
交互题，有一个长度为\(n\)的数组\(a_n\)，每个元素的值未知，但取值只能为\(0/1\)
可以进行不超过\(20\)次询问，询问的格式为一个区间\([l,r]\)，每次交互器会返回这个区间内\(1\)的个数
求序列中第\(k\)个\(0\)的位置
\(n\le 2\times 10^5\)
Tutorial
这个数据范围一眼二分，设询问\([1mid]\)后得到的返回值为\(x\)，则说明\([1,mid]\)中有\(mid-x\)个\(0\)
然后就根据这个和\(k\)的大小关系移动端点即可，主要可能是为了让大家知道有交互题这么一个东西所以选的这题吧
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,t,k;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
scanf("%d%d%d",&n,&t,&k); int l=1,r=n,mid,ret; while (l<=r)
{
mid=l+r>>1; printf("? %d %d\n",1,mid);
fflush(stdout); int x; scanf("%d",&x);
if (mid-x>=k) ret=mid,r=mid-1; else l=mid+1;
}
return printf("! %d\n",ret),fflush(stdout),0;
}
G. Sum Over Zero
Prob
给定一个长为\(n\)的序列\(\{a_n\}\)，你需要将其划分为若干个区间，满足：
- 区间之间彼此不交
- 每个区间\([l,r]\)的元素和均\(\ge 0\)
求所有合法的划分方案中，所有区间的长度之和的最大值
\(n\le 2\times 10^5,a_i\in[-10^9,10^9]\)
Tutorial
感觉最没啥思维含量的一题，好像是这场想+写花的时间最短的一题，也是拿到了这两天的唯一一个一血
首先经典设\(f_{i}\)表示钦定选择了以\(i\)为右端点的区间，此时\([1,i]\)中所有取法的最大值
同时设\(g_i\)表示\([1,i]\)中所有取法的最大值，和\(f_i\)的区别是不强制\(i\)入选，则有\(g_i=\max_\limits{1\le j\le i} f_j\)
考虑\(f_i\)的转移，显然朴素的想法就是枚举\(j<i\)，若可以从\(g_j\)处转移来，则需满足\(pfx_i-pfx_{j}\ge 0\)
，此时\(f_i=\max_\limits{1\le j<i} g_j+(i-j)\)
观察上面的式子，不难发现只要以\(pfx_j\)为下标，\(g_j-j\)为权值把所有以及操作过的点都扔到树状数组上，然后查询就是一个前缀最小值
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,INF=1e9;
int n,a[N],pfx[N],f[N],g[N],rst[N],cnt,ans;
class Tree_Array
{
private:
int bit[N];
public:
#define lowbit(x) (x&-x)
inline void init(void)
{
for (RI i=1;i<=cnt;++i) bit[i]=-INF;
}
inline int get(RI x,int ret=-INF)
{
for (;x;x-=lowbit(x)) ret=max(ret,bit[x]); return ret;
}
inline void add(RI x,CI y)
{
for (;x<=cnt;x+=lowbit(x)) bit[x]=max(bit[x],y);
}
#undef lowbit
}BIT;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%lld",&n),pfx[cnt=1]=0,i=1;i<=n;++i)
scanf("%lld",&a[i]),pfx[i]=pfx[i-1]+a[i],rst[++cnt]=pfx[i];
sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
for (i=0;i<=n;++i) pfx[i]=lower_bound(rst+1,rst+cnt+1,pfx[i])-rst;
for (BIT.init(),BIT.add(pfx[0],0),i=1;i<=n;++i)
f[i]=BIT.get(pfx[i])+i,g[i]=max(g[i-1],f[i]),BIT.add(pfx[i],g[i]-i);
for (i=1;i<=n;++i) ans=max(ans,f[i]);
return printf("%lld",ans),0;
}
H. Watto and Mechanism
Prob
给定\(n\)个文本串和\(m\)个模式串，对于每个模式串判断是否存在某个文本串，使得这两个串之间恰好相差一个字符
\(n,m\le 3\times 10^5,\sum |s|\le 6\times 10^5,s_i\in{a,b,c}\)
Tutorial
首先一眼把所有文本串Hash后的值扔进一个和长度有关的set里，然后对于每个模式串，枚举每一位然后修改成另一个字符，此时变化后的Hash值很好求
然后光速写完交一发WA on 31，估计被卡Hash了，然后就开始加三Hash，魔改seed……
结果上面也提到了，直接GG，只能说自然溢出真是害人不浅啊（下次还写.jpg）
后面补题的时候实在懒得调参了，直接写了个Trie的做法，其实就是把匹配的地方多加上一维表示是否以及出现过改变的位置即可
复杂度看似爆炸其实就是能跑，好像有大佬说因为字符集大小很小的缘故复杂度上界大概是\(O(n\sqrt n)\)的？不过也跑不满的说，实际跑起来很快
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=600005;
int n,m,len; char s[N]; bool flag;
class Trie
{
private:
int ch[N][3],tot; bool end[N];
public:
inline Trie() { tot=1; }
inline void insert(char *s)
{
int len=strlen(s+1),now=1; for (RI i=1;i<=len;++i)
{
if (!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++tot;
now=ch[now][s[i]-'a'];
}
end[now]=1;
}
inline void DFS(CI now=1,CI pos=1,CI sign=0)
{
if (!now) return;
if (pos>len)
{
if (sign&&end[now]) return (void)(flag=1);
return;
}
if (sign) DFS(ch[now][s[pos]-'a'],pos+1,sign); else
{
RI i; for (i=0;i<3;++i) if (s[pos]-'a'!=i&&pos==len&&ch[now][i]&&end[ch[now][i]]) flag=1;
for (i=0;i<3;++i) if (s[pos]-'a'!=i) DFS(ch[now][i],pos+1,1);
DFS(ch[now][s[pos]-'a'],pos+1,sign);
}
}
}T;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%s",s+1),T.insert(s);
for (i=1;i<=m;++i) scanf("%s",s+1),len=strlen(s+1),flag=0,T.DFS(),puts(flag?"YES":"NO");
return 0;
}
Postscript
今天加大班，晚上马上还有三小时的CF，压力拉满了属于是