题目

T 1

最小生成树。

刚开始的解法

忽略 $tol_a+tol_b$，零分。

之后

设 $tol_x$ 为最小，向所有点建边。

1
2
3
4
5
int axx=min_element(tol+1,tol+n+1)-tol,tot2=0;
for(int i=1;i<=n;i++) if(i!=axx){
    if(mp[i*1000000+axx]) tot2+=min(tol[i]+tol[axx],mp[i*1000000+axx]);
    else tot2+=tol[i]+tol[axx];
}

最后

要给整个图建如上的虚拟边：

1
2
3
int axx=min_element(tol+1,tol+n+1)-tol;
for(int i=1;i<=n;i++) if(i!=axx)
    a[++m]={i,axx,tol[i]+tol[axx]};

只要跑个 kruskal 就行了。

T 2

暴力跑 dfs 回溯。

选择出这 $n$ 架飞机的降落顺序。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int d){
	if(f) return;
	if(d>n){
		int ls=b[1].t+b[1].l,fg=1;
		for(int i=2;i<=n;i++)
			if(ls>b[i].d+b[i].t) fg=0;
			else if(ls>b[i].t) ls+=b[i].l;
			else ls=b[i].l+b[i].t;
		if(fg) f=1;
	}
	for(int i=1;i<=n;i++) if(!vis[i]) vis[i]=1,b[d]=a[i],dfs(d+1),vis[i]=0;
}

T 3

因为 $0<x\le1$，当 $N$ 到一定值时 $\sum_{i=1}{N}\frac{x{i}}{i}\le0.0001$。

经过粗略估计，$N\le10^5$。

所以当 $N\ge 10^5$ 时，就可以不算了。

1
n=min(100000ll,n);

T 4

辗转相除。

如果 $y=0$ ，$\texttt{Ollie}$ 赢。

如果 $x / y \neq1$ ，$\texttt{Stan}$ 赢。

每一次跟辗转相除一样 $(y,x-y)$。

1
2
3
4
5
bool ans(int x,int y){
    if(!y) return 0;
	if(x/y!=1) return 1;
	return !ans(y,x-y);
}

T 5

并查集。

Fd 函数寻找环的长度，更新最小值。

如果不是环，将 $f_i$ 更新为 $a_i$（加入环中）。

1
2
3
4
5
int fd(int x){
    cnt++;
    if(x==f[x]) return x;
    return fd(f[x]);
}
1
2
if(fd(a[i])==i) ans=min(ans,cnt);
else f[i]=a[i];

T 6

深度为偶数判红，奇数判蓝，其他为灰色。

用 dfs 遍历即可。

1
2
3
4
5
6
7
8
void dfs(int x,int dep){
	vis[x]=1;
	for(int y:v[x]){
		if(vis[y]) continue;
		ma[make_pair(max(x,y),min(x,y))]=(dep&1)+1;
		dfs(y,dep+1);
	}
}

T 7

首先横着和竖着是一定要切的。

在选横竖中最小的一个就行了：

1
2
3
for(int i=1;i<n;i++)
    for(int j=1;j<m;j++)
        ans+=min(a[i],b[j]);

T 8

每一次单行/列修改只有对角线的真正改了。

只要统计 $i=j$ 的情况就行了。

1
if(i==j) ans=(ans+t)&1;

T 9

打表。

1
2
3
4
5
6
7
8
9
if(i/1%10==4) i+=5;
if(i/10%10==4) i+=59;
if(i/100%10==4) i+=599;
if(i/1000%10==4) i+=5999;
if(i/10000%10==4) i+=59999;
if(i/100000%10==4) i+=599999;
if(i/1000000%10==4) i+=5999999;
if(i/10000000%10==4) i+=59999999;
if(i/100000000%10==4) i+=599999999;

统计 $i^2$，$i$，判断 $S(i^2)$ 是否等于 $S(i)^2$。

1
2
3
4
5
int a=0,b=0,c=i,d=i*i;
while(c>0) a+=c%10,c/=10;
a=a*a;
while(d>0) b+=d%10,d/=10;
if(a==b) ans++;

T 10

经过分析可得：

当 $\min{p_1,p_2…p_n} \le 300$：

就用普通的背包即可。

当 $\min{p_1,p_2…p_n} > 300$：

剩下的不需要循环到 $W$，只用到 $W/\max{p_1,p_2…p_n}$ 即可。

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=n;i++) mx=max(v[i],mx),mn=min(mn,v[i]);
if(mn<=300){
    for(int i=1;i<=n;i++)
        for(int j=w;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+p[i]);
    cout<<f[w];
}else{
    for(int i=1;i<=n;i++)
        for(int j=w/mx;j>=1;j--) f[j]=max(f[j],f[j-1]+p[i]);
    cout<<f[w/mx];
}

T 11

约束条件：

一式：$x_a<x_b<x_c<x_d$

二式：$x_b−x_a=2*(x_d−x_c)$

三式：$x_b−x_a<(x_c−x_b)/3$

暴力

枚举，$O(n^4)$

枚举 $x_a,x_b,x_c,x_d$

加一点优化，$O(n^3):$

