Beijing Institute of Technology 2019.6 Monthly Contest 题解

Author： xzm2019
发布时间：June 27, 2019
6097views
No comments
1840字数
Categories：算法

## A. Radishes

如果$n\leq 40$，我们可以进行暴力求解，复杂度$O(n^2)$

然而如果$n>40$，根据抽屉原理，必定至少有一个$l_i$出现了两边，此时$|l_i-l_j|=0,\ d=0$。我们只要统计每一个数前两次的位置，将最多40个答案进行排序，即可。

```cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int w[100005],l[100005];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) scanf("%d%d",&l[i],&w[i]);
    if (n > 40)
    {
        bool flag = true;
        for (int i = 1; i <= n && flag; i++)
            for (int j = i + 1; j <= n && flag; j++)
                if (l[i] == l[j])
                {
                    printf("%d %d\n",i,j);
                    flag = false; break;
                }
        return 0;
    }
    double minn = 1e200;
    int x1 = 0, x2 = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1 + i; j <= n; j++)
        {
            double tmp = max(1.0 * w[i] / w[j], 1.0 * w[j] / w[i]) * abs(l[i] - l[j]);
            if (tmp < minn)
            {
                minn = tmp;
                x1 = i; x2 = j;
            }
        }
    printf("%d %d\n",x1,x2);
	return 0;
}
```

## B. Visual Cube

~~全场最简单？~~

首先算出来整个图形的大小，用字符串数组存图，先全部初始化为`.`，然后一条条边进行绘制。

```cpp
#include <bits/stdc++.h>
using namespace std;

char s[1005][1005];
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int len=b*2+2*a+1;
        int height=2*b+2*c+1;
        memset(s,'.',sizeof(s));
        int now = -1;
        for (int i=1;i<=b;i++)
        {
            int nowl=2 * i - 1;
            now++;
            for (int j=1;j<=a;j++)
            {
                s[nowl][now+2*j-1]='+';
                s[nowl][now+2*j]='-';
            }
            s[nowl][now+2*a+1]='+';
            for (int j=1;j<=2*c;j++)
                s[2*i-1+j][now + 1]='|';
            nowl++; now++;
            for (int j=1;j<=a;j++)
            {
                s[nowl][now+2*j-1]='\\';
            }
            s[nowl][now+2*a+1]='\\';
        }
        int nowl=2*b;
        now++;
        for (int i=1;i<=c+1;i++)
        {
            nowl++;
            for (int j=1;j<=a;j++)
            {
                s[nowl][now + 2*j-1]='+';
                s[nowl][now + 2*j]='-';
            }
            s[nowl][now + 2*a+1]='+';
            int nowx=nowl,nowy=now + 1;
            for (int i=1;i<=2*b;i++)
            {
                nowx--; nowy--;
                if (s[nowx][nowy]=='.')
                    s[nowx][nowy]='\\';
                if (s[nowx][nowy]=='|') s[nowx][nowy]='+';
            }
            if (i==c+1) break;
            nowl++;
            for (int j=1;j<=a;j++)
            {
                s[nowl][now + 2*j-1]='|';
            }
            s[nowl][now + 2*a+1]='|';
        }
        for (int i=1;i<=height;i++)
        {
            for (int j=1;j<=len;j++) putchar(s[i][j]);
            putchar('\n');
        }
    }
    return 0;
}
```

## C. Mr.Liang's Expression

dfs~注意前导0

