triangle

首先我们看数据规模。 它说 $N \le 300$，因此我们可以预测时间复杂度为 $O(N^3)$ 的解决方案将足够快地找到正确答案。 因此，如果我们能够穷尽地迭代所有三个点的组合，并且每个点都在 $O(1)$ 时间内检查它们是否形成一个具有正面积的三角形，我们就可以在足够短的时间内得到正确的答案。

现在，我们如何确定某些三个点是否形成一个三角形呢？实际上，我们可以使用以下公式。

具有顶点 $(x_1,y_1)$，$(x_2,y_2)$，和 $(x_3,y_3)$ 的三角形，其面积由以下公式表示：$\frac{1}{2} \times \left | (x_2- x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1) \right |$

（注意，如果该值为 $0$，则给定的三个点在一条共同的直线上。）

这一次，重要的是它是否形成一个三角形，因此，检查 $(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)$ 是否成立就足够了。

就是看三点中任意两点组成的直线方程的斜率是否相等。

one

首先，对数组$A$进行排序，使得$A_1 \le A_2 \le \dots \le A_N$。 答案可以表示为

$(X_i-A_1) + (X_i-A_2) +$

$\dots + (X_i-A_k) + (A_{k+1}-X_i)$

$+ \dots +(A_N-X_i)$

$=\sum\limits^{k}_{j=1} (X_i-A_j) +$$\sum^{N}_{j=k+1} (A_j-X_i).$$\sum\limits^{k}_{j=1} (X_i-A_j)$

$= kX_i - \sum\limits^{k}_{j=1} A_j$，其中$kX_i$可以在$O(1)$时间内计算出来，而$\sum^{k}_{j=1} A_j$则可以通过预处理出前缀和，在$O(N)$时间内完成，然后在每次查询时以$O(1)$时间计算出来。同样地，$\sum\limits^{N}_{j=k+1} (A_j-X_i)$也可以用类似的方式计算。

此外，我们可以通过二分查找在每次查询中以$O(\log N)$时间找到满足$A_k \le X_i \le A_{k+1}$的$k$。

因此，整个问题可以在$O(N + Q \log N)$时间内解决。

index(3s)

$\mathrm O (MQ)$ 解法

我们可以通过对每个查询执行 BFS（广度优先搜索）来找到从顶点 $x_i$ 到每个顶点的距离，并计算距离至多为 $k_i$ 的顶点的索引之和，从而得到每个查询的正确答案。然而，由于每个 BFS 需要 $O(M)$ 的时间，总时间复杂度为 $\mathrm O (MQ)$，这太慢了。

满足条件的顶点的观察

通过以下计算，我们可以发现从顶点 $x_i$ 到其距离至多为 $k_i(\leq 3)$ 的顶点并不多。

• 只有顶点 $x_i$ 的距离为 $0$。
• 只有与顶点 $x_i$ 相邻的顶点的距离为 $1$。由于它的度数最多为 $3$，因此最多有 $3$ 个这样的顶点。
• 只有与距离为 $1$ 的顶点相邻的顶点（部分）的距离为 $2$。由于最多有 $3$ 个顶点，每个顶点的度数最多为 $3$，因此最多有 $3 \times 3 = 9$ 个这样的顶点。
• 只有与距离为 $2$ 的顶点相邻的顶点（部分）的距离为 $3$。由于最多有 $9$ 个顶点，每个顶点的度数最多为 $3$，因此最多有 $9 \times 3 = 27$ 个这样的顶点。
• 上述顶点的总数为 $40$。

在上面的讨论中，我们通过将距离为 $k-1$ 的顶点数的 $3$ 倍来评估距离为 $k$ 的顶点数的上限，但我们可以将“$3$ 倍”替换为“$2$ 倍”，因为在距离至少为 $2$ 的顶点的三条相邻边中，至少有一条边来自距离更小的顶点。

无论如何，我们可以安全地重复枚举满足条件的顶点的索引，并找到它们的 $Q$ 次出现次数，而不用担心超时。

通过 BFS 或 DFS 枚举满足条件的顶点

因此，这个问题可以通过仅对距离至多为 $k_i$ 的顶点执行 BFS 来解决，即一旦到达距离为 $k_i$ 的顶点就停止 BFS。更多细节请参考示例代码。（我们存储访问过的顶点至 vs，以便仅使用距离数组中的某些元素，但使用集合或映射可能更容易）

