9月杂题选做
CodeForces - 1366D
题意
给定数组(a),对于(forall a_i),找到其两个因子(d_1 > 1,d_2 > 1) ,st. (gcd(d_1 + d_2 ,a_i) = 1) 若不存在输出-1
[1 leq n leq 5 imes 10^5\
2 leq a_i leq 10^7
]
分析
若(a_i in Prime) 显然不存在
考虑(a_i = prod p_i^{e_i}) ,令(d_1 = p_1,d_2 = p_2...p_alpha) 有$d_1 equiv 0 (mod p_1),d_1 eq 0(mod p_i[i > 1]),d_2 equiv 0 (mod p_i[i > 1]),d_2 eq 0(mod p_1) $
于是有(d_1 + d_2 eq 0 (mod p_i[i > 0]))
代码
int prime[maxn];
bool vis[maxn];
bool is[maxn];
inline int euler_sieve(int n){
int cnt = 0;
for(int i = 2;i <= n;i++){
if(!vis[i]) prime[cnt++] = i;
for(int j = 0;j < cnt;j++){
if(i * prime[j] > n) break;
vis[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
return cnt;
}
int main(){
int cnt = euler_sieve(maxn - 3);
int n = rd();
VI v(n);
for(int i = 0;i < n;i++)
v[i] = rd(),is[v[i]] = 1;
vector<pair<int,pii>> ans(maxn - 3);
for(int i = 0;i < cnt;i++){
for(int j = prime[i];j < maxn - 3;j += prime[i]){
if(is[j]) {
if(ans[j].fi < 2) ans[j].fi++;
if(ans[j].fi == 1) ans[j].se.fi = prime[i],ans[j].se.se = 1;
else if(ans[j].fi == 2) ans[j].se.se *= prime[i];
}
}
}
for(int i = 0;i < n;i++)
if(ans[v[i]].fi != 2) printf("-1 ");
else printf("%d ",ans[v[i]].se.fi);
puts("");
for(int i = 0;i < n;i++)
if(ans[v[i]].fi != 2) printf("-1 ");
else printf("%d ",ans[v[i]].se.se);
}
CodeForces - 1369D
题意
给出树的生长过程。
如果这棵树没有儿子节点，就长出一个儿子节点，如果已经有了一个儿子节点，就再长出两个儿子节点。
询问(n)次生长后的节点个数
[1 leq T leq 10^4\
1 leq n leq 10^6
]
分析
画个图找规律即可
[a_i = 2a_{i-2} +a_{i-1} + [i equiv 0 (mod 3)]
]
代码
int main(){
int T = rd();
VI dp((int)2e6 + 5);
dp[1] = 0;
dp[2] = 0;
for(int i = 3;i < (int)2e6 + 5;i++)
dp[i] = ((ll)mul(dp[i - 2],2) + dp[i - 1] + (i % 3 == 0)) % MOD;
while(T--){
int n = rd();
printf("%d
",mul(dp[n],4));
}
}
CodeForces - 1311D
题意
给定(a leq b leq c),每次操作可以对任意一个数+1或者-1，求最小操作次数st. (a | b且b | c)
[1 leq t leq 100\
1 leq a leq b leq c leq 10^4
]
分析
考虑到(a,b,c)的值域，枚举(a)，由于(a | b),有(b = ka),(k leq lfloor frac{MAX}{a} floor)
确定(a,b)后显然(c)可以贪心地被(O(1))确定
因此总复杂度就是调和级数的复杂度
代码
inline pii get(int tar,int x){
int res1 = x % tar;
int res2 = tar - x % tar;
if(res1 <= res2 && x != x % tar) return make_pair(x - x % tar,res1);
else return make_pair(x - x % tar + tar,res2);
}
int main(){
int T = rd();
while(T--){
int a = rd();
int b = rd();
int c = rd();
int ans = 1e9;
int x,y,z;
x = y = z = 0;
for(int i = 1;i <= 10000;i++){
//int tmp = 0;
int A = i;
for(int j = A;j <= 20000;j+=A){
int B = j;
int C = get(B,c).fi;
//cout << A << ' ' << B << ' ' << C << '
';
int cost = abs(a - i) + abs(B - b) + get(B,c).se;
// cout << cost << '
';
//if(i == 6) cout << i << ' ' << A << ' ' << B << ' ' << C << ' ' << cost << '
';
if(cost < ans) {
ans = cost;
x = A;
y = B;
z = C;
}
}
}
printf("%d
",ans);
printf("%d %d %d
",x,y,z);
}
}
CodeForces - 1322B
题意
给定长度为(n)的数组(a)，计算
[(a_1 + a_2) oplus (a_1 + a_3) oplus ...oplus (a_1 +a_n)\
oplus (a_2 +a_3) oplus ... oplus (a_2 +a_n)\
...
\
oplus (a_{n-1} + a_n)
]
[2 leq n leq 400000\
1 leq a_i leq 10^7
]
分析
题目相当于(n)个元素两两异或求值
从二进制考虑，每一位的结果是否为1由这(O(n^2))个数的1的个数决定。
考虑如何计算第(i)位1的个数，可以知道要这一位为1，两数的和要求是两段连续的区间，于是只需对(a)的前(i)位部分排序，就可以二分算出能够加出1的个数
根据总的(1)的个数确定答案第(i)位
代码
inline int cal(int x,VI &b){
if(*b.rbegin() <= x) return b.size();
return lower_bound(all(b),x + 1) - b.begin();
}
inline int cal(int l,int r,VI &b){
return cal(r,b) - cal(l - 1,b);
}
int main(){
int n = rd();
VI a(n),b(n);
for(int i = 0;i < n;i++)
a[i] = rd();
int ans = 0;
for(int i = 0;i < 25;i++){
for(int j = 0;j < n;j++)
b[j] = a[j] % (1 << (i + 1));
sort(all(b));
ll c = 0;
int dv = 1 << i;
for(int j = 0;j < n;j++){
c += cal(dv - b[j],2 * dv - 1 - b[j],b);
c += cal(3 * dv - b[j],4 * dv - 1 - b[j],b);
}
for(int j = 0;j < n;j++)
if((b[j] * 2) & dv) c--;
c >>= 1;
if(c & 1) ans += dv;
}
printf("%d",ans);
}
CodeForces - 1277D
题意
给定(n)个互不相同的01串,要求拼接成的串在拼接的位置首尾字符相同
现每次操作可以对串翻转，求最小翻转次数st. 存在一种合法的拼接方式
[1 leq n leq 2e5
]
分析
我们只关注01串的首尾字符，只有本质不同的4种：00，01，10，11
考虑00和11都可以一次性拼完，于是可以只考虑01，10，容易发现总是交替拼接，因此最终01和10都是一半的数量级，于是让多的那部分翻转即可，记得判以下翻转的情况
代码
int main(){
int T = rd();
while(T--){
int n = rd();
string s;
int cnt[4] = {0};
VI v(n);
map<string,bool> mp;
vector<string> vv(n);
for(int i = 0;i < n;i++){
cin >> s;
vv[i] = s;
mp[s] = 1;
if(s.length() == 1) {
if(s[0] == '1') cnt[3]++,v[i] = 3;
else cnt[2]++,v[i] = 2;
}
else {
if(s[0] == '0' && s[s.length() - 1] == '1') cnt[0]++,v[i] = 0;
else if(s[0] == '1' && s[s.length() - 1] == '0') cnt[1]++,v[i] = 1;
else if(s[0] == '1') cnt[3]++,v[i] = 3;
else cnt[2]++,v[i] = 2;
}
}
//cout << cnt[0] << ' ' << cnt[1] << ' ' << cnt[2] << ' ' << cnt[3] << '
';
if(!cnt[0] && !cnt[1]) {
if(cnt[2] && cnt[3]) {
puts("-1");
continue;
}
else {
puts("0");
puts("");
continue;
}
}
int num = cnt[0] + cnt[1];
int d = num / 2;
VI ans;
if(cnt[0] <= cnt[1]) {
int del = abs(d - cnt[0]);
for(int i = 0;i < n;i++){
if(!del) break;
string ss = vv[i];
reverse(all(ss));
if(v[i] == 1 && !mp[ss]) ans.push_back(i + 1),del--;
}
}
else {
int del = abs(d - cnt[1]);
for(int i = 0;i < n;i++){
if(!del) break;
string ss = vv[i];
reverse(all(ss));
if(v[i] == 0 && !mp[ss]) ans.push_back(i + 1),del--;
}
}
printf("%d
",(int)ans.size());
for(int i = 0;i < (int)ans.size();i++){
printf("%d ",ans[i]);
}
puts("");
}
}