```cpp
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <map>
#include <set>
#include <bitset>
#include <ctime>
#include <complex>

const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fll;
#define memset0(x) memset(x, 0, sizeof(x))
#define memsetM1(x) memset(x, -1, sizeof(x))
#define memsetINF(x) memset(x, INF, sizeof(x))

using namespace std;

long long ans;
double num;
char str[15];
int ops[15];
int rk[5] = { 3, 1, 1, 2, 2 };

int opCmp(int a, int b)
{
	return rk[a] - rk[b];
}

void dfs(int i = 0, int op = 0)
{
	ops[i] = op;

if (!str[i])
	{
		stack<double> numStack;
		stack<int> opStack;

/*for (int j = 1; j < i; j++)
		{
			cout << ops[j] << " ";
		}
		cout << endl;*/

numStack.push(str[0] - '0');
		for (int j = 1; j < i; j++)
		{
			int dig = str[j] - '0';

if (ops[j] == 0)
			{
				numStack.push(dig);

double num2 = numStack.top();
				numStack.pop();
				double num1 = numStack.top();
				numStack.pop();

numStack.push(num1 * 10 + num2);
			}
			else
			{
				while (!opStack.empty() && opCmp(opStack.top(), ops[j]) > 0)
				{
					double num2 = numStack.top();
					numStack.pop();
					double num1 = numStack.top();
					numStack.pop();
					switch (opStack.top())
					{
					case 0:
						num1 = num1 * 10 + num2;
						break;
					case 1:
						num1 = num1 + num2;
						break;
					case 2:
						num1 = num1 - num2;
						break;
					case 3:
						num1 = num1 * num2;
						break;
					}
					numStack.push(num1);

opStack.pop();
				}
				opStack.push(ops[j]);
				numStack.push(dig);
			}

}
		while (!opStack.empty())
		{
			int cOp = opStack.top();
			opStack.pop();
			double num2 = numStack.top();
			numStack.pop();
			double num1 = numStack.top();
			numStack.pop();
			switch (cOp)
			{
			case 0:
				num1 = num1 * 10 + num2;
				break;
			case 1:
				num1 = num1 + num2;
				break;
			case 2:
				num1 = num1 - num2;
				break;
			case 3:
				num1 = num1 * num2;
				break;
			}
			numStack.push(num1);
		}
		//cout << numStack.top() << endl;
		if (abs(numStack.top() - num) < 1e-6)
		{
			ans++;
		}
		numStack.pop();
		return;
	}
	if (i >= 1 && op == 0)
	{
		if (str[i - 1] == '0' && (i == 1 || ops[i - 1] != 0))
		{
			return;
		}
	}

int dig = str[i] - '0';
	if (!str[i + 1])
	{
		dfs(i + 1, 0);
	}
	else
	{
		for (int j = 0; j < 4; j++)
		{
			dfs(i + 1, j);
		}
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	int startTime = clock();
#endif
	cin >> str >> num;
	dfs();
	cout << ans << endl;

#ifndef ONLINE_JUDGE
	printf("Time = %dms\n", clock() - startTime);
#endif
	return 0;
}
```

## D. Xiao Ming's String

首先如果一个字母的出现次数$>\frac{|S|}{2}+1$，显然不能，则输出`NO`。

否则使用优先队列，每次取前两个元素进行交叉。

```cpp
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
struct alpha{
	int cnt;
	char c;
	alpha(){}
	alpha(int _cnt, char _c){
		cnt = _cnt;
		c = _c;
	}
	bool operator < (const alpha &other) const{
		return cnt < other.cnt;
	}
};

int main(int argc, char * argv[]) 
{
	string s, ans;
	cin >> s;
	int mark[maxn];
	priority_queue<alpha> q;
	bool is_ok = true;
	memset(mark, 0, sizeof(mark));
	for (int i = 0; i < s.size(); i++){
		mark[s[i] - 'a']++;
	}
	for (int i = 0; i < 26; i++){
		if (mark[i]){
			q.push(alpha(mark[i], char(i + 'a')));
		}
	}
	while (!q.empty()){
		alpha a = q.top();
		q.pop();
		if(a.cnt == 0){
			break;
		}
		ans.push_back(char(a.c));
		a.cnt--;

alpha b = q.top();
		q.pop();
		if (b.cnt == 0){
			break;
		}
		ans.push_back(char(b.c));
		b.cnt--;
		q.push(a);
		q.push(b);
	}
	for (int i = 1; i < ans.size(); i++){
		if (ans[i] == ans[i - 1]){
			is_ok = false;
			break;
		}
	}
	if (is_ok && ans.size() == s.size()){
		cout << ans << endl;
	}
	else{
		cout << "NO" << endl;
	}
    return 0;
}
```

## E. Mr.Liang's Sequence Problem(I)

找找因数，推推式子，注意使用`long long`，就完事了~

```cpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        long long N;
        scanf("%lld",&N);
        long long count = 1, sub = sqrt(2 * N);
        for(long long k = 2; k <= sub; k++) {
            if ((N - (k * (k - 1) / 2)) % k == 0) count++;
        }
        printf("%lld\n",count);
    }
    return 0;
}
```

## F. Mr.Liang's Sequence Problem(II)

This **IS** a template problem for ~~segment tree~~ CDQ.

### Solution A: CDQ

假设: $a_x$为原数组第$x$项, 前缀和${\rm sum}_x=\sum\limits_{i=1}^x a_i$, 差分${\rm d}_x=a_x-a_{x-1}\quad(a_0=0)$

区间查询$[l,r]$的和, 实际上可以拆分为$2$个前缀和的差$({\rm sum}_r-{\rm sum}_{l-1})$

区间修改$[l,r]$的值, 实际上可以表示为$2$个差分数组的变化${\rm d}_l+=v, {\rm d}_{r+1}-=v$

考虑差分数组${\rm d}$对前缀和数组第$n$项${\rm sum}_n$的影响

