这道题就是一道$log$方 枚举乘以$b$的次数 那么加上$a$的次数穿插其中
那么剩下的数可以被表示为 $a * b ^ k1 +ａ * b ^ k2 + a * b ^ k3 + ... $
同样的 剩下的树可以被表示成$b$进制的数 这个是同理的 所以就从枚举的次数开始往下能减得就减掉就可以了
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 50; ll p[N],a,b,S,T; int tot = 0; ll check(int t) { ll res = T,ans = t; res -= S * p[t]; if(res < 0) return -1; for(int i = t;i >= 0;i --) { if(res - a * p[i] >= 0) { ll s = res / (a * p[i]); ans += s; res -= s * a * p[i]; } if(! res) return ans; } if(res != 0) return -1; } void Solve( ) { scanf("%lld%lld%lld%lld",& S,& T,& a,& b); p[0] = 1; for(int i = 1;i < N;i ++) { p[i] = p[i - 1] * b; if(p[i] >= T) { if(p[i] == T) { tot = i; break;} else if(p[i] > T) { tot = i - 1; break; } if(p[i] > 1e9 + 1) { tot = i - 1; break;} } } ll ans = -1; for(int i = 0;i <= tot;i ++) { ll tim = check(i); if(ans == -1) ans = tim; else { if(tim == -1) continue; else ans = min(ans, tim); } } printf("%lld ",ans); } int main( ) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); Solve( ); }
这道题是原题啊 之前还写过博客的我 就不说了 高中线性规划题目
代码
#include <bits/stdc++.h> #define oo 1e9 using namespace std; const int N = 1e5 + 5; int n,m,a[N],b[N]; void Init( ) { scanf("%d%d",& n,& m); for(int i = 1;i <= m;i ++) scanf("%d%d",& a[i],& b[i]); } bool check(int t) { int ma1 = -oo,mi1 = oo; int ma2 = -oo,mi2 = oo; for(int i = 1;i <= m;i ++) if(abs(a[i] - b[i]) > t) { ma1 = max(a[i] + b[i] - t, ma1); mi1 = min(a[i] + b[i] + t, mi1); ma2 = max(a[i] - b[i] - t, ma2); mi2 = min(a[i] - b[i] + t, mi2); } return (ma1 <= mi1) && (ma2 <= mi2); } void Solve( ) { int l = 0,r = oo,ans = oo; while(l <= r) { int mid = l + r >> 1; if(check(mid)) ans = mid,r = mid - 1; else l = mid + 1; } printf("%d ",ans); } int main( ) { freopen("b.in","r",stdin); freopen("b.out","w",stdout); Init( ); Solve( ); }
这道题是一道图论题
至于为什么是$n - cnt$因为对于每个环内的关系 我们都可以定下一个元素 使得他不断的与应该放在他这个位置的值进行交换
那么这个时候应该进行$size - 1$次 那么总的就是$n - cnt$次
代码
#include <bits/stdc++.h> using namespace std; const int N = 4e5 + 5; int n,a[N],b[N],x[N],y[N],head[N],nex[N],tov[N]; int tot = 0,cnt = 0,stk[N],top,dfn[N],low[N],idc; bool vis[N]; int read( ) { int t = 1,ans = 0; char x; x = getchar( ); while(x < '0' || x > '9') { if(x == '-') t = -1; x = getchar( ); } while(x >= '0' && x <= '9') { ans = ans * 10 + x - '0'; x = getchar( ); } return ans * t; } void Init( ) { scanf("%d",& n); for(int i = 0;i < n;i ++) { scanf("%d",& a[i]); b[i] = a[i]; } for(int i = 1;i <= 2 * n;i ++) scanf("%d%d",& x[i],& y[i]); } void add(int u,int v) { tot ++; nex[tot] = head[u]; tov[tot] = v; head[u] = tot; } void tarjan(int u) { vis[u] = true; stk[++ top] = u; dfn[u] = low[u] = ++ idc; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(! dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if(vis[v]) { low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]) { cnt ++; while(1) { int x = stk[top --]; vis[x] = false; if(x == u) break; } } } void clear( ) { memset(head, 0, sizeof(head)); tot = 0; memset(dfn, 0, sizeof(dfn)); cnt = 0; memset(vis, 0, sizeof(vis)); top = 0; idc = 0; for(int i = 0;i < n;i ++) b[i] = a[i]; } bool check(int mid) { clear( ); for(int i = 1;i <= mid;i ++) swap(b[x[i]], b[y[i]]); for(int i = 0;i < n;i ++) add(b[i], i); for(int i = 0;i < n;i ++) if(! dfn[i]) tarjan(i); return n - cnt <= mid; } void Solve( ) { int l = 0,r = 2 * n,ans = 2 * n; while(l <= r) { int mid = l + r >> 1; if(check(mid)) ans = mid,r = mid - 1; else l = mid + 1; } printf("%d ",ans); } int main( ) { freopen("c.in","r",stdin); freopen("c.out","w",stdout); Init( ); Solve( ); }