devbox
爱喝兽奶帝天荒
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2023“钉耙编程”中国大学生算法设计超级联赛（4）_j - kong ming qi

作者：爱喝兽奶帝天荒 | 2024-08-20 12:02:00

赞

踩

j - kong ming qi

Simple Set Problem 尺取，双指针，排序

Data Generation 概率，矩阵快速幂

PSO 期望，签到

Guess  推式子，Pollard-Rho筛素数获得全部因子

Kong Ming Qi 构造

Circuit 最短路计数，弗洛伊德

a-b Problem 贪心，签到

 

 

 首先将全部数字加入集合，数字记录所属集合，从小到大移动左指针，而后右指针在原来基础上向右扩展至第一个满足的即可。取一个最小值

 

  1. # include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. struct node
  5. {
  6.     int val,id;
  7. };
  8. struct node s[1000000+10];
  9. int cnt[1000000+10];
  10. bool cmp(struct node &x,struct node&y)
  11. {
  12.     return x.val<y.val;
  13. }
  14. int main()
  15. {
  16.     cin.tie(0);
  17.     ios::sync_with_stdio(0);
  18.     int t;
  19.     cin>>t;
  20.     while(t--)
  21.     {
  22.         int n;
  23.         cin>>n;
  24.         for(int i=1;i<=n;i++)
  25.         {
  26.             cnt[i]=0;
  27.         }
  28.         int len=0;
  29.         for(int i=1;i<=n;i++)
  30.         {
  31.             int x;
  32.             cin>>x;
  33.             for(int j=1;j<=x;j++)
  34.             {
  35.                 len++;
  36.                 cin>>s[len].val;
  37.                 s[len].id=i;
  38.             }
  39.         }
  40.         sort(s+1,s+1+len,cmp);
  41.         int ans=2e9+10;
  42.         int pos=0,nowcnt=0;
  43.         for(int i=1;i<=len;i++)
  44.         {
  45.             if(i>=2)
  46.             {
  47.                 cnt[s[i-1].id]--;
  48.                 if(cnt[s[i-1].id]==0)
  49.                         nowcnt--;
  50.             }
  51.             while(pos<=len&&nowcnt<n)
  52.             {
  53.                 pos++;
  54.                 cnt[s[pos].id]++;
  55.                 if(cnt[s[pos].id]==1)
  56.                     nowcnt++;
  57.             }
  58.  
  59.             if(nowcnt==n&&pos<=len)
  60.             {
  61.                 ans=min(ans,s[pos].val-s[i].val);
  62.             }
  63.         }
  64.         cout<<ans<<'\n';
  65.     }
  66.    return 0;
  67. }

 

最终答案就是由于每个位置匹配成功的贡献是1，所以最终答案就是n-每个匹配成功的期望。

而每个位置还是相互独立的，所以可以看成n*p[0] 其中p[0]是m次交换之后次成功的期望。

当第i-1次0在自己的位置上时，p[i-1] * ( 1 + (n-1)^2 ) / ( n^2 )，即n^2种交换，只有[0,0]交换，和没有0的交换才能保证0仍然在原位置不懂。

当第i-1次0不在自己的位置上时，( 1-p[i-1] ) * ( 2/(n^2) )

二者综合，可以得出p[i]=(n-2)/n * p[i-1] + 2 / (n^2)

