2016 ACM/ICPC Asia Regional Qingdao Online 题解

tonyfang posted @ 2016年9月18日 19:44 in HDU with tags c++ OI , 944 阅读

代码更新 10/13    题解更新13/13

A. 多组询问求大于等于$n$的第一个数,其因数只含2,3, 5, 7.

$n \leq 10^9$

【题解】

预处理+二分

利用STL可以有效提高代码速度

复杂度$O(10^4 + Q)$
# include <stdio.h>
# include <set>
# include <algorithm>
using namespace std;

typedef long long ll;
set<ll> q;
int T, s;
int p[10010], pn=0;

int main() {
	q.insert(2), q.insert(3), q.insert(5), q.insert(7);
	while(!q.empty()) {
		ll _top = *q.begin(); q.erase(_top);
		if(_top > 1e9) break;
		p[++pn] = _top;
		q.insert(_top*2);
		q.insert(_top*3);
		q.insert(_top*5);
		q.insert(_top*7);
	}
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &s);
		printf("%d\n", p[lower_bound(p+1, p+pn+1, s) - p]);
	}
	return 0;
}

B

多组询问,求$a_{n} = \sum_{i=1}^{n} \frac{1}{i^{2}}$。

输入数据不超过1M

复杂度$O(10^7 + Q)$

【题解】

观察到数列收敛,猜测有极限,暴力求出极限后打表。

# include <stdio.h>
# include <string.h>
using namespace std;

typedef long double ld;
typedef double db;
ld p[1000010];
char str[100010];

int main() {
	for (int i=1; i<=1000000; ++i) 
		p[i] = p[i-1] + 1.0f/((ld)i * i);
	while(~scanf("%s", str)) {
		int sz = strlen(str), n;
		if(sz >= 7) puts("1.64493");
		else {
			n = 0;
			for (int i=0; i<sz; ++i) 
				n = (n<<3) + (n<<1) + str[i] - '0';
			printf("%.5lf\n", (db)p[n]);	
		}
	}
	
	return 0;
}

C

给出屏蔽文本,要你从文章中屏蔽这些词。

【题解】AC自动机,卡空间。

D

有一壶水,体积在$[L, R]$之间,要把水近乎平均的倒到两个杯子里(差值小等1),而且要保证这壶水剩下的不能超过1,你不能实时知道还剩下水的体积,求要满足最少倒几次。

$0 < L, R \leq 10^{15}$

【题解】

很明显模拟之后我们发现要分类讨论。

①$1 < R \leq 2$:倒1体积水到一个杯子即可,故答案为1

②$0 < R \leq 1$:明显不用倒水即可,故答案为0

③$0 < L \leq 1$:第一杯1体积,之后每次2体积往上交替加即可。答案为$\frac{R-1}{2}+1$

④$R-L \leq 2$,第一次倒$\frac{L+1}{2}$,第二次倒$\frac{L+3}{2}$即可,答案为2.

⑤其他情况,在保证L的情况下,每次2体积往上交替即可。第一次倒$\frac{L+1}{2}$,第二次倒$\frac{L+3}{2}$即可,故答案为$\frac{R-L}{2}+1$

复杂度$O(T)$

# include <stdio.h>

using namespace std;

typedef long long ll;
ll L, R;

int main() {
	while(~scanf("%I64d%I64d", &L, &R)) {
		if(R<=1) {
			puts("0");
			continue;
		}
		if(R<=2) {
			puts("1");
			continue;
		}
		if(R-L <= 2) {
			puts("2");
			continue;
		}
		if(L <= 1) {
			printf("%I64d\n", (R-1)/2+1);
			continue;
		}
		printf("%I64d\n", (R-L)/2+1);
	}

	return 0;
}

E

扩展锤子剪刀布问题

【题解】

判奇数偶数即可。

复杂度$O(T)$

# include <stdio.h>

using namespace std;

int T, n;

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		if(n&1) puts("Balanced");
		else puts("Bad");
	}

	return 0;
}

F

给一条路,找一条欧拉路,使得经过的点的依次顺序,它们的异或值最大。

$n \leq 100000$

若不符合欧拉路的条件就是Impossible,不联通也是Impossible。

如果点度数两个奇数,那么欧拉路唯一,直接输出固定值即可。

否则,枚举起点(因为起点=终点会被多异或一次)求最大值即可。

