2020牛客寒假算法基础集训营1

题目链接：

https://ac.nowcoder.com/acm/contest/3002

A题

思路：

既然三角形面积为1且有一条边平行于坐标轴，那么这条边为1或者2，我们枚举1平行于x/y轴的情况，加上2平行于x/y轴的情况，再减去（重复的）1、2都平行于坐标轴的情况即是答案；
注意计算的过程中每一步都需要取余；

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
ll n, m;

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	cin >> n >> m;
	ll x = (m - 1) * m % mod * (n - 2) % mod * 2ll % mod + (n - 1) * n % mod * (m - 2) % mod * 2ll % mod;
	x %= mod;
	ll y = (m - 2) * m % mod * (n - 1) % mod * 2ll % mod + (n - 2) * n % mod * (m - 1) % mod * 2ll % mod;
	y %= mod;
	ll z = (m - 1) * 2ll % mod * (n - 2) % mod * 2ll % mod + (n - 1) * 2ll % mod * (m - 2) % mod * 2 % mod;
	ll ans = x + y - z;
	if(ans < 0) ans += mod;
	cout << ans % mod;
	return 0;
}

B题

思路：

很简单的期望题

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	int n, x, a, b;
	cin >> n >> x >> a >> b;
	printf("%.2f", (x / 100.0 * a + (100 - x) / 100.0 * b) * 1.0 * n);
	return 0;
}

C题

思路：

对于每一个靶子，我们将它和umi连接起来，如果这条线段和坐标轴有交点，我们将它记录下来；
对于每个交点，如果我们覆盖到这个交点，则我们可以挡住该靶子；
然后我们分别升序遍历xy轴的所有交点即可；
注意：
1.需要用printf输出不能用cout，不然会wa，可能是精度问题？
2.牛客的编译器的y0好像是保留字，不要设y0就好；

代码：

#include<bits/stdc++.h>

using namespace std;

double x0;
double Y0;
int n, k;
vector<double> x, y;
inline void deal(double & x1, double & y1) {
    double xx;
    xx = x1 == x0 ? x0 : -Y0 * (x1 - x0) / (y1 - Y0) + x0;
    if(xx >= min(x0, x1) && xx <= max(x0, x1)) x.push_back(xx);
    double yy;
    yy = y1 == Y0 ? Y0 : Y0 - x0 * (y1 - Y0) / (x1 - x0);
    if(yy >= min(Y0, y1) && yy <= max(Y0, y1)) y.push_back(yy);
}

int main() {
#ifdef MyTest
    freopen("Sakura.txt", "r", stdin);
#endif
    cin >> x0 >> Y0 >> n >> k;
    for(int i = 0; i < n; i++) {
        double a, b;
        cin >> a >> b;
        deal(a, b);
    }
    double ans = double(1ll << 60);
    k = n - k;
    if(x.size() >= k) {
        sort(x.begin(), x.end());
        for(int i = 0; i + k - 1 < x.size(); i++) {
            ans = min(ans, x[i + k - 1] - x[i]);
        }
    }
    if(y.size() >= k) {
        sort(y.begin(), y.end());
        for(int i = 0; i + k - 1 < y.size(); i++) {
            ans = min(ans, y[i + k - 1] - y[i]);
        }
    }
    if(x.size() >= k || y.size() >= k) printf("%lf", ans);
    else cout << -1;
    return 0;
}

D题

思路：

简单数学题

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif
	int n;
	cin >> n;
	int ans = (1 + n) * n / 2;
	for(int i = 1; i < n; i++) {
		int x;
		cin >> x;
		ans -= x;	
	}
	cout << ans;
	return 0;
}

E题

思路：

写一个O(n)O(sqrt{n})复杂度的求因子个数的函数即可

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
inline ll get(ll n) {
	ll ans = 0;
	for(ll i = 1; i * i <= n; i++) {
		if(n % i == 0) {
			++ans;
			if(i != n / i) ++ ans;
		}
	}
	return ans;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	ll n;
	cin >> n;
	int ans = 0;
	while(n != 2) {
		n = get(n); //cerr << n << ' ';
		++ans;	
	}
	cout << ans;
	return 0;
}

F题

思路：

我们以每一个黑点为源点，分别计算以它的孩子为根结点的子树拥有多少结点，其中遍历到其它黑色结点即停止遍历；
剩下的就是简单计数问题了；
// ------------------------------------
经网友提醒，原代码会TLE，已修改代码；
1.每次从黑点dfs到另一个黑点时记录下来，那么下次从被遍历到的那个黑点dfs时，那一条边无需重复遍历；
2.在计数时，为了避免数组过大，不用O(n2)O(n^2)的方法逐个相加，而用求和递减的方式可以在O(n)O(n)的时间内求出来；

