• 机试（2017 cs se）

    2017计算机系夏令营 

    题解参考： 

    2017 华东师范计算机系暑期夏令营机考

    A. 不等式

    Problem #3304 - ECNU Online Judge

    有点像贪心算法

    选一个刚刚好在条件范围里的b[i]作为候选，【这个“刚刚好”是指选一个符合这个条件的最极限的值】

    代码

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5.      string x;string op[203];int a[203];int b[203];
    6.      int n;cin>>n;
    7.      for(int i=0;i
    8.           cin>>x>>op[i]>>a[i];
    9.           if(op[i]==">")b[i]=a[i]+1;//b[i]是ok的数字,a[i]是题目里的数字
    10.           else if(op[i]=="<")b[i]=a[i]-1;
    11.           else b[i]=a[i];
    12.      }
    13.      int ans=0;
    14.      for(int i=0;i//遍历每一个b[i]
    15.           int cnt=0;
    16.           for(int j=0;j//判断第j个命题是否能满足
    17.                if(op[j]=="="&&b[i]==a[j])cnt++;
    18.                else if(op[j]==">="&&b[i]>=a[j])cnt++;
    19.                else if(op[j]=="<="&&b[i]<=a[j])cnt++;
    20.                else if(op[j]==">"&&b[i]>a[j])cnt++;
    21.                else if(op[j]=="<"&&b[i]
    22.           }
    23.           ans=max(ans,cnt);//取cnt的最大值
    24.      }
    25.      cout<'\n';
    26.      return 0;
    27. }

    B. 1 的个数最多的整数

    Problem #3303 - ECNU Online Judge

    暴力

    首先把a变成二进制，之后从低位到高位遍历，如果这一位是0，那么看看能不能变成1（变成1会不会超过b，如果不会就记录）

    为什么要从低位开始遍历？如果从高位开始遍历的话，有些低位的1就选不到了

    注意：不要新开一个ans=0，之后判断条件为ans+tmp<=b；因为假设a=0001，b=1001（左边是低位）这样ans=1110的时候（这时ansb就不合法了

    所以直接在a上面做加法就可以了

    注意：如果用数组存放a和b的二进制，记得定义在T次循环的内部

    注意：(1<

    代码

    1. #include
    2. using namespace std;
    3. long long a,b;long long tmpa,tmpb;
    4. int main()
    5. {
    6.      int T;cin>>T;
    7.      for(int t=1;t<=T;t++){
    8.           int sa[70]={0};int sb[70]={0};
    9.           cin>>a>>b;
    10.           int st1=0,st2=0;
    11.           tmpa=a,tmpb=b;
    12.           while(tmpa){
    13.                sa[st1]=tmpa%2;tmpa/=2;st1++;
    14.           }
    15.           while(tmpb){
    16.                sb[st2]=tmpb%2;tmpb/=2;st2++;
    17.           }
    18.           long long tmp=1;
    19.           for(int i=0;i
    20.                if(sa[i]==0&&a+tmp<=b)//表示可以变成1看看
    21.                          a+=tmp;
    22.                tmp=tmp*2;
    23.  
    24.           }
    25.           cout<<"Case "<": "<'\n';
    26.      }
    27. }

    C. 打印

    打印n个相同的字符，插入或删除一个花费x，复制花费y

    动态规划

    首先dp[0]=0，dp[1]=x，dp[2]=min(dp[1]+x,dp[1]+y)，dp[3]=min(dp[2]+x,dp[1]+y+x)

    当 i 为双数时，dp[i]=min(dp[i-1]+x，dp[i/2]+y)

    当 i 单数时，dp[i]=min(dp[i-1]，dp[(i-1)/2]+y，dp[(i+1)/2]+y)+x

    注意：i为单数的时候，可以先（i-1）/2，再插入一个x；也可以（i+1）/2，再删除一个x

    代码

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. ll dp[10000007];
    5. int main()
    6. {
    7.      ll n,x,y;cin>>n>>x>>y;dp[1]=x;
    8.      for(int i=2;i<=n;i++){
    9.           if(i%2)dp[i]=min(dp[i-1],min(dp[(i-1)/2]+y,dp[(i+1)/2]+y))+x;
    10.           else dp[i]=min(dp[i-1]+x,dp[i/2]+y);
    11.      }
    12.      cout<
    13.      return 0;
    14. }

    D. 十亿分考

    Problem #3305 - ECNU Online Judge

    完全不会orz

    看标答有用随机数的，有用连分数的

    代码 随机数

    随机 重要的是eps来确定精度，但是如果精度太高会超时（例如1e-16），如果精度太低会WA（例如5e-16）

    for循环来鲁棒之类的（？）

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5.      long double eps=5e-16;
    6.      long double a;cin>>a;
    7.      srand(time(0));
    8.      long long p,q;
    9.      while(1){
    10.           q=rand()%1000000001;
    11.           long long mid=q*a;
    12.           for(long long p=mid-15;p<=mid+15;p++){
    13.                long double chp=(long double)p/q-a;
    14.                if(fabs(chp)
    15.                     cout<
      " "<'\n';
    16.                     return 0;
    17.                }
    18.           }
    19.      }
    20.  
    21. }

    代码 连分数

    题解 2017 华东师范计算机系暑期夏令营机考_十亿分考​​​​​​

    连分数OI wiki连分数 - OI Wiki (oi-wiki.org) 

    任何有理数都可以精确地以两种方式表示为连分数：

    Q：怎么从一个小数a得到a0，a1，a2，……an的表示呢？

    a0=(int)1/a        r0=(double)1/a0-(double)a0

    a1=(int)1/r0       r1=(double)1/a1-(double)a1

     ……

    an=(int)1/rn-1    rn=(double)1/an-(double)an

    Q：怎么从a0，a1，a2序列中算出原来的分子分母？

    这就是从最小的分式开始向上，最小的分式看作0，也就是p=0，q=1；向上p=1，q=cnt[n-1]；之后来到了新的分式，这时上下乘以q通分，分母是cnt[n-2]*q+原来的分子p，因为新来的分子永远是1，所以新的p=q；最后遍历完毕得到p和q

    注意当输入的a为0的时候要特判！！！

    1. #include
    2. using namespace std;
    3. vector<long long> cnt;
    4. long double cal(){
    5.      long double tmp=0;
    6.      for(int i=cnt.size()-1;i>=0;i--){
    7.           tmp+=cnt[i];
    8.           tmp=1/tmp;
    9.      }
    10.      return tmp;
    11. }
    12. int main()
    13. {
    14.      long double a;cin>>a;
    15.      if(!a){cout<<0<<" "<<1<<'\n';return 0;}
    16.      long double tmp=a;
    17.      while(1){
    18.           long long v=1/tmp;
    19.           cnt.push_back(v);
    20.           tmp=(long double)1/tmp-(long double)v;
    21.           if(fabs(a-cal())<4e-16)break;
    22.      }
    23.      long long p=0,q=1;
    24.      for(int i=cnt.size()-1;i>=0;i--){
    25.           p+=cnt[i]*q;
    26.           swap(p,q);
    27.      }
    28.      cout<
      " "<'\n';
    29.      return 0;
    30. }

    E. 有钱人买钻石

    Problem #3306 - ECNU Online Judge

    如果是动态规划的话 p是1e8 太大了

    dfs做，重点在于

    1. 从单价为1的硬币开始dfs

    2. 硬币枚数从高到低枚举，因为方案可行后就可以退出来了

    3. high的值为(p-sum)/y[id]，low的值为high-25

    【注意 int low=max(0,(p-sum)/y[id]-25); 的写法是错误的，因为n[id]可能没有那么多】所以用high

    为什么low是high-25？

    因为例如 30 29 0 0 0

    id=0的时候，high=29，low=4

            遍历到low=4了

    这时来想一想为什么要从大到小遍历呢？——因为要减少小的给大的让位来满足p的需求

    但是我让了25个位置了，就算有一个25来补足，也只是抹平抵消而已，并没有加上什么，说明方案就不可行，

            所以low=high-25就return了

    【但注意for循环的终止条件写  i>low 是错误的，因为low可能>high-25，只是因为不能为负，所以low=0；终止条件要写i>=low  】

    代码 dfs

    1. #include
    2. using namespace std;
    3. int p,n[5],ans=-1;
    4. int y[]={1,5,10,25};
    5. bool dfs(int sum,int id,int num){//已经兑换的额度，第几个硬币，已经兑换的个数
    6.      if(sum>p)return 0;
    7.      if(id==4){
    8.           if(sum==p){
    9.                ans=max(ans,num);
    10.                return 1;
    11.           }
    12.           return 0;
    13.      }
    14.      int high=min(n[id],(p-sum)/y[id]);
    15.      int low=max(0,high-25);//这个最低也挺妙的
    16.      for(int i=high;i>=low;i--){//注意从高到低枚举，成功了就可以break了
    17.           if(dfs(sum+y[id]*i,id+1,num+i))return 1;
    18.      }
    19.      return 0;
    20. }
    21. int main()
    22. {
    23.      ios::sync_with_stdio(0);cin.tie(0);
    24.      cin>>p>>n[0]>>n[1]>>n[2]>>n[3];
    25.      dfs(0,0,0);
    26.      if(ans==-1){cout<<"Impossible\n";return 0;}
    27.      cout<'\n';
    28.      return 0;
    29. }

    F. 送分题

    Problem #3307 - ECNU Online Judge

    离线 排序，以右端点为第一排序，左端点为第二排序来对区间排序

    用map来记录的话，就是种类：

    个数

    右指针移动，如果是增加的话，等于2的时候种类总和+1，之后移到右端点位置后，移动左指针，如果是减少的话如果减了且减到1了，种类总和-1，直到移动到左端点位置结束

    有的时候，不止向右，还会向左，例如3 3和1 5，这个时候就l就像r一样就可以了

    代码 TLE

    虽然是TLE（4/10）代码，但是写代码时注意区间的开闭问题，就比如下面的代码中，

    当 l 的起点是1，减法的时候 mp[a[l]]先减，之后再l--，而且循环条件为l，这就说明now.l这个点还没有被剪掉；r 的起点是0时，加法的时候，先r++，mp[a[r]]再加，循环条件为r，这就说明now.r在循环结束的时候已经被加上了

    1. #include
    2. using namespace std;
    3. struct node{
    4.      int l,r,id;
    5.  
    6. };
    7. bool cmp(node a,node b){
    8.      if(a.r!=b.r)return a.r
    9.      return a.l
    10. }
    11. node qu[500005];//左端点 右端点 id
    12. int a[500005]; int ans[500005];
    13. int main()
    14. {
    15.      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    16.      int N,Q;cin>>N>>Q;
    17.      for(int i=1;i<=N;i++)cin>>a[i];
    18.      for(int i=0;i
    19.           cin>>qu[i].l>>qu[i].r;
    20.           qu[i].id=i;
    21.      }
    22.      sort(qu,qu+Q,cmp);
    23.      int sum=0;
    24.      map<int,int>mp;int l=1,r=0;
    25.      for(int i=0;i
    26.           node now=qu[i];
    27.           while(r
    28.                r++;mp[a[r]]++;if(mp[a[r]]==2)sum++;
    29.                if(mp[a[r]]==3)sum--;
    30.           }
    31.           while(l
    32.                mp[a[l]]--;if(mp[a[l]]==2)sum++;
    33.                if(mp[a[l]]==1)sum--;l++;
    34.           }
    35.           while(l>now.l){
    36.                l--;mp[a[l]]++;if(mp[a[l]]==2)sum++;
    37.                if(mp[a[l]]==3)sum--;
    38.           }
    39.           ans[now.id]=sum;
    40.      }
    41.      for(int i=0;i'\n';
    42.      return 0;
    43. }

    代码 莫队 分块排序 TLE

    上面的代码时间复杂度最差还是O(mn)，所以用莫队

    莫队的形式

    分块，块的大小是根号n，对于l在同一个块内的，按照r的大小排序，否则就按照块号排序

    TLE(8/10)【unordered map使测试7通过了，用node或者把三者拆开来排序的效率都是一样的】

    1. #include
    2. using namespace std;
    3. unordered_map<int,int>mp;
    4. int a[500005];int ans[500005];
    5. int N,Q;int block;
    6. struct node{
    7.      int l,r,id;
    8. };
    9. node qu[500005];//左端点 右端点 id
    10. bool cmp(node a,node b){
    11.      if(a.l/block==b.l/block)//如果是在一个块内的
    12.      return a.r
    13.      return a.l/block//不在一个块内的按照块号分
    14. }
    15. int main()
    16. {
    17.      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    18.      cin>>N>>Q;block=sqrt(N);
    19.      for(int i=1;i<=N;i++)cin>>a[i];
    20.      for(int i=0;i
    21.           cin>>qu[i].l>>qu[i].r;
    22.           qu[i].id=i;
    23.      }
    24.      sort(qu,qu+Q,cmp);
    25.      int sum=0;
    26.      int l=1,r=0;
    27.      for(int i=0;i
    28.           node now=qu[i];
    29.           while(r>now.r){
    30.                mp[a[r]]--;if(mp[a[r]]==2)sum++;
    31.                if(mp[a[r]]==1)sum--;r--;
    32.           }
    33.           while(r
    34.                r++;mp[a[r]]++;if(mp[a[r]]==2)sum++;
    35.                if(mp[a[r]]==3)sum--;
    36.           }
    37.           while(l
    38.                mp[a[l]]--;if(mp[a[l]]==2)sum++;
    39.                if(mp[a[l]]==1)sum--;l++;
    40.           }
    41.           while(l>now.l){
    42.                l--;mp[a[l]]++;if(mp[a[l]]==2)sum++;
    43.                if(mp[a[l]]==3)sum--;
    44.           }
    45.           ans[now.id]=sum;
    46.      }
    47.      for(int i=0;i'\n';
    48.      return 0;
    49. }

    代码 莫队 分块 离散化 AC

    记录思考了两天的SB时刻

    注意看，虽然a[i]的范围是0~1e9，但是它只有5e6个数字，这个时候把a离散化以下，就可以把a在区间内的个数收纳在5e6的数组mp内，其中mp的序号是a[i]数值的种类，mp的值是a[i]在区间里出现的个数

    所以离散化，这样就不会在while里面的map的加减花费太多时间（？），于是就AC了！

    1. #include
    2. using namespace std;
    3. int mp[500005];
    4. int a[500005];int ans[500005];
    5. int N,Q;int block;int tot=0;
    6. struct node{
    7.      int l,r,id;
    8. };
    9. unordered_map<int,int>num;
    10. node qu[500005];//左端点 右端点 id
    11. bool cmp(node a,node b){
    12.      if(a.l/block==b.l/block)//如果是在一个块内的
    13.      return a.r
    14.      return a.l/block//不在一个块内的按照块号分
    15. }
    16. int main()
    17. {
    18.      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    19.      cin>>N>>Q;block=sqrt(N);
    20.      for(int i=1;i<=N;i++){
    21.           cin>>a[i];
    22.           if(num.count(a[i])==0)num[a[i]]=tot++;//离散化
    23.           a[i]=num[a[i]];
    24.      }
    25.      for(int i=0;i
    26.           cin>>qu[i].l>>qu[i].r;
    27.           qu[i].id=i;
    28.      }
    29.      sort(qu,qu+Q,cmp);
    30.      int sum=0;
    31.      int l=1,r=0;
    32.      for(int i=0;i
    33.           node now=qu[i];
    34.           while(r>now.r){
    35.                mp[a[r]]--;if(mp[a[r]]==2)sum++;
    36.                if(mp[a[r]]==1)sum--;r--;
    37.           }
    38.           while(r
    39.                r++;mp[a[r]]++;if(mp[a[r]]==2)sum++;
    40.                if(mp[a[r]]==3)sum--;
    41.           }
    42.           while(l
    43.                mp[a[l]]--;if(mp[a[l]]==2)sum++;
    44.                if(mp[a[l]]==1)sum--;l++;
    45.           }
    46.           while(l>now.l){
    47.                l--;mp[a[l]]++;if(mp[a[l]]==2)sum++;
    48.                if(mp[a[l]]==3)sum--;
    49.           }
    50.           ans[now.id]=sum;
    51.      }
    52.      for(int i=0;i'\n';
    53.      return 0;
    54. }

    2017软件系夏令营

    3296. 2333

    Problem #3296 - ECNU Online Judge

    首先魔法石可以变成2或者3或者23，问最多能组多少个2333

    那最省的组成方法就是三个石头组成一个2333，所以整除3就好了

    重点：做题时要看清题目，一开始看成多少种排列组合了，仔细看了看之后才发现是能组多少个

    注意：输出一个答案后要换行

    代码

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5.      ios::sync_with_stdio(0);cin.tie(0);
    6.      int T;cin>>T;int a;
    7.      while(T--){
    8.           cin>>a;
    9.           cout<3<<'\n';
    10.      }
    11.      return 0;
    12. }

    3297. 铺瓷砖

    Problem #3297 - ECNU Online Judge

    就方案数 和 1的个数

    乍一看以为是状态压缩dp，吓死

    代码 dfs

    方案数就是最后return的时候如果是合理的，那么方案数+1；1的个数就是return的时候加上该方案1的个数

    1. #include
    2. using namespace std;
    3. int maxx=0,all=0,ans=0;
    4. void dfs(int sum,int pre,int num){//sum是已经铺的，pre是前一个，num是有多少个1
    5.      if(sum>=all){
    6.           if(sum==all){maxx=maxx+num;ans++;}
    7.           return;
    8.      }
    9.      if(pre==1){
    10.           dfs(sum+2,2,num);dfs(sum+3,3,num);
    11.      }
    12.      else if(pre==2){
    13.           dfs(sum+1,1,num+1);dfs(sum+3,3,num);
    14.      }
    15.      else if(pre==3){
    16.           dfs(sum+1,1,num+1);dfs(sum+2,2,num);
    17.      }
    18.      else{
    19.           dfs(sum+1,1,num+1);dfs(sum+2,2,num);dfs(sum+3,3,num);
    20.      }
    21. }
    22. int main()
    23. {
    24.      ios::sync_with_stdio(0);cin.tie(0);
    25.      int T;cin>>T;string s;
    26.      while(T--){
    27.           maxx=0;ans=0;cin>>all;
    28.           dfs(0,0,0);
    29.           cout<'\n'<'\n';
    30.      }
    31.      return 0;
    32. }

    代码 线性dp

    用两个dp来表示，一个是方案数，一个是1的个数

    二维dp，第一位是长度，第二位是现在放入的；

    初始化dp[1][1]=1,dp[2][2]=1,dp[3][3]=1,dp[3][2]=1,dp[3][1]=1;

    状态转移dp[i][1]=dp[i-1][2]+dp[i-1][3]，dp[i][2]=dp[i-2][1]+dp[i-2][3]，dp[i][3]=dp[i-3][1]+dp[i-3][2]；

    方案数总数是dp[n][1]+dp[n][2]+dp[n][3]

    如何得到1的个数？——想不出来怎么从上面的dp中找到1的个数的答案，所以就新开了一个one

    状态转移：

    one[n][1]中1的个数是从one[n-1][2]+1和one[n-1][3]+1得到的；【但是这一步是有问题的】

    one[n][2]中1的个数是从one[n-2][1]和one[n-2][3]得到的；

    one[n][3]中1的个数是从one[n-3][1]和one[n-3][2]得到的

    初始化 one[1][1]=1，one[3][1]=1，one[3][2]=1

    Q：上面划线的步骤为什么有问题呢？

    因为不确定one[n-1][2]和one[n-1][3]是否合法，例如one[4][2]就不合法，如果按照上面的步骤就变成了one[5][1]=one[4][2]+one[4][3]+2，这是不合法的

    并且，只要是dp[i-1][2]和dp[i-1][3]存在，所有的它们后面加上1都可以增加one[i][1]的个数

    例如，下面是dp[6][1]的方案，从中可以看到dp[5][2]=2，dp[5][3]=1

    2 3 1

    3 2 1

    2 1 2 1

    从上面可以看到1放在了所有dp[i-1][2]和dp[i-1][3]方案的后面

    Q：应该怎么改进呢？

    状态方程应该变为one[i][1]=one[i-1][2]+one[i-1][3]+dp[i-1][2]+dp[i-1][3];

    1. #include
    2. using namespace std;
    3. int maxx=0,n=0;
    4. int dp[35][4];
    5. int one[35][4];
    6. int main()
    7. {
    8.      ios::sync_with_stdio(0);cin.tie(0);
    9.      int T;cin>>T;string s;
    10.      while(T--){
    11.           memset(dp,0,sizeof(dp));cin>>n;
    12.           dp[1][1]=1,dp[2][2]=1,dp[3][3]=1,dp[3][2]=1,dp[3][1]=1;
    13.           one[1][1]=1,one[3][1]=1,one[3][2]=1;
    14.           for(int i=4;i<=n;i++){
    15.                dp[i][1]=dp[i-1][2]+dp[i-1][3];
    16.                dp[i][2]=dp[i-2][1]+dp[i-2][3];
    17.                dp[i][3]=dp[i-3][1]+dp[i-3][2];
    18.                one[i][1]=one[i-1][2]+one[i-1][3]+dp[i-1][2]+dp[i-1][3];
    19.                one[i][2]=one[i-2][1]+one[i-2][3];
    20.                one[i][3]=one[i-3][1]+one[i-3][2];
    21.           }
    22.           cout<1]+dp[n][2]+dp[n][3]<<'\n'<1]+one[n][2]+one[n][3]<<'\n';
    23.  
    24.      }
    25.      return 0;
    26. }

    不过既然想到状压dp了，那就来一道状压铺瓷砖吧

    补充：状压dp

    291. 蒙德里安的梦想

    参考题解：AcWing 291. 蒙德里安的梦想

    题意：求把N×M的棋盘分割成若干个1×2 的的小长方形，有多少种方案。1≤N,M≤11

    思路：总的方案数就等于摆完所有横向长方形的方案数。所以，我们只用考虑如何枚举横向长方形的摆放即可

    3298. 排队买夜宵

    Problem #3298 - ECNU Online Judge

    做了那么久 终于有一道我一看就会的题了qwq

    和 合法括号序列判断 一模一样的题

    代码

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5.      ios::sync_with_stdio(0);cin.tie(0);
    6.      int T;cin>>T;string s;
    7.      while(T--){
    8.           stack<char>st;
    9.           cin>>s;
    10.           for(int i=0;s[i];i++){
    11.                if(st.empty())st.push(s[i]);
    12.                else if(st.top()=='1'&&s[i]=='0')st.pop();
    13.                else if(st.top()=='0'&&s[i]=='1')st.pop();
    14.                else st.push(s[i]);
    15.           }
    16.           cout<size()<<'\n';
    17.      }
    18.      return 0;
    19. }

    9. Alice and A simple problem

    Problem #9 - ECNU Online Judge

    简单模拟

    代码 

    1. #include
    2. using namespace std;
    3. int dp[101][101],cnt=0;
    4. int main()
    5. {
    6.      int m,n;cin>>m>>n;
    7.      for(int i=0;i//行
    8.           for(int j=0;j
    9.                dp[j][i]=++cnt;
    10.           }
    11.      }
    12.      for(int i=0;i
    13.           for(int j=0;j
    14.                cout<
    15.                if(j!=n-1)cout<<' ';
    16.           }
    17.           cout<<'\n';
    18.      }
    19.      return 0;
    20. }

    11. Cacey and Calphabet

    找到最大上升子序列的长度?

    代码 vector+lower_bound Onlogn

    其实就是贪心算法

    1. #include
    2. using namespace std;
    3. vector<int> v;
    4. int main()
    5. {
    6.     string s;cin>>s;
    7.      for(int i=0;s[i];i++){
    8.           if(v.empty())v.push_back(s[i]-'a');
    9.           else{
    10.                int tmp=lower_bound(v.begin(),v.end(),s[i]-'a')-v.begin();
    11.                if(tmp==v.size())v.push_back(s[i]-'a');
    12.                else v[tmp]=s[i]-'a';
    13.           }
    14.      }
    15.      cout<<26-v.size();
    16.      return 0;
    17. }

    代码 dp On^2

    dp[i]表示以i为结尾的最

    首先找到s[j]小于s[i]且dp[j]最大的，dp[i]=dp[j]+1

    1. #include
    2. using namespace std;
    3. vector<int> v;
    4. int dp[55];
    5. int main()
    6. {
    7.      string s;cin>>s;int n=s.size();
    8.      for(int i=0;i
    9.           int maxx=0;
    10.           for(int j=0;j
    11.                if(s[j]maxx)maxx=dp[j];
    12.           }
    13.           dp[i]=maxx+1;
    14.      }
    15.      cout<<26-dp[n-1];
    16. }

    代码 树状数组 nlogn

    树状数组的目的在于找到 i 之前的s[j]

    所以可以以j 和 i为序，换句话说，树状数组的序号只要26个就可以了

    一边遍历，一边更新树状数组

    1. #include
    2. using namespace std;
    3. # define lowbit(x) x&(-x)
    4. int a[30];
    5. int query(int x){//查询是向下的，比如9的话要查a[8]和a[9]
    6.      int ma=0;
    7.      for(;x;x-=lowbit(x))
    8.           ma=max(ma,a[x]);
    9.      return ma;
    10. }
    11. void add(int x,int k){//更新是向上的，比如更新了a[3]，a[4]也要更新
    12.      for(;x<=26;x+=lowbit(x)) 
    13.          a[x]=max(a[x],k);
    14.      return;
    15. }
    16. int main()
    17. {
    18.      string s;cin>>s;int n=s.size();int ans=0;
    19.      for(int i=0;s[i];i++){
    20.           int ma=query(s[i]-'a'+1-1);//+1是因为树状数组是从1开始的，-1是因为s[j]
    21.           add(s[i]-'a'+1,ma+1);
    22.           ans=max(ans,ma+1);
    23.      }
    24.      cout<<26-ans;
    25. }

    3299. 主色调

    Problem #3299 - ECNU Online Judge

    时限是3s，暴力做法

    在遍历区间的时候，第二层循环来了一个颜色，这个颜色出现次数++，更新其中出现次数最多的颜色的最小的序号【这个用一个if条件判断就可以达到了】

    其实就是很普通的模拟题

    代码

    1. #include
    2. using namespace std;
    3. int a[5003];
    4. int main()
    5. {
    6.      int n;
    7.      while(cin>>n){
    8.           vector<int> ans(n+1,0);
    9.           for(int i=0;i>a[i];
    10.           for(int i=0;i
    11.                vector<int>v(n+1,0);int maxid=0,maxxv=0;
    12.                for(int j=i;j
    13.                     v[a[j]]++;
    14.                     if(maxxva[j])){
    15.                          maxid=a[j];maxxv=v[a[j]];
    16.                     }
    17.                     ans[maxid]++;
    18.                }
    19.           }
    20.           for(int i=1;i<=n;i++){
    21.                cout<if(i!=n)cout<<' ';
    22.           }
    23.           cout<<'\n';
    24.      }
    25. }

    3300. 奇数统计

    Problem #3300 - ECNU Online Judge

    不会做，写一个暴力，TLE了

    1. #include
    2. using namespace std;
    3. int a[100005];
    4. long long C(long long m,long long n){
    5.      long long g=1,d=1;
    6.      for(int i=1;i<=m-n;i++){
    7.           g=g*(i+n);
    8.           d=d*i;
    9.      }
    10.      return g/d;
    11. }
    12. int main()
    13. {
    14.      int n,T;cin>>T;
    15.      while(T--){
    16.           cin>>n;int ans=0;
    17.           for(int i=0;i>a[i];
    18.           for(int i=0;i
    19.                for(int j=0;j
    20.                     if(a[i]continue;
    21.                     if(C(a[i],a[j])&1)ans++;
    22.                }
    23.           }
    24.           cout<'\n';
    25.      }
    26. }

    参考

    题解：EOJ-3300 奇数统计（高维前缀和）

    卢卡斯定理：算法学习笔记(25): 卢卡斯定理 

    组合数的奇偶判断：组合数奇偶性的判断（附证明）

    题解

    前置知识：n!中含有2因子的个数等于(n-它的二进制形式中1的个数)

    Q：为什么n!中含有2因子的个数等于(n-它的二进制形式中1的个数)？

    前置知识：

    N!质因数2的个数 = [N / 2] + [N / 4] + [N / 8] + ....

    因为N/2 表示的是2 4 6 8 10 12……这些相隔为2的数的个数；N / 4表示的是4 8 12 16这些相隔为4的数……这样子加起来就是N!质因数2的个数

    定理：n!中含有2因子的个数等于(n-它的二进制形式中1的个数)证明

    【有点树状数组 lowbit 的感觉】

    补充：n&(n-1)作用：将n的二进制表示中的最低位为1的改为0，用于将n的二进制表示中的最低位为1的改为0

    重点：a&b=b组合数是奇数，所以要找a&b=b的组合

    设sum[b]的值是对于b来说，和b组合的组合数会变成奇数的个数；算法是动态规划

    这里用高维前缀和：

    应用：当序号j是序号i的子集的时候，f[i]+=f[j]; 最后f[i]是所有序号是i的子集的数组的和

    其思路为：第一个回合，现在看最低位的二进制是不是1，如果是的话最低位是0的那个数就会加给你；第x个回合，看看现在第x位的二进制是不是1，如果是的话，把第x位是0的那个数加给你

    1. for(int j = 0; j < n; j++) 
    2.     for(int i = 0; i < 1 << n; i++)
    3.         if(i >> j & 1) f[i] += f[i ^ (1 << j)];

    注意：每一个T记得要初始化前缀和

    代码

    1. #include
    2. using namespace std;
    3. #define int long long
    4. int f[400005];
    5. int a[100005];
    6. signed main()
    7. {
    8.      int T;cin>>T;
    9.      while(T--){
    10.           memset(f,0,sizeof(f));
    11.           int n;cin>>n;int x;
    12.           for(int i=0;i
    13.                cin>>a[i];f[a[i]]++;
    14.           }
    15.           for(int i=0;i<18;i++){
    16.                for(int j=0;j<(1<<18);j++){
    17.                     if(j>>i&1)f[j]+=f[j^(1<
    18.                }
    19.           }int ans=0;
    20.           for(int i=0;i
    21.                ans+=f[a[i]];
    22.           }
    23.           cout<'\n';
    24.      }
    25.      return 0;
    26. }

    3301. OIOIOI 

    Problem #3301 - ECNU Online Judge

    没看到题解，是构造题，算了

  • 相关阅读:
    腾讯云centos7.6安装jdk
    分布式和微服务
    Jmeter接口自动化测试操作流程
    Qt使用QSettings类来读写ini
    电子邮件地址注册过程详解
    vue2.x与vue3.x中自定义指令详解
    基于微服务的分布式新生报到系统-计算机毕业设计
    如何利用Web应用防火墙应对未知威胁
    数据化管理洞悉零售及电子商务——零售策略中的数据化管理
    中国冰淇淋市场深度评估及发展趋势预测报告（2022版）
  • 原文地址：https://blog.csdn.net/zy98zy998/article/details/132712769