https://ac.nowcoder.com/acm/contest/3003#question

前言：嘤嘤嘤

啊，今天这次的感觉不爽，莫得手感，啊，那道dp的题我没做出来，太菜了。

A、做游戏

这个题水的太厉害了，没啥可说的。

  1. import java.util.*;
  2. class q {
  3.     q() {
  4.         Scanner scanner=new Scanner(System.in);
  5.         long a=scanner.nextLong();
  6.         long b=scanner.nextLong();
  7.         long c=scanner.nextLong();
  8.         long x=scanner.nextLong();
  9.         long y=scanner.nextLong();
  10.         long z=scanner.nextLong();
  11.         if(a>y)a=y;
  12.         if(b>z)b=z;
  13.         if(c>x)c=x;
  14.         System.out.println(a+b+c);
  15.     }
  16. }
  17. public class Main {
  18.     public static void main(String[] args) {
  19.         new q();
  20.     }
  21. }

B、排数字

还是水题

  1. import java.util.*;
  2. class q {
  3.     q() {
  4.         Scanner scanner=new Scanner(System.in);
  5.         long a=scanner.nextLong();
  6.         char[] b=scanner.next().toCharArray();
  7.         int x=0,y=0;
  8.         for(int i=0;i<a;i++){
  9.             if(b[i]=='6')x++;
  10.             if(b[i]=='1')y++;
  11.         }
  12.         System.out.println(y<x?y:x-1);
  13.     }
  14. }
  15. public class Main {
  16.     public static void main(String[] args) {
  17.         new q();
  18.     }
  19. }

C、算概率

这个题有点意思，先看看题干

牛牛刚刚考完了期末，尽管 牛牛 做答了所有 2020牛客寒假算法基础集训营2 - 图1 道题目，但他不知道有多少题是正确的。 不过，牛牛 知道第 2020牛客寒假算法基础集训营2 - 图2 道题的正确率是 2020牛客寒假算法基础集训营2 - 图3 。 牛牛 想知道这 2020牛客寒假算法基础集训营2 - 图4 题里恰好有 2020牛客寒假算法基础集训营2 - 图5 题正确的概率分别是多少，对 2020牛客寒假算法基础集训营2 - 图6 取模。 对2020牛客寒假算法基础集训营2 - 图7 取模的含义是：对于一个2020牛客寒假算法基础集训营2 - 图8 的不可约分数 2020牛客寒假算法基础集训营2 - 图9，存在 2020牛客寒假算法基础集训营2 - 图10 使得2020牛客寒假算法基础集训营2 - 图11，2020牛客寒假算法基础集训营2 - 图12 即为 2020牛客寒假算法基础集训营2 - 图13 对 2020牛客寒假算法基础集训营2 - 图14 取模的结果。

啊，这都什么东西，如果照这个题干的意思我完全可以一上来就假定2020牛客寒假算法基础集训营2 - 图15，然后之后的就是找2020牛客寒假算法基础集训营2 - 图16，但这想法肯定不对（蜜汁自信），然后就没的想法了，刚才看了看题解，居然是动态规划。强，第一次知道状态转移方程可以这么用。
先贴出来状态转移方程

2020牛客寒假算法基础集训营2 - 图17

其中，2020牛客寒假算法基础集训营2 - 图18表示前 2020牛客寒假算法基础集训营2 - 图19 道题做对 2020牛客寒假算法基础集训营2 - 图20 道的概率

太强了。计算的原理知道了，那么那个概率 2020牛客寒假算法基础集训营2 - 图21 到底是咋来的，这个题干是个嘛意思。

先贴个已经过了的代码，然后直接在里头加注释吧。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 2005, mod = 1e9 + 7;
  4. //初始化
  5. long long n, p[N], f[N][N];
  6. int main() {
  7.       cin >> n;
  9.         //导数据
  10.       for (int i = 1; i <= n; ++i)cin >> p[i];
  12.         //开始动规
  13.       for (int i = f[0][0] = 1; i <= n; ++i) {
  14.             //每组代表队有几道题，每列代表对几道题
  16.             //每组第一个数据特殊处理
  17.             f[i][0] = f[i - 1][0] * (mod + 1 - p[i]) % mod;
  19.             //开始状态转移
  20.             for (int j = 1; j <= i; ++j)
  21.             f[i][j] = (f[i - 1][j] * (mod + 1 - p[i]) + f[i - 1][j - 1] * p[i]) % mod;
  23.       }
  25.       //结果输出
  26.       for (int i = 0; i <= n; ++i)cout << f[n][i] << ' ';
  28.       return 0;
  29. }