复杂度$O(Tn)$

# include <stdio.h>

using namespace std;

int T, n, m, fa[100010], cnts[100010], deg[100010], v[100010];
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		for (int i=1; i<=n; ++i) {
			fa[i] = i;
			deg[i] = 0;
			scanf("%d", &v[i]);
		}
		for (int i=1, u, vs; i<=m; ++i) {
			scanf("%d%d", &u, &vs);
			deg[u] ++, deg[vs] ++;
			int fu = getf(u), fv = getf(vs);
			if(fu != fv) fa[fu] = fv;
		}
		int cnt=0;
		bool all = 1;
		for (int i=1; i<=n; ++i) if(deg[i] & 1) cnt++, all = 0;
		if(cnt > 2) {
			puts("Impossible");
			continue;
		}
		cnt = 0;
		for (int i=1; i<=n; ++i) cnts[getf(i)] ++;
		for (int i=1; i<=n; ++i) if(cnts[i] > 0) ++cnt;
		if(cnt > 1) {
			puts("Impossible");
			continue;
		}
		if(! all) {
			int ans = 0;
			for (int i=1; i<=n; ++i) {
				if (deg[i]&1) deg[i] = deg[i]/2 + 1;
				else deg[i] /= 2;
				if (deg[i]&1) ans ^= v[i];
			}
			printf("%d\n", ans);
		} else {
			int ans = 0, anss, maxx=0;
			for (int i=1; i<=n; ++i) {
				deg[i] /= 2;
				if (deg[i]&1) ans ^= v[i];
			}
			for (int i=1; i<=n; ++i) {
				anss = ans ^ v[i];
				if(anss > maxx) 
					maxx = anss;
			}
			printf("%d\n", maxx);
		}
	}
	return 0;
}

G

有n个数,每次可以合并k个数,花费的代价为数的和,新数为所有原数的和,如果代价不能超过T,求k的最小值。

$n \leq 100000$

【题解】

二分+优先队列+卡时+fread能过,复杂度$O(Tnlog^2n)$

但是由于插入的单调性,所以我们可以用两个队列维护。一个维护旧的一个维护合并后的。