${\rm sum}_n=\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n\sum\limits_{j=1}^i{\rm d}_j=\sum\limits_{i=1}^n(n+1-i)\cdotp {\rm d}_i=(n+1)\sum\limits\limits_{i=1}^n{\rm d}_i-\sum\limits_{i=1}^ni\cdotp {\rm d}_i$

所以只需要维护好所有$i(1\le i\le n)$的${\rm d}_i$和$i\cdotp {\rm d}_i$的和, 便可以$O(1)$的求出${\rm sum}_n$

所以按照$\rm cdq$分治的经典套路, 第一维对时间分治, 第二维按照修改/查询的位置(拆分为$2$个单点修改/查询)进行排序, 考虑分治的左边对右边影响的时候按照上面的做法便可以$O(1)$的进行修改/查询, 复杂度: $O(n\log n)$

```cpp
#include<bits/stdc++.h>
#define fi first
#define sf scanf
#define se second
#define pf printf
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(x,y) memset((x),(y),sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);++i)
#define fdn(i,x,y) for(int i=(x);i>=(y);--i)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
using namespace std;

const int __=4e5+5;

struct node
{
    int id;ull p,v;
}a[__],t[__];

ull ans[__];

void cdq(int l,int r)
{
    if(l==r)return;
    int m=(l+r)>>1;
    cdq(l,m),cdq(m+1,r);
    ull sum[2]={0};int x,y,z=l;
    for(x=l,y=m+1;y<=r;++y)
    {
        for(;x<=m && a[x].p<=a[y].p;t[z++]=a[x++])
            if(!a[x].id)
            {
                sum[0]=sum[0]+a[x].v;
                sum[1]=sum[1]+a[x].v*a[x].p;
            }
        if(a[y].id)
            ans[a[y].id]+=a[y].v*((a[y].p+1)*sum[0]-sum[1]);
        t[z++]=a[y];
    }
    for(int i=x;i<=m;++i)t[z++]=a[i];
    fup(i,l,r)a[i]=t[i];
}

int main()
{
    ll n;int q;sf("%lld%d",&n,&q);
    int idx=0,qdx=0;
    while(q--)
    {
        int op;ull l,r;
        sf("%d%llu%llu",&op,&l,&r);
        if(op==1)
        {
            ull v;sf("%llu",&v);
            a[++idx]={0,l,v};
            a[++idx]={0,r+1,-v};
        }
        else
        {
            ++qdx;
            a[++idx]={qdx,r,1};
            a[++idx]={qdx,l-1,-1ull};
        }
    }
    cdq(1,idx);
    fup(i,1,qdx)
        pf("%llu\n",ans[i]);
    return 0;
}
```

### Solution B: Segment Tree

当然良心的懋懋把这题实现开到了1.5s，线段树可以通过

离散化后线段树, 注意线段树离散化后是$4\times 10^5$个点(每个线段包含$2$个端点)

