B - PIN Codes (暴力,注意数据范围)
题意:给你n个密码,问你最少改变几位可以让这n个密码不一样
这个题一定要注意看数据范围,因为这个n ..小于10,也就是说至少有一位保持不一样就可以保证不一样了( 0 1 2 3 4 5 6 7 8 9 )
所以直接挑每个数的最后一位暴力改就行了,还有就是存在前导零要用string数组存密码。。STL还是用的不够熟练
const int maxi = 1000; string p[maxi]; int n; void solve() { cin >> n; rpp(i,n) cin >> p[i]; int ans = 0; rpp(i,n) { int ok = 1; for (int j = i + 1; j <= n; j++) if (p[i] == p[j]) ok = 0; if (!ok) { ans++; for (int let = '0'; let <= '9'; let++) { int ok = 1; p[i][3] = let; for (int j = 1; j <= n; j++) if (i != j && p[i] == p[j]) ok = 0; if(ok) break; } } } cout << ans << endl; for (int i = 1; i <= n; i++) cout << p[i] << endl; } int main() { int t;cin >> t; while (t--) solve(); }
D - Secret Passwords (并茶几,一点点思维)
如果直接暴力按照字符串建立并茶几肯定会超时,这里就有一种巧妙的做法,
换一种建造并茶几的思路,按照26个字母建造并茶几,把每个字符串里出现过的字母连接起来,最后统计
int fa[30],tag[30]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} void join(int x,int y){fa[find(y)]=find(x);} int main() { int n;cin>>n;int ans=0; rep(i,29) fa[i]=i; rep(i,n) { string s;cin>>s; tag[s[0]-'a']=1; rpp(j,s.size()-1) join(s[0]-'a',s[j]-'a'),tag[s[j]-'a']=1; } rep(i,'z'-'a'+1) if(fa[i]==i&&tag[i]) ++ans; cout<<ans<<endl; return 0; }