题目大意

按照格雷码的生成方式，输出 n 位格雷码的第 k 号二进制串。（从 0 开始编号）

思路

填完第 k 个 n 位格雷码的第 1 位后，把它转化成某一个 n−1 位格雷码继续填这个 n−1 位格雷码的第 1 位，以此类推。

如何确定转化成第几个 n−1 位格雷码：

当 k<2n−1，因为这个 n 位格雷码的前 2n−1 个二进制串的后 n−1 位是由 n−1 位格雷码正序排列而成的，所以 k 保持不变。

当 k≥2n−1，因为这个 n 位格雷码的后 2n−1 个二进制串的后 n−1 位是由 n−1 位格雷码逆序排列而成的，所以 k 要先减去 2n−1，变成 n−1 位格雷码，再翻转才能保证是逆序的，即 k=r-k+l

不妨设 \( n \leq m \)。 那原式：

$= \sum_{i = 1} ^ n (n \bmod i) \times \sum_{j = 1} ^ m (m \bmod j) - \sum_{i = 1} ^ n (n \bmod i) \times (m \bmod i)$

$= \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \times \sum_{j = 1} ^ m \left( m - \left\lfloor \frac{m}{j} \right\rfloor \times j \right) - \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \left( m - \left\lfloor \frac{m}{i} \right\rfloor \times i \right)$

$= \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \times \sum_{j = 1} ^ m \left( m - \left\lfloor \frac{m}{j} \right\rfloor \times j \right) - \sum_{i = 1} ^ n \left( nm - n \times i \times \left\lfloor \frac{m}{i} \right\rfloor - m \times i \times \left\lfloor \frac{n}{i} \right\rfloor + i ^ 2 \times \left\lfloor \frac{n}{i} \right\rfloor \times \left\lfloor \frac{m}{i} \right\rfloor \right)$

显然对这 3 坨数论分块就可以了

最小割必刷题！

首先我们先把棋盘看作二分图黑白染色，比如我们可以把横纵坐标加起来为奇数的看作黑，偶数看作白。

考虑到一个黑色节点只会对它四周的节点产生影响，不难想到我们直接把把源点往所有黑点连边权为这个点在棋盘上的数的边，白点同理，只是往汇点连边，然后相邻的方格之间连无穷大的边，这样这些边就不会被算在割边中。

那我们对于舍弃一个点，就是把这个点往源点或汇点的边割掉，dinic跑最小割即可。（ISAP不会写QAQ)

一道好题。

这是一个树形结构，我们可以先拍成 $dfn$ 序，然后对于每个星球，本质上就是在其子树内区间再 删去一些小子树 所构成的一些区间，因为最多 $n$ 个操作，所以区间最多 $\mathcal{O}(n)$ 个，线段树分治，把这些区间插入，然后我们考虑如何求答案。

$y,z$ 是没用的，最终答案即为 $(x_0 - x)^2 + c$，拆开得 $- 2x_0x + {x_0}^2 + x^2 + c$。

我们考虑斜率优化，在看这个式子 $s = - 2x_0x + {x_0}^2 + x^2 + c$，移项得 $x^2 + c = 2x_0x - {x_0}^2 + s$，即点 $(x,x^2 + c)$ 斜率为 $2x_0$，维护下凸包即可，若二分则复杂度是 $\mathcal{O}(n\log^2{n})$，只需将 $x$ 与斜率 $x_0$ 都从小到大排序，我们可以利用单调栈达成 $\mathcal{O}(n\log{n})$ 的复杂度。

http://218.28.19.228:8081/cogs/index.php书架二题解

书架2的问题可以转化为求集合中所有子集的问题（每个牛堆是一个子集）用牛高度的加和减书架高度，求最小值。

本题有两种方法

1.搜索 2.状态压缩

状态压缩求子集：

用一个二进制数表示是否选取某个集合元素（1为子集中有此位置元素，0为没有），每次+1，枚举所有子集

下面是状态压缩代码

#include<bits/stdc++.h> 
using namespace std;
int er[25]={0};
int ii=0;
void erj(int a)
{
    while(a!=0)
    {
        er[ii]=a%2;
        a/=2;
        ii++;
    }
}
int main()
{
    freopen("shelf2.in","r",stdin);
    freopen("shelf2.out","w",stdout);
    int n,b;
    cin>>n>>b;
    int a=pow(2,n+1);
    int n1[25]={0};
    for(int i=0;i<n;i++)cin>>n1[i];
    int sum=0,ans=9999999;
    for(int i=0;i<a;i++)
    {
        erj(i);
        for(int j=0;j<ii;j++)
        {
            if(er[j])sum+=n1[j];
        }
        if(sum>=b)
        {
            ans=min(ans,sum-b);
        }
        sum=0;
        ii=0;
        memset(er,0,sizeof(er));
    }
    cout<<ans;
    return 0;
}

 更新时间：

  2001.9.11

COGS 1825 [USACO Jan11]道路与航线

由于 $T \leq 25000,R+P \leq 100000$ ，优先考虑SPFA，

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	memset(p, 0, sizeof(p));
	queue<int> q;
	q.push(s);
	vis[s] = true;
	d[s] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		vis[x] = 0;
		for (int i = 0; i < v[x].size(); i++) {
			if (d[v[x][i].first] > d[x] + v[x][i].second) {
				d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
				if (!vis[v[x][i].first]) q.push(v[x][i].first), vis[v[x][i].first] = true;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> R >> P >> S;
	for (int i = 1; i <= R; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= P; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
	SPFA(S);
	for (int i = 1; i <= T; i++) {
		if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
		else cout << d[i] << endl;
	}
	return 0;
}

最终评测T两个点，考虑换方法。

查看资料注意到SPFA有双端队列优化和优先队列优化，优先队列复杂度 $O(logn)$，故不考虑。双端队列优化思路是：将要加入的节点与队头比较，小于等于插到队头，大于则插到队尾，时间复杂度接近 $O(1)$。

重写代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	memset(p, 0, sizeof(p));
	deque<int> q;
	q.push_back(s);
	vis[s] = true;
	d[s] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop_front();
		vis[x] = 0;
		for (int i = 0; i < v[x].size(); i++) {
			if (d[v[x][i].first] > d[x] + v[x][i].second) {
				d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
				//主要改动如下
				if (!vis[v[x][i].first]) {
					if (d[v[x][i].first] <= d[q.front()]) q.push_front(v[x][i].first);
					else q.push_back(v[x][i].first);
					vis[v[x][i].first] = true;
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> R >> P >> S;
	for (int i = 1; i <= R; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= P; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
	SPFA(S);
	for (int i = 1; i <= T; i++) {
		if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
		else cout << d[i] << endl;
	}
	return 0;
}

后记

在知乎上看到文章关于SPFA的各种优化以及对应hack，可以参考（如何看待 SPFA 算法已死这种说法？ - 知乎 (zhihu.com)）。