#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e4+10,M=5e2+10,sed=31,SED=131,mod=70177,MOD=92311;
int n,m,p,q,ans,tot,hd[mod],nx[N*2],ver[N*2],cnt[N*2],Hash[N],HASH[N];
struct node{
char s[M];
inline bool operator<(const node&rhs)const{
return strcmp(s,rhs.s)<0;}
}a[N];
inline void Insert(const int &x,const int &y)
{
for(int i=hd[x];i;i=nx[i])
if(ver[i]==y){++cnt[i];return;}
nx[++tot]=hd[x];hd[x]=tot;ver[tot]=y;cnt[tot]=1;
return;
}
inline int query(const int &x,const int &y)
{
for(int i=hd[x];i;i=nx[i])
if(ver[i]==y)return cnt[i];
return 0;
}
inline void solve1()
{
int tmp,TMP;ans=-1;
for(int i=0;i<n;i++)
{
tmp=TMP=0;
for(int j=0;j<m;j++)
{
tmp=(tmp*sed+(a[i].s[j]=='N'))%mod;
TMP=(TMP*SED+(a[i].s[j]=='N'))%MOD;
}
Hash[i]=tmp,HASH[i]=TMP;
Insert(tmp,TMP);
}
for(int i=0;i<n;i++)
if(query(Hash[i],HASH[i])==p)//当成满分有p个
{
tmp=TMP=0;
for(int j=0;j<m;j++)//求出零分答案
{
tmp=(tmp*sed+(a[i].s[j]=='Y'))%mod;
TMP=(TMP*SED+(a[i].s[j]=='Y'))%MOD;
}
if(query(tmp,TMP)==q){ans=i;break;}//符合题意
}
if(ans!=-1)printf("%s\n",a[ans].s);
else puts("-1");
return;
}
char cur[M];
inline void solve2()
{
int tmp,TMP;ans=-1;
for(int i=0;i<n;i++)
{
tmp=TMP=0;
for(int j=0;j<m;j++)
{
tmp=(tmp*sed+(a[i].s[j]=='N'))%mod;
TMP=(TMP*SED+(a[i].s[j]=='N'))%MOD;
}
Hash[i]=tmp,HASH[i]=TMP;
Insert(tmp,TMP);
}
for(int i=n-1;i>=0;i--)//枚举零分答案，所以字典序要反着来
if(query(Hash[i],HASH[i])==q)
{
tmp=TMP=0;
for(int j=0;j<m;j++)
{
tmp=(tmp*sed+(a[i].s[j]=='Y'))%mod;
TMP=(TMP*SED+(a[i].s[j]=='Y'))%MOD;
}
if(query(tmp,TMP)==p){ans=i;break;}
}
if(ans!=-1)
{
for(int i=0;i<m;i++)
cur[i]=a[ans].s[i]=='N'?'Y':'N';
printf("%s\n",cur);
}
else puts("-1");
return;
}
inline void solve3()
{
int tmp,TMP;
for(int i=0;i<n;i++)
{
tmp=TMP=0;
for(int j=0;j<m;j++)
{
tmp=(tmp*sed+(a[i].s[j]=='N'))%mod;
TMP=(TMP*SED+(a[i].s[j]=='N'))%MOD;
}
Insert(tmp,TMP);
tmp=TMP=0;
for(int j=0;j<m;j++)
{
tmp=(tmp*sed+(a[i].s[j]=='Y'))%mod;
TMP=(TMP*SED+(a[i].s[j]=='Y'))%MOD;
}
Insert(tmp,TMP);
}
bool flag=true;
for(int i=0;i<m;i++)cur[i]='N';
do{
tmp=TMP=0;
for(int j=0;j<m;j++)
{
tmp=(tmp*sed+(cur[j]=='N'))%mod;
TMP=(TMP*SED+(cur[j]=='N'))%MOD;
}
if(query(tmp,TMP)==0){flag=true;break;}//没有在满分和零分里面出现过
flag=false;
for(int j=m-1;j>=0;j--)
{
if(cur[j]=='Y')cur[j]='N';//已经修改过一次的部分无解
else{cur[j]='Y';flag=true;break;}//没有修改的给它修改了,可能存在解
}
}while(flag);
if(flag)printf("%s\n",cur);
else puts("-1");
return;
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d%d%d",&n,&m,&p,&q);
for(int i=0;i<n;i++)
scanf("%s",a[i].s);
sort(a,a+n);
if(p)solve1();
else if(q)solve2();
else solve3();
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1001;
const int M=1024;
const int power=9;
const int base=1e9;
struct Bignum{
int a[50];
Bignum(){memset(a,0,sizeof(a));}
void print()
{
printf("%d",a[a[0]]);
for(int i=a[0]-1;i>0;i--)
printf("%0*d",power,a[i]);
printf("\n");
}
void add(int k){if(k||a[0])a[++a[0]]=k;}
}f[2][M][3];
Bignum operator +(const Bignum&p,const Bignum&q)
{
Bignum c;
c.a[0]=max(p.a[0],q.a[0]);
for(int i=1;i<=c.a[0];i++)
{
c.a[i]+=p.a[i]+q.a[i];
c.a[i+1]+=c.a[i]/base;
c.a[i]%=base;
}
if(c.a[c.a[0]+1])c.a[0]++;
return c;
}
int n,a[N],pre,cur;
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=n;i;i--)
scanf("%d",&a[i]);
f[0][1023][0].add(1);
for(int i=0;i<n;i++)
{
cur=pre^1;
for(int j=0;j<M;j++)
for(int k=0;k<=2;k++)
f[cur][j][k]=f[pre][j][k];
for(int j=0;j<M;j++)
{
f[cur][j&a[i+1]][1]=f[cur][j&a[i+1]][1]+f[pre][j][0];f[cur][j&a[i+1]][1]=f[cur][j&a[i+1]][1]+f[pre][j][1];
f[cur][j^a[i+1]][2]=f[cur][j^a[i+1]][2]+f[pre][j][1];f[cur][j^a[i+1]][2]=f[cur][j^a[i+1]][2]+f[pre][j][2];
}
pre^=1;
}
f[pre][0][2].print();
return 0;
}
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define MP(a,b) make_pair(a,b)
typedef long long ll;
typedef pair<int,int> pii;
template<class T>inline void read(T&x)
{
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
const int N=51,M=201,K=20001;
int Case,n,m,tot,hd[N],len;
ll T,dis[N][K];//dis[i][j]表示到达i号点，时间为j+p*2d，最小的j+p*2d
bool vis[N][K];
struct Edge{
int v,nx,w;
}e[M];
inline void add(int u,int v,int w)
{
e[++tot].v=v;
e[tot].nx=hd[u];
e[tot].w=w;
hd[u]=tot;
}
inline void spfa()
{
memset(dis,0x3f,sizeof(dis));
dis[0][0]=0;queue<pii>q;q.push(MP(0,0));
while(q.size())
{
pii tmp=q.front();q.pop();
int u=tmp.first,w=tmp.second;vis[u][w]=false;
for(int i=hd[u];i;i=e[i].nx)
{
int v=e[i].v;int neww=dis[u][w]+e[i].w;
if(dis[v][neww%len]>neww)
{
dis[v][neww%len]=neww;
if(!vis[v][neww%len])
{
vis[v][neww%len]=1;q.push(MP(v,neww%len));
}
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
read(Case);
while(Case--)
{
read(n);read(m);read(T);
memset(hd,0,sizeof(hd));tot=0;
for(int i=1,u,v,w;i<=m;i++)
read(u),read(v),read(w),add(u,v,w),add(v,u,w);
if(!hd[0])puts("Impossible");
else
{
len=10001;
for(int i=hd[0];i;i=e[i].nx)
len=min(len,e[i].w);
len*=2;spfa();
if(dis[n-1][T%len]<=T)puts("Possible");
else puts("Impossible");
}
}
return 0;
}
赛后总结
T1又开始瞎JB乱想，在那里琢磨怎么确定每个问题的解……其实直接枚举每个解为正解或0分就可以了。 T2最开始写的是顺着扫一遍倒着扫一遍再枚举分点的DP，又是莫名其妙的错了。 T3也是感觉非常的迷，没想到这种做法。 或许我真的就只是嘴硬吧。三道题都有人AC，我却都不行。感觉他们在不停的进步，我却连门都没摸到。 或许我真的就只是嘴硬吧。