通过二式：枚举 $x_a,x_c,(x_d-x_c)$

可得 $x_d=(x_d-x_c)+x_c,x_b=2*(x_d−x_c)+x_a$

正解

将二式代入三式：$2*(x_d-x_c)<(x_c-x_b)/3$

移项：$6*(x_d-x_c)<x_c-x_d$

得到：$6*(x_d-x_c)+k=x_c-x_d$

成下图：

其中：$a≤1,d≤n$

而 $a-d=9t+1$，

所以：$9t+1≤n$, 得到 $t≤(n-1)/9$

观察到在其他条件不变的情况下，

只要 $c$ 和 $b$ 满足 $x_c−x_b>6t$,

那么这个魔法阵就一定成立。

所以当 $(a_1<a_2,b_1<b_2)$ 时，

只要 $a_1$ 和 $b_2$ 能够和 $c,d$ 组成魔法阵，

$a_1,b_1$ 也一定能和 $c,d$ 组成魔法阵，所以可以使用前缀和优化

1
2
3
4
5
6
for(int i=1;i<=n/9;i++){
    x=1+9*i,y=0;
    for(int j=2+9*i;j<=n;j++) y+=w[j-x]*w[j-x+i+i],d[j]+=y*w[j-i],c[j-i]+=y*w[j];
    x=8*i+1,y=0;  
    for(int j=n-9*i-1;j>=1;j--) y+=w[j+x]*w[j+x+i],a[j]+=y*w[j+i+i],b[j+i+i]+=y*w[j];
}

T 12

难点：需要用滚动数组优化。

定义 $dp_j$ 为当前猴子爬前 $j$ 棵树所消耗的最小能量值

$dp_j=\min{dp_j,dp_{j-1}}+|a_i-b_j|$

1
2
3
if(j==1) dp[j]=dp[j]+abs(a[i]-b[j]);
else if(i==j) dp[j]=dp[j-1]+abs(a[i]-b[j]);
else dp[j]=min(dp[j],dp[j-1])+abs(a[i]-b[j]);

T 13

难点：排序。

1
2
struct stu{ int a,b,c; }a[100005];
bool cmp(stu x,stu y){ return -y.b*x.c>-x.b*y.c; }

之后一个 01 背包就行了。

T 14

模拟，差分。

分两段，从站 $x$ 到站 $n$ 再从站 $1$ 到站 $y$。

注：$s_i$ 是差分数组。

1
2
if(b<e) s[b]+=p,s[e]-=p;
else s[b]+=p,s[1]+=p,s[e]-=p;

之后查一下 $\left\lceil\dfrac{s_i}{36}\right\rceil$。

T 15

我们发现 $S(fib(x))%9=fib(x)%9$

所以
$(S(fib(1))+S(fib(2))+S(fib(3))+…+S(fib(n))) % 9=(fib(1)+fib(2)+fib(3)+…+fid(n)) % 9$
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[1000005]={0,1,1},ans[1000005]={0,1,2},t,n;
signed main(){
	for(int i=3;i<=1000000;i++){
		f[i]=(f[i-1]+f[i-2])%9;
		ans[i]=(ans[i-1]+f[i])%9;
	}
	cin>>t;
	while(t--) cin>>n,cout<<ans[n]<<'\n';
	return 0;
}

T 15

  1. 把 $a_i$ 排序，方便从小到大扫
  2. 用栈进行操作，如果一个位置k上面有数 $a_i=k$，那么就把所有 $=k$ 的数字入栈。再把栈顶出栈，填到这个位置上，记录下 $dis=pop−push$
  3. 对 dis 进行小到大排序，把 b 数组进行大到小排序，算出答案是 $\sum dis×b_i$

T 16

因为我们要这个正整数尽量大，所以我们要把花瓣变成从 $1$ 开始的连续正整数，且长度尽量大。

如果这些选中的堆拿出花瓣的和已经超过了需要的个数或选中的堆拿出花瓣的和加上未选堆花瓣的和还不够组成新堆，都是不行的。

1
2
3
4
5
6
7
8
9
10
11
12
sort(a+1,a+n+1);
int cnt1=0,cnt=0,v=1;
for(int i=1;i<=n;i++){
	if(a[i]<v){
		cnt1=cnt1+(a[i]-1);
		continue;
	}
	cnt+=(a[i]-v),v++;
}
if(cnt>v) cout<<v<<'\n';
else if(cnt+cnt1>=v) cout<<v+1<<'\n';
else cout<<v<<'\n';

T 17

逆序对。

T 18

模拟。

T 19

求拓扑序。

注意一个点不算环。

T 20

双指针+前缀和。

T 21

若当前这只蚂蚁左边的蚂蚁数量等于右边的蚂蚁数量，答案即为这两数之和。

若左边的蚂蚁数量大于右边的蚂蚁数量时，且当前这只蚂蚁面向左，答案为右边蚂蚁数的两倍，否则多一只。

若左边的蚂蚁数量小于右边的蚂蚁数量，且当前这只蚂蚁面向右，答案为左边蚂蚁数量的两倍，否则多一只。

T 22

逆序对。

T 23

线段树。

主墓碑就是 $[1,1]$ 。