### T1
列个式子(或者直接猜)容易发现,小的放前面比放后面更优,所以sort一遍,前一半加,后一半乘即可
### T2
将每个数表示成$k^b$的形式,于是直接累加b即可比大小
注意细节,比如可能爆 long long
### T3
画图可以发现答案只会在$-1$ ~ $3$之间,先丢掉$(0,0)$,对剩下的所有点极角排序,分情况讨论:
1. $(0,0)$输出0
2. $(x,y)$和某个$(a_i,b_i)$的直线过$(0,0)$,输出1,可以二分找到这个点
3. 假设所有点与$(0,0)$在同一条直线上,那么由于步骤2没有输出1,一定无解,输出-1
4. 否则$(a_i,b_i)$与$(0,0)$的连线至少有两种,画图可以发现如果$n > 2$一定输出2
5. 如果$n=2$,只有当询问点,$(0,0)$和两个点构成了一个平行四边形时会输出3,否则输出2
```cpp
#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int n,q;
struct pts
{
ll x,y;
pts() { }
pts(ll x,ll y) : x(x),y(y) { }
pts operator + (const pts &a)const { return pts(x + a.x,y + a.y); }
pts operator - (const pts &a)const { return pts(x - a.x,y - a.y); }
ll operator ^ (const pts &a)const { return x * a.y - y * a.x; }
bool operator == (const pts &a)const { return (x == a.x) && (y == a.y); }
bool operator < (const pts &a)const
{
return ((*this) ^ a) > 0;
}
}pt[N];
bool sm(pts a,pts b) { return ((a ^ b) == 0); }
int main()
{
freopen("c12.in","r",stdin);
freopen("c12.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)
{
scanf("%lld%lld",&pt[i].x,&pt[i].y);
if(pt[i].x == 0 && pt[i].y == 0) --i,--n;
}
sort(pt + 1,pt + n + 1);
bool lin = sm(pt[1],pt[n]);//所有的点都在同一条线上
while(q--)
{
pts a; scanf("%lld%lld",&a.x,&a.y);
if(a.x == 0 && a.y == 0) { puts("0"); continue; }
int it = lower_bound(pt + 1,pt + n + 1,a) - pt;
if(1 <= it && it <= n && sm(pt[it] , a)) { puts("1"); continue; }
if(lin) { puts("-1"); continue; }
if(n > 2) { puts("2"); continue; }
if(a == (pt[1] + pt[2])) puts("3");
else puts("2");
}
return 0;
}
```
### T4
如果分解出来的序列存在一个$a = \prod_{i=1}^{t} p_i^{k_i},t > 1$,那么将$a$换成$p_1^{k_1},p_2^{k_2}...$一定更优(前者能组合出来的lcm后者都可以组合出来,而且后者的和不大于前者)
于是分解出来的每个数一定是1或者$p^k$的形式,线筛出n以内的质因子,背包DP即可,dp的时候因为取了模不能比大小,所以要取个log
(虽然质因子可能很多,但是可以发现不同质因子的贡献都是一样的,所以质因子越小越好,实际上能用的质因子只会有一百多个)
~~也可以打表搞出来~~
```cpp
#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int n;
int p[N],isnotp[N],cnt;
pair<double,ll> f[N];
void init(int maxn)
{
for(int i=2;i<=maxn;++i)
{
if(!isnotp[i]) p[++cnt] = i;
for(int j=1;j<=cnt&&(ll)p[j]*i<=maxn;++j)
{
isnotp[p[j] * i] = 1;
if(i % p[j] == 0) break;
}
}
}
int main()
{
//freopen("d10.in","r",stdin);
//freopen("d10.out","w",stdout);
scanf("%d",&n);
init(n);
int now = 0,sum = 0;
for(int i=1;i<=cnt;++i)
{
now = i;
sum += p[i];
if(sum > n) break;
}
f[0].first = 0; f[0].second = 1;
for(int i=1;i<=now;++i)
{
for(int j=n;j>=1;--j)
{
ll t = p[i],pp = p[i];
for(int k=1;t <= j;++k,pp*=p[i],t += pp)
{
pair<double,ll> nxt = make_pair(f[j - t].first + log2(k + 1),f[j - t].second * (k + 1) % mod);
f[j] = max(f[j] , nxt);
}
}
}
pair<double,ll> ans; ans.first = -1;
for(int i=0;i<=n;++i) ans = max(ans,f[i]);
printf("%lld\n",ans.second);
return 0;
}
```
### T5
将一个点拆成入点和出点,入点向出点连q条边,流量为1,费用分别为$a,a+b,a+2b...$,源点向所有$x_i$连一条流量为1费用为0的边,$y_i$向汇点连一条流量为1费用为0的边,原图的边连接出点和入点,流量为inf,费用为0,然后跑最小费用最大流即可
```cpp
#include<bits/stdc++.h>
#define N 405
#define M 200005
using namespace std;
int n,m,q,s,t;
int in[N],out[N],a[N],b[N];
int dis[N],flow[N],exist[N];
int pre[N],preedge[N];
struct Edge
{
int next,to,flow,dis;
}edge[M << 1]; int head[N],cnt = 1;
void add_edge(int from,int to,int flow,int dis)
{
edge[++cnt].next = head[from];
edge[cnt].to = to;
edge[cnt].flow = flow;
edge[cnt].dis = dis;
head[from] = cnt;
}
void add(int from,int to,int flow,int dis)
{
add_edge(from,to,flow,dis);
add_edge(to,from,0,-dis);
}
bool spfa(int s,int t)
{
memset(dis,100,sizeof(dis));
memset(flow,100,sizeof(flow));
memset(exist,0,sizeof(exist));
queue<int> q;
pre[t]=-1; exist[s]=1; dis[s]=0; q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();exist[u]=0;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].flow>0&&dis[v]>dis[u]+edge[i].dis)
{
dis[v]=dis[u]+edge[i].dis;
flow[v]=min(edge[i].flow,flow[u]);
pre[v]=u;
preedge[v]=i;
if(!exist[v])
{
exist[v]=1;
q.push(v);
}
}
}
}
return pre[t]!=-1;
}
int MCMF()
{
int ret = 0;
while(spfa(s,t))
{
ret += flow[t] * dis[t];
int now = t;
while(now!=s)
{
edge[preedge[now]].flow -= flow[t];
edge[preedge[now]^1].flow += flow[t];
now=pre[now];
}
}
return ret;
}
int main()
{
// freopen("9.in","r",stdin);
// freopen("e9.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
s = 0,t = N - 1;
for(int i=1;i<=n;++i)
{
int a,b; scanf("%d%d",&a,&b);
for(int j=1;j<=q * 2;++j) add(i,i + n,1,a + (j - 1) * b);
}
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
add(x + n,y,q * 2,0);
add(y + n,x,q * 2,0);
}
for(int i=1;i<=q;++i)
{
int x; scanf("%d",&x);
add(s,x,1,0);
}
for(int i=1;i<=q;++i)
{
int x; scanf("%d",&x);
add(x + n,t,1,0);
}
printf("%d\n",MCMF());
return 0;
}
```
### T6
由于加和乘运算可以表示成$ax + b$的形式,可以通过维护a和b来表示一块运算,合并可以做到$O(1)$,其逆运算可以列个式子$O(logn)$做
对于每一个点,预处理出它到根节点这段路径,$d = 1 $ ~ $\sqrt{n}$时,向上走和向下走的表达式,这个表达式可以从d祖先处转移过来做到$O(1)$计算(可以理解为前缀和一样的东西);$d\leq \sqrt{n}$时用这个表达式做差就能得到一条链的表达式,$d>\sqrt{n}$时直接暴力算就行了
跳k级祖先:可以倍增$O(logn)$或者长链剖分$O(1)$求(~~实测加了个深度剪枝的倍增跑得比长链剖分还快~~)
根据跳k级祖先的实现方法,总复杂度为$O(n\sqrt{n}logn)$或$O(n\sqrt{n})$
~~如果被卡常了可以调一下块的大小,我是开的150过的~~
如果有把std按在地上锤的方法请联系出题人
```cpp
#include<bits/stdc++.h>
#define N 100005
#define pr pair<int,int>
using namespace std;
const int mod = 998244353;
const int sqr = 150;
int n,q,lg[N];
int fa[N],dep[N],f[N][18];
int st[N],top;
vector<int> s[N];
pr a[N],up[N][sqr + 5],dw[N][sqr + 5];
inline int qp(int a,int b) { int ret=1; for(;b;b>>=1,a=1ll*a*a%mod) if(b & 1) ret=1ll*ret*a%mod; return ret; }
inline pr merge(pr a,pr b) { return make_pair(1ll * a.first * b.first % mod , (1ll * a.second * b.first + b.second) % mod); }
inline int kfa(int rt,int k)
{
for(register int i=lg[k];i>=0;--i) if(k >> i & 1) rt = f[rt][i];
return rt;
}
inline int lca(int x,int y)
{
if(dep[x] < dep[y]) swap(x,y);
for(int i=17;i>=0;--i) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
if(x == y) return x;
for(int i=17;i>=0;--i) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
return f[x][0];
}
void get(int rt)
{
int x = rt;
for(int d=1;d<=sqr;++d)
{
x = fa[x];
up[rt][d] = a[rt];
if(x) up[rt][d] = merge(up[rt][d] , up[x][d]);
dw[rt][d] = a[rt];
if(x) dw[rt][d] = merge(dw[x][d] , dw[rt][d]);
}
}
void dfs(int rt)
{
dep[rt] = dep[fa[rt]] + 1;
f[rt][0] = fa[rt];
for(int i=1;i<18;++i) f[rt][i] = f[f[rt][i - 1]][i - 1];
get(rt);
for(auto v : s[rt])
{
if(v == fa[rt]) continue;
fa[v] = rt; dfs(v);
}
}
int brute(int x,int y,int c,int d)
{
int l = lca(x,y);
pr ret = make_pair(1,0);
int cnt = 0;
while(1)
{
ret = merge(ret , a[x]);
if(dep[kfa(x,d)] >= dep[l]) x = kfa(x,d);
else break;
}
int fir = dep[l] + (d - (dep[x] - dep[l]));
fir = dep[y] - fir;
for(;fir >= 0;fir -= d) ret = merge(ret,a[kfa(y,fir)]);
return (1ll * c * ret.first % mod + ret.second) % mod;
}
int solve(int x,int y,int c,int d)
{
pr ret = make_pair(1,0);
int A,B,C,D;
int l = lca(x,y),tmp = kfa(x,((dep[x] - dep[l]) / d + 1) * d);
A = up[tmp][d].first; B = up[tmp][d].second;
C = up[x][d].first; D = up[x][d].second;
if(!tmp) ret = up[x][d];
else ret = make_pair(1ll * C * qp(A,mod - 2) % mod , 1ll * (D - B) * qp(A,mod - 2) % mod);
int nxt = ((dep[x] - dep[l]) / d + 1) * d - (dep[x] - dep[l]) + dep[l];
if(nxt <= dep[y])
{
y = kfa(y,dep[y] - (nxt + ((dep[y] - nxt) / d * d)));
tmp = kfa(y,((dep[y] - dep[l] - 1) / d + 1) * d);
A = dw[tmp][d].first; B = dw[tmp][d].second;
C = dw[y][d].first; D = dw[y][d].second;
if(!tmp) ret = merge(ret , dw[y][d]);
else ret = merge(ret , make_pair(1ll * C * qp(A,mod - 2) % mod , (D - 1ll * B * C % mod * qp(A,mod - 2) % mod) % mod));
}
return (1ll * c * ret.first % mod + ret.second) % mod;
}
int main()
{
//freopen("f8.in","r",stdin);
//freopen("f8.out","w",stdout);
lg[0] = -1; for(int i=1;i<N;++i) lg[i] = lg[i >> 1] + 1;
scanf("%d%d",&n,&q);
for(int i=1;i<n;++i)
{
int x,y; scanf("%d%d",&x,&y);
s[x].push_back(y);
s[y].push_back(x);
}
for(int i=1;i<=n;++i)
{
char op[2]; int x;
scanf("%s%d",op,&x);
if(op[0] == '+') a[i] = make_pair(1,x);
else a[i] = make_pair(x,0);
}
dfs(1);
while(q--)
{
int x,y,c,d;
scanf("%d%d%d%d",&x,&y,&c,&d);
if(d > sqr) printf("%d\n",(brute(x,y,c,d) % mod + mod) % mod);
else printf("%d\n",(solve(x,y,c,d) % mod + mod) % mod);
}
return 0;
}
```
全部评论
(0) 回帖