流程是这么个流程，这个 2020牛客寒假算法基础集训营2 - 图22 在式子中的表现为2020牛客寒假算法基础集训营2 - 图23，迷的不行，啊，多想想，到底是为什么使他在这里呈现等价的性质。

D、数三角

这个题说白了就是判断是不是钝角三角形，直接全部列举一遍，先求出三条边的长度2020牛客寒假算法基础集训营2 - 图24（其中2020牛客寒假算法基础集训营2 - 图25为最长边）然后通过2020牛客寒假算法基础集训营2 - 图26且2020牛客寒假算法基础集训营2 - 图27来判断这个三角形是否为钝角三角形。

  1. import java.util.*;
  2. class q {
  3.     //求边长的平方（避免开根后失去精度）
  4.     int length(int x1,int y1,int x2,int y2){
  5.         return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
  6.     }
  7.     q() {
  8.         Scanner scanner=new Scanner(System.in);
  9.         int a=scanner.nextInt();
  10.         if(a<3){
  11.             System.out.println(0);
  12.         }else {
  13.             int[][] l=new int[a][2];
  14.             for(int i=0;i<a;i++){
  15.                 l[i][0]=scanner.nextInt();
  16.                 l[i][1]=scanner.nextInt();
  17.             }
  18.             int t=a-2;
  19.             int y=a-1;
  20.             int k=0;
  21.             for(int z=0;z<t;z++){
  22.                 for(int x=z+1;x<y;x++){
  23.                     for(int c=x+1;c<a;c++){
  24.                         double l1=length(l[z][0],l[z][1],l[x][0],l[x][1]);
  25.                         double l2=length(l[x][0],l[x][1],l[c][0],l[c][1]);
  26.                         double l3=length(l[c][0],l[c][1],l[z][0],l[z][1]);
  27.                         double[] p={l1,l2,l3};
  28.                         Arrays.sort(p);
  29.                         if(p[0]+p[1]<p[2]&&2*Math.sqrt(p[0]*p[1])+p[0]+p[1]>p[2])k++;
  30.                     }
  31.                 }
  32.             }
  33.             System.out.println(k);
  34.         }
  35.     }
  36. }
  37. public class Main {
  38.     public static void main(String[] args) {
  39.         new q();
  40.     }
  41. }

E、做计数

emmmmm，这个题倒是不难，就是会有人一见2020牛客寒假算法基础集训营2 - 图28陷入一种思维盲区，即认为 2020牛客寒假算法基础集训营2 - 图29 和 2020牛客寒假算法基础集训营2 - 图30 都是平方数，但，你们忘了可爱的2020牛客寒假算法基础集训营2 - 图31，实际上，我们可以把2020牛客寒假算法基础集训营2 - 图32理解为2020牛客寒假算法基础集训营2 - 图33。
所以只需令2020牛客寒假算法基础集训营2 - 图34为平方数即可。而2020牛客寒假算法基础集训营2 - 图35；所以只要枚举小于2020牛客寒假算法基础集训营2 - 图36的平方数就可以了。

  1. import java.util.*;
  2. class q {
  3.     q() {
  4.         Scanner scanner=new Scanner(System.in);
  5.         int n=scanner.nextInt();
  6.         long k=0;
  7.         long s=0;
  8.         long sum=0;
  9.         for(int z=1;(k=z*z)<=n;z++){
  10.             int i;
  11.             s=0;
  12.             for(i=1;i*i<=k;i++){
  13.                 if(k%i==0)s++;
  14.             }
  15.             s*=2;
  16.             s--;
  17.             sum+=s;
  18.         }
  19.         System.out.println(sum);
  20.     }
  21. }
  22. public class Main {
  23.     public static void main(String[] args) {
  24.         new q();
  25.     }
  26. }

F、拿物品

