A. Dreamoon and Ranking Collection

题意：题意不太好理解。简单来讲就是，给出一组数，能从1最多数到几，不够的用数来填，最多填x次。思路:代码很简单…先出现过的地方肯定不要花费了,就是补下没出现过的地方就好了…然后判断下最后能连到哪个数就是答案

#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
#include <algorithm>
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define f first
#define s second
using namespace std;
const int N = 1e6 + 10;
typedef pair<int,int> PII;
typedef long long LL;
char s[N],t[N], Ma[N * 2];
int a[N * 2], cnt[N];
int T, Next[N], extend[N];

int main()
{
    int t,n,m;
    cin >> t;
    while(t--)
    {
      int ans = 0;
      memset(cnt,0,sizeof(cnt));
      cin >> n >> m;
      for(int i = 1; i <= n; i ++)
      {
          cin >> a[i];
          cnt[a[i]] = 1;
      }
      sort(a + 1, a + 1 + n);
      for(int i = 1; m >= 0; i ++)
      {
          if(cnt[i]) ans ++;
          else      
          {
              if(m > 0) 
                 ans++,m--;
              else break;
          }
      }
      cout << ans << endl;
    }
    return 0;
}

B,Dreamoon Likes Permutations

题目大意：t组数据,输入n个数,将这n个数分为2段，问你有多少种相邻的子段是从1~任意数(顺序可以乱)的的全排列。输出种类数,还有每个子段的长度,假如没有子段符合题意就输出-1

思路：因为只要分成两段所以，我们先正序扫一遍看看哪些位置是全排列，然后再逆序扫一遍

如何判断是全排列用set set.begin() = 1,set.end() = n ,set.size() = n[因为set自带去重]

下面看代码

#include <iostream>
#include <cstdio>
#include <set>
#include <bits/stdc++.h>
#include <stack>
#include <vector>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
#include <algorithm>
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define f first
#define s second
using namespace std;
const int N = 1e6 + 10, maxn = 2e5 + 10;
typedef long long LL;
typedef pair<LL,LL> PII;
PII ans[N];
LL a[N * 2], cnt[N], T;
unordered_map<int,bool> mp;
set <int> order, unorder;
int main()
{
    IOS;
   
    cin >> T;
    while(T --)
    {
        order.clear();
        unorder.clear();
        mp.clear();
        int n;
        cin >> n;
        for(int i = 1; i <= n; ++ i)
          cin >> a[i];
         
        for(int i = 1; i <= n; ++ i)
        {
            order.insert(a[i]);
            auto b = order.begin();
            auto c = order.end();
            if((int)order.size() == i && (*b) == 1 && *(--c) == i)
              mp[i] = true;
        }
        int cnt = 0;
        for(int i = n; i >= 1; -- i)
        {
            unorder.insert(a[i]);
            auto b = unorder.begin();
            auto c = unorder.end();
            if((int)unorder.size() == n - i + 1 && (*b) == 1 && *(--c) == n - i + 1 && mp[i - 1])
              ans[cnt ++] = {i - 1,n - i + 1};
        }
        cout << cnt << endl;
        for(int i = 0; i < cnt; ++ i)
         cout << ans[i].f << " " << ans[i].s << endl;
    }
    return 0;
}

C. Dreamoon Likes Coloring

不得不说这题意坑死我qwq

题目大意：就是说给你n个格子（编号从1~n）你有m次操作，每次操作你可以在[1 ~ n - mi + 1]里选择一个起点，涂长度为mi的连续个格子，每次操作涂上的颜色最后一定要可见，并且所有的格子都要涂上颜色

其实你观察可以发现每次操作可以涂任意位置连续长度为mi的格子

qwq比赛的时候被这个颜色坑到了

通过观察可知选择边界点一定可以涂色到最后，为了防止颜色被覆盖，每次操作可以从对应次序的格子开始涂，在最后的操作选择最后一个涂到最后就可以了

无解情况:1.就是你m次操作覆盖的长度加起来小于n

2.就是你每次操作可以涂的颜色长度不能被前面的覆盖

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;cin>>n>>m;
 
    int l[n]={};
    long long tot_len=0;
    
    for(int i=0;i<m;i++)
    {
        cin>>l[i];
        if(n-l[i]+1<=i)//最大染色起点在前面的方格中
        {
            cout<<"-1";
            return 0;
        }
        tot_len+=l[i];
    }
 
    if(tot_len<n)//总染色长度小于n
    {
        cout<<"-1";
        return 0;
    }
 
    for(int i=0;i<m;i++)//开始染色
    {
        cout<<max(i+1LL,n-tot_len+1)<<" \n"[i==m-1];
        tot_len-=l[i];
    }
 
    return 0;
}

D. Dreamoon Likes Sequences

题目大意:就是说从1~d中选择出一个数列a1,a2,a3,a4…an;

1.an数列是单调递增的数列

2.设bn = a1 ^ a2 ^ a3…^an;

bn数列也是一个递增数列

问你，这样的数列a有多少个

模上m

思路：通过观察可知，异或是不进位的加法，要求异或递增，那么二进制上最高位上的数字是不同位的，并且an也是递增的。所以，设d最高的二进制有n位那么a数列的长度不超过n，对于相同位数的数我们最多只能选择一个

那么就是一个分组背包问题dp[i][j]表示考虑到前i组，选了其中j组的方案数。

cnt[i]表示第i组有多少个

dp[i][j] += dp[i-1][j-1]*cnt[i] 考虑要第i组

dp[i][j] += dp[i-1][j] 考虑不要第i组

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i, n) for(int i = 0; i < n; ++i)
#define for1(i, n) for(int i = 1; i <= n; ++i)
#define IO ios::sync_with_stdio(false);cin.tie(0)

const int inf = 2e9; 
const ll INF = 8e18;

ll dp[35], num[35];

int main() {
    IO;
    //freopen("in.txt", "r", stdin);
    int t; cin >> t; while(t--) {
        memset(dp, 0, sizeof(dp));
        memset(num, 0, sizeof(num));
        ll d, m; cin >> d >> m;
        int lim = 0, cnt = 1;
        while(1) {
            if(d <= cnt) break;
            d -= cnt;
            num[++lim] = cnt;
            cnt <<= 1;
        }
        num[++lim] = d;
        dp[0] = 1;
        for(int i = 1; i <= lim; ++i) {
            for(int j = i; j >= 1; --j) {
                dp[j] = dp[j - 1] * num[i] + dp[j];
                dp[j] %= m;
            }
        }   
        ll ans = 0;
        for1(i, lim) ans += dp[i];
        ans %= m;
        cout << ans << '\n';
    }
    return 0;
}