A:
创历史新低
dalao:d<=5,所以一个位置上只能是[i-d,i+d]，考虑状压
ljx's code
#include <bits/stdc++.h>
using namespace std;
const int maxn=505;
const int mod=998244353;
int read(){int ret=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while( isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch&15);ch=getchar();}return ret*f;
}
int n,d,ans;
int a[maxn],f[maxn][5005];
bool vis[maxn*2];
int main(){n=read(),d=read();int base=(1<<(2*d+1))-1;for(int i=1;i<=n;++i){a[i]=read();if(a[i]!=-1) vis[a[i]]=1;}for(int i=n+1;i<=n+d;++i) vis[i]=1;int in=0;for(int p=0-d;p<=0+d;++p){in<<=1;if(p<=0) in|=1;else in|=vis[p];}f[0][in]=1;for(int i=1;i<=n;++i){for(int p=0;p<=base;++p){int now=((p<<1)&base)|vis[i+d];if(a[i]!=-1){f[i][now]=(f[i][now]+f[i-1][p])%mod;}else{for(int t=0;t<=2*d;++t){if(now&(1<<t)) continue;f[i][now|(1<<t)]=(f[i][now|(1<<t)]+f[i-1][p])%mod;}}}}printf("%d\n",f[n][base]);return 0;
}
B:
你会发现，原本的第一个1只会到下一个的第一个1，原本的第二个1只会到下一个的第二个1……
因此，第i个1的区间在 s1中第i个1的坐标和s2中第i个1的坐标之间
然后如果是这样：
1的区间：
[-----------][---------------][---------------]
显然，在一起时总贡献最大
0同理。
code:
//write as ljx's code
//%bailjx
#include <bits/stdc++.h>
using namespace std;
inline int read(){int x=0;char ch=getchar();while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x;}
int n,m,cnt,ans;
int a[300005],f[300005],l[300005],r[300005];
char ch1[300005],ch2[300005];
int main(){n=read(),m=read();scanf("%s",ch1+1);scanf("%s",ch2+1);cnt=0;for(int i=1;i<=n+m;++i)if(ch1[i]=='1')l[++cnt]=i;cnt=0;for(int i=1;i<=n+m;++i)if(ch2[i]=='1')r[++cnt]=i;for(int i=1;i<=m;++i)if(r[i]<l[i]) swap(r[i],l[i]);for(int i=1;i<=m;++i){int L=1,R=i;while(L<R){int mid=(L+R)>>1;if(l[i]-(i-mid)<=r[mid]) R=mid;else L=mid+1;}f[i]=f[R-1]+(i-R);}ans+=f[m];cnt=0;for(int i=1;i<=n+m;++i){if(ch1[i]=='0'){l[++cnt]=i;}}cnt=0;for(int i=1;i<=n+m;++i)if(ch2[i]=='0')r[++cnt]=i;for(int i=1;i<=n;++i)if(r[i]<l[i]) swap(r[i],l[i]);for(int i=1;i<=n;++i){int L=1,R=i;while(L<R){int mid=(L+R)>>1;if(l[i]-(i-mid)<=r[mid]) R=mid;else L=mid+1;}f[i]=f[R-1]+(i-R);}ans+=f[n];printf("%d\n",ans);return 0;
}
C:
| T3 原题 | ARC132E |
|---|
so
nobody knows.
50pts:
//This is liujiaxin's
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int mod=998244353;
int read(){int ret=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while( isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch&15);ch=getchar();}return ret*f;
}
int n,cnt,inv2=(mod+1)/2;
char ch[maxn];
int pos[maxn],sump[maxn],f[1005][1005];
struct BIT{int tree[1005];void add(int x,int v){x++;for(;x<=n+1;x+=x&-x) tree[x]=(tree[x]+v)%mod;}int query(int x){x++;int ret=0;for(;x;x-=x&-x) ret=(ret+tree[x])%mod;return ret;}
}fir[1005],sec[1005];
int quick_pow(int a,int b){int ret=1;while(b){if(b&1) ret=1ll*ret*a%mod;a=1ll*a*a%mod;b>>=1;}return ret;
}
int main(){n=read();scanf("%s",ch+1);for(int i=1;i<=n;++i){if(ch[i]=='.'){pos[++cnt]=i;}}if(cnt==n){printf("%d\n",1ll*n*inv2%mod);return 0;}pos[cnt+1]=n+1;for(int i=0;i<=cnt;++i){for(int p=pos[i]+1;p<pos[i+1];++p){if(ch[p]=='<'){f[i][i+1]++;}}fir[i].add(i+1,f[i][i+1]);sec[i+1].add(i,f[i][i+1]);}for(int i=1;i<=cnt+1;++i){sump[i]=(sump[i-1]+pos[i])%mod;}for(int len=2;len<=cnt+1;++len){int v=quick_pow(len-1,mod-2);for(int l=0;l+len<=cnt+1;++l){int r=l+len;f[l][r]=((sump[r-1]-sump[l]+mod)%mod-1ll*pos[l]*(len-1)%mod+mod)%mod;f[l][r]=(f[l][r]+(fir[l].query(r-1)-fir[l].query(l)+mod)%mod)%mod;f[l][r]=(f[l][r]+(sec[r].query(r-1)-sec[r].query(l)+mod)%mod)%mod;f[l][r]=1ll*f[l][r]*v%mod*inv2%mod;fir[l].add(r,f[l][r]);sec[r].add(l,f[l][r]);}}printf("%d\n",f[0][cnt+1]);return 0;
}
D:
只要考虑两边间的距离是否小于等于不走这条路的dis即可。
this is by ljx
#include <bits/stdc++.h>
using namespace std;
const int maxn=2005;
const long long INF=0x3f3f3f3f3f3f3f3fll;
int read(){int ret=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while( isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch&15);ch=getchar();}return ret*f;
}
int n,m,cnt;
long long ans;
struct line{int u,v,l,c;bool operator<(const line &B)const{return l<B.l||(l==B.l&&c<B.c);}
}p[maxn];
int fa[maxn];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int lnk[maxn],son[maxn*2],nxt[maxn*2],w[maxn*2];
void add_e(int x,int y,int z){son[++cnt]=y;nxt[cnt]=lnk[x];lnk[x]=cnt;w[cnt]=z;}
struct node{int id;long long val;bool operator<(const node &B)const{return val<B.val;}
}hep[maxn];
int hep_size;
void put(int id,long long val){hep[++hep_size]=(node){id,val};int son=hep_size;while(son!=1&&hep[son]<hep[son>>1]) swap(hep[son],hep[son>>1]),son>>=1;
}
node get(){node ret=hep[1];hep[1]=hep[hep_size--];int fa=1,son;while((fa<<1)<=hep_size){if((fa<<1|1)>hep_size||hep[fa<<1]<hep[fa<<1|1]) son=fa<<1;else son=fa<<1|1;if(hep[son]<hep[fa]) swap(hep[son],hep[fa]),fa=son;else break;}return ret;
}
long long dis[maxn];
bool vis[maxn];
long long DIJ(int s,int t){memset(dis,0x3f,sizeof dis);memset(vis,0,sizeof vis);put(s,dis[s]=0);while(hep_size){int now=get().id;if(vis[now]) continue;vis[now]=1;for(int j=lnk[now];j;j=nxt[j]){if(dis[son[j]]>dis[now]+w[j]){dis[son[j]]=dis[now]+w[j];put(son[j],dis[son[j]]);}}}return dis[t];
}
int main(){n=read(),m=read();for(int i=1;i<=n;++i) fa[i]=i;for(int i=1;i<=m;++i){p[i].u=read();p[i].v=read();p[i].l=read();p[i].c=read();}sort(p+1,p+m+1);for(int i=1;i<=m;++i){int fx=getfa(p[i].u),fy=getfa(p[i].v);if(fx==fy) continue;fa[fx]=fy;ans+=p[i].c;add_e(p[i].u,p[i].v,p[i].l);add_e(p[i].v,p[i].u,p[i].l);}for(int i=1;i<=m;++i){if(DIJ(p[i].u,p[i].v)>p[i].l){add_e(p[i].u,p[i].v,p[i].l);add_e(p[i].v,p[i].u,p[i].l);ans+=p[i].c;}}printf("%lld\n",ans);return 0;
}
