跳转至

暑假集训系列题解(四)

暑假集训系列题解(四)

题目1

题目链接

Reversible Cards

题目描述

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,例如1-2,2-3,3-4,这种情况答案为3
  2. 连通块有环,则该连通块对答案的贡献度为点的数目,例如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

题目链接

Second Large Rectangle

题目描述

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

题目链接

Simple Math 2

题目描述

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^½⌋=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;
}