6-26
T1粉丝问我ctrl键在哪里
励志阿伟现在正处在一个冰火迷宫中，迷宫由 n 个格子组成，每个格子要么是冰之格，要么是火之格，励志阿伟刚开始可以选择从迷宫中任意一个开始走，走到第 i 个位置时会得到值为 ai 的积分。如果励志阿伟当前在冰之格，那么他可以选择一个编号大于当前格子的冰之格，跳到那里。如果励志阿伟当前在火之格，那么他可以选择一个编号大于当前格子的火之格，跳到那里。如果励志阿伟目前没有格子可以走，那么结束。励志阿伟想最大化他的得分，于是他学会了一个超能力，他能在比赛开始的时候改变最多 m 个格子的状态，即将一个格子从冰之格变成火之格或从火之格变成冰之格，改变第 i 个格子的状态会让励志阿伟的得分减少 pi 。 你能告诉励志阿伟他最多能得几分吗？（特别地，励志阿伟可以选择一个格子都不走积分为 0。
在考试时看错了题面，痛失80分，正解应为贪心，从第一个收益为正的冰/火各自开始，计算每个格子的收益并排序可得。
std:
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define int ll
#define N 200005
using namespace std;
map<int,int>dp[N],s[N];
int ts[N],tdp[N];
int son[N];
int dis[N];
int siz[N];
int n,m;
poly G[N],P[N];
int sum[N];
int r[N],val[N];
void dfs(int k,int fa)
{
siz[k]+=1;
for (auto u:G[k])
{
if (u==fa) continue;
dfs(u,k);
if (siz[u]>siz[son[k]]) son[k]=u;
siz[k]+=siz[u];
}
siz[k]+=P[k].size();
}
void dfs1(int k,int fa)
{
if (son[k])
{
dfs1(son[k],k);
swap(s[k],s[son[k]]);
swap(dp[k],dp[son[k]]);
ts[k]=ts[son[k]];
tdp[k]=tdp[son[k]];
ts[k]++;
s[k][(0)-ts[k]]=s[k][(1)-ts[k]];
tdp[k]--;
dp[k].erase((-1)-tdp[k]);
}
int zson=0;
int mx=0;
for (auto u:G[k])
{
if (u==fa||u==son[k]) continue;
dfs1(u,k);
}
for (auto u:G[k])
{
if (u==fa||u==son[k]) continue;
for (auto [j,v]:s[u])
{
if (j+ts[u]<dp[k].size())
{
dp[k][(j+ts[u])-tdp[k]]+=v;
}
}
}
for (auto u:G[k])
{
if (u==fa||u==son[k]) continue;
for (auto [j,v]:s[u])
{
s[k][(j+1+ts[u])-ts[k]]+=v;
}
}
for (auto u:G[k])
{
if (u==fa||u==son[k]) continue;
for (auto [ii,v]:dp[u])
{
int i=ii+tdp[u];
int coef=0;
if (s[u].count((i-1)-ts[u])) coef+=-s[u][(i-1)-ts[u]];
if (s[k].count((i)-ts[k])) coef+=s[k][(i)-ts[k]];
dp[k][(i-1)-tdp[k]]=max(dp[k][(i-1)-tdp[k]],v+coef);
}
}
for (auto i:P[k])
{
int ds=r[i];
int coef=0;
if (s[k].count((ds+1)-ts[k])) coef=s[k][(ds+1)-ts[k]];
dp[k][ds-tdp[k]]=max(dp[k][ds-tdp[k]],coef+val[i]);
}
for (auto u:G[k])
if (u!=fa&&u!=son[k]&&s[u].count(-ts[u]))
s[k][0-ts[k]]+=s[u][0-ts[u]];
if (dp[k].count(-tdp[k]))
s[k][0-ts[k]]=max(s[k][0-ts[k]],dp[k][0-tdp[k]]);
}
void BellaKira()
{
cin>>n>>m;
for (int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i=1;i<=m;i++)
{
int pos;
cin>>pos>>r[i]>>val[i];
P[pos].push_back(i);
}
dfs(1,0);
dfs1(1,0);
int ans=s[1][-ts[1]];
for (auto u:dp[1]) ans=max(ans,u.se);
cout<<ans<<'\n';
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
T2原神，启动
你需要构造一个 n × n 的矩阵，每个点填黑或白，使得相邻格子不同色的对数恰好为 m考试时只打了25分的部分分，被dp所限制了，正解是构造，可将整个表格不同色对数个数最大化，再解方程。
std：
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
// #define int ll
#define N 1005
using namespace std;
int n,m,a[N][N],b[N][N],col[N][N];
void BellaKira()
{
cin>>n>>m;
if (n==1)
{
if (m==0)
{
cout<<"Possible\n0\n";
return;
}
cout<<"Impossible\n";
return;
}
if (n==2)
{
if (m==4)
{
cout<<"Possible\n01\n10\n";
return;
}
if (m==2)
{
cout<<"Possible\n01\n01\n";
return;
}
if (m==0)
{
cout<<"Possible\n00\n00\n";
return;
}
cout<<"Impossible\n";
return;
}
memset(a,-1,sizeof(a));
for (a[1][1]=0;a[1][1]<=1;a[1][1]++)
for (a[n][1]=0;a[n][1]<=1;a[n][1]++)
for (a[n][n]=0;a[n][n]<=1;a[n][n]++)
for (a[1][n]=0;a[1][n]<=1;a[1][n]++)
{
int x=0,y=0,z=0,p=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
b[i][j]=a[i][j];
if ((i+j)%2==0&&b[i][j]==-1) b[i][j]=0;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if ((i+j)%2==1&&b[i][j]==-1)
{
int tt=0,pp=0;
for (int dx=-1;dx<=1;dx++)
for (int dy=-1;dy<=1;dy++)
if (dx+dy&&(dx==0||dy==0)&&i+dx>=1&&i+dx<=n&&j+dy>=1&&j+dy<=n)
{
tt+=1;
pp+=b[i+dx][j+dy];
}
if (tt==4) x++,col[i][j]=1;
else if (pp==0) y++,col[i][j]=2;
else p++,col[i][j]=3+pp;
}
for (int i=1;i<=n;i++)
for (int j=1;j<n;j++)
if (b[i][j]!=-1&&b[i][j+1]!=-1)
z+=b[i][j]!=b[i][j+1];
for (int i=1;i<n;i++)
for (int j=1;j<=n;j++)
if (b[i][j]!=-1&&b[i+1][j]!=-1)
z+=b[i][j]!=b[i+1][j];
int X=-1,Y=-1,Z=-1;
// assert(p<=4);
for (int j=0;j<=y;j++)
for (int k=0;k<=p;k++)
if ((m-(z+j*3+k*1+(p-k)*2))%4==0
&&(m-(z+j*3+k*1+(p-k)*2))/4<=x
&&(m-(z+j*3+k*1+(p-k)*2))/4>=0)
{
X=(m-(z+j*3+k*1+(p-k)*2))/4,Y=j,Z=k;
}
if (X!=-1)
{
cout<<"Possible\n";
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (b[i][j]==-1)
{
if (col[i][j]==1)
{
b[i][j]=(X>0);
X--;
}
else
if (col[i][j]==2)
{
b[i][j]=(Y>0);
Y--;
} else
if (col[i][j]==4)
{
if (Z)
{
Z--;
b[i][j]=0;
} else b[i][j]=1;
} else
if (col[i][j]==5)
{
if (Z)
{
Z--;
b[i][j]=1;
} else b[i][j]=0;
}
}
cout<<b[i][j];
}
cout<<'\n';
}
return;
}
}
cout<<"Impossible\n";
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
cin>>T;
while (T--)
{
BellaKira();
}
}
T3雨田天宇
定义一个长度为 n 的序列 a 的权值为所有重排 a 之后的新序列 a ′ 的 ∑ni=1 |a ′ i −a ′ n−i+1| 的最大值。求所有长度为 n 的每个数取值在 [1, m] 的序列的权值的和，对 998244353 取模。
考虑拆开看贡献，首先显然排序过后的 a 是最优解之一。考虑横着算贡献，也就是枚举 i，枚举 j，使得 j 个数小于 i，n − j 个数大于等于i，然后算一下这一行对答案的贡献就行了。
std：
// Problem: Sum Over All Arrays
// Contest: CodeChef - START86
// URL: https://www.codechef.com/problems/SUMOVERALL
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define int ll
#define N 5005
using namespace std;
int n,m,C[N][N],pw[N][N];
void BellaKira()
{
int ans=0;
cin>>n>>m;
int t=0;
for (int i=0;i<=n;i++)
for (int j=1;j<=m;j++)
{
int coef=0;
if (i<=(n+1)/2)
coef=min(i,n/2);
else coef=min(i,n/2)-(i-(n+1)/2);
ans=(ans+coef*C[n][i]%mod*pw[m-j+1][i]%mod*pw[j-1][n-i]%mod)%mod;
}
cout<<ans*2%mod<<'\n';
}
signed main()
{
C[0][0]=1;
for (int i=1;i<N;i++)
{
C[i][0]=1;
for (int j=1;j<=i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
for (int i=0;i<N;i++)
{
pw[i][0]=1;
for (int j=1;j<N;j++)
pw[i][j]=pw[i][j-1]*i%mod;
}
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
T4安排 r
定义一个长度为 n 的序列 a 后缀和序列为另一个长度为 n 的序列 b 使得对于所有 i都有 定义将一个序列一般化指把序列中的每个数都跟 bi = ∑n j=i aj。 1018 取 min，然后跟 −1018 取 max。现在给你一个长度为 n 的序列，你可以执行以下三种操作：1：将序列中所有数取反。2：选取一个区间 [l, r](1 ≤ l ≤ r ≤ n)，将 [l, r] 这个区间变为这个区间的前缀和序列，然后将 a 一般化。3：选取一个区间 [l, r](1 ≤ l ≤ r ≤ n)，将 [l, r] 这个区间变为这个区间的后缀和序列，然后将 a 一般化。你需要花费最少的次数使得序列中每个数都是非负整数。
先把只需要操作零次和操作一次判掉，操作一次只需要操作整个序列即可，可以证明一定不劣。有如下结论：操作次数不超过 3。这是因为我们发现对一个区间 [l, r] 做前缀和本质上是从 al , al+1, ..., ar 变成 sl −sl−1, sl+1−sl−1, ..., sr−sl−1。做后缀和本质上是从 al , al+1, ..., ar 变成 sr−sl−1, sr−sl , ..., sr−sr−1。所以如果我们找到 s 最小的位置 x 与 s 最大的位置 y，若 x ≤ y，则能在两次之内完成，否则我们把序列取反，两个位置就会反一反，也能在三次之内完成。再考虑分治，动态维护凸壳
std：
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf ((int)1e18)
#define mod 998244353
#define int ll
#define N 500005
using namespace std;
int n,m,a[N],s[N];
int ss[N];
int Tmp[N];
int tmpa[N];
int pre[N],suf[N];
vector<pair<int,pa>>ans;
int chk()
{
{
bool bl=1;
for (int i=1;i<=n;i++)
bl&=(a[i]>=0);
if (bl)
{
return 1;
}
{
bl=1;
int x=0;
for (int i=1;i<=n;i++)
{
x=min(inf,a[i]+x),x=max(-inf,x);
bl&=(x>=0);
}
if (bl)
{
ans.push_back(mp(2,mp(1,n)));
return 1;
}
}
{
bl=1;
int x=0;
for (int i=n;i>=1;i--)
{
x=min(inf,a[i]+x),x=max(-inf,x);
bl&=(x>=0);
}
if (bl)
{
ans.push_back(mp(3,mp(1,n)));
return 1;
}
}
{
bl=1;
int x=0;
for (int i=1;i<=n;i++)
bl&=(a[i]<=0);
if (bl)
{
ans.push_back(mp(1,mp(0,0)));
return 1;
}
}
}
return 0;
}
void outp()
{
cout<<ans.size()<<endl;
for (auto [u,v]:ans)
{
cout<<u;
if (v.fi) cout<<" "<<v.fi<<" "<<v.se;
if (u==1)
{
for (int i=1;i<=n;i++) Tmp[i]=-Tmp[i];
}else
if (u==2)
{
for (int i=v.fi+1;i<=v.se;i++)
Tmp[i]+=Tmp[i-1],Tmp[i]=max(Tmp[i],-inf),Tmp[i]=min(Tmp[i],inf);
} else
{
for (int i=v.se-1;i>=v.fi;i--)
Tmp[i]+=Tmp[i+1],Tmp[i]=max(Tmp[i],-inf),Tmp[i]=min(Tmp[i],inf);
}
cout<<endl;
}
// for (int i=1;i<=n;i++)
// cout<<Tmp[i]<<" ";
// cout<<endl;
for (int i=1;i<=n;i++)
assert(Tmp[i]>=0);
exit(0);
}
void chklf(){
for (int i=1;i<=n;i++)
tmpa[i]=a[i];
int now=1;
__int128 all=0;
while (ans.size()<=2){
while (now<=n&&all+tmpa[now]>=0){
all+=tmpa[now];
now++;
}
ans.push_back(mp(2,mp(1,now-1)));
for (int i=1;i<now;i++)
tmpa[i]=(tmpa[i-1]+tmpa[i]),tmpa[i]=min(tmpa[i],inf),tmpa[i]=max(tmpa[i],-inf);
all=0;
for (int i=1;i<now;i++)
all+=tmpa[i];
bool bl=1;
for (int i=1;i<=n;i++) bl&=(tmpa[i]>=0);
if (bl) break;
}
if (ans.size()==2) outp();
ans.clear();
}
void chkrt(){
for (int i=1;i<=n;i++)
tmpa[i]=a[i];
int now=n;
__int128 all=0;
while (ans.size()<=2){
while (now>=1&&all+tmpa[now]>=0)
{
all+=tmpa[now];
now--;
}
ans.push_back(mp(3,mp(now+1,n)));
for (int i=n;i>now;i--)
tmpa[i]=(tmpa[i+1]+tmpa[i]),tmpa[i]=min(tmpa[i],inf),tmpa[i]=max(tmpa[i],-inf);
all=0;
for (int i=n;i>now;i--)
all+=tmpa[i];
bool bl=1;
for (int i=1;i<=n;i++) bl&=(tmpa[i]>=0);
if (bl) break;
}
if (ans.size()==2) outp();
ans.clear();
}
pa sta[N];
int tp;
int p[N];
int cnt;
int alltag;
pa Rt[N];
int rev;
int Mn[N];
int L=-1,R=-1;
inline pa sub(pa x,pa y)
{
return mp(x.fi-y.fi,x.se-y.se);
}
inline pa addy(pa x,int del)
{
return mp(x.fi,x.se+del);
}
inline int mul(pa x,pa y)
{
return x.fi*y.se-x.se*y.fi;
}
namespace lct
{
struct node
{
int k,b;
node(pa x)
{
k=x.fi,b=x.se;
}
node(int x,int y)
{
k=x,b=y;
}
node()
{
k=b=0;
}
inline int val(int x)
{
return k*x+b;
}
}tr[N<<2];
int lson[N<<2];
int rson[N<<2];
int tot=0;
int rt=0;
void update(int &k,int l,int r,node x)
{
if (!k)
{
k=++tot;
assert(tot<(N<<2));
tr[k]=x;
lson[k]=0,rson[k]=0;
return;
}
int mid=l+(r-l)/2;
if (tr[k].val(mid)>x.val(mid)) swap(tr[k],x);
if (l==r) return;
if (tr[k].k<x.k)
{
update(lson[k],l,mid,x);
} else update(rson[k],mid+1,r,x);
}
int query(int k,int l,int r,int L)
{
if (!k) return inf;
int mid=l+(r-l)/2;
if (L<=mid) return min(tr[k].val(L),query(lson[k],l,mid,L));
return min(tr[k].val(L),query(rson[k],mid+1,r,L));
}
void clr()
{
rt=0;
tot=0;
}
}
void work(int l,int r)
{
if (l==r) return;
int mid=l+(r-l)/2;
// cout<<"work "<<l<<" "<<r<<endl;
work(l,mid);
work(mid+1,r);
tp=0;
cnt=0;
alltag=0;
for (int i=mid+1;i<=r;i++)
{
int mx=-inf;
alltag+=a[i];
alltag-=s[i];
pa now=mp(r-i+1,-s[n]-alltag);
while (tp>1&&mul(sub(addy(sta[tp],alltag),addy(now,alltag)),
sub(addy(sta[tp-1],alltag),addy(now,alltag)))>=0)
{
tp--;
}
sta[++tp]=now;
if (suf[i+1])
{
int L=2,R=tp;
int pos=tp;
pa zero=mp(r-i,0);
while (L<=R)
{
int mid=L+(R-L)/2;
if (mul(sub(addy(sta[mid],alltag),zero),sub(addy(sta[mid-1],alltag),zero))>=0)
{
pos=mid-1;
R=mid-1;
} else
{
L=mid+1;
}
}
int lim=(sta[pos].se+alltag-0)/(sta[pos].fi-r+i);
if (sta[pos].se+alltag>0)
lim=(sta[pos].se+alltag+(sta[pos].fi-r+i)-1)/(sta[pos].fi-r+i);
Rt[++cnt]=mp(lim,i);
}
}
lct::clr();
for (int i=mid;i>=l;i--)
{
int sm=(-s[i-1])*(mid-i+1)+ss[mid]-ss[i-1];
Mn[i]=min(sm+s[i-1]+pre[i-1],inf);
lct::update(lct::rt,-n,n,lct::node(mid-i+1,ss[mid]-ss[i-1]));
Mn[i]=min(Mn[i],lct::query(lct::rt,-n,n,-s[i-1]));
p[i]=i;
}
sort(p+l,p+mid+1,[&](int x,int y)
{
return -s[x-1]<-s[y-1];
});
lct::clr();
sort(Rt+1,Rt+cnt+1);
int pos=1;
for (int ii=l;ii<=mid;ii++)
{
int i=p[ii];
// cout<<"!!"<<i<<" "<<-s[i-1]<<endl;
while (pos<=cnt&&-s[i-1]>=Rt[pos].fi)
{
// cout<<"ins "<<Rt[pos].se<<endl;
lct::update(lct::rt,-n,n,
lct::node(-(Rt[pos].se-mid),-(ss[Rt[pos].se]-ss[mid]+s[n]-s[Rt[pos].se])));
pos++;
}
int mx=-lct::query(lct::rt,-n,n,-s[i-1]);
if (mx+Mn[i]>=0)
{
for (int j=1;j<pos;j++)
{
lct::node now=
lct::node(-(Rt[j].se-mid),-(ss[Rt[j].se]-ss[mid]+s[n]-s[Rt[j].se]));
if (now.val(-s[i-1])==-mx)
{
if (rev==0)
ans.push_back(mp(2^rev,mp(i,Rt[j].se)));
else
ans.push_back(mp(2^rev,mp(n-Rt[j].se+1,n-i+1)));
ans.push_back(mp(3^rev,mp(1,n)));
outp();
}
}
}
}
// cout<<"work "<<l<<" "<<r<<endl;
}
void BellaKira()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i],s[i]=s[i-1]+a[i],Tmp[i]=a[i];
if (chk())
{
outp();
}
ans.push_back(mp(1,mp(0,0)));
for (int i=1;i<=n;i++)
a[i]=-a[i];
if (chk())
{
outp();
}
for (int i=1;i<=n;i++)
a[i]=-a[i];
ans.clear();
int mn=0,mx=0;
for (int i=1;i<=n;i++)
{
if (s[i]>=s[mx]) mx=i;
if (s[i]<s[mn]) mn=i;
}
if (mn>=mx)
{
pre[0]=inf,suf[n+1]=1;
for (int i=1;i<=n;i++)
pre[i]=min(pre[i-1],-s[i-1]);
for (int i=n;i>=1;i--)
suf[i]=suf[i+1]&(s[n]-s[i-1]>=0);
for (int i=1;i<=n;i++)
ss[i]=ss[i-1]+s[i];
chklf();
chkrt();
work(1,n);
rev=1;
reverse(a+1,a+n+1);
for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
pre[0]=inf,suf[n+1]=1;
for (int i=1;i<=n;i++)
pre[i]=min(pre[i-1],-s[i-1]);
for (int i=n;i>=1;i--)
suf[i]=suf[i+1]&(s[n]-s[i-1]>=0);
for (int i=1;i<=n;i++)
ss[i]=ss[i-1]+s[i];
work(1,n);
reverse(a+1,a+n+1);
ans.push_back(mp(1,mp(0,0)));
for (int i=1;i<=n;i++)
a[i]=-a[i],s[i]=s[i-1]+a[i];
mn=0,mx=0;
for (int i=1;i<=n;i++)
{
if (s[i]>=s[mx]) mx=i;
if (s[i]<s[mn]) mn=i;
}
ans.push_back(mp(2,mp(mn+1,n)));
ans.push_back(mp(3,mp(1,mx)));
outp();
} else
{
ans.push_back(mp(2,mp(mn+1,n)));
ans.push_back(mp(3,mp(1,mx)));
outp();
}
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
标签：int,6.26,--,pa,mp,2023,fi,集训,define From： https://www.cnblogs.com/determination/p/17521263.html