qbxt D4 && NOIP提高组考前刷题冲刺班（第四场）
A
模拟即可,用struct和map优化
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e4 + 7;
int n;
char s[MAXN];
string t;
map<string, int> mp;
int tot;
struct rec {
string r;
ll v;
int kd;
} a[MAXN];
inline void output(int x) {
if(a[x].kd == 1) {
printf("%lld\n", a[x].v);
} else cout << a[x].r << '\n';
return ;
}
inline int getid(string s) {
if(mp.find(s) != mp.end())return mp[s];
mp[s] = ++tot;
return mp[s];
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%s", s);
t.clear();
int m = strlen(s);
int kd = 0;
for(int i = 0; i < m; ++i) {
if(s[i] == '+') {
kd = i;
break;
}
if(s[i] == '=') {
kd = -i;
break;
}
}
if(kd == 0) {
for(int i = 0; i < m; ++i)t.push_back(s[i]);
if(mp.find(t) != mp.end()) {
int id = mp[t];
output(id);
} else puts("no");
} else if(kd < 0) {
kd = -kd;
for(int i = 0; i < kd; ++i)t.push_back(s[i]);
bool qwq = 0;
for(int i = kd + 1; i < m; ++i)if(s[i] == '"') {
qwq = 1;
break;
}
//是字符串类型,我们自闭
if(qwq) {
string tmp;
tmp.clear();
for(int i = kd + 1; i < m; ++i) {
if(isalpha(s[i]) || isdigit(s[i])) {
tmp.push_back(s[i]);
}
}
int id = getid(t);
a[id].r = tmp;
a[id].kd = 2;
} else {
ll tmp = 0;
for(int i = kd + 1; i < m; ++i) {
if(isdigit(s[i])) {
tmp = tmp * 10 + s[i] - '0';
}
}
int id = getid(t);
a[id].v = tmp;
a[id].kd = 1;
}
} else {
for(int i = 0; i < kd; ++i)t.push_back(s[i]);
bool qwq = 0;
++kd;
for(int i = kd + 1; i < m; ++i)if(s[i] == '"') {
qwq = 1;
break;
}
if(mp.find(t) != mp.end()) {
int id = mp[t];
if(qwq) {//字符串加!
if(a[id].kd == 1)continue;
string tmp;
tmp.clear();
for(int i = kd + 1; i < m; ++i) {
if(isalpha(s[i]) || isdigit(s[i])) {
tmp.push_back(s[i]);
}
}
a[id].r += tmp;
} else {//数字加!
if(a[id].kd == 1) {
ll tmp = 0;
for(int i = kd + 1; i < m; ++i) {
if(isdigit(s[i])) {
tmp = tmp * 10 + s[i] - '0';
}
}
a[id].v += tmp;
} else {
string tmp;
tmp.clear();
for(int i = kd + 1; i < m; ++i) {
if(isdigit(s[i])) {
tmp.push_back(s[i]);
}
}
a[id].r += tmp;
}
}
}
}
}
return 0;
}
B
最难的一题(doge)
首先对于一个字符串有用的只有一个:每个字符数量
那么我们首先可以枚举Alice和Bob选择的字符串是哪两个
然后我们想知道Alice选择的字符串能否用一种字典序打爆所有其他字符串
首先,我们确定的字符集第一个字符,一定要满足数量大于等于所有的其他串!
然后你会发现,这样满足的字符其实有很多个
先放a再放b,和先放b再放a是一样的
因为我们都是先把a比第i个字符串小的剃掉,再把b比第i个字符串小的剃掉
那么我们会发现这个本质是相同的
也就是说,无论这些字符以什么顺序去填本质都是相同的!
先枚举一个i从1~26,表示我们字典集第i位
然后再去枚举一个k去尝试填他
把所有剩下的还没有被删掉的暴力出现小于k的删除
即可
如果长度不同,还要特判每个字符是否是当且字符串最后一个
等等被唐爷爷卡了
aab
aabb,先a后b,先b后a本质不同.....
然后么得了/..真被卡了......
code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 7;
//虽然我觉得跑不过去
//但是我比较牛逼
int n;
char s[MAXN];
struct rec {
int b[30];
} a[MAXN];
int ed;
//考虑一个字符串能成为老大哥
//当且仅当他按照自己最优势(最多的)的排完序后
//比所有其他字符串的字典序都小
//也就是说暴力比较即可
//但是还有一种情况
//就是说如果我有的你没有,还是老子赢
//因为我可以把它放到开头然后直接胜利
//另外就是他字符集大于等于老子
//这个很好看,就是我的字符比到最后一步也一定要比他少
//不行萎了萎了
//喵喵喵
int que[MAXN], tmp[MAXN], vis[MAXN];
inline int chk(int x) {
int tl = 0;
for(int i = 1; i <= n; ++i)if(i != x)que[++tl] = i;
for(int i = 0; i < 26; ++i)vis[i] = 0;
for(int k = 0; k < 26; ++k) {//排名第一???
int rc = -1;
int mcnt = 0;
for(int j = 0; j < 26; ++j) {//n^2*26^2,随便过
if(!vis[j] && a[x].b[j]) {//我要有才行...
bool flg = 1;
int cnt = 0;
for(int i = 1; i <= tl; ++i) {
int u = que[i];
if(a[u].b[j] < a[x].b[j]) {
cnt++;
}
if(a[u].b[j] > a[x].b[j]) {
flg = 0;
break;
}
}
if(flg) {
if(cnt > mcnt) {
mcnt = cnt;
rc = j;
}
}
}
}
if(rc < 0)break;
vis[rc] = 1;
int hd = 0;
for(int i = 1; i <= tl; ++i) {
int u = que[i];
if(a[u].b[rc] == a[x].b[rc]) {//相同!!
tmp[++hd] = u;
}
}
tl = hd;
if(tl == 0)return 1;
for(int i = 1; i <= tl; ++i)que[i] = tmp[i];
}
return 0;
}
int main() {
freopen("T2.in", "r", stdin);
freopen("T2.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%s", s);
int m = strlen(s);
for(int k = 0; k < m; ++k)a[i].b[s[k] - 'a']++;
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
ans += chk(i); //qieke
}
printf("%d\n", ans);
return 0;
}
C
首先我们要找出所有的区间?然后计算每个位置的贡献?
那要算出有多少个区间包括某个点
可以发现,我们能够尺取这个区间
因为随着区间变长,逆序对数单调不减
就是说,对于每一个r
那么我们找到最大的那个l,[1~l,r]这些区间都满足条件
可以用一个二度差分实现一个前缀区间都满足的加
然后在右端点+1处再打一个-L的标记
这样我们求一个二次前缀和和一个一次前缀和,就能知道一个位置被匹配多少次
然后就能算每个位置的贡献,从而得到答案!
还有一个版,问有多少区间相交
唐爷爷:点减边容斥
就是每个点被覆盖的贡献-每条边被覆盖的贡献
当然可以做补集转换,就是说考虑有多少不相交的区间
那可以枚举一个最大的左端点,然后看小于这个左端点的右端点有多少个即可
code:
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&(-x))
using namespace std;
const int MAXN = 4e6 + 7;
const int P = 1e9 + 7;
const int inv2 = (P + 1) / 2;
int n, a[MAXN];
namespace fastIO {
#define BUF_SIZE (1<<20)
static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
inline char nc() {
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
}
return *p1++;
}
inline int read() {
int x = 0;
char s = nc();
for(; !isdigit(s); s = nc());
for(; isdigit(s); s = nc())x = (x << 3) + (x << 1) + s - '0';
return x;
}
}
using namespace fastIO;
struct BIT {
int tr[MAXN];
inline void add(int x, int V) {
for(; x <= n; x += lowbit(x))tr[x] += V;
}
inline int qry(int x) {
ll ret = 0;
for(; x; x -= lowbit(x))ret += tr[x];
return ret;
}
} tr;
ll Ni, cf[MAXN], cf2[MAXN], K;
inline void add3(int L, int R, int x) {
ll ret = R - L - tr.qry(x);//有多少比他小的,就是比他大的
Ni += ret;
tr.add(x, 1);
return;
}
inline void pop(int x) {
tr.add(x, -1);
int ret = tr.qry(x - 1);
Ni -= ret;
return ;
}
inline void add2(int x) {
Ni += tr.qry(x - 1);
tr.add(x, 1);
return ;
}
int main() {
// freopen("test.in", "r", stdin);
n = read();
K = read();
for(int i = 1; i <= n; ++i)a[i] = read();
int L = 1;
for(int R = 1; R <= n; ++R) {
add3(L, R, a[R]);
while(L <= R && Ni >= K) {
pop(a[L]);
if(Ni < K) {
add2(a[L]);
break;//说明这个是极限了
}
++L;
}
//相当于所有左端点到这的区间都qwq了
if(Ni >= K) {
cf2[1]++;
cf2[L + 1]--;
cf[R + 1] -= L; //左端点在这取的所有终结
}
}
for(int i = 1; i <= n; ++i) {
cf2[i] += cf2[i - 1];
}
for(int i = 1; i <= n; ++i) {
cf[i] += cf[i - 1];
}
for(int i = 1; i <= n; ++i) {
cf2[i] += cf2[i - 1];
}
for(int i = 1; i <= n; ++i)cf[i] += cf2[i], cf[i] %= P;
//前缀和!!!!!!!!!
ll ans = 0;
for(int i = 1; i <= n; ++i) {
ans = (ans + (1ll * cf[i] * (cf[i] - 1) % P * inv2 % P)) % P;
}
printf("%lld\n", ans);
return 0;
}
/*
6
abbcc
aabbc
abbbc
aaabc
aabcc
abccc
*/
D
计数题...
std:
可以发现,如果只有一个根的时候我们可以拓扑序树上dp一下
然后我们再考虑有两个根,会发现他们之间的路径拿出来,其中删除点的方案一定是这个路径的一个区间
那么我们就能设计表示这个路径的都被删除的方案数
然后转移就是考虑l+1和r-1
方法就是这一段的siz和和那一个子树的siz求个组合数,然后乘上他内部自由分配的方案数
my:
暴力出奇迹
考虑一个树的拓扑序为
然后我们只需要考虑这个链上第一个被删掉的是哪个,后面都是本质不同的了
会发现我们断掉一条边可以把树分成两个连通块,然后就有了这两个点先被删掉方案
再每个相邻的做一下即可
代码如下
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 7;
const int P = 1e9 + 7;
int home[MAXN], nxt[MAXN], to[MAXN], ccnt, n, p1, p2;
int vis[MAXN];
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline void ct(int x, int y) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
}
ll fac[MAXN], ifac[MAXN], ans1, inv[MAXN], ans;
inline void init() {
fac[0] = 1;
ifac[0] = 1;
for(int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % P;
}
ifac[n] = ksm(fac[n], P - 2);
for(int i = n - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
for(int i = 1; i <= n; ++i)inv[i] = ifac[i] * fac[i - 1] % P;
return ;
}
//尺取,一次跳两个点!!
//随便选取一个点开始即可
//O(n) chk 应该不会qaq吧??
int fa[MAXN], q[MAXN], tot;
bool flg = 1;
inline void dfs1(int u, int F) {
if(u == p2) {
int x = u;
while(x != p1) {
q[++tot] = x;
x = fa[x];
}
q[++tot] = x;
flg = 0;
return ;
}
if(!flg)return ;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F)continue;
fa[v] = u;
dfs1(v, u);
}
return ;
}
int siz[MAXN];
inline void dfs2(int u, int F) {
siz[u] = 1;
for(int i = home[u]; i; i = nxt[i]) {
if(vis[i])continue;
int v = to[i];
if(v == F)continue;
dfs2(v, u);
siz[u] += siz[v];
}
ans1 = ans1 * inv[siz[u]] % P;
}
inline ll C(int x, int y) {
return fac[x] * ifac[y] % P * ifac[x - y] % P;
}
inline void solve() {
dfs1(p1, 0);
//关键是我们要找个边...QAQ
//好吧...其实可以神秘法找边
int rc = 0;
for(int i = 1; i <= tot; i += 2) {
int u = q[i];
int x = q[i + 1];//你没了!
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == x) {
rc = i;
vis[rc] = vis[rc ^ 1] = 1;
break;
}
}
ans1 = 1;
if(x != 0)dfs2(p1, 0);
dfs2(p2, 0);//不访问标记
if(x != 0)ans1 = ans1 * fac[siz[p1]] % P * fac[siz[p2]] % P;
else ans1 = ans1 * fac[siz[p2]] % P;
ans = (ans + ans1 * C(n, siz[p2]) % P) % P;
vis[rc] = vis[rc ^ 1] = 0;
}
printf("%lld\n", ans);
}
inline void solve2() {
ans1 = 1;
dfs2(p1, 0);
ans1 = ans1 * fac[siz[p1]] % P;
printf("%lld\n", ans1);
return ;
}
int main() {
// freopen("test4.in", "r", stdin);
// freopen("test4.out", "w", stdout);
scanf("%d%d%d", &n, &p1, &p2);
init();//预处理阶乘
ccnt = 1;
for(int i = 2, x, y; i <= n; ++i) {
scanf("%d%d", &x, &y);
ct(x, y);
ct(y, x);
}
if(p1 != p2) {
solve();
} else {
solve2();
}
return 0;
}
口胡T1
一个矩阵,问是否存在子矩阵和在[k,2k]之间
都是正数
大于k的数都是没意义的,一个能让游戏直接结束,一个能全不选
所以说我们只需要枚举剩下点的最大值
假如这个最大值大于2k
因为我们扣去一行,如果剩下的第一次小于k,那么另一侧一定满足
考虑悬线,找到这个最大矩阵
口胡T2_pre
图上随机游走
高斯消元
口胡T2_niubi
一个01序列,问把这个序列改成全0/全1的期望代价
操作方式是一个指针只在开始位置,然后随机跳到位置j,然后代价为
2^s然后高消显然是不行的
根据期望的线性性,我们只需要计算每一个经过期望次数
我们压压状态,会发现只和指针所在位置以及其他位置0/1态有关
表示位置i是否等于位置j,当前指针是否在i,以及其他n-2个位置有多少个和i相同
转移分指针在不在i,从i走到哪里转移
高斯消元即可
然后我们最后枚举两个位置,利用这个期望次数拼起来即可
时间复杂度相当低.....n可以做150??