```cpp
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+5;
typedef long long ll;
int Case = 1;
vector<unsigned long long>ve;
struct node{
    int op;
    long long l, r;
    unsigned long long val;
}Q[maxn];
struct point{
    int l, r;
    unsigned long long len;
    unsigned long long sum;
    unsigned long long lazy;
    int mid() {
        return (l+r)/2;
    }
}tr[maxn<<2];
void pushup(int rt) {
    tr[rt].len = tr[rt<<1].len + tr[rt<<1|1].len;
    tr[rt].sum = tr[rt<<1].sum + tr[rt<<1|1].sum;
}
void build(int rt, int l, int r) {
    tr[rt].l = l;tr[rt].r = r;
    if(l == r) {
        tr[rt].len = ve[l]-ve[l-1];
        return;
    }
    int mid = tr[rt].mid();
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    pushup(rt);
}
void pushdown(int rt) {
    if(tr[rt].lazy) {
        unsigned long long x = tr[rt].lazy;
        tr[rt<<1].lazy += x;
        tr[rt<<1|1].lazy += x;
        tr[rt<<1].sum += x*tr[rt<<1].len;
        tr[rt<<1|1].sum += x*tr[rt<<1|1].len;
        tr[rt].lazy = 0;
    }
}
void update(int rt, int l, int r, unsigned long long val) {
    //cout<<l<<" "<<r<<endl;
    if(tr[rt].l == l && tr[rt]. r == r) {
        tr[rt].lazy += val;
        tr[rt].sum += val*tr[rt].len;
        return;
    }
    pushdown(rt);
    int mid = tr[rt].mid();
    if(r <= mid) update(rt<<1, l, r, val);
    else if(l > mid) update(rt<<1|1, l, r, val);
    else {
        update(rt<<1, l, mid, val);
        update(rt<<1|1, mid+1, r, val);
    }
    pushup(rt);
}
unsigned long long query(int rt, int l, int r) {
    //cout<<l<<" "<<r<<endl;
    if(tr[rt].l == l && tr[rt].r == r) {
        return tr[rt].sum;
    }
    pushdown(rt);
    int mid = tr[rt].mid();
    if (r <= mid)
      return query(rt << 1, l, r);
    else if (l > mid)
      return query(rt << 1|1, l, r);
    else
      return query(rt << 1, l, mid) + query(rt << 1|1, mid+1, r);
}
int getid(long long x) {
    return lower_bound(ve.begin(), ve.end(), x)-ve.begin()+1;
}
void solve() {
    //freopen("in.txt", "r", stdin);
    long long n;int q;
    scanf("%lld%d", &n, &q);
    for(int i = 1; i <= q; i++) {
        scanf("%d", &Q[i].op);
        if(Q[i].op == 1) {
            scanf("%lld%lld%llu", &Q[i].l, &Q[i].r, &Q[i].val);
        }
        else scanf("%lld%lld", &Q[i].l, &Q[i].r);
        Q[i].r++;
        ve.push_back(Q[i].l);
        ve.push_back(Q[i].r);
    }
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    int len = ve.size();
    build(1, 1, len-1);
    for(int i = 1; i <= q; i++) {
        long long l = Q[i].l, r = Q[i].r;
        int op = Q[i].op;
        if(op == 1) update(1, getid(l), getid(r)-1, Q[i].val);
        else
          printf("%llu\n", query(1, getid(l), getid(r)-1));
    }
    return;
}
int main() {
    //g++ -std=c++11 -o2 1.cpp -o f && ./f < in.txt
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
#endif
while(Case--) {
    solve();
    }
return 0;
}
```

## G. q_Wq's Dating

显然要求两个人手上的串一样也就是这个串是回文串

树上的回文子串查询问题无法使用类似于 Mancher 的算法解决。

考虑哈希的解法。首先假定节点$1$为根，将无根树转换为有根树。对于树上每个节点，预处理维护两个哈希值：$HashUp(i)$表示从节点$i$到节点$1$的路径上的字母序列的哈希值，$HashDown(i)$表示从节点$1$到节点$i$的路径上的字母序列的哈希值。则树上任意一有向简单路的哈希值均可计算。处理查询时，只需要检查从$u$到$v$的哈希值是否与从$v$到$u$的哈希值相同即可。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN=400005;
const int mod=998244353;
struct node{
    int id;
    long long pre,en;
    int prelen,enlen;
    vector<int> G;
}mapp[MAXN];
char s[MAXN];
int degree[MAXN];
long long pp[MAXN],pq[MAXN];
int depth[MAXN];
int parent[MAXN][25];

