暑假集训系列题解（四）
题目1
题目链接
题目描述
We have N cards numbered 1 to N. Each side of each card has a color represented by a positive integer.
One side of Card i has a color ai, and the other side has a color bi.
For each card, you can choose which side shows up. Find the maximum possible number of different colors showing up.
Constraints
1≤N≤200000
1≤ai,bi≤400000
All numbers in input are integers.
输入
Input is given from Standard Input in the following format:
N
a1 b1
a2 b2
:
aN bN
输出
Print the answer.
样例输入
【样例1】 4 1 2 1 3 4 2 2 3 【样例2】 2 111 111 111 111 【样例3】 12 5 2 5 6 1 2 9 7 2 7 5 5 4 2 6 7 2 2 7 8 9 7 1 8
样例输出
【样例1】 4 【样例2】 1 【样例3】 8
提示
样例1解释
We can choose the sides with 1, 3, 4, 2 to have four colors.
样例2解释
They are painted with just one color.
题解
并查集，建立连通块。分两种情况：
- 连通块无环，为一棵树，则该连通块对答案的贡献度为点的个数减1，例如1-2，2-3，3-4，这种情况答案为3
- 连通块有环，则该连通块对答案的贡献度为点的数目，例如1-2，2-3，3-1，该情况答案为4
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll fa[400500]={0}; ll huan[400500]={0}; ll sum[400500]={0}; ll findfa(ll n) { if(n==fa[n]) return n; return fa[n]=findfa(fa[n]); } int main() { ll n,s,e; for(ll i=1;i<=400000;i++) fa[i]=i; scanf("%lld",&n); for(ll i=1;i<=n;i++) { ll x,y; scanf("%lld%lld",&x,&y); ll fx=findfa(x); ll fy=findfa(y); if(fx==fy) huan[fx]=huan[fy]=1; else fa[fy]=fx; } for(ll i=1;i<=400000;i++) { findfa(i); huan[fa[i]]|=huan[i]; sum[fa[i]]++; } ll ans=0; for(ll i=1;i<=400000;i++) { if(sum[i]!=0) { if(huan[i]) ans+=sum[i]; else ans+=sum[i]-1; } } cout<<ans<<endl; }
题目2
题目链接
题目描述
Given a N×M binary matrix. Please output the size of second large rectangle containing all "1".
Containing all "1" means that the entries of the rectangle are all "1".
A rectangle can be defined as four integers x1,y1,x2,y2 where 1≤x1≤x2≤N and 1≤y1≤y2≤M. Then, the rectangle is composed of all the cell (x, y) where x1≤x≤x2 and y1≤y≤y2. If all of the cell in the rectangle is "1", this is a valid rectangle.
Please find out the size of the second largest rectangle, two rectangles are different if exists a cell belonged to one of them but not belonged to the other.
输入
The first line of input contains two space-separated integers N and M.
Following N lines each contains M characters cij.
1≤N,M≤1000
N×M≥2
cij∈"01"
输出
Output one line containing an integer representing the answer. If there are less than 2 rectangles containning all "1", output "0".
样例输入
1 2 01
样例输出
0
题解
构造列方向的前缀和，后用单调栈求出区间最小值和区间长度乘积的第二大值即可。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; int sum[2050][2050] = {0}; int a[2050][2050] = {0}; struct node { ll pos, val; }; node s[100500] = {0}; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%1d", &a[i][j]); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (a[i][j]) sum[i][j] = sum[i - 1][j] + a[i][j]; else sum[i][j] = 0; } ll ans = 0; ll max1 = 0, max2 = 0; for (ll i = 1; i <= n; i++) { ll top = 0; for (ll j = 1; j <= m + 1; j++) { if (top == 0) { s[++top] = {j, sum[i][j]}; } else { while (s[top].val > sum[i][j]) { ll tmp = (ll)(j - s[top - 1].pos - 1) * (ll)s[top].val; ll tmp1 = (ll)(j - s[top - 1].pos - 2) * (ll)s[top].val; ll tmp2 = (ll)(j - s[top - 1].pos - 1) * (ll)(s[top].val - 1); top--; if (tmp > max1) swap(max1, tmp); if (tmp > max2) swap(max2, tmp); if (tmp1 > max1) swap(max1, tmp1); if (tmp1 > max2) swap(max2, tmp1); if (tmp2 > max1) swap(max1, tmp2); if (tmp2 > max2) swap(max2, tmp2); } s[++top] = {j, sum[i][j]}; } } } cout << max2 << endl; }
题目3
题目链接
题目描述
Given positive integers N and M, find the remainder when $⌊10^N/M⌋$ is divided by M.
What is ⌊x⌋?⌊x⌋ denotes the greatest integer not exceeding x. For example:
⌊2.5⌋=2
⌊3⌋=3
⌊9.9999999⌋=9
⌊100/3⌋=⌊33.33...⌋=33
Constraints
1≤N≤$10^{18}$
1≤M≤10000
输入
Input is given from Standard Input in the following format: N a1 b1 a2 b2 : aN bN
输出
Print the answer.
样例输入
【样例1】 1 2 【样例2】 2 7 【样例3】 1000000000000000000 9997
样例输出
【样例1】 1 【样例2】 0 【样例3】 9015
提示
样例1解释：
We have ⌊10^1/2⌋=5, so we should print the remainder when 5 is divided by 2, that is, 1.
题解
$⌊\frac{10^N}{M}⌋ \% m = ⌊\frac{10^N}{M}-k*m⌋ \% m =⌊\frac{10^N-k*m^2}{M}⌋\% m=⌊\frac{10^N \% m^2}{M}⌋\% m$
$⌊\frac{10^N}{M}⌋ \% m = ⌊\frac{10^N}{M}-k*m⌋ \% m =⌊\frac{10^N-k*m^2}{M}⌋\% m=⌊\frac{10^N \% m^2}{M}⌋\% m$
所以，只需要利用快速幂算法计算出 $ 10 ^N \% m^2$ 即可
如果Latex无法显示，请看下面图片：
image-20210730211015287代码
#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3, "Ofast", "inline") #include <bits/stdc++.h> using namespace std; typedef long long ll; map<ll, ll> mp; vector<ll> v; int main() { ll n, m; cin >> n >> m; ll mod = m * m, ans1 = 1, ans2 = 10; while (n != 0) { if (n % 2) ans1 = (ans1 * ans2) % mod; ans2 = (ans2 * ans2) % mod; n /= 2; } ll ans = (ans1 / m + m) % m; cout << ans << endl; }