2019 牛客 多校赛 第八场

slove  3/10

rank  374

补题   

--------------------------------------------------------

B、Beauty Values

一个区间的贡献为这个区间的不同数字的个数，求所有子区间的贡献和

反向思考，计算一个数字在子区间中出现的次数，当区间的左端点在这个数字上一次出现位置和当前位置之间，并且右端点在当前位置之后，这个数字都产生了贡献，所以当前位置的数字的贡献就是左端点数量*右端点数量，然后遍历一遍。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>v[100005];
int main()
{
	int n, t;
	scanf("%d", &n);
	for (int i = 1; i <= 100000; i++)
		v[i].push_back(0);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &t);
		v[t].push_back(i);
	}
	ll ans = 0;
	for (int i = 1; i <= 100000; i++)
	{
		int len = v[i].size();
		for (int j = 1; j < len; j++)
		{
			ll l = v[i][j] - v[i][j - 1];
			ll r = n - v[i][j] + 1;
			ans += l * r;
		}
	}
	printf("%lld\n", ans);
}

C、CDMA

1、手玩案例，然后对于2*2的矩阵，我们希望把他扩展到4*4的话，考虑将一行扩展为两行，列翻倍。

2、新矩形的第一行是两个原矩阵的第一行，新矩阵的第二行是原矩阵第一行+原矩阵第一行的相反数。

3、同理，向下扩展。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
	int a[1200][1200];
}ans;
node t[15];
int main()
{
	int n;
	scanf("%d", &n);
	int tt = 1, res = 2;
	while (res != n)
	{
		tt++;
		res *= 2;
	}
	tt--;
	ans.a[1][1] = 1;
	ans.a[1][2] = 1;
	ans.a[2][1] = 1;
	ans.a[2][2] = -1;
	int hang = 2;
	while (tt--)
	{
		int newhang = 1;
		for (int i = 1; i <= hang; i++)
		{
			for (int j = 1; j <= hang; j++)
				t[tt].a[newhang][j] = ans.a[i][j];
			for (int j = 1; j <= hang; j++)
				t[tt].a[newhang][j + hang] = ans.a[i][j];
			newhang++;
			for (int j = 1; j <= hang; j++)
				t[tt].a[newhang][j] = ans.a[i][j];
			for (int j = 1; j <= hang; j++)
				t[tt].a[newhang][j + hang] = -ans.a[i][j];
			newhang++;
		}
		ans = t[tt];
		hang = newhang - 1;
	}
	for (int i = 1; i <= hang; i++)
	{
		for (int j = 1; j <= hang; j++)
			printf("%d%c", ans.a[i][j], j == hang ? '\n' : ' ');
	}
}

G、Gemstones

string大法好，自带erase删除方法。

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
const int INF = 0x3f3f3f3f;
string s;
void solve() {
    cin >> s;
    int len = s.size();
    int ans = 0;
    for (auto it = s.begin(); it != s.end(); )
    {
        auto it1 = it;
        it1++;
        if (it1 == s.end())
            break;
        auto it2 = it1;
        it2++;
        if (it2 == s.end())
            break;
        if (*it == *it1 && *it1 == *it2)
        {
            s.erase(it);
            s.erase(it);
            s.erase(it);
            ans++;
            if (it != s.begin())
                it--;
            if (it != s.begin())
                it--;
        }
        else
            it++;
    }
    printf("%d\n", ans);
 
}
int main(void)
{
    solve();
    return 0;
}