首页 > 其他分享 >2024.4.20 笔记

2024.4.20 笔记

时间：2024-04-20 20:11:58浏览次数：14  
标签：ch 2024.4 int rint 笔记 return ++ 字符串 20

2024.4.20 笔记

SP4354 Snowflakes

记录所有的雪花，判断是否存在两个雪花是相同的。由于数据量较大，需要 \(O(n)\) 的复杂度来查询雪花，考虑哈希表

定义一个哈希值的转换方式，让不同的雪花哈希值不相同，相同的雪花的六个角一定是相同的 \(6\) 个值且相同的顺序排列，只不过起点在不同的角上。因此可以将哈希值定义为每朵雪花的六个角的长度之和 \(+\) 六个角的长度乘积。

然后还需要判断两个雪花是否相同，不能使用哈希值比较的方法，因为可能会产生哈希冲突，因此可以使用雪花的特性，两个相同的雪花，各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。我们可以基于这个特性直接暴力判断。

int n;
int snow[N][6];
int h[N], ne[N], idx;
int t[6];

int get_hash(int a[]) 
{
    int res1 = 0, res2 = 0;
    for (rint i = 0; i < 6; i++)
    {
		res1 = (res1 + a[i]) % P;
		res2 = (res2 * a[i]) % P;
	}
    return (res1 + res2) % P;
}

bool check(int a[], int b[])
{
    for (rint i = 0; i < 6; i++)
    {
        for (rint j = 0; j < 6; j++)
        {
            bool flag = 1;
            for (rint k = 0; k < 6; k++) 
                if (a[(i + k) % 6] != b[(j + k) % 6])
                    flag = 0;
            if (flag) return 1;
            flag = 1;
            for (rint k = 0; k < 6; k++)
                if (a[(i + k) % 6] != b[(j - k) % 6]) 
				    flag = 0;
            if (flag) return 1;
        }		
	}
    return 0;
}

bool insert(int a[]) 
{
    int x = get_hash(a);
    for (rint i = h[x]; i; i = ne[i]) 
    {
        if (check(snow[i], a)) return 1;
	}
    idx++;
    for (rint i = 0; i < 6; i++) snow[idx][i] = a[i];		
    ne[idx] = h[x];
    h[x] = idx; 
    return 0;
}

signed main()
{
    cin >> n;
    while (n--)
    {
        for (rint i = 0; i < 6; i++)
        {
			cin >> t[i];
		}
        if (insert(t))
        {
            puts("Twin snowflakes found.");
            return 0;
        }
    }
    puts("No two snowflakes are alike.");
    
    return 0;
}

AcWing 138. 兔子与兔子

本题每次要比较的是字符串中的某两个区间是否相同，可以用字符串哈希来做，只需要使该区间内哈希值一样即可

int n, m;
char s[N];
//h[i] 表示原字符串中前 i 个字符组成的字符串的哈希值
//p[i] 表示 p 的 i 次方
uint h[N], p[N];

uint calc(int l, int r) 
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

signed main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);

    p[0] = 1; 
    for (rint i = 1; i <= n; i++) 
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i];
    }

    cin >> m;
    while (m--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (calc(l1, r1) == calc(l2, r2)) puts("Yes"); 
        else puts("No"); 
    }
    return 0;
}

AcWing 139. 回文子串的最大长度

由于 zty 讲的是哈希，就不用manacher了

本题要求的是一个字符串中最大回文串的长度，我们可以枚举中间点，然后每次求出当前中间点的最大回文串，对所有情况取一个最大值即可。

但是对于中间点有两种情况，如果字符串是奇数个，那么是存在中间点的，但是如果字符串是偶数个，那么是不存在中间点的。这里我们可以用一个常用技巧来简化判断，将字符串中每两个字符之间加上一个特殊字符，假设加上一个 '#'，
对于奇数个的字符串，a#b#c#d#f，添加后还是奇数个。对于偶数个的字符串，a#b#c#d，添加后变成了奇数个。通过这样的处理，我们只需要考虑奇数情况的字符串就行了，奇数个的字符串一定是存在中间点的，因此直接枚举中间点即可。

