A题
大意
略
思路
显然是把前面的元素放到最后一个
代码
#include<bits/stdc++.h>
#define fi first
#define se second
//#define b tm
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,k;
int a[maxn];
signed main(){
int _;cin>>_;
while(_--){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int temp=k;
for(int i=1;i<n;i++){
if(a[i]>=k){
a[i]-=k;
k=0;
break;
}else{
k-=a[i];
a[i]=0;
}
}
int dif=temp-k;
a[n]+=dif;
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
printf("
");
}
return 0;
}
B题
大意
给你一个长度为(n(nle 1e3))的数组，每次可以选择两个相邻的数(a[i],a[i+1])使这两个元素变为一个元
素，值为(a[i]igoplus a[i+1])，判断最后是否存在大于等于(2)个元素，使得所有元素相等
思路
若所有元素异或值为(0)，那么肯定可以
但是也有可能出现(3)个相同的元素
所以再去分为三段去考虑即可
代码
#include<bits/stdc++.h>
#define fi first
#define se second
//#define b tm
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,k;
int a[maxn];
int pre[maxn],suf[maxn];
signed main(){
int _;cin>>_;
while(_--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=(pre[i-1]^a[i]);
}
suf[n+1]=0;
for(int i=n;i>=1;i--){
suf[i]=(suf[i+1]^a[i]);
}
bool flag=0;
for(int i=1;i<=n;i++){
//[1,i]
//[i+1,j]
//[j+1,n];
for(int j=i+1;j<n;j++){
if(pre[i]==suf[j+1]&&pre[i]==pre[n]){
flag=1;
}
}
}
if(pre[n]==0) flag=1;
printf(flag?"YES
":"NO
");
}
return 0;
}
C题
大意
给你长度为(n(nle 100))的数组(a(1le a[i] le 2e3))，要你删除最少的数，使得这个数组，不能找到
一些数使得总和为这个数组的一半
思路
首先可以(dp)判断是否可以构成一半
若不能构成那么答案就是(0)
若能构成肯定删除一个奇数即可，若没有奇数，你可以把所有元素除(2)再找奇数，显然是成立的，所以答
案必定是(2)的因子数最少
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e2+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,k;
int a[maxn];
bool dp[maxn][200005];
signed main(){
cin>>n;
int sum=0;
int mi=inf,pos=-1;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
int temp=a[i],cnt=0;
while(temp%2==0){
temp=temp/2;
cnt++;
}
if(cnt<mi){
mi=cnt;
pos=i;
}
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=sum;j++){
if(dp[i-1][j]){
dp[i][j]=dp[i][j+a[i]]=1;
}
}
}
int ans=-1;
if(sum%2==1||!dp[n][sum/2]){
ans=-1;
}else{
ans=a[1];
}
if(ans==-1){
printf("%d",0);
}else{
printf("1
%d",pos);
}
return 0;
}
D题
大意
给你长度为(n(nle 1e5))的数组(a(1le a[i] le1e5))，(q(qle 1e5))次查询，每次查询([l,r])最少分为多少段
才能使每段元素满足相互互质
思路
定义(nxt[i])为以(a[i])为起点，向后延申，最近的和(a[i])互质的数的坐标(-1)
那么可以利用质因子分解，从后往前遍历一边即可得到(nxt)数组
定义(dp[i])表示以(a[i])为起点，满足题意的区间最远的右边界+1
那么(dp[i]=min(dp[i+1],nxt[i]))
设(dp[i][j])表示以(i)为起点，走(2^j)步
倍增求解答案即可
代码
#include<bits/stdc++.h>
#define fi first
#define se second
//#define b tm
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,q;
int a[maxn];
int nxt[maxn];
int prime[maxn],cnt;
int isprime[maxn];
int pos[maxn];
int dp[maxn][30];
void getprime(int n){
for(ll i=2;i<=n;i++){//开ll因为后面要计算i*prime[j]
if(!isprime[i]){
prime[++cnt]=i;
isprime[i]=i;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
isprime[i*prime[j]]=prime[j];
if(i%prime[j]==0) break;
}
}
}
void rmq(){
for(int i=1;i<=n;i++){
dp[i][0]++;
}
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
dp[i][j]=dp[dp[i][j-1]][j-1];
}
}
}
int cal(int l,int r){
int now=l;
int x=0;
for(int i=20;i>=0;i--){
if(dp[now][i]!=0&&dp[now][i]<=r){
now=dp[now][i];
x+=(1<<i);
}
}
return x+1;
}
signed main(){
getprime(100000);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
memset(pos,0x3f,sizeof(pos));
// 每个位置预处理inf
for(int i=n;i>=1;i--){
nxt[i]=n;
int temp=a[i];
while(isprime[temp]){
int x=isprime[temp];
nxt[i]=min(nxt[i],pos[x]-1);
while(temp%x==0){
temp=temp/x;
}
pos[x]=i;
}
}
dp[n][0]=n;
for(int i=n-1;i>=1;i--){
dp[i][0]=min(dp[i+1][0],nxt[i]);
}
rmq();
for(int i=1,l,r;i<=q;i++){
scanf("%d%d",&l,&r);
printf("%d
",cal(l,r));
}
return 0;
}