交易
Description
数轴上有 n 个商人，第 i 个商人位于 \(x_i\) 处。初始时你在原点，有 n 个金币。当你与某个商人在同一个坐标时，你可以给他一个金币，t 秒后他会在当前位置放下一个货物。当你与某个货物在同一个坐标时，你可以获得它。你只能与每个商人交易一次。
在数轴上移动 1 个单位长度需要花费 1 个单位的时间，交易和获得货物不需要时间。
你需要求出你获得 n 个货物并走到坐标为 m 处的最小时间。
Input
第一行三个正整数 n,m,t。
第二行 n 个正整数 \(x_i\)。
Output
一行一个整数表示答案。
Sample Input
2 3 3
1 2
Sample Output
6
HINT
\(n\leq3000000,0<x_1<\dots<x_n<m\leq10^9,0\leq{t}\leq10^9\).
Solution
100分
显然所有货物分成一段一段,付完当前段金币把货物全取走是最优的.
\(f[i]\)表示取完前\(i\)个,此时在\(x_i\)的最优价值.
\(f[i]=min\{f[j]+(x_{j+1}-x_j)+g(j+1,i)\}\;(j<i)\).
其中,\(g(i,j)\)付完\([i,j]\)段金币把货物全取走走到\(x_j\)的代价.
\(g(i,j)=3(x_j-x_i)+max\{0,t-2(x_j-x_i)\}\).
\(ans=f[n]+m-x_n\).
观察上式可以发现,将\(x_i\)的代价提取出来,可以得到
\(f[i]=min\{f[j]+g(j+1,i)\}\;(j<i)\),
\(g(i,j)=2(x_j-x_i)+max\{0,t-2(x_j-x_i)\}=max\{t,2(x_j-x_i)\}\),
\(ans=f[n]+m\).
考虑 \(2(x_j-x_i)>t\) 和 \(2(x_j-x_i)\leq{t}\) 两种情况,
前者只需对 \(f[i]-2\times{x_{i+1}}\) 取最小值 ;
因为\(x_i\)是递增的,所以当\(i>j\)时,若\(f[i]<f[j]\),则\(f[i]-2\times{x_{i+1}}<f[j]-2\times{x_{j+1}}\),单调队列维护即可.
#define N 3000001
#define INF 3000000000ll
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
typedef long long ll;
ll f[N],mi;
int x[N],Q[N],n,m,t,H,T;
inline ll g(int i,int j){
return max(t,2ll*(x[j]-x[i]));
}
inline void Aireen(){
n=read();m=read();t=read();
for(int i=1;i<=n;++i) x[i]=read();
for(int i=1;i<=n;++i) f[i]=INF;
H=1;T=0;Q[++T]=0;mi=INF;
for(int i=1;i<=n;++i){
while(H<=T&&2ll*(x[i]-x[Q[H]+1])>t){
mi=min(mi,f[Q[H]]-2ll*x[Q[H]+1]);++H;
}
if(H<=T) f[i]=min(mi+2ll*x[i],f[Q[H]]+t);
else f[i]=mi+2ll*x[i];
while(H<=T&&f[i]<=f[Q[T]]) --T;
Q[++T]=i;
}
printf("%lld\n",f[n]+m);
}
字符串
Description
给定两个长度相同的字符串 S,T，你需要求出最少进行多少次变换可以使 S 变为 T。
一次变换定义为：从前往后确定字符串的每一位，它要么变为上一位(变换后的)，要么不变(当然第一位只能不变)。
Input
第一行一个正整数 n 表示字符串长度，第二行 S，第三行 T。
Output
一行一个整数表示答案。 如果无解输出-1。
Sample Input
2
orzfang
orzzfff
Sample Output
2
HINT
\(n\leq3000000\).
Solution
100分
\(g[i]\)表示\(t_i\)是由\(s_{g[j]}\)复制得到的,显然\(g[i]\)是不下降的.
\(f[i]\)表示位置\(i\)变为\(t_i\)所需最少变换次数,\(ans=max\{f[i]\}\).
当 \(g[i]<i\) 时,对于任意 \(g[i]\leq{j}<i,f[j]=f[j+1]+1;f[i]=f[i]+1\).
这个也就等价于将序列左移+1.
差分一下即可O(1)维护.
#define N 3000005
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
int g[N],f[N],n,ans;
char s[N],t[N];
inline bool chk(){
for(int i=n,j=n;j;--j){
if(i>j) i=j;
while(i&&s[i]!=t[j]) --i;
if(!i) return false;
g[j]=i;
}
return true;
}
inline bool cmp(){
for(int i=1;i<=n;++i)
if(s[i]!=t[i]) return false;
return true;
}
inline void Aireen(){
scanf("%d%s%s",&n,s+1,t+1);
if(!chk()){
puts("-1");return;
}
if(cmp()){
puts("0");return;
}
for(int i=n,x=0,l=0;i;--i){
if(g[i]!=g[i+1]){
++l;++f[g[i]+l];
++x;ans=max(ans,x);
}
x-=f[i+l];f[i+l]=0;
}
printf("%d\n",ans);
}
矩阵
Description
有一个 \(n\times{n}\) 的矩阵，初始时有 m 个格子是黑的，其余全是白的。
每次你可以选择三个数 x,y,z，满足(x,y)和(y,z)是黑的， (z,x)是白的，然后将(z,x)染黑。
你需要求出最终最多能有多少个黑格。
Input
第一行两个正整数 n， m，接下来 m 行每行两个正整数表示黑格。
Output
一行一个整数表示答案。
Sample Input
233333 3
233 23333
2333 23333
23333 233333
Sample Output
5
HINT
\(n,m\leq1000000,1\leq{a,b}\leq{n}\),每组(a,b)互不相同。
Solution
100分
对于一个点 \((x,y)\),连边 \(x->y\).考虑每个连通块.
用\(0,1,2\)对点进行编号,则对于一条边\((u,v),u+1\equiv{v}(mod\;3)\).
如果一个连通块无法进行合法编号,则必然存在一个二元环,可以证明可以连边成为一个任意两点间联通的图(包括自环).
如果一个连通块存在\(0,1,2\)所有编号,则任意满足\((u,v),u+1\equiv{v}(mod\;3)\)的两点之间都有连边.
除以上情况之外,都无法连新的边.
#define N 1000010
#define Nxt(a) (a<3?a+1:1)
#define Lst(a) (a>1?a-1:3)
using namespace std;
typedef long long ll;
struct graph{
int nxt,to;
}e1[N],e2[N];
ll ans;
int g1[N],g2[N],c[N],siz[4],n,m,cnt,tot;
bool flag;
inline void addedge(int x,int y){
e1[++cnt].nxt=g1[x];g1[x]=cnt;e1[cnt].to=y;
e2[cnt].nxt=g2[y];g2[y]=cnt;e2[cnt].to=x;
}
inline void dfs(int u){
++cnt;++siz[c[u]];
for(int i=g1[u];i;i=e1[i].nxt){
++tot;
if(!c[e1[i].to]){
c[e1[i].to]=Nxt(c[u]);
dfs(e1[i].to);
}
else if(Nxt(c[u])!=c[e1[i].to]) flag=true;
}
for(int i=g2[u];i;i=e2[i].nxt){
++tot;
if(!c[e2[i].to]){
c[e2[i].to]=Lst(c[u]);
dfs(e2[i].to);
}
else if(Lst(c[u])!=c[e2[i].to]) flag=true;
}
}
inline void Aireen(){
n=read();m=read();
for(int i=1,j,k;i<=m;++i){
j=read();k=read();addedge(j,k);
}
for(int i=1;i<=n;++i){
if(!c[i]&&g1[i]){
flag=false;
siz[1]=siz[2]=siz[3]=0;
c[i]=1;tot=cnt=0;dfs(i);
if(flag) ans+=1ll*cnt*cnt;
else if(siz[1]&&siz[2]&&siz[3])
ans+=1ll*siz[1]*siz[2]+1ll*siz[2]*siz[3]+1ll*siz[3]*siz[1];
else ans+=tot>>1;
}
}
printf("%lld\n",ans);
}
2017-04-10 11:33:50