第四届辽宁省大学生程序设计竞赛(正式赛)(12/13)

AC情况

赛中通过赛后通过暂未通过
A
B
C
D
E
F
G
H
I
J
K
L
M

整体体验

easy:ABFHL

mid:MJGC

hard:IDKE

心得

感觉出了一堆典题,少数题还有些意思,E题确实神仙

题解

A. 欢迎来到辽宁省赛(签到)

输出27

B. 胜率(枚举)

枚举分母到10000

// Problem: 胜率
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
int t,a,b;
void sol(){scanf("%d.%d",&a,&b);a=a*100+b;//printf("a:%d\n",a);//printf("%d\n",30000/7);rep(i,1,10000){rep(j,0,i){int v=j*10000/i,w=(j*100000/i)%10;if(w>=5)v++;if(v==a){pte(i);return;}}}
}
int main(){t=1;while(t--){sol();}return 0;
}
F. 隔板与水槽(枚举)

枚举一下中间的隔板

// Problem: 隔板与水槽
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=5e3+10;
int t,n,a[N];
void sol(){sci(n);rep(i,1,n)sci(a[i]);ll ans=0;rep(i,2,n-1){ll ma=0,mb=0;rep(j,1,i-1){ma=max(ma,1ll*min(a[i],a[j])*(i-j));}rep(j,i+1,n){mb=max(mb,1ll*min(a[i],a[j])*(j-i));}ans=max(ans,ma+mb);}ptlle(ans);
}
int main(){t=1;while(t--){sol();}return 0;
}
H. 取石子(博弈 性质题)

a^2x^2+ax+1b^2y^2+by+1都是奇数,所以只和初始局面奇偶性有关

// Problem: 取石子
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/H
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
int t,a,b,n;
void sol(){sci(a),sci(b),sci(n);puts(n&1?"Alice":"Bob");
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}
L. 区间与绝对值(莫队+树状数组)

莫队+树状数组维护增加/删除时对应贡献改变即可

n=q=1e5,4s,O(nsqrt(n)logn)还可以

// Problem: 区间与绝对值
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/L
// Memory Limit: 524288 MB
// Time Limit: 8000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int maxn=1e5+10,N=maxn;
int n,m,l,r,a[maxn];
int col[maxn];
int pos[maxn];//pos[i]代表i下标所在的块号
ll now[maxn];//now[i]代表颜色i有几只袜子 
ll res,len,dom,g;
int sz;//块的大小
struct node
{int l,r,id;ll ans;
}e[maxn];
bool cmp1(node a,node b)
{if(pos[a.l]==pos[b.l]){if(pos[a.l]&1)return a.r>b.r;else return a.r<b.r;}return a.l<b.l;
}
bool cmp2(node a,node b)
{return a.id<b.id;
}struct BitPre{ // 求前缀和(可改为max等)int n,tr[N];void init(int _n){n=_n;memset(tr,0,(n+1)*sizeof(*tr));}void addSum(int x,int v){for(int i=x;i<=n;i+=i&-i)tr[i]+=v;}void addMx(int x,int v){for(int i=x;i<=n;i+=i&-i)tr[i]=max(tr[i],v);}int askSum(int x){int ans=0; for(int i=x;i;i-=i&-i)ans+=tr[i];return ans;}int askMx(int x){int ans=0; for(int i=x;i;i-=i&-i)ans=max(ans,tr[i]);return ans;}// 树状数组求从小到大第k个, 1<=k<=sum(n), 1<=x<=nint kth(int k){int x=0;for(int i=1<<std::__lg(n);i;i>>=1){if(x+i<=n && k>tr[x+i]){x+=i;k-=tr[x];}}return x+1;}
}tr,tr2;
void add(int pos,int v){res-=tr.askSum(v);res+=1ll*tr2.askSum(v)*v;res+=tr.askSum(maxn-10)-tr.askSum(v);res-=(1ll*tr2.askSum(maxn-10)-tr2.askSum(v))*v;tr.addSum(v,v);tr2.addSum(v,1);
}
void del(int pos,int v){tr.addSum(v,-v);tr2.addSum(v,-1);res+=tr.askSum(v);res-=1ll*tr2.askSum(v)*v;res-=tr.askSum(maxn-10)-tr.askSum(v);res+=(1ll*tr2.askSum(maxn-10)-tr2.askSum(v))*v;
}
signed main(){sci(n),sci(m);tr.init(maxn-5);tr2.init(maxn-5);rep(i,1,n)sci(a[i]);sz=(int)sqrt(n); for(int i=1;i<=n;++i)pos[i]=1+(i-1)/sz;for(int i=1;i<=m;++i){scanf("%d%d",&e[i].l,&e[i].r);e[i].id=i;}sort(e+1,e+m+1,cmp1);l=1;r=0;//[l,r] 初始什么都没有 for(int i=1;i<=m;++i){for(;r<e[i].r;r++)add(r+1,a[r+1]);for(;r>e[i].r;r--)del(r,a[r]);for(;l<e[i].l;l++)del(l,a[l]);for(;l>e[i].l;l--)add(l-1,a[l-1]);e[i].ans=res;}sort(e+1,e+m+1,cmp2);for(int i=1;i<=m;++i){printf("%lld\n",2ll*e[i].ans);}return 0;
}
M. 让二追三(概率期望)