唯一要注意的是如果$(n-1) mod (k-1) \not= 0$(因为合并一次消去了$k-1$个数,总共要消去$n-1$个数,那么我们把小的提前合并即可。复杂度$O(Tnlogn)$

# include <stdio.h>
# include <queue>
# include <algorithm>
# define R register

using namespace std;

typedef long long ll;
int T, n;
ll t;
ll a[100010];
int l, r, mid, ans;
queue<ll> q1, q2;

inline int read() {
	R int x=0; 
	R char ch=getchar();
	while(ch > '9' || ch < '0') ch = getchar();
	while(ch >= '0' && ch <= '9') {
		x = (x<<3) + (x<<1) + ch - '0';
		ch = getchar();
	}
	return x;
}

inline ll readll() {
	R ll x=0; 
	R char ch=getchar();
	while(ch > '9' || ch < '0') ch = getchar();
	while(ch >= '0' && ch <= '9') {
		x = (x<<3) + (x<<1) + ch - '0';
		ch = getchar();
	}
	return x;
}
inline bool check(int k) {
	R ll res, sum, ret = 0;
	R int gs;
	while(!q1.empty()) q1.pop();
	while(!q2.empty()) q2.pop();
	for (int i=1; i<=n; ++i) q1.push((ll)a[i]);
	if((n-1)%(k-1) != 0) {
		res = (n-1)%(k-1)+1, sum = 0;
		for (int i=1; i<=res; ++i) {
			sum += q1.front();
			q1.pop();
		}
		q2.push(sum);
		ret += sum;
	}
	while(!q1.empty()) {
		sum = 0;
		for (int i=1; i<=k; ++i) {
			if(!q1.empty() && !q2.empty()) {
				if(q1.front() <= q2.front()) sum+=q1.front(), q1.pop();
				else sum += q2.front(), q2.pop();
			} else if(!q1.empty()) sum += q1.front(), q1.pop();
			else if(!q2.empty()) sum += q2.front(), q2.pop();
		}
		ret += sum;
		q2.push(sum);
	}
	if(ret > t) return false;
	sum = gs = 0;
	while(!q2.empty()) {
		sum += q2.front(); ++gs; q2.pop();
		if(gs == k) {
			q2.push(sum);
			ret += sum;
			sum=gs=0;
			if(q2.size() == 1) break;
		}
	}
	return ret <= t;
}

int main() {
	T = read();
	while(T--) {
		n = read(), t = readll();
		for (int i=1; i<=n; ++i) a[i] = readll();
		sort(a+1, a+n+1);
		l=2, r=n, ans=1000001;
		while(l<=r) {
			int mid = l+r>>1;
			if(check(mid)) {
				r=mid-1;
				ans = min(ans, mid);
			}
			else l=mid+1;
		}
		printf("%d\n", ans);
	}

	return 0;
}

 

H

给出一个$n\times m$的格子,格子$(i,j)$的值为$p(i,j)$,两个格子间距离定义为格子中心的欧几里得距离,你可以选择一个格子,距离小于等于$r$的那些格子都会贡献$\frac{p(i,j)}{d+1}$,选择一个格子,使得贡献和最大。

【题解】造多项式,FFT即可。

I

求树删去一条边后分成的两个块的直径最大值的期望,为了输出方便,答案乘以$n-1$。

$ n \leq 100000$

【题解】其实就是问树删去一条边后分成的两个块的直径最大值的和了

首先预处理出树的一条直径$(a,b)$,标记直径上的边,如果枚举的不是直径上的边,答案就是直径长度。

如果枚举的是直径上的边,那么我们考虑,对于$a$和$b$为根分别预处理,得到$f1_x, f2_x$分别表示以$a$为根和以$b$为根,$x$的子树的直径大小是多少。这个可以通过树形dp预处理。

所以接下来就是查询啦,很简单啦

总复杂度$O(Tn)$

比较难拍所以附带暴力以及数据生成器(视需要自行修改)

# include <stdio.h>
# include <string.h>
# include <algorithm>

using namespace std;

int T, n;
int head[500100], nxt[800100], to[800100], w[800100], tot=0, pos[800100];
bool inc[500100];
int fr[500100];
int u[500100], v[500100];
typedef long long ll;
ll ans=0;

int fir[500100], sec[500100], f1[500100], f2[500100], son[500100];

inline void add(int uu, int vv, int tw, int ii) {
	++tot;
	nxt[tot]=head[uu];
	head[uu]=tot;
	to[tot]=vv;
	w[tot]=tw;
	pos[tot]=ii;
} 

int mx, res;

inline void dfs(int cur, int fa, int curw) {
	if(curw > mx) {
		mx = curw;
		res = cur;
	}
	for (int i=head[cur]; i; i=nxt[i]) {
		if(to[i] == fa) continue;
		dfs(to[i], cur, curw+w[i]);
	}
}


bool success = 0;
inline void dfsnode(int cur, int fa, int too) {
	if(success) return;
	if(cur == too) {
		success = 1;
		return ;
	}
	for (int i=head[cur]; i; i=nxt[i]) {
		if(to[i] == fa) continue;
		inc[pos[i]] = 1;
		fr[pos[i]] = cur;
		dfsnode(to[i], cur, too);
		if(success) break;
		inc[pos[i]] = 0;
		fr[pos[i]] = 0;
	}
}

inline void dp1(int x, int fa) {
	son[x]=f1[x]=fir[x]=sec[x]=0;
	for(int i=head[x]; i; i=nxt[i]) {
		if(to[i] == fa) continue;
		++son[x];
		dp1(to[i], x);
		fir[to[i]] += w[i], sec[to[i]] += w[i];
		if(son[x] == 1) fir[x]=fir[to[i]];
		else {
			if(fir[to[i]] > fir[x]) {
				sec[x] = fir[x];
				fir[x] = fir[to[i]];
			} 
			else if(fir[to[i]] > sec[x]) sec[x] = fir[to[i]];
		}
		f1[x] = max(f1[x], f1[to[i]]);
	}
	if(son[x] == 1) f1[x] = max(f1[x], fir[x]);
	else if(son[x] > 1) f1[x] = max(f1[x], fir[x] + sec[x]);
}

inline void dp2(int x, int fa) {
	son[x]=f2[x]=fir[x]=sec[x]=0;
	for(int i=head[x]; i; i=nxt[i]) {
		if(to[i] == fa) continue;
		++son[x];
		dp2(to[i], x);
		fir[to[i]] += w[i], sec[to[i]] += w[i];
		if(son[x] == 1) fir[x]=fir[to[i]];
		else {
			if(fir[to[i]] > fir[x]) {
				sec[x] = fir[x];
				fir[x] = fir[to[i]];
			} 
			else if(fir[to[i]] > sec[x]) sec[x] = fir[to[i]];
		}
		f2[x] = max(f2[x], f2[to[i]]);
	}
	if(son[x] == 1) f2[x] = max(f2[x], fir[x]);
	else if(son[x] > 1) f2[x] = max(f2[x], fir[x] + sec[x]);
}

int main() {
	//freopen("hdu5886.in", "r", stdin);
	//freopen("hdu5886.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		ans=0;
		tot=0; memset(head, 0, sizeof(head));
		memset(inc, 0, sizeof(inc)); success = 0;
		scanf("%d", &n);
		for (int i=1, tw; i<n; ++i) {
			scanf("%d%d%d", &u[i], &v[i], &tw);
			add(u[i], v[i], tw, i);
			add(v[i], u[i], tw, i);
		}
		mx=-1; dfs(1, 0, 0); int posa = res;
		mx=-1; dfs(posa, 0, 0); int posb = res;
		//printf("%d %d\n", posa, posb);
		dfsnode(posa, 0, posb);
		//for (int i=1; i<n; ++i) printf("%d\n", inc[i]);
		dp1(posa, 0);
		//for (int i=1; i<=n; ++i) printf("i=%d, %d\n", i, f1[i]);
		dp2(posb, 0);
		//printf("%d\n", mx);
		for (int i=1; i<n; ++i) {
			if(!inc[i]) ans += (ll)mx;
			else {
				int from = fr[i], to = u[i]+v[i]-from;
				int zj = max(f2[from], f1[to]);
				ans += (ll)zj;
			}
		}
		printf("%I64d\n", ans);
	}

	return 0;
}
/*
1
10
4 3 56
3 6 85
8 7 45
7 5 164
5 1 166
1 6 2
6 10 174
9 2 61
2 10 14

ans:4664
*/

 

