A. Puzzle From the Future
题意：
整数的构建为di=ai+bi，然后去掉d中相邻且相同的部分即为d
已知整数b，你需要找到一个整数a，使得整数d最大。
思路：
为使得整数d最大，则第一位需为b1+1，后面的位置判断是否为前面的数-1，是则不变（已为当前最大），不是则当前位+1，使得整数d最大。
AC Code：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '
'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n;
char b[N], d[N];
void solve(){
cin>>n>>b;
d[0]=b[0]+1;
for(int i=1; i<n; i++){
if(b[i]==d[i-1]-1) d[i]=b[i];
else d[i]=b[i]+1;
}
for(int i=0; i<n; i++) cout<<d[i]-b[i];
cout<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}B. Different Divisors
题意：
如果y可被x整除且无余数，则将正整数x称为正整数y的除数。 例如，1是7的除数，而3不是8的除数。
我们给您一个整数d，并要求您找到最小的正整数a，使得：
a至少有4个除数；
a的任意两个除数之间的差至少为d。
思路：
打表后发现四个除数：第一个为1，第二个和第三个为相差不小于d的素数，第四个即为第二个和第三个的乘积。
所以素数打表一下，然后开始找一个与1的差至少为d的素数，再从这个素数开始找下一个差至少为d的素数。
AC Code：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '
'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int d;
bool vis[N];
int prime[N], p[N], x;
void oulasai(int n)
{
vis[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]) prime[x++]=i, p[i]=i;
for(int j=0;j<x;j++)
{
if(i*prime[j]>n) break;
vis[i*prime[j]]=true;
p[i*prime[j]]=prime[j];
if(i%prime[j]==0) break;
}
}
}
void solve(){
cin>>d;
int ans, flag=1;
for(int i=0; i<x; i++){
if(prime[i]>d&&flag) ans=prime[i], flag=0;
if(prime[i]>=ans+d) {ans*=prime[i]; break;}
}
cout<<ans<<endl;
return ;
}
signed main(){
oulasai(N);
int T;
cin>>T;
while(T--) solve();
return 0;
}C. Array Destruction
题意：
给你一个长度为2*n的数组a，首先，选择任何正整数x。然后执行以下操作n次：选择总和等于x的两个数组元素；
从a中删除它们，并用两个数字中最大的替换x。
你需要输出第一次选择的正整数x和n次删除的每两个数
思路：
显然每次删除的值必定包含当前数组中的最大值，所以第一次选择的值可以枚举数组中最大值和其他每个值的和。
然后模拟并且记录每次的删除路径，循环：每次删除先选择当前数组最大值amax，然后判断x-amax是否存在，存在则继续执行此循环，否则退出当前枚举情况。
AC Code：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
#include<set>
#include<vector>
using namespace std;
#define endl '
'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, a[N], ans;
multiset<int>s;
vector<pair<int,int>>v;
void solve(){
cin>>n;
for(int i=1; i<=2*n; i++) cin>>a[i];
sort(a+1,a+1+2*n);
for(int i=1; i<2*n; i++){
s.clear(); v.clear();
for(int j=1; j<=2*n; j++) s.insert(a[j]);
v.push_back({a[i],a[2*n]});
s.erase(s.find(a[i]));
s.erase(s.find(a[2*n]));
int now=a[2*n];
for(int k=1; k<n; k++){
int fi=*prev(s.end());
s.erase(s.find(fi));
if(s.find(now-fi)!=s.end()){
s.erase(s.find(now-fi));
v.push_back({now-fi,fi});
now=fi;
}
else break;
}
if(v.size()==n) {ans=a[i]+a[2*n]; break;}
}
if(v.size()==n){
cout<<"YES"<<endl;
cout<<ans<<endl;
for(auto it:v) cout<<it.first<<" "<<it.second<<endl;
}
else cout<<"NO"<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}D. Cleaning
题意：
给你一个长度为n的数组a，你可以执行一次（可不执行）操作：
选择一个下标i（1<=i<=n-1），将i和i+1的值交换
然后执行任意次操作：
选择一个下标i（1<=i<=n-1），将i和i+1的值都减少一
求能否是否数组a的所有值均变为0
思路：
首先不考虑交换操作，对于减值操作，从前往后减和从后往前减操作的结果显然是相等的。
对于每个位置的值，假设t为减去的值，从前操作为：
a1=t
a2-a1=t
a3-(a2-a1)=t
从后操作类似，为使得最终每个位置的值均为0，则t显然需要满足大于等于0。
综上，需要构建一个从前操作的pre数组记录当前位置i，为ai减去前一个pre[i-1]的值，若小于0则需特殊标记，类似的构建一个从后操作的suf数组。
最后判断交换i和i+1的位置的值后，对于pre[i-1]和suf[i+2]的两个值，a[i+1]和a[i]能否分别满足对应位置的值并且满足后剩余值是否相等（剩下的这两个位置为相邻可以自行消去）。
AC Code：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '
'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, a[N];
int pre[N], suf[N];
void solve(){
cin>>n;
suf[n+1]=0; //初始化
for(int i=1; i<=n; i++){ //构建pre数组
cin>>a[i];
if(pre[i-1]!=-1 && a[i]>=pre[i-1]) pre[i]=a[i]-pre[i-1];
else pre[i]=-1;
}
if (pre[n] == 0) {cout<<"YES"<<endl; return ;} //不需要交换即可满足
for(int i=n; i>=1; i--){ //构建suf数组
if(suf[i+1]!=-1 && a[i]>=suf[i+1]) suf[i]=a[i]-suf[i+1];
else suf[i]=-1;
}
for(int i=1; i<n; i++){
if(pre[i-1]==-1 || suf[i+2]==-1) continue;
if(a[i]>=suf[i+2] && a[i+1]>=pre[i-1] && a[i]-suf[i+2]==a[i+1]-pre[i-1]) {cout<<"YES"<<endl; return ;} //交换的数字的相邻位置对值的需求能满足且满足后剩余相等
}
cout<<"NO"<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
Comments NOTHING