题目地址
Edu48
A.Death Note
翻译
你有一个无穷页的本子，每一页可以写\(m\)个名字，
你在第\(i\)天要写\(a_i\)个名字，如果这一页恰好写满了，你就会翻页，
问每天的翻页次数。
题解
傻逼题，求个前缀和，然后除\(m\)计算前缀翻页次数，再和前面一天减一下就好。
代码
#include<cstdio>
#define ll long long
#define MAX 200200
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m;
ll a[MAX];
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)a[i]=read()+a[i-1];
for(int i=1;i<=n;++i)a[i]/=m;
for(int i=1;i<=n;++i)printf("%I64d ",a[i]-a[i-1]);
return 0;
}
B. Segment Occurrences
翻译
给定两个串\(S,T\)，每次询问在\(S[l,r]\)中，\(T\)出现的次数。
题解
这数据范围只要预处理怎么搞都可以吧
#include<cstdio>
#define ll long long
#define MAX 1010
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m,q,a[MAX];
char S[MAX],T[MAX];
bool check(int p)
{
for(int i=p,j=1;j<=m;++i,++j)
if(S[i]!=T[j])return false;
return true;
}
int main()
{
n=read();m=read();q=read();
scanf("%s",S+1);scanf("%s",T+1);
for(int i=1;i+m-1<=n;++i)
if(check(i))a[i]=1;
for(int i=1;i<=n;++i)a[i]+=a[i-1];
while(q--)
{
int l=read(),r=read();
if(r-l+1<m)puts("0");
else printf("%d\n",a[r-m+1]-a[l-1]);
}
return 0;
}
C. Vasya And The Mushrooms
翻译
（我直接说题意吧，懒得翻故事了）
给定一个\(2*n\)的网格，每个格子有个权值，
现在随意指定一条从左上角开始的路径，要求所有格子都被走过，
按照路径顺序给所有格子依次编上\([0..n-1]\)的编号，
最大号权值乘编号的和。
题解
发现这样一个性质，如果当前在\((1,i)\)位置，并且\((2,i-2)\)没被走过，
那么就只能够先一直走到\((1,n)\)再下来再回来这样走了。在\((2,i)\)的位置同理。
那么一个合法的方案一定是先在前面若干列上下上下这样\(S\)形走，
然后一直在这一行走到尽头再转回来走另外一行。
走到尽头再转回来这个过程可以提前处理，只需要从头到尾模拟一遍就好了。
剩下的答案计算也只需要再模拟一遍走\(S\)形的过程。
细节需要注意。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 300300
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,a[MAX],b[MAX];
ll s,sa[MAX],sb[MAX],ra[MAX],rb[MAX],ans,da[MAX],db[MAX];
int main()
{
n=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)b[i]=read();
for(int i=n;i>=1;--i)da[i]=da[i+1]+a[i],db[i]=db[i+1]+b[i];
s=0;for(int i=n;i>=1;--i)sa[i]=sa[i+1]+s,s+=a[i];
s=0;for(int i=n;i>=1;--i)sb[i]=sb[i+1]+s,s+=b[i];
for(int i=n;i>=1;--i)ra[i]=ra[i+1]+1ll*(n-i)*a[i];
for(int i=n;i>=1;--i)rb[i]=rb[i+1]+1ll*(n-i)*b[i];
s=0;
for(int i=1,t=0;i<=n;++i)
if(i&1)
{
ans=max(ans,s+sa[i]+rb[i]+1ll*t*da[i]+1ll*(t+n-i+1)*db[i]);
s+=1ll*t*a[i];++t;
ans=max(ans,s+sb[i]+ra[i+1]+1ll*t*db[i]+1ll*(t+n-i+1)*da[i+1]);
s+=1ll*t*b[i];++t;
}
else
{
ans=max(ans,s+sb[i]+ra[i]+1ll*t*db[i]+1ll*(t+n-i+1)*da[i]);
s+=1ll*t*b[i];++t;
ans=max(ans,s+sa[i]+rb[i+1]+1ll*t*da[i]+1ll*(t+n-i+1)*db[i+1]);
s+=1ll*t*a[i];++t;
}
cout<<ans<<endl;
return 0;
}
D. Vasya And The Matrix
翻译
有一个\(n\)行\(m\)列的矩阵，
告诉你每行、每列的异或和。
还原这个矩阵。
题解
按照二进制位拆开考虑，相当于矩阵只含有\(01\)，要构造一个\(01\)矩阵满足条件即可。
如果是\(01\)矩阵，先随便把左上角\((n-1)*(m-1)\)个数给填上，剩下的利用异或和再填就好了。
额外判断一下\((n,m)\)位置是否合法。
忽然感觉不拆位也可以做？？？反正左上角跑出来二进制位都是满的。。。
写着写着代码就变成这个鬼样子了，丑的不行
#include<cstdio>
#include<cstdlib>
#define ll long long
#define MAX 101
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m,g[MAX][MAX],a[MAX],b[MAX];
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=m;++i)b[i]=read();
for(int i=0;i<30;++i)
{
for(int j=1;j<n;++j)
for(int k=1;k<m;++k)g[j][k]|=1<<i;
int s1=0,s2=0;
for(int j=1;j<n;++j)
if(((m-1)&1)^((bool)(a[j]&(1<<i))))s1^=1,g[j][m]|=1<<i;
for(int j=1;j<m;++j)
if(((n-1)&1)^((bool)(b[j]&(1<<i))))s2^=1,g[n][j]|=1<<i;
if((((bool)(b[m]&(1<<i)))^s1)!=(((bool)(a[n]&(1<<i)))^s2)){puts("NO");exit(0);}
if(((bool)(b[m]&(1<<i)))^s1)g[n][m]|=1<<i;
}
puts("YES");
for(int i=1;i<=n;++i,puts(""))
for(int j=1;j<=m;++j)printf("%d ",g[i][j]);
return 0;
}
E. Rest In The Shades
翻译
在\(x\)轴正半轴上有\(n\)条不相交的线段，
现在有一个光源从\((a,S_y)\)以\(1\)单位每\(s\)的速度移动到\((b,S_y)\)
每次询问一个点，回答这个点处在未被照亮的状态的时间。
题解
考虑一个暴力，对于每次询问，我们可以将它和所有线段在\(y=S_y\)这条直线上的投影给求出来，最终并起来和\([a,b]\)取交就是答案。
我们发现无论点在哪里，只要他们的\(y\)相同，那么它的投影的总长度在\(y=S_y\)上的长度就不会变化。
唯一需要考虑的问题只有他们和\([a,b]\)的交。
因为所有线段不交，所以投影也必定不交，那么二分一下投影在\([a,b]\)内的最左的线段和最右的线段，直接计算答案就好了。细节很迷啊。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 200200
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
double Sy,A,B,L[MAX],R[MAX],p[MAX];
int n,q;
int main()
{
Sy=read();A=read();B=read();
n=read();
for(int i=1;i<=n;++i)L[i]=read(),R[i]=read();
for(int i=1;i<=n;++i)p[i]=p[i-1]+R[i]-L[i];
q=read();
while(q--)
{
double x=read(),y=read();
double xl=A+(x-A)*(-Sy)/(y-Sy);
double xr=B+(x-B)*(-Sy)/(y-Sy);
int x1=upper_bound(&L[1],&L[n+1],xl)-L-1;
int x2=upper_bound(&L[1],&L[n+1],xr)-L-1;
double lf=0,rt=0;
if(x1)lf=p[x1-1]+min(R[x1],xl)-L[x1];
if(x2)rt=p[x2-1]+min(R[x2],xr)-L[x2];
printf("%.10lf\n",(rt-lf)*(y-Sy)/y);
}
return 0;
}
F. Road Projects
翻译
给定一棵树，边有边权。
给定\(m\)个询问，每次给定一个\(x\)
你可以选择任意两个没有边相连的点连上一条长度为\(x\)的边，
要求使得\(1\)和\(n\)之间的最短路最大。
询问之间互相独立。
题解
我们这样子考虑，我们把\(1-n\)的链给拿出来拎直。
这样子就是一条链，然后底下挂着若干子树。
如果链上某个点的子树中，有超过两个点的链，或者这个点有两个以上的不同的儿子。
那么我们直接选两个点连起来即可，这样子最短路一定不会经过这条新边。
当有两个儿子的时候，显然可以把儿子之间连起来，
当有一条长度大于等于\(3\)的链，显然可以把链尾和链的第一个点之间连起来。
所以如果答案会被改变，这条链+子树的形态一定是每个点底下挂着一个点（可以不挂）。
那么，假设\(1-n\)的链上的每个点底下挂的点的距离设为\(l[i]\)，链上两点之间的距离是\(dis(u,v)\)
那么，对于每个询问\(x\)，
我们显然是要找到两个\(1-n\)链上的点\(u,v\)，使得\(l[u]+x+l[v]-S(u,v)\)最大。
或者是找到两个\(1-n\)上距离恰好经过了\(2\)条边的点，使得\(-S(u,v)\)最大。
上面的式子和\(x\)没有任何关系，显然是找\(l[u]+l[v]-S(u,v)\)最大。
那么我们假设\(u>v\)，我们对于每个\(u\)找到前面最大的\(v\)，此时\(u\)固定，
即\(l[v]-S(u,v)\)最大，\(S(u,v)\)可以写成前缀和的形式，那么接着就和\(u\)也无关，
那么这样子只需要记下前缀最大值就好了。后缀做法同理。
细节有点烦，我一开始写错了好多次。。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 300300
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m;
struct Line{int v,next,w;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
int fa[MAX],dep[MAX];
int son[MAX],c[MAX],tot,size[MAX];
ll l[MAX],dis[MAX],S[MAX];
bool vis[MAX];
void dfs(int u,int ff)
{
dep[u]=dep[ff]+1;fa[u]=ff;size[u]=1;l[u]=dis[u];son[u]=0;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff&&!vis[e[i].v])
{
dis[e[i].v]=dis[u]+e[i].w;
dfs(e[i].v,u);
size[u]+=size[e[i].v];
++son[u];l[u]=max(l[u],l[e[i].v]);
}
}
ll mx,Max;
int main()
{
n=read();m=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
Add(u,v,w);Add(v,u,w);
}
dfs(1,0);tot=dep[n];
for(int i=tot,u=n;i;--i)c[i]=u,vis[u]=true,S[i]=dis[u],u=fa[u];
memset(dis,0,sizeof(dis));
for(int i=1;i<=tot;++i)dfs(c[i],0);
mx=l[1]+S[1];Max=-S[tot];
for(int i=2;i<=tot;++i)
{
if(son[c[i]])Max=max(Max,mx+l[c[i]]-S[i]);
mx=max(mx,l[c[i]]+S[i]);
}
mx=l[n]-S[tot];
for(int i=tot-1;i;--i)
{
if(son[c[i]])Max=max(Max,mx+l[c[i]]+S[i]);
mx=max(mx,l[c[i]]-S[i]);
}
for(int i=1;i<tot-1;++i)
Max=max(Max,-S[i+2]+S[i]);
bool fl=false;
for(int i=1;i<=tot;++i)
if(son[c[i]]>=2||size[c[i]]>=3)fl=true;
while(m--)
{
ll x=read()+Max+S[tot];if(fl)x=S[tot];
printf("%I64d\n",min(x,S[tot]));
}
return 0;
}
G. Appropriate Team
翻译
给定\(n\)个数\(\{a_i\}\)，
求存在一个数\(v\)，满足\(gcd(a_i,v)=X,lcm(a_j,v)=Y\)的\((i,j)\)对数。
题解
不看题解不会做系列
先对于\(y\) 分解质因数，这个东西可以泼辣的肉。
然而题解给了一种很神仙的方法。
首先你对于所有小于\(y^{1/3}\)的数暴力分解，
这样子最多剩下一个大于\(y^{1/3}\)的质数，或者是\(y^{1/3}\)的平方。
因为题目是要找到一个合法的\(v\)，所以在分解的时候只需要考虑和所有\(a_i\)相关的质因子。
和\(a_i\)无关的质因子是可以直接忽视掉的，所以再利用每个\(a_i\)来求剩下的那个大因子。
首先你拿到\(a_i\)，把它所有小于y含有的小于\(y^{1/3}\)的质因子除掉，
然后剩下的部分和\(y\)求个\(gcd\)检查是否合法。
最终分解出来的质因子数量并不会很多。大概不会超过\(20\)个吧。
回到题目，如果\(y\%x\neq 0\)，直接判\(0\)。
现在的条件是\(x|y\)。我们分\(a_i\)和\(a_j\)考虑。
首先\(a_i\)一定是\(x\)的倍数，不妨令\(a_i=kx\)，
把\(k\)用\(y\)的所有因数分解，状压未含有哪些因数，统计每个状压结果的个数。
然后对于这个状压结果，计算超集和。
再对于每个\(a_j\)考虑可以和它产生贡献的\(a_i\)
因为\(v\)是\(y\)的因数，而又是\(x\)的倍数，并且\((v,a_i)=x\)
所以\(v\)只能含有\(a_i\)不含有的那部分因数，也就是上面状压的结果。
那么，对于每个\(a_j\)，我们求出最小的\(v\)就可以直接利用超集和计算符合条件的数的个数了。
考虑怎么求出最小的\(v\)满足\(lcm(v,a_j)=y\)
我们从最小值开始，\(v\)的最小值是\(x\)，
每次让\(v\)乘上\(y/lcm(v,a_i)\)就好了，直到\(lcm=y\)终止。
那么只需要求出所有不含有\(v\)这些质因数的\(a_i\)了。
也就是所有不含有\(v/x\)这些质因数的\(k\)，那么直接美滋滋的用超集和可以很容易的计算啦。
第一次用C++11，感觉很爽啊
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 200300
#define ll long long
ll a[MAX],c[MAX],x,y,all[MAX];
vector<ll> p;
ll divide(ll x){for(ll d:p)while(x%d==0)x/=d;return x;}
int n;
ll Multi(ll a,ll b,ll MOD)
{
ll s=0;
while(b){if(b&1)s=(s+a)%MOD;a=(a+a)%MOD;b>>=1;}
return s;
}
ll fpow(ll a,ll b,ll MOD)
{
ll s=1;
while(b){if(b&1)s=Multi(s,a,MOD);a=Multi(a,a,MOD);b>>=1;}
return s;
}
bool Miller_Rabin(ll x)
{
if(x==2)return true;
for(int tim=10;tim;--tim)
{
ll a=rand()%(x-2)+2;
if(fpow(a,x-1,x)!=1)return false;
ll p=x-1;
while(!(p&1))
{
p>>=1;ll nw=fpow(a,p,x);
if(Multi(nw,nw,x)==1&&nw!=1&&nw!=x-1)return false;
}
}
return true;
}
ll Pollard_rho(ll n,int c)
{
ll i=0,k=2,x=rand()%(n-1)+1,y=x;
while(233)
{
++i;x=(Multi(x,x,n)+c)%n;
ll d=__gcd((y-x+n)%n,n);
if(d!=1&&d!=n)return d;
if(x==y)return n;
if(i==k)y=x,k<<=1;
}
}
vector<ll> fac;
void Fact(ll n,int c)
{
if(n==1)return;
if(Miller_Rabin(n)){fac.push_back(n);return;}
ll pp=n;while(pp>=n)pp=Pollard_rho(n,c--);
Fact(pp,c);Fact(n/pp,c);
}
int get(ll x)
{
int S=0;
for(int j=0,l=p.size();j<l;++j)
if(x%p[j]==0)S|=1<<j;
return S;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>x>>y;
if(y%x){cout<<0<<endl;return 0;}
for(int i=1;i<=n;++i)cin>>a[i];
Fact(y,123);
sort(fac.begin(),fac.end());
for(int i=0,l=fac.size();i<l;++i)
if(i==0||fac[i]!=fac[i-1])p.push_back(fac[i]);
for(int i=1;i<=n;++i)
if(a[i]%x==0)
{
int S=get(a[i]/x);
++c[((1<<p.size())-1)^S];
}
for(int i=0;i<MAX;++i)
{
for(int j=i;j;j=(j-1)&i)all[j]+=c[i];
all[0]+=c[i];
}
ll ans=0;
for(int i=1;i<=n;++i)
{
if(y%a[i])continue;
ll cur=x;
while(233)
{
ll lcm=(a[i]/__gcd(a[i],cur))*cur;
if(lcm==y)break;
cur*=y/lcm;
}
cur/=x;ans+=all[get(cur)];
}
cout<<ans<<endl;
return 0;
}