正題

題目大意:https://jzoj.net/senior/#main/show/3888

---

題目大意

$n$個人$m$道題，已知道每個人的選項(xiàng)和有$p$個人滿分和$q$個人零分，求字典序最小的可能的正確答案。

---

解題思路

用字符串$hash$判斷即可。要注意的是如果沒有一個人滿分也沒有一個人零分要用$dfs$找到字典序最小的。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<map> #define ull unsigned long long using namespace std; const int N=31000,P=131; int n,m,p,q,flag; char ans[600]; map<ull,int> v; struct node{ull z,f;string s; }a[N]; bool cmp(node x,node y) {return x.s<y.s;} void dfs(int x,ull z,ull w) {if(x>=m){if(!v[z]&&!v[w]){for(int i=0;i<m;i++)putchar(ans[i]);flag=1;}return;}if(flag) return;ans[x]='N';dfs(x+1,z*P,w*P+1);if(flag) return;ans[x]='Y';dfs(x+1,z*P+1,w*P); } int main() {scanf("%d%d%d%d",&n,&m,&p,&q);for(int i=1;i<=n;i++){cin>>a[i].s;for(int j=0;j<m;j++)a[i].z=a[i].z*P+(a[i].s[j]=='Y'),a[i].f=a[i].f*P+(a[i].s[j]=='N');v[a[i].z]++;}if(!p&&!q){dfs(0,0,0);return 0;}sort(a+1,a+1+n,cmp);if(!p){for(int i=n;i>=1;i--)if(v[a[i].z]==q){for(int j=0;j<m;j++)putchar(a[i].s[j]=='Y'?'N':'Y');return 0;}}for(int i=1;i<=n;i++){int w=v[a[i].z];if(w!=p) continue;if(v[a[i].f]==q){cout<<a[i].s;return 0;}}printf("-1"); }

總結(jié)

以上是生活随笔為你收集整理的jzoj3888-正确答案【字符串hash,dfs】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。