寒假学习计划
比赛地址
[A] honoka和格点三角形
题意
给出一个n*m的点阵,相邻两点距离为1.求能构成多少个不同的格点三角形,使得三角形面积为1,且至少有一条边平行于坐标轴.
题解
分两种情况考虑.
一种是边平行于y轴,这时又分两种情况,这条边的边长是1还是2.平行x轴的情况类似.注意平行于x轴和y轴的三角形只需要统计一次.
最后未化简的式子是
2(n(n-1)(m-2)+n(n-2)(m-1)+(m-1)(m-2)(n-2)+(n-1)(m-2)^{2})
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
using namespace std;
LL n,m,Ans,x,cnt,sum;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline LL read(){
LL p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read();
n--; m--;
cnt=n*(n+1)%MOD; cnt=cnt*(m-1)%MOD;
Ans+=cnt;
cnt=(n+1)*(n-1)%MOD; cnt=cnt*m%MOD;
Ans+=cnt;
cnt=m*(m-1)%MOD; cnt=cnt*(n-1);
Ans+=cnt;
cnt=(m-1)*(m-1)%MOD; cnt=cnt*n%MOD;
Ans+=cnt;
Ans=Ans*2%MOD;
cout<<Ans<<endl;
return 0;
}
[B] kotori和bangdream
题意
一段乐曲有n个音符,每个音符有两种可能的状态,每种状态会带来不同的分数.求最后分数的期望.
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n;
double ans,cnt,a,b,x;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d%lf%lf%lf",&n,&x,&a,&b);
cnt=x/100*a+(100-x)/100*b;
ans=cnt*n;
printf("%.2lf\n",ans);
return 0;
}
[C] umi和弓道
题意
给出坐标平面的n个目标和射手的坐标,现在要求射手能够射击到的目标数不超过k个,问能否通过在某个坐标轴铺设一段连续的木板来实现这个任务.如果可以,输出木板的最短长度.
题解
首先和射手同一象限的目标一定不会被挡到,直接排除.
剩下的目标和射手的连线会和坐标轴相交于一点,将这一点的横坐标或纵坐标分别记录下来,然后对x轴以及y轴上的这些点的坐标排序.按顺序枚举即可.
注意,有些交点其实是在射手与目标的反向延长线上,这种情况应舍去.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define EPS 1e-8
#define INF 0x3f3f3f3f
using namespace std;
int i,tot,k,n,tot1,tot2;
double y[N],x[N];
struct Vector{
double x,y;
void Clean(void){x=y=0;}
void Write(void){printf("%.3lf %.3lf\n",x,y);}
Vector operator +(Vector p){return (Vector){x+p.x,y+p.y};}
Vector operator -(Vector p){return (Vector){x-p.x,y-p.y};}
double operator *(Vector p){return x*p.y-y*p.x;}
double operator &(Vector p){return x*p.x+y*p.y;}
};
typedef Vector V;
struct Point{
double x,y;
void Clean(void){x=y=0.0;}
void Write(void){printf("%.3lf %.3lf\n",x,y);}
Vector operator +(Point p){return (Vector){x+p.x,y+p.y};}
Vector operator -(Point p){return (Vector){x-p.x,y-p.y};}
};
typedef Point P;
P s,w,a[N];
inline double Min(double a,double b){return (a<b)?a:b;}
inline double Max(double a,double b){return (a>b)?a:b;}
inline double Fabs(double x){return (x<-EPS)?-x:(x>EPS)?x:0;}
inline int Equ(double x,double y){return (Fabs(x-y)<EPS);}
inline double Norm(double x){return (x>0)? (x>EPS)?x:0 : (x<-EPS)?x:0;}
inline bool Point_On_Line(P x,P y,P z){return (Fabs((x-y)*(x-z)) == 0);}
inline bool Point_On_Seg(P x,P y,P z){
double s;
s=(x-y)*(x-z);
if (Fabs(s)>EPS) return 0;
if (Min(y.x,z.x)-EPS>x.x||Max(y.x,z.x)+EPS<x.x) return 0;
if (Min(y.y,z.y)-EPS>x.y||Max(y.y,z.y)+EPS<x.y) return 0;
return 1;
}
inline int LineCross(P a,P b,P c,P d,P &e){
V A=b-a,B=d-c; e=a;
if (Fabs(A*B) == 0)
return (Point_On_Line(a,b,c))?0:-1;
double l=((c-a)*B)/(A*B);
e.x+=(b.x-a.x)*l; e.y+=(b.y-a.y)*l;
return 1;
}
inline void Ready(){
register int i=0,flag=0;
P c,d;
c.x=0; c.y=0; d.x=0; d.y=1;
for (i=1;i<=tot;i++){
flag=LineCross(s,a[i],c,d,w);
if (flag==1 && Point_On_Seg(w,s,a[i])) y[++tot1]=w.y;
}
sort(y+1,y+1+tot1);
d.x=1; d.y=0;
for (i=1;i<=tot;i++){
flag=LineCross(s,a[i],c,d,w);
if (flag==1 && Point_On_Seg(w,s,a[i])) x[++tot2]=w.x;
}
sort(x+1,x+1+tot2);
}
inline void Work(){
register int i=0,sum=tot-k;
double Ans=-1,l=0;
for (i=1;i+sum-1<=tot2;i++){
l=x[i+sum-1]-x[i];
if (Ans > 0) Ans=Min(Ans,l);
else Ans=l;
}
for (i=1;i+sum-1<=tot1;i++){
l=y[i+sum-1]-y[i];
if (Ans > 0) Ans=Min(Ans,l);
else Ans=l;
}
if (Equ(Ans,-1)) puts("-1");
else printf("%.10lf\n",Ans);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%lf%lf",&s.x,&s.y);
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++){
scanf("%lf%lf",&w.x,&w.y);
if (w.x*s.x>0 && w.y*s.y>0) {k--; continue;}
a[++tot]=w;
}
if (k<0) {puts("-1"); return 0;}
Ready(); Work();
return 0;
}
[D] hanayo和米饭
题意
有n个数字,从1到n,现在有一个数字被抹去了,求这个数是多少.
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i;
int a[100010];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=1;i<n;i++) a[i]=read();
sort(a+1,a+n);
if (a[1]==2) {puts("1"); return 0;}
for (i=1;i<n;i++){
if (a[i]!=i) {
printf("%d",i);
return 0;
}
}
printf("%d",n);
return 0;
}
[E] rin和快速迭代
题意
定义f(x)为x的约数个数.求给出n,求f(n)在迭代几次后能达到2.
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
LL n,Ans;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline LL read(){
LL p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Dfs(LL x){
register LL i=0,l=(long long)(sqrt(x)),cnt=0;
if (x==2) return;
if (l*l>x) l--;
//cout<<x<<" "<<l<<endl;
Ans++;
for (i=1;i<=l;i++){
if (!(x%i)) cnt++;
if (!(x%i) && i*i!=x) cnt++;
}
Dfs(cnt);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
Dfs(n);
cout<<Ans<<endl;
return 0;
}
[F] maki和tree
题意
给出一棵树,树上每个点为黑白两种颜色之一.求有多少个不同的点对,使得两点间的路径上只有一个黑点.
题解
树分治裸题.
找到重心后,统计从重心向下走的纯白路径数和只含一个黑点的路径数,然后根据重心节点的颜色统计答案.
官方题解是把白色的连通块缩点,然后符合条件的路径一定是白-黑-白或黑-白这样的组合,直接根据缩点后的大小统计答案即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,x,y,root,lsum=1,tot;
LL white,black,B,W,Ans=0;
char c[N];
int msize[N],size[N],col[N],head[N],v[N];
struct Edge{
int t,next,l;
}e[N*8];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
inline void FindRoot(int x,int fa){
int i=0;
size[x]=1; msize[x]=0;
for (i=head[x];i;i=e[i].next)
if (!v[e[i].t]&&e[i].t!=fa) {
FindRoot(e[i].t,x); msize[x]=Max(msize[x],size[e[i].t]);
size[x]+=size[e[i].t];
}
msize[x]=Max(msize[x],tot-msize[x]);
if (msize[x]<msize[root]) root=x;
}
inline void Dfs(int x,int fa,int p){
register int i=0;
p+=col[x];
if (p>=2) return;
(p)?++black:++white;
for (i=head[x];i;i=e[i].next){
if (v[e[i].t] || e[i].t==fa) continue;
Dfs(e[i].t,x,p);
}
}
inline void Calc(int x){
register int i=0;
B=W=0;
// cout<<x<<" "<<Ans<<endl;
for (i=head[x];i;i=e[i].next){
if (v[e[i].t]) continue;
black=white=0;
Dfs(e[i].t,x,0);
if (col[x]) Ans+=W*white;
else Ans+=W*black+B*white;
// cout<<e[i].t<<" "<<black<<" "<<white<<" "<<Ans<<endl;
B+=black; W+=white;
}
if (col[x]) Ans+=W; else Ans+=B;
}
inline void Solve(int x){
register int i=0;
v[x]=1; Calc(x);
for (i=head[x];i;i=e[i].next)
if (!v[e[i].t]){
root=0; tot=size[e[i].t];
FindRoot(e[i].t,0); Solve(root);
}
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
scanf("%s",&c);
for (i=1;i<=n;i++) col[i]=(c[i-1]=='W')?0:1;
for (i=1;i<n;i++){
x=read(); y=read();
Add(x,y); Add(y,x);
}
msize[root=0]=INF; tot=n;
FindRoot(1,0); Solve(root);
cout<<Ans<<endl;
return 0;
}
[G] eli和字符串
题意
给出一个字符串,求其中的最短子串,满足其中含有至少k个相同字母.
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;
int n,k,Ans,i,j,x;
char c[N];
int w[27][N],sum[27];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); k=read();
scanf("%s",&c);
if (k==1){
puts("1"); return 0;
}
for (i=0;i<n;i++){
x=c[i]-'a'; sum[x]++;
w[x][sum[x]]=i;
}
Ans=INF;
for (i=0;i<26;i++) w[i][0]=1;
for (i=0;i<26;i++)
for (j=k;j<=sum[i];j++)
Ans=Min(Ans,w[i][j]-w[i][j-k+1]+1);
if (Ans!=INF)
cout<<Ans<<endl;
else cout<<-1<<endl;
return 0;
}
[H] nozomi和字符串
题意
给出一个01串,可以执行k次翻转操作:每次操作选择某一位,然后把0变成1,或是1变成0.求能获得的最长全0或全1子串是多少.
题解
签到题.
二分答案+前缀和.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;
int n,k,Ans=0;
int s[N];
char c[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Ready(){
register int i=0,x=0;
for (i=1;i<=n;i++){
x=c[i-1]-48; s[i]=s[i-1]+x;
}
}
inline bool Check(int pos,int l){
int sum=0;
if (pos+l-1>n) return 0;
sum=s[pos+l-1]-s[pos-1];
if (sum<=k || (l-sum) <= k) return 1;
return 0;
}
inline void Work(){
register int i=0,low=1,high=n,mid=0,ans=0;
for (i=1;i<=n;i++){
low=1; high=n; ans=0;
while (low<high){
mid=(low+high)>>1;
if (Check(i,mid)) ans=mid,low=mid+1;
else high=mid-1;
}
while (Check(i,ans+1)) ans++;
while (!Check(i,ans)) ans--;
Ans=Max(Ans,ans);
}
printf("%d\n",Ans);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); k=read();
if (n==1){
puts("1");
return 0;
}
scanf("%s",&c);
Ready(); Work();
return 0;
}
[I] nico和niconiconi
题意
给出一个字符串,对三种子串进行计数:nico,niconi,niconiconi.最后每一种子串可以带来a,b,c的得分.计数过程中,不允许被统计的子串有重叠的情况.求最大得分.
题解
DP.
分三种情况从前向后转移即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 300010
#define INF 0x3f3f3f3f
using namespace std;
int n,i;
LL a,b,c,Ans=0;
char s[N];
LL f[N];
string name[3];
inline LL Max(LL a,LL b){return (a>b)?a:b;}
inline LL read(){
LL p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline LL Check(int A,int B){
register int p=0,i=0;
if (B-A==3) p=0;
else if (B-A==5) p=1;
else p=2;
for (i=A;i<=B;i++)
if (s[i]!=name[p][i-A]) return 0;
if (!p) return a;
else if (p==1) return b;
else return c;
}
inline void DP(){
register int i=0;
memset(f,0,sizeof(f));
for (i=1;i<=n;i++){
f[i]=Ans;
if (i>=4) f[i]=Max(f[i],f[i-4]+Check(i-3,i));
if (i>=6) f[i]=Max(f[i],f[i-6]+Check(i-5,i));
if (i>=10) f[i]=Max(f[i],f[i-10]+Check(i-9,i));
Ans=Max(f[i],Ans);
}
for (i=1;i<=n;i++) Ans=Max(Ans,f[i]);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); a=read(); b=read(); c=read();
scanf("%s",s+1);
if (n<4) {puts("0"); return 0;}
name[0]="nico"; name[1]="niconi"; name[2]="niconiconi";
DP();
cout<<Ans<<endl;
return 0;
}
[J] u's的影响力
题意
已知f(1)=x,f(2)=y,f(n)=f(n-1)f(n-2)a^{b}.求 f(n)
题解
手算前几项后不难得出,答案为
x^{Fib(n-2)}y^{Fib(n-1)}a^{g(n-3)b}
Fib(n)表示斐波那契数列第n项. g(1)=1,g(2)=2,g(3)=4,g(n)=2g(n-1)-g(n-3)
有了g(n)的递推式后,就可以套矩阵快速幂去做了.
注意因为答案要对1e9+7取模,所以需要对指数进行欧拉降幂.也就是说,在计算指数的过程中需要对1e9+6取模.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<unordered_map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL unsigned long long
#define N 4
#define MO 1000000007
#define MOD 1000000006
#define INF 0x3f3f3f3f
using namespace std;
LL n,x,y,a,b,i,cnt,Ans,sum,Sum;
unordered_map<LL,LL> M;
LL Fib(LL x){
if (M.count(x)) return M[x];
LL a=(x+1)/2,b=x/2+1;
return M[x]=((Fib(a)*Fib(b))%MOD+(Fib(a-1)*Fib(b-1)))%MOD;
}
inline LL Mi(LL x,LL y){
LL p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MO:0,p=(p*p)%MO,t<<=1);
return Res;
}
class Matrix{
public:
int sz;
LL a[N][N];
void Init(int x){sz=x;}
void Clear(void){memset(a,0,sizeof(a));}
}A,B,C;
Matrix operator *(Matrix x,Matrix y){
int i=0,j=0,k=0,Sz=x.sz;
Matrix c; c.Clear(); c.Init(Sz);
for (i=1;i<=Sz;i++)
for (j=1;j<=Sz;j++)
for (k=1;k<=Sz;k++)
c.a[i][j]=(c.a[i][j]+x.a[i][k]*y.a[k][j]%MOD+MOD)%MOD;
return c;
}
inline LL Array(LL n){
register LL i=n-3,j=1;
if (n==1) return 1;
if (n==2) return 2;
if (n==3) return 4;
A.Init(3); B.Init(3);
A.Clear(); B.Clear();
B.a[1][1]=B.a[2][2]=B.a[3][3]=1;
A.a[1][1]=2; A.a[1][3]=MOD-1;
A.a[2][1]=1; A.a[3][2]=1;
for (;j<=i;j<<=1){
if (j&i) B=B*A;
A=A*A;
}
return (4*B.a[1][1]%MOD+2*B.a[1][2]%MOD+B.a[1][3])%MOD;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%llu%llu%llu%llu%llu",&n,&x,&y,&a,&b);
if (n<=2){
if (n==1) cout<<x%MO;
if (n==2) cout<<y%MO;
return 0;
}
if (a%MO==0 || x%MO==0 || y%MO==0){
puts("0"); return 0;
}
a%=MO; x%=MO; y%=MO; b%=MOD;
M[1]=M[2]=1;
cnt=Array(n-2); cnt=Mi(a,(cnt*b)%MOD);
sum=Fib(n-2); sum=Mi(x,sum);
Sum=Fib(n-1); Sum=Mi(y,Sum);
Ans=(cnt*sum)%MO; Ans=(Ans*Sum)%MO;
cout<<Ans<<endl;
return 0;
}
总结
寒假基础训练第一场,感觉难度并不是很高,考察的都是很基本的东西.
比赛途中也暴露了一些问题,比如计算几何里判断点在线段上的板子是有错的,里面的式子不知为什么套了个绝对值.也明显感觉到做计几的题不是很熟练,手感有待提高.
下午也犯了n多智障错误,比如最后一题特判前两项忘了取模导致最后WA了6发;F题其实有简单解法,结果没有细想直接拿树分治莽了上去,浪费了一些时间.希望以后几场可以改进.
本文地址: 2020寒假算法集训营 Day1题解