可以用矩阵快速幂解决，但n,m的范围很大，注意对n取模，防止相乘直接爆ll

 

 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. # define mod  998244353
  5. ll base[2][2],res[2][2];
  6. void mulans()
  7. {
  8.     ll temp[2][2];
  9.     for(int i=0;i<2;i++)
  10.     {
  11.         for(int j=0;j<2;j++)
  12.         {
  13.             temp[i][j]=0;
  14.         }
  15.     }
  16.     for(int k=0;k<2;k++)
  17.     {
  18.         for(int i=0;i<2;i++)
  19.         {
  20.             for(int j=0;j<2;j++)
  21.             {
  22.                 temp[i][j]=(temp[i][j]+res[i][k]*base[k][j]%mod)%mod;
  23.             }
  24.         }
  25.     }
  26.     for(int i=0;i<2;i++)
  27.     {
  28.         for(int j=0;j<2;j++)
  29.         {
  30.             res[i][j]=temp[i][j];
  31.         }
  32.     }
  33.     return ;
  34. }
  35. void mulbase()
  36. {
  37.     ll temp[2][2];
  38.     for(int i=0;i<2;i++)
  39.     {
  40.         for(int j=0;j<2;j++)
  41.         {
  42.             temp[i][j]=0;
  43.         }
  44.     }
  45.     for(int k=0;k<2;k++)
  46.     {
  47.         for(int i=0;i<2;i++)
  48.         {
  49.             for(int j=0;j<2;j++)
  50.             {
  51.                 temp[i][j]=(temp[i][j]+base[i][k]*base[k][j]%mod)%mod;
  52.             }
  53.         }
  54.     }
  55.     for(int i=0;i<2;i++)
  56.     {
  57.         for(int j=0;j<2;j++)
  58.         {
  59.             base[i][j]=temp[i][j];
  60.         }
  61.     }
  62.     return ;
  63. }
  64. void qp(ll pow)
  65. {
  66.     for(int i=0;i<2;i++)
  67.     {
  68.         for(int j=0;j<2;j++)
  69.         {
  70.             res[i][j]=0;
  71.             res[i][i]=1;
  72.         }
  73.     }
  74.     while(pow)
  75.     {
  76.         if(pow&1)
  77.             mulans();
  78.         pow>>=1;
  79.         mulbase();
  80.     }
  81. }
  82. ll qsm(ll bas,ll pow)
  83. {
  84.     ll ans=1;
  85.     bas%=mod;
  86.     while(pow)
  87.     {
  88.         if(pow&1)
  89.             ans=ans*bas%mod;
  90.         pow>>=1;
  91.         bas=bas*bas%mod;
  92.     }
  93.     return ans;
  94. }
  95. int main()
  96. {
  97.  
  98.     int t;
  99.     cin>>t;
  100.     while(t--)
  101.     {
  102.         ll n,m;
  103.         scanf("%lld%lld",&n,&m);
  104.         n%=mod;
  105.         for(int i=0;i<2;i++)
  106.         {
  107.             for(int j=0;j<2;j++)
  108.             {
  109.                 base[i][j]=0;
  110.             }
  111.         }
  112.         ll now=((n-2)%mod+mod)%mod*qsm(n,mod-2)%mod;
  113.         ll noww=2ll*qsm(n*n%mod,mod-2)%mod;
  114.         base[0][0]=now;
  115.         base[0][1]=base[1][1]=1;
  116.         qp(m);
  117.         ll ans=(res[0][0]+res[0][1]*noww%mod)%mod;
  118.         ans*=n;
  119.         ans%=mod;
  120.         cout<<((n-ans)%mod+mod)%mod<<'\n';
  121.     }
  122.     return 0;
  123. }

 

 

 其实可以暴力打出前几十个数字的表，发现，只有当n时质数或者n是一个质数的幂的时候，s[n]才不是0

然后利用PR求解即可。

  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=(a);i<=(b);i++)
  3. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  4. typedef long long ll;
  5. using namespace std;
  6. const int MOD=998244353;
  7. ll ksm(ll a,ll b,ll p){
  8.     ll ret=1;
  9.     for(;b;b>>=1,a=(__int128)a*a%p)
  10.         if(b&1)ret=(__int128)ret*a%p;
  11.     return ret;
  12. }
  13. bool Miller_Rabin(ll p){
  14.     if(p<2)return 0;
  15.     if(p==2||p==3)return 1;
  16.     ll d=p-1,r=0;
  17.     while(!(d&1))++r,d>>=1;
  18.     for(ll k=0;k<10;++k){
  19.         ll a=rand()%(p-2)+2;
  20.         ll x=ksm(a,d,p);
  21.         if(x==1||x==p-1)continue;
  22.         for(int i=0;i<r-1;++i){
  23.             x=(__int128)x*x%p;
  24.             if(x==p-1)break;
  25.         }
  26.         if(x!=p-1)return 0;
  27.     }
  28.     return 1;
  29. }
  30. int tot;
  31. ll decom[100];
  32. ll Pollard_Rho(ll x){
  33.     ll s=0,t=0;
  34.     ll c=(ll)rand()%(x-1)+1;
  35.     int step=0,goal=1;
  36.     ll val=1;
  37.     for(goal=1;;goal<<=1,s=t,val=1){
  38.         for(step=1;step<=goal;step++){
  39.             t=((__int128)t*t+c)%x;
  40.             val=(__int128)val*abs(t-s)%x;
  41.             if(step%127==0){
  42.                 ll d=__gcd(val,x);
  43.                 if(d>1)return d;
  44.             }
  45.         }
  46.         ll d=__gcd(val,x);
  47.         if(d>1)return d;
  48.     }
  49. }
  50. void solve(ll x){
  51.     if(x<2)return;
  52.     if(Miller_Rabin(x)){
  53.         decom[++tot]=x;
  54.         return;
  55.     }
  56.     ll p=x;
  57.     while(p==x)p=Pollard_Rho(x);
  58.     solve(x/p);solve(p);
  59. }
  60. # define mod 998244353
  61. int main(){
  62.     fastio;
  63.     srand(time(0));
  64.     int T;cin>>T;
  65.     while(T--){
  66.         tot=0;
  67.         ll n;cin>>n;
  68.         assert(1<=n&&n<=(ll)(1e18));
  69.         solve(n);
  70.         sort(decom+1,decom+tot+1);
  71.         tot=unique(decom+1,decom+tot+1)-(decom+1);
  72.  
  73.         if(tot==1)
  74.         {
  75.             cout<<decom[1]%mod<<" ";
  76.         }
  77.         else
  78.         {
  79.             cout<<1<<" ";
  80.         }
  81.     }
  82.     return 0;
  83. }

 

 

 

 

