比赛链接
https://ac.nowcoder.com/acm/contest/1114#question
题解链接
https://ac.nowcoder.com/discuss/302786?type=101
B
代码如下
C
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<bitset>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int n,m,Q;
char s[maxn][maxn];
char tmp[maxn];
bitset<maxn>a[maxn],b,c,d;
int main() {
// ios::sync_with_stdio(false);
//freopen("富豪凯匹配串.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s[i]);
for(int j=0;j<m;j++) a[i][j]=s[i][j]-'0';
}
scanf("%d",&Q);
while(Q--){
scanf("%s",tmp);
for(int i=0;i<m;i++){
b[i]=tmp[i]=='_'?0:tmp[i]-'0';
c[i]=tmp[i]=='_'?1:0;
}
// D(b);D(c);E;
int ans=0;
for(int i=1;i<=n;i++){
d=a[i]^b; //将a[i]中所有下划线对应的位置原封不动的提取出来，其他位置置为0。如果有非下划线位置与询问串有不同，对应位置也会置为1.
if((d&c)==d) ans++; //d&c表示将所有下划线对应位置都提取出来，其他位置置为0。(d&c)==d表示除了下划线对应位置，其他位置都相同。
}
printf("%d\n",ans);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
D
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxN=500000+5;
const int maxn=200+5;
const int maxL=2000000+5;
const int maxl=6+5;
const int maxm=84*84*2+5;
const int maxv=999999+5;
const int maxV=9+5;
const int INF=0x3f3f3f3f;
int n,Q;
char str[maxl],tmp[maxL];
struct node{
int from,to,cap;
}edge[maxm];
int head[maxn],tot,d[maxn],s,t;
int maxflow;
int cnt=0;
int vis[maxv],num[maxn],g[maxn][maxl],c[maxV];
void init(){
memset(head,0,sizeof(head));
tot=1;
memset(c,0,sizeof(c));
}
int calc(){
int res=0;
for(int i=0;i<6;i++){
res=res*10+str[i]-'0';
}
return res;
}
void add(int from,int to,int cap){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].cap=cap;
edge[++tot].from=head[to],head[to]=tot,edge[tot].to=from,edge[tot].cap=0;
}
queue<int>q;
bool bfs(){
memset(d,0,sizeof(d));
while(q.size()) q.pop();
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to,cap=edge[i].cap;
if(cap&&!d[y]){
d[y]=d[x]+1;
q.push(y);
if(y==t) return 1;
}
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow,k;
for(int i=head[x];i&&rest;i=edge[i].from){
int y=edge[i].to;
if(edge[i].cap&&d[y]==d[x]+1){
k=dinic(y,min(rest,edge[i].cap));
if(!k) d[y]=0;
edge[i].cap-=k;
edge[i^1].cap+=k;
rest-=k;
}
}
return flow-rest;
}
int main() {
ios::sync_with_stdio(false);
//freopen("德育分博弈政治课.in","r",stdin);
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++){
scanf("%s",str);
sort(str,str+6);
int val=calc();
if(!vis[val]){
vis[val]=++cnt;
int temp=val;
for(int j=0;j<6;j++){
g[cnt][j]=temp%10;
temp/=10;
}
}
num[vis[val]]++;
}
s=0,t=cnt+9+1;
while(Q--){
init();
scanf("%s",tmp);
int len=strlen(tmp);
for(int i=0;i<len;i++){ //用char字符串 一定要先算出长度 不要一直将strlen带着走 否则耗时将特别长
c[tmp[i]-'0']++;
}
for(int i=1;i<=cnt;i++){
add(s,i,num[i]);
for(int j=0;j<6;j++) add(i,g[i][j]+cnt,INF);
}
for(int i=1;i<=9;i++){
add(cnt+i,t,c[i]);
}
maxflow=0;
int flow=0;
while(bfs()){
while(flow=dinic(s,INF)) maxflow+=flow;
}
// D(maxflow);E;
if(maxflow==len) printf("dyf\n");
else printf("zzk\n");
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
E
代码如下
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=500000+5;
const int maxnum=1000000+5;
const int INF=0x3f3f3f3f;
int n,Q,a[maxn],pos[maxnum],d[maxn]; //d[i]表示a[i]左边第一个与它相同的数字的下标
int ans[maxn];
struct node{
int L,R,id;
bool operator<(const node& h)const{return R<h.R;}
}q[maxn];
struct SegmentTree{
int l,r,dat;
}tr[maxn<<2];
void init(){
memset(pos,-1,sizeof(pos));
}
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r;
if(l==r){
tr[rt].dat=INF;
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
void update(int rt,int x,int v){
if(tr[rt].l==tr[rt].r){
tr[rt].dat=min(tr[rt].dat,v);
return;
}
int mid=tr[rt].l+tr[rt].r>>1;
if(x<=mid) update(rt<<1,x,v);
else update(rt<<1|1,x,v);
tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
int query(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].dat;
int val=INF;
int mid=tr[rt].l+tr[rt].r>>1;
if(l<=mid) val=min(val,query(rt<<1,l,r));
if(mid<r) val=min(val,query(rt<<1|1,l,r));
return val;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("老瞎眼 pk 小鲜肉.in","r",stdin);
init();
scanf("%d%d",&n,&Q);
pos[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]^=a[i-1];
if(pos[a[i]]==-1) d[i]=-1;
else d[i]=pos[a[i]]+1;
pos[a[i]]=i;
// D(pos[a[i]]);D(d[i]);E;
}
for(int i=1;i<=Q;i++){
scanf("%d%d",&q[i].L,&q[i].R);
q[i].id=i;
}
sort(q+1,q+Q+1);
build(1,1,n);
int cnt=1;
for(int i=1;i<=n;i++){
if(d[i]!=-1) update(1,d[i],i-d[i]+1);
while(q[cnt].R==i){
ans[q[cnt].id]=query(1,q[cnt].L,q[cnt].R);
cnt++;
}
}
for(int i=1;i<=Q;i++){
if(ans[i]==INF) printf("-1\n");
else printf("%d\n",ans[i]);
}
return 0;
}
网友评论