n<5的情况输出0,n>=5的话,统计每个五连位置00111对答案个数的贡献,

有n-4个这样的五连位置,所以是(n-4)*p,其中p为出现00111的概率

// Problem: 让二追三
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/M
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,mod=1e9+7,inv2=(mod+1)/2;
int t,a,b,n;
int modpow(int x,int n,int mod){int res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
void sol(){sci(a),sci(b),sci(n); if(n<5){puts("0");return;}int p=1ll*a*modpow(b,mod-2,mod)%mod;int np=(1-p+mod)%mod;int w=1ll*p*p%mod*p%mod*np%mod*np%mod;pte(1ll*(n-4)*w%mod);
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}
J. 齐次递推公约数(反演 gcd fib性质)

类斐波那契数列性质,有f(gcd(i,j))=gcd(f(i),f(j))

所以只需要枚举gcd=d,统计gcd=d的(i,j)对数有多少对,

假设有x对,则对答案的贡献是f(d)*x

可以反演,这里用的是减掉d的倍数的方式,得到恰好等于d的方案数

// Problem: 齐次递推公约数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/J
// Memory Limit: 524288 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)]
const int N=3e6+10,mod=1e9+7;
int t,n,f[N],res;
ll cnt[N];
void sol(){sci(n);f[1]=1;rep(i,2,n){f[i]=(3ll*f[i-1]%mod+2ll*f[i-2]%mod)%mod;}per(i,n,1){int tot=1;for(int j=2*i;j<=n;j+=i){cnt[i]-=cnt[j];tot++;}cnt[i]+=1ll*tot*tot;res=(res+1ll*cnt[i]%mod*f[i]%mod)%mod;}pte(res);// int res2=0;// for(int i=1;i<=n;++i){// for(int j=1;j<=n;++j){// res2=(res2+__gcd(f[i],f[j]))%mod;// }// }// pte(res2);
}
int main(){t=1;while(t--){sol();}return 0;
}
G. 树上公约数(树的直径 )

枚举gcd=d,将边权是d的倍数的边都连起来,得到对应森林

若森林里存在长度为k的路径,即森林的某棵树上存在长度>=k的直径

对于每棵树两遍搜索求直径,找到符合条件的最大的d,不存在输出-1

复杂度O(n*max(d_{a_{n}}))

// Problem: 树上公约数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/G
// Memory Limit: 524288 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,M=2e5;
int n,k,p[N],w,tmp,to;
vector<int>fac[N],e[N];
vector<int>edg[N];
bool vis[N];
void dfs(int u,int fa,int dis){vis[u]=1;if(dis>tmp)tmp=dis,to=u;for(auto &v:e[u]){if(v==fa)continue;dfs(v,u,dis+1);}
}
int sol(){per(i,M,1){if(!SZ(edg[i]))continue;for(auto &id:edg[i]){e[id].clear();e[p[id]].clear();vis[id]=0;}for(auto &id:edg[i]){e[id].pb(p[id]);e[p[id]].pb(id);}for(auto &id:edg[i]){if(vis[id])continue;tmp=1;dfs(id,0,1);tmp=1;dfs(to,0,1);if(tmp>=k)return i;}}return -1;
}
int main(){for(int i=1;i<=M;++i){for(int j=i;j<=M;j+=i){fac[j].pb(i);}}sci(n),sci(k);rep(i,2,n){sci(p[i]),sci(w);for(auto &d:fac[w]){edg[d].pb(i);}}pte(sol());return 0;
}
C. 连环爆炸(dp)

题目链接:https://ac.nowcoder.com/acm/contest/68774/C

这个题还挺有意思的,出的挺好的,虽然三个ac的代码都是贪心骗过去的

按怪的先死到后死排序,这样就是无后效性,所以按血量增序排序,

假设我们已经获得了一些预制伤害值就可以顺利触发流程炸死所有怪,

但是不知道这个值具体是多少,所以把这个值存入dp值

按血量增序排序,

dp[i][j]表示前i个怪,手动消灭了j个,令前i个怪全死,还需要在开局预置的伤害数最少是多少

转移就是枚举第i个怪是手动爆的,

还是被前面的崩死的,

还是没崩死,需要开局再补充delta伤害

// Problem: 连环爆炸
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=4e3+10;
int n;
P c[N];
ll sum[N],dp[N][N];//dp[i][j]表示前i个手动爆了j个 前i个全死 需要预支的伤害最小值
void ckmin(ll &x,ll y){x=min(x,y);
}
int main(){sci(n);rep(i,1,n)sci(c[i].fi),sci(c[i].se);sort(c+1,c+n+1);rep(i,1,n){rep(j,0,i){dp[i][j]=4e18;}}dp[1][0]=c[1].fi;dp[1][1]=0;sum[1]=c[1].se;rep(i,1,n-1){sum[i+1]=sum[i]+c[i+1].se;rep(j,0,i){if(sum[i]<c[i+1].fi){ckmin(dp[i+1][j],max(dp[i][j],c[i+1].fi-sum[i]));}else{ckmin(dp[i+1][j],dp[i][j]);}ckmin(dp[i+1][j+1],max(0ll,dp[i][j]-c[i+1].se));}}// rep(i,1,n){// rep(j,0,i){// printf("i:%d j:%d dp:%d\n",i,j,dp[i][j]);// }// }rep(i,0,n){if(dp[n][i]==0){pte(i);return 0;}}return 0;
}

补题部分

D. 三角形打野(计算几何 叉积 三分)
题意


给定x轴正半轴,以及从原点出发的一条射线(在第一象限内),

以及两个点(保证这两个点在给定射线与x正半轴夹角范围内,而不在x轴或给定的射线上),

做一条直线AB,使得这条直线与x正半轴和给定射线组成的三角形将给定的两个点包含在内或边界上。

求满足条件的三角形的最小面积。

两点坐标可能相等,误差小于0.001即为正确

题解

太久不写计算几何感觉基础题都没什么思路,补的话感觉也只能用高中的思路写

手玩一下发现,所求直线AB和x轴的交点是在一个区间内,并且一定过其中至少一个点

记原来给的两个点为P、Q,作PX1平行射线交x轴于X1,作QX2平行射线交x轴于X2

左端点是X1和X2更靠右的那个,右端点可以设成一个很大的值,比如1e18

既然有当前x轴交点坐标,并且能取得最小值,所以凹函数,三分这个x的位置

将当前x轴交点X与P、Q分别连线,XP在XQ顺时针方向说明外侧是XP,否则是XQ

这个也画一下,就很显而易见

然后就是求外侧向量(不妨是XP)与射线的交点,求出交点后用叉积即可求得面积

代码
// Problem: 三角形打野
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)using i64 = long long;
using T = db;
const db eps = 1e-8;struct Point {T x;T y;Point(T x = 0, T y = 0) : x(x), y(y) {}Point &operator+=(const Point &p) {x += p.x, y += p.y;return *this;}Point &operator-=(const Point &p) {x -= p.x, y -= p.y;return *this;}Point &operator*=(const T &v) {x *= v, y *= v;return *this;}friend Point operator-(const Point &p) {return Point(-p.x, -p.y);}friend Point operator+(Point lhs, const Point &rhs) {return lhs += rhs;}friend Point operator-(Point lhs, const Point &rhs) {return lhs -= rhs;}friend Point operator*(Point lhs, const T &rhs) {return lhs *= rhs;}
};T dot(const Point &a, const Point &b) {return a.x * b.x + a.y * b.y;
}T cross(const Point &a, const Point &b) {return a.x * b.y - a.y * b.x;
}
int t;
db k,x,y;
Point a,b;
db pos(db k1,db x,db y){db b=y-k1*x;return -b/k1;
}
db cal(db z){Point p(z,0),o(0,0);Point pa=a-p,pb=b-p,pc,po=o-p;if(cross(pa,pb)>0)pc=pa;else pc=pb;if(fabs(pc.x)<eps){return 0.5*z*k*z;}db xs=k*z/(pc.y-k*pc.x);Point up(z+xs*pc.x,xs*pc.y);pc=up-p;db ans=0.5*fabs(cross(pc,po));return ans;
}
void sol(){scanf("%lf%lf%lf%lf%lf%lf",&y,&x,&a.x,&a.y,&b.x,&b.y);db l=0,r=1e18;k=y/x;l=max(l,pos(k,a.x,a.y));l=max(l,pos(k,b.x,b.y));while(r-l>eps){db m=(l+l+r)/3,m2=(l+r+r)/3;if(cal(m)<cal(m2))r=m2;else l=m;}printf("%.10lf\n",cal(l));
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}
I. 元-神(单调栈 单调队列)
题意

