2020.11.20 比赛总结题解合集

news/2024/11/28 7:49:08/

我明白了，我永远不会组合数学…这就去办退学手续…

Part 1 总结

期望得分： 100 + 100 + 100 + [ 0 , 30 ] = [ 300 , 320 ] 100+100+100+[0,30]=[300,320] 100+100+100+[0,30]=[300,320]。
实际得分： 100 + 100 + 90 + 20 = 310 100+100+90+20=310 100+100+90+20=310。
第三题学校评测电脑过慢 T 了一个点。相信在 CCF 神机上就没有这样的问题。
本来差不多 1.5 h 1.5 h 1.5h 就过了前三道题目（真有点让我惊讶…），以为出题人会在 T4 放一个极不可做的题目，以为自己的计数方法是错的，于是成功垫底…

Part 2 题解

tip:如果想看题面请跳到 Part 4。

T1-简单题（easy）

首先很容易发现答案只与 A + B A+B A+B 和 C C C 有关，且每一轮：

A + B ≤ C , ( A + B , C ) − > ( 2 A + 2 B , C − A − B ) A+B\leq C,(A+B,C)->(2A+2B,C-A-B) A+B≤C,(A+B,C)−>(2A+2B,C−A−B)
A + B > C , ( A + B , C ) − > ( A + B − C , 2 C ) A+B> C,(A+B,C)->(A+B-C,2C) A+B>C,(A+B,C)−>(A+B−C,2C)

然后发现这东西好像没有什么规律。那就打表吧！
打出来答案就是 C × 2 k m o d ( A + B + C ) C\times 2^k\bmod (A+B+C) C×2kmod(A+B+C)。
其实这东西很好证明，因为很容易发现这两种情况在 m o d ( A + B + C ) \bmod (A+B+C) mod(A+B+C) 意义下是等价的。

T2-斗地主（playingcard）

这题好像有点熟悉？没关系，反正都是水题。
考虑将一张卡片 ( a i , b i ) (a_i,b_i) (ai​,bi​) 看成一条 ( a i , b i ) (a_i,b_i) (ai​,bi​) 的边。
容易发现当有节点在询问区间以外的时候，我们总有方法给边定向使得在区间内的点每个入度都大于 0 0 0。而当节点全在区间一类的时候，只要存在环我们也可已轻易做到。
那么唯一的不合法情况就是区间内存在完整的连通块是一颗树。我们记录我们连边后每个这样的联通块中编号最小的点 x i x_i xi​ ，编号最大的点 y i y_i yi​ 。
那么不符合条件就是存在 l ≤ x i 且 r ≥ y i l\leq x_i且r≥y_i l≤xi​且r≥yi​。
二维数点板题，直接做就可以了。
其实我们也可以不这么做，我们可以直接记录以 p x p_x px​ 表示右端点为 x x x 的限制的最小的 y y y 然后做一遍后缀最小值即可。
复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn)。

T3-变化的树（change）

真没有什么好说的…考虑 u u u 点对它子树内的一点 v v v 的贡献是：
x − k ( d e p v − d e p u ) = x + k × d e p u − k × d e p v x-k(dep_v-dep_u)=x+k\times dep_u-k\times dep_v x−k(depv​−depu​)=x+k×depu​−k×depv​
发现这些操作都可以写成 k × d e p v + b k\times dep_v+b k×depv​+b 的形式，我们分别用树状数组维护 k , b k,b k,b 即可。
复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn)。

T4-炼金术（alchemy）

看完这题的第一个想法就是直接算叶子节点质因子的分布情况，就能唯一确定一种方案。
就这？这也能当 T4??
一定是我想错了，好像看题目描述每层方案好像和相同的价值的个数有关系，这样做可能会错…
于是就开始了暴力搜索的不归路…
好久没有写过这种要写两个个函数互相调用的hash+记忆化搜索了!

