POI2012题解
这次的完整的\(17\)道题哟。
[BZOJ2788][Poi2012]Festival
很显然可以差分约束建图。这里问的是变量最多有多少种不同的取值。
我们知道，在同一个强连通分量中的变量的相对大小是限制死了的，即这个强连通分量中的最大值减去最小值不为\(\inf\)，而这个区间中的所有数一定都可以被取到（因为这里的边权只有\(0,\pm1\)嘛），所以一个强连通分量对答案的贡献是这个强连通分量中的最长路\(+1\)。对于不在同一个强连通分量中的变量，其相对大小不受限制，取值一定可以做到无交集，所以答案就是各强连通分量的答案之和。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 605;
int n,m1,m2,a[N][N],to[N*N],nxt[N*N],head[N],cnt,dfn[N],low[N],tim,vis[N],S[N],bel[N],scc,ans;
void Tarjan(int u){
dfn[u]=low[u]=++tim;vis[S[++S[0]]=u]=1;
for (int e=head[u];e;e=nxt[e])
if (!dfn[to[e]]) Tarjan(to[e]),low[u]=min(low[u],low[to[e]]);
else if (vis[to[e]]) low[u]=min(low[u],dfn[to[e]]);
if (dfn[u]==low[u]){
++scc;int x=0;
do x=S[S[0]--],vis[x]=0,bel[x]=scc;while (x^u);
}
}
int main(){
n=gi();m1=gi();m2=gi();
memset(a,63,sizeof(a));
for (int i=1;i<=n;++i) a[i][i]=0;
while (m1--){
int u=gi(),v=gi();
a[u][v]=min(a[u][v],1);a[v][u]=-1;
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
}
while (m2--){
int u=gi(),v=gi();a[v][u]=min(a[v][u],0);
to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
}
for (int i=1;i<=n;++i) if (!dfn[i]) Tarjan(i);
for (int t=1;t<=scc;++t){
for (int k=1;k<=n;++k)
if (bel[k]==t)
for (int i=1;i<=n;++i)
if (bel[i]==t)
for (int j=1;j<=n;++j)
if (bel[j]==t)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
int md=0;
for (int i=1;i<=n;++i)
if (bel[i]==t)
for (int j=1;j<=n;++j)
if (bel[j]==t)
md=max(md,a[i][j]);
ans+=md+1;
}
for (int i=1;i<=n;++i) if (a[i][i]<0) return puts("NIE"),0;
printf("%d\n",ans);return 0;
}
[BZOJ2789][Poi2012]Letters
醒醒，交换次数就是逆序对数。
然后同种字母之间的相对顺序不会改变（你去交换两个相邻的同种字母试试），所以就给字符标个号然后求逆序对即可。
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e6+5;
int n,nxt[N],hd[26],c[N];char s1[N],s2[N];long long ans;
void mdf(int k){while(k<=n)++c[k],k+=k&-k;}
int qry(int k){int s=0;while(k)s+=c[k],k^=k&-k;return s;}
int main(){
scanf("%d%s%s",&n,s1+1,s2+1);
for (int i=1,c;i<=n;++i) c=s1[i]-'A',nxt[i]=hd[c],hd[c]=i;
for (int i=n,c;i;--i) c=s2[i]-'A',ans+=qry(hd[c]),mdf(hd[c]),hd[c]=nxt[hd[c]];
printf("%lld\n",ans);return 0;
}
[BZOJ2790][Poi2012]Distance
对于两个数\(a,b\)，他们之间的距离函数\(d(a,b)=f(a)+f(b)-2f(\gcd(a,b))\)，其中\(f(i)\)为\(i\)中包含的质因子个数。我们枚举\(\gcd\)再找出所有是\(\gcd\)倍数的数，显然只会用\(f(a)\)最小的\(a\)与其余的\(b\)去匹配。
可能枚举到的\(\gcd\)并不是真正的\(\gcd(a,b)\)，但可以保证此时算出的答案不会更优而使答案最优的\(\gcd(a,b)\)一定会被枚举到。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1e6+5;
int n,zhi[N],pri[N],tot,s[N],a[N],nxt[N],hd[N],q[N],top,ans[N],pos[N],las[N];
int main(){
memset(ans,63,sizeof(ans));
for (int i=2;i<N;++i){
if (!zhi[i]) pri[++tot]=i,s[i]=1;
for (int j=1;i*pri[j]<N;++j){
zhi[i*pri[j]]=1;s[i*pri[j]]=s[i]+1;
if (i%pri[j]==0) break;
}
}
n=gi();
for (int i=1;i<=n;++i) a[i]=gi(),nxt[i]=hd[a[i]],hd[a[i]]=i;
for (int i=1;i<N;++i){
top=0;
for (int j=i;j<N;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 (s[a[q[j]]]<s[a[p]]||(s[a[q[j]]]==s[a[p]]&&q[j]<p)) swap(p,q[j]);
for (int j=2;j<=top;++j){
int val=s[a[q[j]]]+s[a[p]]-(s[i]<<1);
if (val<ans[q[j]]||(val==ans[q[j]]&&p<pos[q[j]])) ans[q[j]]=val,pos[q[j]]=p;
if (val<ans[p]||(val==ans[p]&&q[j]<pos[p])) ans[p]=val,pos[p]=q[j];
}
}
for (int i=1;i<=n;++i) printf("%d\n",pos[i]);
return 0;
}
[BZOJ2791][Poi2012]Rendezvous
虽然有一大堆条件，但实际上\(x,y\)只有至多两种取值。（在环上\(a\)走到\(b\)，或者\(b\)走到\(a\)，\(a,b\)同时走一定不优）
如果在同一棵基环内向树上的话就是走到树上\(\mbox{lca}\)。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 5e5+5;
int n,m,fa[N],vis[N],S[N],ins[N],cir[N],pos[N],len[N],id,nxt[N],hd[N],dep[N],sz[N],bel[N],top[N];
void dfs(int u){
if (ins[u]){
++id;
for (int i=S[0];S[i+1]!=u;--i)
cir[S[i]]=id,pos[S[i]]=++len[id];
return;
}
if (vis[u]) return;vis[u]=1;
ins[S[++S[0]]=u]=1;dfs(fa[u]);ins[u]=S[S[0]--]=0;
}
void dfs1(int u,int f,int rt){
dep[u]=dep[f]+1;sz[u]=1;bel[u]=rt;
for (int v=hd[u];v;v=nxt[v])
dfs1(v,u,rt),sz[u]+=sz[v];
}
void dfs2(int u,int up){
top[u]=up;int son=0;
for (int v=hd[u];v;v=nxt[v]) son=sz[v]>sz[son]?v:son;
if (son) dfs2(son,up);else return;
for (int v=hd[u];v;v=nxt[v]) if (v^son) dfs2(v,v);
}
int lca(int u,int v){
while (top[u]^top[v]){
if (dep[top[u]]>dep[top[v]]) u=fa[top[u]];
else v=fa[top[v]];
}
return dep[u]<dep[v]?u:v;
}
bool cmp(int x1,int y1,int x2,int y2){
if (max(x1,y1)^max(x2,y2)) return max(x1,y1)<max(x2,y2);
if (min(x1,y1)^min(x2,y2)) return min(x1,y1)<min(x2,y2);
return x1>=y1;
}
int main(){
n=gi();m=gi();dep[0]=-1;
for (int i=1;i<=n;++i) fa[i]=gi();
for (int i=1;i<=n;++i) if (!vis[i]) dfs(i);
for (int i=1;i<=n;++i) if (!cir[i]) nxt[i]=hd[fa[i]],hd[fa[i]]=i;
for (int i=1;i<=n;++i) if (cir[i]) dfs1(i,0,i),dfs2(i,i);
while (m--){
int u=gi(),v=gi();
if (cir[bel[u]]^cir[bel[v]]) puts("-1 -1");
else if (bel[u]==bel[v]){
int w=lca(u,v);
printf("%d %d\n",dep[u]-dep[w],dep[v]-dep[w]);
}else{
int c1=(pos[bel[u]]-pos[bel[v]]+len[cir[bel[u]]])%len[cir[bel[u]]];
int c2=len[cir[bel[u]]]-c1;
if (cmp(dep[u]+c1,dep[v],dep[u],dep[v]+c2)) printf("%d %d\n",dep[u]+c1,dep[v]);
else printf("%d %d\n",dep[u],dep[v]+c2);
}
}
return 0;
}
[BZOJ2792][Poi2012]Well
肯定是二分答案。先不考虑那个\(0\)，可以贪心地减，具体来说就是从前往后如果\(a_i>a_{i-1}+mid\)就把\(a_i\)减成\(a_{i-1}+mid\)，从后往前如果\(a_i>a_{i+1}+mid\)就把\(a_i\)减成\(a_{i+1}+mid\)。
现在考虑把一个位置改成\(0\)，相当于是从这个点开始向左向右画两条斜率为\(\pm mid\)的直线，在这条直线上方的点都要减。考虑求出把每个位置改成\(0\)后影响的区间左右端点，这个一定是随下标增长单调的，所以就可以线性计算出把每个位置改成\(0\)所需的额外代价。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
ll gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const ll N = 1e6+5;
int n;ll m,a[N],b[N],sum[N],cost[N];
int check(ll mid){
ll 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]+mid) tot+=b[i]-b[i-1]-mid,b[i]=b[i-1]+mid;
for (int i=n-1;i;--i) if (b[i]>b[i+1]+mid) tot+=b[i]-b[i+1]-mid,b[i]=b[i+1]+mid;
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]>mid*(i-l)) --l;
cost[i]=sum[i]-sum[l]-(mid*(i-l-1)*(i-l)>>1);
}
for (int i=1,r=1;i<=n;++i){
while (r<=n&&b[r]>mid*(r-i)) ++r;
if (tot+cost[i]+sum[r-1]-sum[i]-(mid*(r-i-1)*(r-i)>>1)<=m) return i;
}
return 0;
}
int main(){
n=gi();scanf("%lld",&m);
for (int i=1;i<=n;++i) a[i]=gi();
int l=0,r=1<<30,res;
while (l<=r){
int mid=l+r>>1;
if (check(mid)) res=mid,r=mid-1;
else l=mid+1;
}
printf("%d %lld\n",check(res),res);return 0;
}
[BZOJ2793][Poi2012]Vouchers
维护每种人数最后一个取到哪里了，直接暴力，复杂度是调和级数。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1e6+5;
int n,m,mrk[N],hd[N],vis[N],tot;
long long sum,ans[N];
int main(){
m=gi();while (m--) mrk[gi()]=1;
for (int i=1;i<N;++i) hd[i]=i;
n=gi();while (n--){
int x=gi();long long now=sum;
while (now<sum+x){
while (hd[x]<N&&vis[hd[x]]) hd[x]+=x;
if (hd[x]>=N) break;
vis[hd[x]]=1;++now;if (mrk[hd[x]]) ans[++tot]=now;
}
sum+=x;
}
printf("%d\n",tot);
for (int i=1;i<=tot;++i) printf("%lld\n",ans[i]);
return 0;
}
[BZOJ2794][Poi2012]Cloakroom
询问离线，按\(a_i\)值加入背包，背包维护\(f_i\)表示所有凑出\(i\)的方案中\(b_i\)值最小值的最大值。
转移比较清奇，\(f_i=\max\{f_i,\min\{f_i-c,b\}\}\)。初值\(f_0=\inf,f_i=-1(i>0)\) 。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1e6+5;
int n,m,f[N],ans[N];
struct node{
int c,a,b;
bool operator < (const node &x) const
{return a<x.a;}
}p[N];
struct query{
int m,k,s,id;
bool operator < (const query &x) const
{return m<x.m;}
}q[N];
void insert(int c,int b){
for (int i=100000;i>=c;--i)
if (~f[i-c]) f[i]=max(f[i],min(f[i-c],b));
}
int main(){
n=gi();
for (int i=1;i<=n;++i) p[i]=(node){gi(),gi(),gi()};
m=gi();
for (int i=1;i<=m;++i) q[i]=(query){gi(),gi(),gi(),i};
sort(p+1,p+n+1);sort(q+1,q+m+1);
memset(f,-1,sizeof(f));f[0]=1<<30;
for (int i=1,j=1;i<=m;++i){
while (j<=n&&p[j].a<=q[i].m) insert(p[j].c,p[j].b),++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;
}
[BZOJ2795][Poi2012]A Horrible Poem
字符串\(\mbox{hash}\)。有一种\(O(q\sqrt n)\)枚举约数的做法，然后每次尝试减去一个质因数就可以做到\(O(q\log n)\) 。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ull unsigned long long
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 5e5+5;
const int base = 20020415;
int n,q,pri[N],tot,zhi[N],p[N];
char s[N];ull pw[N],hsh[N];
ull cal(int l,int r){return hsh[r]-hsh[l-1]*pw[r-l+1];}
bool check(int l,int r,int sz){return cal(l,r-sz)==cal(l+sz,r);}
int main(){
for (int i=pw[0]=1;i<N;++i) pw[i]=pw[i-1]*base;
n=gi();scanf("%s",s+1);q=gi();
for (int i=1;i<=n;++i) hsh[i]=hsh[i-1]*base+s[i];
for (int i=2;i<=n;++i){
if (!zhi[i]) pri[++tot]=i,p[i]=i;
for (int j=1;j<=tot&&i*pri[j]<=n;++j){
zhi[i*pri[j]]=1;p[i*pri[j]]=pri[j];
if (i%pri[j]==0) break;
}
}
while (q--){
int l=gi(),r=gi(),ans=r-l+1;
for (int i=r-l+1;i>1;i/=p[i])
if (check(l,r,ans/p[i])) ans/=p[i];
printf("%d\n",ans);
}
return 0;
}
[BZOJ2796][Poi2012]Fibonacci Representation
每次贪心减去与当前\(n\)值绝对值之差最小的\(\mbox{Fibonacci}\)数即可。不太会证。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
ll f[1000];int len;
int cal(ll n){
if (n==0) return 0;
int x=lower_bound(f+1,f+len+1,n)-f;
return cal(min(n-f[x-1],f[x]-n))+1;
}
int main(){
f[1]=1;f[len=2]=2;
while (f[len]<=1e18) ++len,f[len]=f[len-1]+f[len-2];
int T;scanf("%d",&T);while (T--){
ll n;scanf("%lld",&n);printf("%d\n",cal(n));
}
return 0;
}
[BZOJ2797][Poi2012]Squarks
前几天\(\mbox{NOIP}\)模拟赛的一个题。考场上当然不会做啦
假设\(x_1\le x_2\le ... \le x_n\)，如果已知\(x_1\)，因为\(x_1+x_2\)一定是这\(\binom n2\)个数中最小的，所以就可以知道\(x_2\)，继而可以知道\(x_3\)，因为\(x_1+x_3\)一定是次小的。接着去掉\(x_2+x_3\)后，\(x_1+x_4\)又是最小的，然后就又知道了\(x_4\)。。。以此类推便可以解出所有的\(x_i\)。
所以现在的瓶颈在于枚举\(x_1\)。因为\(x_1+x_2,x_1+x_3\)一定是最小的两个数，而且如果我们知道了\(x_2+x_3\)就可以把这三个数都解出来，所以可以枚举\(x_2+x_3\)是第几个数。只需要从第\(3\)个枚举到第\(n\)个即可，因为比\(x_2+x_3\)还小的一定是\(x_1+x_i\)，这样的数只有\(n-1\)个。
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 305;
int n,m,a[N*N],tmp[N],len,x[N],ans[N][N],tot;
multiset<int>S,S0;
void work(int x1){
S=S0;x[1]=x1;x[2]=*S.begin()-x1;S.erase(S.begin());
if (x[2]<x[1]) return;
for (int i=3;i<=n;++i){
x[i]=*S.begin()-x1;S.erase(S.begin());
if (x[i]<x[i-1]) return;
for (int j=2;j<i;++j){
if (S.find(x[j]+x[i])==S.end()) return;
S.erase(S.find(x[j]+x[i]));
}
}
++tot;
for (int i=1;i<=n;++i) ans[tot][i]=x[i];
}
int main(){
n=gi();m=n*(n-1)>>1;
for (int i=1;i<=m;++i) S0.insert(a[i]=gi());sort(a+1,a+m+1);
for (int i=3;i<=n;++i){
int x=a[1]+a[2]-a[i];
if (x<=0||(x&1)) continue;
tmp[++len]=x>>1;
}
len=unique(tmp+1,tmp+len+1)-tmp-1;
for (int i=1;i<=len;++i) work(tmp[i]);
printf("%d\n",tot);
for (int i=1;i<=tot;++i,puts(""))
for (int j=1;j<=n;++j)
printf("%d ",ans[i][j]);
return 0;
}
[BZOJ2798][Poi2012]Bidding
口胡一下好了。
考虑第一维，它一定是\(2^a3^b\)的形式。所以总状态数只有\(O(n\log^2n)\)，记忆化搜索一下就好了吧。
不很懂为什么要强行把博弈出成交互。
[BZOJ2799][Poi2012]Salaries
可以求出每个点最大的可以取到的权值，然后问题就变成了，给你若干个数，每个数可以取前\(b_i\)大的权值，求每个数是否可以确定取那个值。
直接按照\(b_i\)排序然后权值从小往大处理就好了。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1e6+5;
int n,m,rt,a[N],vis[N],nxt[N],head[N],mx[N];
pair<int,int>p[N];
void dfs(int u,int x){
if (!a[u]) p[++m]=make_pair(x,u);
for (int v=head[u];v;v=nxt[v]) dfs(v,a[v]?a[v]:mx[x-1]);
}
int main(){
n=gi();
for (int i=1,f;i<=n;++i){
f=gi(),a[i]=gi();vis[a[i]]=1;
if (f^i) nxt[i]=head[f],head[f]=i;
else rt=i;
}
for (int i=1;i<=n;++i) mx[i]=vis[i]?mx[i-1]:i;
dfs(rt,n);sort(p+1,p+m+1);
for (int i=1,j=0,k=0;i<=n;++i)
if (vis[i]) ++k;
else{
int t=0;
while (j<m&&p[j+1].first==i) ++j,++t;
if (t==1&&j+k==i) a[p[j].second]=i;
}
for (int i=1;i<=n;++i) printf("%d\n",a[i]);
return 0;
}
[BZOJ2800][Poi2012]Leveling Ground
把原序列差分，变成\(n+1\)个数，每次操作相当于是选两个数一个加\(a\)一个减\(a\)或者一个加\(b\)一个减\(b\)。
设\(i\)位置上加了\(x_i\)次\(a\)，加了\(y_i\)次\(b\)，于是就有\(ax_i+by_i=val_i\)（假设\(val_i\)是差分后这个位置上的值）。上\(\mbox{exgcd}\)，然后我们要最小化\(|x_i|+|y_i|\)。因为\(val_i\)可能取负值，所以\(|x_i|+|y_i|\)取最小的位置有：\(x\)取最小非负整数解或最大非正整数解，\(y\)取最小非负整数解或最大非正整数解。
取完之后可能\(\sum x_i\neq0\)，所以还要把一些\(x_i\)与\(y_i\)均摊一下，可以开个堆，每次选择变化量最小的一种方式去修改\(x_i\)与\(y_i\)的值。
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
#define ll long long
#define pi pair<ll,int>
const int N = 1e5+5;
int n,A,B,D,X,Y,val[N],ansx[N],ansy[N];
priority_queue<pi,vector<pi>,greater<pi> >Q;
void exgcd(int a,int b,int &x,int &y){
if (!b) x=1,y=0;
else exgcd(b,a%b,y,x),y-=a/b*x;
}
int abs(int x){return x>0?x:-x;}
ll cost(int i){
return 1ll*abs(ansx[i]-B)+abs(ansy[i]+A)-abs(ansx[i])-abs(ansy[i]);
}
int main(){
n=gi()+1;A=gi();B=gi();D=__gcd(A,B);A/=D;B/=D;exgcd(A,B,X,Y);
for (int i=1;i<n;++i) val[i]=gi();
for (int i=n;i;--i){
val[i]-=val[i-1];
if (val[i]%D) return puts("-1"),0;val[i]/=D;
int x=(1ll*X*val[i]%B+B)%B,y=(val[i]-1ll*A*x)/B;
ansx[i]=x,ansy[i]=y;
x-=B,y+=A;
if (abs(x)+abs(y)<abs(ansx[i])+abs(ansy[i]))
ansx[i]=x,ansy[i]=y;
y=(1ll*Y*val[i]%A+A)%A,x=(val[i]-1ll*B*y)/A;
if (abs(x)+abs(y)<abs(ansx[i])+abs(ansy[i]))
ansx[i]=x,ansy[i]=y;
y-=A,x+=B;
if (abs(x)+abs(y)<abs(ansx[i])+abs(ansy[i]))
ansx[i]=x,ansy[i]=y;
}
ll t=0;
for (int i=1;i<=n;++i) t+=ansx[i];
t/=B;if (t<0){
t=-t;swap(A,B);swap(X,Y);
for (int i=1;i<=n;++i) swap(ansx[i],ansy[i]);
}
for (int i=1;i<=n;++i) Q.push(make_pair(cost(i),i));
while (t--){
int i=Q.top().second;Q.pop();
ansx[i]-=B;ansy[i]+=A;Q.push(make_pair(cost(i),i));
}
t=0;
for (int i=1;i<=n;++i) t+=abs(ansx[i])+abs(ansy[i]);
printf("%lld\n",t>>1);return 0;
}
[BZOJ2801][Poi2012]Minimalist Security
对于每个连通块，设其中某一个点的权值减少量为\(x\)，那么其他所有点的权值减少量都可以用\(k_ix+b_i\)表示。这样也可以求出\(x\)的取值范围。\(dfs\)过程中遇到返祖边解个方程即可。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 5e5+5;
const int M = 3e6+5;
int n,m,to[M<<1],nxt[M<<1],head[N],cnt;
ll p[N],ww[M<<1],k[N],b[N],low,upp,sumk,sumb,ans_min,ans_max;
void link(int u,int v,ll w){
to[++cnt]=v;nxt[cnt]=head[u];ww[cnt]=w;head[u]=cnt;
to[++cnt]=u;nxt[cnt]=head[v];ww[cnt]=w;head[v]=cnt;
}
void dfs(int u){
if (k[u]==1) low=max(low,-b[u]),upp=min(upp,p[u]-b[u]);
else low=max(low,b[u]-p[u]),upp=min(upp,b[u]);
sumk+=k[u];sumb+=b[u];
for (int e=head[u],v;e;e=nxt[e])
if (!k[v=to[e]]){
k[v]=-k[u];b[v]=-b[u]+p[u]+p[v]-ww[e];
dfs(v);
}else{
if (k[u]!=k[v]){
if (b[u]+b[v]!=p[u]+p[v]-ww[e]) puts("NIE"),exit(0);
}else{
ll tmp=p[u]+p[v]-ww[e]-b[u]-b[v];
if (tmp&1) puts("NIE"),exit(0);
tmp=(tmp>>1)*k[u];
if (low>tmp||upp<tmp) puts("NIE"),exit(0);
low=upp=tmp;
}
}
}
int main(){
n=gi();m=gi();
for (int i=1;i<=n;++i) p[i]=gi();
for (int i=1;i<=m;++i){
int u=gi(),v=gi();ll w=gi();
link(u,v,w);
}
for (int i=1;i<=n;++i)
if (!k[i]){
k[i]=1;b[i]=0;sumk=sumb=0;
low=-1e18;upp=1e18;
dfs(i);
if (low>upp) puts("NIE"),exit(0);
if (sumk>=0){
ans_min+=1ll*sumk*low+sumb;
ans_max+=1ll*sumk*upp+sumb;
}else{
ans_min+=1ll*sumk*upp+sumb;
ans_max+=1ll*sumk*low+sumb;
}
}
printf("%lld %lld\n",ans_min,ans_max);return 0;
}
[BZOJ2802][Poi2012]Warehouse Store
贪心，能选则选，否则如果当天的量比之前选过的量最多的那天的量要少就不选那天改选当天。
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 250005;
int n,a[N],vis[N],ans;long long sum;
priority_queue<pair<int,int> >Q;
int main(){
n=gi();
for (int i=1;i<=n;++i) a[i]=gi();
for (int i=1;i<=n;++i){
int b=gi();sum+=a[i];
if (sum>=b) sum-=b,Q.push(make_pair(b,i)),vis[i]=1;
else if (!Q.empty()&&b<Q.top().first&&sum+Q.top().first>=b){
sum+=Q.top().first,vis[Q.top().second]=0,Q.pop();
sum-=b,Q.push(make_pair(b,i)),vis[i]=1;
}
}
for (int i=1;i<=n;++i) if (vis[i]) ++ans;
printf("%d\n",ans);
for (int i=1;i<=n;++i) if (vis[i]) printf("%d ",i);
puts("");return 0;
}
[BZOJ2803][Poi2012]Prefixuffix
首先可以发现就是求把原串分成\(ABCBA\)这样的形式后最大的\(|A|+|B|\) （\(A,B,C\)是三个字符串，可能为空串）。一个好证但不容易发现的结论是：假设对于长度为\(i\)的\(A\)串其对应的最大的\(B\)串长度是\(f_i\)，则一定有\(f_i\le f_{i+1}+2\)。所以直接暴力就好了。
此题卡\(\mbox{Hash}\)。写了双模数才过的。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
#define ll long long
const int N = 1e6+5;
const ll base = 20020415;
int n,ans;char s[N];
struct Hash{
ll mod,hsh[N],pw[N];
void work(){
for (int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*base%mod;
for (int i=1;i<=n;++i) hsh[i]=(hsh[i-1]*base+s[i])%mod;
}
ll cal(int i,int k){
return (hsh[i]-hsh[i-k]*pw[k]%mod+mod)%mod;
}
}A,B;
bool equal(int i,int j,int k){
return A.cal(i,k)==A.cal(j,k)&&B.cal(i,k)==B.cal(j,k);
}
int main(){
scanf("%d%s",&n,s+1);
A.mod=998244353;B.mod=1000000007;
A.work();B.work();
for (int i=n>>1,j=0;i;--i,j=min(j+2,(n>>1)-i))
if (equal(i,n,i))
while (~j){
if (!equal(i+j,n-i,j)) --j;
else {ans=max(ans,i+j);break;}
}
printf("%d\n",ans);return 0;
}
[BZOJ3060][Poi2012]Tour de Byteotia
两端点都\(>k\)的边一定不会被删。
所以先加入所有两端点\(>k\)的边，再拿剩下的边做一次\(\mbox{Kruskal}\)状的东西即可。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 2e6+5;
int n,m,k,fa[N],a[N],b[N],ans;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=gi();m=gi();k=gi();
for (int i=1;i<=n;++i) fa[i]=i;
for (int i=1;i<=m;++i){
a[i]=gi(),b[i]=gi();
if (min(a[i],b[i])>k) fa[find(a[i])]=find(b[i]),++ans;
}
for (int i=1;i<=m;++i)
if (find(a[i])^find(b[i]))
fa[find(a[i])]=find(b[i]),++ans;
printf("%d\n",m-ans);return 0;
}