AtCoder Beginner Contest 342 (已更新:C D)
C
似曾相识的经典映射题……而只会map的蒟蒻成功又被卡住了
简单的用map映射无法处理如r->a,a->r这样的多重映射,应该在先存下原本的信息,再作映射
写到这突然悟了……再改改
果然是没有悟一点(⊙﹏⊙),由于只处理26个字母,每次修改实时更新就行
错解
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
//const int N=1e2+5;
//int a[N];
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;cin>>n;
string s;cin>>s;
int q;cin>>q;
char c,d;
map<char,char>mp;
while(q--){
cin>>c>>d;
mp[c]=d;
}
for(auto i:s){
if(mp.count(i)) cout<<mp[i];
else cout<<i;
}
return 0;
}
正解
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
//const int N=1e2+5;
//int a[N];
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;cin>>n;
string s;cin>>s;
map<char,char>mp;
for(char i='a';i<='z';i++){
mp[i]=i;
}
int q;cin>>q;
char c,d;
while(q--){
cin>>c>>d;
for(char i='a';i<='z';i++){
if(mp[i]==c) mp[i]=d;
}
}
for(auto i:s){
cout<<mp[i];
}
return 0;
}
D
补充知识
唯一分解定理:任何一个大于1的整数n 都可以分解成若干个素因数的连乘积,如果不计各个素因数的顺序,那么这种分解是唯一的。
分析
完全平方数由于可以分解为两个完全相同的数的乘积,每个数又可以唯一的分解成质因子的乘积,因此完全平方数一定可以分解为质因子的偶数次的乘积,所以两数相乘要得到完全平方数的话,这两数的每个质因子的次方和都要是偶数
举个栗子:
12*48=576,576是完全平方数
12=2乘2乘3,48=3乘4乘4
两数质因子的次方和:
2:2次 3:2次 4:2次
而12*4=48,48不是完全平方数
12=2乘2乘3,4=2乘2
两数质因子的次方和:
2:4次 3:1次
所以我们可以只看每个数的为奇数次方的质因子,如果当前出现了n次,说明有(n-1)对的数的积满足每个质因子的次方和都是偶数,即完全平方数
操作
对于n个数,我们可以除去它的偶数次质因子,得到的是它的一次方的质因数的乘积x,再用cnt数组统计它的出现次数,ans+=cnt[x]-1(相当于加上此前x的出现次数)。此外,考虑到这个数可能是0,这时ans+=其它数的个数-已经遇到的为0的数的个数,所以应可以先声明tmp=n,数为0时ans+=tmp-1,tmp--;
如序列 0 1 3 2 0 7
第一次遇到0:ans+=5
第二次遇到0:ans+=4
如数本身就是完全平方数,当前出现了n次,对答案的贡献也是n-1,所以不用特判
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int cnt[N];
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,x;cin>>n;
int tmp=n,ans=0;
while(n--){
cin>>x;
if(x==0){
ans+=tmp-1;
tmp--;
continue;
}
for(int i=2;i<=x/i;i++){
while(x%(i*i)==0){
x/=(i*i);
}
}
cnt[x]++;
ans+=cnt[x]-1;
}
cout<<ans;
return 0;
}
标签:cout,int,cin,--,abc342,ans,define
From: https://www.cnblogs.com/mono-4/p/18032245