哈尔滨理工大学软件与微电子学院程序设计竞赛（同步赛）DEFH

D Array

题意

有 $n$ 个数，它们的异或和等于 $x$ ，它们的和等于 $y$ ，求可能的 $n$ 的最小值。

分析

$codeforces628D$ 原题：链接

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

然后 $a \land a = 0$ ， $0 \land a = a$ 。

并且 $n$ 和 $m$ 一定是相差二的倍数，因为肯定是某个位数上的两个 $1$ 抵消了。

#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

题意

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

分析

$bitset$ 优化，第 $i$ 位表示匹配到 $i$ 。

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

#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

题意

一个 $n \times m$ 的矩形区域，有一些点不能取，问一共有多少个矩形。

分析

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

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

时间复杂度 $O(n^3)$

#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;
}

接下来考虑怎么优化到 $O(n^2)$

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

#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

显然 $a$ 可以到 $b$ ，那么 $b$ 可以到 $a$ 。

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

#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;
}