寒假学习计划
比赛地址
[A] 做游戏
题意
两个人在石头剪刀布,给出每个人出每种类型的次数,求第一个人最多赢几场.
题解
签到题
代码
#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 a,b,c,x,y,z,Ans;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline LL Min(LL a,LL 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("%lld%lld%lld",&a,&b,&c);
scanf("%lld%lld%lld",&x,&y,&z);
Ans=Min(a,y)+Min(b,z)+Min(c,x);
cout<<Ans<<endl;
return 0;
}
[B] 排数字
题意
给出一个由数字构成的字符串,现在要求将其重新排列,求最多能够拼出多少个'616'子串.
题解
签到题
代码
#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,i,a,b,Ans;
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;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d",&n);
scanf("%s",&c);
for (i=0;i<n;i++){
if (c[i]-48==6) a++;
if (c[i]-48==1) b++;
}
Ans=Min(b,a-1);
cout<<Ans<<endl;
return 0;
}
[C] 算概率
题意
有n道题,每道题有一个正确率p_{i}.求恰好答对0,1,...,n道题的概率是多少.
题解
DP
f[i][j]=f[i-1] [ j ] (1-p_{i})+f[i-j] [ j - 1 ] p_{i}
代码
#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 2020
#define MOD 1000000007
#define INF 0x3f3f3f3f
using namespace std;
LL n,i,j;
LL p[N],f[N][N];
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();
for (i=1;i<=n;i++) p[i]=read();
f[0][0]=1;
for (i=1;i<=n;i++){
for (j=0;j<=n;j++){
f[i][j]=(f[i][j]+f[i-1][j]*(1-p[i]+MOD)%MOD)%MOD;
if (j)
f[i][j]=(f[i][j]+f[i-1][j-1]*p[i]%MOD)%MOD;
}
}
for (i=0;i<n;i++)
printf("%lld ",f[n][i]);
printf("%lld",f[n][n]);
return 0;
}
[D] 数三角
题意
给出平面上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 N 520
#define EPS 1e-8
#define INF 0x3f3f3f3f
using namespace std;
int n,i,j,k,Ans;
double x,y,z;
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 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 bool 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 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 double Dis(P a,P b){return pow(a.x-b.x,2)+pow(a.y-b.y,2);}
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;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d",&n);
Ans=0;
if (n<2){
puts("0");
return 0;
}
for (i=1;i<=n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
}
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
for (k=j+1;k<=n;k++){
if (Point_On_Seg(a[i],a[j],a[k])) continue;
if (Point_On_Seg(a[i],a[k],a[j])) continue;
if (Point_On_Seg(a[k],a[j],a[i])) continue;
x=Dis(a[i],a[j]); y=Dis(a[j],a[k]);
z=Dis(a[i],a[k]);
if (x+y-z<0) Ans++;
if (x-y+z<0) Ans++;
if (-x+y+z<0) Ans++;
}
cout<<Ans<<endl;
return 0;
}
[E] 做计数
题意
求有多少组i,j,k,满足\sqrt{i}+\sqrt{j}=\sqrt{k}且ij<n
题解
化简,有
\sqrt{ij}=\frac{k-i-j}{2}
只需计算1-\sqrt{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,l;
LL 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 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 LL Count(int x){
register int i=0,up=int(sqrt(x));
LL sum=0;
for (i=1;i<=up;i++){
if (!(x%i)) sum++;
if (!(x%i) && i*i!=x) sum++;
}
return sum;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
l=int(sqrt(n));
for (i=1;i<=l;i++){
Ans+=Count(i*i);
}
cout<<Ans<<endl;
return 0;
}
[F] 拿物品
题意
有n件物品,每件物品有两个属性a_{i},b_{i}.两个人按照最优策略轮流拿物品,第一个人的分数是拿的物品的a属性之和,第二个人是b属性之和.每个人的目标是最大化自己的分数与对方分数的差值.输出一种方案.
题解
贪心.
根据a_{i}+b_{i}排序,然后从大到小轮流拿.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#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,i,x,y;
vector <int> Ans,ans;
struct Data{
int x,y,z;
}a[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 bool cmp(const Data &a,const Data &b){
return a.x>b.x;
}
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].x=read();
for (i=1;i<=n;i++) a[i].y=read();
for (i=1;i<=n;i++){
x=a[i].x; y=a[i].y;
a[i].x=x+y; a[i].z=i;
}
sort(a+1,a+1+n,cmp);
for (i=1;i<=n;i++){
if (i%2) Ans.push_back(a[i].z);
else ans.push_back(a[i].z);
}
for (i=0;i<Ans.size()-1;i++)
printf("%d ",Ans[i]);
printf("%d\n",Ans[Ans.size()-1]);
for (i=0;i<ans.size()-1;i++)
printf("%d ",ans[i]);
printf("%d",ans[ans.size()-1]);
return 0;
}
[G] 判正误
题意
给出a,b,c,d,e,f,g,判断是否有a^{b}+c^{d}+e^{f}=g
题解
随便选几个模数,然后判断上式是否在模意义下相等.
代码
#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 T,a,b,c,d,e,f,g;
LL p[11]={0,2,3,5,7,11,13,19260817,127,19,23};
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 Mi(LL x,LL y,LL MOD){
LL p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
return Res;
}
inline bool Check(){
register int i=0;
LL x=0,y=0;
for (i=1;i<=10;i++){
x=(Mi(a,d,p[i])+Mi(b,e,p[i])+Mi(c,f,p[i])+p[i])%p[i];
if ((x-g)%p[i] != 0) return 0;
}
return 1;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
a=read(); b=read(); c=read(); d=read();
e=read(); f=read(); g=read();
if (Check()) puts("Yes");
else puts("No");
}
return 0;
}
[H] 施魔法
题意
给出n个物品,每个物品有个权值a_{i}.每一次需要挑选出至少k个物品,获得Maxa_{i}-Mina_{i}的份数.要求每个物品恰好被选中一次.求最小得分.
题解
首先按照权值从小到大排序.显然有DP式子:
f[i]=Min(f[i],f[j]+Score(j+1,i))=Min(f[i],a[i]+f[j]-a[j+1])
所以只需要维护f[i]-a[i+1]的前缀最小值即可.
正确的维护方法是O(n)的,下面写的是O(nlogn)的线段树维护.
代码
#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,k,i;
LL sum;
int a[N];
LL f[N];
struct Tree{
int l,r;
LL d;
}t[N*4];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL 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 Maketree(int x,int low,int high){
int mid=(low+high)>>1;
t[x].l=low; t[x].r=high;
if (low==high){
t[x].d=(low<=k)?INF:0;
if (low==1) t[x].d=-a[1];
return;
}
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
t[x].d=Min(t[l(x)].d,t[r(x)].d);
}
inline LL Query(int x,int low,int high){
int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==low&&t[x].r==high) return t[x].d;
if (high<=mid) return Query(l(x),low,high);
else if (low>mid) return Query(r(x),low,high);
else return Min(Query(l(x),low,mid),Query(r(x),mid+1,high));
}
inline void Add(int x,int low,LL p){
int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==t[x].r){
t[x].d=p; return;
}
(low<=mid)?Add(l(x),low,p):Add(r(x),low,p);
t[x].d=Min(t[l(x)].d,t[r(x)].d);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n);
if (n==1 || k==1){
puts("0"); return 0;
}
if (k==n){
printf("%d\n",a[n]-a[1]);
return 0;
}
Maketree(1,1,n+1);
for (i=k;i<=n;i++){
sum=Query(1,1,i-k+1);
f[i]=sum+a[i];
Add(1,i+1,f[i]-a[i+1]);
}
cout<<f[n]<<endl;
return 0;
}
[I] 建通道
题意
给出一个图,每个点有一个权值v_{i}.现在要求构建一个最小生成树.两点间边权大小是lowbit(v_{i} \ xor \ v_{j}).求最小生成树的权值和.
题解
首先去重,然后从低位向高位枚举.如果剩下的每个点的点权在这一位既有1又有0,假设枚举到了第k位,则答案是2^{k}(n-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;
LL n,i,j,cnt;
LL a[N];
LL Ans,sum;
struct Tree{
int s[2];
LL sum;
}t[N*30];
inline LL Min(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 void Insert(int id){
register int i=0,p=0,x=0;
for (i=0;i<=30;i++){
x=a[id]&(1<<i);
if (x>0) x=1;
if (t[p].s[x])
p=t[p].s[x];
else
p=t[p].s[x]=++cnt;
}
t[p].sum=1;
}
inline void Init(int x){
if (!t[x].s[0] && !t[x].s[1]) return;
if (t[x].s[0]) Init(t[x].s[0]);
if (t[x].s[1]) Init(t[x].s[1]);
if (t[x].s[0]) t[x].sum+=t[t[x].s[0]].sum;
if (t[x].s[1]) t[x].sum+=t[t[x].s[1]].sum;
}
inline LL DP(int x,LL cost){
LL tot=0;
if (!t[x].s[0] && !t[x].s[1]) return 0;
if (!t[x].s[0] || !t[x].s[1]){
if (t[x].s[0]) return DP(t[x].s[0],cost<<1);
if (t[x].s[1]) return DP(t[x].s[1],cost<<1);
}
tot=Min(DP(t[x].s[0],cost<<1)+t[t[x].s[1]].sum*cost,DP(t[x].s[1],cost<<1)+t[t[x].s[0]].sum*cost);
return tot;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
if (n==1){
puts("0"); return 0;
}
for (i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n); a[0]=-1; cnt=0;
for (i=1;i<=n;i++)
if (a[i]==a[i-1]) continue;
else a[++cnt]=a[i];
Ans=0; n=cnt;
if (n==1){
puts("0"); return 0;
}
for (i=0;i<30;i++){
sum=0;
for (j=1;j<=n;j++)
if ((a[j]&(1<<i)) > 0) sum++;
if (sum==0 || sum==n) continue;
cout<<((LL)1<<i)*(LL)(n-1);
return 0;
}
puts("0");
return 0;
}
[J] 求函数
题意
已知有n个函数,f_{i}(x)=k_{i}x+b_{i}
现在有两种操作,第一种是把第i个函数修改为kx+b.第二种是求f_{r}(f_{r-1}(...f_{l+1}(f_{l}(1)))).
对于第二种操作,输出结果.
题解
答案形式为
\sum_{i=l+1}^{r}\Pi_{j=i}^{r}k_{j}b_{i-1}+b_{r}+\Pi_{j=l}^{r}k_{j}
不妨设为g(l,r),令k(i,j)=\Pi_{j=i}^{r}k_{j}.不难得到如下合并公式:
g(l,r)=k(l,h)k(h,r)+k(h,r)(g(l,h)-k(l,h))+g(h,r)-k(h,r)=k(l,r)+k(h,r)(g(l,h)-k(l,h))+g(h,r)-k(h,r)
化成这种形式后就可以用线段树维护了.
代码
#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 MOD 1000000007
#define INF 0x3f3f3f3f
using namespace std;
LL n,m,i,op,x,y,z,Ans;
LL k[N],b[N];
struct Tree{
LL l,r,b,k;
}t[N*8];
struct Data{
LL x,y;
}s;
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 Maketree(LL x,LL low,LL high){
LL mid=(low+high)>>1;
t[x].l=low; t[x].r=high;
if (low==high){
t[x].b=b[low]; t[x].k=k[low];
return;
}
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
t[x].b=((t[l(x)].b*t[r(x)].k)%MOD+t[r(x)].b)%MOD;
t[x].k=(t[l(x)].k*t[r(x)].k)%MOD;
}
inline void Change(LL x,LL low){
LL mid=(t[x].l+t[x].r)>>1;
if (t[x].l==t[x].r){
t[x].k=k[low]; t[x].b=b[low];
return;
}
(low<=mid)?Change(l(x),low):Change(r(x),low);
t[x].b=((t[l(x)].b*t[r(x)].k)%MOD+t[r(x)].b)%MOD;
t[x].k=t[l(x)].k*t[r(x)].k%MOD;
}
inline Data Merge(Data a,Data b){
return (Data){(a.x*b.x)%MOD,((a.y*b.x)%MOD+b.y)%MOD};
}
inline Data Query(LL x,LL low,LL high){
LL mid=(t[x].l+t[x].r)>>1;
if (t[x].l==low && t[x].r==high){
return (Data){t[x].k,t[x].b};
}
if (high<=mid) return Query(l(x),low,high);
else if (low>mid) return Query(r(x),low,high);
else return Merge(Query(l(x),low,mid),Query(r(x),mid+1,high));
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read();
for (i=1;i<=n;i++) k[i]=read();
for (i=1;i<=n;i++) b[i]=read();
Maketree(1,1,n);
while (m--){
op=read(); x=read(); y=read();
if (op==1){
z=read(); k[x]=y; b[x]=z;
Change(1,x);
} else {
s=Query(1,x,y);
printf("%lld\n",(s.x+s.y)%MOD);
}
}
return 0;
}
总结
寒假基础训练第二场,难度明显比第一场有所增加.
这次需要改进的地方在于思维题的处理.首先是F题的式子推的比较慢,连着错了好几次.还有就是I题和之前CF上刚刚做过的一道题特别像,于是没有多想直接拿Trie树上DP写了,浪费了大量的时间,间接导致J题没有写完.
J题的式子一开始推错了,拿两棵线段树用逆元维护了一些奇奇怪怪的东西.后来式子修正后就没有时间去调试了,差1题AK.
接下来还是要加强思维方面的练习,提高推式子的速度.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020寒假算法集训营 Day2题解
本文地址: 2020寒假算法集训营 Day2题解
