2019 牛客 多校赛 第十场

slove  4/10

rank  297

补题   5/10

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

Link

B、Coffee Chicken

s[1]=“COFFEE”，S[2]=“CHICKEN"，s[i]=s[i-2]+s[i-1]，求第 n 个串的第 K - K+10 个字符

预处理一下所有小于等于1e12的长度，然后爆搜，大概就是如果查询的长度小于等于前一个串，那么就搜前一个串，否则，搜后一个串。

然后发现当 n 很大的时候，他的前缀（除了前13个是奇偶变换的）是等于他前面的前缀的（打表），然后就可以爆搜了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e4 + 7;
ll f[N];
char s[3][100] = { "","COFFEE","CHICKEN" };
int main()
{
	int Q, k;
	f[1] = strlen(s[1]);
	f[2] = strlen(s[2]);
	for (int i = 3; i <= 500; i++)
		f[i] = 1e18;
	for (int i = 3; f[i - 1] <= 1e18; i++)
	{
		f[i] = f[i - 2] + f[i - 1];
		k = i;
	}
	scanf("%d", &Q);
	while (Q--)
	{
		ll x, y;
		scanf("%lld%lld", &x, &y);
		if (x > 61)
		{
			x = (x & 1) ? 61 : 60;
		}
		for (int i = 0; i < 10; i++)
		{
			ll xx = x;
			ll yy = y + i;
			if (yy > f[xx])
				break;
			while (xx > 2)
			{
				if (yy > f[xx - 2])
				{
					yy -= f[xx - 2];
					xx--;
				}
				else
					xx -= 2;
			}
			printf("%c", s[xx][yy - 1]);
		}
		printf("\n");
	}
}

D、Han Xin and His Troops

中国剩余定理解同余式，本来是个板子题，卡了long long

#include<bits/stdc++.h>
typedef __int128 ll;
using namespace std;
void exgcd(ll a, ll b, ll& g, ll& x, ll& y)
{
    if (b == 0)
    {
        g = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, g, y, x);
    y -= (a / b) * x;
}
bool flag = false;
ll a1, a2, n1, n2;
long long m;
ll abs(ll x)
{
    return x > 0 ? x : -x;
}
  
void china()
{
    ll d = a2 - a1;
    ll g, x, y;
    exgcd(n1, n2, g, x, y);
    if (d % g == 0)
    {
        x = ((x * d / g) % (n2 / g) + (n2 / g)) % (n2 / g);
        a1 = x * n1 + a1;
        n1 = (n1 * n2) / g;
    }
    else
        flag = true;
}
  
int n;
  
long long as[100001];
  
long long ns[100001];
  
ll realchina()
{
    a1 = as[0];
    n1 = ns[0];
    for (ll i = 1; i < n; i++)
    {
        a2 = as[i];
        n2 = ns[i];
        china();
        if (flag)
            return -1;
    }
    return a1;
}
  
int main()
{
    cin >> n >> m;
    flag = false;
    for (ll i = 0; i < n; i++)
        cin >> ns[i] >> as[i];
    ll num = (ll)realchina();
    if (num > m)
        printf("he was probably lying");
    else if (num == -1)
        printf("he was definitely lying");
    else
        printf("%lld", num);
    //    cout<<(long long)realchina()<<endl;
}

E、Hilbert Sort

对二维平面上的点按照希尔伯特曲线进行排序

一个整块可以分为四小块，每块可以找到一个公式，对应为顺序访问

如上图，我们以上图作为标准小块，那么将它看成4个小块，左上角小块可以将x,y坐标互换，就变成了标准小块，右上角的x,y互换后，用小块的长度减它们在加一，也变成了原小块，这样就可以无限递归下去求到每一个位置对应在希尔伯特曲线中的位置。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
struct qqq
{
	int x;
	int y;
	ll val;
}in[1000005];
ll dfs(ll x, ll y, int n)
{
	if (n == 1)
	{
		if (x == 1 && y == 1)
			return 1;
		else if (x == 2 && y == 1)
			return 2;
		else if (x == 2 && y == 2)
			return 3;
		else
			return 4;
	}
	ll kuai = 1LL << (n - 1);
	if (x <= kuai && y <= kuai)
		return dfs(y, x, n - 1);
	else if (x > kuai && y <= kuai)
		return kuai * kuai + dfs(x - kuai, y, n - 1);
	else if (x > kuai && y > kuai)
		return kuai * kuai * 2 + dfs(x - kuai, y - kuai, n - 1);
	else
		return kuai * kuai * 3 + dfs(kuai + 1 - (y - kuai), kuai + 1 - x, n - 1);
}
int main()
{
	ll n, k;
	sc("%lld%lld", &n, &k);
	for (int i = 0; i < n; i++)
	{
		sc("%lld%lld", &in[i].x,  &in[i].y);
		in[i].val = dfs(in[i].x, in[i].y, k);
	}
	sort(in, in + n, [](qqq q, qqq w) {
		return q.val < w.val;
		});
	for (int i = 0; i < n; i++)
		printf("%d %d\n", in[i].x, in[i].y);
}

F、Popping Balloons

平面上有1e5个气球，你可以选择三行和三列的坐标，打爆选择的行列上的所有的气球，问你最多能打爆多少个气球。

思维+线段树，想通了就是线段树***题。

1、首先我们可以预处理以某一列  作为起点，打  这三列打到的气球

