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;
} 
京公网安备 11010502036488号