cbh大爷说：写博客不能弃坑。
orz cbh
那我就来更新博客了。
violet这个系列的题好神啊……出题人好劲啊……
……怎么最近都在理性愉悦啊……
另外bzoj400题纪念~
2708: [Violet 1]木偶
首先先对所有木偶按照特征值排序
考虑一种木偶与绳索配对的方法：
木偶\(1\)与绳索\(k+1\)配对，木偶\(2\)与绳索\(k+2\)配对……木偶\(n-k\)与绳索\(n\)配对。
当木偶\(n-k+1\)无法与绳索\(k\)配对时，这样的配对方法能扔掉\(k\)个木偶。
容易证明，最优的配对方式一定可以分成许多段，每段内用这种方式进行配对。
于是可以dp。
首先令\(g_{l,r}\)表示l~r之间用那种方式配对最多能扔掉多少个木偶，\(g_{l,r}\)可以通过枚举\(k\)算出，时间复杂度\(O(n^3)\)
令\(f_i\)表示到1~i之间能扔掉多少个木偶，那么有\(f_i=max\left \{ f_j+g_{j+1,i} \right \}\)。直接dp，时间复杂度\(O(n^2)\)
时间复杂度为\(O(n^2)\)
#include <bits/stdc++.h>
#define N 100
using namespace std;
int n;
int f[N], ai[N];
int g[N][N];
int main()
{
while (scanf("%d", &n) !=EOF)
{
for (int i = ; i <= n; ++ i) scanf("%d", &ai[i]);
sort(ai + , ai + n + );
for (int i = ; i <= n; ++ i)
for (int j = i; j <= n; ++ j)
{
int bo = ;
for (int k = ; k <= j - i + ; ++ k)
{
int p, q;
for (p = i, q = i + k; q <= j; ++ p, ++ q)
if (ai[q] - ai[p] > ) bo = ;
if (abs(ai[p] - ai[i + k - ]) <= ) bo = ;
if (!bo) {g[i][j] = k - ; break;}
}
if (bo) g[i][j] = j - i + ;
//if (g[i][j] != cal(i, j))
// puts("haha");
}
for (int i = ; i <= n; ++ i) f[i] = ;
for (int i = ; i <= n; ++ i)
for (int j = ; j < i; ++ j)
f[i] = max(f[i], f[j] + g[j + ][i]);
printf("%d\n", f[n]);
}
}
2709: [Violet 1]迷宫花园
二分答案，判断最短路，期间因为eps的问题wa了许多发QAQ
时间复杂度\(O(RClogRClogv)\)
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
int r, c;
double ll;
char mp[][];
int get(int rr, int cc)
{
return (rr - ) * c + cc;
}
int dr[] = {, -, , }, dc[] = {, , , -};
vector <int> bi[];
vector <double> ci[];
int s, e;
void build(int a, int b, double c)
{
bi[a].push_back(b); ci[a].push_back(c);
bi[b].push_back(a); ci[b].push_back(c);
}
struct node
{
int t; double l;
};
bool operator < (node a, node b) {return a.l > b.l;}
priority_queue <node> H;
int vis[]; double dis[];
int main()
{
int T;
cin >> T;
while (T --)
{
cin >> ll >> r >> c;
for (int i = ; i <= r; i++)
{
char cc;
scanf("%c", &cc);
while (cc != '\n') scanf("%c", &cc);
for (int j = ; j <= c; j++)
{
scanf("%c", &cc);
while (cc == '\n') scanf("%c",&cc);
mp[i][j] = cc;
if (cc=='S') s = get(i, j);
if (cc=='E') e = get(i, j);
}
}
{
double lb = , rb = ;
while (rb - lb > 0.0000001)
{
double md = (lb + rb) / ;
for (int i = ; i <= r * c; ++ i) bi[i].clear(), ci[i].clear();
for (int i = ; i <= r; ++ i)
for (int j = ; j <= c; ++ j)
for (int d = ; d < ; ++ d)
if (mp[i][j] != '#' && mp[i + dr[d]][j + dc[d]] != '#')
build(get(i, j), get(i + dr[d], j + dc[d]), (d >= ? : md));
for (int i = ; i <= r * c; ++ i)
dis[i] = INF, vis[i] = ;
while (!H.empty()) H.pop();
dis[s] = ,
H.push((node){s, });
while (!H.empty())
{
int hd;
do hd = H.top().t, H.pop();
while (vis[hd] && !H.empty());
if (!vis[hd]) vis[hd] = ;
else break;
for (int i = ; i < bi[hd].size(); ++ i)
if (dis[hd] + ci[hd][i] < dis[bi[hd][i]])
{
dis[bi[hd][i]] = dis[hd] + ci[hd][i];
H.push((node){bi[hd][i], dis[bi[hd][i]]});
}
}
if (dis[e] > ll) rb = md;
else lb = md;
}
printf("%.5lf\n", lb);
} }
}
2710: [Violet 1]追风者
好神的题啊，我不会做QAQ
2711: [Violet 2]After 17
题目要求最小化\(\sum_{i=1}^{n}\sum_{j=i+1}^{n}x_i x_j + y_i y_j\)，于是\(x\)和\(y\)可以分别考虑。
\(\sum_{i=1}^{n}\sum_{j=i+1}^{n}x_i x_j = \frac{(\sum_{i=1}^{n}x_i)^2-\sum_{i=1}^{n}x_i^2}{2}\)
通过归纳法（？）可以证明当\(\sum abs(x_i)\)最大时最优。因此\(\sum_{i=1}^{n}x_i)^2\)是定值，于是就可以用dp去求\(\sum_{i=1}^{n}x_i^2\)的最大值。
时间复杂度\(O(nl)\)
#include <bits/stdc++.h>
using namespace std;
#define N 210
#define M 40010
int f[N][M * ];
int n;
int xi[N], yi[N];
double ans;
void solve(int d[])
{
for (int i = ; i <= n; ++ i)
for (int j = -M; j < M; ++ j)
f[i][j + M] = ;
f[][M] = ;
for (int i = ; i < n; ++ i)
for (int j = -M; j < M; ++ j)
if (f[i][j + M])
f[i + ][j + d[i + ] + M] = f[i + ][j - d[i + ] + M] = ;
for (int i = ; i < M; ++ i)
if (f[n][M + i] || f[n][M - i])
{
ans += pow(i, );
break;
}
}
int main()
{
scanf("%d", &n);
for (int i = ; i <= n; ++ i)
{
scanf("%d%d", &xi[i], &yi[i]);
ans -= pow(xi[i], ) + pow(yi[i], );
}
solve(xi);
solve(yi);
printf("%.2lf", ans / );
}
2712: [Violet 2]棒球
第二道神题啊QAQ
考虑将边界化成分数，为什么要化成分数呢？因为精度问题。
化成分数后就转成了这么个问题：求分数\(\frac{p}{q}\)，最小化\(p\),\(q\)，使得\(\frac{lp}{lq} < \frac{p}{q} \leq \frac{rp}{rq}\)
若\(\frac{p}{q} = \frac{rp}{rq}\)，那么\(q=\frac{rq}{gcd(rp, rq)}\)。
剩下得就是\(\frac{lp}{lq} < \frac{p}{q} < \frac{rp}{rq}\)
考虑如下做法
若有一个整数\(p\)满足\(\frac{lp}{lq} < p < \frac{rp}{rq}\)，那么就输出\(p\)
如果\(lp<lq\)且\(rp<rq\)，则去递归求\(\frac{rq}{rp} < \frac{p'}{q'} < \frac{lq}{lp}\)，那么原问题得解就是\(\frac{q'}{p'}\)
否则，令\(k=\left \lfloor \frac{lp}{lq} \right \rfloor\)，递归求\(\frac{rq - k * rp}{rp} < \frac{p'}{q'} < \frac{lq - k * lp}{lp}\)，那么原问题得解就是\(\frac{p' + k * q'}{q'}\)
算法的正确性是显然的。递归时新问题的最优解\(\frac{p'}{q'}\)一定对应原问题的最优解\(\frac{p}{q}\)。如果前者对应的不是后者的最优解，那么就一定可以通过原问题的最优解构造出一个新问题的解\(\frac{p''}{q''}\)，使得这个解比\(\frac{p'}{q'}\)更优。
注意边界问题
时间复杂度\(O(r)\)
#include <bits/stdc++.h>
#define LL long long
#define pL pair <LL, LL>
using namespace std;
int n; LL r;
pL solve(LL lu, LL ld, LL ru, LL rd)
{
LL x = lu / ld + ;
if (x * rd < ru) return pL(x, );
if (!lu) return pL(, rd / ru + );
if (lu <= ld && ru <= rd)
{pL nw = solve(rd, ru, ld, lu); return pL(nw.second, nw.first);}
x = lu / ld;
pL nw = solve(lu - ld * x, ld, ru - rd * x, rd);
nw.first += nw.second * x;
return nw;
}
int main()
{
while (scanf("%d 0.%lld", &n, &r) == )
{
if (r == ) {puts(""); continue;}
LL x = ; while (n --) x *= ;
LL lu = r * - , ld = x, ru = r * + , rd = x;
for( ; lu % == && ld % == ; lu /= , ld /= );
for( ; ru % == && rd % == ; ru /= , rd /= );
pL ans = solve(lu, ld, ru, rd);
//printf("%lld %lld\n", ans.first, ans.second);
printf("%lld\n", min(ans.second, ld));
}
}
2713: [Violet 2]愚蠢的副官
第三道神题……我dp被卡常数了，极限数据要跑8s……交标程走人
2714: [Violet 3]交替和
数位dp
定义一个数的交替和为将该数从高位到低位添加至序列L后，A(L)的值，比如\(1101B\)的交替和为\(-1\)
定义\(f_{0,i}\)表示b进制下，所有可以有前导零的i位数的交替和的和。
定义\(f_{1,i}\)表示b进制下，所有可以有前导零的i位偶数的交替和减去所有可以有前导零的i位奇数的交替和
设\(n\)在\(b\)进制下有\(len\)位
那么答案由两部分组成。第一部分是位数在\(1\)~\(len-1\)之间的数，第二部分是位数为\(len\)的数。
维护当前要计算的第一个数位对答案的贡献的系数\(np\)。
第一部分枚举位数，最高位，用\(f\)以及\(np\)计算贡献
第二部分枚举与n从第几位开始不同，以及这一位选了多少，依然用\(f\)以及\(np\)计算贡献
时间复杂度\(O(blogn)\)
/**************************************************************
Problem: 2714
User: AwD
Language: C++
Result: Accepted
Time:0 ms
Memory:1296 kb
****************************************************************/
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL b, n;
LL f[][], g[];
LL ni[], nl, ans;
int main()
{
cin >> b >> n;
g[] = ;
for (LL i = , j = ; j <= n; ++ i, j *= b)
{
LL np = ;
for (LL k = ; k < b; ++ k)
f[][i] += f[][i - ] * - + g[i - ] * k,
f[][i] += f[][i - ] * -np + (g[i - ] & ) * k * np,
np = np * ((g[i - ] * i)& ? -: );
g[i] = g[i - ] * b;
}
while (n)
{
ni[++ nl] = n % b;
n /= b;
}
{
LL np = , s = ;
for (LL i = ; i < nl; ++ i)
{
for (LL k = ; k < b; ++ k)
ans += f[i & ][i - ] * -np + (i & ? g[i - ] & : g[i - ]) * k * np,
np = np * ((g[i - ] * i) & ? -: );
}
//cout << ans << "\n";
for (LL i = nl; i >= ; -- i)
{
for (LL k = (i == nl); k <= (ni[i] - (i != )); ++ k)
ans += f[nl & ][i - ] * ((nl - i) & ? : -) * np + (nl & ? g[i - ] & : g[i - ]) * (s + ((nl - i) & ? -: ) * k) * np,
np = np * ((g[i - ] * nl) & ? -: );
s += ((nl - i) & ? -: ) * ni[i];
}
cout << ans << "\n";
}
}
2715: [Violet 3]最优指令
状压所有状态是否可以出现，简单bfs即可
时间复杂度\(O(2^SC)\)
#include <bits/stdc++.h>
#define N (1 << 17)
using namespace std;
int s, c;
int dis[N], vis[N];
queue <int> Q;
int pres[N], prei[N];
int trans[][];
void dfs(int t)
{
if (t != ( << s) - )
{
dfs(pres[t]);
if (prei[t] < ) printf("%d", prei[t]);
else printf("%c", prei[t] - + 'a');
}
}
int main()
{
scanf("%d%d", &s, &c);
for (int i = ; i < s; ++ i)
for (int j = ; j < c; ++ j)
scanf("%d", &trans[i][j]);
Q.push(( << s) - ); vis[( << s) - ] = ;
while (!Q.empty())
{
int hd = Q.front(); Q.pop();
for (int i = ; i < c; ++ i)
{
int nw = ;
for (int j = ; j < s; ++ j)
if (hd & ( << j))
nw |= ( << trans[j][i]);
if (!vis[nw])
{
vis[nw] = ;
dis[nw] = dis[hd] + ;
pres[nw] = hd;
prei[nw] = i;
Q.push(nw);
}
}
}
if (!vis[]) puts("impossible");
else dfs();
}
2716: [Violet 3]天使玩偶
裸的k-d树，我的常数写的好挫啊QAQ
时间复杂度\(O((n+m)\sqrt{n + m})\)
#include <bits/stdc++.h>
#define INF 100000000
#define N 1000100
using namespace std;
int n, m;
struct point {int d[];};
struct node
{
int opt, ch[], si;
int bd[][];
point mid;
} tr[N];
stack <int> S;
int nw, tmp;
int comp(point a, point b) {return a.d[nw] < b.d[nw];}
point ls[N];
void dfs_dele(int t)
{
if (tr[t].ch[]) dfs_dele(tr[t].ch[]);
ls[++ tmp] = tr[t].mid;
if (tr[t].ch[]) dfs_dele(tr[t].ch[]);
tr[t].ch[] = tr[t].ch[] = ;
tr[t].opt = tr[t].si = ;
S.push(t);
}
void update(int t)
{
tr[t].bd[][] = min(tr[t].mid.d[], min(tr[tr[t].ch[]].bd[][], tr[tr[t].ch[]].bd[][]));
tr[t].bd[][] = max(tr[t].mid.d[], max(tr[tr[t].ch[]].bd[][], tr[tr[t].ch[]].bd[][]));
tr[t].bd[][] = min(tr[t].mid.d[], min(tr[tr[t].ch[]].bd[][], tr[tr[t].ch[]].bd[][]));
tr[t].bd[][] = max(tr[t].mid.d[], max(tr[tr[t].ch[]].bd[][], tr[tr[t].ch[]].bd[][]));
}
int rebuild(int opt, int l, int r)
{
nw = opt; sort(ls + l, ls + r + , comp);
int mid = (l + r) / ;
int hd = S.top(); S.pop();
tr[hd].mid = ls[mid];
tr[hd].opt = opt; tr[hd].si = r - l + ;
if (l < mid) tr[hd].ch[] = rebuild(!opt, l, mid - );
if (mid < r) tr[hd].ch[] = rebuild(!opt, mid + , r);
update(hd);
return hd;
}
int insert(int opt, int t, point nw)
{
if (!t)
{
t = S.top(); S.pop();
tr[t].opt = opt;
tr[t].si = ; tr[t].mid = nw;
}
else
{
int k = tr[t].mid.d[tr[t].opt] < nw.d[tr[t].opt];
tr[t].si ++;
tr[t].ch[k] = insert(!opt, tr[t].ch[k], nw);
if (1.0 * tr[tr[t].ch[k]].si / tr[t].si > 0.7)
{
tmp = ; dfs_dele(t);
t = rebuild(opt, , tmp);
}
}
update(t);
return t;
}
int nowans;
int dis(point a, point b)
{
return abs(a.d[] - b.d[]) + abs(a.d[] - b.d[]);
}
int dis(point a, int t)
{
int tmp = ;
for (int i = ; i <= ; ++ i)
if (a.d[i] < tr[t].bd[i][]) tmp += tr[t].bd[i][] - a.d[i];
for (int i = ; i <= ; ++ i)
if (a.d[i] > tr[t].bd[i][]) tmp += a.d[i] - tr[t].bd[i][];
return tmp;
}
int s, dp;
void ask(int t, point nw)
{
s ++;
if (dis(tr[t].mid, nw) < nowans) nowans = dis(tr[t].mid, nw);
int b[];
b[] = dis(nw, tr[t].ch[]);
b[] = dis(nw, tr[t].ch[]);
int k = b[] < b[];
if (tr[t].ch[k]) if (b[k] < nowans) ask(tr[t].ch[k], nw);
if (tr[t].ch[!k]) if (b[!k] < nowans) ask(tr[t].ch[!k], nw);
//dp --;
}
int root;
int main()
{
tr[].bd[][] = tr[].bd[][] = INF;
scanf("%d%d", &n, &m);
for (int i = N - ; i >= ; -- i) S.push(i);
for (int i = ; i <= n + m; ++ i)
{
int t = , x, y;
if (i > n) scanf("%d", &t);
scanf("%d%d", &x, &y);
nowans = INF;
if (t == ) root = insert(, root, (point){x, y});
else
{
s = ;
ask(root, (point){x, y});
printf("%d\n", nowans);
}
}
}
2717: [Violet 4]迷路的兔子
第四道神题= =
奥妙重重的构造题，只要知道这是对的就好了是不是哇QAQ
时间复杂度\(O(n^2)\)
#include <bits/stdc++.h>
#define N 1000
using namespace std;
int n, x;
int remain[N][N];
int main()
{
cin >> n;
cout << n * (n - ) / << "\n";
for (int i = ; i <= (n >> ); ++ i)
for (int j = ; j <= n; ++ j)
cout << j << " " << (j + i - ) % n + << " " << (j + i + i - ) % n + << "\n";
}
2718: [Violet 4]毕业旅行
建二分图，把每个点\(i\)拆成两个点\(A_i\)，\(B_i\)
用传递闭包把原图中每个点能到达的点都跑出来，若\(i\)能到达\(j\)，那么就在新图中将\(A_i\)与\(B_j\)连一条边。
那么原图的独立集就相当于新图中的独立集。直接上匈牙利。
时间复杂度\(O(n^3)\)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int sx[][];
int vx[], vy[], pr[];
int ans;
int dfs(int t)
{
vx[t] = ;
for (int i = ; i <= n; ++ i)
if (sx[t][i] && !vy[i] && !vx[pr[i]])
{
if (!pr[i] || dfs(pr[i]))
{
pr[i] = t;
return ;
}
}
return ;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = ; i <= m; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
sx[a][b] = ;
}
for (int k = ; k <= n; ++ k)
for (int i = ; i <= n; ++ i)
for (int j = ; j <= n; ++ j)
if (sx[i][k] && sx[k][j])
sx[i][j] |= ;
for (int i = ; i <= n; ++ i)
{
for (int j = ; j <= n; ++ j) vx[j] = vy[j] = ;
if (dfs(i)) ans ++;
}
printf("%d", n - ans);
}
2719: [Violet 4]银河之星
由于第二种移动的存在，所有在模三意义下同余的位置是等价的，因此可以缩在一起。
直接上记搜。
注意两个坑点：
1.由于棋盘大小的限制，某些情况下第二种移动是没法做的，因此要现判断这些移动的可行性。
2.由于棋盘大小的限制，每种位置能放的棋子的数量是有上限的，搜索时要判断一下
时间复杂度O(跑的出)
#include <bits/stdc++.h>
using namespace std;
int k, n, m, fin_x, fin_y;
int fin;
struct status
{
int ss[];
status () {for (int i = ; i < ; ++ i) ss[i] = ;}
};
int operator <(status a, status b)
{
for (int i = ; i < ; ++ i)
if (a.ss[i] != b.ss[i])
return a.ss[i] < b.ss[i];
return ;
}
map <status, int> M;
int xd[] = {-, -, -, , , , , };
int yd[] = {-, , , , , , -, -};
int ai[], bi[], ci[], tot;
int cg[][], mx[];
int get_pos(int x, int y)
{
x = x % ;
y = y % ;
return x * + y;
}
int dfs(status nw)
{
if (M.count(nw)) return M[nw];
int is_ans = ;
for (int i = ; i < ; ++ i)
if (((bool)nw.ss[i]) ^ (i == fin))
is_ans = ;
if (is_ans) return ;
for (int i = ; i < tot; ++ i)
if (nw.ss[ai[i]] && nw.ss[bi[i]])
{
status nx = nw;
nx.ss[ai[i]] --;
nx.ss[bi[i]] --;
nx.ss[ci[i]] ++;
if (nx.ss[ci[i]] > mx[ci[i]]) continue;
if (dfs(nx)) return M[nw] = ;
}
return M[nw] = ;
}
void init()
{
for (int i = ; i < ; ++ i)
for (int j = ; j < ; ++ j)
cg[i][j] = -;
for (int i = ; i < ; ++ i) mx[i] = ;
for (int i = ; i <= n; ++ i)
for (int j = ; j <= m; ++ j)
{
mx[get_pos(i, j)] ++;
for (int d = ; d < ; ++ d)
if (i + xd[d] * >= && i + xd[d] * <= n && j + yd[d] * >= && j + yd[d] * <= m)
cg[get_pos(i, j)][get_pos(i + xd[d], j + yd[d])] = get_pos(i + xd[d] * , j + yd[d] * );
}
tot = ;
for (int i = ; i < ; ++ i)
for (int j = ; j < ; ++ j)
if (cg[i][j] >= )
{
ai[tot] = i;
bi[tot] = j;
ci[tot] = cg[i][j];
tot ++;
}
}
int main()
{
while (scanf("%d%d%d%d%d", &k, &n, &m, &fin_x, &fin_y) == )
{
fin = get_pos(fin_x, fin_y);
M.clear();
status start;
for (int i = ; i <= k; ++ i)
{
int x, y;
scanf("%d%d", &x, &y);
start.ss[get_pos(x, y)] ++;
}
init();
if (dfs(start)) puts("Yes");
else puts("No");
}
}
2720: [Violet 5]列队春游
数学题，推推式子可以得到结论
时间复杂度\(O(nlogn)\)
#include <bits/stdc++.h>
using namespace std;
int n, s;
int ai[];
double ans; int main()
{
scanf("%d", &n);
for (int i = ; i <= n; ++ i) scanf("%d", &ai[i]);
sort(ai + , ai + n + );
for (int i = , j = ; i <= n; ++ i)
if (ai[i] != ai[i + ])
{
ans += 1.0 * (i - j) * (n + ) / (n + - j);
j = i;
}
printf("%.2lf", ans);
}
2721: [Violet 5]樱花
又是一道数学题，答案是\((n!)^2\)的约数个数，筛一下素数即可
时间复杂度\(O(n)\) （还是\(O(nloglogn)\)？）
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
#define mod 1000000007
#define inf 1000000000
using namespace std;
int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
int n,cnt;
ll ans=;
int pri[],mn[],num[];
bool del[];
void getpri()
{
for(int i=;i<=n;i++)
{
if(!del[i])pri[++cnt]=i,mn[i]=cnt;
for(int j=;pri[j]*i<=n&&j<=cnt;j++)
{
del[pri[j]*i]=;mn[pri[j]*i]=j;
if(i%pri[j]==)break;
}
}
}
void cal(int x)
{
while(x!=)
{
num[mn[x]]++;
x/=pri[mn[x]];
}
}
int main()
{
n=read();
getpri();
for(int i=;i<=n;i++)
cal(i);
for(int i=;i<=cnt;i++)
ans=ans*(num[i]*+)%mod;
printf("%lld\n",ans);
return ;
}
2722: [Violet 5]爱的花环
还是神题= =
由于\(A_{i,j}=A_{j,i}\)
因此\(l_{i,j}\)和\(l_{j,i}\)的限制，\(r_{i,j}\)和\(r_{j,i}\)的限制可以分别合并在一起。
且\(\sum_{i=1}^{n}\sum_{j=1}^{n}A_{i,j}=0\)可以化为：\(\sum_{i=1}^{n}A_{i,i} + 2\sum_{i=1}^{n}\sum_{j=i+1}^{n}A_{i,j}=0\)。
考虑做以下变换：
对于所有满足\(i!=j\)的数对\((i,j)\)，将\(l_{i,j}\)、\(r_{i,j}\)翻倍。
对于所有\(k_{i,i}\)，将其翻倍。
在这个变换之后，原问题就转化为了：求一个满足
\(\sum_{i=1}^{n}\sum_{j=i}^{n}A_{i,j}=0\)，
\(l_{i,j}\leq A_{i,j}\leq r_{i,j}\)，
对于所有\(i != j\)，有\(A_{i,j}mod2=0\)
这些限制的数组\(A\)，使得\(\sum_{i=1}^{n}\sum_{j=i}^{n}k_{i,j}A_{i,j}\)最大。
这个问题得到的答案是原问题的两倍。
现考虑如何解决这个问题。
首先先排除对于所有\(i != j\)，有\(A_{i,j}mod2=0\)这个限制，由于\(k_{i,j}\)为正，可以这样做：
1.将所有\(A_{i,j}\)赋值为\(r_{i,j}\)
2.如果当前\(\sum_{i=1}^{n}\sum_{j=i}^{n}A_{i,j}=0\)，结束，返回答案
3.否则在满足\(A_{i,j}!=l_{i,j}\)的数对\((i,j)\)中找一个\(k_{i,j}\)最小的，将它的\(A_{i,j}\)减小，减小到满足下面任意一条限制为止：
a.\(\sum_{i=1}^{n}\sum_{j=i}^{n}A_{i,j}=0\)
b.\(A_{i,j}=l_{i,j}\)
4.转至步骤2
这个贪心的正确性是明显的。
那么加上对于所有\(i != j\)，有\(A_{i,j}mod2=0\) 这个限制。考虑会发生什么：
可能会出现一个\(A_{i,j}(i != j)\)变成奇数了。
为了满足这个限制，需要改变它的奇偶性。这个值从哪里来？只能从某一个\(A_{p,p}\)中来。
让答案尽可能的优，我们需要找到一个\(abs(k_{p,p} - k_{i,j})\)最小的\((p, p)\)，并在\((p, p)\)，\((i, j)\)之间移动一个1即可。
然后就是这样了……
时间复杂度\(O(n^2logn^2)\)
#include <bits/stdc++.h>
#define N 300000
#define INF 100000000
#define LL long long
using namespace std;
LL n;
LL ss[][], pp[][], tot;
LL ki[N], li[N], ri[N];
LL nw[N];
LL ord[N], nwsum, ans;
LL comp(LL a, LL b)
{
return ki[a] < ki[b];
}
int main()
{
//freopen("garland6.in", "r", stdin);
scanf("%lld", &n);
for (LL i = ; i <= n; ++ i) ss[i][i] = ++ tot;
for (LL i = ; i <= n; ++ i)
for (LL j = i + ; j <= n; ++ j)
ss[i][j] = ss[j][i] = ++ tot;
for (LL i = ; i <= n * (n - ); ++ i)
li[i] = -INF, ri[i] = INF, ki[i] = ;
for (LL i = ; i <= n; ++ i)
for (LL j = ; j <= n; ++ j)
{
LL a;
scanf("%lld", &a);
ki[ss[i][j]] += a;
}
for (LL i = ; i <= n; ++ i)
for (LL j = ; j <= n; ++ j)
{
LL a;
scanf("%lld", &a);
li[ss[i][j]] = max(li[ss[i][j]], a);
}
for (LL i = ; i <= n; ++ i)
for (LL j = ; j <= n; ++ j)
{
LL a;
scanf("%lld", &a);
ri[ss[i][j]] = min(ri[ss[i][j]], a);
}
for (LL i = ; i <= n; ++ i) ki[i] *= ;
for (LL i = n + ; i <= tot; ++ i) li[i] *= , ri[i] *= ;
//for (LL i = 1; i <= tot; ++ i) cout << li[i] << " "; cout << "\n";
//for (LL i = 1; i <= tot; ++ i) cout << ri[i] << " "; cout << "\n";
//for (LL i = 1; i <= tot; ++ i) cout << ki[i] << " "; cout << "\n";
for (LL i = ; i <= tot; ++ i) ord[i] = i;
sort(ord + , ord + tot + , comp);
for (LL i = ; i <= tot; ++ i) nw[i] = ri[i], nwsum += ri[i];
for (LL i = ; i <= tot; ++ i)
if (nwsum > ri[ord[i]] - li[ord[i]]) nwsum -= ri[ord[i]] - li[ord[i]], nw[ord[i]] = li[ord[i]];
else if (ord[i] <= n || nwsum % == )
{
nw[ord[i]] -= nwsum; break;
}
else
{
nw[ord[i]] -= nwsum;
LL p = i, q = i;
while (ord[q] > n && q <= tot) ++ q;
while (ord[p] > n && p >= ) -- p;
if (p < || (q <= tot && ki[ord[q]] - ki[ord[i]] < ki[ord[i]] - ki[ord[p]]))
{
nw[ord[i]] ++;
nw[ord[q]] --;
}
else
{
nw[ord[i]] --;
nw[ord[p]] ++;
}
break;
}
for (LL i = ; i <= n; ++ i)
for (LL j = ; j <= n; ++ j)
if (i == j)
pp[i][j] = nw[ss[i][j]];
else
{
pp[i][j] = nw[ss[i][j]] / ;
if (nw[ss[i][j]] % == ) puts("mdzz");
}
/*
for (LL i = 1; i <= n; ++ i)
{
for (LL j = 1; j <= n; ++ j) printf("%d ", pp[i][j]);
puts("");
}*/
for (LL i = ; i <= tot; ++ i) ans += nw[i] * ki[i];
printf("%lld", ans / );
}
2723: [Violet 6]星之波动
好像很神的样子QAQ，不敢看
2724: [Violet 6]蒲公英
很显然的分块，l~r之间的众数只可能出现在：l~块a的众数，块a~块b的众数，块b~r的众数之间，预处理出任意两块之间的众数，乱搞即可。
时间复杂度\(O(n\sqrt{n})\)
#include <bits/stdc++.h>
#define N 50000
#define P 1000
using namespace std;
int n, m, s;
int ai[N], si[N];
int mx[P][P], in[N], st[N];
vector <int> L[N], S;
int nowi[N], nowmax;
int get(int t, int l, int r)
{
int p = (upper_bound(L[t].begin(), L[t].end(), r) - lower_bound(L[t].begin(), L[t].end(), l)) * (n + ) - t;
return p;
}
int main()
{
scanf("%d%d", &n, &m); s = sqrt(n / (log(n) / log())) + ;
for (int i = ; i <= n; ++ i)
scanf("%d", &ai[i]), si[i] = ai[i];
sort(si + , si + n + );
for (int i = ; i <= n; ++ i)
ai[i] = lower_bound(si + , si + n + , ai[i]) - si;
for (int i = ; i <= n; ++ i) L[ai[i]].push_back(i);
for (int i = , p = ; i <= n; i += s, ++ p)
for (int j = ; j <= s && i + j - <= n; ++ j)
in[i + j - ] = p; for (int i = ; i <= n; i += s)
{
for (int j = ; j <= n; ++ j) nowi[j] = ;
for (int j = i; j <= n; ++ j)
{
nowi[ai[j]] ++;
if (nowi[ai[j]] > nowi[nowmax] || nowi[ai[j]] == nowi[nowmax] && ai[j] < nowmax)
nowmax = ai[j];
if (in[j] != in[j + ]) mx[in[i]][in[j]] = nowmax;
}
}
for (int i = , last = ; i <= m; ++ i)
{
int l, r, ans = ;
scanf("%d%d", &l, &r);
//last = 0;
l = (l + last - ) % n + ;
r = (r + last - ) % n + ;
if (l > r) swap(l, r);
S.clear();
if (in[l] == in[r]) for (int i = l; i <= r; ++ i) S.push_back(ai[i]);
else
{
for (int i = l; in[i] == in[l]; ++ i) S.push_back(ai[i]);
for (int i = r; in[i] == in[r]; -- i) S.push_back(ai[i]);
S.push_back(mx[in[l] + ][in[r] - ]);
}
for (int i = ; i < S.size(); ++ i)
if (get(S[i], l, r) > get(ans, l, r))
ans = S[i];
ans = si[ans];
printf("%d\n", ans);
last = ans;
}
}
2725: [Violet 6]故乡的梦
终于要写完了QAQ
首先从\(s\)开始建最短路径生成树。
定义关键路径为该树上\(s\)->\(t\)的路径。
定义一个点的\(dep\)
若一个点在关键路径上，则该点的\(dep\)为它是关键路径上的第几个点。
若一个点不在关键路径上，则该点的\(dep\)为它沿着树边走，到达第一个在关键路径上的点的\(dep\)。
很明显，如果切断的边\((x, y)\)如果不在关键路径上的话，最短路是不会变的。
因此考虑\((x, y)\)在树上的情况，假定x是y的父亲。
考虑这时的路径是怎样的：\(s\)->\(x'\)->\(y'\)->\(t\)
其中\(s\)->\(x'\)是在原图上\(s\)到\(x'\)的最短路，且\(x'\)尽可能的晚，\(y'\)->\(t\)是原图上\(y'\)到\(t\)的最短路，且\(y'\)尽可能的早。
这三段一定不能含有\(x\)->\(y\)
首先考虑\(s\)->\(x'\)这一段，要使得其中没有\(x\)->\(y\)，只需要保证\(dep_{x'}\leq dep_{x}\)即可
接着考虑\(y'\)->\(t\)这一段，要使得其中没有\(x\)->\(y\)，只需要保证\(dep_{y}\leq dep_{y'}\)即可。由于最短路不会绕一圈，这个的正确性是显然的。
最后考虑\(x'\)->\(y'\)这一段
假设\(x'\)->\(y'\)不止一条边，那么设其中有一个点\(a\)，因此这一段就变成了\(x'\)->\(a\)->\(y'\)
但是由于只切断了一条边，因此\(a\)到\(s\)或者\(t\)中一个点的路径一定是最短路，于之前的设定矛盾。
因此\(x'\)->\(y'\)只有一条边。
于是我们可以枚举每条不在最短路图上的边\((a, b)\)，用它去更新切断边在\(\left [ dep_{a},dep_{b} \right ]\)内的答案。用线段树维护即可
时间复杂度\(O((n+m)logn)\)
#include <bits/stdc++.h>
#define N 300000
#define M 900000
#define INF 1000000000000000ll
#define LL long long
using namespace std;
LL n, m, s, e;
vector <LL> bi[N], ci[N];
LL vis[N];
LL dis[N], die[N], pre[N], lst[N], tot;
LL inls[N];
struct node {LL t, d;};
struct comp {LL operator () (node a, node b) {return a.d > b.d;}};
priority_queue <node, vector <node>, comp> H; queue <LL> Q; void dfs1(int t, int p)
{
inls[t] = p;
for (LL i = ; i < bi[t].size(); ++ i)
if (pre[bi[t][i]] == t)
if (inls[bi[t][i]]) dfs1(bi[t][i], inls[bi[t][i]]);
else dfs1(bi[t][i], p);
} LL mn[M], finmn[N];
void put_min(LL t, LL lb, LL rb, LL l, LL r, LL d)
{
if (lb == l && rb == r) {mn[t] = min(mn[t], d); return;}
LL ml = (lb + rb) / , mr = (lb + rb) / + ;
if (l <= ml) put_min(t * , lb, ml, l, min(r, ml), d);
if (r >= mr) put_min(t * + , mr, rb, max(l, mr), r, d);
}
void dfs_seg(LL t, LL lb, LL rb)
{
if (lb != rb)
{
mn[t * ] = min(mn[t * ], mn[t]);
dfs_seg(t * , lb, (lb + rb) / );
mn[t * + ] = min(mn[t * + ], mn[t]);
dfs_seg(t * + , (lb + rb) / + , rb);
}
else finmn[lb] = mn[t];
}
LL q;
int main()
{
scanf("%lld%lld", &n, &m);
for (LL i = ; i <= m; ++ i)
{
LL a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
bi[a].push_back(b); ci[a].push_back(c);
bi[b].push_back(a); ci[b].push_back(c);
}
scanf("%lld%lld", &s, &e);
for (LL i = ; i <= n; ++ i)
dis[i] = INF;
dis[s] = ; H.push((node){s, });
while (!H.empty())
{
LL hd;
do hd = H.top().t, H.pop();
while (vis[hd] && !H.empty());
if (vis[hd]) break; else vis[hd] = ;
for (LL i = ; i < bi[hd].size(); ++ i)
if (dis[hd] + ci[hd][i] < dis[bi[hd][i]])
dis[bi[hd][i]] = dis[hd] + ci[hd][i],
pre[bi[hd][i]] = hd,
H.push((node){bi[hd][i], dis[bi[hd][i]]});
} for (LL i = ; i <= n; ++ i) vis[i] = ;
for (LL i = ; i <= n; ++ i)
die[i] = INF;
die[e] = ; H.push((node){e, });
while (!H.empty())
{
LL hd;
do hd = H.top().t, H.pop();
while (vis[hd] && !H.empty());
if (vis[hd]) break; else vis[hd] = ;
for (LL i = ; i < bi[hd].size(); ++ i)
if (die[hd] + ci[hd][i] < die[bi[hd][i]])
die[bi[hd][i]] = die[hd] + ci[hd][i],
H.push((node){bi[hd][i], die[bi[hd][i]]});
} for (LL p = e; p; p = pre[p])
lst[++ tot] = p, inls[p] = tot; dfs1(s, inls[s]);
for (LL i = ; i <= tot * ; ++ i) mn[i] = INF;
for (LL i = ; i <= n; ++ i)
for (LL j = ; j < bi[i].size(); ++ j)
if (inls[i] > inls[bi[i][j]] && pre[bi[i][j]] != i)
put_min(, , tot, inls[bi[i][j]], inls[i] - , dis[i] + ci[i][j] + die[bi[i][j]]);
dfs_seg(, , tot); scanf("%lld", &q);
for (LL i = ; i <= q; ++ i)
{
LL a, b;
scanf("%lld%lld", &a, &b);
if (inls[a] > inls[b]) swap(a, b);
if (lst[inls[a]] == a && lst[inls[b]] == b && inls[b] - inls[a] == )
if (finmn[inls[a]] != INF) printf("%lld\n", finmn[inls[a]]);
else puts("Infinity");
else printf("%lld\n", dis[e]);
}
}
呼~~~