# include <stdio.h>
# include <string.h>
# include <algorithm>

using namespace std;

int T, n;
int head[500100], nxt[800100], to[800100], w[800100], tot=0, pos[800100];
bool vis[800100];
bool inc[500100];
int fr[500100];
int u[500100], v[500100], ppos[500100];
typedef long long ll;
ll ans=0;

int fir[500100], sec[500100], f1[500100], f2[500100], son[500100];

inline void add(int uu, int vv, int tw, int ii) {
	++tot;
	nxt[tot]=head[uu];
	head[uu]=tot;
	to[tot]=vv;
	w[tot]=tw;
	pos[tot]=ii;
	vis[tot]=0;
} 

int mx, res;

inline void dfs(int cur, int fa, int curw) {
	if(curw > mx) {
		mx = curw;
		res = cur;
	}
	for (int i=head[cur]; i; i=nxt[i]) {
		if(to[i] == fa || vis[i]) continue;
		dfs(to[i], cur, curw+w[i]);
	}
}

int main() {
	//freopen("hdu5886.in", "r", stdin);
	//freopen("hdu5886.ans", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		ans=0;
		tot=0; memset(head, 0, sizeof(head));
		scanf("%d", &n);
		for (int i=1, tw; i<n; ++i) {
			scanf("%d%d%d", &u[i], &v[i], &tw);
			add(u[i], v[i], tw, i);
			ppos[i] = tot;
			add(v[i], u[i], tw, i);
		}
		for (int i=1; i<n; ++i) {
			vis[ppos[i]] = vis[ppos[i]+1]=1;
			mx=-1;dfs(u[i],0,0); int poss=res;
			mx=-1;dfs(poss,0,0); int gg = mx;
			mx=-1;dfs(v[i],0,0); poss=res;
			mx=-1;dfs(poss,0,0);
			vis[ppos[i]] = vis[ppos[i]+1]=0;
			ans+=max(mx, gg);
		}
		printf("%I64d\n", ans);
	}

	return 0;
}

 