实际上这题就是这么的水…
将 n n n 拆成 p 1 k 1 p 2 k 2 p 3 k 3 … p_1^{k_1}p_2^{k_2}p_3^{k_3}\dots p1k1​​p2k2​​p3k3​​…
直接计算叶子节点质因子的分布情况：
∏ p i ∑ j = 1 k i m j ( m k j ) ( k i − 1 i − 1 ) \prod_{p_i} \sum^{k_i}_{j=1}m^j\binom{m^k}{j}\binom{k_i-1}{i-1} pi​∏​j=1∑ki​​mj(jmk​)(i−1ki​−1​)
然后我们用上我们的分解质因数的卡常技巧暴力算即可。
复杂度： O ( q ∑ k i ) O(q\sum k_i) O(q∑ki​)。

Part 3 实现

T1-easy

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 100000
#define INF 1000000000
#define mem(x,v) memset(x,v,sizeof(x)) LL read(){LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*F;
}int MOD,T,A,B,C,k;int add(int a,int b){return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){return (1LL*a*b)%MOD;}
int fst_pow(int a,int b){int res=1;while(b){if(b&1)res=mul(res,a);a=mul(a,a),b>>=1;}return res;
}int main(){freopen("easy.in","r",stdin);freopen("easy.out","w",stdout);T=read();while(T--){A=read(),B=read(),C=read(),k=read();MOD=A+B+C;printf("%d\n",mul(C,fst_pow(2,k)));}
}

T2-playingcard

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 400000
#define INF 1000000000
#define mem(x,v) memset(x,v,sizeof(x)) LL read(){LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*F;
}int n,m,q,fa[MAXN+5],siz[MAXN+5],cnt[MAXN+5],tot;
int l[MAXN+5],r[MAXN+5],ans[MAXN+5];
struct node{int op,x,y,id;
}a[MAXN+5];int xfind(int x){return (fa[x]==x)?x:fa[x]=xfind(fa[x]);}
void bin(int u,int v){int a=xfind(u),b=xfind(v);if(a==b){cnt[a]++;return ;}fa[b]=a,siz[a]+=siz[b],cnt[a]+=cnt[b]+1;
}bool cmp(node s1,node s2){if(s1.x==s2.x)return s1.op<s2.op;return s1.x>s2.x;
}struct bit{int C[MAXN+5];int lowbit(int x){return x&(-x);}void Insert(int x){while(x<=MAXN)C[x]++,x+=lowbit(x);}int Query(int x){int res=0;while(x)res+=C[x],x-=lowbit(x);return res;}
}T;int main(){freopen("playingcard.in","r",stdin);freopen("playingcard.out","w",stdout);n=read(),m=read();for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1,l[i]=n+1,r[i]=0;for(int i=1;i<=m;i++){int u=read(),v=read();bin(u,v);}for(int i=1;i<=n;i++){int p=xfind(i);l[p]=min(l[p],i),r[p]=max(r[p],i);}for(int i=1;i<=n;i++)if(xfind(i)==i&&siz[i]-1==cnt[i])a[++tot]=(node){0,l[i],r[i],0};q=read();for(int i=1;i<=q;i++){int x=read(),y=read();a[++tot]=(node){1,x,y,i};}sort(a+1,a+tot+1,cmp);for(int i=1;i<=tot;i++)if(a[i].op)ans[a[i].id]=T.Query(a[i].y);else T.Insert(a[i].y);for(int i=1;i<=q;i++)printf("%s\n",ans[i]?"No":"Yes"); 
}