然后就要对于每个中间点求最大回文串的长度，可以求当前中间点两边需要加上的边长，然后二分求这个边长的最大值。每次二分出最大值后统计一下回文串的长度，更新最大值即可。

int n;
char s[N];
//h[] 表示正序的字符串哈希值
//rh[] 表示倒序的字符串哈希值
//p[i] 表示p的i次方
uint h[N], rh[N], p[N];

uint calc(uint h[], int l, int r) 
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

signed main()
{
    int T = 1;
    while (scanf("%s", s + 1), strcmp(s + 1, "END"))
    {
        n = strlen(s + 1);
        for (rint i = n * 2; i >= 1; i -= 2) 
		//在字符串的每两个字符之间插入一个相同的数
        {
            s[i] = s[i / 2];
            s[i - 1] = 'z' + 1;
        }
        n *= 2; //更新字符串的长度
        p[0] = 1; 
        for (rint i = 1, j = n; i <= n; i++, j--) 
        {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + s[i]; 
            rh[i] = rh[i - 1] * P + s[j]; 
        }

        int res = 0; 
		//记录最大回文串的长度
        for (rint i = 1; i <= n; i++)
		//枚举中间值
        {
            int l = 0, r = min(i - 1, n - i);
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                //如果两边的字符串相等说明当前边长已经是回文串，那么可以继续扩大边长
                if (calc(h, i - mid, i - 1) == calc(rh, n - (i + mid) + 1, n - (i + 1) + 1)) l = mid;
                else r = mid - 1; 
				//否则说明不是回文串，那么更大的边长也不能组成回文串，因此需要缩小边长
            }

            if(s[i - l] <= 'z') res = max(res, l + 1); 
			//如果头和尾是字符串中的字符，那么整个回文串的长度是边长+1
            else res = max(res, l); 
			//如果头和尾是额外添加的特殊字符，那么整个回文串的长度就是边长
        }
        printf("Case %lld: %lld\n", T++, res);
    }
    return 0;
}

P3435 OKR-Periods of Words

本题是一个字符串关于循环元的证明。

这里直接得出结论：对于字符串中每一位 i，s[i - ne[i] + 1 ~ i] 和 s[1 ~ ne[i]] 都是相等的，并且不存在更大的 ne 值满足这个条件

还能得出推论：最小循环节是 1-ne[i]，次小循环节是 1-ne[ne[i]] ，依次能得出一个字符串所有的循环节。

