T1
贪心
10 元先找5元
20元 先找10+5，再找3张5
#include<cstdio> using namespace std; int m5,m10,m20; int main()
{
freopen("book.in","r",stdin);
freopen("book.out","w",stdout);
int n;
scanf("%d",&n);
int x;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
if(x==) m5++;
else if(x==)
{
if(!m5) { puts("NO"); return ; }
m5--; m10++;
}
else
{
if(m10 && m5) m10--,m5--;
else if(m5>=) m5-=;
else { puts("NO"); return ; }
}
}
puts("YES"); return ;
}
T2
小c记得的出口位置看做左括号
从右往左扫描 信息
左括号入栈
否则判断当前栈顶 是否能匹配，
匹配则为右括号，不匹配当左括号入栈
栈空则有解，非空则无解
#include<cstdio>
#include<iostream>
#include<algorithm> #define N 1000001 using namespace std; int a[N]; int st[N],top; bool zf[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
freopen("program.in","r",stdin);
freopen("program.out","w",stdout);
int n,m;
read(n);
for(int i=;i<=n;++i) read(a[i]);
read(m);
int x;
for(int i=;i<=m;++i)
{
read(x);
if(a[x]>) a[x]=-a[x];
}
for(int i=n;i;--i)
{
if(a[i]<) st[++top]=a[i],zf[i]=true;
else
{
if(st[top]==-a[i]) top--;
else st[++top]=-a[i],zf[i]=true;
}
}
if(top) { puts("NO"); return ; }
for(int i=;i<=n;i++)
{
if(!zf[i]) printf("+%d ",abs(a[i]));
else printf("-%d ",abs(a[i]));
}
fclose(stdin); fclose(stdout);
return ;
}
不会spj所以不知道对错的代码
对于一个出口，判断前面是否有足够的入口
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 1000001 int a[N],b[N];
int tot[N],pre[N]; int outtot[N]; bool out[N],zf[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
freopen("program.in","r",stdin);
freopen("program.out","w",stdout);
int n; read(n);
int x;
for(int i=;i<=n;i++)
{
read(x); a[i]=x;
pre[i]=++tot[x];
}
int m; read(m);
for(int i=;i<=m;++i) read(b[i]);
sort(b+,b+m+);
int t=unique(b+,b+m+)-b-;
for(int i=;i<=t;i++)
{
x=b[i];
outtot[a[x]]++; out[x]=true;
if(pre[x]<outtot[a[x]]*) { puts("NO"); return ; }
}
for(int i=;i<=n;i++)
if(tot[i]&) { puts("NO"); return ; }
for(int i=;i<=n;i++)
{
if(out[i]) printf("-%d ",a[i]);
else if(outtot[a[i]]) printf("+%d ",a[i]),outtot[a[i]]--;
else if(!zf[a[i]]) printf("+%d ",a[i]),zf[a[i]]^=;
else printf("-%d ",a[i]),zf[a[i]]^=;
}
}
T3
把钥匙看做左括号，门看做右括号
模拟括号匹配，任意两点间只有两种状态：匹配，缺右括号
那么问题转化为 从a走到b 能否括号匹配
宽搜+DP
dp[i][j][k]表示 点i到点j 是否有状态k
k=0 表示 i到j的路径上能够括号匹配
k：1——10 表示 点i到j的路径上，栈顶为右括号k
k：11——20 表示点i到j的路径上，栈顶为左括号k，即缺右括号k
每次更新一个ijk，就相当于在ij之间连一条状态为k的边，扔进队列里
从队列里取出 从u到v的状态为w的边
如果w=0，那么 枚举状态k （0,11——20）
if dp[i][u][k]=true 更新 dp[i][v][k]
if dp[v][i][k]=true 更新 dp[u][i][k]
如果w！=0，那么 只能去找右括号
即if dp[v][i][w-10] 更新 dp[u][i][0]
为什么 w=0 是双向更新，w!=0是单项更新？
因为只能是栈中有左括号的情况下，右括号才能入栈
对于每一次询问，判断dp[u][v][0] 即可
#include<cstdio> using namespace std; bool dp[][][]; int head,tail; int q[][]; int main()
{
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i) dp[i][i][]=true;
int u,v,w;
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
if(!w)
{
dp[u][v][w]=dp[v][u][w]=true;
q[tail][]=u; q[tail][]=v; q[tail++][]=w;
q[tail][]=v; q[tail][]=u; q[tail++][]=w;
}
else if(w<)
{
w=-w;
dp[u][v][w]=dp[v][u][w]=true;
}
else
{
w+=;
dp[u][v][w]=dp[v][u][w]=true;
q[tail][]=u; q[tail][]=v; q[tail++][]=w;
q[tail][]=v; q[tail][]=u; q[tail++][]=w;
}
}
while(head<tail)
{
u=q[head][]; v=q[head][]; w=q[head++][];
if(!w)
{
for(int i=;i<=n;++i)
{
if(dp[i][u][] && !dp[i][v][])
{
dp[i][v][]=true;
q[tail][]=i; q[tail][]=v; q[tail++][]=;
}
if(dp[v][i][] && !dp[u][i][])
{
dp[u][i][]=true;
q[tail][]=u; q[tail][]=i; q[tail++][]=;
}
for(int j=;j<=;++j)
{
if(dp[i][u][j] && !dp[i][v][j])
{
dp[i][v][j]=true;
q[tail][]=i; q[tail][]=v; q[tail++][]=j;
}
}
}
}
else
{
for(int i=;i<=n;++i)
{
if(dp[v][i][w-] && !dp[u][i][])
{
dp[u][i][]=true;
q[tail][]=u; q[tail][]=i; q[tail++][]=;
}
}
}
}
int q;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&u,&v);
puts(dp[u][v][] ? "YES" : "NO");
}
}