题解

写到这个题的时间有点不够,感觉再手玩玩就玩出来了,诈骗题

考虑暴力怎么做,最暴力当然是从左往右迭代m^2

稍微不那么暴力一点的暴力,是从右到左维护第i个值按时间序都可能是哪些值,是一条链表

但是链表的复杂度也是最坏O(m^2)的,

考虑最右的值只有一种,右数第二的值有两种,以此类推

如果拿第i个值暴力的和第i+1个值的链表上的值一个一个比,自然是O(m^2)

称第i值为L,第i+1个值的链表上当前要比的值为R

1. 若c[L][R]=1,说明第i个值不会变成这个R,那么第i个值左侧的值有L的阻挡也不会变成R,可以把R从链表里删了

2. 若c[R][L]=1,说明第i个值是L的时候,会在这一轮被同化成R,那么把L加到R的前面,停止操作即可

由于比每次都是从链头比的,并且第i条链是从第i+1条链删掉若干次头结点后塞入元素L,

所以,实际是一个栈结构,单调栈维护即可,就是一个弹栈的过程,

弹到为空或出现第二种情况后,把L放入栈顶,此时栈底的元素就是经过若干轮后最终变成的元素

因为还要访问栈底,所以写的实际是个双端队列

代码
// Problem: 元-神
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/I
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e3+10,M=1e6+10;
int n,t,c[N][N],m,a[M];
int sol(){deque<int>q;sci(m);rep(i,1,m){sci(a[i]);}int ans=0;per(i,m,1){while(!q.empty() && !c[q.front()][a[i]])q.pop_front();q.push_front(a[i]);ans^=q.back();//printf("%d ",q.back());}return ans;
}
int main(){sci(n);sci(t); // t=1rep(i,1,n){rep(j,1,n){sci(c[i][j]);}}while(t--){pte(sol());}return 0;
}
E. 神-原(lucas定理 递归 极值点)
题目

思路来源

2023辽宁省赛E-CSDN博客

题解

纯纯神仙题,完全根据思路来源补的代码

虽然lucas的部分是暴力展开的,但是我极值取到的[l,r]就没求出来

虽然理论复杂度在p=2这是1e7左右,但是写的时候是瓶颈,实际提交的过程中一度TLE

最后想起来,p=2的时候,lucas定理的推论,n&m=m时C(n,m)%p=1,

加上之后就AC了,那一刻,真香!

代码
// Problem: 神-原
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/68774/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e6+10,M=1e6,H=2e7+10;
int n,m,p,mod;
int Finv[N],fib[N],fac[N],inv[N];
int f(int a,int n);
int g(int a,int n);
int modpow(int x,int n,int mod){int res=1;for(;n;x=1ll*x*x%mod,n>>=1)if(n&1)res=1ll*res*x%mod;return res;
}
void init(int n){ //n<Ninv[0]=inv[1]=1;fib[0]=0;fib[1]=1;rep(i,2,n)fib[i]=(fib[i-1]+fib[i-2])%mod;for(int i=2;i<=n;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fac[0]=Finv[0]=1;for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,Finv[i]=1ll*Finv[i-1]*inv[i]%mod;
}
int C(int n,int m){if(m<0||m>n)return 0;if(p==2)return (n&m)==m?1:0;int ans=1ll*fac[n]*Finv[n-m]%mod*Finv[m]%mod;//printf("n:%d m:%d c:%d\n",n,m,ans);return ans;
}
int Lucas(int n, int m){if(m<0||m>n)return 0;if(p==2)return (n&m)==m?1:0;return m==0?1:1ll*C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
int g(int a,int n){//if(a<0 || n<0)return 0;int x=n%p,y=n/p,z=a/p;int v=1ll*f(x,x)*f(z-1,y)%p;if(p-1==x)return v;int w=(f(p-1,x+p)-f(x,x+p)+p)%p;if(w){int u=f(z-1,y-1);v=(v+1ll*w*u%p)%p;}return v;
}
int ch(int a,int n){int up=a%p,ans=0;rep(i,0,up){int l=C((n-i)%p,i),r=Lucas((n-i)/p-a/p,a/p);ans=(ans+1ll*l*r%p)%p;}return ans;
}
int f(int a,int n){if(a<0 || n<0)return 0;if(a==n && n<M)return fib[n+1];a=min(a,n);if(n<=p){int ans=0;rep(i,0,a){ans=(ans+C(n-i,i))%mod;}//printf("a:%d n:%d ans:%d\n",a,n,ans);return ans;}if(a<=M){int ans=0;rep(i,0,a){ans=(ans+Lucas(n-i,i))%mod;}//printf("a:%d n:%d ans:%d\n",a,n,ans);return ans;}return (g(a,n)+ch(a,n))%p;
}
int sol(){if(!m)return f(n-1,n-1);if(m==n)return 0;int l=(n-2*m+2)/3+1,r=l+m-1;if(l<1)l=1,r=m;//printf("l:%d r:%d f(n-1,n-1):%d\n",l,r,f(n-1,n-1));int v=(f(n-1,n-1)-f(r-1,n-1)+p)%p;if(l>1)v=(v+f(l-2,n-m-1))%p;return v;
}
int main(){sci(n),sci(m),sci(p);mod=p;init(M);pte(sol());return 0;
}
K. 稻妻扑克(大模拟)

大模拟,咕咕咕

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/181961.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

iphone15 nplayer播放本地电影投屏天猫魔盒(电视)卡顿解决方案

文章目录 投屏环境现象写在前面 解决方案所需投屏app安装方法试用结果如果文章对您有用&#xff0c;欢迎收藏或关注&#xff01; iphone15 nplayer播放本地电影投屏天猫魔盒(电视)卡顿解决方案 投屏环境 全千兆wifi6局域网 1000兆电信宽带 天锚魔盒4Pro 8G&#xff08;M19&…

《研发效能(DevOps)工程师》课程简介(四)丨IDCF

由国家工业和信息化部教育与考试中心颁发的职业技术证书&#xff0c;也是国内首个研发效能&#xff08;DevOps&#xff09;职业技术认证&#xff0c;内涵1000页学习教材2000分钟的课程内容讲解460多个技术知识点300多道练习题。涵盖【组织与协作】、【产品设计与运营】、【开发…

YOLOv8-Seg改进:动态蛇形卷积(Dynamic Snake Convolution) | ICCV2023

🚀🚀🚀本文改进:动态蛇形卷积(Dynamic Snake Convolution),增强微小特征提取能力,引入到YOLOv8-Seg,与C2f结合实现二次创新 🚀🚀🚀Dynamic Snake Convolution亲测在番薯破损分割任务中,mask mAP@0.5 从原始的0.625提升至0.645 🚀🚀🚀YOLOv8-seg创新专…

namespace

1.namespace技术 namespace是Linux内核的一组特性&#xff0c;支持对内核资源进行分区隔离&#xff0c;让一组进程只能看到一组资源&#xff0c;而另一组进程只能看到另一组不同的资源。换句话说&#xff0c;namespace的关键特性是进程隔离。在运行许多不同服务的服务器上&…

2023.11.4 Idea 配置国内 Maven 源

目录 配置国内 Maven 源 重新下载 jar 包 配置国内 Maven 源 <mirror><id>alimaven</id><name>aliyun maven</name><url>http://maven.aliyun.com/nexus/content/groups/public/</url><mirrorOf>central</mirrorOf> …

chrome 扩展 popup 弹窗的使用

popup的基本使用方法 popup介绍 popup 是点击 browser_action 或者 page_action图标时打开的一个小窗口网页&#xff0c;焦点离开网页就立即关闭&#xff0c;一般用来做一些临时性的交互。 popup配置 V3版本中&#xff08;V2版本是在 browser_action 中 &#xff09;&#x…

台灯选用什么类型好?双十一值得入手的护眼台灯推荐

如何给孩子挑选一盏能够护眼的台灯一直是许多家长都为之头痛的一大难题&#xff0c;主要是如今市面上的台灯实在太多了&#xff0c;而且迭代速度非常快&#xff0c;再加上这些产品中还混杂了许多不专业品牌、网红产品和低价劣质产品等等&#xff0c;想要挑选到一款好的台灯确实…

python把Word题库转成Excle题库

又到了一年一度的背题时刻&#xff0c;但是收到的题库是Word版的&#xff0c;页数特别多 话不多说&#xff0c;上代码&#xff0c;有图有真相&#xff0c;代码里面备注的很详细 # 导入所需库 import csv import os import refrom docx import Document from win32com import c…

电子敲木鱼小程序源码系统 支持广告视频流量主 带完整搭建教程

大家好啊&#xff01;好久不见。今天罗峰来给大家分享一款电子敲木鱼小程序源码系统。相信大家都听说这个电子敲木鱼小程序&#xff0c;是当代年轻人缓解压力的一款小程序。今天罗峰就来给大家介绍一下他的功能&#xff0c;这款小程序自带广告视频流量&#xff0c;帮你轻松赚钱…

皮肤病辅助诊断软件,基于Android编写

1.系统介绍 编写的皮肤病辅助诊断软件&#xff0c;包括皮肤病识别、皮肤病区域分割、皮肤病信息介绍、识别历史记录查询、简单图像处理操作以及本机信息查询等功能 2.登录界面 运行之后首先显示登录界面 3.注册界面 注册一个账号 4.主界面 输入用户名密码点击登录按钮…

基于SpringAOP实现自定义接口权限控制

文章目录 一、接口鉴权方案分析1、接口鉴权方案2、角色分配权限树 二、编码实战1、定义权限树与常用方法2、自定义AOP注解3、AOP切面类&#xff08;也可以用拦截器实现&#xff09;4、测试一下 一、接口鉴权方案分析 1、接口鉴权方案 目前大部分接口鉴权方案&#xff0c;一般…

中文sd:SkyPaint-AI-Diffusion

https://huggingface.co/SkyworkAIGC/SkyPainthttps://huggingface.co/SkyworkAIGC/SkyPainthttps://github.com/SkyWorkAIGC/SkyPaint-AI-Diffusionhttps://github.com/SkyWorkAIGC/SkyPaint-AI-Diffusion从model_index.json看&#xff0c;应该算是标准的sd1.5架构了。 {&quo…

【Head First 设计模式】-- 观察者模式

背景 客户有一个WeatherData对象&#xff0c;负责追踪温度、湿度和气压等数据。现在客户给我们提了个需求&#xff0c;让我们利用WeatherData对象取得数据&#xff0c;并更新三个布告板&#xff1a;目前状况、气象统计和天气预报。 WeatherData对象提供了4个接口&#xff1a; …

linux系统SQL server数据库定时收缩

问题现象 出现下图问题&#xff0c;导致连接该数据库的程序不能正常启动 解决办法 定时收缩数据库 数据库定时收缩脚本 需要三个脚本文件 linux_sqlcmd_timing_task_shrink.sh&#xff1a;主脚本文件 # 设置数据库名称、用户名、密码等信息 # db_name"volador"…

Elasticsearch:使用你的 RAG 来进行聊天

什么是人工智能中的检索增强生成&#xff08;RAG&#xff09;&#xff1f; 检索增强生成 (RAG)&#xff0c;与你的文档聊天的超级英雄&#xff0c;架起信息检索和文本生成世界的桥梁&#xff01; 这就像福尔摩斯和莎士比亚联手解决需要大量知识的复杂任务。 RAG 突然介入&…

使用Python自动修改电脑的静态IP地址

目录 一、引言 二、实现思路 三、详细步骤 四、Python代码 五、注意事项 六、适用性和局限性 七、总结 一、引言 在网络应用中&#xff0c;有时我们需要频繁更改电脑的静态IP地址。例如&#xff0c;当我们在不同网络环境&#xff08;家庭、办公室&#xff09;中使用电脑…

洗衣洗鞋柜洗衣洗鞋小程序

支持&#xff1a;一键投递、上门取衣、自主送店、多种支付方式 TEL: 17638103951(同V) -----------------用户下单-------------- -------------------------多种支付和投递方式------------------------- -----------------商家取鞋--------------

C++前缀和算法的应用:最大化城市的最小供电站数目

本文涉及的基础知识点 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 二分法 题目 给你一个下标从 0 开始长度为 n 的整数数组 stations &#xff0c;其中 stations[i] 表示第 i 座城市的供电站数目。 每个供电站可以在一定 范围 内给所…

算法题:203. 移除链表元素(递归法、设置虚拟头节点法等3种方法)Java实现创建链表与解析链表

1、算法思路 讲一下设置虚拟头节点的那个方法&#xff0c;设置一个新节点指向原来链表的头节点&#xff0c;这样我们就可以通过判断链表的当前节点的后继节点值是不是目标删除值&#xff0c;来判断是否删除这个后继节点了。如果不设置虚拟头节点&#xff0c;则需要将头节点和后…

产品经理墨刀学习----注册页面

我们做的产品是一个校园论坛学习开发系统&#xff0c;目前才开始学习。 &#xff08;一&#xff09;流程图 &#xff08;二&#xff09;简单墨刀设计--注册页面 &#xff08;1&#xff09;有账号 &#xff08;a&#xff09;直接登录&#xff1a; &#xff08;b&#xff09;忘…