这个题……怎么说，刚一到手你可能被花花题干迷惑了双眼，然后在2020牛客寒假算法基础集训营2 - 图37和2020牛客寒假算法基础集训营2 - 图38 中迷惑了双眼，不知道先考虑 2020牛客寒假算法基础集训营2 - 图39 还是 2020牛客寒假算法基础集训营2 - 图40 。我们可以把每一个点统一出一个贡献标准来。你如果选了一个点，那对方就选不了这个点，所以这个点对你本人的贡献为你可以获得的点数和对方获得不了的点数的和2020牛客寒假算法基础集训营2 - 图41。那么标准确定了，然后就是个排序，然后挨个选当前可以取到的最大值就可以了。

  1. import java.util.*;
  2. class q {
  3.     //快速排序
  4.     private void quickSort(long[] a, int l, int r, int[] m){
  5.         if(l>=r)return;
  6.         int i = l; int j = r; long key = a[m[l]],p=m[l];
  7.         while(i<j){
  8.             while(i<j && a[m[j]]>=key)j--;
  9.             if(i<j){
  10.                 m[i] = m[j];
  11.                 i++;
  12.             }
  13.             while(i<j && a[m[i]]<key)i++;
  14.             if(i<j){
  15.                 m[j] = m[i];
  16.                 j--;
  17.             }
  18.         }
  19.         m[i] = (int) p;
  20.         quickSort(a, l, i-1,m);
  21.         quickSort(a, i+1, r,m);
  22.     }
  23.     q() {
  24.         Scanner scanner=new Scanner(System.in);
  25.         int n=scanner.nextInt();
  26.         long[] k=new long[n];
  27.         int[] m=new int[n];
  28.         for(int i=0;i<n;i++){
  29.             k[i]=scanner.nextInt();
  30.             m[i]=i;
  31.         }
  32.         for(int i=0;i<n;i++){
  33.             k[i]+=scanner.nextInt();
  34.         }
  35.         quickSort(k,0,n-1,m);
  36.         for(int i=n-1;i>=0;i-=2) {
  37.             System.out.print(m[i]+1);
  38.             System.out.print(' ');
  39.         }
  40.         System.out.println();
  41.         for(int i=n-2;i>=0;i-=2) {
  42.             System.out.print(m[i]+1);
  43.             System.out.print(' ');
  44.         }
  45.     }
  46. }
  47. public class Main {
  48.     public static void main(String[] args) {
  49.         new q();
  50.     }
  51. }

G、判正误

先来看看这丑陋的题干在问的是哪个的式子

2020牛客寒假算法基础集训营2 - 图42

多么丑陋。

首先的想法是同余，然后看是不是一样，然后当时我的代码不知道出了什么故障，说我tle。我还以为要进行优化，就又把别的又调试了调试，还是不行。于是我推到了全重写了一遍，还是不行。之后和别人交流了一下，发现这个题居然在卡数据，还转卡1000000007等一系列有特殊原因的数，然后我把2020牛客寒假算法基础集训营2 - 图43变成了2020牛客寒假算法基础集训营2 - 图44就可以了。后来我又试了试，发现111111和987也可以。（这怕不就是面向数据编程/狗头）

  1. import java.util.*;
  2. public class Main{
  3.     static int lll=987;
  4.     static long testPosition(long l,long ll) {
  5.         long b=ll;
  6.         long r = 1, base = l;
  7.         while (b!=0) {
  8.             if ((b & 1)!=0) {
  9.                 r *= base;
  10.                 r%=lll;
  11.             }
  12.             base *= base;
  13.             base%=lll;
  14.             b >>= 1;
  15.         }
  16.         return r;
  17.     }
  18.     public static void main(String []args){
  19.         Scanner kb=new Scanner(System.in);
  20.         int n=kb.nextInt();
  21.         while(n--!=0){
  22.             long a=kb.nextLong()%lll;
  23.             long b=kb.nextLong()%lll;
  24.             long c=kb.nextLong()%lll;
  25.             long d=kb.nextLong();
  26.             long e=kb.nextLong();
  27.             long f=kb.nextLong();
  28.             long g=kb.nextLong();
  29.             a=testPosition(a,d);
  30.             b=testPosition(b,e);
  31.             c=testPosition(c,f);
  32.             a=(a+b+c)%lll;
  33.             g=g%lll;
  34.             if (a!=g) {
  35.                 System.out.println("No");
  36.             }else {
  37.                 System.out.println("Yes");
  38.             }
  40.         }
  42.     }
  43. }

H、施魔法

首先，根据题干的意思与尝试，我们索要选取的必然是经排序后而产生的连续区间。然后这又是个动态规划问题

2020牛客寒假算法基础集训营2 - 图45

其中， 2020牛客寒假算法基础集训营2 - 图46 表示用掉前 2020牛客寒假算法基础集训营2 - 图47 个元素的最小代价。
然后就是个码代码了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 3e5 + 7;
  4. int dp[N], pre, a[N], n, k;
  5. int main() {
  6.   scanf("%d%d", &n, &k);
  7.   for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  8.   sort(a + 1, a + 1 + n);
  9.   pre = -a[1];
  10.   for (int i = 1; i < k; ++i) dp[i] = 2e9;
  11.   for (int i = k; i <= n; ++i) {
  12.     dp[i] = pre + a[i];
  13.     pre = min(pre, dp[i - k + 1] - a[i - k + 2]);
  14.   }
  15.   cout << dp[n];
  16.   return 0;
  17. }