暑假集训系列题解（四）
暑假集训系列题解（四）¶
题目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解释 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".
样例输入¶
样例输出¶
题解¶
构造列方向的前缀和，后用单调栈求出区间最小值和区间长度乘积的第二大值即可。
代码¶
#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解释： We have ⌊10^½⌋=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
所以，只需要利用快速幂算法计算出 $ 10 ^N \% m^2$ 即可
代码¶
#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;
}