[国庆集训]Day4解题报告

题目链接

T1

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

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

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

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

#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到N，不经过 $u,v$
路径为： $1−>u−>v−>N$
路径为： $1−>v−>u−>N$

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

#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$ 的暴力预处理好
剩下一个点，三个数都是质数
然而我的代码跑了一个下午没有分解完

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

下面放代码↓

#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;
}