杭电多校第二场
1005-Everything Is Generated In Equal Probability[期望递推]
如果猜的话就是：\((n^2-1)/9\)
暴力跑一下得到样例是怎么出来的 然后猜测一下…….
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
const ll night=443664157;
int main() {
ll n;
while(cin>>n){
cout<<(n*n%mod-1+mod)%mod*night%mod<<endl;
}
return 0;
}
让我们来探讨一下正解．
一般做期望的题思路要清晰，要算某个可以算的期望然后获得对答案的贡献．本题最里层的问题就是求逆序对的期望．那每一个点对\((x,y)\)都有\(\frac{1}{2}\)的概率有贡献．易得一个长为\(n\)的序列逆序对的期望为\(\frac {C_{n}^{2}}{2}\)
一个长为\(i\)的序列的子序列有\(2^i\)个
每个子序列的概率为\(\frac {1}{2^i}\)
长度为\(j\)的子序列的个数为\(C_{i}^j\)
对本题而言，长度为\(i\)的长为\(i\)的子序列期望\(f(i)\)等于所有产生的子序列的期望加起来
\[f(i)=\frac {1}{2^i}\sum_{j=0}^{i}C_{i}^jf(j)+\frac {C_{n}^{2}}{2} \]
左右两边同乘以\(2^i\)
\[f(i)=\frac{1}{2^{i-1}}\sum_{j=0}^{i-1}C_{i}^jf(j)+ {C_{n}^{2}}2^{i-1} \]
就得到一个递推式子 \(O(n^2)\)处理一下
1008-Harmonious Army[最小割建模]
可以看一下2016年国家集训队论文“网络流的一些建模方法”
这题应该从最小割角度建模
把每条边当做有权边 求最小的边集让S与T不连通
再用总边权减去最小割
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
const int maxm = 1e6 + 7;
#define ll long long
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct Dinic {
struct Edge {
int next, to;
ll f;
} e[maxm];
int head[maxn], dep[maxn], tol;
ll ans;
int cur[maxn];
int src, sink, n;
void add(int u, int v, ll f) {
tol++;
e[tol].to = v;
e[tol].next = head[u];
e[tol].f = f;
head[u] = tol;
tol++;
e[tol].to = u;
e[tol].next = head[v];
e[tol].f = 0;
head[v] = tol;
}
bool bfs() {
queue<int> q;
memset(dep, -1, sizeof(dep));
q.push(src);
dep[src] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
for (register int i = head[now]; i; i = e[i].next) {
if (dep[e[i].to] == -1 && e[i].f) {
dep[e[i].to] = dep[now] + 1;
if (e[i].to == sink) return true;
q.push(e[i].to);
}
}
}
return false;
}
ll dfs(int x, ll maxx) {
if (x == sink) return maxx;
for (register int &i = cur[x]; i; i = e[i].next) {
if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) {
ll flow = dfs(e[i].to, min(maxx, e[i].f));
if (flow) {
e[i].f -= flow;
e[i ^ 1].f += flow;
return flow;
}
}
}
return 0;
}
ll dinic(int s, int t) {
ans = 0;
this->src = s;
this->sink = t;
while (bfs()) {
for (register int i = 0; i <= n; i++)
cur[i] = head[i];
while (ll d = dfs(src, inf))
ans += d;
}
return ans;
}
void init(int n) {
this->n = n;
for(int i=0;i<=n;++i) head[i]=0;
tol = 1;
}
} G;
int main() {
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
ll u,v,a,b,c;
ll sum=0;
G.init(n+10);
int S=0,T=n+2;
for(int i=1;i<=m;++i){
scanf("%lld%lld%lld%lld%lld",&u,&v,&a,&b,&c);
sum+=(a+b+c);
G.add(S,u,a+b);
G.add(S,v,a+b);
G.add(u,T,b+c);
G.add(v,T,b+c);
G.add(u,v,a+c-b*2);
G.add(v,u,a+c-b*2);
}
printf("%lld\n",sum-G.dinic(S,T)/2);
}
return 0;
}
1009-I Love Palindrome String[回文树]
回文树的模板题
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 300005;
const int N = 26;
int ans[MAXN];
struct PAT {
struct node {
int len, num, fail, son[N];
} t[MAXN];
int x[MAXN];
short s[MAXN];
bool vis[MAXN];
int sum[MAXN];
int tot, last, n;
void init(int len) {
for (register int i = 0; i < len + 5; ++i) {
t[i].len = t[i].num = t[i].fail = 0;
for (register int j = 0; j < 26; ++j) t[i].son[j] = 0;
x[i] = vis[i] = 0;
sum[i] = 0;
}
tot = last = 1;
n = 0;
t[0].len = 0, t[1].len = -1;
t[0].fail = t[1].fail = 1;
s[0] = -1;
}
void add(int c) {
int p = last;
s[++n] = c;
while (s[n] != s[n - 1 - t[p].len])p = t[p].fail;//匹配找到第一个合法的最长后缀回文子串
if (!t[p].son[c]) {//如果没有新的本质不同的回文子串
int v = ++tot, k = t[p].fail;
while (s[n] != s[n - t[k].len - 1])k = t[k].fail;//获得新节点的fail
t[v].fail = t[k].son[c];
t[v].len = t[p].len + 2;
t[v].num = t[t[v].fail].num + 1;
t[p].son[c] = v;
}
last = t[p].son[c];
sum[last]++;//不同位置算不同的
}
void solve() {
for (register int i = tot; i >= 2; --i) {//从后往前
if (x[i] == 0) x[i] = i;
while (x[i] >= 2 && t[x[i]].len > (t[i].len + 1) / 2) {//沿着fail指针找
x[i] = t[x[i]].fail;
}
if (x[i] >= 2 && t[x[i]].len == (t[i].len + 1) / 2) {//若找到长度为其一半的回文子串的节点
vis[i] = 1;//说明这个字符串是满足题意的串
}
x[t[i].fail] = x[i];//优化,不需要重复找
sum[t[i].fail] += sum[i];//父亲累加儿子的sum，因为如果fail[v]=u，则u一定是v的子回文串！
if (vis[i]) ans[t[i].len] += sum[i];
}
}
} T;
char str[MAXN];
int main() {
int len;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin >> str) {
len = strlen(str);
T.init(len);
for (register int i = 1; i <= len; ++i) {
T.add(str[i-1] - 'a');
ans[i] = 0;
}
T.solve();
for (register int i = 1; i < len; ++i)cout << ans[i] << " ";
cout << ans[len] << endl;
}
return 0;
}
1010-Just Skip The Problem[签到]
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e6 + 3;
ll fac[mod];
int main() {
fac[0] = 1;
for (ll i = 1; i < mod; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
int n;
while (scanf("%d", &n) != EOF) {
if (n >= mod) {
puts("0");
} else {
printf("%lld\n", fac[n]);
}
}
return 0;
}
1011-Keen On Everything But Triangle[主席树+斐波那契数列性质]
知道正着来只需要44次就能得到三角形
反着来也要想到
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100005], n, m, copn;
vector<ll> v;
struct Node {
ll l, r, sum;
} node[100005 * 20];
ll tot = 0;
ll tree[100005];
ll getpos(ll x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
ll build(ll l, ll r) {
ll now = ++tot;
node[now].sum = 0;
if (l == r)
return now;
ll mid = (l + r) >> 1;
node[now].l = build(l, mid);
node[now].r = build(mid + 1, r);
return now;
}
ll update(ll last, ll pos) {
ll now = ++tot, ret = now;
node[now].sum = node[last].sum + 1;
ll l = 1, r = n;
while (l < r) {
ll mid = (l + r) >> 1;
if (pos <= mid) {
node[now].l = ++tot, node[now].r = node[last].r;
last = node[last].l, now = tot;
r = mid;
} else {
node[now].l = node[last].l, node[now].r = ++tot;
last = node[last].r, now = tot;
l = mid + 1;
}
node[now].sum = node[last].sum + 1;
}
return ret;
}
/*
inline void update(ll pre,ll& cur,ll l,ll r,ll v){
cur=++tot;
num[cur]=num[pre]+1;
if(l==r) return;
ls[cur]=ls[pre],rs[cur]=rs[pre];
ll m=(l+r)>>1;
if(v<=m) update(ls[pre],ls[cur],l,m,v);
else update(rs[pre],rs[cur],m+1,r,v);
}
*/
ll ask_kth(ll ltree, ll rtree, ll k) {
ll l = 1, r = n;
while (l < r) {
ll mid = (l + r) >> 1;
if (node[node[rtree].l].sum - node[node[ltree].l].sum >= k) {
ltree = node[ltree].l, rtree = node[rtree].l;
r = mid;
} else {
k -= (node[node[rtree].l].sum - node[node[ltree].l].sum);
ltree = node[ltree].r, rtree = node[rtree].r;
l = mid + 1;
}
}
return l;
}
void init() {
v.clear();
tot = 0;
for (ll i = 0; i < 100005 * 20; i++)
node[i].sum = 0;//初始化
copn = n;
}
void solve() {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
n = v.size();//离散化
tree[0] = build(1, n);
for (ll i = 1; i <= copn; i++) tree[i] = update(tree[i - 1], getpos(a[i]));
}
inline ll Query(ll l, ll r, ll cnt) {
return v[ask_kth(tree[l - 1], tree[r], cnt) - 1];
}
int main() {
while (scanf("%lld%lld", &n, &m) != EOF) {
init();
for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]), v.push_back(a[i]);
solve();
while (m--) {
ll l, r;
ll val = -1;
scanf("%lld%lld", &l, &r);//询问[l,r]第k小
ll ans1 = 0, ans2 = 0, ans3 = 0;
for (ll i = 1; i <= (r - l) + 1; i++) {
ll cnt = (r - l) + 2 - i;
if (ans2) ans1 = ans2;
else ans1 = Query(l, r, cnt);
cnt--;
if (cnt < 1) continue;
if (ans3) ans2 = ans3;
else ans2 = Query(l, r, cnt);
cnt--;
if (cnt < 1) continue;
ans3 = Query(l, r, cnt);
if (ans1 < ans2 + ans3) {
val = ans1 + ans2 + ans3;
break;
}
}
printf("%lld\n", val);
}
}
return 0;
}
京公网安备 11010502036488号