T3-change

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 300000
#define MOD 1000000007
#define INF 1000000000
#define mem(x,v) memset(x,v,sizeof(x)) LL read(){LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*F;
}int add(int a,int b){return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){return (1LL*a*b)%MOD;}
int fst_pow(int a,int b){int res=1;while(b){if(b&1)res=mul(res,a);a=mul(a,a),b>>=1;}return res;
}int n,q,dfn[MAXN+5],ot[MAXN+5],dep[MAXN+5],ct;
vector<int> G[MAXN+5];struct Seg_tree{#define mid (l+r>>1)#define pl (x<<1)#define pr (x<<1|1)int sum[(MAXN<<2)+5],tag[(MAXN<<2)+5];void pushdown(int x){if(tag[x]){tag[pl]=add(tag[pl],tag[x]),tag[pr]=add(tag[pr],tag[x]);sum[pl]=add(sum[pl],tag[x]),sum[pr]=add(sum[pr],tag[x]);tag[x]=0;}}void Insert(int x,int l,int r,int L,int R,int v){if(r<L||R<l)return ;if(L<=l&&r<=R){tag[x]=add(tag[x],v),sum[x]=add(sum[x],v);return ;}pushdown(x);Insert(pl,l,mid,L,R,v),Insert(pr,mid+1,r,L,R,v);}int Query(int x,int l,int r,int pos){if(l==r)return sum[x];pushdown(x);if(pos<=mid)return Query(pl,l,mid,pos);else return Query(pr,mid+1,r,pos);}
}T1,T2;void dfs(int x){dfn[x]=++ct;for(int i=0;i<G[x].size();i++){int v=G[x][i];dep[v]=dep[x]+1;dfs(v);}ot[x]=ct;
}int main(){freopen("change.in","r",stdin);freopen("change.out","w",stdout);n=read();for(int i=2;i<=n;i++){int f=read();G[f].push_back(i);}dfs(1);q=read();while(q--){int op=read(),v=read();if(op==1){int x=read(),k=read();T1.Insert(1,1,n,dfn[v],ot[v],add(x,mul(k,dep[v])));T2.Insert(1,1,n,dfn[v],ot[v],dec(0,k));}else{printf("%d\n",add(T1.Query(1,1,n,dfn[v]),mul(dep[v],T2.Query(1,1,n,dfn[v]))));}}
}

T4-alchemy

暴力

存一下自己喜闻乐见暴力…

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 1000
#define MAXM 1000000
#define MOD 998244353
#define INF 1000000000
#define mem(x,v) memset(x,v,sizeof(x)) LL read(){LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*F;
}int q,n,m,k;
int pri[MAXN+5],pcnt,isp[MAXN+5];
vector<int> num[MAXN+5],P;
int vis[MAXM+5],tot,id[MAXN+5],p[MAXN+5],sz[MAXN+5];
int fac[MAXN+5],ifac[MAXN+5];int add(int a,int b){return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){return (1LL*a*b)%MOD;}
int fst_pow(int a,LL b){int res=1;while(b){if(b&1)res=mul(res,a);a=mul(a,a),b>>=1;}return res;
}void prepare(){fac[0]=1;for(int i=1;i<=MAXN;i++)fac[i]=mul(fac[i-1],i);ifac[MAXN]=fst_pow(fac[MAXN],MOD-2);for(int i=MAXN;i>=1;i--)ifac[i-1]=mul(ifac[i],i);isp[1]=1;for(int i=2;i<=MAXN;i++){if(!isp[i]){num[i].push_back(1);pri[++pcnt]=i;}for(int j=1;j<=pcnt&&i*pri[j]<=MAXN;j++){isp[i*pri[j]]=1;if(i%pri[j]==0){num[i*pri[j]]=num[i];num[i*pri[j]][num[i].size()-1]++;break;}num[i*pri[j]]=num[i];num[i*pri[j]].push_back(1);}}for(int i=2;i<=MAXN;i++){sort(num[i].begin(),num[i].end());int hs=0;for(int j=0;j<num[i].size();j++)hs=hs*10+num[i][j];if(!vis[hs]){vis[hs]=++tot;p[tot]=hs,sz[tot]=num[i].size();}id[i]=vis[hs];}for(int i=1;i<=MAXN;i++)if(!vis[i]){P.clear();int p=i;for(int j=1;j<=5;j++){if(p%10)P.push_back(p%10);p/=10;}sort(P.begin(),P.end());int hs=0;for(int j=0;j<P.size();j++)hs=hs*10+P[j];vis[i]=vis[hs];}
}int f[40][MAXN+5][MAXN+5];int dfs(int,LL,int);bool check(int a,int b){int tmp=10;for(int i=1;i<=5;i++){if((a%tmp)>(b%tmp))return 0;tmp*=10;}return 1;
}int solve(int x,int m,int k,int cnt,int num,int res){if(x<0||cnt>m)return 0;if(!x){return mul(res,ifac[m-cnt]);}if(cnt==m)return 0;int tmp=0;for(int i=1;i<=num;i++){if(!vis[i]||!check(i,x))continue;for(int j=1;j<10;j++){if(!check(i*j,x))break;tmp=add(tmp,solve(x-i*j,m,k,cnt+j,i-1,mul(mul(res,fst_pow(dfs(vis[i],m,k-1),j)),ifac[j])));}}return tmp;
}int dfs(int n,LL m,int k){if(k==0)return fst_pow(m,sz[n]);if(f[n][m][k]>=0)return f[n][m][k];return f[n][m][k]=solve(p[n],m,k,0,p[n],fac[m]);
}int main(){freopen("alchemy.in","r",stdin);freopen("alchemy.out","w",stdout);q=read();prepare();mem(f,-1);while(q--){n=read(),m=read(),k=read();printf("%d\n",dfs(id[n],m,k));}
}