此外，通过上述分析，深度优先搜索（DFS）也足够快。

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N,M;
	cin>>N>>M;
	vector<vector<int>> E(N);
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--,b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	vector<int> dis(N,-1);
	
	int Q;
	cin>>Q;
	
	for(int i=0;i<Q;i++){
		int x,k;
		cin>>x>>k;
		x--;
		queue<int> q;
		q.push(x);
		dis[x] = 0;
		vector<int> vs;
		while(q.size()>0){
			int u = q.front();
			q.pop();
			vs.push_back(u);
			if(dis[u]==k){
				continue;
			}
			for(int j=0;j<E[u].size();j++){
				int v = E[u][j];
				if(dis[v]!=-1)continue;
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
		int ans = 0;
		for(int j=0;j<vs.size();j++){
			ans += vs[j]+1;
			dis[vs[j]] = -1;
		}
		cout<<ans<<endl;
	}
	
    return 0;
}

logic

由于操作是独立的位运算，我们可以独立考虑每一位。

将操作 $i$ 视为从 $\{0,1\}$ 到 $\{0,1\}$ 的函数 $f_i$。通过在计算组合函数 $f_i\circ f_{i-1}\circ\ldots \circ f_1$ 时，用一对 $(f(0),f(1))$ 来表达 $f$，问题可以在总共 $O(N\log A)$ 时间内解决。

参考代码（C++）1

#include<bits/stdc++.h>
using namespace std;
#define bit(x,i)(((x)>>(i))&1)

int main(){
	int n,c;
	cin >> n >> c;
	vector<pair<int,int>>op(n);
	for(int i=0;i<n;i++)cin >> op[i].first >> op[i].second;

	vector<int>ans(n);
	for(int k=0;k<30;k++){
		array<int,2>func={0,1};
		int crr=bit(c,k);
		for(int i=0;i<n;i++){
			array<int,2>f;
			int x=bit(op[i].second,k);
			if(op[i].first==1)f={0&x,1&x};
			if(op[i].first==2)f={0|x,1|x};
			if(op[i].first==3)f={0^x,1^x};
			func={f[func[0]],f[func[1]]};
			crr=func[crr];
			ans[i]|=crr<<k;
		}
	}

	for(int i=0;i<n;i++)cout << ans[i] << endl;
return 0;
}

做法二

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2e5 + 5;
int op[N], a[N], ans[N];
int main()
{
	int n, val;
	scanf("%d%d", &n, &val);
	for (int i = 1; i <= n; i++) scanf("%d%d", &op[i], &a[i]);
	for (int d = 0; d <= 30; d++)
	{
		bool sum = (val & (1 << d)); int cov = -114514, rev = 0;
		for (int i = 1; i <= n; i++)
		{
			bool x = (a[i] & (1 << d));
			if (op[i] == 1) {sum &= x; if (x == 0) cov = 0, rev = 0;}
			if (op[i] == 2) {sum |= x; if (x == 1) cov = 1, rev = 0;}
			if (op[i] == 3) {/*sum ^= x;*/ if (x == 1) rev++;}
			
			if (cov != -114514) sum = cov;
			if (rev & 1) sum ^= 1;
			if (sum) ans[i] += (1 << d);
		}
	}
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}

rle

考虑一个动态规划（DP），其中我们定义 $\mathrm{dp}[i][j] 表示($ 长度为 $i$ 的字符串 $S$ 与长度为 $j$ 的字符串 $T$ 的数量)。考虑到追加一个 $k$ 字符的重复部分，其中 $S_i \neq S_{i+1}$ 且 $S_{i+1}=S_{i+2}=\dots =S_{i+k}$，我们可以写出如下转移方程：

$ dp(i+k)(j+1+{k 的位数})+=dp(i)(j) \times 25 (1 \le k \le N) $ 。

然而，此 DP 的时间复杂度为 $\mathrm{O}(N^3)$。由于 $\lceil \log_{10} (N+1) \rceil$ 种 $1+k$ 的位数，故可以通过一次性处理具有相同 $1+k$ 位数的转移，并在进行 DP 时采取累计求和的方式对其进行优化。现在每个转移花费 $\mathrm{O}(\log N)$ 时间，因此问题可以在总时间为 $\mathrm{O}(N^2\log N)$ 的情况下解决。 参考代码（C++）：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }

ll dp[3101][3101];
ll sum[3101][3101];
int main() {
  ll n,p;
  cin>>n>>p;
  dp[0][0]=modPow(25,p-2,p)*26ll%p;
  vector<ll> ten={1,10,100,1000,10000,100000};
  for(int i=1;i<=n;i++) sum[0][i]=dp[0][0];
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      for(int k=1;k<=4;k++){
        if(i-k-1<0) continue;
        ll x=max(j-ten[k-1]+1,0ll),y=max(j-ten[k]+1,0ll);
        dp[i][j]+=(sum[i-k-1][x]-sum[i-k-1][y]+p)*25;
        dp[i][j]%=p;
      }
      sum[i][j+1]=sum[i][j]+dp[i][j];
      sum[i][j+1]%=p;
    }
  }
  ll sum=0;
  for(int i=1;i<n;i++) sum+=dp[i][n];
  cout<<sum%p<<endl;
return 0;
}

另一题解：

ABC249E (tsawke.com)