• “蔚来杯“2022牛客暑期多校训练营4

    目录

    N.Particle Arts(签到)

    K.NIO's Sword(枚举)

    D.Jobs (Easy Version)(前缀和)

    H.Wall Builder II

    A.Task Computing

    (翻译来自牛客多校群题解,我写题解是记录一下思路qwq)

    N.Particle Arts(签到)

    思路:算是个阅读题吧,直接把1尽量往前放即可.

    1. #include
    2. #define int __int128
    3. using namespace std;
    4. const int N =5e5+10,mod=998244353;
    5. int a[100005];
    6. int cnt[16];
    7. inline __int128 scan()
    8. {
    9.     __int128 x=0,f=1;
    10.     char ch=getchar();
    11.     while(ch<'0'||ch>'9'){
    12.         if(ch=='-')
    13.             f=-1;
    14.         ch=getchar();
    15.     }
    16.     while(ch>='0'&&ch<='9'){
    17.          x=x*10+ch-'0';
    18.          ch=getchar();
    19.     }
    20.     return x*f;
    21. }
    22. void print(__int128 x)
    23. {
    24.     if(x < 0)
    25.     {
    26.         x = -x;
    27.         putchar('-');
    28.     }
    29.     if(x > 9) print(x/10);
    30.     putchar(x%10 + '0');
    31. }
    32. void solve()
    33. {
    34.     int n,x,sum=0;
    35.     n = scan();
    36. 	
    37.     for(int i=1;i<=n;i++)
    38.     {
    39.         int tot=0;
    40.        	x = scan(); 
    41.         sum+=x;
    42.         while(x)
    43.         {
    44.             cnt[tot++]+=x%2;
    45.             x/=2;
    46.         }
    47.     }
    48.     for(int i=1;i<=n;i++)
    49.     {
    50.         for(int j=0;j<15;j++)
    51.         {
    52.             if(cnt[j])
    53.             {
    54.                 a[i]+=(1<
    55.                 cnt[j]--;
    56.             }
    57.         }
    58.     }
    59.     int zi=0,mu=n*n*n;
    60.     for(int i=1;i<=n;i++)
    61.     {
    62.         zi+=a[i]*a[i]*n*n+sum*sum-2*n*a[i]*sum;
    63.     }
    64.     int ggcd=__gcd(mu,zi);
    65. 	print(zi / ggcd);
    66. 	printf("/");
    67. 	print(mu/ggcd);
    68.     // cout<
    69.     return ;
    70. }
    71. signed main()
    72. {
    73.     cin.tie(0);
    74.     cout.tie(0);
    75.     ios::sync_with_stdio(0);
    76.     solve();
    77.     return 0;
    78. }

    K.NIO's Sword(枚举)

    可以由公式

    A_{i-1}*10^{ki}+x_{i}=A_{i} (0<=x_{i}<=10^{ki})

    推导出下面式子

    i-1*10^{ki}+x_{i}\equiv i (mod n)

    那就可以直接针对每个i去枚举ki(从0开始枚举),求最小值xi,当满足条件时直接将ki加到记录到结果里即可.

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N =5e5+10,mod=998244353;
    5. int pow10[20];
    6. int n;
    7. bool check(int i,int len)
    8. {
    9.     int res=i*pow10[len]%n;
    10.     res=((i+1)-res+n)%n;
    11.     if(res
    12.         return true;
    13.     else
    14.         return false;
    15. }
    16. void solve()
    17. {
    18.     int len,ans=0;
    19.     cin>>n;
    20.     pow10[0]=1;
    21.     for(int i=1;i<=18;i++)
    22.         pow10[i]=pow10[i-1]*10;
    23.     for(int i=1;i<=n;i++)
    24.     {
    25.         len=0;
    26.         while(true)
    27.         {
    28.             if(check(i,len))
    29.             {
    30.                 ans+=len;
    31.                 break;
    32.             }
    33.             len++;
    34.         }
    35.     }
    36.     cout<
    37.     return ;
    38. }
    39. signed main()
    40. {
    41.     cin.tie(0);
    42.     cout.tie(0);
    43.     ios::sync_with_stdio(0);
    44.     solve();
    45.     return 0;
    46. }

    D.Jobs (Easy Version)(前缀和)

    思路:我们开一个类似于前缀和的数组,can[ i ][ j ][ k ]存的值是在第i个公司当你的前两项属性值达到j和k时你的另一个属性值最少是多少.那么又因为j和k最大为400,我们就可以想前缀和那样直接从1开始遍历求出每个公司当两个属性达到某个值时另外一个值只需要多少就可以的结果.最后check一下即可.

    1. #include
    2. using namespace std;
    3. const int mod=998244353;
    4. long long pw[2000006];
    5. int n,len,a,b,c;
    6. int can[12][410][410];
    7. int solve(int x,int y,int z)
    8. {
    9.     int res=0;
    10.     for(int i=1;i<=n;i++)
    11.         if(z>=can[i][x][y])
    12.             res++;
    13. //当我们的第三项属性高于要求,则这个公司会聘用我们
    14.     return res;
    15. }
    16. signed main()
    17. {
    18.     memset(can,0x3f,sizeof can);
    19.     int q,seed1;
    20.     long long ans=0,lastans=0;
    21.     scanf("%d%d",&n,&q);
    22.     for(int i=1;i<=n;i++)
    23.     {
    24.         scanf("%d",&len);
    25.         while(len--)
    26.         {
    27.             scanf("%d%d%d",&a,&b,&c);
    28.             can[i][a][b]=min(can[i][a][b],c);
    29.         }
    30.         for(int j=1;j<=400;j++)
    31.             for(int k=1;k<=400;k++)
    32.                 can[i][j][k]=min({can[i][j][k],can[i][j-1][k],can[i][j][k-1]});
    33. //类似前缀和,求出当在第i个公司我们前两个属性为j和k时另一个属性的最小需求
    34.     }   
    35.     int seed;
    36.     scanf("%d",&seed); 
    37.     std::mt19937 rng(seed);
    38.     std::uniform_int_distribution<>u(1,400);	 
    39.     pw[0]=1;
    40.     for(int i=1;i<=q;i++)
    41.         pw[i]=pw[i-1]*seed%mod;
    42.     for (int i=1;i<=q;i++)
    43.     {
    44.         int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
    45.         int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
    46.         int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
    47.         lastans=solve(IQ,EQ,AQ);  // The answer to the i-th friend
    48.         ans+=lastans*pw[q-i];
    49.         ans%=mod;
    50.     }
    51.     printf("%lld",ans);
    52. 	return 0;
    53. }

    H.Wall Builder II

    思路:对于所有的面积进行枚举判断出所有可以拼成的长宽情况再进行check即可.

    此处的check就是把这个矩形分成很多行,我们一行行的贪心的去填充(小矩形宽度为1).填充方法为每次把可以填充进去的最大长度的矩形填充进去,最后判断是否可以填充完.(直接搬的队友代码)

    1. # include 
    2. # define endl '\n'
    3. # define int long long
    4. # define PII pair
    5. const int N = 110;
    6. using namespace std;
    7. using LL = long long;
    8. int cnt[N];
    9. void solve()
    10. {
    11.     int n,s=0,x,y,m=1e18;
    12.     cin>>n;
    13.     for(int i=1;i<=n;i++) 
    14.     {
    15.         s+=(n-i+1)*i;
    16.         cnt[i]=n-i+1;
    17.     }
    18.     for (int i=1;i*i<=s;i++)
    19.         if((s%i==0)&&(i+s/i
    20.             x=i,y=s/i;
    21.     cout<<(x+y)*2<
    22.     // cout << "x = " << x << " y = " << y << endl;
    23.     for(int i=1;i<=x;i++)
    24.     {
    25.         int l=y;
    26.         for(int j=n;j>=1;)
    27.         {
    28.             if(j<=l&&cnt[j]>0)
    29.             {
    30.                 cout<" "<-1<<" ";
    31.                 l-=j;
    32.                 cout<" "<
    33.                 cnt[j]--;
    34.             }
    35.             else 
    36.                 j--;
    37.         }
    38.     }
    39.     return;
    40. }
    41.  
    42. signed main() 
    43. {
    44.     ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    45.     int t = 1;
    46.     cin >> t;
    47.     while (t --) solve();
    48.     return 0;
    49. }

    A.Task Computing(贪心+dp)

    思路: 我们对于这些物品的组合方式进行排序的话,就会想到对于两个临近物品进行大小组合出的效果进行排序,我们比较两个相邻物品(第i个和第i+1个),按照不同顺序摆放得到的贡献表示为:

    w[i]+p[i]*w[i+1] 和 w[i+1]+p[i+1]*w[i];那么按照这个顺序进行从小到大的排序之后,组合的情况将会成为最优的,在进行组合的话.会发现这个题已经变成了一个背包问题,直接跑01背包即可.

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N =1e5+10,mod=998244353;
    5. const int pp=10000;
    6. double f[25];
    7. struct node
    8. {
    9.     double w,p; 
    10. }goods[N];
    11. void solve()
    12. {
    13.     int n,m;
    14.     cin>>n>>m;
    15.     for(int i=1;i<=n;i++)
    16.         cin>>goods[i].w;
    17.     for(int i=1;i<=n;i++)
    18.     {
    19.         cin>>goods[i].p;
    20.         goods[i].p/=pp;
    21.     }
    22.     sort(goods+1,goods+1+n,[&](node &x1,node &x2){
    23.         return x1.w+x1.p*x2.w
    24.     });
    25.     for(int i=1;i<=n;i++)
    26.         for(int j=m;j>=1;j--)
    27.             f[j]=max(f[j],f[j-1]*goods[i].p+goods[i].w);
    28.     cout<setprecision(8)<
    29.     return ;
    30. }
    31. signed main()
    32. {
    33.     cin.tie(0);
    34.     cout.tie(0);
    35.     ios::sync_with_stdio(0);
    36.     solve();
    37.     return 0;
    38. }

  • 相关阅读:
    C语言 编译和链接
    梦开始的地方——C语言指针练习题
    Python 中的 tqdm() 方法
    【题解】NowCoder DP4 最小花费爬楼梯
    【DPDK】Trace Library
    finally执行语句的注意和小陷阱
    Linux小技巧之awk必知必会
    理解网络协议里的协议
    5.XSS-反射型(post)利用：获取cookie
    小车测速模块使用介绍
  • 原文地址：https://blog.csdn.net/qq_49593247/article/details/126305238