11.16 NOIP模拟赛

A. 长春花
给定一个素数 p，对每个 0≤x<p，设 f(x) 表示一个最小的非负整数 a，使得存在一个非负整数 b，满足 (a2+b2)mod p=x。
现在，你想要求 max{f(0),f(1),⋯,f(p−1)} 的值。

解:直接暴力。

#include <bits/stdc++.h>
using namespace std;
mt19937 hua(20041115);
const int N = 5e5 + 50;
int sq[N];
int main() {
	int p;
	cin >> p;
	memset(sq, -1, sizeof sq);
	for (int i = 0; i < p; ++i)
		sq[1ll * i * i % p] = i;
	int mx = -1;
	for (int i = 0; i < p; ++i) {
		bool ok = false;
		for (int a = 0; a < p; ++a) {
			int b = ((i - 1ll * a * a) % p + p) % p;
			if (sq[b] != -1) {
				ok = true;
				mx = max(a, mx);
				break;
			}
		}
		assert(ok);
	}
	cout << mx << '\n';
}

B. 紫罗兰

给定一张 n 个顶点 m 条边的无向图，顶点的编号在 1∼n 内，第 i 条无向边连接着顶点 xi​ 与 yi​。我们称顶点 v0​,v2​,⋯,vk−1​ 构成了一个大小为 k 的环，当且仅当 k≥3，且对任意 0≤i<k，图中都存在一条连接顶点 vi​ 与 v(i+1)mod k​ 的无向边。我们称一个环 C 为最小环，当且仅当图中不存在一个大小严格小于 C 的环。
现在，你想要求出，图中有多少本质不同的最小环。
我们称两个环 C1​(u0​,u1​,⋯,uk−1​) 与 C2​(v0​,v1​,⋯,vk−1​) 不同，当且仅当组成这两个环的边不同。

解:
首先，我们求出图中的最小环长 。由于图中边无权，因此对于一个固定的顶点 ，我们可以使用 BFS在 的时间复杂度内计算出包含 的最小环的长度。具体地，我们维护 表示从 出发到顶点 的最短路。当我们从 第一次访问到一个顶点 时，更新其对应的 值，否则我们可以找到一个长度为 的环。注意到虽然我们不能保证该环为简单环，但注意到我们找到的所有环在去除公共部分后一定是一个简单环，因此我们对所有环取 min 一定可以得到最小环长。对于计数部分，我们直接在计算最小环长时顺便统计方案数即可.
我们发现：

1. 以环上的任意一点为起点均会统计该环一次，因此答案要除以 。
2. 当 为偶数时，每个环会从两个方向上各被统计一次，因此答案要额外再除以 。

#include <bits/stdc++.h>
using namespace std;
mt19937 hua(20041115);
const int N = 6005;
int n, m, dist[N], ways[N], len = 0x3f3f3f3f;
long long cnt = 0;
vector<int> G[N];
void gogo(int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(ways, 0, sizeof ways);
    queue<int> que;
    que.push(s);
    dist[s] = 0;
    ways[s] = 1;
    while (!que.empty()) {
        int x = que.front(); que.pop();
        for (int y : G[x]) {
            if (dist[x] == dist[y] || dist[x] + 1 == dist[y]) {
                int cyc = dist[x] + dist[y] + 1;
                long long c = ways[x] * ways[y];
                if (cyc < len) {
                    len = cyc;
                    cnt = c;
                }
                else if (cyc == len) {
                    cnt += c;
                }
            }
            if (dist[y] > dist[x] + 1) {
                dist[y] = dist[x] + 1;
                ways[y] = ways[x];
                que.push(y);
            }
            else if (dist[y] == dist[x] + 1) {
                ways[y] += ways[x];
            }
        }
    }   
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (int x = 1; x <= n; ++x) {
        gogo(x);
    }
    if (len % 2) {
        cnt /= len;
        cnt /= 2;
    }
    else {
        cnt /= len;
    }
    cout << cnt << "\n";
}

原文地址：http://www.cnblogs.com/mrkou/p/16897120.html