Problem - E - Codeforces

思路：

1. 首先，如果n为奇数，中间那个数无法调整，所以只考虑偶数
2. 只有26个字母，我们用cnt[]记录每个字母需要交换的对数。设maxn为交换对数最多的字母。
3. 显然，如果cnt[maxn]>n/2,显然无法调整
4. 如果sum-cnt[maxn]>=cnt[maxn]，我们只需要把需要的对数，不同的互相交换，一共(sum+1)/2次即可
5. 如果大于，我们可以在本来就不同的对数中寻找这些不包含maxn这个元素的对数的数量tmp。如果tmp+sum>=2*cnt[maxn]，可以，次数是cnt[maxn]，否则不可

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
#define int              long long
const int N = 2e5 + 10;void mysolve()
{int n;string s;cin>>n>>s;if(n&1){cout<<-1<<endl;return;}vector<int>cnt(26);int sum=0;for(int i=0; i<n/2; ++i)if(s[i]==s[n-1-i])cnt[s[i]-'a']++,sum++;int maxn=max_element(cnt.begin(),cnt.end())-cnt.begin();if(cnt[maxn]*2<=sum)cout<<(sum+1)/2<<endl;else if(cnt[maxn]>n/2)cout<<-1<<endl;else{int tmp=0;for(int i=0; i<n/2; ++i)if(s[i]!=s[n-1-i]&&s[i]!='a'+maxn&&s[n-1-i]!='a'+maxn)tmp++;if(sum+tmp>=2*cnt[maxn])cout<<cnt[maxn]<<endl;else cout<<-1<<endl;}
}int32_t main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll t=1;cin >> t;while (t--){mysolve();}system("pause");return 0;
}

Problem - G2 - Codeforces

思路：

1. 首先，我们先知道1e9内的数的因子至多到1000。
2. 如果我们每次取元素x，他的贡献是对于x的因子b，数组存在x/b与x*b，可以计入贡献。我们不难发现。如果枚举因子，需要次数<=1000,产生因子的代价为,x<=1e9，代价有点高。如果是简单版本的1e6，我们是可以接受这个代价的(<=1000).
3. 那么如何处理1e6~1e9呢，考虑到他们的范围是1000，所以我们可以考虑上限b，即x*b<=1e9，发现枚举次数也是<=1000，得解
4. 每个元素出现cnt次，那么他自己跟自己产生的贡献也有cnt*(cnt-1)*(cnt-2)

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
#define int              long long
const int N = 2e5 + 10;
vector<int> getelement(int x)//暴力枚举因子
{vector<int>ans;for(int i=1; i*i<=x; ++i)if(x%i==0){ans.push_back(i);if(i*i!=x)ans.push_back(x/i);}sort(ans.begin(),ans.end());return ans;
}
void mysolve()
{map<int,int>cnt;int n,x;cin>>n;for(int i=1; i<=n; ++i)cin>>x,cnt[x]++;int ans=0;for(auto [x,k]:cnt){ans+=k*(k-1)*(k-2);//自身贡献if(x<=1e6){vector<int>tmp=getelement(x);for(auto v:tmp)if(v!=1&&x%v==0&&cnt.count(x/v)&&cnt.count(x*v))ans+=cnt[x/v]*k*cnt[x*v];//取下限}else for(int i=2; i*x<=1e9; ++i)if(x%i==0&&cnt.count(x/i)&&cnt.count(x*i))ans+=cnt[x/i]*k*cnt[x*i];//取上限}cout<<ans<<endl;
}int32_t main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll t=1;cin >> t;while (t--){mysolve();}system("pause");return 0;
}