void dfs(int x, int y)
{
	depth[x] = depth[y] + 1;
	parent[x][0] = y;
	for (auto &i: mapp[x].G)
		if (i != y) dfs(i, x);
}
void build(int root, int n)
{
	dfs(root, 0);
	for (int i = 1; i <= 20; i++)
		for (int j = 1; j <= n; j++)
			parent[j][i] = parent[parent[j][i - 1]][i - 1];
}
int lca(int u, int v)
{
	for (int i = 20; i >= 0; i--)
	{
		if (depth[parent[u][i]] >= depth[v])
			u = parent[u][i];
		if (depth[parent[v][i]] >= depth[u])
			v = parent[v][i];
	}
	for (int i = 20; i >= 0; i--)
		if (parent[u][i] != parent[v][i])
		{
			u = parent[u][i];
			v = parent[v][i];
		}
	if (u != v)
	{
		u = parent[u][0];
		v = parent[v][0];
	}
	return u;
}
void dfs1(int now,int last)
{
    mapp[now].pre=(mapp[last].pre*1001+s[now])%mod;
    mapp[now].prelen=mapp[last].prelen+1;
    for (auto &i:mapp[now].G)
        if (i!=last)
            dfs1(i,now);
}
long long qpow(long long base, long long index) {
    long long ans = 1;
    while (index) {
        if (index & 1)
            ans = ans * base % mod;
        base = base * base % mod;
        index >>= 1;
    }
    return ans;
}
void dfs2(int now,int last)
{
    if (now==1)
    {
        mapp[1].en=s[1];
        mapp[1].enlen=1;
        return;
    }
    for (auto &i:mapp[now].G)
        if (i!=last&&mapp[i].prelen<mapp[now].prelen)
        {
            dfs2(i,now);
            mapp[now].enlen=mapp[i].enlen+1;
            mapp[now].en=(mapp[i].en+s[now]*pp[mapp[i].enlen])%mod;
        }
}
inline long long gethash(int u,int v)
{
    int t=lca(u,v);
    long long tmp1=((mapp[u].en-mapp[t].en)%mod+mod)%mod*pq[mapp[t].enlen]%mod;
    long long tmp2=((mapp[v].pre-mapp[t].pre*pp[mapp[v].prelen-mapp[t].prelen]%mod)%mod+mod)%mod;
    long long ans=((tmp1*1001+s[t])%mod*pp[mapp[v].prelen-mapp[t].prelen]%mod+tmp2)%mod;
    //printf("%d %d %d %lld %lld %lld\n",u,v,t,tmp1,tmp2,ans);
    return ans;
}
int main()
{
    mapp[1].pre=mapp[1].en=mapp[1].prelen=mapp[1].enlen=0;
    int n;
    scanf("%d",&n);
    pp[0]=1; pp[1]=1001;
    for (int i=2;i<=n;i++) pp[i]=pp[i-1]*1001%mod;
    pq[0]=1; pq[1]=qpow(1001,mod-2);
    for (int i=2;i<=n;i++) pq[i]=pq[i-1]*pq[1]%mod;
    scanf("%s",s+1);
    for (int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        mapp[u].G.emplace_back(v);
        mapp[v].G.emplace_back(u);
        degree[u]++; degree[v]++;
    }
    build(1,n);
    dfs1(1,0);
    for (int i=2;i<=n;i++)
        if (degree[i]==1)
            dfs2(i,0);
    int Q;
    scanf("%d",&Q);
    while (Q--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if (gethash(u,v)==gethash(v,u))
            printf("Happy!\n");
        else printf("555\n");
    }
    return 0;
}
```

## H. Mr.Liang's Sequence Problem(III)

不难打表答案就是$(\frac{n}{2}+1)$

在不打表($T=1$)之前，这题是这样做的：

> 定义: $f(n)$为$\lfloor \frac{n}{1}\rfloor,\lfloor \frac{n}{2}\rfloor,\cdots,\lfloor \frac{n}{n}\rfloor$中不同数字的个数, 那么有一个比较经典的结论: $f(n)=2\cdotp \lfloor \sqrt n\rfloor-\Big[\lfloor \sqrt n\rfloor\cdotp(\lfloor \sqrt n\rfloor+1)\gt n\Big]$
>
> 可以观察到: 若$1\le x\le y$, 那么$f(x)\le f(y)$, 因此$f(n)$关于$n$满足单调性, 所以可以进行二分, 找到$f(n)=m$的最小值$l$以及$f(n)=m+1$的最小值$r$, 答案就是: $(r-l)$

```cpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--){
        long long x;
        scanf("%lld",&x);
        printf("%lld\n",x / 2 + 1);
    }
    return 0;
}
```

## I. SuPer Fast Algorithm

不难发现，这是一个SPFA的代码，需要你hack它，也就是你要使得他TLE。

1. 打开百度
2. 搜索`SPFA怎么卡`

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <complex>
#include <random>
#include <stack>
#include <time.h>
#define SET0(X) memset(X,0,sizeof(X));
#define SET_1(X) memset(X,-1,sizeof(X));
#define RAND(a,b) ((rand() % (b-a+1))+ a)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct edge{int u,v,w;};
vector<edge>v;

int id[20][10010],n=10,cnt,m=100000/n,a[1000000];
int r(){
    return rand();
}
int main(){
    srand((unsigned)time(NULL));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            id[i][j]=++cnt;
            a[cnt]=cnt;
        }

int SIZE=990;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            if(i<n){
                v.push_back(edge{id[i][j],id[i+1][j],1});
                if(j<m){
                    v.push_back(edge{id[i][j],id[i+1][j+1],r()%SIZE+10});
                    v.push_back(edge{id[i+1][j+1],id[i][j],r()%SIZE+10});
                }
            }
            if(j<m){
                v.push_back(edge{id[i][j],id[i][j+1],r()%SIZE+10});
            }
        }
    random_shuffle(v.begin(),v.end());
    printf("%d %d\n",cnt,(int)v.size());
    for(int i=0;i<v.size();++i)
        printf("%d %d %d\n",a[v[i].u],a[v[i].v],v[i].w);
    return 0;
}
```

## J. Regular Expression

对所有的字符串$t_i$建立AC自动机, 由于$\sum |t_i| \leq 10^3$，那么AC自动机上节点数$\leq 10^3$

$dp[i][j]$代表: 考虑字符串$s$前$i$个字符, 在自动机上状态为$j$的答案

