迟到1h,险些掉分,呼~
A
数据范围很小,模拟签到题。
/* * @Author: wxyww * @Date: 2020-04-10 19:52:33 * @Last Modified time: 2020-04-10 20:02:50 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int h,a,H,A; void solve() { int ans = 0; int HH = H; while(h > 0) { H = HH; while(h > 0 && H > 0) { H -= a; if(H <= 0) break; h -= A; } if(H <= 0) ans++; } printf("%d\n",ans); } int main() { int T = read(); while(T--) { h = read(),a = read(),H = read(),A = read(); if(a >= H) {puts("-1");continue;} solve(); } return 0; }
B
每当较少的数量*2<=较多的数量,就将较少的数量乘以2。算一下步数即可。
/* * @Author: wxyww * @Date: 2020-04-10 20:03:07 * @Last Modified time: 2020-04-10 20:05:18 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int main() { int T = read(); while(T--) { int n = read(),m = read(); if(n > m) swap(n,m); int ans = 0; while(n && m) { ++ans; if(n + n <= m) n += n; else --n,--m; } printf("%d\n",ans); } return 0; }
C
答案相同的题看做一个整体,统计出每个整体的大小。然后爆搜即可。
复杂度上限(k为整体的数量)
/* * @Author: wxyww * @Date: 2020-04-10 20:10:48 * @Last Modified time: 2020-04-10 20:15:24 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 100; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt; }e[N * N]; int head[N],ejs; void add(int u,int v) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } int vis[N],tot,a[N]; void dfs(int u) { a[tot]++; vis[u] = 1; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(vis[v]) continue; dfs(v); } } int ans; void solve(int pos,int na,int nb,int nc,int nd) { if(pos == tot + 1) { ans++;return; } if(a[pos] <= na) solve(pos + 1,na - a[pos],nb,nc,nd); if(a[pos] <= nb) solve(pos + 1,na,nb - a[pos],nc,nd); if(a[pos] <= nc) solve(pos + 1,na,nb,nc - a[pos],nd); if(a[pos] <= nd) solve(pos + 1,na,nb,nc,nd - a[pos]); } int main() { int na = read(),nb = read(),nc = read(),nd = read(),m = read(); while(m--) { int x = read(),y = read(); add(x,y);add(y,x); } for(int i = 1;i <= 12;++i) { if(!vis[i]) { ++tot; dfs(i); } } solve(1,na,nb,nc,nd); cout<<ans; return 0; }
D
比较经典的一个思路就是。统计出号点到每个点的距离,统计出每个点到号点的距离。
当一条边反向时,直接用计算出必须经过这条边的最短路。
然后有一个问题,如果在计算的时候经过的这条边的正向边,现在反过来这条正向边不存在了,那不就错了吗?
这样可能确实会影响我们计算出的新最短路,但是题目问的是最短路是否会变短,我们只要上述情况不会导致最短路变短即可。
对于一条边,如果经过了此边,也就是,反向之后计算出的新路径长度为,所以这样路径长度显然比不经过此边的时候多了。所以并不会影响最终答案。
/* * @Author: wxyww * @Date: 2020-04-10 20:33:31 * @Last Modified time: 2020-04-10 20:46:10 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 200010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt,w,u; }e[N]; int head[N],ejs; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].u = u;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w; } ll dis1[N],dis2[N]; int vis[N]; queue<int>q; void spfa(ll *dis,int S) { dis[S] = 0; q.push(S); while(!q.empty()) { int u = q.front();q.pop();vis[u] = 0; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; if(!vis[v]) vis[v] = 1,q.push(v); } } } } int main() { int n = read(),m = read(); for(int i = 1;i <= m;++i) { int u = read(),v = read(),w = read(); add(u,v,w); } memset(dis1,0x3f,sizeof(dis1)); spfa(dis1,1); memset(head,0,sizeof(head)); ejs = 0; memset(dis2,0x3f,sizeof(dis2)); for(int i = 1;i <= m;++i) add(e[i].v,e[i].u,e[i].w); spfa(dis2,n); int Q = read(); ll ans = dis1[n]; while(Q--) { int x = read(); if(dis1[e[x].u] + dis2[e[x].v] + e[x].w < ans) puts("YES"); else puts("NO"); } return 0; }
E
首先想到二分答案。先二分一个。然后判断是否能找出至少个长度为的不相交的相同子串。
用表示前i个位置哈希值为j的不想交子串个数最多为多少。转移就是。显然爆炸。
考虑一个延时加入,用表示哈希值为的答案。当枚举到时才用更新。这样每次判断复杂度就成了
在加上外层套的二分答案复杂度。总的复杂度就是,理论上讲是可以在牛客上跑过去的。我没跑过去,只好用了
/* * @Author: wxyww * @Date: 2020-04-10 20:50:36 * @Last Modified time: 2020-04-10 21:07:19 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<unordered_map> #include<queue> #include<vector> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 200010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } char s[N]; unordered_map<ull,int>ma; ull hs[N],base[N],B = 27; ull get(int l,int r) { return hs[r] - hs[l - 1] * base[r - l + 1]; } int n,K,f[N]; bool check(int x) { ma.clear(); memset(f,0,sizeof(f)); for(int i = x;i <= n;++i) { if(i - x >= x) { ma[get(i - x - x + 1,i - x)] = max(f[i - x],ma[get(i - x - x + 1,i - x)]); } ull t = get(i - x + 1,i); f[i] = ma[t] + 1; if(f[i] >= K) return true; } return false; } int main() { n = read(),K = read(); scanf("%s",s + 1); base[0] = 1; for(int i = 1;i <= n;++i) { hs[i] = hs[i - 1] * B + s[i] - 'a' + 1; base[i] = base[i - 1] * B; } int l = 1,r = n,ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) ans = mid,l = mid + 1; else r = mid - 1; } cout<<ans<<endl; return 0; }
F
不会点分树,看完官方题解临时学了一发。
点分树其实就是将点分治过程中每个重心向下一层的重心连边。因为点分治最多递归层,所以点分树的树高不超过
然后对于点分树上每个店开一个动态开点线段树。维护子树中每种成熟度到当前点的最近距离。
修改和查询就从当前点暴力向上跳即可。
真的调了好久~
文末赋上一份自己写的数据生成器(纯随机),希望能帮助大家调题。(๑•ᴗ•๑)
/* * @Author: wxyww * @Date: 2020-04-11 08:19:33 * @Last Modified time: 2020-04-11 10:25:52 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 1000010,logN = 20,INF = 1e9 + 8; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int w,v,nxt; }e[N << 1]; int head[N],ejs; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w; } //利用LCA求dist int w[N],lca[N][logN + 1],dis[N],dep[N]; void dfs(int u,int fa) { dep[u] = dep[fa] + 1; for(int i = 1;i <= logN;++i) lca[u][i] = lca[lca[u][i - 1]][i - 1]; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == fa) continue; dis[v] = dis[u] + e[i].w; lca[v][0] = u; dfs(v,u); } } int LCA(int x,int y) { if(dep[x] < dep[y]) swap(x,y); for(int i = logN;i >= 0;--i) if(dep[lca[x][i]] >= dep[y]) x = lca[x][i]; for(int i = logN;i >= 0;--i) if(lca[x][i] != lca[y][i]) x = lca[x][i],y = lca[y][i]; if(x != y) x = lca[x][0]; return x; } int dist(int x,int y) { return dis[x] + dis[y] - 2 * dis[LCA(x,y)]; } //点分树 int mx[N],siz[N],fa[N],vis[N]; vector<int>tmp; void get(int u,int father) { siz[u] = 1; mx[u] = 0; tmp.push_back(u); for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(vis[v] || v == father) continue; get(v,u); siz[u] += siz[v]; mx[u] = max(mx[u],siz[v]); } } int build(int u) { tmp.clear(); get(u,0); int rt = 0; int k = tmp.size(); for(int i = 0;i < k;++i) { if(mx[tmp[i]] <= k / 2 && (k - siz[tmp[i]]) <= k / 2) { rt = tmp[i];break; } } vis[rt] = 1; for(int i = head[rt];i;i = e[i].nxt) { int v = e[i].v; if(vis[v]) continue; fa[build(v)] = rt; } return rt; } //动态开点线段树 struct TREE { int ls,rs,val; }tree[10000010]; int root[N],tot; void update(int &rt,int l,int r,int pos,int w) { if(!rt) { rt = ++tot; tree[rt].val = INF; } if(l == r) { tree[rt].val = min(tree[rt].val,w); return; } int mid = (l + r) >> 1; if(pos <= mid) update(tree[rt].ls,l,mid,pos,w); else update(tree[rt].rs,mid + 1,r,pos,w); tree[rt].val = min(tree[tree[rt].ls].val,tree[tree[rt].rs].val); } int query(int rt,int l,int r,int L,int R) { if(!rt) return INF; if(L <= l && R >= r) return tree[rt].val; int ans = INF; int mid = (l + r) >> 1; if(L <= mid) ans = min(ans,query(tree[rt].ls,l,mid,L,R)); if(R > mid) ans = min(ans,query(tree[rt].rs,mid + 1,r,L,R)); return ans; } int main() { int n = read(),m = read(); for(int i = 1;i <= n;++i) w[i] = read(); for(int i = 1;i < n;++i) { int u = read(),v = read(),w = read(); add(u,v,w);add(v,u,w); } dfs(1,0); build(1); tree[0].val = INF; for(int i = 1;i <= n;++i) { int t = i; while(t) { update(root[t],1,10000,w[i],dist(t,i)); t = fa[t]; } } while(m--) { int opt = read(); if(opt == 1) { int u = read(),x = read(); int t = u; while(t) { update(root[t],1,10000,x,dist(t,u)); t = fa[t]; } } else { int u = read(),l = read(),r = read(); int ans = INF,t = u; while(t) { ans = min(ans,dist(u,t) + query(root[t],1,10000,l,r)); t = fa[t]; } if(ans > 1e9) puts("-1"); else printf("%d\n",ans + ans); } } return 0; }
F题数据生成器
/* * @Author: wxyww * @Date: 2020-04-11 09:55:37 * @Last Modified time: 2020-04-11 09:58:44 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int Rand(int l,int r) { return rand() % (r - l + 1) + l; } int main() { srand(time(0)); int n = Rand(5,10),m = Rand(10,20); printf("%d %d\n",n,m); for(int i = 1;i <= n;++i) printf("%d ",Rand(1,10)); puts(""); for(int i = 2;i <= n;++i) { printf("%d %d %d\n",Rand(1,i - 1),i,Rand(1,10)); } while(m--) { int opt = Rand(1,2); printf("%d ",opt); if(opt == 1) { printf("%d %d\n",Rand(1,n),Rand(1,10)); } else { int l = Rand(1,10); printf("%d %d %d\n",Rand(1,n),l,Rand(l,10)); } } return 0; }