大二上第五周学习笔记

最近有点平衡不了绩点科研竞赛

这周要回归了 提高效率 平衡好

B - Reverse Game（博弈论）

这道题的关键是转化为把1全部放到右边游戏就结束了

所以每次操作可以使得1左1个或者2个

那么就可以转化为取石子的模型，n个石子，每次取1个或2个

判断是不是3的倍数就行了

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

int main()
{
    string s;
    cin >> s;
    int len = s.size();

    long long sum = 0, cnt = 0;
    rep(i, 0, len)
        if(s[i] == '1')
        {
            sum += len - i - 1;
            cnt++;
        }
    sum -= cnt * (cnt - 1) / 2;

    if((sum % 3) == 0) puts("Bob");
    else puts("Alice");

    return 0;
}

M - Mistake（贪心）

是一个很巧妙的贪心

把每个数分配到当前能分配到的最小的编号里去

依照这种方式构造的答案是最完善的，又保证有解

所以输入的图白给了

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 5e5 + 10;
int a[N], n, m, k;

int main()
{
    scanf("%d%d%d", &n, &k, &m);
	while(m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
	}
	_for(i, 1, n * k)
	{
		int x; scanf("%d", &x);
		printf("%d ", ++a[x]);
	}

    return 0;
}

Shuffle Cards（stl rope）

这道题就是用平衡树做的

但是有一个骚方法，用stl容器 rope

其内部是平衡树实现的

这个容器是用来处理字符串的，可以在logn内实现区间插入，区间删除，区间替换

数组查询O（1） 删除O（n）

链表查询O（n）删除O（1）

而这个容器，也就是平衡树，是查询O（logn） 删除O（logn）

首先要加头文件 注意万能头不包括，还要加一个using namespace

#include <ext/rope>
using namespace __gnu_cxx;

操作如下

参考[rope大法好] STL里面的可持久化平衡树--rope - viv - 博客园

rope<int> r, x;
r.push_back(x)     // 在末尾添加x
r.insert(pos,x)    // 在pos插入x 区间插入
r.erase(pos,x)     // 从pos开始删除x个 区间删除
r.replace(pos,x)   // 从pos开始换成x 区间替换
r.substr(pos,x)    // 提取pos开始x个

此题AC代码，直接提取区间相加就好了

#include <bits/stdc++.h>
#include <ext/rope>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
using namespace __gnu_cxx;

int main()
{
	rope<int> r;
	int n, m;

	scanf("%d%d", &n, &m);
	_for(i, 1, n) r.push_back(i);
	while(m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		r = r.substr(a - 1, b) + r.substr(0, a - 1) + r.substr(a + b - 1, n - a - b + 1);
	}
	rep(i, 0, n) printf("%d ", r[i]); puts("");

    return 0;
}

E  Sort String(哈希 + 输出优化)

其实就是迅速处理出这个字符串之前有没有出现过

套路是哈希配合unordered_map

我交了一发T了

这个输出巨大，所以我就加了一个输出优化

输出优化其实很简单，就是用putchar

把数拆成一位一位的然后用putchar输出

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef unsigned long long ull;
const int N = 2e6 + 10;
const int base = 131;
unordered_map<ull, int> mp;
vector<int> ans[N];
ull Hash[N], p[N];
char s[N];
int n;

ull get_hash(int l, int r)
{
	return Hash[r] - Hash[l - 1] * p[r - l + 1]; 
}

int w[60];
void write(int x)
{
	int t = 0;
	while(x)
	{
		w[++t] = x % 10;
		x /= 10;
	}
	if(!t) putchar('0');
	for(int i = t; i >= 1; i--) putchar(w[i] + '0');

}

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	_for(i, 1, n) s[n + i] = s[i];

	p[0] = 1;     //不要漏这句
	_for(i, 1, 2 * n) 
	{
		p[i] = p[i - 1] * base;
		Hash[i] = Hash[i - 1] * base + s[i];
	}

	int cnt = 0;
	_for(i, 1, n)
	{
		ull cur = get_hash(i, i + n - 1);
		if(!mp[cur]) mp[cur] = ++cnt;
		ans[mp[cur]].push_back(i - 1);
	}

	write(cnt); puts("");
	_for(i, 1, cnt)
	{
		write(ans[i].size()); putchar(' ');
		for(auto x: ans[i]) write(x), putchar(' ');
		puts("");
	}

	return 0;
}

E  Sort String(KMP循环节)

这题还有一种做法

如果满足相等，一定是是有循环节

证明比较感性 用纸笔画一画

所以用kmp判断循环节就可以了

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e6 + 10;
int Next[N], n, num, cnt;
char s[N];

void get_next()
{
	Next[0] = -1;
	int i = 0, j = -1;
	while(i < n)
	{
		if(j == -1 || s[i] == s[j])
		{
			i++; j++;
			Next[i] = j;
		}
		else j = Next[j];
	}
}

int main()
{
	scanf("%s", s);
	n = strlen(s);

	get_next();
	if(n % (n - Next[n])) num = 1;
	else num = n / (n - Next[n]);
	cnt = n / num;
	
	printf("%d\n", cnt);
	_for(i, 1, cnt)
	{
		printf("%d ", num);
		_for(j, 0, num - 1) printf("%d ", i - 1 + cnt * j);
		puts("");
	}

	return 0;
}

J.farm(哈希 + 随机化)

这道题看到一个很骚的做法

就是如果没有枯萎，那么把施肥的种类加起来模花的种类等于0

但是数字很小的时候就不行 比如1 + 2 = 3 和3

那么我们可以用哈希，映射到一个很大的值，就很难出现这种情况

为了大且随机，我们可以用随机化，也就是乘以一个rand

之前比赛有一道构造题，数据范围很小，可以在很短的时间内验证，因此可以随机化构造答案

随机化是个方法

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
vector<ll> a[N], b[N];
int n, m, t;
ll Hash[N];

int main()
{
	srand(time(0));
	_for(i, 0, 1e6) Hash[i] = i * i + i * rand();
	scanf("%d%d%d", &n, &m, &t);
	_for(i, 0, n + 10) a[i].resize(m + 10), b[i].resize(m + 10);
	_for(i, 1, n)
		_for(j, 1, m)
		{
			int x; scanf("%d", &x);
			b[i][j] = Hash[x];
		}

	while(t--)
	{
		int x1, y1, x2, y2, k;
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
		a[x1][y1] += Hash[k];
		a[x2 + 1][y1] -= Hash[k];
		a[x1][y2 + 1] -= Hash[k];
		a[x2 + 1][y2 + 1] += Hash[k];
	}

	int ans = 0;
	_for(i, 1, n)
		_for(j, 1, m)
		{
			a[i][j] += -a[i - 1][j - 1] + a[i - 1][j] + a[i][j - 1];
			if(a[i][j] % b[i][j]) ans++;
		}
	printf("%d\n", ans);

	return 0;
}