#include<cstdio>
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[30000+20];
struct nod
{
	int id,d;
}d[30000+20];
bool cmpid(nod x,nod y)
{
	return x.id<y.id;
}
bool cmp(nod x,nod y)
{
	if(x.d!=y.d)return x.d<y.d;
	else return x.id<y.id;
}
int main()
{
	freopen("hdu5886.in","w",stdout);
	srand(time(NULL));
	puts("10");
	for (int jj=1;jj<=10;++jj) {
	int n=10;
	cout<<n<<endl;
	for(int i=1;i<=n;i++)
	{
		d[i].d=1;
		d[i].id=i;
	}
	for(int i=1;i<=n-2;i++)a[i]=rand()%n+1;
	for(int i=1;i<=n-2;i++)d[a[i]].d++;
		for(int i=1;i<=n-2;i++)
		{
			sort(d+1,d+n+1,cmp);
			int j;
			for(j=1;j<=n;j++) if(d[j].d)break;
			printf("%d %d %d\n",d[j].id,a[i], rand()%200+1);
			d[j].d--;
			sort(d+1,d+n+1,cmpid);
			d[a[i]].d--;
		}
		sort(d+1,d+n+1,cmp);
		printf("%d %d %d\n",d[n-1].id,d[n].id, rand()%200+1);
	}
	
	return 0;
}

J

求0/1背包,$T \leq 10, n \leq 100, wi, vi \leq 10^9$。

【题解】

dfs+剪枝

每次到一层做一次可分解背包判断可行性。

时间复杂度:理论$O(T2^n)$;实际:$O(能过)$

# include <stdio.h>
# include <algorithm>
using namespace std;

typedef long double ld;
typedef long long ll;
int n, m;
struct pi {
	int a, b;
	ld rate;
}p[110];
ll maxx = 0;

inline bool cmp(pi a, pi b) {
	return a.rate > b.rate;
}

inline void dfs(int cur, ll v, ll w) {
	if(w>maxx) maxx = w;
	if(cur == n+1) return;
	ld vv=(ld)v, ww=(ld)w;
	for (int i=cur; i<=n; ++i) {
		if(vv + p[i].a <= m) {
			vv += p[i].a;
			ww += p[i].b;
		} else {
			ww += (m - vv) * p[i].rate;
			break;
		}
	}
	if(ww < maxx) return;
	if(v+p[cur].a<=m) dfs(cur+1, v+p[cur].a, w+p[cur].b);
	dfs(cur+1, v, w);
}

int main() {
	
	while(~scanf("%d%d", &n, &m)) {
		maxx = 0;
		for (int i=1; i<=n; ++i) {
			scanf("%d%d", &p[i].a, &p[i].b);
			p[i].rate = (ld)p[i].b/p[i].a;
		}
		sort(p+1, p+n+1, cmp);
		dfs(1, 0, 0);
		printf("%I64d\n", maxx);
	}

	return 0;
}

K

求一张图1~n的最短路中的图的最小割

$n \leq 1000$

【题解】

裸题 代码by zhouyis

复杂度 $O(Tn^2)$