若$s_{i + 1} = '?'$，则$\mathrm{d} \mathrm{p}[i+1][k]=\max (\mathrm{d} \mathrm{p}[i+1][k], \mathrm{d} \mathrm{p}[i][j]+\mathrm{words})$，$k$为状态$j$读入字符$a,b,c,\cdots,z$后转移的状态。

若$s_{i + 1} \neq '?'$，则$\mathrm{d} \mathrm{p}[i+1][k]=\max (\mathrm{d} \mathrm{p}[i+1][k], \mathrm{d} \mathrm{p}[i][j]+\mathrm{words})$，$k$为状态$j$读入字符$s_{i+1}$后转移的状态。

$words$为以状态$k$结尾的单词的个数

$dp[i][j]$第一维可以使用滚动数组优化掉。

```cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define fo(i,a) for(int i=1;i<=(a.n);i++)
#define mem(x,y) memset((x),(y),sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);i++)
#define fdn(i,x,y) for(int i=(x);i>=(y);i--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int __=1e3+5;

int dp[2][__];

struct AhoCorasickAutomaton
{
    static const int alp=26;

static int to_idx(char ch)
    {
        return ch-'a'+1;
    }

struct Trie
    {
        struct node
        {
            int nex[alp+1],last,num;
            void clear()
            {
                num=last=0;
                mem(nex,0);
            }
        }t[__];

Trie() {clear();}

node& operator[](int x){return t[x];}

int idx;

void insert(char s[])
        {
            int x=0;
            for(int i=1;s[i];++i)
            {
                int k=to_idx(s[i]);
                if(!t[x].nex[k])
                {
                    t[x].nex[k]=++idx;
                    t[idx].clear();
                }
                x=t[x].nex[k];
            }
            ++t[x].num;
        }

void clear(){idx=0;t[0].clear();}
    }t;

AhoCorasickAutomaton() {clear();}

#define nex(x) t[x].nex[i]
#define fail(x) t[x].nex[0]

void get_fail()
    {
        queue<int>Q;Q.push(0);
        while(!Q.empty())
        {
            int x=Q.front();Q.pop();
            for(int i=1;i<=alp;++i)
                if(nex(x))
                {
                    Q.push(nex(x));
                    if(x)fail(nex(x))=nex(fail(x));
                }
                else nex(x)=nex(fail(x));
            if(t[fail(x)].num)t[x].last=fail(x);
            else t[x].last=t[fail(x)].last;
            t[x].num+=t[t[x].last].num;
        }
    }

int ac(char s[],int len)
    {
        dp[0][0]=0;
        for(int i=1,f=1;i<=len;++i,f=!f)
        {
            mem(dp[f],-1);
            for(int j=0;j<=t.idx;++j)
            {
                if(dp[!f][j]==-1)continue;
                if(s[i]!='?')
                {
                    int x=to_idx(s[i]),y=t[j].nex[x];
                    dp[f][y]=max(dp[f][y],dp[!f][j]+t[y].num);
                    continue;
                }
                for(int k=1;k<=alp;++k)
                {
                    int y=t[j].nex[k];
                    dp[f][y]=max(dp[f][y],dp[!f][j]+t[y].num);
                }
            }
        }
        int ans=0;
        for(int i=0;i<=t.idx;++i)
            ans=max(ans,dp[len&1][i]);
        return ans;
    }

void clear(){t.clear();}
}aca;

char a[__],b[__];

int main()
{
    mem(dp,-1);
    int m;sf("%s%d",a+1,&m);
    for(int i=1;i<=m;++i)
    {
        sf("%s",b+1);
        aca.t.insert(b);
    }
    aca.get_fail();
    pf("%d\n",aca.ac(a,strlen(a+1)));
    return 0;
}
```

## K. Mr.Liang's Sequence Problem(IV)

### 1.数位$\rm dp$

数位$\rm dp$简单题, 可能被发现的比较晚

${\rm dp}[i][j]$代表长度为$i$, 数位总和为$j$的所有数字的数位之和

struct DigitalDynamicProgramming
{
    int bit[20];
    ll dp[20][200];

DigitalDynamicProgramming() {memset(dp,-1,sizeof(dp));}

ll dfs(int len,int sum,bool lim)
    {
        if(!len)return sum;
        if(!lim && ~dp[len][sum])return dp[len][sum];
        int r=lim?bit[len]:9;

ll res=0;
        for(int i=0;i<=r;++i)
        {
            res+=dfs(len-1,sum+i,lim && i==bit[len]);
        }
        if(lim)return res;
        return dp[len][sum]=res;
    }

ll cal(ll x)
    {
        if(x<0)return 0;
        int idx=0;
        for(;x;x/=10)bit[++idx]=x%10;
        return dfs(idx,0,true);
    }
}dp;

