最后一次j组了，写篇题解纪念一下
A
假如 \(a=1\)，\(a^b=1\)
假如 \(a>1\)，可以发现当 \(b>30\) 时 \(a^b\) 必然大于 \(10^9\)
于是我们可以暴力计算，如果计算的过程中大于 \(10^9\)，输出 -1
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'
||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<=
'9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define N
//#define M
//#define mo
int n, m, i, j, k, T;
int a, b;
signed main()
{
freopen("pow.in", "r", stdin);
freopen("pow.out", "w", stdout);
// srand(time(0));
// T=read();
// while(T--) {
//
// }
a=read(); b=read();
if(a==1) return printf("1"), 0;
for(i=k=1; i<=b; ++i)
{
k*=a;
if(k>(int)1e9) return printf("-1"), 0;
}
printf("%lld\n", k);
return 0;
}
B
化简式子：
\[e_i\times d_i=(p_i-1)(q_i-1)+1 \]\[e_i\times d_i=p_iq_i-p_i-q_i+2 \]\[e_i\times d_i=n_i-p_i-q_i+2 \]所以 \(p,q\) 满足以下条件：
-
\(p_i+q_i=n_i-e_i\times d_i+2\)
-
\(p_i\times q_i=n_i\)
令
\(q_i=m-p_i\)，\(l=p_i\times q_i=p_i(m-p_i)\)
和一定，差小积大
二分 \(p_i\)，求出当前的 \(l\)
- \(l>n\)，缩小 \(p_i\)
- \(l<n\)，扩大 \(p_i\)
无解就是二分出来不满足条件
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'
||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<=
'9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define N
//#define M
//#define mo
int n, m, i, j, k, T;
int l, r, e, d, mid;
signed main()
{
freopen("decode.in", "r", stdin);
freopen("decode.out", "w", stdout);
// srand(time(0));
T=read();
while(T--) {
n=read(); e=read(); d=read();
m=n-e*d+2;
// printf("%lld\n", m);
if(m<=1) printf("NO\n");
else
{
l=1; r=m/2;
while(l<r)
{
mid=(l+r+1)>>1;
if(mid*(m-mid)<=n) l=mid;
else r=mid-1;
}
for(i=max(1ll, l-5); i<=min(r+5, m-1); ++i)
if(i*(m-i)==n) {
printf("%lld %lld\n", i, m-i);
break;
}
if(i>min(r+5, m-1)) printf("NO\n");
}
}
return 0;
}
C
1|0&1 ，正常顺序：1|(0&1)
怎么求表达式的值？
- 没有括号，没有
&操作
0|1|1|0|1...
- 没有括号（顺带求一类短路）
0|1&0|1&0&1|0...
以 | 分段，分别计算每一段的值，变成第一种情况
- 有括号
0|(1&0|1&1)&1|
递归处理括号内的内容
求被短路:
a|b|c|d|e...
此时求二类短路
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'
||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<=
'9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define N 1000010
//#define M
//#define mo
struct node
{
int x=0, a=0, b=0;
}z[N];
int n, m, i, j, k, T;
int top;
char s[N];
node calc(int x)
{
int st=top, m=0;
node l, ans;
while(s[++k]!=')')
{
if(s[k]=='&')
{
if(z[top].x==0) ++z[top].a, m=-1;
else m=1;
}
else if(s[k]=='|') continue;
else
{
if(s[k]=='(') l=calc(k+1);
else l.x=s[k]-'0', l.a=l.b=0;
if(m==1)
{
z[top].a+=l.a;
z[top].b+=l.b;
z[top].x&=l.x;
}
else if(m!=-1) z[++top]=l;
m=0;
}
}
for(int i=st+1; i<=top; ++i)
{
// printf("%lld\n", z[i].a);
if(ans.x) ++ans.b;
else ans.x|=z[i].x, ans.a+=z[i].a, ans.b+=z[i].b;
}
top=st;
// printf("%lld %lld\n", x, ans.x);
return ans;
}
signed main()
{
freopen("expr.in", "r", stdin);
freopen("expr.out", "w", stdout);
// srand(time(0));
// T=read();
// while(T--) {
//
// }
scanf("%s", s+1);
n=strlen(s+1); s[n+1]=')';
node t=calc(1);
printf("%lld\n%lld %lld", t.x, t.a, t.b);
return 0;
}
D
先按 \(x\) 坐标排序，再按 \(y\) 坐标排序（保证无后效性）
排好后的点对 \((x_i,y_i)\) 和 \((x_j, y_j)\)，假设 \(i<j\)，\(i\) 必然不能接在 \(j\) 后面
假如 \(j\) 能接在 \(i\) 后面，它们之间需要 \(x_j-x_i+y_j-y_i-1\) 个过继点
\(j\) 能接在 \(i\) 后面，满足 \(x_j\geq x_i\) 且 \(y_j\geq y_i\)
设 \(dp(u,i)\) 代表以第 \(u\) 个点为结尾，且用了 \(i\) 个过继点的最长子序列
枚举上一个给定点 \(v\)，
\[dp(u,i)=dp(v,i-(x_u-x_v+y_u-y_v-1))+x_u-x_v+y_u-y_v \]最后答案：\(\max dp(u,i)+k-i\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar(
);}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48
);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define inF 0x3f3f3f3f3f3f3f3f
//#define mo
#define N 200010
#define M 2510
int n, m, i, j, k, T;
int f[N][25], a[N], c[N], dp[N];
int g[N][25], dep[N], ans;
int s[M][M], r[M][M], flg[N];
int q, K, u, v, st, ed, len;
vector<int>G[N];
vector<int>Z[N];
queue<int>que;
void dfs(int x, int fa)
{
dep[x]=dep[fa]+1;
for(int y : G[x])
{
if(y==fa) continue;
dfs(y, x); f[y][0]=x, g[y][0]=a[y];
}
}
int lca(int x, int y)
{
if(x==y) return x;
if(dep[x]<dep[y]) swap(x, y);
for(int k=22; k>=0; --k)
if(dep[f[x][k]]>=dep[y])
ans+=g[x][k], x=f[x][k];
if(x==y) return x;
for(int k=22; k>=0; --k)
if(f[x][k]!=f[y][k])
ans+=g[x][k]+g[y][k], x=f[x][k], y=f[y][k];
ans+=a[f[x][0]];
return f[x][0];
}
void sol1()
{
while(q--)
{
st=read(); ed=read();
ans=0; k=lca(st, ed);
printf("%lld\n", ans);
}
}
void sol2()
{
while(q--)
{
st=read(); ed=read();
ans=0; k=lca(st, ed);
len=dep[st]+dep[ed]-2*dep[k]+1;
if(K==1) printf("%lld\n", ans);
else
{
m=0;
while(st!=k) c[++m]=st, st=f[st][0];
c[++m]=k;
m=len;
while(ed!=k) c[m--]=ed, ed=f[ed][0];
dp[0]=inF; dp[1]=a[c[1]];
for(i=2; i<=len; ++i)
{
dp[i]=inF;
for(j=1; j<=K; ++j)
if(i-j>=0)
{
// printf("%lld %lld\n", i, i)
dp[i]=min(dp[i], dp[i-j]+a[c[i]]);
}
}
printf("%lld\n", dp[len]);
}
}
}
void pao(int x)
{
que.push(x); r[x][x]=a[x]; flg[st]=1;
while(!que.empty())
{
u=que.front(); que.pop();
for(int v : Z[u])
{
if(r[x][u]+a[v]<r[x][v])
{
r[x][v]=r[x][u]+a[v];
que.push(v);
}
}
}
}
signed main()
{
freopen("transmit.in", "r", stdin);
freopen("transmit.out", "w", stdout);
// srand(time(0));
// T=read();
// while(T--) {
//
// }
n=read(); q=read(); K=read();
for(i=1; i<=n; ++i) a[i]=read();
for(i=1; i<n; ++i)
{
u=read(); v=read();
G[u].pb(v); G[v].pb(u);
}
dfs(1, 0);
// for(i=1; i<=n; ++i) printf("%lld ", dep[i]);
// printf("\n");
for(k=1; k<=22; ++k)
for(i=1; i<=n; ++i)
f[i][k]=f[f[i][k-1]][k-1],
g[i][k]=g[i][k-1]+g[f[i][k-1]][k-1];
if(K==1) return sol1(), 0;
if(q>=2500) return sol2(), 0;
memset(r, 0x3f, sizeof(r));
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
s[i][j]=dep[i]+dep[j]-2*dep[lca(i, j)]+1;
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
{
// printf("s(%lld %lld)=%lld\n", i, j, s[i][j]);
if(s[i][j]<=K+1) Z[i].pb(j);
}
while(q--)
{
st=read(); ed=read();
if(!flg[st]) pao(st);
printf("%lld\n", r[st][ed]);
}
return 0;
}