Comet OJ - 模拟赛测试 Day2

感觉题目出得不是很难,部分分给得很足

# A - 收拾房间 reorder

std::merge() 秒过

# B - 天天背单词 prefix

长度总和 N=106N=10^6

我都不敢用 sort

God Song 教育我用 suffix array,我不会

假设单词总数为 nn

字符串比较的复杂度为 min(s1,s2)\min(|s_1|,|s_2|)

那么快速排序的复杂度就是 nlognNn=Nlognn\log n \cdot \frac{N}{n}=N\log n

不知道这个分析是不是假的

因为不存在某个单词是另一个单词的前缀

就可以用 hash 把单词转成一个序列

就成为了简单题

# C - 养盆栽 monotony

r,c20r,c\le20 肯定是状压,考虑状态的设计

基本思想是暴力列,DP 行

暴力枚举 stst,为保留哪些列

暴力枚举 ss,为哪些列是单调递增

ssts\subseteq st 枚举复杂度为 3c3^c

定义 f(s,i)f(s,i) 为以第 ii 行结束,并且至少有两行,列状态为 ss 的切割方案数

f(s,i)=j<if(s,j) f(s,i)=\sum_{j<i} f(s,j)

如上转移即可得到答案,但复杂度过高

实际上,ss 的状态可由两行决定,也就是说其取值方案在 r2r^2 级别

于是只需要枚举 ststss 状态的确定和 DP 转移合在一起为 r2r^2

故复杂度为 2cr22^cr^2

# Code

A

#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;

// #define DEBUG 1 //调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
inline char gc() {
#if DEBUG //调试,可显示字符
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? -1 : *p1++;
}
inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
template <class T>
inline void read(T &x) {
register double tmp = 1;
register bool sign = 0;
x = 0;
register char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc()) tmp /= 10.0, x += tmp * (ch - '0');
if (sign) x = -x;
}
inline void read(char *s) {
register char ch = gc();
for (; blank(ch); ch = gc())
;
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}
inline void read(char &c) {
for (c = gc(); blank(c); c = gc())
;
}
inline void push(const char &c) {
#if DEBUG //调试,可显示字符
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <class T>
inline void write(T x) {
if (x < 0) x = -x, push('-'); // 负数输出
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
inline void write(const char *s) {
while (*s != '\0') push(*(s++));
}
template <class T>
inline void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;

const int N = 1e5+10;

int a[N], b[N], res[N], exi[N];

int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#endif
int n, m; io.read(n), io.read(m);
rep(i, 1, m){
io.read(a[i]);
exi[a[i]] = 1;
}
int pt = 0;
rep(i, 1, n) if (exi[i] == 0) b[++pt] = i;
std::merge(a+1, a+1+m, b+1, b+1+pt, res+1);
rep(i, 1, n) io.write(res[i], '\n');
return 0;
}

B

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull;
using std::make_pair; using std::pair; typedef pair<int, int> pii; typedef pair<int, ll> pil; typedef pair<ll, ll> pll;
const int N = 1e6+10, p = 1e9+7, base = 29, mod1=998244353, mod2=1e9+7;
ll fac[N], invf[N];

ll ksm(ll a, int n){
ll ret = 1;
while(n){
if (n&1) (ret*=a)%=p;
n>>=1; (a*=a)%=p;
}
return ret;
}

void init(){
fac[0] = 1;
rep(i, 1, 1000000) fac[i] = fac[i-1] * i % p;
invf[1000000] = ksm(fac[1000000], p-2);
per(i, 999999, 0) invf[i] = invf[i+1]*(i+1)%p;
}

std::string s, a[N];
ll A(int n, int k){ return fac[n]*invf[n-k]%p; }
std::map<pll, int> order;
#define lowbit(i) (i&(-i))
int c[N];
void add(int i, int x){ for(; i<=1000000; i+=lowbit(i)) c[i] += x; }
int ask(int i){int ret = 0; for(; i > 0; i-=lowbit(i)) ret += c[i]; return ret; }

int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#endif
std::ios::sync_with_stdio(0); cout.tie(0);
init();
int n, K; cin >> n >> K;
rep(i, 1, n) cin >> a[i];
std::sort(a+1, a+1+n);
rep(i, 1, n){
ll ret1 = 0, ret2 = 0;
for(int j = 0; j < a[i].size(); ++j){
(ret1 = ret1*base+a[i][j]-'a'+1) %= mod1;
(ret2 = ret2*base+a[i][j]-'a'+1) %= mod2;
}
order[pll(ret1, ret2)] = i;
}
cin >> s;
ll ret = 0, ret1 = 0, ret2 = 0; int cnt = 0;
for(int i = 0; i < s.size(); ++i){
(ret1 = ret1*base+s[i]-'a'+1) %= mod1;
(ret2 = ret2*base+s[i]-'a'+1) %= mod2;
if (order.count(pll(ret1, ret2))){
++cnt; int rk = order[pll(ret1, ret2)];
add(rk, 1);
(ret += (rk-ask(rk))*A(n-cnt, K-cnt)%p ) %= p;
ret1 = ret2 = 0;
}
}
ret = (ret+1)%p;
cout << ret << endl;
return 0;
}

C

#include <iostream>
#include <cstring>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull;

const int R = 20;

int a[R][R], f[1<<R][R], s_all[R][R], valid[R];

int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#endif
std::ios::sync_with_stdio(0); cout.tie(0);
int r, c; cin >> r >> c;
rep(i, 0, r-1) rep(j, 0, c-1) cin >> a[i][j];
ll ret = 0;
rep(i, 1, r-1){
rep(j, 0, i-1){
int s = 0;
rep(k, 0, c-1) if (a[i][k] > a[j][k]) s |= (1<<k);
s_all[j][i] = s;
}
}
for(int chs = 1; chs < (1<<c); ++chs){
rep(i, 0, r-1){
++ret; valid[i] = 1;
int ll = -1, l = -1;
rep(j, 0, c-1){
if((1<<j)&chs){
if ( ll != -1 && !( (ll<l&&l<a[i][j]) || (ll>l&&l>a[i][j]) ) )
{ --ret; valid[i] = 0; break; }
ll = l, l = a[i][j];
}
}
}
rep(i, 1, r-1){
if (!valid[i]) continue;
rep(j, i+1, r-1) if (valid[j]) f[chs&s_all[i][j]][i] = 0;
rep(j, 0, i-1){
if (!valid[j]) continue;
int s = (chs&s_all[j][i]);
f[s][i] += f[s][j] + 1;
ret += f[s][j]+1;
}
}
}
cout << ret << endl;
return 0;
}