srm 545

发表于   |   分类于   |  

275

Description

让你构造一个长度为$n$的串，逆序数恰好为$m$且字典序比某字符串$string$大，请构造字典序最小的这样的串。

Solution

数据范围非常小，暴力搜索即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int M = 26;
string ans;
struct StrIIRec {
    string dfs(int n, int minInv, string minStr, set<char> S) {
        if (minInv > (n - 1) * n / 2)   return "";
        if (n == 1) return string(1, *S.begin());
        int cnt = 0;
        if (!minStr.size()) minStr = "a";
        for (set<char>:: iterator it = S.begin(); it != S.end(); it++) {
            if (*it >= minStr[0]) {
                set<char> f = S;
                f.erase(*it);
                string t;
                if (*it == minStr[0])   t = dfs(n - 1, minInv - cnt, string(minStr, 1), f);
                else t = dfs(n - 1, minInv - cnt, "", f);
                if (t.size())   return *it + t;
            }
            ++cnt;
        }
        return "";
    }
    string recovstr(int n, int minInv, string minStr) {
        set<char> S;
        for (int i = 0; i < 26; ++i)    S.insert('a' + i);
        string ans = dfs(n, minInv, minStr, S);
        return ans;
    }
};

500

Description

你可以在$H\times L$的网格上以$(x,0)$为起点画一条非水平的射线，$0\le x\le L$，且为整数。在这个射线上每次要取$k$个整数坐标。问一共可以取得多少个不同的坐标集合$(1\le H,L,K\le 2000)。$

Solution

暴力枚举$dx, dy$，当$gcd(dx,dy)=1$的时候这个就相当于枚举斜率啦，然后我们需要枚举$x$,显然枚举会超时，我们考虑只有当$x+=dx,y+=dy$的时候，点数才可能会发生变化，枚举即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 2005, M = 1e9 + 7;
int c[N][N];
struct Spacetsk {
    int countsets(int L, int H, int K) {
        if (K == 1) return (H + 1) * (L + 1) % M;
        c[0][0] = 1;
        for (int i = 1; i <= 2001; ++i) {
            c[i][0] = 1;
            for (int j = 1; j <= i; ++j)    c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
        }
        int ans = 0;
        for (int i = 0; i <= L; ++i)    (ans += c[H + 1][K]) %= M;
        for (int dx = 1; dx <= L; ++dx)
             for (int dy = 1; dy <= H; ++dy) {
                if (__gcd(dx, dy) == 1) {
                    int sum = 0, cnt = 0;
                    for (int x = 0, y = 0; x <= L; x += dx, y += dy) {
                        if (y <= H) ++cnt;  
                        int num = min(dx, L - x + 1);
                        (sum += 1ll * num * c[cnt][K] % M) %= M;
                    }
                    (ans += sum * 2 % M) %= M;
                }
             }
        return ans;
    }
};