暑假集训系列题解（四）
题目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;
}