2018 ACM-ICPC南京网络赛
前言
其实这次补题就差LCT，所以花了比较长的时间学了LCT，毕竟要学LCT需要先学树链剖分，要学树链剖分需要先学点分治 _(:з」∠)_
虽然补了，但是以蒟蒻目前的实力，在有限时间内其实是遇不到这些题目的 qwq
另外就是，计蒜客的题目难截图，所以用Latex重排版，效果差了点，各位见谅
C - GDY
链接
https://nanti.jisuanke.com/t/30992
题意
懒得自己打了，直接copy网上的，来源：https://blog.csdn.net/w326159487/article/details/82378666
有 n 个人 m 张牌，牌的编号从1～13，其大小顺序为 3 < 4 < … < 12 < 13 < 1 < 2
在游戏开始时，每个人先从牌堆中抽取5张牌（五张五张抽），题目保证在初始抽牌结束时每个人手中至少有一张牌
然后从第一个人开始，他会取出手牌中最小的牌，并打出，接下来第二个人要出的牌必须为下一张牌，如第一个人出4下一个人须出5，也可以出2，2可以吃除了2的任何牌，但手牌中有下一张牌和2时，优先出下一张牌。
当第 i 个人出牌后其余人都无法出牌则所有人从牌库中抽一张牌，若牌库空了则跳过，然后第 i 个人继续出牌，出其手中最小的牌。
思路 —— 模拟
按照题目模拟就行
然而容易死于读错题目 = =||
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 200 + 5;
const int M = 20000 + 5;
int player[N][20];
int card[M], pp;
inline void init(){
memset(player, 0, sizeof(player));
pp = 0;
}
void AssignFirst(int n, int m){
for(int i = 0; i < n; i++){
for(int k = 0; k < 5; k++){
if(pp >= m) return;
player[i][card[pp]]++;
pp++;
}
}
}
void AssignProcess(int n, int m, int pos_player){
for(int i = pos_player; i < n; i++){
if(pp >= m) return;
player[i][card[pp]]++;
pp++;
}
for(int i = 0; i < pos_player; i++){
if(pp >= m) return;
player[i][card[pp]]++;
pp++;
}
}
int getMinCard(int pos_player, int pre_card){
if(pre_card == -1){
for(int i = 3; i < 15; i++){
if(player[pos_player][i]) return i;
}
}else if(pre_card + 1 < 15 && player[pos_player][pre_card + 1]){
return pre_card + 1;
}
return -1;
}
int getSum(int pos_player){
int ret = 0;
for(int i = 3; i <= 13; i++){
ret += player[pos_player][i] * i;
}
ret += (player[pos_player][14] + player[pos_player][15] * 2);
return ret;
}
int main(){
int t, csn = 1;
scanf("%d", &t);
while(t--){
init();
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++){
scanf("%d", &card[i]);
if(card[i] <= 2) card[i] += 13;
}
AssignFirst(n, m);
int cur_player = 0, pre_card = -1, fail_cnt = 0;
while(true){
if(!getSum(cur_player)) break;
int cur_min_card = getMinCard(cur_player, pre_card);
if(cur_min_card != -1){
player[cur_player][cur_min_card]--;
pre_card = cur_min_card;
fail_cnt = 0;
}else if(player[cur_player][15] && pre_card != 15){
player[cur_player][15]--;
pre_card = 15;
fail_cnt = 0;
}else{
fail_cnt++;
}
if(!getSum(cur_player)) break;
if(fail_cnt == n - 1){
AssignProcess(n, m, (cur_player + 1)%n);
pre_card = -1;
fail_cnt = 0;
}
cur_player++;
if(cur_player >= n) cur_player = 0;
}
printf("Case #%d:\n", csn++);
for(int i = 0; i < n; i++){
int tmp = getSum(i);
if(tmp) printf("%d\n", tmp);
else puts("Winner");
}
}
}
D - Jerome’s House
链接
https://nanti.jisuanke.com/t/30993
题意
给定一个凸多边形，在离边垂直距离至少为r的区域内选三个点，使|x1(y2−y3) + x2(y3−y1) + x3∗(y1−y2)|最大，求出这一最大值
思路 —— 半平面交 + 三分
距离为r就先做出内移r的多边形，用到半平面交
接下来求最大值，这个式子原来是两倍三角形的面积！（如果写成行列式便可发现）
在做出来的新的多边形中三角形最大值肯定是三个点都会落在顶点（证明？不会 QAQ）
那么暴力枚举点求一下面积取最大就好了，但是会TLE的，因为N <= 1000
那么可以枚举两个点再三分其他点，毕竟这肯定是个先增后减或先减后增的函数嘛（证明？还是不会 QAQ）
对于求出来的新的多边形，直接三分会遇到部分中间断层的问题，只要将顶点再copy一遍到后面即可，即对于任意两个点(l, r)，可以三分[l + 1, r - 1]与[r + 1, l + sz - 1]（下标假设从1开始，sz为新多边形的点数）
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1500 + 15;
const double eps = 1e-8;
struct Point{
double x, y;
Point() {}
Point(double x, double y): x(x), y(y) {}
Point operator + (const Point& b){
return Point(x + b.x, y + b.y);
}
Point operator - (const Point& b) {
return Point(x - b.x, y - b.y);
}
Point operator * (double d){
return Point(x * d, y * d);
}
};
typedef Point Vector;
struct Line{
Point a, b;
double angle;
void getAngle() {angle = atan2(b.y - a.y, b.x - a.x);}
Line(){}
Line(Point a, Vector b): a(a), b(b) {}
};
vector<Line> hp;
vector<Point> pt;
vector<Point> ans;
Line que[N];
inline double sqr(double x){ return x * x; }
int dcmp(double x) {
return x < -eps ? -1 : x > eps;
}
double cross(Vector a, Vector b){
return a.x * b.y - a.y * b.x;
}
double area(Point a, Point b, Point c) {
return cross(b - a, c - a);
}
bool isOnLineRight(Line u, Point v){
return dcmp(cross(u.b - u.a, v - u.a)) < 0;
}
bool cmp(Line u, Line v) {
int d = dcmp(u.angle - v.angle);
if(d) return d > 0;
return dcmp(cross(u.b - u.a, v.b - u.a)) < 0;
}
Vector normal(Vector u){
double len = sqrt(sqr(u.x) + sqr(u.y));
return Vector(-u.y / len, u.x / len);
}
Line moveLine(Line u, double r){
Vector x = normal(u.b - u.a);
return Line(u.a + x * r, u.b + x * r);
}
Point getLineIntersection(Line u, Line v){
Point ret = u.a;
double t = ((u.a.x-v.a.x) * (v.a.y-v.b.y)
-(u.a.y-v.a.y) * (v.a.x-v.b.x))
/ ((u.a.x-u.b.x) * (v.a.y-v.b.y)
-(u.a.y-u.b.y) * (v.a.x-v.b.x));
ret.x += (u.b.x-u.a.x) * t, ret.y += (u.b.y-u.a.y) * t;
return ret;
}
bool judge(Line l1, Line l2, Line l3) {
Point p = getLineIntersection(l2, l3);
return isOnLineRight(l1, p);
}
void hpi(){
ans.clear();
sort(hp.begin(), hp.end(), cmp);
int m = 0;
for(int i = 0; i < hp.size(); i++){
if(i && dcmp(hp[i].angle - hp[m - 1].angle) == 0) continue;
hp[m++] = hp[i];
}
hp.erase(hp.begin() + m, hp.end());
que[1] = hp[0], que[2] = hp[1];
int head = 1, tail = 2;
for(int i = 2; i < hp.size(); i++){
while(head < tail && judge(hp[i], que[tail - 1], que[tail])) tail--;
while(head < tail && judge(hp[i], que[head + 1], que[head])) head++;
que[++tail] = hp[i];
}
while(head < tail && judge(que[head], que[tail - 1], que[tail])) tail--;
while(head < tail && judge(que[tail], que[head + 1], que[head])) head++;
que[head - 1] = que[tail];
for(int i = head; i <= tail; i++){
ans.push_back(getLineIntersection(que[i], que[i - 1]));
}
}
double solve(int i, int j){
double res = 0;
int l = i + 1, r = j - 1;
while(l <= r){
int lm = l + (r - l) / 3;
int rm = r - (r - l) / 3;
double t1 = fabs(area(ans[i], ans[j], ans[lm]));
double t2 = fabs(area(ans[i], ans[j], ans[rm]));
if(dcmp(t1 - t2) > 0){
res = t1;
r = rm - 1;
}else{
res = t2;
l = lm + 1;
}
}
return res;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
hp.clear();
pt.clear();
int n;
double r;
scanf("%d%lf", &n, &r);
for(int i = 0; i < n; i++){
double x, y;
scanf("%lf%lf", &x, &y);
pt.push_back(Point(x, y));
if(i){
hp.push_back(Line(pt[i], pt[i - 1]));
hp[hp.size() - 1] = moveLine(hp[hp.size() - 1], r);
hp[hp.size() - 1].getAngle();
}
}
hp.push_back(Line(pt[0], pt[n - 1]));
hp[hp.size() - 1] = moveLine(hp[hp.size() - 1], r);
hp[hp.size() - 1].getAngle();
hpi();
int m = ans.size();
for(int i = 0; i < m; i++){
ans.push_back(ans[i]);
}
double res = 0;
for(int i = 0; i < m; i++){
for(int j = i + 2; j < m; j++){
res = max(res, solve(i, j));
res = max(res, solve(j, i + m));
}
}
printf("%.6f\n", res);
}
return 0;
}
H - Set
链接
https://nanti.jisuanke.com/t/30997
题意
给定N个数，他们一开始都在各自的集合内，以及M个操作，现在有三种操作：
1 u v，合并u和v的所在集合
2 u，对u所在的集合中所有数字+1
3 u k x，询问在u所在的集合中有多少数字满足y % (2^k) = x
思路 —— 动态开点的字典树
主要是因为操作3所以使用了字典树，学习了
毕竟是2^k，那么查询能够暴力在字典树上查询x就行，所以维护一个sz[o]，表示以其为根子树大小，维护方法也简单，就插入的时候经过++就行
现在考虑如何进行操作2，借鉴线段树，搞懒惰标记，那么如果+1，会导致0变1,1变0，也就是交换两个儿子，同时1变0的那个部分，还要继续进位，所以懒惰标记还要往下传，0变1不会继续进位，因此不需要往下传懒惰标记
推广一下就是，如果+x，若x为奇数，那么先解决+1的部分，让x变为偶数，而偶数就不会交换两个儿子，两个儿子对后续影响则是产生+x/2
最后考虑操作1，直接暴力合并即可
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6e5 + 5;
#define lson ch[o][0]
#define rson ch[o][1]
int ch[N * 32][2];
int sz[N * 32], lzy[N * 32];
int ft[N];
int tot;
inline void newNode(int& o){
o = tot++;
ch[o][0] = ch[o][1] = -1;
sz[o] = lzy[o] = 0;
}
inline void init(int n){
for(int o = 1; o <= n; o++){
ft[o] = o;
lson = rson = -1;
sz[o] = lzy[o] = 0;
}
tot = n + 1;
}
int find(int x){ return ft[x] == x ? x : ft[x] = find(ft[x]); }
void pushDown(int o){
if(!lzy[o]) return;
if(lzy[o] & 1){
swap(lson, rson);
if(lson != -1) lzy[lson]++;
}
if(lson != -1) lzy[lson] += lzy[o] / 2;
if(rson != -1) lzy[rson] += lzy[o] / 2;
lzy[o] = 0;
}
void push(int idx, int x){
int o = idx;
for(int i = 0; i < 30; i++, x >>= 1){
sz[o]++;
int& nxt = ch[o][x&1];
if(nxt == -1) newNode(nxt);
o = nxt;
}
sz[o]++;
}
void merge(int p, int q){
pushDown(p);
pushDown(q);
sz[p] += sz[q];
for(int k = 0; k < 2; k++){
if(ch[p][k] == -1 && ch[q][k] != -1) ch[p][k] = ch[q][k];
else if(ch[p][k] != -1 && ch[q][k] != -1) merge(ch[p][k], ch[q][k]);
}
}
int query(int idx, int x, int k){
int o = find(idx);
for(int i = 0; i < k; i++, x >>= 1){
pushDown(o);
int& nxt = ch[o][x&1];
if(nxt == -1) return 0;
o = nxt;
}
return sz[o];
}
void update(int idx){
int o = find(idx);
lzy[o]++;
}
void umerge(int x, int y){
int p = find(x), q = find(y);
if(p != q){
merge(p, q);
ft[q] = p;
}
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init(n);
for(int i = 1; i <= n; i++){
int tmp;
scanf("%d", &tmp);
push(i, tmp);
}
while(m--){
int op;
scanf("%d", &op);
if(op == 3){
int u, k, x;
scanf("%d%d%d", &u, &k, &x);
printf("%d\n", query(u, x, k));
}else if(op == 2){
int u;
scanf("%d", &u);
update(u);
}else{
int u, v;
scanf("%d%d", &u, &v);
umerge(u, v);
}
}
}
}
F - An Easy Problem On The Trees
链接
https://nanti.jisuanke.com/t/30995
题意
有一棵树有N个点，现在有三种操作：
1 x y：若x和y不在同一连通分量上，则连接x和y
2 x y：若x和y在同一连通分量上，则以x为根，切断y和他父亲的边
3 x：求从x点出发，等概率地游走，最后回到x的期望
思路 —— LCT
首先操作3的结论是2 * (sz[x] - 1) / deg[x]（有没有dalao告诉窝这是怎么来的 QAQQQ）
deg很好维护，sz的话就用LCT维护
最后说一下操作2中y和它父亲这件事情，makeRoot(x)然后splay(y)，此时y为根且无右子树，那么y的父亲应该是以ch[y][0]为根中序遍历的最后一个点
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson ch[x][0]
#define rson ch[x][1]
using namespace std;
typedef long long ll;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
const int MOD = 998244353;
inline char get(void) {
static char buf[1000000], *p1 = buf, *p2 = buf;
if (p1 == p2) {
p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline int read() {
int x = 0; static char c; bool minus = false;
for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') minus = true;
for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (minus) x = -x;
return x;
}
char WritellBuffer[1024];
template <typename T>
inline void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
if(end) putchar(end);
}
int deg[N];
struct LinkCutTree{
int fa[N], ch[N][2], sum[N], val[N], lzy[N];
int stk[N];
int si[N];
inline bool nRoot(int x){
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
void pushUp(int x){
sum[x] = sum[lson] + sum[rson] + si[x] + 1;
}
void pushR(int x){
swap(lson, rson);
lzy[x] ^= 1;
}
void pushDown(int x){
if(lzy[x]){
if(lson) pushR(lson);
if(rson) pushR(rson);
lzy[x] = 0;
}
}
void rotate(int x){
int y = fa[x], z = fa[y];
int p = (ch[y][1] == x), w = ch[x][p^1];
if(nRoot(y)) ch[z][ch[z][1] == y] = x;
ch[x][p^1] = y, ch[y][p] = w;
if(w) fa[w] = y;
fa[y] = x, fa[x] = z;
pushUp(y);
}
void splay(int x){
int pstk = 0, y = x;
for(y = x; nRoot(y); y = fa[y]){
stk[++pstk] = y;
}
stk[++pstk] = y;
while(pstk) pushDown(stk[pstk--]);
while(nRoot(x)){
int y = fa[x], z = fa[y];
if(nRoot(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
rotate(x);
}
pushUp(x);
}
void access(int x){
for(int y = 0; x; y = x, x = fa[x]){
splay(x);
si[x] += sum[rson];
si[x] -= sum[y];
rson = y;
pushUp(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
pushR(x);
}
int findRoot(int x){
access(x);
splay(x);
while(lson){
pushDown(x);
x = lson;
}
return x;
}
void split(int x, int y){
makeRoot(x);
access(y);
splay(y);
}
bool link(int x, int y){
makeRoot(x);
if(findRoot(y) != x){
si[y] += sum[x];
fa[x] = y;
deg[x]++;
deg[y]++;
return true;
}else{
return false;
}
}
};
void extgcd(ll a, ll b, ll& x, ll& y){
if(b == 0){
x = 1, y = 0;
}else{
extgcd(b, a%b, y, x);
y -= (a / b) * x;
}
}
ll getInv(ll a){
ll x, y;
extgcd(a, MOD, x, y);
return ((x % MOD) + MOD) % MOD;
}
LinkCutTree lct;
int main(){
int n = read(), m = read();
for(int i = 1; i <= n - 1; i++){
int x = read(), y = read();
lct.link(x, y);
}
while(m--){
int op = read();
if(op == 1){
int x = read(), y = read();
if(!lct.link(x, y)){
write(-1, '\n');
}
}else if(op == 2){
int x = read(), y = read();
if(lct.findRoot(x) == lct.findRoot(y) && x != y){
lct.makeRoot(x);
lct.access(y);
lct.splay(y);
int w = lct.ch[y][0];
while(true){
lct.pushDown(w);
if(!lct.ch[w][1]) break;
w = lct.ch[w][1];
}
deg[y]--;
deg[w]--;
w = lct.ch[y][0];
lct.fa[w] = lct.ch[y][0] = 0;
lct.pushUp(y);
}else{
write(-1, '\n');
}
}else{
int x = read();
lct.makeRoot(x);
write((2LL * (lct.sum[x] - 1) * getInv(deg[x])) % MOD, '\n');
}
}
}
