CSP-S2考前综合强化刷题（第三场）
昨天挂10,今天挂20QAQ
A
1e6!全部写出来五十万位的数/se
高精度期望80pts
做法一:
会发现我们只需要比较大小
那么我们可以用个能够比较大小的映射函数
开根号显然我们还要算好几百位的数
比如对数函数!
logN!=log1+log2+log3....+log(n)
也就是说我们1e6个数全部求一个阶乘然后搞一个前缀和数组,这个和的第i项就是n!取对数
然后只需要枚举一个k,看与的大小关系
做法二:
结论 : 左边的阶乘不会大于右边的阶乘倍
显然如果大于我们就可以把左边的一个分给右边并保证仍成立
所以可以记录左边的倍数比右边打多少
code:
#include<bits/stdc++.h>
#define db double
#define ll long long
using namespace std;
const int MAXN = 2e6 + 7;
db f[MAXN];
ll g[MAXN];
int n;
int main() {
scanf("%d", &n);
if(n == 1) {
return puts("1"), 0;
}
if(n == 2) {
return puts("2"), 0;
}
if(n == 3) {
return puts("3"), 0;
}
f[3] = 6;
g[3] = 3;//前三个,初始化一下
for(ll i = 4; i <= n; ++i) {
f[i] = f[i - 1];
g[i] = g[i - 1];
while(f[i] / i < 1 && g[i] < i) {
++g[i];
f[i] = f[i] * g[i] * g[i];
}
f[i] /= i;
}
printf("%lld\n", g[n]);
return 0;
}
扩展:组合数问题
首先杨辉三角最下面一行的中间是最大的,而且次大的一定在最大的相邻位置
所以这k个数我们只需要用一个大根堆比较然后依次选下去就好了
然后我们从大根堆取k次就是前k大的组合数
显然比较大小不能取模,我们可以对其取对数
然后
B
先处理字符串,把整个拓扑图建出来
然后n^2去pick每个即可...
模拟建图处理字符串的时候可以分阶段来搞...然后有一个:;就换阶段,这样比较好写
注意把所有字符串按照字典序pick出来然后分配下点的编号
写模拟一定要代码优美一些
全考场切的最快?
code:
//考虑按照依赖关系建图
//会发现是一个拓扑排序
//然后我们有一些时间轴,每个时间轴都可以向后推进
//然后时间轴要任务的时候我们可以把所有点按照深度和名字进行排序
//然后就可以做了?
//名字字符集为小写大写数字,要是不是就撕了zhx
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 7;
const int MAXM = 3e5 + 7;
#define ll long long
string s, a, b;
map<string, int> mp;
int T, ccnt, home[MAXN], nxt[MAXM], to[MAXM], in[MAXN];
priority_queue<string, vector<string>, greater<string> > hp;
priority_queue<int, vector<int>, greater<int> > heap;
int vis[MAXN], tim[MAXN], Sm;
struct NODE {
int id, ft;
bool operator<(const NODE x)const {
return ft == x.ft ? id > x.id : ft > x.ft;
}
} e[MAXN];
priority_queue<NODE> task;
inline void ct(int x, int y) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
in[y]++;
}
int main() {
freopen("test.in", "r", stdin);
cin >> s;
int flg = 0;
//正在进行第几个阶段?
//任务的名字为第二关键字??
for(int i = 0; i < (int)s.size(); ++i) {
if(s[i] == '/') {
hp.push(a);
a.clear();
flg = -1;
continue;
}
if(s[i] == ';') {
hp.push(a);
a.clear();
flg = 0;
continue;
}
if(s[i] == ':') {
flg = 1;
continue;
}
if(!flg) {
a.push_back(s[i]);
}
}
a.clear();
while(!hp.empty()) {
a = hp.top();
hp.pop();
cout << a << endl;
mp[a] = ++T;
}
a.clear();
flg = 0;
for(int i = 0; i < (int)s.size(); ++i) {
if(s[i] == ';') {
flg = 0;
a.clear();
continue;
}
if(s[i] == ':') {
flg++;
continue;
}
if(s[i] == '/') {//上四挡
flg = 4;
continue;
}
if(!flg) {
a.push_back(s[i]);
} else if(flg == 1) {
if(s[i] == '[') {
continue;
}
if(s[i] == ',' || s[i] == ']') {
if(b.empty())continue;
ct(mp[b], mp[a]);
b.clear();
continue;
}
b.push_back(s[i]);
} else if(flg == 2) {
tim[mp[a]] = tim[mp[a]] * 10 + s[i] - '0';
cout << a << endl;
//快读即可
}
if(flg == 4) {
Sm = Sm * 10 + s[i] - '0';
if(Sm > T)break;
}
}
for(int i = 1; i <= T; ++i)e[i].id = i;
//有多少任务就有多少点
int fed = 0;
while(fed < Sm) {
++fed;
heap.push(0);
//每个机器最早结束时间
}
fed = 0;
while(fed < T) {
for(int i = 1; i <= T; ++i) {
if(in[i] == 0 && !vis[i]) {
vis[i] = 1;
task.push(e[i]);
//把这个点放入qwq里
}
}
int t = heap.top();
heap.pop();
NODE u = task.top();
task.pop();
for(int i = home[u.id]; i; i = nxt[i]) {
int v = to[i];
e[v].ft = max(e[v].ft, tim[u.id] + max(t, u.ft));
//考虑我们这个任务结束的时间应该是这个任务开始做的时间+做这个任务的时间
//前者显然和机器开工时间与开始做时间最大值有关
in[v]--;
}
fed++;
heap.push(max(t, u.ft) + tim[u.id]);
}
int ans = 0;
while(!heap.empty()) {
ans = max(ans, heap.top());
heap.pop();
}
printf("%d\n", ans);
return 0;
}
/*
abc:[a1,a2]:10;AB1:[]:2;AB2:[]:3;ab1:[AB1,AB2]:3;ab3:[AB2]:4;a2:[ab1,ab3,AB2]:2;a1:[ab1]:3/3
*/
C
挂了20QAQAQAQ
对于长度为1,我们可以直接暴力
对于长度<=10,我们可以直接复制粘贴到一样长
考场上直接TLE/ll
注意50!整除任何你想要的,所以不用考虑余数
均为质数
3,5的情况?
010010010010010
100111001110011
->
110121011120021
你会发现第一个串会和第二个字符串每一位都有重叠的操作!!
那么其实相当于(2个0+1个1)*(2个0+3个1)=4个0+8个1+3个2??
因为一定会有重复!
生成函数??
当两字符串互质时,我们只关心彼此间0/1的个数!
然后我们最后相当于多个二项式相乘!!
...可以分治FFT优化
然鹅,如果不互质就萎了
分块匹配!!!
lcm 4,6 =12
4 4 4 4-> 1 2 1 2 1 2
6 6 -> 1 2 3 1 2 3
设最大公因数为g
10 01 10 01 10 01
01 00 11 01 00 11
你会发现4的每一块的第一位都不可能和6的第二位产生影响
然后我们可以继续,取出4的第二位和六的每一块的第二位乘起来
然后得到两个多项式系数求和?
这两个答案求和就是我们想要的答案,可以发现多项式的指数可能变小?
扩展到n个?你会发现我们要小心gcd!QAQ
如果一个字符串含有2,3,5,7,作为因子那么我们就把它扩展到322725*49的形式
但是如果包含了大于7的因子,他的平方一定大于50,所以只会包括一个大于7的
怎么扩?
每个p拓展到12p,因为我们最大只能有4
这样做完之后,我们最大公约数为12(或者更大一个p)
所有数我们可以按照12进行分组,然后做12次多项式乘法就好了
然后会发现我们可以做了!
每组有12位,要做12次乘法
然后一共有n/12组
每组的第一个数之间做多项式乘法
复杂度瓶颈在于扩展1e6的....
打码通过精加工变得好快/jk
code:
//From Dawn light
//first kill!
//orzzhx
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1000;
const int MAXT = 105;
const int MAXS = 55;
const int P = 1e9 + 7;
int n, la, lc;
string s[MAXT];
ll fac[MAXT];
int L[MAXT], a[MAXT][MAXS], vis[MAXN], B[50][MAXN];
ll A[MAXN];
ll D[MAXN], E[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 add(ll &x, ll y) {
x += y;
if(x >= P)x -= P;
}
ll c[MAXN];
inline void mul(ll *a, ll *b, int &la, int lb) {
memset(c, 0, sizeof(c));
for(int i = 0; i < lb; ++i) {
for(int j = 0; j < la; ++j) {
add(c[i + j], b[i] * a[j] % P);
}
}
la = la + lb - 1;
for(int i = 0; i < la; ++i)a[i] = c[i];
return ;
}
const int Bas = 1058400;
int C[Bas + 3];
inline void init() {
fac[0] = 1;
for(int i = 1; i <= 50; ++i)fac[i] = fac[i - 1] * i % P;
for(int i = 1; i <= n; ++i) {
L[i] = s[i].size();
for(int k = 0; k < L[i]; ++k)a[i][k] = s[i][k] - '0';
int tmp = L[i];
while(tmp % 2 == 0)tmp /= 2;
while(tmp % 3 == 0)tmp /= 3;
while(tmp % 5 == 0)tmp /= 5;
while(tmp % 7 == 0)tmp /= 7;
if(tmp == 1) {
vis[0] = 1;
for(int k = 0; k < Bas; ++k)C[k]+=a[i][k % L[i]];
} else {
int tl = tmp * 12;
vis[tmp] = 1;
for(int k = 0; k < tl; ++k)B[tmp][k]+= a[i][k % L[i]];
}
}
bool flg = vis[0];
for(int t = 0; t < 12; ++t) {
la = 0;vis[0] &= flg;memset(A, 0, sizeof(A));
for(int k = t; k < Bas; k += 12) {A[C[k]]++;la = max(la, C[k] + 1);}
for(int i = 1; i <= 50; ++i) {
if(!vis[i]) continue;
memset(E, 0, sizeof(E));
lc = 0;
for(int k = t; k < i * 12; k += 12) {E[B[i][k]]++;lc = max(lc, B[i][k] + 1);}
if(!vis[0]) {vis[0] = 1; la = lc; for(int k = 0; k < lc; ++k)A[k] = E[k]; continue;}
mul(A, E, la, lc);
}
for(int k = 0; k < la; ++k)add(D[k], A[k]);
}
vis[0] &= flg;
return ;
}
inline bool cmp(const string x, const string y) {
return x.size() < y.size();
}
signed main() {
scanf("%lld", &n);
for(int i = 1; i <= n; ++i)cin >> s[i];
sort(s + 1, s + n + 1, cmp);
init();
int qwq = fac[50];
if(vis[0])qwq = qwq * ksm(Bas, P - 2) % P; else qwq = qwq * ksm(12, P - 2) % P;
for(int i = 1; i <= 50; ++i)if(vis[i])qwq = qwq * ksm(i, P - 2) % P;
for(int i = 0; i <= n; ++i)printf("%lld\n", 1ll * D[i] * qwq % P);
return 0;
}
D
显然我们可以枚举中间的那个j,然后计算左右两边的贡献,就是左边那些大于他的和右边那些大于他的都可以拼起来
然后你会发现我们这个贡献好像就是就是有多少区间包括他
做完了,树状数组维护即可
注意翻转值域的时候不要出现0
code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 5e5 + 7;
const int P = 1e9 + 7;
int n, a[MAXN];
ll ans;
struct rec {
#define lowbit(x) (x&(-x))
ll tr[MAXN];
inline void add(int x, ll V) {
for(; x <= n; x += lowbit(x))tr[x] += V;
}
inline ll qry(int x) {
ll ret = 0;
for(; x; x -= lowbit(x))ret += tr[x];
return ret;
}
} bt1, bt2;
inline void add(ll &x, ll y) {
x += y;
if(x >= P)x -= P;
}
int main() {
scanf("%d", &n);
int M = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
M = max(M, a[i]);
}
++M;
for(int i = 1; i <= n; ++i) {
bt1.add(M - a[i], n - i + 1);
}
for(int i = 1; i <= n; ++i) {
bt1.add(M - a[i], -n + i - 1);
add(ans, bt1.qry(M - a[i] - 1) * bt2.qry(M - a[i] - 1) % P);
bt2.add(M - a[i], i);
}
printf("%lld\n", ans);
return 0;
}