首先有一个构造方案，图中黑点可以消去白点三个，而自己保持不变。根据这一构造，在n>=3的时候，如果m>=3，可以先利用左侧消去将m消三列，留下最后三行的后三列没被消去，利用右侧方案，消去。最终会变成一个n<=3,m<=3的情况

首先n=1||m=1的时候，是对应行列个数除以2向上取整。

n<=3m<=3的时候可以打表出来

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. int nx[4]={0,0,-1,1};
  5. int ny[4]={1,-1,0,0};
  6. int a[10][10],n,m;
  7. bool check(int x,int y)
  8. {
  9.     return x>=0&&x<=n+1&&y>=0&&y<=m+1;
  10. }
  11. int ans=1e9;
  12. int all;
  13. void work()
  14. {
  15.     int flag=0;
  16.  
  17.     if(ans==1)
  18.         return ;
  19.     for(int i=0;i<=n+1;i++)
  20.     {
  21.         for(int j=0;j<=m+1;j++)
  22.         {
  23.             if(a[i][j])
  24.             {
  25.                 for(int k=0;k<4;k++)
  26.                 {
  27.                     int xx=i+nx[k];
  28.                     int yy=j+ny[k];
  29.                     if(check(xx,yy)&&a[xx][yy])
  30.                     {
  31.                         int xxx=xx+nx[k];
  32.                         int yyy=yy+ny[k];
  33.                         if(check(xxx,yyy)&&!a[xxx][yyy])
  34.                         {
  35.                             a[i][j]=0;
  36.                             a[xx][yy]=0;
  37.                             a[xxx][yyy]=1;
  38.                             work();
  39.                             a[i][j]=1;
  40.                             a[xx][yy]=1;
  41.                             a[xxx][yyy]=0;
  42.                             flag=1;
  43.                         }
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.     }
  49.  
  50.     if(flag==0)
  51.     {
  52.         int nowcnt=0;
  53.         for(int i=0;i<=n+1;i++)
  54.         {
  55.             for(int j=0;j<=m+1;j++)
  56.             {
  57.                 nowcnt+=(a[i][j]);
  58.             }
  59.         }
  60.  
  61.         if(nowcnt<ans)
  62.         {
  63.             //cout<<nowcnt<<'\n';
  64.             ans=nowcnt;
  65.         }
  66.     }
  67. }
  68. int pre[10][10];
  69. int main()
  70. {
  71.  
  72.     pre[1][1]=1;
  73.     pre[1][2]=1;
  74.     pre[1][3]=2;
  75.     pre[1][4]=2;
  76.     pre[2][1]=1;
  77.     pre[3][1]=2;
  78.     pre[4][1]=2;
  79.     pre[2][2]=1;
  80.     pre[2][3]=2;
  81.     pre[2][4]=1;
  82.     pre[3][2]=2;
  83.     pre[3][3]=2;
  84.     pre[3][4]=2;
  85.     pre[4][2]=1;
  86.     pre[4][3]=2;
  87.     pre[4][4]=1;
  88.     int t;
  89.     cin>>t;
  90.     while(t--)
  91.     {
  92.         int x,y;
  93.         scanf("%d%d",&x,&y);
  94.         if(x>y)
  95.             swap(x,y);
  96.         if(x==1)
  97.         {
  98.             cout<<(y+1)/2<<'\n';
  99.  
  100.         }
  101.         else
  102.         {
  103.             if(x<=4&&y<=4)
  104.             {
  105.                 cout<<pre[x][y]<<'\n';
  106.             }
  107.             else
  108.             {
  109.                 x%=3;
  110.                 y%=3;
  111.                 if(x<=0)
  112.                     x+=3;
  113.                 if(y<=0)
  114.                     y+=3;
  115.                 cout<<pre[x][y]<<'\n';
  116.             }
  117.         }
  118.     }
  119.  
  120.  
  121.  
  122.     return 0;
  123. }

 

 

有向图计环，在弗洛伊德的时候，转移点k从1枚举到n。考虑对每个环，记录包含[1,1],[1,2],[1,3]...[1,n]的全部环，对于一个包含[1,k]的环，要想不重复的记录，需要以k为起点，这样，包含[1,2]的以2为起点的环，和包含[1,3]以3为起点的环。一定不会重复。又比如，[1,7]的环中，有[4,6],[1,3]。。各种，而[4,6]的环，在[1,6]的时候，已经被以6为起点的记录。 

 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. ll dis[510][510],cnt[510][510],inf=1e15,edge[510][510];
  5. # define mod 998244353
  6. int main()
  7. {
  8.     cin.tie(0);
  9.     ios::sync_with_stdio(0);
  10.     int t;
  11.     cin>>t;
  12.     while(t--)
  13.     {
  14.         int n,m;
  15.         cin>>n>>m;
  16.         for(int i=1; i<=n; i++)
  17.         {
  18.             for(int j=1; j<=n; j++)
  19.             {
  20.                 dis[i][j]=inf;
  21.                 dis[i][i]=0;
  22.                 cnt[i][j]=0;
  23.                 edge[i][j]=0;
  24.             }
  25.         }
  26.         while(m--)
  27.         {
  28.             int x,y;
  29.             ll val;
  30.             cin>>x>>y>>val;
  31.             dis[x][y]=min(dis[x][y],val);
  32.             edge[x][y]=val;
  33.             cnt[x][y]=1;
  34.         }
  35.         ll minn=1e18,ans=0;
  36.         for(int k=1; k<=n; k++)
  37.         {
  38.             for(int i=1; i<=n; i++)
  39.             {
  40.                 for(int j=1; j<=n; j++)
  41.                 {
  42.                     if(dis[i][j]==dis[i][k]+dis[k][j])
  43.                     {
  44.                         cnt[i][j]=(cnt[i][j]+cnt[i][k]*cnt[k][j]%mod)%mod;
  45.                     }
  46.                     else if(dis[i][j]>dis[i][k]+dis[k][j])
  47.                     {
  48.                         dis[i][j]=dis[i][k]+dis[k][j];
  49.                         cnt[i][j]=cnt[i][k]*cnt[k][j]%mod;
  50.                     }
  51.  
  52.                 }
  53.             }
  54.             for(int i=1; i<k; i++)
  55.             {
  56.                 if(edge[k][i])
  57.                 {
  58.                     if(edge[k][i]+dis[i][k]<minn)
  59.                     {
  60.                         minn=edge[k][i]+dis[i][k];
  61.                         ans=cnt[i][k];
  62.                     }
  63.                     else if(edge[k][i]+dis[i][k]==minn)
  64.                     {
  65.                         ans+=cnt[i][k];
  66.                         ans%=mod;
  67.                     }
  68.                 }
  69.             }
  70.         }
  71.         if(minn>=inf)
  72.         {
  73.             cout<<-1<<" "<<-1<<'\n';
  74.             continue;
  75.         }
  76.         cout<<minn<<" "<<ans<<'\n';
  77.     }
  78.  
  79.     return 0;
  80. }

 

 

按照A+B排序的原理是，A+B如果大，要么可以让自己加的分多，要么可以避免对面加更多的分。

  1. # include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. struct node
  5. {
  6.     int a,b,c;
  7. };
  8. struct node s[100000+10];
  9. bool cmp(struct node &x, struct node &y)
  10. {
  11.     return x.c>y.c;
  12. }
  13. int main()
  14. {
  15.      cin.tie(0);
  16.      ios::sync_with_stdio(0);
  17.      int t;
  18.      cin>>t;
  19.      while(t--)
  20.      {
  21.          int n;
  22.          cin>>n;
  23.          for(int i=1;i<=n;i++)
  24.          {
  25.              cin>>s[i].a>>s[i].b;
  26.              s[i].c=s[i].a+s[i].b;
  27.          }
  28.          sort(s+1,s+1+n,cmp);
  29.          ll sum1=0,sum2=0;
  30.          for(int i=1;i<=n;i++)
  31.          {
  32.              if(i%2)
  33.              {
  34.                  sum1+=s[i].a;
  35.              }
  36.              else
  37.              {
  38.                  sum2+=s[i].b;
  39.              }
  40.          }
  41.  
  42.          cout<<sum1-sum2<<'\n';
  43.      }
  44.  
  45.    return 0;
  46. }

 

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号