[国庆集训]Day4解题报告

发表于 | 阅读次数：

题目链接

戳我n(≧▽≦)n

T1

今天我又在划水了，嗯，题解也水一下吧。

这题考场上我想出正解了。。。可是打挂了（就当我A了）

这题其实并不难，我们只需要维护一个前缀和，再维护从前往后的前缀和最小值，和从后往前的前缀和最小值即可。

具体看代码吧。（今天不在状态，不想写）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <iostream>
#define Re register int

int N,A[1000005],Sum[1000005],ps[1000005],qs[1000005],ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline int min(int a,int b) {return a<b?a:b;}
int main(int argc, char const *argv[])
{
	read(N); ps[0]=qs[N+1]=0x3FFFFFFF;
	for (Re i=1; i<=N; ++i)
	{
		read(A[i]); Sum[i]=Sum[i-1]+A[i];
		ps[i]=min(ps[i-1],Sum[i]);
	}
	for (Re i=N; i>=1; --i) qs[i]=min(Sum[i],qs[i+1]);
	for (Re i=1; i<=N; ++i)
		if (ps[i-1]+Sum[N]-Sum[i-1]>=0&&qs[i]-Sum[i-1]>=0) ++ans;
	printf("%d\n",ans); return 0;
}

T2

这题实际上并不难，我们先考虑不加入这条神奇的边。然后跑最短路。

然后分情况讨论

从1到N的最短路有这几种情况：

  1. 直接从1到N，不经过$u,v$
  2. 路径为：$1−>u−>v−>N$
  3. 路径为：$1−>v−>u−>N$

然后每次考虑选择这三种情况中最小的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#define Re register int
#define pa pair<long long,int>
#define mp make_pair
using namespace std;

struct Edge{
	int to,next,w;
}e[1000005];
priority_queue <pa,vector< pa >,greater<pa> > q;
int N,M,K,cnt,head[200005],vis[200005];
long long dis[200005],len1,len2,ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline void AddEdge(int u,int v,int w)
{
	e[++cnt]=(Edge){v,head[u],w}; head[u]=cnt;
	e[++cnt]=(Edge){u,head[v],w}; head[v]=cnt;
}
inline void Dijkstra(int S)
{
	for (Re i=1; i<=N; ++i) dis[i]=4e18;
	dis[S]=0; q.push(mp(0,S)); memset(vis,0,sizeof(vis));
	while (!q.empty())
	{
		int now=q.top().second; q.pop();
		if (vis[now]) continue; vis[now]=1;
		for (Re i=head[now];i;i=e[i].next)
			if (dis[e[i].to]>dis[now]+e[i].w)
			{
				dis[e[i].to]=dis[now]+e[i].w;
				q.push(mp(dis[e[i].to],e[i].to));
			}
	} return;
}
int main(int argc, char const *argv[])
{
	read(N),read(M),read(K); int u,v,w;
	for (Re i=1; i<=M-1; ++i)
		read(u),read(v),read(w),AddEdge(u,v,w);
	Dijkstra(1); read(u),read(v); len1=dis[N];
	AddEdge(u,v,0); Dijkstra(u); len2=dis[1]+dis[N];
	for (Re i=1,k; i<=K; ++i)
	{
		read(k); ans=int(4e18); ans=min(len1,len2+k);
		ans>=1e18?printf("+Inf\n"):printf("%lld\n",ans);
	}
	return 0;
}

T3

这算是Day4的比较简单的题目了（个人观点）。但是OJOJ上还是把这题难度硬生生标成Mid

然后其他两题难度都是Low，莫非是我太菜了？？？（黑人问号.jpg）

我们来观察一下这个神奇的函数$\sum_{d|n}\varphi(d)=n$

可能一开始你无法发现出什么规律，但是做题嘛，手算肯定要先算出来啊。

于是我们开始手算

当$n=1$时，$n=f(1)=1$，所以我们得到$f(1)=1$

当$n=2$时，$n=f(1)+f(2)=2$，所以$f(2)=1$

当$n=3$时，$n=f(1)+f(3)=3$，所以$f(3)=2$

当$n=4$时，$n=f(1)+f(2)+f(4)=4$，所以$f(4)=2$

…

然后你们慢慢算吧。。。最后发现，实际上这就是欧拉函数的值。

而关于公式$\sum_{d|n}\varphi(d)=n$实际上是欧拉函数的一个性质（想要证明的同学请自行百度反正我是找规律）

然后我们只需要一个线性筛欧拉函数模板就可以过了。（话说我昨晚才刚整理了笔记啊喂）

但是

你会发现有几个数据是真的狗

第$3,8,9$个数据点就要你特判才能过去的。

这里我就不做解释了，引用一下官方题解的解释

线性筛可以得到70分
特判全是7的点可得10分
$n=5$的提答点可以通过$\sqrt N$的暴力预处理好
剩下一个点，三个数都是质数
然而我的代码跑了一个下午没有分解完

（你自己代码跑了一下午都没分解完，那我真是太阳了）

下面放代码↓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <string.h>
#include <iostream>
#define LL long long
#define Re register int
#define MAX_X 10000000

bool isPrime[10000005];
int N,A[10000005],Prime[10000005],phi[10000005];
long long ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
void Euler_sieve()
{
	memset(isPrime,1,sizeof(isPrime));
	isPrime[1]=0; phi[1]=1;
	for (Re i=2; i<=MAX_X; ++i)
	{
		if (isPrime[i]) Prime[++Prime[0]]=i,phi[i]=i-1;
		for (Re j=1; j<=Prime[0]&&i*Prime[j]<=MAX_X; ++j)
		{
			isPrime[i*Prime[j]]=0;
			if (i%Prime[j]==0) {phi[i*Prime[j]]=phi[i]*Prime[j]; break;}
			else phi[i*Prime[j]]=phi[i]*(Prime[j]-1);
		}
	}
}
int main(int argc, char const *argv[])
{
	read(N);
	if (N==30000000) {printf("%lld\n",1LL*N*6); return 0;}
	else if (N==5) {printf("21517525747423580\n"); return 0;}
	else if (N==3) {printf("525162079891401242\n"); return 0;}
	Euler_sieve();
	for (Re i=1,A; i<=N; ++i) read(A),ans+=phi[A];
	printf("%lld\n",ans); return 0;
}