• 22/6/24~6/25

    1，cf Palindromic Numbers；2,牛牛看云;3,中位数切分;4,cf Another Problem About Dividing Numbers;5,九小时九个人九扇门;

    1，cf Palindromic Numbers

    题意：给你一个长度为n的正整数，一定存在另一个长度也为n的数，使得他俩的和为回文数；求出另一个数；

    思路：看正整数开头的数字，在1~8就可以用长度为n的999....来当回文数，再减去给出的数字，就可得到长度为n的另一个数，如果开头数字是9，那么我选择的是长度为n+1的111....，用到了高精度除法；

    高精度除法复习：

    （A的长度>B的长度 ,每次存的是(t+10)%10,这样做的好处就是不用特判t<0是否需要借数等,直接在后面特判,t<0,说明需要借1,t=1,这样下一轮t=A[i]-t,就会少1,最后除去前导0的操作); 

    code:

    1. #pragma GCC optimize(2)
    2. #include<bits/stdc++.h>
    3. #define rep1(i,a,n) for( int i=a;i<n;++i) 
    4. #define rep2(i,a,n) for( int i=a;i<=n;++i) 
    5. #define per1(i,n,a) for( int i=n;i>a;i--) 
    6. #define per2(i,n,a) for( int i=n;i>=a;i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define pb push_back
    12. #define pf push_front
    13. #define endl "\n"
    14. #define lowbit(m) ((-m)&(m))
    15. #define YES cout<<"YES\n"
    16. #define NO cout<<"NO\n"
    17. #define Yes cout<<"Yes\n"
    18. #define No cout<<"No\n"
    19. #define yes cout<<"yes\n"
    20. #define no cout<<"no\n"
    21. #define yi first
    22. #define er second
    23. using namespace std;
    24. typedef pair<long long,long long>PLL;
    25. typedef long long LL;
    26. typedef pair<int,int> PII;
    27. typedef pair<int,PII> PIII;
    28. typedef double dob; 
    29. const int N=1e5+10;
    30. char a[N];
    31. vector<int> sub(vector<int>A,vector<int>B)
    32. {
    33.     vector<int>C;
    34.     int t=0;
    35.     int asiz=A.size();
    36.     int bsiz=B.size();
    37.     rep1(i,0,asiz)
    38.     {
    39.         t=A[i]-t;
    40.         if(i<bsiz)t-=B[i];
    41.         C.pb((t+10)%10);
    42.         if(t<0)t=1;
    43.         else t=0;
    44.     }
    45.     while(C.size()>1&&C.back()==0)C.pop_back();
    46.     return C;
    47. }
    48. void solve()
    49. {
    50.     int n;
    51.     cin>>n;
    52.     rep2(i,1,n)cin>>a[i];
    53.     if(a[1]=='9')
    54.     {
    55.         vector<int>A,B;
    56.         rep2(i,1,n+1)A.push_back(1);
    57.         per2(i,n,1)B.push_back(a[i]-'0');
    58.         auto C=sub(A,B);
    59.         int csiz=C.size();
    60.         per2(i,csiz-1,0)cout<<C[i];
    61.         cout<<endl;
    62.     }
    63.     else
    64.     {
    65.         vector<int>A,B;
    66.         rep2(i,1,n)A.pb(9);
    67.         per2(i,n,1)B.pb(a[i]-'0');
    68.         auto C=sub(A,B);
    69.         int csiz=C.size();
    70.         per2(i,csiz-1,0)cout<<C[i];
    71.         cout<<endl;
    72.     }
    73. }
    74. signed main()
    75. {
    76.     quick_cin();
    77.     int T;
    78.     cin>>T;
    79.     while(T--)solve();
    80.     return 0;
    81. }

     2,牛牛看云;

     思路:直接按公式做肯定是tle的,看序列的数据范围,只有1000,所以可以记录0~1000的每个数的出现次数,然后转换下求法即可;

    1. #pragma GCC optimize(2)
    2. #include<bits/stdc++.h>
    3. #define rep1(i,a,n) for( int i=a;i<n;++i) 
    4. #define rep2(i,a,n) for( int i=a;i<=n;++i) 
    5. #define per1(i,n,a) for( int i=n;i>a;i--) 
    6. #define per2(i,n,a) for( int i=n;i>=a;i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define pb push_back
    12. #define pf push_front
    13. #define endl "\n"
    14. #define lowbit(m) ((-m)&(m))
    15. #define YES cout<<"YES\n"
    16. #define NO cout<<"NO\n"
    17. #define Yes cout<<"Yes\n"
    18. #define No cout<<"No\n"
    19. #define yes cout<<"yes\n"
    20. #define no cout<<"no\n"
    21. #define yi first
    22. #define er second
    23. using namespace std;
    24. typedef pair<long long,long long>PLL;
    25. typedef long long LL;
    26. typedef pair<int,int> PII;
    27. typedef pair<int,PII> PIII;
    28. typedef double dob; 
    29. const int N=1e6+10;
    30. LL cs[N];
    31. LL ans;
    32. signed main()
    33. {
    34.     quick_cin();
    35.     int n;
    36.     cin>>n;
    37.     rep2(i,1,n)
    38.     {
    39.         int x;
    40.         cin>>x;
    41.         cs[x]++;
    42.     }
    43.     rep2(i,0,1000)
    44.     {
    45.         LL num=0;
    46.         rep2(j,i,1000)
    47.         {
    48.             if(j==i)num=((cs[i]+1)*cs[i])/2;
    49.             else num=cs[i]*cs[j];
    50.             ans+=num*abs(i+j-1000);
    51.         }
    52.     }
    53.     cout<<ans;
    54.     return 0;
    55. }

    3,中位数切分;

    数学题:

    结论:设cnt1为>=m的数的个数,cnt2为<m的个数,如果cnt1>cnt2,则ans=cnt1-cnt2;否则就是-1;

    证明:

    设f(l,r)为数组al到ar的cnt1-cnt2的值,很明显f(l,r)>1才是符合要求的区间;

    f(l,r)的性质:f(l,r)=f(l,mid)+f(mid+1,r);

    要找的就是存在一个位置mid,使得f(l,mid)>0&&f(mid+1,r)>0;

    看f(l,mid)=1的情况,此时f(l,r)>1,所以f (mid+1,r)=f(l,r)-f(l,mid)>0,所以此时就可以切;

    为了切最多的区间,肯定是f(l,r)=1;

    又因为整个在f(1,n)区间进行切割,所以总的和等于f(1,n)=cnt1-cnt2;

    code:

    1. #pragma GCC optimize(2)
    2. #include<bits/stdc++.h>
    3. #define rep1(i,a,n) for( int i=a;i<n;++i) 
    4. #define rep2(i,a,n) for( int i=a;i<=n;++i) 
    5. #define per1(i,n,a) for( int i=n;i>a;i--) 
    6. #define per2(i,n,a) for( int i=n;i>=a;i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define pb push_back
    12. #define pf push_front
    13. #define endl "\n"
    14. #define lowbit(m) ((-m)&(m))
    15. #define YES cout<<"YES\n"
    16. #define NO cout<<"NO\n"
    17. #define Yes cout<<"Yes\n"
    18. #define No cout<<"No\n"
    19. #define yes cout<<"yes\n"
    20. #define no cout<<"no\n"
    21. #define yi first
    22. #define er second
    23. using namespace std;
    24. typedef pair<long long,long long>PLL;
    25. typedef long long LL;
    26. typedef pair<int,int> PII;
    27. typedef pair<int,PII> PIII;
    28. typedef double dob; 
    29. const int N=1e6+10;
    30. int n,m;
    31. void solve()
    32. {
    33.     cin>>n>>m;
    34.     int cnt1=0,cnt2=0;
    35.     rep2(i,1,n)
    36.     {
    37.         int x;
    38.         cin>>x;
    39.         if(x>=m)cnt1++;
    40.         else cnt2++;
    41.     }
    42.     if(cnt1>cnt2)cout<<cnt1-cnt2<<endl;
    43.     else cout<<-1<<endl;
    44. }
    45. signed main()
    46. {
    47.     quick_cin();
    48.     int T;
    49.     cin>>T;
    50.     while (T--)
    51.     {
    52.         solve();
    53.     }
    54.     return 0;
    55. }

    4, cf Another Problem About Dividing Numbers

    题意:

    思路:求出来最小操作次数和最多操作次数即可;对于a=b&&k=1的情况进行特判;

    最小操作次数:

    a=b,0;

    a!=b,a!=gcd(a,b)&&b!=gcd(a,b)时为2,否则为1;

    最大操作次数:

    a与b的质因数个数之和;

    1. #pragma GCC optimize(2)
    2. #include<bits/stdc++.h>
    3. #define rep1(i,a,n) for( int i=a;i<n;++i) 
    4. #define rep2(i,a,n) for( int i=a;i<=n;++i) 
    5. #define per1(i,n,a) for( int i=n;i>a;i--) 
    6. #define per2(i,n,a) for( int i=n;i>=a;i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define pb push_back
    12. #define pf push_front
    13. #define endl "\n"
    14. #define lowbit(m) ((-m)&(m))
    15. #define YES cout<<"YES\n"
    16. #define NO cout<<"NO\n"
    17. #define Yes cout<<"Yes\n"
    18. #define No cout<<"No\n"
    19. #define yes cout<<"yes\n"
    20. #define no cout<<"no\n"
    21. #define yi first
    22. #define er second
    23. using namespace std;
    24. typedef pair<long long,long long>PLL;
    25. typedef long long LL;
    26. typedef pair<int,int> PII;
    27. typedef pair<int,PII> PIII;
    28. typedef double dob; 
    29. const int N=1e6+10;
    30. int a,b,k;
    31. inline int gcd(int a,int b)
    32. {
    33.     if(b)while((a%=b)&&(b%=a));
    34.     return a+b;
    35. }
    36. int zhi(int num)
    37. {
    38.     int ans=0;
    39.     for(int i=2;i*i<=num;i++)
    40.     {
    41.         while(num%i==0)
    42.         {
    43.             num/=i;
    44.             ans++;
    45.         }
    46.     }
    47.     if(num!=1)ans++;
    48.     return ans;
    49. }
    50. int xiao(int a,int b)
    51. {
    52.     int ans=0;
    53.     int num=gcd(a,b);
    54.     if(a!=num)ans++;
    55.     if(b!=num)ans++;
    56.     return ans;
    57. }
    58. int da(int a,int b)
    59. {
    60.     return zhi(a)+zhi(b);
    61. }
    62. void solve()
    63. {
    64.     cin>>a>>b>>k;
    65.     if(xiao(a,b)<=k&&k<=da(a,b)&&(a!=b||k!=1))YES;
    66.     else NO;
    67. }
    68. signed main()
    69. {
    70.     quick_cin();
    71.     int T;
    72.     cin>>T;
    73.     while (T--)
    74.     {
    75.         solve();
    76.     }
    77.     return 0;
    78. }

     5,九小时九个人九扇门

    题意:

     数字根的结论:一个数的数字根是它%9的结果;

    一个四位数abcd%9=(a*1000+b*100+c*10+d)%9=(a+b+c+d)%9;

    问题转化为: 从a数组中选择一些数字，使得其求和对9取模为0，1，2，3，4，5，6，7，8有多少种选法

    最后记得-1,不能一个也不选;

    1. #pragma GCC optimize(2)
    2. #include<bits/stdc++.h>
    3. #define rep1(i,a,n) for( int i=a;i<n;++i) 
    4. #define rep2(i,a,n) for( int i=a;i<=n;++i) 
    5. #define per1(i,n,a) for( int i=n;i>a;i--) 
    6. #define per2(i,n,a) for( int i=n;i>=a;i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define pro_q priority_queue
    11. #define pb push_back
    12. #define pf push_front
    13. #define endl "\n"
    14. #define lowbit(m) ((-m)&(m))
    15. #define YES cout<<"YES\n"
    16. #define NO cout<<"NO\n"
    17. #define Yes cout<<"Yes\n"
    18. #define No cout<<"No\n"
    19. #define yes cout<<"yes\n"
    20. #define no cout<<"no\n"
    21. #define yi first
    22. #define er second
    23. using namespace std;
    24. typedef pair<long long,long long>PLL;
    25. typedef long long LL;
    26. typedef pair<int,int> PII;
    27. typedef pair<int,PII> PIII;
    28. typedef double dob; 
    29. const int N=1e6+10;
    30. LL f[N][9];
    31. const int mod=998244353;
    32. signed main()
    33. {
    34.     quick_cin();
    35.     int n;
    36.     cin>>n;
    37.     f[0][0]=1;
    38.     rep2(i,1,n)
    39.     {
    40.         int x;
    41.         cin>>x;
    42.         rep1(j,0,9)
    43.         {
    44.             f[i][(j+x)%9]=(f[i][(j+x)%9]+f[i-1][j])%mod;
    45.             f[i][j]=(f[i][j]+f[i-1][j])%mod;
    46.         }
    47.     }
    48.     rep2(i,1,8)cout<<f[n][i]<<" ";
    49.     cout<<f[n][0]-1;
    50.     return 0;
    51. }

  • 相关阅读:
    Excel导入和导出
    Java的五大引用
    Hashmap 原理、源码、面试题（史上最全）
    列表、字典、元组、集合总结
    【JS】阿拉伯数字转成中文数字（包括亿单位长数字）
    【 SuperPoint 】图像特征提取上的对比实验
    Linux高级IO
    计算机考研408难吗？学到什么程度才能考130?
    网络安全之命令执行漏洞复现
    21-SpringSecurity
  • 原文地址：https://blog.csdn.net/aidaqiudeaichao/article/details/125446397