Codeforces Round #696
Codeforces Round #696
@[toc]
CF1474A Puzzle From the Future
题意：
在2022年，Mike发现了两个长度为n的二进制整数a和b(它们都只由前导有0的数字(和1)表示)。为了不忘记它们，他想用以下方式构造整数d:
他将a和b按位加和而不进行进位转换，从而得到一个整数c，所以c可能有一个或多个2。例如，0110和1101按位求和的结果是1211，011000和011000按位加和的结果是022000；
之后，Mike将c中相等的连续数字折叠为1位，因此得到d。经过这个操作，1211变成121,022000变成020(所以，d不会有相等的连续数字）。
不幸的是，迈克在自己计算d之前就失去了整数a。现在，为了让他高兴起来，你要找到一个长度为n的二进制整数a，使d成为最大的可能的整数。
最大可能的整数的意思是102＞21，012<101，021=21，以此类推。
题解：
规律题，找到规律就行
我们发现a的第一位肯定是1（从左往右数），为了让d更大，我们要让a加b更大，且不能存在一样的数，所以从第二位开始，如果a和b的第i-1位 等于 b的第i位+1，说明第a位就不能取1，只能取0，反之可取1
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
string b="1";
for(int i=1;i<n;i++)
{
int w=s[i]-'0';
int x,y;
x=s[i-1]-'0';
y=b[i-1]-'0';
if(w+1==x+y)b+='0';
else b+='1';
}
cout<<b<<endl;
}
return 0;
} CF1474B Different Divisors
题意：
求一个数，这个数至少有4个除数，且每个除数的差至少是d。
题解：
根据题意多举例子就能发现：
第一位肯定是1，最后一位肯定是中间所有数的乘积，然后第二位比第1位大d，且我们要保证除了第一位和最后一位，其他位的数都必须是质数，这样可以保证最后一位最小
所以我们每次找大于前一位+d的质数
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
const int maxn=1e7+9;
int tag[maxn],prime[maxn];
int cnt=0;
void Prime(int N)
{
memset(tag,0,sizeof(tag));
tag[0]=tag[1]=1;
for(int i=2;i<N;i++)
{
if(!tag[i])
prime[cnt++]=i;
for(int j=0;j<cnt&&prime[j]*i<N;j++)
{
tag[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
int main()
{
Prime(1000000);
int t;
cin>>t;
while(t--)
{
int d;
cin>>d;
int x=1;
x+=d;
x=lower_bound(prime,prime+cnt,x)-prime;
int y=prime[x];
y+=d;
y=lower_bound(prime,prime+cnt,y)-prime;
cout<<prime[x]*prime[y]<<endl;
}
}
CF1474C Array Destruction
题意：
题目给出一个长度为2n的正整数序列，现在问你是否存在一个x使得可以不断的进行如下操作，直到这个序列变为空：
从序列中找到两个数字a1,a2，使得a1+a2==x，然后从序列中删掉这两个数字，x的值也被更新，x=max(a1,a+2)。
题解：
因为n的范围并不大，所以x可以暴力枚举
因为x是单调递增的，所以第一个x必然是最大的那个数加上另一个数，最大的数是确定的，另一个数可以枚举
所以一开始枚举2n-1个另一个数，和最大的那个数一起组成最初的x，然后接下来每一步都知道x是谁，且知道最大值是谁，那么x-最大值直接二分查找。一直进行下去，如果中间有二分找不到的数，就从头枚举另一个数重新来
复杂度：O(n^2^logn)
这题主要看你set用的熟不熟练了
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int T, n, a[maxn], ans;
multiset<int> st;
vector<pair<int, int> > vec;
bool _check(int ii) {
st.clear();
for (int i = 0; i < 2*n-1; i ++) {
if (i == ii) continue;
st.insert(a[i]);
}
vec.clear();
vec.push_back({a[2*n-1], a[ii]});
ans = a[2*n-1] + a[ii];
int tmp = a[2*n-1];
for (int i = 1; i < n; i ++) {
multiset<int>::iterator it = st.end(), it2;
it --;
int x = *it;
st.erase(it);
it2 = st.lower_bound(tmp - x);
if (it2 == st.end()) return false;
int y = *it2;
if (x + y != tmp) return false;
vec.push_back({x, y});
tmp = max(x, y);
st.erase(it2);
}
return true;
}
bool check() {
for (int i = 0; i < 2*n-1; i ++) if (_check(i)) return true;
return false;
}
int main() {
scanf("%d", &T);
while (T --) {
scanf("%d", &n);
for (int i = 0; i < 2*n; i ++) scanf("%d", a+i);
sort(a, a+2*n);
if (check()) {
puts("YES");
printf("%d\n", ans);
for (auto x : vec) printf("%d %d\n", x.first, x.second);
}
else puts("NO");
}
return 0;
} CF1474D Cleaning
题意：
每次拿走两个相邻位置的一个石头（可以拿多次），且有且只有一次交换两个相邻位置的机会，问能不能将所有石头拿走
题解：
如果有后一个数字大于前一个数字，我们从前往后就会出现后一个为0，前一个还不为0的情况，所以一定不可能。同理从后往前删除是一样的情况
我们用pre预先处理从前往后的差分
suf预处理从后往前的差分
如果pre与suf数组存在同一位置相等，说明就可以全部拿走
因为还有一次交换的机会，所以直接暴力交换i和i+1两个位置，然后求出当前位置新的pre和和suf，用于判断是否相等
代码：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std ;
const int maxn = 2e5 + 10 ;
typedef long long ll ;
ll a[maxn] , pre[maxn] , suf[maxn] ;
const ll inf = 1e18 ;
int main(){
int t ;
cin >> t ;
while(t--){
ll n ;
cin >> n ;
memset(pre , 0 , sizeof(pre)) ;
memset(suf , 0 , sizeof(suf)) ;
for(ll i = 1 ; i <= n ; i++) cin >> a[i] ;
for(ll i = 1 ; i <= n ; i++)
{
if(a[i] >= pre[i-1]) pre[i] = a[i] - pre[i-1] ;
else pre[i] = inf / 2 ; // 预处理pre，当有不符合情况的时候，pre数组从此往后全为inf/2
}
for(ll i = n ; i >= 1 ; i--)
{
if(a[i] >= suf[i+1]) suf[i] = a[i] - suf[i+1] ;
else suf[i] = inf ;// 从后往前，如果有不符合，那么全为inf
}
bool flag = 1 ;
for(ll i = 1 ; i <= n - 1 ; i++)
{
if(pre[i] == suf[i+1]){ // 如果可以接上的话直接输出yes就行
flag = 0 ;
break ;
}
else
{
ll tmp1 = a[i] ; // 如果接不上，那么交换a[i]与a[i+1] 然后实现pre[i] 和 suf[i+1] 如果接的上输出yes
ll tmp2 = a[i+1] ;
if(tmp1 >= suf[i+2] && tmp2 >= pre[i-1])
{
tmp1 -= suf[i+2] ;
tmp2 -= pre[i-1] ;
if(tmp1 == tmp2)
{
flag = 0 ;
break ;
}
}
}
}
if(!flag) cout << "YES" << endl ;
else cout << "NO" << endl ;
}
return 0 ;
}
CF1474E What Is It?
题意：
一个排列，你可以选择i , j ( i ≠ j ) ，满足a [ j ] = i , 然后交换a[i],a[j]，交换收益为 (i-j)^2^。
让你构造一个长度为n的排列，使得交换过程所得收益最大。
题解：
我们不难发现我们每次交换，都会使得至少一个数归位（也就是a[i]=i），当所有位置归位时我们将无法再交换，所以最多交换n-1次
我们再考虑距离为n-1的对数最多是多少？只有一对，就是（1，n），除此之外没有了
我们再考虑n-2的对数最多是多少？最多是两对，就是(1,n-1)和(2,n),（当然其他考虑也是一样的），最多只有两对
当距离为n-3的也只有两对
那么最大收益就是(n-1)^2^ + 2(n-2)^2^ + 2(n-3)^2^+...
这样收益就算出来了
至于步骤我们可以你想考虑，也就是一开始数组a都是归位的，然后先弄(n-1)对，再弄(n-2)对，这样就得到最后的排列和交换过程
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
int a[maxn];
int main() {
int T;scanf("%d",&T);
while(T--) {
int n;scanf("%d",&n);
for(int i = 1;i <= n;i++) {
a[i] = i;
}
vector<pair<int,int> >vec;
ll ans = 0;
int cnt = n - 1;
for(int i = n - 1;;i--) { //交换两点的距离
swap(a[i + 1],a[1]);
vec.push_back({i + 1,1});
ans += 1ll * i * i;
cnt--;
if(cnt == 0) break;
if(i == n - 1) continue;
swap(a[n - i],a[n]);
vec.push_back({n - i,n});
ans += 1ll * i * i;
cnt--;
if(cnt == 0) break;
}
printf("%lld\n",ans);
for(int i = 1;i <= n;i++) {
printf("%d ",a[i]);
}
printf("\n");
printf("%d\n",n - 1);
for(int i = vec.size() - 1;i >= 0;i--) {
printf("%d %d\n",vec[i].first,vec[i].second);
}
}
return 0;
}
CF1474F 1 2 3 4 ..
题意：
题解：
代码：
codeforces题目分析
腾讯开奖126人在聊