int main()
{
    ll l,r;sf("%lld%lld",&l,&r);
    pf("%lld\n",dp.cal(r)-dp.cal(l-1));
    return 0;
}
```

### 2.计算贡献

考虑数字$0,1,2,\cdots ,9$分别在个位, 十位, 百位,$\cdots$出现的次数, 不难发现:

个位每$10$个数字出现一个循环, 每个循环中每个数字分别出现$1$次

百位每$100$个数字出现一个循环, 每个循环中每个数字分别出现连续$10$次

千位每$1000$个数字出现一个循环, 每个循环中每个数字分别出现连续$100$次

$\cdots$

以此类推

ll cal(ll n)
{
    ll res=0;
    for(ll m=10;m<=n*10;m*=10)
        for(int i=0;i<=9;++i)
        {
            res+=n/m*(m/10)*i;
            if(n%m+1>=i*m/10)
                res+=min(n%m+1-i*m/10,m/10)*i;
        }
    return res;
}

int main()
{
    ll l,r;sf("%lld%lld",&l,&r);
    pf("%lld\n",cal(r)-cal(l-1));
	return 0;
}
```

Last modification：June 27th, 2019 at 11:33 pm

If you think my article is useful to you, please feel free to appreciate

Comment *

私密评论

Name *

Email *

Site

Beijing Institute of Technology 2019.6 Monthly Contest 题解

xzm2019 • 2019 年 06 月 27 日

## A. Radishes

如果$n\leq 40$，我们可以进行暴力求解，复杂度$O(n^2)$

```cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

## B. Visual Cube

~~全场最简单？~~

首先算出来整个图形的大小，用字符串数组存图，先全部初始化为`.`，然后一条条边进行绘制。

```cpp
#include <bits/stdc++.h>
using namespace std;

## C. Mr.Liang's Expression

dfs~注意前导0

using namespace std;

long long ans;
double num;
char str[15];
int ops[15];
int rk[5] = { 3, 1, 1, 2, 2 };

int opCmp(int a, int b)
{
	return rk[a] - rk[b];
}