#include<map>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<complex>
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;
#define inf 1001001001
#define infll 1001001001001001001LL
#define ll long long
#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl
#define gmax(a,b) (a)=max((a),(b))
#define gmin(a,b) (a)=min((a),(b))
#define Ri register int
#define gc getchar()
#define il inline
il int read(){
    bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch=='-')f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=gc;}return f?x:-x;
}
#define gi read()
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
int n,m;
namespace maxf{
    const int N=1005,M=233333;
    struct edge{
        int to,next;ll cap;
    }e[M];
    int last[N],cnt=1;int h[N];
    void insert(int u,int v,ll cap,ll revc){
        e[++cnt]=(edge){v,last[u],cap};last[u]=cnt;
        e[++cnt]=(edge){u,last[v],revc};last[v]=cnt;
    }
    bool bfs(int s,int t){
        memset(h,-1,sizeof(h));
        h[s]=0;
        queue<int>q; 
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=last[u];i;i=e[i].next){
                if(e[i].cap&&h[e[i].to]==-1){
                    h[e[i].to]=h[u]+1;
                    q.push(e[i].to);
                }
            }
        }
        return h[t]!=-1; 
    }
    ll dfs(int v,int t,ll f){
        if(v==t)    return f;
        ll used=0,w=0;
        for(int u=last[v];u;u=e[u].next){
            if(h[e[u].to]==h[v]+1){
                w=dfs(e[u].to,t,min(f-used,e[u].cap));
                e[u].cap-=w;
                e[u^1].cap+=w;
                 used+=w;
                if(used==f)    return f;
            }
        }
        if(!used)    h[v]=-1;
        return used;
    }
    ll maxflow(int s,int t){
        ll ans=0;
        while(bfs(s,t)){
            ans+=dfs(s,t,(1ll<<60));
            if(ans>=(1ll<<60))return ans;} 
        return ans;
    }
    int main(){
        cout<<maxflow(1,n)<<endl;
    }
}
namespace graph_theory{
    #define M 220000
    struct edge{
        int to,next,v,cost;
    }e[M]; 
    #define N 10000
    int cnt,last[N],inq[N],dis[N];    
    //dis:length of shorest path
    //inq: is point "i" be pushed into the queue 
    void insert(int a,int b,int c,int d){
        e[++cnt]=(edge){b,last[a],c,d};last[a]=cnt;
    }
    int spfa(int s,int t){
        queue<int>q;
        for(int i=1;i<=N-1;i++)dis[i]=(1e9); 
        q.push(s);dis[s]=0;inq[s]=true;
        while(!q.empty()){
            int c=q.front();q.pop();inq[c]=false;
            for(int i=last[c];i;i=e[i].next){
                if(dis[e[i].to]>dis[c]+e[i].v){
                    //update dis[e[i].to] 
                    dis[e[i].to]=dis[c]+e[i].v;
                    if(!inq[e[i].to]){
                        q.push(e[i].to);
                        inq[e[i].to]=true; 
                    }
                }
            }
        }
        return dis[t];
    } 
    int main(){
        memset(last,0,sizeof(last));cnt=1; 
        n=gi;m=gi;
        for(int i=1;i<=m;i++){
            int a,b,c;
            a=gi;b=gi;c=gi;
            insert(a,b,1,c);
            insert(b,a,1,c);
        }
        spfa(1,n);
        
        memset(maxf::last,0,sizeof(maxf::last));maxf::cnt=1; 
        for(int i=1;i<=n;i++){
            for(int j=last[i];j;j=e[j].next){
                if(dis[i]+e[j].v==dis[e[j].to]){
                    maxf::insert(i,e[j].to,e[j].cost,0);
                }
            }
        }
        return 0;
    }
    #undef N
    #undef M
}
int main(){
    int T=gi;
    while(T--){
        graph_theory::main();
        maxf::main();
    }
}

L

给出$n$个数,$m$次询问问去掉三个数(可以相同)后,剩下的数能否用不超过10个组成87.

$n \leq 100$

【题解】

bitset dp,时间有点紧,所以用读入优化就能过啦,982ms。

理论时间复杂度$O(Tn^3 \times 10 \times 87)$,实际复杂度$O(能过)$。

# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <bitset>
using namespace std;

typedef long long ll;
bitset<90> f[11];
int ans[60][60][60];
int a[100], n, m;
int q[4];

inline int read() {
	int x=0;char ch=getchar();
	while(ch>'9' || ch<'0') ch=getchar();
	while(ch>='0' && ch<='9') {
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}

inline int chk(int x, int y, int z) {
	for (int i=0; i<=n; ++i) f[i].reset();
	f[0][0]=1;
	for (int i=1; i<=n; ++i) {
		if(i==x || i==y || i==z) continue;
		for (int t=10; t>=1; --t)
			f[t] |= f[t-1]<<a[i];
	}
	if(f[10][87] == 1) return 1;
	return 0;
}

int main() {
	int T; T=read();
	while(T--) {
		n=read();
		memset(ans, 0, sizeof(ans));
		for (int i=1; i<=n; ++i) a[i]=read();
		for (int i=1; i<=n; ++i)
			for (int j=i; j<=n; ++j)
				for (int k=j; k<=n; ++k)
					if(chk(i, j, k)) 
						ans[i][j][k] = 1;
		m=read();
		while(m--) {
			for (int i=1; i<=3; ++i) q[i]=read();
			sort(q+1,q+3+1);
			printf("%s\n", ans[q[1]][q[2]][q[3]] ? "Yes" : "No");
		}
	}

	return 0;
}

M

给出一个字符串,要求支持往后加一个字符,询问字符串T(是原串子串,以$[L,R]$形式给出),问T中的一个子串最长的至少出现两次的子串的长度,强制在线。

【题解】后缀树(自动机)+可持久化线段树+LCT。具体不会。

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter