对应过来做一遍逆序对就好了。
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e6+10;
const int mod=1e9+7;
const int N=30;
int n,a[maxn],now[N];
long long ans;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
string s1,s2;
int pre[N],fir[N],nxt[maxn];
int c[maxn];
int main(){
n=read();
cin>>s2>>s1;
for(int i=1;i<=n;i++){
int t=s1[i-1]-'A'+1;
if(!fir[t])fir[t]=pre[t]=i;
else nxt[pre[t]]=i,pre[t]=i;
}
for(int i=1;i<=n;i++){
int t=s2[i-1]-'A'+1;
if(!now[t])now[t]=fir[t];
a[i]=now[t];
now[t]=nxt[now[t]];
}
for(int i=n;i>=1;i--){
for(int j=a[i];j;j-=(j&(-j)))ans+=c[j];
for(int j=a[i];j<=n;j+=(j&(-j)))c[j]++;
}
printf("%lld
",ans);
return 0;
}
没看到只能减不能加，没考虑(0)就半天想不会……
二分答案(mid)，前后扫求出不考虑(a_k=0)的答案(tot)。
考虑将一个点变为(0)会产生什么影响：过此点作斜率为(pm mid)的两条直线，直线以上的点都受影响。
因为它的波动幅度不超过(mid)，故影响范围是一个区间。
维护区间左右端点即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int mod=1e9+7;
int n,m,a[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int b[maxn],sum[maxn],cost[maxn];
inline int check(int val){
int tot=0;
for(int i=1;i<=n;i++)b[i]=a[i];
for(int i=2;i<=n;i++)
if(b[i]>b[i-1]+val){
tot+=b[i]-b[i-1]-val;
b[i]=b[i-1]+val;
}
for(int i=n-1;i>=1;i--)
if(b[i]>b[i+1]+val){
tot+=b[i]-b[i+1]-val;
b[i]=b[i+1]+val;
}
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+b[i];
for(int i=n,l=n;i;i--){
while(l&&b[l]>(i-l)*val)l--;
cost[i]=sum[i]-sum[l]-val*(i-l)*(i-l-1)/2;
}
for(int i=1,r=1;i<=n;i++){
while(r<=n&&b[r]>(r-i)*val)r++;
if(tot+cost[i]+sum[r-1]-sum[i]-val*(r-i)*(r-i-1)/2<=m)
return i;
}
return 0;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
int l=0,r=1<<30,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld %lld
",check(ans),ans);
return 0;
}
不要以为数据范围大就不能用( ext{floyd})，只要你想不到别的方法，那它就可以。
算是几乎把差分约束有学了一遍吧（也不知道以前我学了个啥）。
连边如下：(add(a_i,b_i,1),add(b_i,a_i,-1),add(d_i,c_i,0))
跑一边( ext{tarjan})缩点，考虑每个强连通分量。
一个( ext{scc})内，显然由于大小关系卡得很死，那么它的取值就是最短路，它的贡献则是直径加一。
出现负环即为不合法，由于我们对每个( ext{scc})内( ext{floyd})过了，只需判断(dis[i][i]<0)即可。
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=5e5+10;
const int mod=1e9+7;
const int N=666;
int n,m1,m2,ans;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int beg[N],nex[maxn],to[maxn],e;
inline void add(int x,int y){
e++;nex[e]=beg[x];
beg[x]=e;to[e]=y;
}
int dis[N][N],col[N],scc;
int dfn[N],low[N],ti,ins[N];
stack<int>st;
inline void tarjan(int x){
dfn[x]=low[x]=++ti;
st.push(x);ins[x]=1;
for(int i=beg[x];i;i=nex[i]){
int t=to[i];
if(!dfn[t]){
tarjan(t);
low[x]=min(low[x],low[t]);
}else if(ins[t])
low[x]=min(low[x],dfn[t]);
}
if(dfn[x]==low[x]){
col[x]=++scc;
ins[x]=0;
while(st.top()!=x){
int t=st.top();
st.pop();
col[t]=scc;
ins[t]=0;
}
st.pop();
}
}
int main(){
n=read(),m1=read(),m2=read();
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++)
dis[i][i]=0;
int x,y;
for(int i=1;i<=m1;i++){
x=read(),y=read();
add(x,y),add(y,x);
dis[x][y]=min(dis[x][y],1);
dis[y][x]=-1;
}
for(int i=1;i<=m2;i++){
x=read(),y=read();
add(y,x);
dis[y][x]=min(dis[y][x],0);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int t=1;t<=scc;t++){
for(int i=1;i<=n;i++)
if(col[i]==t)
for(int j=1;j<=n;j++)
if(col[j]==t)
for(int k=1;k<=n;k++)
if(col[k]==t)
dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
int len=-inf;
for(int i=1;i<=n;i++)
if(col[i]==t)
for(int j=1;j<=n;j++)
if(col[j]==t)len=max(len,dis[i][j]);
ans+=len+1;
}
for(int i=1;i<=n;i++)
if(dis[i][i]<0)return puts("NIE"),0;
printf("%d
",ans);
return 0;
}
容易得出(d(a,b)=f(a)+f(b)-2f(gcd(a,b)))，其中(f(i))为(i)的质因数个数。
套路：考虑枚举(gcd)，更新答案，时间复杂度(Theta(nln n))
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e6+10;
const int mod=1e9+7;
int n,a[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int pri[maxn],tot,flag[maxn];
int f[maxn];
int nxt[maxn],hd[maxn];
int q[maxn];
int ans[maxn],pos[maxn];
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=2;i<maxn;i++){
if(!flag[i])pri[++tot]=i,f[i]=1;
for(int j=1;j<=tot&&i*pri[j]<maxn;j++){
flag[i*pri[j]]=1;f[i*pri[j]]=f[i]+1;
if(i%pri[j]==0)break;
}
}
/*
for(int i=1;i<=tot;i++)
for(int j=pri[i];j<maxn;j+=pri[i])
f[j]++;
*/
for(int i=1;i<=n;i++)
nxt[i]=hd[a[i]],hd[a[i]]=i;
for(int i=1;i<=n;i++)
ans[i]=pos[i]=inf;
for(int i=1;i<maxn;i++){
int top=0;
for(int j=i;j<maxn;j+=i)
for(int k=hd[j];k;k=nxt[k])
q[++top]=k;
if(top<=1)continue;
int p=q[1];
for(int j=2;j<=top;j++)
if(f[a[p]]>f[a[q[j]]]||(f[a[p]]==f[a[q[j]]]&&p>q[j]))p=q[j];
for(int j=1;j<=top;j++){
if(q[j]==p)continue;
int val=f[a[q[j]]]+f[a[p]]-2*f[i];
if(val<ans[q[j]]||(val==ans[q[j]]&&pos[q[j]]>p))
ans[q[j]]=val,pos[q[j]]=p;
if(val<ans[p]||(val==ans[p]&&pos[p]>q[j]))
ans[p]=val,pos[p]=q[j];
}
}
for(int i=1;i<=n;i++)
printf("%d
",pos[i]);
return 0;
}
若两点在同一内向树上，则求(lca)，否则先走到环上然后解决。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m,s1[maxn],t1[maxn],tot;
int fa[maxn],rd[maxn];
inline int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int beg[maxn],nex[maxn],to[maxn],e;
inline void add(int x,int y){
e++;nex[e]=beg[x];
beg[x]=e;to[e]=y;
}
int f[maxn][20],dep[maxn],rt[maxn];
int col[maxn],sz[maxn],id[maxn];
inline void dfs(int x,int anc,int root){
f[x][0]=anc;
for(int i=1;i<=19;i++)
f[x][i]=f[f[x][i-1]][i-1];
dep[x]=dep[anc]+1;
rt[x]=root;
for(int i=beg[x];i;i=nex[i])
if(to[i]!=anc&&col[to[i]]!=col[root])
dfs(to[i],x,root);
}
inline int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=19;i>=0;i--)
if(dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
fa[i]=i;
int x,y;
for(int i=1;i<=n;i++){
x=i,y=read();
if(find(x)!=find(y)){
add(y,x);
f[x][0]=y;
rd[x]++;
fa[find(x)]=find(y);
}else tot++,s1[tot]=y,t1[tot]=x;
}
for(int i=1;i<=tot;i++){
x=s1[i],y=t1[i];
int cnt=0;
while(x!=y){
col[x]=i;sz[i]++;
id[x]=++cnt;x=f[x][0];
}
col[y]=i;sz[i]++;
id[y]=sz[i];
}
dep[0]=-1;
for(int i=1;i<=n;i++)
if(col[i])dfs(i,0,i);
//for(int i=1;i<=n;i++)
// printf("dep[%d]=%d rt[%d]=%d
",i,dep[i],i,rt[i]);
for(int i=1;i<=m;i++){
x=read(),y=read();
if(find(x)!=find(y)){
puts("-1 -1");
continue;
}
if(rt[x]==rt[y]){
int anc=lca(x,y);
printf("%d %d
",dep[x]-dep[anc],dep[y]-dep[anc]);
continue;
}
int a=dep[x],b=dep[y],c=col[rt[x]];
int s=(id[rt[y]]-id[rt[x]]+sz[c])%sz[c],t=sz[c]-s;
//printf("s=%d t=%d
",s,t);
int p=max(a+s,b),q=max(a,b+t);
int p1=min(a+s,b),q1=min(a,b+t);
if(p<q||(p==q&&p1<=q1))printf("%d %d
",a+s,b);
else printf("%d %d
",a,b+t);
}
return 0;
}
不知道为什么感觉波兰人好喜欢链表啊。
这题就维护每个值取到什么地方了，复杂度(Theta(n ln n))，要开( ext{long long})。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int N=1e6+1;
const int mod=1e9+7;
int n,m,a[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int hd[maxn],vis[maxn],cnt;
int ans[maxn],tot;
signed main(){
m=read();
int x,y;
for(int i=1;i<=m;i++)
x=read(),a[x]=1;
for(int i=1;i<N;i++)hd[i]=i;
n=read();
for(int i=1;i<=n;i++){
x=read(),y=0;
while(hd[x]<N&&y<x){
if(!vis[hd[x]]){
vis[hd[x]]=1;y++;
if(a[hd[x]])ans[++tot]=cnt+y;
}hd[x]+=x;
}cnt+=x;
}
sort(ans+1,ans+1+tot);
printf("%lld
",tot);
for(int i=1;i<=tot;i++)
printf("%lld
",ans[i]);
return 0;
}
离线是个好东西。可惜我没想到。
考虑离线，从小到大加入(a_i)，维护(f_i)，记录凑到(i)的方案的最小值的最大值。
状态转移方程有(f_i=max{f_i,min{f_{i-c},b}})
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e6+10;
const int mod=1e9+7;
int n,m,f[maxn],ans[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
struct node{
int c,a,b;
bool operator<(const node &x){
return a<x.a;
}
}p[maxn];
struct query{
int m,k,s,id;
bool operator<(const query &x){
return m<x.m;
}
}q[maxn];
inline void insert(int x){
for(int i=100000;i>=p[x].c;i--)
if(~f[i-p[x].c])f[i]=max(f[i],min(f[i-p[x].c],p[x].b));
}
int main(){
n=read();
for(int i=1;i<=n;i++)
p[i]=(node){read(),read(),read()};
m=read();
for(int i=1;i<=m;i++)
q[i]=(query){read(),read(),read(),i};
sort(p+1,p+1+n);sort(q+1,q+1+m);
memset(f,-1,sizeof(f));f[0]=inf;
for(int i=1,j=1;i<=m;i++){
while(j<=n&&p[j].a<=q[i].m)insert(j++);
ans[q[i].id]=(f[q[i].k]>q[i].m+q[i].s);
}
for(int i=1;i<=m;i++)
puts(ans[i]?"TAK":"NIE");
return 0;
}
#2696. 「POI2012」可怕的诗 A Horrible Poem
容易想到(Theta(qsqrt n))的枚举每一个因子的做法，然而正解是(Theta(qlog n))的。
考虑每次除去一个素因子。还有判断函数可以这样写：
inline void pd(int l,int a,int b){
return make(a,b-l)==make(a+l,b);
}
这样写就能判断(l)是不是(S[a...b])的周期。
我写完正解之后极限数据在本地要跑( ext{15s})，交上去评测机只跑了( ext{26ms})，我想打人。
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=5e5+10;
const int base=29;
const int mod=1e8+9;
int n,m,hs[maxn],pw[maxn];string s;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}int flag[maxn],tot;
inline int make(int l,int r){
return (hs[r]-1ll*hs[l-1]*pw[r-l+1]%mod+mod)%mod;
}int pri[maxn],p[maxn];
inline bool pd(int l,int a,int b){return make(a,b-l)==make(a+l,b);}
int main(){
freopen("loj2696.in","r",stdin);
freopen("loj2696.out","w",stdout);
n=read();cin>>s;
for(int i=1;i<=n;++i)
hs[i]=(1ll*hs[i-1]*base%mod+s[i-1]-'a'+1)%mod;
pw[0]=1;
for(int i=1;i<=n;++i)
pw[i]=1ll*pw[i-1]*base%mod;
for(int i=2;i<=n;i++){
if(!flag[i])pri[++tot]=i,p[i]=i;
for(int j=1;j<=tot&&pri[j]*i<=n;j++){
flag[i*pri[j]]=1;
p[i*pri[j]]=pri[j];
if(i%pri[j]==0)break;
}
}
m=read();
int x,y,len,z;
for(int i=1;i<=m;++i){
x=read(),y=read();len=y-x+1;
for(int j=len;j>1;j/=p[j])
if(pd(len/p[j],x,y))len/=p[j];
printf("%d
",len);
}
return 0;
}
#2697. 「POI2012」斐波那契表示法 Fibonacci Representation
玄学贪心求证明！
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+10;
const int mod=1e9+7;
const ll N=4e17+10;
ll n,m,f[maxn];
inline ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
inline int divide(int l,int r,ll val){
int ans=1;
while(l<=r){
int mid=(l+r)>>1;
if(f[mid]<=val)ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main(){
n=read();
f[1]=f[2]=1ll;
int t=3;
for(;(f[t]=f[t-1]+f[t-2])<N;t++);
while(n--){
m=read();
int cnt=0;
while(m){
cnt++;int p=divide(1,t,m);
m=min(m-f[p],f[p+1]-m);
}
printf("%d
",cnt);
}
return 0;
}
#2693. 「POI2012」比赛路线 Tour de Byteotia
两端点都(>k)的边一定不会被删。
所以先加入所有两端点(>k)的边，再拿剩下的边做一次( ext{Kruskal})即可。
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e6+10;
const int mod=1e9+7;
int n,m,k;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int fa[maxn];
inline int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int tot,a[maxn],b[maxn];
int u[maxn],v[maxn];
int main(){
n=read(),m=read(),k=read();
int x,y;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
x=read(),y=read();
if(x>y)swap(x,y);
u[i]=x;v[i]=y;
if(x>k)fa[find(x)]=find(y);
}
for(int i=1;i<=m;i++){
x=u[i],y=v[i];
if(x>k)continue;
if(find(x)==find(y))
++tot,a[tot]=x,b[tot]=y;
else fa[find(x)]=find(y);
}
printf("%d
",tot);
for(int i=1;i<=tot;i++)
printf("%d %d
",a[i],b[i]);
return 0;
}
排序。考虑枚举(a_2+a_3)的位置。
注意到(a_2+a_3)前面的一定是(a_1+a_2)，(a_1+a_3)，(a_1+a_4)……(a_1+a_{pos})，故(a_1)到(a_{pos})的值都可以确定。
已经确定的这些数会产生一些和，把这些和从序列中去掉后，剩下的第一个一定是(a_1+a_{pos+1})，故又可以知道(a_{pos+1})的值。
发现比(a_2+a_3)小的只有可能是(a_1+a_2)到(a_1+a_n)，故此处复杂度(Theta(n))，总理论复杂度(Theta(n^3log n))。
实际跑得飞快。
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
int n,m,a[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
map<int,int>sta,cnt,pre;
int ans[301][301],tot,b[maxn];
int main(){
n=read();m=n*(n-1)/2;
for(int i=1;i<=m;i++)a[i]=read();
for(int i=1;i<=m;i++)sta[a[i]]++;
sort(a+1,a+1+m);
for(int i=3;i<=n;i++){
int sum=(a[1]+a[2]+a[i])/2,flag=1;
b[1]=sum-a[i];b[2]=sum-a[2];b[3]=sum-a[1];
for(int j=4;j<=i;j++)b[j]=a[j-1]-b[1];
cnt.clear(),pre.clear();
for(int j=1;j<=i;j++){
for(int k=1;k<j;k++){
int x=b[j]+b[k];cnt[x]++;
if(cnt[x]>sta[x]){flag=0;break;}
}if(!flag)break;
pre[a[j]]++;
}if(!flag)continue;
for(int j=i+1,pos=i+1;j<=n;j++){
while(pre[a[pos]]<cnt[a[pos]])
pre[a[pos++]]++;
b[j]=a[pos]-b[1];
for(int k=1;k<j;k++){
int x=b[k]+b[j];cnt[x]++;
if(cnt[x]>sta[x]){flag=0;break;}
}if(!flag)continue;
}if(!flag)continue;flag=0;
for(int j=1;j<=n;j++)
flag|=(ans[tot][j]^b[j]);
if(flag)tot++;
for(int j=1;j<=n;j++)
ans[tot][j]=b[j];
}
printf("%d
",tot);
for(int i=1;i<=tot;i++){
for(int j=1;j<=n;j++)
printf("%d ",ans[i][j]);
puts("");
}
return 0;
}
思路挺妙。我们可以求出每个点最大取到的值，考虑转化问题为每个点有上限，能确定几个点。
从小到大排序，直接处理即可。
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e6+10;
const int mod=1e9+7;
int n,m,a[maxn],rt,vis[maxn],mx[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int beg[maxn],nex[maxn],to[maxn],e;
inline void add(int x,int y){
e++;nex[e]=beg[x];
beg[x]=e;to[e]=y;
}
pair<int,int>b[maxn];
inline void dfs(int x,int val){
if(!a[x])b[++m]=make_pair(val,x);
for(int i=beg[x];i;i=nex[i])
dfs(to[i],a[to[i]]?a[to[i]]:mx[val-1]);
}
int main(){
n=read();
for(int i=1,x;i<=n;i++){
x=read();a[i]=read();
if(x==i)rt=i;else add(x,i);
vis[a[i]]=1;
}
for(int i=1;i<=n;i++)
mx[i]=vis[i]?mx[i-1]:i;
dfs(rt,n);
sort(b+1,b+1+m);
for(int i=1,j=1,k=0;i<=n;i++){
if(vis[i]){k++;continue;}
int cnt=0;
while(b[j].first==i)cnt++,j++;
if(cnt==1&&j-1+k==i)
a[b[j-1].second]=i;
}
for(int i=1;i<=n;i++)
printf("%d
",a[i]);
return 0;
}
#2703. 「POI2012」仓库式商店 Warehouse Store
直接反悔贪心即可。不会证明。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+10;
const int mod=1e9+7;
int n,m,ans[maxn];
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int a[maxn],b[maxn];
priority_queue<pair<int,int> >q;
signed main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
for(int i=1,tot=0,t;i<=n;i++){
tot+=a[i];
if(tot>=b[i]){
m++;tot-=b[i];
q.push(make_pair(b[i],i));
continue;
}
if(q.empty())continue;
t=q.top().first;
if(b[i]<t){
q.pop();
q.push(make_pair(b[i],i));
tot+=t-b[i];
}
}
printf("%lld
",m);
for(int i=1;i<=m;i++){
ans[i]=q.top().second;
q.pop();
}
sort(ans+1,ans+1+m);
for(int i=1;i<=m;i++)
printf("%lld ",ans[i]);
return 0;
}
#2704. 「POI2012」前后缀 Prefixuffix
不知道怎么想到的。问题要求将原串划分为( ext{ABCBA})的形式。
考虑( ext{A})的长度为(i)时( ext{B})的最大长度为(f_i)，易证有(f_ileq f_{i+1}+2)，故可以(Theta(n))求出(f)数组。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int mod=1e9+9;
const int base=141;
int n,hs[maxn],pw[maxn],f[maxn],ans;
string s;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
inline int make(int r,int len){
return (hs[r]-hs[r-len]*pw[len]%mod+mod)%mod;
}
inline bool check(int r1,int r2,int len){
return make(r1,len)==make(r2,len);
}
signed main(){
n=read();cin>>s;
for(int i=1;i<=n;i++)
hs[i]=(hs[i-1]*base+s[i-1]-'a'+1)%mod;
pw[0]=1;for(int i=1;i<=n;i++)pw[i]=pw[i-1]*base%mod;
for(int i=n/2;i;i--){
f[i]=min(f[i+1]+2,n/2-i);
while(!check(i+f[i],n-i,f[i]))f[i]--;
}
for(int i=1;i<=n/2;i++)
if(check(i,n,i))ans=max(ans,i+f[i]);
printf("%lld
",ans);
return 0;
}
#2702. 「POI2012」极简主义的安保 Minimalist Security
考虑一个联通块，设一个点的值为(x)，则其他所有点的值都可以用(x)表示。
-
若可以解出(x)，直接计算贡献即可。
-
否则计算(x)的范围，每个点有(0leq xleq p_i)，注意到整体是一个一次函数，则极值分别取端点即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
#define inf 1e9
const int maxn=5e5+10;
const int maxm=6e6+10;
const int mod=1e9+7;
int n,m,p[maxn],v[maxn];
ll amx,amn;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int beg[maxn],nex[maxm],to[maxm],w[maxm],e;
inline void add(int x,int y,int z){
e++;nex[e]=beg[x];
beg[x]=e;to[e]=y;w[e]=z;
}
int vis[maxn],sta[maxn],top,xv;
struct node{int k,b;}a[maxn];
inline void dfs(int x){
sta[++top]=x;vis[x]=1;
for(int i=beg[x];i;i=nex[i]){
int t=to[i];
if(!vis[t]){
a[t].k=-a[x].k;
a[t].b=w[i]-a[x].b;
dfs(t);
}else if(a[x].k+a[t].k==0){
if(a[x].b+a[t].b!=w[i])puts("NIE"),exit(0);
}else xv=(w[i]-a[x].b-a[t].b)/(a[x].k+a[t].k);
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
p[i]=read();
int x,y,z;
for(int i=1;i<=m;i++){
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
xv=inf,top=0;
a[i].k=1;dfs(i);
if(xv!=inf){
for(int j=1,t;j<=top;j++)
t=sta[j],v[t]=a[t].k*xv+a[t].b;
for(int j=1;j<=top;j++)
for(int k=beg[sta[j]];k;k=nex[k])
if(v[sta[j]]+v[to[k]]!=w[k])return puts("NIE"),0;
for(int j=1;j<=top;j++)
if(v[sta[j]]>p[sta[j]])return puts("NIE"),0;
for(int j=1,t;j<=top;j++)
t=sta[j],amn+=p[t]-v[t],amx+=p[t]-v[t];
}else{
int l=-inf,r=inf,ksum=0;ll bsum=0;
for(int j=1;j<=top;j++){
int t=sta[j];
ksum-=a[t].k;bsum+=p[t]-a[t].b;
if(a[t].k==1){
l=max(l,-a[t].b);
r=min(r,p[t]-a[t].b);
}else{
l=max(l,a[t].b-p[t]);
r=min(r,a[t].b);
}
}
if(l>r)return puts("NIE"),0;
if(ksum>=0)amn+=ksum*l+bsum,amx+=ksum*r+bsum;
else amn+=ksum*r+bsum,amx+=ksum*l+bsum;
}
}
printf("%lld %lld
",amn,amx);
return 0;
}
#2701. 「POI2012」找平地面 Leveling Ground
太难了，先搁着，以后做。
参考资料：zsy大佬的poi2012题解