省选模拟40
A. 交通
预处理一下如果在第 \(i\) 个路口遇到红灯，然后走到结尾的时间
从后往前计算，用线段树维护一下，就能查询出最近的遇到一个红灯的位置
然后加上中间路程的时间再加上等待红灯的时间就行了
再对于每个询问都这么找一下第一个遇到的红灯就能算出答案
Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define lson st[x].ls
#define rson st[x].rs
#define meow(args...) fprintf(stderr,args)
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,q,g,r,T,rt,tot;
int d[50010],s[50010],f[50010];
struct seg{int ls,rs,mn;}st[50010*80];
inline void pushup(int x){
st[x].mn=n+1;
if(lson) st[x].mn=min(st[lson].mn,st[x].mn);
if(rson) st[x].mn=min(st[rson].mn,st[x].mn);
}
void upd(int &x,int l,int r,int pos,int k){
if(!x) st[x=++tot].mn=n+1;if(l==r) return st[x].mn=k,void();
int mid=(l+r)>>1;
if(pos<=mid) upd(lson,l,mid,pos,k);
else upd(rson,mid+1,r,pos,k);
pushup(x);
}
int query(int x,int l,int r,int L,int R){
if(!x) return n+1;if(L<=l&&r<=R) return st[x].mn;
int mid=(l+r)>>1,res=n+1;
if(L<=mid) res=min(res,query(lson,l,mid,L,R));
if(R>mid) res=min(res,query(rson,mid+1,r,L,R));
return res;
}
inline int getnxt(int pos){
int L,R,v=n+1;
if(pos B. 选拔
用字符串的算法似乎不太好搞
写了个 \(AC\) 自动机，最多拿 \(90\)
于是用考虑一个 \(dp\)
设 \(f1_{i,j,k},f2_{i,j,k}\) 表示在第 \(i\) 个节点从下/上能匹配到第 \(j\) 个串的第 \(k\) 个字符
发现后两维总共就 \(O(s)\) 于是压到一起用 \(bitset\) 去优化
复杂度 \(O(\frac{ns}{w})\)
Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define meow(args...) fprintf(stderr,args)
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,now;
char st[10];
string s,t[30010];
bool jud;
vector>g[30010];
bitset<60010>f1[30010],f2[30010],trans[30],tmp,ans;
void dfs(int x,int fa){
f1[x]=f2[x]=trans[26];
for(auto L:g[x]) if(L.first!=fa){
dfs(L.first,x);
f1[L.first]<<=1;f1[L.first]&=trans[L.second];
tmp=f1[L.first];tmp<<=1;tmp&=f2[x];ans|=tmp;
f2[L.first]>>=1;f2[L.first]&=trans[L.second];
tmp=f1[x];tmp<<=1;tmp&=f2[L.first];ans|=tmp;
f1[x]|=f1[L.first],f2[x]|=f2[L.first];
}
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("selection.in","r",stdin);
freopen("selection.out","w",stdout);
n=read();
for(int i=1,x,y;i>t[i];s=s+char('z'+1)+t[i];}s=s+char('z'+1);
for(int i=0;i C. 等待
咕咕咕