正解

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;#define LL long long
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 1000000
#define MOD 998244353
#define INF 1000000000
#define mem(x,v) memset(x,v,sizeof(x)) LL read(){LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*F;
}int q,n,F;LL m,k;
int pri[MAXN+5],pcnt,isp[MAXN+5],tmp,ans;
int fac[MAXN+5],ifac[MAXN+5],lp[MAXN+5];int add(int a,int b){return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){return (1LL*a*b)%MOD;}
int fst_pow(int a,int b){int res=1;while(b){if(b&1)res=mul(res,a);a=mul(a,a),b>>=1;}return res;
}void prepare(){fac[0]=1;for(int i=1;i<=MAXN;i++)fac[i]=mul(fac[i-1],i);ifac[MAXN]=fst_pow(fac[MAXN],MOD-2);for(int i=MAXN;i>=1;i--)ifac[i-1]=mul(ifac[i],i);isp[1]=lp[1]=1;for(int i=2;i<=MAXN;i++){if(!isp[i])pri[++pcnt]=i,lp[i]=i;for(int j=1;j<=pcnt&&i*pri[j]<=MAXN;j++){isp[i*pri[j]]=1;lp[i*pri[j]]=min(lp[i],pri[j]);if(i%pri[j]==0)break;}}
}int Comb(int a,int b){if(b>a)return 0;return mul(fac[a],mul(ifac[a-b],ifac[b]));
}
int pComb(int a,int b){int res=1;for(int i=0;i<b;i++)res=mul(res,dec(a,i));return mul(res,ifac[b]);
}
bool check(LL a,LL b){if(a==1)return 1;LL res=1;while(b){res*=a,b--;if(res>=MAXN)return 0;}return 1;
}int main(){freopen("alchemy.in","r",stdin);freopen("alchemy.out","w",stdout);prepare();q=read();while(q--){n=read(),m=read(),k=read();tmp=fst_pow(m%MOD,k%(MOD-1)),ans=1;F=check(m,k),m%=MOD;while(n>1){int num=0,tp=n;while(tp%lp[n]==0)num++,tp/=lp[n];int res=0,prd=1,t2=1;for(int j=1;j<=num;j++){prd=mul(prd,m),t2=mul(t2,dec(tmp,j-1));if(F)res=add(res,mul(Comb(num-1,j-1),mul(Comb(tmp,j),prd)));else res=add(res,mul(Comb(num-1,j-1),mul(mul(t2,ifac[j]),prd)));}ans=mul(ans,res),n=tp;}printf("%d\n",ans);}
}

Part 4 resource

T1

d1
d2

T2

d3
d4

T3

d5
d6
d7
d8

T4

d9
d10


http://www.ppmy.cn/news/676675.html

相关文章

游戏毕业设计参考文献合集

游戏毕业设计参考文献合集

如今不管是手机游戏还是网络游戏&#xff0c;都受到热捧&#xff0c;游戏设计也由此走入大家的视线中&#xff0c;本文整理了260个中英文"游戏毕业设计参考文献范例",涵盖游戏角色设计、游戏网站设计、游戏动画设计等等&#xff0c;以供参考。 游戏毕业设计参考文献一…
阅读更多...
排序算法合集

排序算法合集

目录 引言:本博客将逐个分析插入排序,冒泡排序,归并排序,堆排序,快速排序,计数排序,基数排序等常见排序算法 一.时间复杂度为n*n的算法-插入排序与冒泡排序 1.插入排序 2.冒泡排序 二.时间复杂度为n*logn的算法-归并排序,堆排序,快速排序 1.归并排序 2.堆排序 3.快速排…
阅读更多...
简易斗地主（java）

简易斗地主（java）

准备牌-发牌-看牌 通过建立一个集合poker来存储一副牌&#xff1b; 牌分为王与其他&#xff08;其他通过两个数组来构成——花色color与序号num&#xff09;&#xff1b; 通过Collections中的shuffle方法随机发牌&#xff1b; package ChinesePoker;import java.util.Array…
阅读更多...
Eureka 和nacos 的区别

Eureka 和nacos 的区别

目录 1 区别 1 区别 Eureka和Nacos都是用于服务发现和注册的工具&#xff0c;但它们有一些区别&#xff1a;语言支持&#xff1a;Eureka是Netflix开发的&#xff0c;使用Java编写&#xff0c; 而Nacos是阿里巴巴开发的&#xff0c;使用Java编写。 因此&#xff0c;如果您的应用…
阅读更多...
NASA网站曝严重漏洞，或将沦为黑客钓鱼网站？

NASA网站曝严重漏洞，或将沦为黑客钓鱼网站？

美国国家航空航天局&#xff08;NASA&#xff09;天体生物学专用网站存在一个严重的安全漏洞&#xff0c;可能通过伪装带有NASA名称的危险URL来诱骗用户访问恶意网站。 太空旅行无疑是危险的。然而&#xff0c;在访问NASA网站的时候也有可能如此。Cybernews研究团队发现了一个N…
阅读更多...
Launcher 横竖屏幕旋转时会出现应用名称不显示问题

Launcher 横竖屏幕旋转时会出现应用名称不显示问题

因为在屏幕横屏时,launcher 的布局长宽发生了变化,icon 变小 这个时候会重新走调整icon 大小的方法 package/apps/Launcher3/src/com/android/launcher3/DeviceProfile.java 这个类中 我们找到updateIconSize()这个方法 里面有一个 adjustToHideWorkspaceLabels();方法中…
阅读更多...
android三星s8底部菜单,三星Galaxy S8/S8+国行获更新：导航栏可隐藏/视野更宽阔

android三星s8底部菜单,三星Galaxy S8/S8+国行获更新：导航栏可隐藏/视野更宽阔

【IT168 资讯】三星Galaxy S8/S8在国内上市也已经有一段时间了&#xff0c;双曲面全视屏为用户的视觉体验带来前所未有的冲击。接近18&#xff1a;5的屏幕比例让用户无论是阅读还是娱乐时&#xff0c;均获得了更宽阔的视野。不过由于三星Galaxy S8/S8为了追求更高的屏占比&…
阅读更多...
横竖屏切换SurfaceView 大小的调整

横竖屏切换SurfaceView 大小的调整

视频播放的实现大概有以下形式&#xff1a; 1.使用系统自带视频播放类VideoView 2.使用MediaPlayersurfaceView 3.使用一些第三方框架如&#xff1a;vitamio 还有像新浪在github上开放的视频播放框架等... 使用场景&#xff1a; 第一种方法&#xff1a;简单&#xff0c;但…
阅读更多...
最新文章

Copyright @ 2022~2023