D1T1 小凯的疑惑
分析
求不能用 ax+by=t(x>0,y>0) 表示的最大值 t。
我们不妨求最小 t0，满足 t≥t0时， t 恒能用 ax+by 表示。
设 t0=ax+by。
设 ax′+by′=1,ax′′+by′′=1，其中 x′,y′′分别是最小的正数解。
我们要让 t0−1 无解，最大可以满足的 x,y 就是 x=x′−1， y=y′′−1。
这样子 t0−1 一定无法构造出两个正整数解，不是 x 小于 0 就是 y 小于 0。
于是 ans=a(x′−1)+b(y′′−1)−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)的。其实想一想也知道，统计方案，就是个 dp。设 dis[a] 为到 a 的最短路长度。
我们用 f[a][k] 表示以 a 为终点， 1 到 a 的距离为 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 奶酪
分析
对可以连通的圆建边跑 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(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 列队
分析
要得出正解我们还得一个一个任务看。
30pts，暴力模拟即可。
50pts，要想办法降低空间复杂度。注意到每次都只和一排和最后一列有关系，我们对询问的行列动态开空间即可。
80pts，即 x=1 的情况，每次只对第一行和最后一列操作。
首先询问第一行的第 k 个位置的值，我们想办法用线段树来求。
我们用每个位置代表每个值，用线段树将每个位置加上 1，每次找到区间第 k 大的位置，即找到了那个值，删除只用那个位置减 1 即可。
然后对于最后一列，我们每次把从第一行弹出来的值加入末尾。
每次查询，如果 k 大于 sum[root[1]]，也就是第一行的总个数，就在最后一列查找第 k−sum[root[1]] 的值就可以了。
到这一来我们就可以思考 100pts 做法了。
首先我 80pts 的做法并不太好，对第一行适用而已。如果有多行就实在不知道最后一列并入每一行的值是哪些。于是我们每次要将最后一列的值汇入修改的那一行。相当于是，每一行都维护了 m−1个值，最后一列维护 n 个值。
对于每一个汇入行的值，我们都用一个 vector 存起来，这样就保证了空间复杂度。然后做法就和 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;
}
京公网安备 11010502036488号