所以分差到底要不要取绝对值啊
3分钟出暴力,十分钟码好,然后样例过不去…
好吧,我是sb,求中位数之前是要排序的。
直接冲暴力,50pts。
\(w=3\) 的点,开个桶记录一下又有20pts
还有人冲平衡树
正解:
题解曰:
然后注意到这题的输入很诡异,其实可以当做是随机数据
我:????
好吧,其实是我太菜了,取模操作让这个数列分布均匀。
数据范围:\(w\le k\le n\),所以不应该是取模操作吗
既然是随机数据 那么它就满足分布均匀这一性质,所以,中位数的值变化是常数级的我不知道该怎么来描述,所以这句话摘自题解
那么只需要用个指针,维护中位数的位置就好了,对奇偶分类讨论即可。
有个sb坑点,计算 \(s1\) 的时候可能会爆int。
小优化:
素数个数只筛到 \(n\) 个就够了。
具体实现见code。
Code
#include<bitset>
#include<cstdio>
#define re register
const int N = 1e7+10;
const int T = 1.8e8+10;
namespace OMA
{
int n,k,w;
double sum;
int nt[N];
int s1[N],s2[N];
int cnt,pri[N];
std::bitset<T>vis;
inline void opt()
{
for(re int i=2; i<=T,cnt<=n; i++)
{
if(!vis[i])
{ vis[pri[++cnt] = i] = 1; }
for(re int j=1; j<=cnt&&i*pri[j]<=T; j++)
{
vis[i*pri[j]] = 1;
if(!(i%pri[j]))
{ break ; }
}
}
}
int mid[2],pos[2],tmp[2];
signed main()
{
scanf("%d%d%d",&n,&k,&w),opt();
for(re int i=1; i<=n; i++)
{ s1[i] = 1LL*i*pri[i]%w; }
for(re int i=1; i<=n; i++)
{ s2[i] = s1[i]+s1[i/10+1]; }
for(re int i=1; i<=k-1; i++)
{ nt[s2[i]]++; }
if(k&1)
{
mid[0] = k/2+1;
for(re int i=k; i<=n; i++)
{
nt[s2[i]]++;
if(s2[i]<=tmp[0])
{ pos[0]++; }
if(i>k)
{
nt[s2[i-k]]--;
if(s2[i-k]<=tmp[0])
{ pos[0]--; }
}
while(pos[0]<mid[0])
{ pos[0] += nt[++tmp[0]]; }
while(pos[0]>=mid[0]+nt[tmp[0]])
{ pos[0] -= nt[tmp[0]--]; }
sum += tmp[0];
}
}
else
{
mid[0] = k/2,mid[1] = k/2+1;
for(re int i=k; i<=n; i++)
{
nt[s2[i]]++;
if(s2[i]<=tmp[0])
{ pos[0]++; }
if(s2[i]<=tmp[1])
{ pos[1]++; }
if(i>k)
{
nt[s2[i-k]]--;
if(s2[i-k]<=tmp[0])
{ pos[0]--; }
if(s2[i-k]<=tmp[1])
{ pos[1]--; }
}
while(pos[0]<mid[0])
{ pos[0] += nt[++tmp[0]]; }
while(pos[0]>=mid[0]+nt[tmp[0]])
{ pos[0] -= nt[tmp[0]--]; }
while(pos[1]<mid[1])
{ pos[1] += nt[++tmp[1]]; }
while(pos[1]>=mid[1]+nt[tmp[1]])
{ pos[1] -= nt[tmp[1]--]; }
sum += (double)(tmp[0]+tmp[1])/2.0;
}
}
printf("%0.1lf\n",sum);
return 0;
}
}
signed main()
{ return OMA::main(); }
显然,每次取最大值即是最优策略。
用大根堆维护当前集合中的最大值会T
然后就…
题面没说分差是谁减谁,我默认取绝对值,结果是 \(A-B\)
可恶,然而sb出题人
祭奠一下失去的50pts。
50pts
#include<queue>
#include<cstdio>
#define MAX 100010
#define re register
namespace OMA
{
int a[MAX],p;
int n,k,ans[2],tmp;
std::priority_queue<int>q;
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
inline int abs(int a)
{ return a>=0?a:-a; }
signed main()
{
//freopen("node.in","r",stdin);
//freopen("my.out","w",stdout);
n = read(),k = read();
for(re int i=1; i<=n; i++)
{ a[i] = read(); }
for(re int i=1; i<=k; i++)
{
ans[0] = ans[1] = tmp = 0,p = read();
for(re int j=1; j<=p; j++)
{ q.push(a[j]); }
while(!q.empty())
{
ans[tmp] += q.top();
q.pop();
if(a[p+1]>0)
{ q.push(a[++p]); }
tmp ^= 1;
}
printf("%d\n",ans[0]-ans[1]);
//printf("%d\n",abs(ans[0]-ans[1]));
}
return 0;
}
}
signed main()
{ return OMA::main(); }
考虑其他解法。
我们可以开个桶,统计一下当前集合中每个数出现的次数,再用一个变量维护当前集合中的最大值,每回用最大值去更新答案。
考虑如何维护这个最大值。
我们发现,如果新加入的数不小于当前集合中的最大值,在最优策略下,它会直接被拿走,那么最大值就不会被更新。
如果比当前最大值小,我们直接拿最大值去更新答案,更新前判断维护的最大值的桶里是否还有数,如果没有,直接去枚举来更新最大值,然后更新答案。
可以发现,维护的最大值是在不断减小的,那么枚举时的复杂度就会降低,所以时间复杂度 \(O(nk)\)
记得开long long
Code
#include<cstdio>
#define MAX 200010
#define re register
#define LL long long
namespace OMA
{
int n,k,q,to,tmp;
LL ans[2];
int a[MAX],cnt[MAX];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
inline int max(int a,int b)
{ return a>b?a:b; }
signed main()
{
n = read(),k = read();
for(re int i=1; i<=n; i++)
{ a[i] = read(); }
for(re int i=1; i<=k; i++)
{
q = read()-1;
int times = 0;
ans[0] = ans[1] = tmp = to = 0;
for(re int j=1; j<=q; j++)
{ cnt[a[j]]++,to = max(to,a[j]); }
while(1)
{
if(times==n)
{ break ; }
q++;
if(q<=n&&a[q]>=to)
{ ans[times%2] += a[q],times++; continue ; }
else
{
cnt[a[q]]++;
if(cnt[to]==0)
{
for(re int j=to-1; j; j--)
{ if(cnt[j]){ to = j; break ; } }
}
ans[times%2] += to,cnt[to]--,times++;
}
}
printf("%lld\n",ans[0]-ans[1]);
}
return 0;
}
}
signed main()
{ return OMA::main(); }
还是想骂sb出题人分差不加绝对值
考场乱搜,大样例都过不了,还能搜对俩点?
外加输出0的7pts,t3有15pts搜错了都有8pts
15pts
#include<cstdio>
#define MAX 100010
#define re register
//#define int long long
namespace OMA
{
int n,v,p[MAX];
int come[MAX],ans;
struct graph
{
int next;
int to;
}edge[MAX<<1];
int cnt=1,head[MAX];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
inline void add(int u,int v)
{
edge[++cnt].next = head[u];
edge[cnt].to = v;
head[u] = cnt;
}
inline int max(int a,int b)
{ return a>b?a:b; }
inline void dfs(int u,int fa,int res,int meet,int now)
{
//printf("u=%d fa=%d rest of v=%d tourist haven meeted=%d gezi=%d\n",u,fa,res,meet,now);
if(!res)
{ ans = max(ans,now-meet); /*printf("ans=%d\n",ans);*/ return ; }
for(re int i=head[u]; i; i=edge[i].next)
{
int v = edge[i].to;
if(v!=fa)
{ dfs(v,u,res-1,meet,now+come[v]-p[u]); }
}
}
signed main()
{
//freopen("node.in","r",stdin);
//freopen("my.out","w",stdout);
n = read(),v = read();
for(re int i=1; i<=n; i++)
{ p[i] = read(); }
for(re int i=1,x,y; i<=n-1; i++)
{
x = read(),y = read();
add(x,y),add(y,x);
}
if(!v)
{ printf("0\n"); return 0; }
for(re int i=1; i<=n; i++)
{
for(re int j=head[i]; j; j=edge[j].next)
{ come[i] += p[edge[j].to]; }
//printf("come[%d]=%d\n",i,come[i]);
}
//dfs(1,0,v-1,p[1],come[1]+p[1]);
for(re int i=1; i<=n; i++)
{ dfs(i,0,v-1,p[i],come[i]+p[i]); }
printf("%d\n",ans);
return 0;
}
}
signed main()
{ return OMA::main(); }
正解:
树形dp,还没改出来 正在改,快了快了,所以先咕了QAQ
话说后两题改了个题面就拿过来了,真的好吗
updated on 7.25
看了战神题解才改出来,方程好麻烦啊啊啊
我们设 \(dp1_{u,i,0/1}\) 表示从 \(u\) 走到 \(u\) 的子树,选了 \(i\) 个,\(u\) 被没被选,0没选,1选,设\(dp2_{u,i,0/1}\) 表示从 \(u\) 的子树走到 \(u\) ,选了 \(i\) 个,\(u\) 被没被选,0没选,1选。
则有:
\[dp1_{u,i,0}=\max(dp1_{son,i,0},dp1_{son,i,1})
\]
\[dp1_{u,i,1}=\max(dp1_{son,j-1,0},dp1_{son,j-1,1})
\]
\[dp2_{u,i,0}=\max(dp2_{son,j,0},dp2_{son,j,1})
\]
\[dp2_{u,i,1}=\max(dp2_{son,j-1,0},dp2_{son,j-1,1}+sum_{u}+p_{fa}-p_{son})
\]
其中 \(sum_{u}\) 表示 \(u\) 节点的儿子的权值和。
设答案为 \(ans\),则有:
\[ans=\max(\max(dp1_{son,i,0},dp1_{son,i,1})+\max(dp2_{u,v-i,0},dp2_{u,v-i,1}))
\]
\[ans=\max(\max(dp2_{son,i,0},dp2_{son,i,1})+\max(dp1_{u,v-i,0},dp1_{u,v-i,1}+p_{fa}-p_{son}))
\]
Code
#include<cstdio>
#include<climits>
#define V 110
#define N 100010
#define re register
#define LL long long
#define MIN INT_MIN
namespace OMA
{
int n,v;
struct graph
{
int next;
int to;
}edge[N<<1];
int cnt=1,head[N];
int p[N];
LL ans,sum[N];
LL dp1[N][V][2],dp2[N][V][2];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
inline void add(int u,int v)
{
edge[++cnt].next = head[u];
edge[cnt].to = v;
head[u] = cnt;
}
inline LL max(LL a,LL b)
{ return a>b?a:b; }
inline void dfs(int u,int fa)
{
for(re int i=head[u]; i; i=edge[i].next)
{
int to = edge[i].to;
if(to!=fa)
{ dfs(to,u); sum[u] += p[to]; }
}
dp1[u][0][1] = dp2[u][0][1] = MIN;
dp2[u][1][1] = max(dp2[u][1][1],sum[u]+p[fa]);
for(re int i=head[u]; i; i=edge[i].next)
{
int to = edge[i].to;
for(re int j=v; ~j; j--)
{
ans = max(ans,max(dp1[to][j][0],dp1[to][j][1])+max(dp2[u][v-j][0],dp2[u][v-j][1]));
ans = max(ans,max(dp2[to][j][0],dp2[to][j][1])+max(dp1[u][v-j][0],dp1[u][v-j][1]+p[fa]-p[to]));
}
for(re int j=1; j<=v; j++)
{
dp1[u][j][0] = max(dp1[u][j][0],max(dp1[to][j][0],dp1[to][j][1]));
dp1[u][j][1] = max(dp1[u][j][1],max(dp1[to][j-1][0],dp1[to][j-1][1])+sum[u]);
dp2[u][j][0] = max(dp2[u][j][0],max(dp2[to][j][0],dp2[to][j][1]));
dp2[u][j][1] = max(dp2[u][j][1],max(dp2[to][j-1][0],dp2[to][j-1][1])+sum[u]+p[fa]-p[to]);
}
}
}
signed main()
{
n = read(),v = read();
for(re int i=1; i<=n; i++)
{ p[i] = read(); }
for(re int i=1,u,v; i<=n-1; i++)
{
u = read(),v = read();
add(u,v),add(v,u);
}
dfs(1,0);
printf("%lld\n",ans);
return 0;
}
}
signed main()
{ return OMA::main(); }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章