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 '\n'
#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 '\n'
#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 '\n'
#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 '\n'
#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;
}

平平无奇的大学在读本科生