void dfs(int i = 0, int op = 0)
{
	ops[i] = op;

if (!str[i])
	{
		stack<double> numStack;
		stack<int> opStack;

/*for (int j = 1; j < i; j++)
		{
			cout << ops[j] << " ";
		}
		cout << endl;*/

numStack.push(str[0] - '0');
		for (int j = 1; j < i; j++)
		{
			int dig = str[j] - '0';

if (ops[j] == 0)
			{
				numStack.push(dig);

double num2 = numStack.top();
				numStack.pop();
				double num1 = numStack.top();
				numStack.pop();

opStack.pop();
				}
				opStack.push(ops[j]);
				numStack.push(dig);
			}

int dig = str[i] - '0';
	if (!str[i + 1])
	{
		dfs(i + 1, 0);
	}
	else
	{
		for (int j = 0; j < 4; j++)
		{
			dfs(i + 1, j);
		}
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	int startTime = clock();
#endif
	cin >> str >> num;
	dfs();
	cout << ans << endl;

#ifndef ONLINE_JUDGE
	printf("Time = %dms\n", clock() - startTime);
#endif
	return 0;
}
```

## D. Xiao Ming's String

首先如果一个字母的出现次数$>\frac{|S|}{2}+1$，显然不能，则输出`NO`。

否则使用优先队列，每次取前两个元素进行交叉。

## E. Mr.Liang's Sequence Problem(I)

找找因数，推推式子，注意使用`long long`，就完事了~

```cpp
#include <bits/stdc++.h>
using namespace std;

## F. Mr.Liang's Sequence Problem(II)

This **IS** a template problem for ~~segment tree~~ CDQ.

### Solution A: CDQ

假设: $a_x$为原数组第$x$项, 前缀和${\rm sum}_x=\sum\limits_{i=1}^x a_i$, 差分${\rm d}_x=a_x-a_{x-1}\quad(a_0=0)$

区间查询$[l,r]$的和, 实际上可以拆分为$2$个前缀和的差$({\rm sum}_r-{\rm sum}_{l-1})$

区间修改$[l,r]$的值, 实际上可以表示为$2$个差分数组的变化${\rm d}_l+=v, {\rm d}_{r+1}-=v$

考虑差分数组${\rm d}$对前缀和数组第$n$项${\rm sum}_n$的影响

所以只需要维护好所有$i(1\le i\le n)$的${\rm d}_i$和$i\cdotp {\rm d}_i$的和, 便可以$O(1)$的求出${\rm sum}_n$

const int __=4e5+5;

struct node
{
    int id;ull p,v;
}a[__],t[__];

ull ans[__];

### Solution B: Segment Tree

当然良心的懋懋把这题实现开到了1.5s，线段树可以通过

离散化后线段树, 注意线段树离散化后是$4\times 10^5$个点(每个线段包含$2$个端点)

## G. q_Wq's Dating

显然要求两个人手上的串一样也就是这个串是回文串

树上的回文子串查询问题无法使用类似于 Mancher 的算法解决。

```cpp
#include <bits/stdc++.h>
using namespace std;

## H. Mr.Liang's Sequence Problem(III)

不难打表答案就是$(\frac{n}{2}+1)$

在不打表($T=1$)之前，这题是这样做的：

```cpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--){
        long long x;
        scanf("%lld",&x);
        printf("%lld\n",x / 2 + 1);
    }
    return 0;
}
```

## I. SuPer Fast Algorithm

不难发现，这是一个SPFA的代码，需要你hack它，也就是你要使得他TLE。

1. 打开百度
2. 搜索`SPFA怎么卡`

## J. Regular Expression

对所有的字符串$t_i$建立AC自动机, 由于$\sum |t_i| \leq 10^3$，那么AC自动机上节点数$\leq 10^3$

$dp[i][j]$代表: 考虑字符串$s$前$i$个字符, 在自动机上状态为$j$的答案

$words$为以状态$k$结尾的单词的个数

$dp[i][j]$第一维可以使用滚动数组优化掉。

const int __=1e3+5;

int dp[2][__];

struct AhoCorasickAutomaton
{
    static const int alp=26;

static int to_idx(char ch)
    {
        return ch-'a'+1;
    }

Trie() {clear();}

node& operator[](int x){return t[x];}

int idx;

void clear(){idx=0;t[0].clear();}
    }t;

AhoCorasickAutomaton() {clear();}

#define nex(x) t[x].nex[i]
#define fail(x) t[x].nex[0]

void clear(){t.clear();}
}aca;

char a[__],b[__];

## K. Mr.Liang's Sequence Problem(IV)

### 1.数位$\rm dp$

数位$\rm dp$简单题, 可能被发现的比较晚

${\rm dp}[i][j]$代表长度为$i$, 数位总和为$j$的所有数字的数位之和

struct DigitalDynamicProgramming
{
    int bit[20];
    ll dp[20][200];

DigitalDynamicProgramming() {memset(dp,-1,sizeof(dp));}

ll dfs(int len,int sum,bool lim)
    {
        if(!len)return sum;
        if(!lim && ~dp[len][sum])return dp[len][sum];
        int r=lim?bit[len]:9;

ll res=0;
        for(int i=0;i<=r;++i)
        {
            res+=dfs(len-1,sum+i,lim && i==bit[len]);
        }
        if(lim)return res;
        return dp[len][sum]=res;
    }

ll cal(ll x)
    {
        if(x<0)return 0;
        int idx=0;
        for(;x;x/=10)bit[++idx]=x%10;
        return dfs(idx,0,true);
    }
}dp;

int main()
{
    ll l,r;sf("%lld%lld",&l,&r);
    pf("%lld\n",dp.cal(r)-dp.cal(l-1));
    return 0;
}
```

### 2.计算贡献

考虑数字$0,1,2,\cdots ,9$分别在个位, 十位, 百位,$\cdots$出现的次数, 不难发现:

个位每$10$个数字出现一个循环, 每个循环中每个数字分别出现$1$次

百位每$100$个数字出现一个循环, 每个循环中每个数字分别出现连续$10$次

千位每$1000$个数字出现一个循环, 每个循环中每个数字分别出现连续$100$次

$\cdots$

以此类推

int main()
{
    ll l,r;sf("%lld%lld",&l,&r);
    pf("%lld\n",cal(r)-cal(l-1));
	return 0;
}
```

Beijing Institute of Technology 2019.6 Monthly Contest 题解

Leave a Comment

2019南昌邀请赛网络赛个人记录（附官方题解）

北京理工大学第七届程序设计新生赛题解（unofficial）

第 43 届 ACM/ICPC 亚洲区域赛（南京）总结

北京理工大学第八届程序设计新生赛题解

Beijing Institute of Technology 2019.6 Monthly Contest 题解

第 4 届中国大学生程序设计竞赛总决赛总结

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 现场赛题解

【转】Prufer codes与Generalized Cayley's Formula

北京理工大学2020年蓝桥杯校内选拔赛题解

睿信书院2018级14班程序设计基础期中考试选择题部分

Beijing Institute of Technology 2019.6 Monthly Contest 题解