这波啊，这波是直接倒一
考数据结构必挂选手
四道原题，两道没改，一道没做过，其中 T1 当时过了这次却挂了 10 分，这都是需要反思的。
注 意 爆 零
T1:100 ( ightarrow) 90
T4:30 ( ightarrow) 5
T1:凉宫春日的忧郁
算法1：取对数
对 (X^Y) 和 (Y!) 取对数，前者是 (Ylog X)，后者是 (log1+log2+cdots+log Y)，可以直接比较大小，记得防止炸精。
算法2：乱搞
可以发现分界线大概是 (cfrac{X}{Y}=cfrac{2}{5})。直接判断即可。不过要注意在小数据是不满足这个规律的，所以小数据需要暴力，否则会像我一样挂 (10 ext{pts})。
代码不粘了，有手就行。
T2:漫无止境的八月
可以发现，只有在所有模 (k) 意义下同余的位置的和都相等的时候游戏才能获胜。所以开哈希表当桶存一下就好了。
出题人丧心病狂居然连 unordered_map 都卡。人傻了。
记得开 long long。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e6+10;
const int Mod=1152763;
int n,K,q;
int a[maxn],sum[maxn];
struct Node{
int to,w,nxt;
}e[maxn<<1];
inline int read(){
int x=0;bool fopt=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return fopt?x:-x;
}
int head[Mod+10],cnt;
inline void push(int u,int v){
e[++cnt].to=v;
e[cnt].w=1;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inline void add(int u){
int x=u%Mod;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to==u)return e[i].w++,void();
push(x,u);
}
inline void del(int u){
int x=u%Mod;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to==u)return e[i].w--,void();
throw;
}
inline int query(int u){
int x=u%Mod;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to==u)return e[i].w;
return 0;
}
signed main(){
#ifndef LOCAL
freopen("august.in","r",stdin);
freopen("august.out","w",stdout);
#endif
n=read();K=read();q=read();
for(int i=1;i<=n;i++){
a[i]=read();
sum[i%K]+=a[i];
}
for(int i=0;i<K;i++)
add(sum[i]);
puts(query(sum[0])==K?"Yes":"No");
//实际上如果符合条件的话所有的sum值都是相等的，但只有sum[0]一定存在(k=n=1)，所以查询sum[0]
while(q--){
int pos=read(),dx=read();
del(sum[pos%K]);
sum[pos%K]+=dx;
add(sum[pos%K]);
puts(query(sum[0])==K?"Yes":"No");
}
return 0;
}
另一种思想是利用差分，就不用开桶了，还可以防止炸内存。通通的题解
T3:射手座之日
关于 dfs 序的部分，只要计算子节点相互之间的 (size) 乘积乘上当前点的权值即可。
正解是 dsu on tree，用两个数组维护当前点是否是一个极长区间的左右端点，同时需要记录另一个端点的位置，一边合并一边统计方案数。
一般 dsu on tree 的题都能用线段树合并，本题也相同。时间复杂度都是 (O(nlog n)) 的。
T4:货车运输
是 NOIP 2013 的原题。
首先对于两个点的若干条简单路径中，一定要选路径中权值最小的边最大的一条路径。所以我们能想到最大生成树。
当把最大生成树建出来之后，直接用树链剖分+线段树求路径上的最小值就可以了。
依然需要开 long long。
事实上，用树剖的时间复杂度是小常数 (O(nlog^2 n))，但足以通过本题。如果使用倍增可以做到 (O(nlog n))，而且代码短很多。但是我不想写倍增，因为三个 namespace 很带感。
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int INF=0x3f3f3f3f;
int n,m;
vector<pair<int,int> > g[maxn];
struct Edge{
int from,to,w;
friend inline bool operator <(register const Edge& A,register const Edge& B){
return A.w>B.w;
}
}e[maxn];
inline int read(){
int x=0;bool fopt=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return fopt?x:-x;
}
namespace DSU{
int f[maxn];
inline void Init(){
for(int i=1;i<=n;i++)
f[i]=i;
}
int Find(int x){
return x==f[x]?x:(f[x]=Find(f[x]));
}
inline bool isLink(int u,int v){
return Find(u)==Find(v);
}
inline void Merge(int u,int v){
int fau=Find(u),fav=Find(v);
if(fau!=fav)f[fau]=fav;
}
}
using namespace DSU;
inline void Kruskal(){
sort(e+1,e+m+1);
int tot=0;
for(int i=1;i<=m;i++){
if(tot==n-1)break;
int u=e[i].from,v=e[i].to,w=e[i].w;
if(!isLink(u,v)){
Merge(u,v);tot++;
g[u].push_back(make_pair(v,w));
g[v].push_back(make_pair(u,w));
}
}
}
namespace LinkCut{
int fa[maxn],dep[maxn],siz[maxn],son[maxn],val[maxn];
void dfs1(int u){
dep[u]=dep[fa[u]]+1;siz[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i].first;
if(v==fa[u])continue;
fa[v]=u;val[v]=g[u][i].second;
dfs1(v);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]])son[u]=v;
}
}
int Nodetot;
int top[maxn],dfn[maxn],rank[maxn];
void dfs2(int u,int t){
top[u]=t;dfn[u]=++Nodetot;rank[Nodetot]=u;
if(son[u])dfs2(son[u],t);//注意一定要先递归重儿子！
for(int i=0;i<g[u].size();i++){
int v=g[u][i].first;
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
}
using namespace LinkCut;
namespace SEG{
#define lson (rt<<1)
#define rson (rt<<1|1)
int tree[maxn<<2];
inline void pushup(int rt){
tree[rt]=min(tree[lson],tree[rson]);
}
void build(int rt,int l,int r){
if(l==r)return tree[rt]=val[rank[l]],void();
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(rt);
}
int query(int rt,int l,int r,int s,int t){
if(r<l)return INF;
if(s<=l&&r<=t)return tree[rt];
int mid=(l+r)>>1,ans=INF;
if(s<=mid)ans=min(ans,query(lson,l,mid,s,t));
if(t>mid)ans=min(ans,query(rson,mid+1,r,s,t));
return ans;
}
inline int querymin(int u,int v){
int ans=INF;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ans=min(ans,query(1,1,n,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
ans=min(ans,query(1,1,n,dfn[v]+1,dfn[u]));
return ans;
}
#undef lson
#undef rson
}
using namespace SEG;
int main(){
#ifndef LOCAL
freopen("truck.in","r",stdin);
freopen("truck.out","w",stdout);
#endif
n=read();m=read();Init();
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
e[i]=(Edge){u,v,w};
}
Kruskal();dfs1(1);dfs2(1,1);build(1,1,n);
int T=read();
while(T--){
int u=read(),v=read();
if(!isLink(u,v))puts("-1");
else printf("%d
",querymin(u,v));
}
return 0;
}
T5:作业
提供一个非正解。这道题在题库里的时限卡到了 5s 导致会 TLE 两个点，在洛谷和 BZOJ 上是可以 A 的。
其实也没啥，暴力一看就是莫队+权值树状数组作桶。时间复杂度 (O(msqrt{nlog n}))。第一问有手就行，第二问就是 HH的项链 改一改。
%:pragma GCC target("avx")
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast","inline","-ffast-math")
%:pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,m,S;
int c[maxn];
struct Node{
int l,r,a,b,id;
friend inline bool operator <(register const Node& A,register const Node& B){
return (A.l/S)^(B.l/S)?A.l<B.l:(((A.l/S)&1)?A.r<B.r:A.r>B.r);
}
}q[maxn];
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2?(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2?EOF:*p1++):*p1++)
inline int read(){
int x=0;bool fopt=1;char ch=gc();
for(;!isdigit(ch);ch=gc())if(ch=='-')fopt=0;
for(;isdigit(ch);ch=gc())x=(x<<3)+(x<<1)+ch-48;
return fopt?x:-x;
}
int tree[2][maxn];
#define lowbit(x) (x&-x)
inline void add(int x,int b,int opt){
while(x<=n){
tree[opt][x]+=b;
x+=lowbit(x);
}
}
inline int query(int x,int opt){
int ret=0;
while(x){
ret+=tree[opt][x];
x-=lowbit(x);
}
return ret;
}
int cnt[maxn];
pair<int,int> res[maxn];
inline void moadd(int x){
add(c[x],1,0);
if(!cnt[c[x]])add(c[x],1,1);
cnt[c[x]]++;
}
inline void model(int x){
add(c[x],-1,0);
cnt[c[x]]--;
if(!cnt[c[x]])add(c[x],-1,1);
}
int main(){
#ifndef LOCAL
freopen("homework.in","r",stdin);
freopen("homework.out","w",stdout);
#endif
n=read();m=read();
for(int i=1;i<=n;i++)
c[i]=read();
S=sqrt(n);
for(int i=1;i<=m;i++){
int l=read(),r=read(),a=read(),b=read();
q[i]=(Node){l,r,a,b,i};
}
sort(q+1,q+m+1);
int l=1,r=0;
for(int i=1;i<=m;i++){
int s=q[i].l,t=q[i].r,a=q[i].a,b=q[i].b;
while(r<t)moadd(++r);
while(l>s)moadd(--l);
while(r>t)model(r--);
while(l<s)model(l++);
res[q[i].id].first=query(b,0)-query(a-1,0);
res[q[i].id].second=query(b,1)-query(a-1,1);
}
for(int i=1;i<=m;i++)
printf("%d %d
",res[i].first,res[i].second);
return 0;
}