2021.7.14 Contest 题解
T1:
Description:
给定整数 \(n\)，将 \(1-n\) 分成两组，每一组至少有一个数，并且使得两组数字的和的最大公约数最大，请输出最大的最大公约数。
Input:
一行一个正整数 \(n\)。
Output:
一行一个整数，表示答案。
Sample1 Input:
6
Sample1 Output:
7
Hint:
\(1< n<10^9\)
题目分析：
通过数学归纳法可知，给定 \(1-n\) 中的每一个数，则 \([1,n*(n+1)/2]\) 都能用若干个数的和表示出来。
于是原问题转化为求 \(n*(n+1)/2\) 的最大的和自己不相等的因数。直接把 \(n\) 和 \((n+1)\) 分解质因数即可，稍微注意一些细节。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,tmp1,tmp2;LL ans;inline int read(){int ret=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();return ret*f;}
int main(){
cin>>n,ans=1ll*n*(n+1)/2;if(n%4==0||(n+1)%4==0){cout<<ans/2ll<<'\n';return 0;}
for(register int i=3;i<=sqrt(n);i++) if(n%i==0){tmp1=i;break;} if(!tmp1) if(n%2==0) tmp1=n/2;else tmp1=n;
for(register int i=3;i<=sqrt(n+1);i++) if((n+1)%i==0){tmp2=i;break;}if(!tmp2) if((n+1)%2==0) tmp2=(n+1)/2;else tmp2=n+1;
int tmp=min(tmp1,tmp2);cout<<ans/(LL)tmp<<'\n';return 0;
}
T2:
Description:
在OI大陆，每个OIer都有一个rating。每场比赛以后，参赛者的rating都会发生改变。蜗蜗一共参加了 \(n\) 场比赛，所以他的rating一共变动了 \(n\) 次。在第场比赛后，他的rating变成了 \(a_i\)。我们不在意第 \(1\) 场比赛前他的rating是多少。
佳佳是蜗蜗最好的朋友。蜗蜗想让佳佳对他的rating曲线有深刻的了解。每场比赛过后，蜗蜗都可以决定告诉或不告诉佳佳他最新的rating。如果蜗蜗决定告诉佳佳，佳佳会收到蜗蜗最新的rating，否则佳佳会假设蜗蜗的rating仍旧是上次告诉他的时候的样子。蜗蜗想要保证在任何时候，蜗蜗实际的rating和佳佳知道的蜗蜗的rating的差的绝对值不超过 \(m\)。
在第一场比赛过后，蜗蜗必须告诉佳佳他的rating。
请问蜗蜗最少要告诉佳佳几次他的rating？
Input:
第一行两个整数 \(n,m\)。 第二行 \(n\) 个整数 \(\{a_n\}\)。
Output:
输出一行一个整数表示答案。
Sample1 Input:
4 0
1 2 2 3
Sample1 Output:
3
Sample2 Input:
6 5
6 5 0 10 0 10
Sample2 Output:
2
Hint:
对于 \(20\%\) 的数据，\(1 \le n \le 20\)。
对于 \(100\%\) 的数据，\(1 \le n \le 5 \times 10^3,0 \le m,a_i \le 10^9\)。
题目分析：
阅读理解DP入门题，直接设 \(f_i\) 表示到第 \(i\) 场比赛蜗蜗至少要告诉佳佳rating的次数。\(O(n^2)\) 转移即可，用线段树可以优化成 $ O(nlogn)$.
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 5005
#define LL long long
using namespace std;
int n,m,a[N],f[N][2];struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('\n');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='\n');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
fin>>n>>m;for(register int i=1;i<=n;i++){fin>>a[i],f[i][0]=n,f[i][1]=min(f[i-1][0],f[i-1][1])+1;int Max=a[i],Min=a[i];for(register int j=i-1;j;j--){if(a[j]+m>=Max&&a[j]-m<=Min) f[i][0]=min(f[i][0],f[j][1]);Max=max(Max,a[j]),Min=min(Min,a[j]);}}cout<<min(f[n][0],f[n][1])<<'\n';return 0;
}
T3:
Description:
对于 \([1,n]\) 的子集 \(A\)，它的分数 \(s\) 为
- 初始分数为 \(0\)；
- 对于所有的 \(i \in A\)，\(s+=a_i\)；
- 对于所有满足 \(i,j \in \{x \in A|x \ge 2 \},i^k=j(k \in \{x \in Z|x \ge 2\})\) 的二元组 \((i,j)\)，\(s-=b_j\)。
请求出分数最高的子集的分数是多少。
Input:
第一行一个正整数 \(n\)。
第二行 \(n\) 个正整数 \(\{a_n\}\)。
第三行 \(n\) 个正整数 \(\{b_n\}\)。
Output:
一行一个数表示答案。
Sample1 Input:
4
1 1 1 2
1 1 1 1
Sample1 Output:
4
Sample1 Input:
4
1 1 1 1
1 1 1 2
Sample1 Output:
3
Hint:
对于 \(20\%\) 的数据，\(n \le 20\)。
对于全部数据，\(1 \leq n \leq 10^5,1\leq a_i,b_i \leq 10^9.\)
题目分析：
对于某个质因数的幂次最多只会有 \(16\) 个数。爆搜即可。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,a[N],b[N],v[N];bool vis[N];LL res,ans;
inline void dfs(LL x,int y,LL s){if(x>n){res=max(res,s);return;} vis[x]=1;for(register LL i=1ll*x*x;i<=(LL)n;i*=x) v[i]++;dfs(x*y,y,s+max(0ll,(LL)a[x]-1ll*b[x]*v[x]));for(register LL i=1ll*x*x;i<=(LL)n;i*=x) v[i]--;dfs(x*y,y,s);}
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('\n');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='\n');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
// freopen("set.in","r",stdin);freopen("set.out","w",stdout);
fin>>n;for(register int i=1;i<=n;i++) fin>>a[i];for(register int i=1;i<=n;i++) fin>>b[i];ans=a[1];for(register int i=2;i<=n;i++) if(!vis[i]) res=0,dfs(i,i,0),ans+=res;cout<<ans<<'\n';return 0;
}
T4:
Description:
mifafa 正在编写杭州城市大脑智能引擎。
杭州的道路可以被抽象成为一幅无向图。每条路的初始速度都是 \(1\mathrm{m/s}\)。
mifafa 可以使用 \(1\) \(\texttt{RMB}\) 让任意一条路的速度提升 \(1\mathrm{m/s}\)。如果一条路的速度为 \(a\mathrm{m/s}\)，那么我们需要 \(\frac{1}{a}\mathrm{s}\) 才能通过这条道路。初始 mifafa 有 \(k\) \(\texttt{RMB}\)，mifafa 要把这 \(k\) \(\texttt{RMB}\) 花在升级这些道路上。
现在有两位选手，一位要从 \(s_1\) 走到 \(t_1\)，一位要从 \(s_{2333}\) 走到 \(t_{2333}\)，请问 mifafa 要怎么花钱，使得两位选手花费的总时间最少？当 mifafa 花完 \(\texttt{RMB}\) 之后，两位选手都会走花费时间最少的路。mifafa 花在每条道路上的钱都必须是非负整数。
Input:
第一行三个整数 \(n,m,k\)，表示点数，边数与初始 \(\texttt{RMB}\) 数。
此后 \(m\) 行每行两个数表示边。
此后一行四个整数表示 \(s_1,t_1,s_{2333},t_{2333}\)。数据保证 \(s_1,t_1\)、\(s_{2333},t_{2333}\) 联通
Output:
一行一个数表示答案。相对误差或绝对误差在 \((\frac{4^4-4^{\frac{4}{4^{4-4}+4^{4-4}}}}{4 \times (4+4^{\frac{4}{4+4}})})^{-4-4-4^{4-4}}\) (\(10^{-9}\)) 内即为正确。
Sample1 Input:
6 5 1
1 2
3 2
2 4
4 5
4 6
1 5 3 6
Sample1 Output:
5.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Sample2 Input:
1 0 100
1 1 1 1
Sample2 Output:
0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Sample3 Input:
4 2 3
1 2
3 4
1 2 3 4
Sample3 Output:
0.83333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
Hint:
对于 \(100\%\) 的数据，满足 \(0\le n,m\le 5\times 10^3\)，\(0\le k\le 10^9\)。
题目分析：
先以每个点为起点跑一遍BFS。于是两条路径可以拆成形如 \(s->x->y->t\) 的柿子，其中 \(x->y\) 是两条路径的交。当然，两条路径不相交也可以。于是我们可以预处理出在相交的路径长度为 \(i\) 时剩余的最短路径 \(A_i\)。
我们枚举每个 \(i\)，通过二分来确定分配 \(\texttt{RMB}\) 的方案。我们考虑到对于相交的路径会产生 \(\frac{2}{a}\) 的贡献，而剩余的路径的贡献为 \(\frac{1}{a}\)。我们假设给每条相交的路径上的边分配 \(x\) \(\texttt{RMB}\) ，则给不相交的路径上的每条边分配的 \(\texttt{RMB}\) 数 \(y\) 满足 \(\frac{2}{x-1}-\frac{2}{x} \geq \frac{1}{y}-\frac{1}{y+1}\)，解出满足该方程的最大的 \(y\) ，判断给定的 \(k\) \(\texttt{RMB}\) 是否足够。如果足够，则 \(x\) 可能取到更大的值；反之，\(x\) 的值应当更小。
二分出 \(x\) 之后计算即可。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 5005
#define inf 100000000
#define LL long long
#define DB double
using namespace std;
int n,m,K,s1,t1,s2,t2,H,T,tot,q[N],fir[N],nxt[N<<1],son[N<<1],dis[N][N],A[N];bool ok[N][N],vis[N];DB ans=inf;
inline void add(int x,int y){son[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;} inline void bfs(int s){
for(register int i=1;i<=n;i++) vis[i]=0,dis[s][i]=inf;vis[s]=1,H=T=1,dis[s][s]=0,q[1]=s;while(H<=T)
{int x=q[H++];for(register int i=fir[x];i;i=nxt[i]) if(!vis[son[i]]) vis[son[i]]=1,q[++T]=son[i],dis[s][son[i]]=dis[s][x]+1;}
}
inline int read(){int ret=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();return ret*f;}
int main(){
n=read(),m=read(),K=read();for(register int i=1,x,y;i<=m;i++) x=read(),y=read(),(!ok[x][y])&&(add(x,y),add(y,x),ok[x][y]=ok[y][x]=1,0);A[0]=inf;for(register int i=1;i<=n;i++) A[i]=inf,bfs(i);s1=read(),t1=read(),s2=read(),t2=read();
for(register int i=1;i<=n;i++) for(register int j=1;j<=n;j++){
if((dis[s1][i]^inf)&&(dis[s2][i]^inf)&&(dis[t1][j]^inf)&&(dis[t2][j]^inf)&&(dis[i][j]^inf)) A[dis[i][j]]=min(A[dis[i][j]],dis[s1][i]+dis[s2][i]+dis[t1][j]+dis[t2][j]);
if((dis[s1][i]^inf)&&(dis[s2][j]^inf)&&(dis[t1][j]^inf)&&(dis[t2][i]^inf)&&(dis[i][j]^inf)) A[dis[i][j]]=min(A[dis[i][j]],dis[s1][i]+dis[s2][j]+dis[t1][j]+dis[t2][i]);
}
A[0]=min(A[0],dis[s1][t1]+dis[s2][t2]);for(register int i=0;i<=n;i++){
int x=i,y=A[i],l=1,r=K+1,xx=1;while(l<=r){
int mid=l+r>>1;LL delta=4ll+8ll*mid*(mid-1),X=(LL)ceil((-2.0+sqrt(delta))/4.0);
while(2ll*(X-1)*X>=1ll*mid*(mid-1)&&X>1) X--;LL res=1ll*(mid-1)*x+1ll*y*(X-1);if(res<=K) xx=mid,l=mid+1;else r=mid-1;
}
if(!i&&!A[i]){ans=0;break;}LL delta=4ll+8ll*xx*(xx-1),X=(LL)ceil((-2.0+sqrt(delta))/4.0);while(2ll*(X-1)*(X-1)+2ll*X-1ll*xx*(xx-1)>=0&&X>1) X--;X=max(X,1ll);LL res=1ll*(xx-1)*x+1ll*y*(X-1),tmp=K-res;
DB ret=2.0*x/xx+1.0*y/X;while(tmp&&2ll*X*(X+1)>=1ll*xx*(xx+1)){if(tmp>x) tmp-=x,ret-=(2.0*x/((xx+1)*xx)),xx++;else ret-=(2.0*tmp/((xx+1)*xx)),tmp=0;}
if(tmp) if(tmp<=y) ans=min(ans,-1.0*tmp/((X+1)*X)+ret);else ans=min(ans,-2.0*(tmp-y)/((xx+1)*xx)-1.0*y/((X+1)*X)+ret);else ans=min(ans,ret);
}
printf("%0.12lf\n",ans);return 0;
}