代码：

#include<bits/stdc++.h>

using namespace std;

inline int read() {
	int x = 0; char c;
	while(c = getchar(), c < '0' || c > '9');
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x;
}

const int maxn = 1e5 + 5;
char s[maxn];
unordered_map<int, int> mp[maxn];
int n;
bool vst[maxn], b[maxn];
vector<int> G[maxn];
typedef long long ll;
typedef pair<int, int> P;
vector<P> sv;

ll dfs(int u) {
	vst[u] = true;
	ll res = 1;
	for(int & x : G[u]) if(!vst[x]) {
		if(b[x]) sv.push_back(P(x, u));
		else res += dfs(x);
	}
	return res;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	n = read();
	scanf("%s", s);
	for(int i = 0; i < n; i++) if(s[i] == 'B') b[i + 1] = true;
	for(int i = 1; i < n; i++) {
		int x = read(), y = read();
		G[x].push_back(y), G[y].push_back(x);	
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) if(b[i]) {
		vector<int> v;
		ll sum = 0;
		for(int & x : G[i]) {
			if(b[x]) continue;
			sv.clear();
			ll res = mp[i][x] ? mp[i][x] : dfs(x);
			if(res) v.push_back(res), sum += res;
			if(sv.size()) for(P & p : sv) mp[p.first][p.second] = res;	
		}
		ans += sum;
		for(int i = 0; i < v.size(); i++) {
			sum -= v[i];
			ans += v[i] * sum;
		}
	}
	printf("%lld", ans);
	return 0;
}

G题

思路：

对于每一个字母，我们用vector存储它出现过的位置；
然后分别遍历26个字母，对于单个字母，我们遍历该字母的出现位置序列，计算该字母出现k次时的最短序列长度；

代码：

#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;
int n, k;
string s;
vector<int> p[30];

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif
	cin >> n >> k >> s;
	for(int i = 0; i < s.length(); i++) {
		p[s[i] - 'a'].push_back(i);	
	}
	int ans = INF;
	for(int i = 0; i < 26; i++) {
		if(p[i].size() < k) continue;
		for(int j = 0; j + k - 1 < p[i].size(); j++) {
			ans = min(ans, p[i][j + k - 1] - p[i][j]);	
		}
	}
	if(ans != INF) cout << ans  + 1;
	else cout << -1;
	return 0;
}

H题

思路：

假设目前我们把1变为0，可以变k个；
除去所有的0，我们知道我们需要变的这k个1必定是相邻的；
那么，对于每一个1，我们假设它是这段我们需要变的序列的第一个1，那么对于这段序列，我们找到这段序列的左边第一个1的位置为p，右边第一个1的位置为q，那么此刻该序列的长度就是q-p+-1；
对于将0变成1的思想是同理的；

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
int n, k;
vector<int> a, b;
int aa[maxn], bb[maxn];

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif
	string s;
	cin >> n >> k >> s;
	for(int i = 0; i < n; i++) {
		if(s[i] == '0') aa[i] = a.size(), a.push_back(i);
		else bb[i] = b.size(), b.push_back(i);
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		if(s[i] == '0') {
			int p = aa[i];
			int lf = p ? a[p - 1] : -1;
			int rt = p + k < a.size() ? a[p + k] : n;
	//		cout << i << ' ' << p << ' ' << lf << ' ' << rt << '
';
			ans = max(ans, rt - lf - 1);
		}else {
			int p = bb[i];
			int lf = p ? b[p - 1] : -1;
			int rt = p + k < b.size() ? b[p + k] : n;
	//		cout << i << ' ' << p << ' ' << lf << ' ' << rt << '
';
			ans = max(ans, rt - lf - 1);
		}	
	}
	cout << ans;
	return 0;
}

I题

思路：

设dp[i]是以字符串中第i个字符为末尾所能得到的 最大分数
遍历字符串，如果以当前字符为首的子串分别满足nico niconi niconiconi，就更新dp即可；

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + 5;
typedef long long ll;
int n;
ll a, b, c, dp[maxn];

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif
	string s;
	cin >> n >> a >> b >> c >> s;
	s = "0" + s;
	for(int i = 1; i <= n; i++) {
		if(i + 3 <= n && s.substr(i, 4) == "nico") {
			dp[i + 3] = max(dp[i + 3], dp[i - 1] + a);
			if(i + 5 <= n && s.substr(i, 6) == "niconi") {
				dp[i + 5] = max(dp[i + 5], dp[i - 1] + b);
				if(i + 9 <= n && s.substr(i, 10) == "niconiconi") {
					dp[i + 9] = max(dp[i + 9], dp[i - 1] + c);
				}
			}
		}
		dp[i] = max(dp[i], dp[i - 1]);
	}
	cout << dp[n];
	return 0;
}

