D Array

题意

个数,它们的异或和等于,它们的和等于,求可能的的最小值。

分析

原题:链接

首先我们要明白一个道理,异或和一定小于等于求和。

然后

并且一定是相差二的倍数,因为肯定是某个位数上的两个抵消了。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m,k,ok;

void solve()
{
    if(n > m || (n-m)%2)
    {
        cout<<-1<<endl;
        return;
    }
    if(n == m)
    {
        if(n == 0) cout<<0<<endl;
        else cout<<1<<endl;
        return;
    }
    int res = (m-n)/2;
    if(n&res) cout<<3<<endl;
    else cout<<2<<endl;
}

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    while(~scanf("%d%d",&n,&m))
    {
        solve();
    }
    return 0;
}

E Price

题意

有一个字符串,问字符串里面有多少个匹配串。

分析

优化,第位表示匹配到

然后有一种贪心的策略,就是尽量取前面的串,总数一定是最大的。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int maxn = 2001110;
const int M = 1e9+7;
int n,m,k,ok;

int a[maxn];

bitset<810> b[10],pre,cur;

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    cin>>n>>m;
    for(int i = 1; i <= n; i++) 
    {
        scanf("%1d",a+i);
    }
    for(int i = 1,x; i <= m; i++) 
    {
        cin>>k;
        for(int j = 1; j <= k; j++) 
        {
            cin>>x;
            b[x][i] = 1;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) 
    {
        pre <<= 1;
        pre[1] = 1;
        cur = pre&b[a[i]];
        if(cur[m])
        {   
            ans++;
            cur.reset();
        }
        pre = cur;
    }
    if(ans) cout<<ans<<endl;
    else cout<<"Failed to win the prize"<<endl;
    return 0;
}

F Animal Protection

题意

一个的矩形区域,有一些点不能取,问一共有多少个矩形。

分析

首先我们看一下暴力怎么做这题。

我们枚举每个矩形的右下角,再枚举左边界。

时间复杂度

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define ll __int128_t
const int inf = 0x3f3f3f3f;
const int maxn = 1110;
const int M = 1e9+7;
int n,m,k,ok;

char s[maxn];

int a[maxn][maxn],up[maxn];

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {  
        cin>>(s+1);
        for(int j = 1; j <= m; j++)
        {
            if(s[j] == 'X')
            {
                a[i][j] = 1;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i][j]) up[j] = i;
        }
        for(int j = 1; j <= m; j++)
        {
            int temp = inf;
            for(int k = j; k >= 1; k--)
            {
                temp = min(temp,i-up[k]);
                ans = (ans + temp);
            }
        }
    }
    cout<<ans%M<<endl;
    return 0;
}

接下来考虑怎么优化到

还是枚举每个矩形的右下角,不过我们利用单调栈去维护前面的信息。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define ll __int128_t
const int inf = 0x3f3f3f3f;
const int maxn = 1110;
const int M = 1e9+7;
int n,m,k,ok;

char str[maxn];

int a[maxn][maxn];

int s[maxn],top;

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        cin>>(str+1);
        for(int j = 1; j <= m; j++)
        {
            if(str[j] == 'O') a[i][j] = a[i-1][j] + 1;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {  
        int sum = 0;top = 0;
        for(int j = 1; j <= m; j++)
        {
            sum += a[i][j];
            while(top && a[i][j] <= a[i][s[top]])
            {
                sum -= (s[top]-s[top-1])*(a[i][s[top]]-a[i][j]);
                top--;
            }
            s[++top] = j;
            ans += sum;
        }
    }
    cout<<ans%M<<endl;
    return 0;
}

H Maze

题意

一个迷宫,每次可以走和当前不同的格子,问可以到达的格子有多少个?

分析

我一开始以为是选了一个方向就不能回去了,裂开.jpg

显然可以到,那么可以到

我们利用并查集维护互相可以到达的集合。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define ll __int128_t
const int inf = 0x3f3f3f3f;
const int maxn = 10001110;
const int M = 1e9+7;
int n,m,q;

char a[3010][3010];

int sz[maxn];

int pre[maxn];

int find(int x)
{
    return pre[x]==x?x:pre[x] = find(pre[x]);
}

void unite(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return;
    pre[x] = y;
    sz[y] += sz[x];
}

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    cin>>n>>m>>q;
    for(int i = 1; i <= n; i++) 
    {
        cin>>(a[i]+1);
    }
    for(int i = 1; i <= n*m; i++) 
    {
        sz[i] = 1;
        pre[i] = i;
    }
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) 
        {
            if(i > 1 && a[i-1][j] != a[i][j])
            {
                unite((i-2)*m+j,(i-1)*m+j);
            }
            if(j > 1 && a[i][j-1] != a[i][j])
            {
                unite((i-1)*m+j-1,(i-1)*m+j);
            }
        }
    }
    int x,y;
    while(q--)
    {
        cin>>x>>y;
        x = find((x-1)*m+y);
        cout<<sz[x]<<endl;
    }
    return 0;
}