void get_next(char p[], int n)
{
    for (rint i = 2, j = 0; i <= n; i++)
    {
        while (j > 0 && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
}

signed main()
{
    scanf("%lld%s", &n, s + 1);
    get_next(s, n);
    for (rint i = 2, j = 2; i <= n; i++, j = i)
    {
        while (ne[j]) j = ne[j];
        if (ne[i]) ne[i] = j;//记忆化一下，不然会 TLE 30pts
        ans += i - j;
    }
    cout << ans << endl;
    return 0;
}

P5410 【模板】扩展 KMP

学的 George1123 佬的

这里只给出代码

int ans1, ans2;
int z[M];
char a[N], b[N];
char new_s[M];

void exKMP_getZ(char s[])
{
	int n = strlen(s);	
	for (rint i = 1, j = 0; i < n; i++)
	{
		int k = i - j;
		if (z[j] - k > 0) z[i] = min(z[k], z[j] - k);
		while (z[i] + i < n && s[z[i]] == s[z[i] + i]) z[i]++;
		if (z[j] - z[i] < k) j = i;
	}
}

signed main()
{
	scanf("%s%s", a, b);
	int la = strlen(a);	
	int lb = strlen(b);
	for (rint i = 0; i < lb; i++) new_s[i] = b[i];	
	for (rint i = lb, j = 0; i < la + lb; i++, j++) new_s[i] = a[j];
	
	exKMP_getZ(new_s);
	
	for (rint i = 0; i < lb; i++)
	{
		if (!i) ans1 ^= lb + 1;
		else ans1 ^= (min(z[i], lb - i) + 1) * (i + 1);			
	}
	for (rint i = 0; i < la; i++) ans2 ^= (min(z[i + lb], lb) + 1) * (i + 1);
	cout << ans1 << endl << ans2 << endl;
	
	return 0;
}

AcWing 142. 前缀统计

本题要求的是已知若干个字符串，然后查找出有多少个字符串是给定查询的字符串的前缀。

关于前缀的统计可以用 Trie 树来做，将已知的字符串全部加入 Trie 树中，在每个字符串的结尾节点做上标记。

然后在 Trie 树上查询给定的字符串，在查询这个字符串的路上到达的所有前缀都是字符串的前缀，每走到一个节点就将标记上累计的字符串个数累加到结果上。

int n, m;
int tr[N][27], tot = 1; 
int cnt[N];
char s[N];

void insert(char s[]) 
{ 
	int len = strlen(s), p = 1;
	for (rint k = 0; k < len; k++) 
	{
		int ch = s[k] - 'a';
		if (!tr[p][ch]) tr[p][ch] = ++tot;
		p = tr[p][ch];
	}
	cnt[p]++;
}

int search(char s[]) 
{
	int len = strlen(s), p = 1;
	int ans = 0;
	for (rint k = 0; k < len; k++) 
	{
		p = tr[p][s[k] - 'a'];
		if (!p) return ans;
		ans += cnt[p];
	}
	return ans;
}

signed main() 
{
	cin >> n >> m;
	for (rint i = 1; i <= n; i++) 
	{
		scanf("%s", s);
		insert(s);
	}
	for (rint i = 1; i <= m; i++) 
	{
		scanf("%s", s);
		cout << search(s) << endl;
	}
	return 0;
}

AcWing 143. 最大异或对

字典树不单单可以高效存储和查找字符串集合，还可以存储二进制数字

将每个数以二进制方式存入字典树，找的时候从最高位去找有无该位的异

void insert(int val) 
{ 
	int p = 1;
	for (rint k = 30; k >= 0; k--) 
	{
		int ch = val >> k & 1;
		if (!tr[p][ch]) tr[p][ch] = ++tot;
		p = tr[p][ch];
	}
}

int search(int val) 
{
	int p = 1;
	int ans = 0;
	for (rint k = 30; k >= 0; k--) 
	{
		int ch = val >> k & 1;
		if (tr[p][ch ^ 1]) 
		{ // 走相反的位
			p = tr[p][ch ^ 1];
			ans |= 1 << k;
		} 
		else 
		{ // 只能走相同的位
			p = tr[p][ch];
		}
	}
	return ans;
}

signed main() 
{
	cin >> n;
	for (rint i = 1; i <= n; i++) 
	{
		cin >> a[i];
		insert(a[i]);
		ans = max(ans, search(a[i]));
	}
	cout << ans << endl;
	return 0;
}

AcWing 144. 最长异或值路径

首先可以用深搜求出所有点到根节点的异或距离，由于在二进制中异或运算相当于减法，

因此对于 x->y 之间的异或路径长度即可求解

我们现在需要枚举所有点，对于每个点x都求出和它的异或路径的异或值最大的一个点 \(y\)，那么从 \(x\) 能走到的最长的异或路径也可求解

要从 \(n\) 个数中选出两个数，使得这两个数的异或值最大，可以使用 Trie 树快速求解

void add(int a, int b, int c)
{
	e[++idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}

void dfs(int x, int father, int sum)
{
    a[x] = sum;
    for (rint i = h[x]; i; i = ne[i])
    {
        int y = e[i];
        if (y == father) continue; 
		dfs(y, x, sum ^ w[i]);
    }
}

void insert(int val) 
{ 
	int p = 1;
	for (rint k = 30; k >= 0; k--) 
	{
		int ch = val >> k & 1;
		if (!tr[p][ch]) tr[p][ch] = ++tot;
		p = tr[p][ch];
	}
}

int search(int val) 
{
	int p = 1;
	int ans = 0;
	for (rint k = 30; k >= 0; k--) 
	{
		int ch = val >> k & 1;
		if (tr[p][ch ^ 1]) 
		{ 
			p = tr[p][ch ^ 1];
			ans |= 1 << k;
		} 
		else 
		{ 
			p = tr[p][ch];
		}
	}
	return ans;
}

signed main()
{
    cin >> n;
    for (rint i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dfs(0, 0, 0);
    for (rint i = 1; i <= n; i++) insert(a[i]);
    int res = 0;
    for (rint i = 1; i <= n; i++) res = max(res, search(a[i]));
    cout << res << endl;
    return 0;
}

AcWing 147. 数据备份

可以发现最优解中每两个配对的办公楼一定时相邻的，因此我们可以计算一下每两个相邻的办公楼之间的距离。

d[i] 表示第 \(i\) 个办公楼和第 \(i+1\) 个办公楼之间的距离。

那么问题就变成了从 d[] 数列中选 \(k\) 个数，使它们的和最小，并且相邻的两个数不能被同时选(任一办公楼都属于唯一的配对组)

如果 k = 1，答案就是 d[] 数列中的最小值。
如果 k = 2，答案则一定是以下两种情况：

    1. 选择最小值 d[i]，以及除了 d[i - 1], d[i], d[i + 1] 之外的其他数中的最小值
    1. 选择最小值两侧的两个数，d[i - 1] 和 d[i + 1]

很容易证明，如果不选 d[i - 1] 和 d[i + 1]，那么最优解一定选了 d[i]，选了 d[i] 后不能选 d[i - 1] 和 d[i + 1]，因此还选了这三个数以外的最小值。如果选了d[i - 1]或d[i + 1]其中一个，由于d[i]的最小值，那么这时将 d[i - 1] 或 d[i + 1] 换成 d[i] 答案会更小，因此在最优解只有以上两种情况，且 d[i] 两则的数要么都选要么都不选。

因此，我们可以先选上最小值 d[i]，然后把 d[i - 1], d[i], d[i + 1] 从数列中删去，再在原位置加入 d[i - 1] + d[i + 1] - d[i]，这时就变成了"从新的数列中选出不超过 \(k-1\) 个数，使它们的和最小，且相邻两个数不能同时选"这个子问题。

对于子问题，如果选了 d[i - 1] + d[i + 1] + d[i]，相当于去掉 d[i]，换上 d[i - 1] 和 d[i + 1]。如果没选，那么刚才选出的 d[i] 加上这次选出的最小值就是最优解。这样恰好涵盖了最优解的两种情况。

综上所述，得出了本题的算法：

建立一个链表，连接 \(n-1\) 个节点，分别表示 d[1], d[2], ..., d[n - 1]，即每两个办公楼之间的距离。再建立一个最小堆，
与链表构成映射关系(即堆中也有 \(n-1\) 个节点，权值分别是 d[1], d[2], ..., d[n - 1]，同时记录对应的在链表中的下标)。

每次取出堆顶，把权值累加到答案中，设堆顶对应链表节点的下标为 p，数值为 w[p]，在链表中删除 p, p->prev, p->next，
在同样的位置插入一个新节点 q，记录数值 w[q] = w[p->prev] + w[p->next] - w[p]。在堆中同时删除对应的 p->prev 和 p->next 的节点，
插入对应链表节点 q，权值为 w[q] 的新节点。

重复上述操作 \(K\) 次，就得到了最终答案。

int n, k;
int d[N];
int l[N], r[N]; 
//链表
int idx;
bool st[N]; 
//记录某个节点是否被删去
priority_queue<pii, vector<pii>, greater<pii> > h; 

void remove(int x) 
{ //删除链表中某个元素
	st[x] = 1; 
	//记录当前节点在堆中也被删除
	r[l[x]] = r[x];
	l[r[x]] = l[x];
}

signed main() 
{
	cin >> n >> k;
	for (rint i = 0; i < n; i++) cin >> d[i];
	for (rint i = n - 1; i > 0; i--) d[i] -= d[i - 1];
	d[0] = d[n] = inf; //设置两个边界哨兵
	for (rint i = 1; i < n; i++) 
	{
		l[i] = i - 1;
		r[i] = i + 1;
		h.push({d[i], i}); 
		//加入堆中
	}
	int res = 0; //记录最小总和
	for (rint i = 0; i < k; i++) 
	{
		while (st[h.top().second]) h.pop(); 
		//将所有应该删去的节点删去
		pii t = h.top(); 
		//取出堆顶
		h.pop();
		int v = t.first;
		int p = t.second, left = l[p], right = r[p];
		remove(left), remove(right); //删去两边的节点
		res += v; //累加值
		d[p] = d[left] + d[right] - d[p]; //修改值
		h.push({d[p], p}); //将修改后的节点放回堆中
	}
	cout << res << endl;
	return 0;
}

AcWing 241. 楼兰图腾

从左向右依次遍历每个数 \(a[i]\)，使用树状数组统计在 \(i\) 位置之前所有比 \(a[i]\) 大的数的个数、以及比 \(a[i]\) 小的数的个数。统计完成后，将 \(a[i]\) 加入到树状数组。

从右向左依次遍历每个数 \(a[i]\)，使用树状数组统计在 \(i\) 位置之后所有比 \(a[i]\) 大的数的个数、以及比 \(a[i]\) 小的数的个数。统计完成后，将 \(a[i]\) 加入到树状数组。

int n, a[N];
int l[N], r[N];
int c[N];
int A, V; 

int lowbit(int x) {return x & -x;}

void add(int x, int k) 
{ 
	for (rint i = x; i <= n; i += lowbit(i)) c[i] += k;
}

int ask(int x) 
{ 
	int ans = 0;
	for (rint i = x; i; i -= lowbit(i)) ans += c[i];
	return ans;
}

signed main() 
{
	cin >> n;
	for (rint i = 1; i <= n; i++) cin >> a[i];
	for (rint i = 1; i <= n; i++) 
	{ 
	//因为从左往右遍历并插值，所以在调用 ask 函数时 c 中存的都是第 i 个节点左边的值
		int y = a[i]; //当前节点的高度
		l[i] = ask(y - 1); //找到当前节点左边的比高度比 y 小的数的个数
		r[i] = ask(n) - ask(y);//找到当前节点左边的比高度比 y 大的数的个数
		add(y, 1);//把 y 插入到 c 数组中, 相当于建树
	}

	memset(c, 0, sizeof c);
	//准备从右往左读，再建一遍树

	for (rint i = n; i >= 1; i--) 
	{ 
		int y = a[i];
		l[i] *= ask(y - 1);
		A += l[i];
		//以 y 为最高点的总方案数为 (y 左边比 y 低的点数) * (y 右边比 y 低的点数)
		r[i] *= ask(n) - ask(y);
		V += r[i];
		//以 y 为最低点的总方案数为 (y 左边比 y 高的点数) * (y 右边比 y 高的点数)
		add(y, 1);
	}

	cout << V << " " << A << endl;
	return 0;
}

P3605 Promotion Counting

求某节点子树内比该节点的点权大的点的个数

int n, p[N], b[N], ans[N];
vector<int> e[N];

int c[N];
int lowbit(int x){ return x & -x;}
void add(int x, int y) 
{
	for (; x <= n; x += lowbit(x)) c[x] += y;
}
int query(int x)
{
	int ans = 0;
    for (; x; x -= lowbit(x)) ans += c[x];
    return ans;
}
	
void dfs(int x) 
{ 
	ans[x] = query(p[x]) - query(n); 
	for (auto y : e[x]) dfs(y); 
	ans[x] += (query(n) - query(p[x]));
	add(p[x], 1); 
}

signed main() 
{
	cin >> n;
	for (rint i = 1; i <= n; i++)
	{
		cin >> p[i];
		b[i] = p[i];
	}
		
	sort(b + 1, b + n + 1); 
	for (rint i = 1; i <= n; i++)
	{
		p[i] = lower_bound(b + 1, b + n + 1, p[i]) - b;		
	}

	for (rint i = 2; i <= n; i++) 
	{
		int x;
		cin >> x;
		e[x].push_back(i);
	}
	dfs(1);
	for (rint i = 1; i <= n; i++) cout << ans[i] << endl;
		
	return 0;
}

P4054 [JSOI2009] 计数问题

定义第一个维度为 \(x\)，第二个维度为 \(y\)，第三个维度为权值 \(c\)。

定义两个函数 \(add(x,y,c,d)\) 和 \(sum(x,y,c)\)。

  • \(add(x,y,c,d)\)：将左上角点坐标为 \((1,1)\)，右下角点坐标为 \((x,y)\) 的矩形中中权值 \(c\) 的格子的个数增加 \(d\)
  • \(sum(x,y,c)\) 统计左上角点坐标为 \((1,1)\)，右下角点坐标为 \((x,y)\) 的矩形中权值为 \(c\) 的格子的个数。

因此当进行操作 1 时，将原先的权值出现次数 \(-1\)，将修改后的权值的出现次数 \(+1\)；

当进行操作 2 时，根据容斥原理，易得答案为 \(sum(x2, y2, c) - sum(x2, y1 - 1, c) - sum(x1 - 1, y2, c) + sum(x1 - 1, y1 - 1, c)\)。

int lowbit(int x) {return x & (-x);}

void add(int x, int y, int k, int color) 
{
	for (rint i = x; i <= n; i += lowbit(i))
		for (rint j = y; j <= m; j += lowbit(j))
			c[i][j][color] += k;
}

int query(int x, int y, int color)
{
	int ans = 0;
	for (rint i = x; i; i -= lowbit(i))
		for (rint j = y; j; j -= lowbit(j))
			ans += c[i][j][color];
	return ans;
}

signed main() 
{
	cin >> n >> m;
	for (rint i = 1; i <= n; i++)
	{
		for (rint j = 1; j <= m; j++) 
		{
			cin >> color;
			a[i][j] = color;
			add(i, j, 1, color);
		}		
	}
	
	int T;
	cin >> T;
	while (T--)
	{
		int op;
		cin >> op;
		int x1, y1, x2, y2;
		if (op == 1) 
		{
			cin >> x1 >> y1 >> color;
			add(x1, y1, -1, a[x1][y1]);
			a[x1][y1] = color;
			add(x1, y1, 1, color);
		} 
		else 
		{
			cin >> x1 >> x2 >> y1 >> y2 >> color;
			cout << query(x2, y2, color) - query(x1 - 1, y2, color) - query(x2, y1 - 1, color) + query(x1 - 1, y1 - 1, color) << endl;
		}
	}
	return 0;
}

标签：ch,2024.4,int,rint,笔记,return,++,字符串,20
From： https://www.cnblogs.com/spaceswalker/p/18148065

相关文章

  • Living-Dream 系列笔记 第54期
    状压dp：是对dp状态表示的优化。若有多个维度，每个维度仅有\(0/1\)，则将状态转为一个二进制数，并以十进制数表示。位操作（全文背诵）：任意二进制数位\(\operatorname{and}\1\)得本身。任意二进制数位\(\operatorname{xor}\1\)得本身。任意二进制数位\(\o......
  • 原型设计——墨语笔记APP
    一、对比分析墨刀、Axure、Mockplus等原型设计工具的各自的适用领域及优缺点。墨刀、Axure、Mockplus等原型设计工具各有特色，下面我将从适用领域、优点和缺点三个方面对它们进行对比分析。1.墨刀适用领域：墨刀主要适用于快速原型设计和高保真度的交互设计，特别适合移动端应用、小......
  • （数据结构代码，总结，自我思考）=＞ { return 个人学习笔记； } 【To be continued~】
    俗话说“学而不思则罔”，是时候复习和整理一下自己先前的学习历程了！Chapter-One《BinarySearch》publicstaticintbinarySearch(int[]a,inttarget){inti=0,j=a.length-1;while(i<=j){intm=(i+j)>>>1;//求......
  • POI2011ROZ-Difference
    POI#Year2011#枚举#贪心枚举最后差最大的两个字符\(a,b\)，将原串中\(a\rightarrow1,b\rightarrow-1\)，其他标\(0\)原来的问题转化为强制包含\(1,-1\)的最大字段和问题，维护每个位置前最近的\(-1\)，贪心取最大的//Author:xiaruizeconstintMOD=1000000007;const......
  • POI2011PRO-Programming Contest
    POI#Year2011#Dinic#网络流#贪心容易想到拆点的费用流做法，但是二分再拆点的时间复杂度是不可接受的考虑因为每个的时间\(r\)是定值，所以不可能出现做题个数差超过\(1\)的情况所以每一轮每个分配一个，用\(Dinic\)在推进一次，知道满流//Author:xiaruizeconstintN=......
  • POI2011MET-Meteors
    POI#Year2011#整体二分整体二分板子，用树状数组维护即可//Author:xiaruizeconstintN=1e6+10;intn,m,t;vector<int>vec[N];structnode{ intl,r,x;}s[N];piia[N];structBIT{ inttr[N]; voidadd(intx,intv) { while(x<=m*2) { ......
  • POI2011LIZ-Lollipop
    POI#Year2011#构造#妙妙题假设能取到\(x\)，那么\(\forally\),\(x,y\)奇偶性相同，\(x>y\)，\(y\)一定可以是\(x\)的一个子区间，处理奇数和偶数的最大值，离线，从大到小做//Author:xiaruizeconstintN=1e6+10;intn,m;inta[N],s[N];piist,en;piiqry[N];p......
  • POI2011Lightning Conductor
    POI#Year2011#dp#决策单调性令\(dp_i=\max\limits_{j=1}^{i-1}{a_j+\sqrt{i-j})}\)\(w(j,i)=\sqrt{i-j}\)满足四边形不等式所以这个\(dp\)具有决策单调性，分治维护//Author:xiaruizeconstintN=5e5+10;intn;inta[N];doubledp[N];doublew(intx,inty......
  • POI2011KON-Conspiracy
    POI#Year2011#数学考虑按照\(deg\)排序，然后暴力加入，这样可以得到一个极大的子集方案数分两种，一种为从团内去掉一个\(deg=siz-1\)的点，或者是将一个团外的\(deg=siz-1\)的点与一个团内的交换//Author:xiaruizeconstintINF=0x3f3f3f3f3f3f3f3f;constintMOD=10......
  • POI2011INS-Inspection
    POI#树上问题#贪心考虑什么样的点合法，这个点需要尽可能的均匀的子树，手摸几个发现，当且仅当这个点是重心的时候是可行的那么贪心的来说，我们希望最后一个不需要回来的路径长度尽可能的大，搜索就可以做到特判当有一个子树的\(siz\)为\(\frac{n}{2}\)时，最后的路径一定在这棵树......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99