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;
}
};