J题

思路：

1.最后的结果一定可以表示为f(n)=ae1∗be2∗xe3f(n)=a^{e1}*b^{e2}*x^{e3}，则目前的目标就是将这三个指数求出来；
2.这三个指数的值一定非常大，远远超过long long所能表达的范围，因此我们采用费马小定理将它们限定在一定范围内，即利用公式ap−1≡1(modp)a^{p-1}equiv1(mod p)，则可以在计算指数时，进行取余1e9+61e9+6的操作；但是注意费马小定理只有在整数aa不是指数pp的倍数时才可以使用，因此需要特判题目中x,y,a为1e9+71e9+7的倍数的情况；
3.对于指数e1e1和e2e2的计算，我们可以发现它们遵从斐波那契数列的规律，这里设f(n)f(n)是斐波那契数列的第nn项，则有e1=f(n−2),e2=f(n−1)e1=f(n-2),e2=f(n-1)，计算斐波那契数列第nn项我们可以使用矩阵快速幂在O(log(n))O(log(n))时间内快速求得，这里给出递推矩阵：
[1110]∗[f(n)f(n−1)]=[f(n+1)f(n)] left[ egin{matrix} 1 & 1 \1& 0 end{matrix} ight]* left[ egin{matrix} f(n) \f(n-1) end{matrix} ight]= left[ egin{matrix} f(n+1)\f(n) end{matrix} ight]
4.对于指数e3e3的计算，我们不难发现第nn项的数值等于前两项的和加上11，即设f(n)f(n)表示第nn项e3e3的值，则有f(n)=f(n−1)+f(n−2)+1f(n)=f(n-1)+f(n-2)+1，是不是和斐波那契数列很像QAQ，因此同样的我们使用矩阵快速幂求第nn项的值，这里给出递推矩阵：
[111100001]∗[f(n)f(n−1)1]=[f(n+1)f(n)1] left[ egin{matrix} 1 & 1 &1\1& 0&0\0&0&1 end{matrix} ight]* left[ egin{matrix} f(n) \f(n-1)\1 end{matrix} ight]= left[ egin{matrix} f(n+1)\f(n)\1 end{matrix} ight]

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

inline mat mul(mat & a, mat & b, ll mod) {
	mat r(a.size(), vec(b[0].size()));
	for(int i = 0; i < a.size(); i++)
	for(int k = 0; k < b.size(); k++)
	for(int j = 0; j < b[0].size(); j++) 
	r[i][j] = (r[i][j] + a[i][k] * b[k][j]) % mod;
	return r;
}
inline mat mat_pow(mat a, ll b, ll mod) {
	mat r(a.size(), vec(a[0].size()));
	for(int i = 0; i < a.size(); i++) r[i][i] = 1;
	for(; b; b >>= 1) {
		if(b & 1) r = mul(r, a, mod);
		a = mul(a, a, mod);
	}
	return r;
}
inline ll pow_mod(ll a, ll n, ll mod) {
	ll r = 1;
	for(; n; n >>= 1) {
		if(n & 1) r = a * r % mod;
		a = a * a % mod;	
	}
	return r;
}
ll n, x, y, a, b, mod = 1e9 + 7;
ll get1() {
	mat A(2, vec(2));
	A[0][0] = A[0][1] = A[1][0] = 1;
	mat r = mat_pow(A, n - 3, mod - 1);
	ll ex = (r[1][0] + r[1][1]) % (mod - 1), ey = (r[0][0] + r[0][1]) % (mod - 1);
	return pow_mod(x % mod, ex, mod) * pow_mod(y % mod, ey, mod) % mod;
}
ll get2() {
	mat A(3, vec(3));
	A[0][0] = A[0][1] = A[0][2] = A[1][0] = A[2][2] = 1;
	mat r = mat_pow(A, n - 2, mod - 1);
	ll ea = r[0][2] * (b % (mod - 1)) % (mod - 1);
	return pow_mod(a % mod, ea, mod);
}
int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	cin >> n >> x >> y >> a >> b;
	if(n == 1 || n == 2) { cout << (n == 1 ? x : y) % mod; exit(0); }
	if(x % mod == 0 || y % mod == 0 || a % mod == 0) { cout << 0; exit(0); }
	cout << get1() * get2() % mod << '
';
	return 0;	
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yuhan-blog/p/12308617.html