2、那么我们枚举以每一行  作为起点，打  这三行，

3、因为这三行的气球可能与我选择的最优列有重复气球，那么我们只需要将这三行的气球删掉（比如说点(i,j)有一个气球，那么删除后列  就少了一个气球），这样就做到了对相同气球去重，然后再询问一下打哪个  作为起点的最多，加一下就是答案。

4、所以整个题目就变成了区间查询最大值和单点更新，似乎是个线段树入门题?

5、注意判一下越界

#include <bits/stdc++.h>
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e5 + 5;
const int inf = 100001;
vector<int>v[MAXN];
int maxn[MAXN * 4];
int n, r, x, y;
void update(int left, int right, int k, int pos, int val)
{
	if (left == right)
	{
		maxn[k] += val;
		return;
	}
	int mid = (left + right) / 2;
	if (pos <= mid)
		update(left, mid, k << 1, pos, val);
	else
		update(mid + 1, right, k << 1 | 1, pos, val);
	maxn[k] = max(maxn[k << 1], maxn[k << 1 | 1]);
}
void add(int pos, int val)
{
	if (pos > 0 && pos <= inf)
		update(1, inf, 1, pos, val);
	if (pos - r > 0 && pos - r <= inf)
		update(1, inf, 1, pos - r, val);
	if (pos - 2 * r > 0 && pos - 2 * r <= inf)
		update(1, inf, 1, pos - 2 * r, val);
}
int main()
{
	sc("%d%d", &n, &r);
	for (int i = 1; i <= n; i++)
	{
		sc("%d%d", &x, &y);
		v[x + 1].push_back(y + 1);
		add(y + 1, 1);//影响前三列
	}
	int ans = 0, len, sum;
	for (int i = 1; i <= inf; i++)//枚举选第 i、i+r、i+2*r 行 
	{
		sum = v[i].size();
		if (i + r <= inf)
			sum += v[i + r].size();
		if (i + 2 * r <= inf)
			sum += v[i + 2 * r].size();

		len = v[i].size();
		for (int j = 0; j < len; j++)
			add(v[i][j], -1);
		if (i + r <= inf)
		{
			len = v[i + r].size();
			for (int j = 0; j < len; j++)
				add(v[i + r][j], -1);
		}
		if (i + 2 * r <= inf)
		{
			len = v[i + 2 * r].size();
			for (int j = 0; j < len; j++)
				add(v[i + 2 * r][j], -1);
		}

		ans = max(ans, sum + maxn[1]);

		len = v[i].size();
		for (int j = 0; j < len; j++)
			add(v[i][j], 1);
		if (i + r <= inf)
		{
			len = v[i + r].size();
			for (int j = 0; j < len; j++)
				add(v[i + r][j], 1);
		}
		if (i + 2 * r <= inf)
		{
			len = v[i + 2 * r].size();
			for (int j = 0; j < len; j++)
				add(v[i + 2 * r][j], 1);
		}
	}
	printf("%d\n", ans);
}

H、Stammering Chemists

签到。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 20;
int first[MAX], nextt[MAX], u[MAX], v[MAX], cnt = 0, du[MAX], yuan[MAX], tot = 0;
bool vis[MAX];
void add(int a, int b) {
    u[cnt] = a, v[cnt] = b;
    nextt[cnt] = first[u[cnt]];
    first[u[cnt]] = cnt; ++cnt;
}
void dfs(int now, int count) {
    if (count == 2) {
        ++tot;
        return;
    }
    for (int num = first[now]; num != -1; num = nextt[num]) {
        if (!vis[v[num]]) {
            vis[v[num]] = true;
            dfs(v[num], count + 1);
            vis[v[num]] = false;
        }
    }
}
void solve() {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(du, 0, sizeof(du));
        memset(yuan, 0, sizeof(yuan));
        memset(first, -1, sizeof(first));
        memset(vis, false, sizeof(vis));
        tot = 0; cnt = 0;
        for (int i = 1; i <= 5; ++i) {
            int a, b;
            scanf("%d%d", &a, &b);
            ++yuan[a], ++yuan[b];
            ++du[a], ++du[b];
            add(a, b), add(b, a);
        }
        sort(du + 1, du + 7);
        if (du[1] == 1 && du[2] == 1 && du[3] == 2 && du[4] == 2 && du[5] == 2 && du[6] == 2) {
            printf("n-hexane\n");
        }
        else if (du[1] == 1 && du[2] == 1 && du[3] == 1 && du[4] == 1 && du[5] == 2 && du[6] == 4) {
            printf("2,2-dimethylbutane\n");
        }
        else if (du[1] == 1 && du[2] == 1 && du[3] == 1 && du[4] == 1 && du[5] == 3 && du[6] == 3) {
            printf("2,3-dimethylbutane\n");
        }
        else if (du[1] == 1 && du[2] == 1 && du[3] == 1 && du[4] == 2 && du[5] == 2 && du[6] == 3) {
            for (int i = 1; i <= 6; ++i) {
                if (yuan[i] == 3) {
                    vis[i] = true;
                    dfs(i, 0);
                    if (tot == 2) {
                        printf("3-methylpentane\n");
                    }
                    else {
                        printf("2-methylpentane\n");
                    }
                }
            }
        }
    }
}
int main(void)
{
    solve();
    return 0;
}