D1T1 小凯的疑惑

分析

求不能用 a x + b y = t ( x > 0 , y > 0 ) ax+by=t (x > 0, y > 0) ax+by=t(x>0,y>0) 表示的最大值 t t t
我们不妨求最小 t 0 t_0 t0,满足 t t 0 t\geq t_0 tt0时, t t t 恒能用 a x + b y ax+by ax+by 表示。
t 0 = a x + b y t_0 = ax + by t0=ax+by
a x + b y = 1 , a x + b y = 1 ax' + by' = 1, ax''+by''=1 ax+by=1,ax+by=1,其中 x , y x',y'' x,y分别是最小的正数解。
我们要让 t 0 1 t_0-1 t01 无解,最大可以满足的 x , y x,y x,y 就是 x = x 1 x = x'-1 x=x1 y = y 1 y = y''-1 y=y1
这样子 t 0 1 t_0-1 t01 一定无法构造出两个正整数解,不是 x x x 小于 0 0 0 就是 y y y 小于 0 0 0
于是 a n s = a ( x 1 ) + b ( y 1 ) 1 ans = a(x'-1)+b(y''-1)-1 ans=a(x1)+b(y1)1

代码如下

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL z = 1;
void exgcd(int a, int b, int &x, int &y){
	if(!b){
		x = 1; y = 0;
	}
	else{
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
}
int main(){
	int a, b, x, y;
	scanf("%d%d", &a, &b);
	exgcd(a, b, x, y);
	while(x < 0) x += b;
	while(x > b) x -= b;
	while(y < 0) y += a;
	while(y > a) y -= a;
	printf("%lld", z * a * (x - 1) + z * b * (y - 1) - z);
	return 0;
}

D1T2 时间复杂度

分析

这是一道大模拟,我们用一个栈来记录循环,找栈的最大深度就可以了。细节挺多,要把细节都想清楚再打,事半功倍!!!Think twice,code once!

代码如下

#include <cstdio>
#include <string.h>
#include <cctype>
#include <algorithm>
using namespace std;
int sta[305], v[1005], t[1005], ok[1005], cnt, tot;
char s[1005], o[4], a[123], beg[123], en[123];
int main(){
    int i, j, n, m, T, l, r, f, sum, maxn, flag, ff, len1, len2, tmp1, tmp2;
    scanf("%d", &T);
    while(T--){
        memset(sta, 0, sizeof(sta));
        memset(v, 0, sizeof(v));
        memset(t, 0, sizeof(t));
        memset(ok, 0, sizeof(ok));
        cnt = f = ff = tot = flag = maxn = 0;
        scanf("%d%s", &n, s);
        m = strlen(s);
        for(i = 0; i < m; i++){
            if(s[i] == '(') l = i+1;
            if(s[i] == ')') r = i-1;  
        }
        if(l == r) f = 1;
        else
            for(sum = i = 0; i < m; i++)
                if(isdigit(s[i])) sum = sum * 10 + s[i] - '0';
        while(n--){
            scanf("%s", o);
            if(o[0] == 'F'){
                scanf("%s%s%s", a, beg, en);
                if(v[a[0]]){
                    flag = 2;
                    continue;
                }
                v[a[0]] = 1;
                t[++cnt] = a[0];
                if(ff) continue;
                len1 = strlen(beg);
                len2 = strlen(en);
                if(beg[0] == 'n' && en[0] == 'n') continue;
                else if(beg[0] == 'n' && isdigit(en[0])) ff = 1, ok[cnt] = -1;
                else if(isdigit(beg[0]) && en[0] == 'n') tot++, ok[cnt] = 1;
                else{
                    for(tmp1 = i = 0; i < len1; i++)
                        if(isdigit(beg[i])) tmp1 = tmp1 * 10 + beg[i] - '0';
                    for(tmp2 = i = 0; i < len2; i++)
                        if(isdigit(en[i])) tmp2 = tmp2 * 10 + en[i] - '0';
                    if(tmp1 > tmp2) ff = 1, ok[cnt] = -1;
                }
            }
            else{
                maxn = max(maxn, tot);
                v[t[cnt]] = 0;
                if(ok[cnt] == 1) tot--, ok[cnt] = 0;
                if(ok[cnt] == -1) ok[cnt] = ff = 0;
                cnt--;
            }
            if(cnt < 0) flag = 2;
        }
        if(flag == 2 || cnt > 0) printf("ERR\n");
        else if(!maxn && f) printf("Yes\n");
        else if(maxn == sum && !f) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

D1T3 逛公园

分析

从数据范围来看,复杂度大概是 O ( n k ) O(n*k) O(nk)的。其实想一想也知道,统计方案,就是个 d p dp dp。设 d i s [ a ] dis[a] dis[a] 为到 a a a 的最短路长度。
我们用 f [ a ] [ k ] f[a][k] f[a][k] 表示以 a a a 为终点, 1 1 1 a a a 的距离为 d i s [ a ] + k dis[a]+k dis[a]+k 的方案数。
然后用记忆化搜索就可以了(其实用拓扑排序也可以但我不怎么会

代码如下

#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct node{
	int a, b, c, n;
}d[N * 2], e[N * 2];
int P, k, cnt, ret;
int p[N], h[N], v[N], f[N][55], vis[N][55], V[N][55], flag, dis[N];
void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void crr(int a, int b, int c){
	e[++ret].a = a; e[ret].b = b; e[ret].c = c; e[ret].n = p[a]; p[a] = ret;
}
int dp(int a, int k){
	int i, b, c;
	if(vis[a][k] == -1) return f[a][k];
	if(vis[a][k] == 1){
		flag = 1;
		return f[a][k];
	}
	vis[a][k] = 1;
	for(i = p[a]; i; i = e[i].n){
		b = e[i].b;
		c = e[i].c;
		if(dis[a] <= dis[b] + c && k + dis[a] - dis[b] - c >= 0) f[a][k] = (f[a][k] + dp(b, k - (c - (dis[a] - dis[b])))) % P;
	}
	vis[a][k] = -1;
	return f[a][k];
}
int main(){
	int i, j, n, m, T, a, b, c, ans;
	scanf("%d", &T);
	while(T--){
		ret = cnt = 0;
		ans = flag = 0;
		memset(V, 0, sizeof(V));
		memset(h, 0, sizeof(h));
		memset(f, 0, sizeof(f));
		memset(vis, 0, sizeof(vis));
		memset(p, 0, sizeof(p));
		scanf("%d%d%d%d", &n, &m, &k, &P);
		queue<int> q;
		for(i = 1; i <= m; i++){
			scanf("%d%d%d", &a, &b, &c);
			cr(a, b, c);
			crr(b, a, c);
		}
		memset(dis, 1, sizeof(dis));
		q.push(1);
		dis[1] = 0;
		while(!q.empty()){
			a = q.front(); q.pop();
			v[a] = 0;
			for(i = h[a]; i; i = d[i].n){
				b = d[i].b;
				c = d[i].c;
				if(dis[b] > dis[a] + c){
					dis[b] = dis[a] + c;
					if(!v[b]){
						v[b] = 1;
						q.push(b);
					}
				}
			}
		}
		//printf("%d\n", dis[n]);
		f[1][0] = 1;
		for(i = 0; i <= k; i++) ans = (ans + dp(n, i)) % P;
		if(flag == 1) printf("-1\n");
		else printf("%d\n", ans);
		
	}
	return 0;
}

D2T1 奶酪

分析

对可以连通的圆建边跑 b f s bfs bfs 即可,最后判断一下可不可以到达顶端。

代码如下

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define eps 1e-7
#define N 1000005
#define LL long long
using namespace std;
struct node{
	int a, b, n;
}d[N * 2];
LL x[1005], y[1005], z[1005], hh, r;
int f[1005], v[1005], h[1005], n, cnt, fl;
LL getdis(int i, int j){
	return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j]);
}
void cr(int a, int b){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void bfs(int a){
	queue<int> q;
	int b, i;
	q.push(a);
	while(!q.empty()){
		a = q.front(); q.pop();
		for(i = h[a]; i; i = d[i].n){
			b = d[i].b;
			if(!v[b]){
				q.push(b);
				v[b] = 1;
			}
		}
	}
	for(i = 1; i <= n; i++){
		if(v[i] && z[i] + r >= hh) fl = 1;
	}
}
int main(){
	int i, j, T, k, m, a, b;
	scanf("%d", &T);
	while(T--){
		memset(v, 0, sizeof(v));
		memset(f, 0, sizeof(f));
		memset(h, 0, sizeof(h));
		cnt = fl = 0;
		scanf("%d%lld%lld", &n, &hh, &r);
		for(i = 1; i <= n; i++){
			scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
			if(z[i] - r <= 0) f[i] = 1;
		}
		for(i = 1; i <= n; i++){
			for(j = i + 1; j <= n; j++){
				if(4 * r * r >= getdis(i, j)) cr(i, j), cr(j, i);
			}
		}
		for(i = 1; i <= n; i++){
			if(!f[i] || v[i]) continue;
			v[i] = 1;
			bfs(i);
		}
		if(fl) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

D2T2 宝藏

TAT这道题写过了直接给代码吧

复杂度是 O ( n 3 n ) O(n3^n) O(n3n)

代码如下

//f[i][s] = max(f[i-1][s0] + i * v[s0][s^s0])
#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;
int f[12][1 << 12], v[1 << 12][1 << 12], g[1 << 12][12], mp[12][12], ans = inf;
int main(){
	int i, j, k, n, m, a, b, c, s, s0, sum;
	memset(f, 1, sizeof(f));
	memset(v, 1, sizeof(v));
	memset(g, 1, sizeof(g));
	memset(mp, 1, sizeof(mp));
	scanf("%d%d", &n, &m);
	for(i = 1; i <= m; i++){
		scanf("%d%d%d", &a, &b, &c);
		a--, b--;
		if(mp[a][b] > c) mp[a][b] = mp[b][a] = c;
	}
	/*for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(mp[i][j]) v[1 << i][1 << j] = mp[i][j];*/
	for(i = 0; i < (1 << n); i++){
		for(j = 0; j < n; j++){
			if(1 << j & i) continue;
			for(k = 0; k < n; k++) if(1 << k & i) g[i][j] = min(g[i][j], mp[j][k]);
			//printf("===%d %d %d\n", i, j, g[i][j]);
		}
	}
	for(i = 0; i < (1 << n); i++){
		s = (1 << n) - 1 - i;
		for(j = s; j; j = (j - 1) & s){
			sum = 0;
			for(k = 0; k < n; k++) if(1 << k & j) sum += g[i][k];
			v[i][j] = min(v[i][j], sum);
			//printf("===============%d %d %d\n", i, j, v[i][j]);
		}
	}
	for(i = 0; i < n; i++) f[0][1 << i] = 0;
	for(i = 1; i < n; i++){
		for(s = 0; s < (1 << n); s++){
			for(s0 = s; s0; s0 = (s0 - 1) & s) f[i][s] = min(f[i][s], f[i - 1][s0] + i * v[s0][s ^ s0]);
			//printf("%d %d %d\n", i, s, f[i][s]);
		}
	}
	for(i = 0; i < n; i++) ans = min(ans, f[i][(1 << n) - 1]);
	printf("%d", ans);
	return 0;
} 

D2T3 列队

分析

要得出正解我们还得一个一个任务看。
30 p t s 30pts 30pts,暴力模拟即可。
50 p t s 50pts 50pts,要想办法降低空间复杂度。注意到每次都只和一排和最后一列有关系,我们对询问的行列动态开空间即可。
80 p t s 80pts 80pts,即 x = 1 x = 1 x=1 的情况,每次只对第一行和最后一列操作。
首先询问第一行的第 k k k 个位置的值,我们想办法用线段树来求。
我们用每个位置代表每个值,用线段树将每个位置加上 1 1 1,每次找到区间第 k k k 大的位置,即找到了那个值,删除只用那个位置减 1 1 1 即可。
然后对于最后一列,我们每次把从第一行弹出来的值加入末尾。
每次查询,如果 k k k 大于 s u m [ r o o t [ 1 ] ] sum[root[1]] sum[root[1]],也就是第一行的总个数,就在最后一列查找第 k s u m [ r o o t [ 1 ] ] k - sum[root[1]] ksum[root[1]] 的值就可以了。
到这一来我们就可以思考 100 p t s 100pts 100pts 做法了。
首先我 80 p t s 80pts 80pts 的做法并不太好,对第一行适用而已。如果有多行就实在不知道最后一列并入每一行的值是哪些。于是我们每次要将最后一列的值汇入修改的那一行。相当于是,每一行都维护了 m 1 m-1 m1个值,最后一列维护 n n n 个值。
对于每一个汇入行的值,我们都用一个 v e c t o r vector vector 存起来,这样就保证了空间复杂度。然后做法就和 x = 1 x = 1 x=1 的情况差不多了。

代码如下

#include <bits/stdc++.h>
#define N 300005
#define M 600000
#define lson l, m, lch[rt]
#define rson m + 1, r, rch[rt]
#define LL long long
using namespace std;
vector<LL> vec[N];
LL v[M], z = 1, val, w;
int root[N], sum[N * 30], lch[N * 30], rch[N * 30], cnt;
void update(int l, int r, int &rt, int p, int c){
	if(!rt) rt = ++cnt, sum[rt] = (r - l + 1);
	sum[rt] += c;
	if(l == r) return;
	int m = l + r >> 1;
	if(p <= m) update(lson, p, c);
	else update(rson, p, c);
}
int query(int l, int r, int rt, int k){
	if(l == r) return l;
	int m = l + r >> 1;
	if(!lch[rt]) lch[rt] = ++cnt, sum[lch[rt]] = (m - l + 1);
	if(!rch[rt]) rch[rt] = ++cnt, sum[rch[rt]] = (r - m); 
	if(k <= sum[lch[rt]]) return query(lson, k);
	return query(rson, k - sum[lch[rt]]);
}
int main(){
	int i, j, n, m, q, x, y, t;
	scanf("%d%d%d", &n, &m, &q);
	for(i = 1; i <= n; i++) v[i] = z * i * m;
	for(i = 0; i <= n; i++) root[i] = ++cnt, sum[root[i]] = M;
	for(i = 1; i <= q; i++){
		scanf("%d%d", &x, &y);
		t = query(1, M, root[x], y);
		w = query(1, M, root[0], x);
		if(t <= m - 1){
			val = z * (x - 1) * m + z * t;
			update(1, M, root[x], t, -1);
			update(1, M, root[0], w, -1);
			w = v[w];
			printf("%lld\n", val);
			vec[x].push_back(w);
			v[i + n] = val;
		}
		else{
			if(vec[x].size() >= t - (m - 1)){
				update(1, M, root[x], t, -1);
				update(1, M, root[0], w, -1);
				val = vec[x][t - m];
				w = v[w];
				printf("%lld\n", val);
				vec[x].push_back(w);
				v[i + n] = val;
			}
			else{
				printf("%lld\n", v[w]);
				update(1, M, root[0], w, -1);
				v[i + n] = v[w];
			}
		}
	}
	return 0;
}