• 2022/7/28

    E-Music Game_dp

    dp[i]表示前i个的期望是多少，第i个失败的话就是dp[i]=dp(i-1)*(100-p[i]),成功的话就要去枚举起点，所以方程就是dp[i]=dp[i-1]*(1-p_{i})+\sum_{j=1}^{i}[((i-j+1)^{m}+dp[j-2])*(1-p_{j-1})*\prod_{k=j}^{i}p_{k}] 

    图片和题解都是这个

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll n,m,p[1005],dp[1005],mul[1005][1005];
    8. ll qpow(ll a,ll b){
    9.     ll res=1;
    10.     while(b){
    11.         if(b&1) res=res*a%mod;
    12.         a=a*a%mod;
    13.         b>>=1;
    14.     }
    15.     return res;
    16. }
    17. int main(){
    18.     ll inv=qpow(100,mod-2);
    19.     cin>>n>>m;
    20.     for(int i=1;i<=n;i++) cin>>p[i],mul[i][i]=p[i]*inv%mod;
    21.     for(int i=1;i<=n;i++)
    22.     for(int j=i+1;j<=n;j++)
    23.         mul[i][j]=(mul[i][j-1]*p[j]%mod)*inv%mod;
    24.     for(int i=1;i<=n;i++){
    25.         dp[i]=(dp[i-1]*(100-p[i])%mod)*inv%mod;
    26.         for(int j=1;j<=i;j++){
    27.             dp[i]=(dp[i]+(((qpow(i-j+1,m)+dp[j-2])%mod)*((100-p[j-1])*inv%mod)%mod)*mul[j][i]%mod)%mod;
    28.         }
    29.     }
    30.     printf("%lld\n",dp[n]);
    31.     system("pause");
    32.     return 0;
    33. }

     1249C2 - Good Numbers (hard version)

    其实是和二进制差不多的，但是3进制会有2这个余数，而题目中又说不能有重复的，所以碰到2的话比该位高的最近的0改为1，其后全改为0就可以啦

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll q,n,fac[66],vis[66];
    8. ll qpow(ll a,ll b){
    9.     ll res=1;
    10.     while(b){
    11.         if(b&1) res=res*a;
    12.         a=a*a;
    13.         b>>=1;
    14.     }
    15.     return res;
    16. }
    17. int main(){
    18.     fac[0]=1;
    19.     for(int i=1;i<=39;i++) fac[i]=fac[i-1]*3LL;
    20.     cin>>q;
    21.     while(q--){
    22.         cin>>n;
    23.         for(int i=0;i<=40;i++) vis[i]=0;
    24.         ll sup=upper_bound(fac,fac+39,n)-fac;
    25.         ll x=sup-1,y=n;
    26.         while(y){
    27.             while(x>=0&&y
    28.             if(x<0) break;
    29.             vis[x]=y/fac[x];
    30.             y%=fac[x];
    31.         }
    32.         ll zero;
    33.         for(int i=sup;i>=0;i--){
    34.             //cout<
    35.             if(vis[i]==0) zero=i;
    36.             if(vis[i]>1){
    37.                     vis[zero]=1;
    38.                     for(int j=zero-1;j>=0;j--) vis[j]=0;
    39.                     break;
    40.             }
    41.         }
    42.             ll ans=0;
    43.             for(int i=0;i<=sup;i++) 
    44.                 if(vis[i]) ans+=fac[i];
    45.             printf("%lld\n",ans);
    46.     }
    47.     system("pause");
    48.     return 0;
    49. }

    1458A - Row GCD gcd的性质

    gcd的一条性质关于辗转相除法的：gcd(a,b)=gcd(a,b-a),gcd(a,b,c)=gcd(a,b-a,c-b);

    所以该题gcd(a[1]+b[j],a[2]+b[j],a[3]+b[j])=gcd(a[1]+b[j],a[2]-a[1],a[3]-a[2]);

    1459C. Row GCD（经典数论）_a碟的博客-CSDN博客

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll n,m,a[200005],b[200005];
    8. int main(){
    9.     cin>>n>>m;
    10.     ll q=0;
    11.     for(int i=1;i<=n;i++){
    12.         cin>>a[i];
    13.     }
    14.     q=a[2]-a[1];
    15.     for(int i=3;i<=n;i++) q=__gcd(q,abs(a[i]-a[i-1]));
    16.     for(int i=1;i<=m;i++){
    17.         cin>>b[i];
    18.         if(n==1){
    19.             printf("%lld\n",a[1]+b[i]);continue;
    20.         }
    21.         printf("%lld ",__gcd(a[1]+b[i],q));
    22.     }
    23.     system("pause");
    24.     return 0;
    25. }

    C-公因子_牛客练习赛66 (nowcoder.com)gcd的性质

    也上一题类似，用的是一个性质，这次只要关注a[1]的取值就行了，但貌似只有排完序求得x的最小值是正确的

    Row GCD(差分+辗转相减法)_一个石马农的博客-CSDN博客

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll n,a[1000006];
    8. int main(){
    9.     cin>>n;
    10.     for(int i=1;i<=n;i++) cin>>a[i];
    11.     sort(a+1,a+n+1);
    12.     ll g=abs(a[2]-a[1]);
    13.     for(int i=3;i<=n;i++) g=__gcd(g,abs(a[i]-a[i-1]));
    14.     if(a[1]>=0) printf("%lld %lld\n",g,g-a[1]%g);
    15.     else printf("%lld %lld\n",g,abs(a[1])%g);
    16.     system("pause");
    17.     return 0;
    18. }

    4302 Interval GCD (zzstep.com)线段树，树状数组，gcd的性质

    也是用到了上面的那条性质，线段树维护a数组的差分数组的gcd，这样每次修改一个区间[x,y]只需要修改x,和y+1就行，树状数组维护差分数组的前缀和方便求答案

    Interval GCD（线段树区间增加、区间查询）_sunday_soft的博客-CSDN博客

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll n,m,a[500005],b[500005],t[500005<<2],ta[5000005];
    8. void pushup(ll p){t[p]=__gcd(t[p<<1],t[p<<1|1]);}
    9. void build(ll l,ll r,ll p){
    10.     if(l==r){t[p]=b[l];return;}
    11.     ll mid=l+r>>1;
    12.     build(l,mid,p<<1);
    13.     build(mid+1,r,p<<1|1);
    14.     pushup(p);
    15. }
    16. void update(ll l,ll r,ll x,ll y,ll p){
    17.     if(l==r){t[p]+=y;return;}
    18.     ll mid=l+r>>1;
    19.     if(x<=mid) update(l,mid,x,y,p<<1);
    20.     else update(mid+1,r,x,y,p<<1|1);
    21.     pushup(p);
    22. }
    23. ll query(ll l,ll r,ll L,ll R,ll p){
    24.     if(L<=l&&r<=R) return abs(t[p]);
    25.     ll mid=l+r>>1;
    26.     ll val=0;
    27.     if(L<=mid) val=__gcd(val,query(l,mid,L,R,p<<1));
    28.     if(R>mid) val=__gcd(val,query(mid+1,r,L,R,p<<1|1));
    29.     return abs(val);
    30. }
    31. void add(ll x,ll y){
    32.     for(int i=x;i<=n;i+=lowbit(i)) 
    33.         ta[i]+=y;
    34. }
    35. ll ask(ll x){
    36.     ll res=0;
    37.     for(int i=x;i;i-=lowbit(i))
    38.         res+=ta[i];
    39.     return res;
    40. }
    41. int main(){
    42.     scanf("%lld%lld",&n,&m);
    43.     for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i]-a[i-1];
    44.     build(1,n,1);
    45.     while(m--){
    46.         char op;
    47.         ll x,y,z;;
    48.         cin>>op;
    49.         if(op=='Q'){
    50.             scanf("%lld%lld",&x,&y);
    51.             ll val=a[x]+ask(x);
    52.             printf("%lld\n",__gcd(val,query(1,n,x+1,y,1)));
    53.         }
    54.         else{
    55.             scanf("%lld%lld%lld",&x,&y,&z);
    56.             update(1,n,x,z,1),add(x,z);
    57.             if(yupdate(1,n,y+1,-z,1),add(y+1,-z);
    58.         }
    59.     }
    60.     system("pause");
    61.     return 0;
    62. }

    1444A - Division

    p不整除q直接输出p，否则枚举q的质因子，p一直除这个质因子知道p不能整除q，更新最大值

    Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)——C. Division_cll7777777的博客-CSDN博客

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll q,p,t,cnt;
    8. ll pri[1000006],a[1000006],vis[1000006];
    9. bool ispri[1000006];
    10. void prime(ll n){
    11.     memset(ispri,1,sizeof(ispri));
    12.     ispri[0]=ispri[1]=0;
    13.     for(ll i=2;i<=n;i++){
    14.         if(ispri[i]) pri[++cnt]=i;
    15.         for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
    16.             ispri[i*pri[j]]=0;
    17.             if(i%pri[j]==0) break;
    18.         }
    19.     }
    20. }
    21. int main(){
    22.     prime(1000000);
    23.     scanf("%lld",&t);
    24.     while(t--){
    25.         scanf("%lld%lld",&p,&q);
    26.         ll y=q,ct=0;
    27.         if(p%q){printf("%lld\n",p);continue;}
    28.         for(int i=1;i<=cnt;i++){
    29.             if(q%pri[i]==0){
    30.                 a[++ct]=pri[i];
    31.                 while(q%pri[i]==0) q/=pri[i];
    32.             }
    33.         }
    34.         if(q>1) a[++ct]=q;
    35.         ll x=p,ans=0;
    36.         for(int i=1;i<=ct;i++){
    37.             x=p;
    38.             while(x%y==0&&x%a[i]==0) x/=a[i];
    39.             ans=max(x,ans);
    40.         }
    41.         printf("%lld\n",ans);
    42.     }
    43.     system("pause");
    44.     return 0;
    45. }

    1551C - Interesting Story

    一共就5个字母，枚举一下如果当前字母的个数大于其他所有个数最多可以用几个单词，枚举的时候如果是当前字母就加1，不是就减1，最后看看能加几个单词

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll t,n,a[200005];
    8. string s[200005];
    9. int main(){
    10.     scanf("%lld",&t);
    11.     while(t--){
    12.         scanf("%lld",&n);
    13.         ll ans=0;
    14.         for(int i=1;i<=n;i++) cin>>s[i];
    15.         for(char c='a';c<='e';c++){
    16.             for(int i=1;i<=n;i++) a[i]=0;
    17.             for(int i=1;i<=n;i++)
    18.             for(int j=0;jsize();j++) 
    19.                 if(s[i][j]==c) a[i]++;
    20.                 else a[i]--;
    21.             sort(a+1,a+n+1);
    22.             ll res=0,sum=0;
    23.             for(int i=n;i>=1;i--){
    24.                 sum+=a[i];
    25.                 if(sum<=0) break;
    26.                 res++;
    27.             }
    28.             ans=max(ans,res);
    29.         }
    30.         printf("%lld\n",ans);
    31.     }
    32.     system("pause");
    33.     return 0;
    34. }

    A-Game_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）（热身赛） 期望

    期望的线性性，E(x+y)=E(x)+E(y), 如果每次都是互质的话只需要抽n/2次就够了，只抽一次的话是1/C(n,2),预处理出符合条件的对数cnt，答案就是cnt/C(n,2)*n/2,注意n的奇偶需要判断一下，奇数的话是（n-1)/2次，虽然说计算机的出发两者其实是一样的，但是放到期望里面好像就不一样了

    北化ACM集训队-浅谈期望题的做法_哔哩哔哩_bilibili

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll n;
    8. int main(){
    9.     ll cnt=0;
    10.     scanf("%lld",&n);
    11.     for(int i=1;i<=n;i++)
    12.     for(int j=i+1;j<=n;j++)
    13.     if(__gcd(i,j)==1) cnt++;
    14.     ll p=cnt,q=n-1;
    15.     if(n&1) q=n;
    16.     printf("%lld/%lld\n",p/__gcd(p,q),q/__gcd(p,q));
    17.     system("pause");
    18.     return 0;
    19. }

    570D - Tree Requests树上启发式合并

    和板子是一样的套路，看来启发式合并或许难的不是合并的过程，而是先要想出一个可以适合启发式合并的暴力思路，这个题就是没有想到暴力的思路，其实也就是统计每个深度的各个颜色的个数，然后离线判断每个询问，板子大致一样，也就是统计函数要根据题目来写

    题解 CF570D 【Tree Requests】 - 牛蛙丶丶 的幼儿园 - 洛谷博客

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll n,m,tot[500005][27];
    8. ll son[500005],siz[500005],dep[500005],fson,vis[500005];
    9. bool ans[500005];
    10. char s[500005];
    11. struct qq{
    12.     ll su,id;
    13. };
    14. vectorq[500005];
    15. ll head[1000006],cnt;
    16. struct Edge{
    17.     ll from,to,next;
    18. }edge[1000006];
    19. void  addedge(ll from, ll to){
    20.     edge[++cnt].from=from;
    21.     edge[cnt].to=to;
    22.     edge[cnt].next=head[from];
    23.     head[from]=cnt;
    24. }
    25. void dfs1(ll u,ll fa){
    26.     dep[u]=dep[fa]+1;siz[u]=1;
    27.     for(int i=head[u];i;i=edge[i].next){
    28.         ll j=edge[i].to;
    29.         if(j==fa) continue;
    30.         dfs1(j,u);
    31.         siz[u]+=siz[j];
    32.         if(siz[j]>siz[son[u]]) son[u]=j;
    33.     }
    34. }
    35. void cal(ll u,ll fa,ll val){
    36.     tot[dep[u]][s[u]-'a']+=val;
    37.     for(int i=head[u];i;i=edge[i].next){
    38.         ll j=edge[i].to;
    39.         //if(j!=fa&&j!=fson) cal(j,u,val);
    40.         if(j!=fa&&!vis[j]) cal(j,u,val);
    41.     }
    42. }
    43. bool check(ll u){
    44.     ll res=0;
    45.     for(int i=0;i<26;i++){
    46.         if(tot[u][i]&1) res++;
    47.         if(res>1) return 0;
    48.     }
    49.     return 1;
    50. }
    51. void dfs2(ll u,ll fa,ll keep){
    52.     for(int i=head[u];i;i=edge[i].next){
    53.         ll j=edge[i].to;
    54.         if(j!=fa&&j!=son[u]) dfs2(j,u,0);
    55.     }
    56.     if(son[u]) dfs2(son[u],u,1),vis[son[u]]=1;
    57.     cal(u,fa,1);vis[son[u]]=0;
    58.     for(int i=0;isize();i++) ans[q[u][i].id]=check(q[u][i].su);
    59.     if(!keep) cal(u,fa,-1);
    60. }
    61. int main(){
    62.     scanf("%lld%lld",&n,&m);
    63.     for(int i=2;i<=n;i++){
    64.         ll u;scanf("%lld",&u);
    65.         addedge(u,i);addedge(i,u);
    66.     }
    67.     scanf("%s",s+1);
    68.     dfs1(1,0);
    69.     for(int i=1;i<=m;i++){
    70.          ll a,b;
    71.         scanf("%lld%lld",&a,&b);
    72.         q[a].push_back({b,i});
    73.     }
    74.     dfs2(1,0,1);
    75.     for(int i=1;i<=m;i++) 
    76.         if(ans[i]) printf("Yes\n");
    77.         else printf("No\n");
    78.     system("pause");
    79.     return 0;
    80. }

    CF208E Blood Cousins -树上启发式合并

    新学了个倍增求k级祖先，下面的人讲的还可以，lg[i]就是log2(i)+1,应该就是表示i可以向上跳几次

    题解 P3379 【【模板】最近公共祖先（LCA）】 - MorsLin 的博客 - 洛谷博客

    找出k级祖先来然后去遍历这个祖先的子树，相同深度的个数减1就是答案，注意这是个森林，所以每个根就要进行dfs

    题解 CF208E 【Blood Cousins】 - 坡道旁的向日葵 - 洛谷博客

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const int mod=1e9+7;
    7. ll n,m,tot[500005];
    8. ll son[500005],siz[500005],dep[500005],fson;
    9. ll f[100005][30],lg[100005],ans[100005];
    10. struct qq{
    11.     ll su,id;
    12. };
    13. vectorq[500005];
    14. ll head[1000006],cnt;
    15. struct Edge{
    16.     ll from,to,next;
    17. }edge[1000006];
    18. void  addedge(ll from, ll to){
    19.     edge[++cnt].from=from;
    20.     edge[cnt].to=to;
    21.     edge[cnt].next=head[from];
    22.     head[from]=cnt;
    23. }
    24. ll kthparent(ll u,ll k){
    25.     for(int i=lg[dep[u]];i>=0;i--)
    26.         if(dep[u]-dep[f[u][i]]<=k) k-=dep[u]-dep[f[u][i]],u=f[u][i];
    27.     return u;
    28. }
    29. void dfs1(ll u,ll fa){
    30.     dep[u]=dep[fa]+1;siz[u]=1;
    31.     for(int i=1;i<=lg[dep[u]];i++)
    32.         f[u][i]=f[f[u][i-1]][i-1];
    33.     for(int i=head[u];i;i=edge[i].next){
    34.         ll j=edge[i].to;
    35.         if(j==fa) continue;
    36.         dfs1(j,u);
    37.         siz[u]+=siz[j];
    38.         if(siz[j]>siz[son[u]]) son[u]=j;
    39.     }
    40. }
    41. void cal(ll u,ll fa,ll val){
    42.     tot[dep[u]]+=val;
    43.     for(int i=head[u];i;i=edge[i].next){
    44.         ll j=edge[i].to;
    45.         //if(j!=fa&&j!=fson) cal(j,u,val);
    46.         if(j!=fa&&j!=fson) cal(j,u,val);
    47.     }
    48. }
    49. void dfs2(ll u,ll fa,ll keep){
    50.     for(int i=head[u];i;i=edge[i].next){
    51.         ll j=edge[i].to;
    52.         if(j!=fa&&j!=son[u]) dfs2(j,u,0);
    53.     }
    54.     if(son[u]) dfs2(son[u],u,1),fson=son[u];
    55.     cal(u,fa,1);fson=0;
    56.     for(int i=0;isize();i++) ans[q[u][i].id]=tot[dep[q[u][i].su]]-1;
    57.     if(!keep) cal(u,fa,-1);
    58. }
    59. int main(){
    60.     lg[0]=-1;
    61.     for(int i=1;i<=100000;i++) lg[i]=lg[i>>1]+1;
    62.     scanf("%lld",&n);
    63.     for(int i=1;i<=n;i++){
    64.         scanf("%lld",&f[i][0]);
    65.         if(f[i][0]) addedge(f[i][0],i),addedge(i,f[i][0]);
    66.     }
    67.     for(int i=1;i<=n;i++){
    68.         if(!f[i][0]) dfs1(i,0);
    69.     }
    70.     scanf("%lld",&m);
    71.     for(int i=1;i<=m;i++){
    72.         ll x,p;
    73.         scanf("%lld%lld",&x,&p);
    74.         q[kthparent(x,p)].push_back(qq{x,i});
    75.     }
    76.     for(int i=1;i<=n;i++){
    77.         if(!f[i][0]) dfs2(i,0,0);
    78.     }
    79.     for(int i=1;i<=m;i++) printf("%lld ",ans[i]);
    80.     system("pause");
    81.     return 0;
    82. }

  • 相关阅读:
    【AI大模型】驱动的未来：穿戴设备如何革新血液、皮肤检测与营养健康管理
    学习记忆——方法篇——联想法+记忆宫殿+数字编码
    Vue 中 v-if 和 v-show 有什么区别？
    批量PDF转HTML：高效管理与优化文档格式
    操作系统学习（八）进程同步与通信
    工业交换机常见的硬件故障有哪些？
    深度学习——Bounding Box预测
    web网页设计期末课程大作业：旅游网页主题网站设计——中国风的温泉酒店预订网(13页)HTML+CSS+JavaScript
    深入浅出Pytorch中的计算细节_input/output
    深入浅出学习透析Nginx服务器的基本原理和配置指南「负载均衡篇」
  • 原文地址：https://blog.csdn.net/weixin_52621204/article/details/126031640