A. Luntik and Concerts

题目

题意
有a个1 b个2 c个3 现在将这些数分成两组 问两组的和 最小的差值是多少

思路
计算数的总和 是否能被2整除 能整除的就是0 不能被整除的就是1

代码

#include<iostream>using namespace std;
typedef long long ll;
ll t,a,b,c;int main()
{ios::sync_with_stdio(false);cin>>t;while(t--){cin>>a>>b>>c;cout<<(a+b*2+c*3)%2<<endl;}return 0;
}

B. Luntik and Subsequences

题目

题意
给一个数组 数字总和和为s 问数组有多少个子数组的数字和为s-1

思路
子数组和为s-1 必然是原数组减去一个1 所以首先记录原数组有多少个1
子数组减去任意个0和都不变 计算0的个数cnt对每个1的贡献值 2^cnt次
相乘得出结果

代码

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;ll t,n,te;int main()
{ios::sync_with_stdio(false);cin>>t;while(t--){ll num1=0,num0=0;cin>>n;for(int i=0;i<n;i++){cin>>te;if(te==1)num1++;else if(te==0)num0++;}if(num1){cout<<num1*(1ll<<num0)<<endl;}elsecout<<0<<endl;}return 0;
}

C. Grandma Capa Knits a Scarf

题目

题意
给一个字符串 删除任意个 一种字母使它成为回文串 问最少删除几个字符能变成回文串 不能输出 -1

思路
用a到z去尝试 从字符串两边向中间去匹配 两边相同就向中间走 如果有一边等于当前尝试的字符 就尝试去删除(跳过这一位 让下一位跟另一边相匹配) 否则就表示不能通过删除当前字符使得原串变成回文串

代码

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;ll t,n,te;
string s;int main()
{ios::sync_with_stdio(false);cin>>t;while(t--){cin>>n;cin>>s;int mmin=n+1;for(char i='a';i<='z';i++){int ans=0,l=0,r=n-1,flag=1;while(l<r){if(s[l]==s[r]){l++;r--;}else if(s[l]==i){l++;ans++;}else if(s[r]==i){r--;ans++;}else{flag=0;break;}}if(flag)mmin=min(ans,mmin);}if(mmin>n)mmin=-1;cout<<mmin<<endl;}return 0;
}

D. Vupsen, Pupsen and 0

题目

题意
给一个长度为n不含0的数组a 现要求找到另一个不含0的数组b 使得sum(a1xb1+ …aixbi…)和为0 同时要求sum(b1+b2+…)和不超过1e9

思路
已知 任意一个数x其他数的和=其他每个数x这个数 的和
同时 也可以采用两两抵消的原则
综合以上两种思路 当n%2==0就采用两两抵消
否则就让其中3个数进行策略1(求两个和不为0的值 让第3个数对应的bi=这个值取反 其他两个数的bi=第3个数)

代码

#include<iostream>
#include<cmath>
#define N 100005
using namespace std;
typedef long long ll;ll t,n,te,a[N];
string s;int main()
{ios::sync_with_stdio(false);cin>>t;while(t--){ll sum=0,mmin=200005;int flag=0;cin>>n;for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}for(int i=0;i<n;i++){if(sum-a[i]!=0&&mmin>a[i]){flag=i;mmin=a[i];}}//ll ssum=0;if(n%2==0){for(int i=0;i<n;i+=2){cout<<-a[i+1]<<" "<<a[i]<<" ";}cout<<endl;continue;}for(int i=0;i<n-3;i+=2){cout<<-a[i+1]<<" "<<a[i]<<" ";}if(a[n-1]+a[n-2]!=0){cout<<-(a[n-1]+a[n-2])<<" "<<a[n-3]<<" "<<a[n-3]<<endl;}else if(a[n-2]+a[n-3]!=0){cout<<a[n-1]<<" "<<a[n-1]<<" "<<-(a[n-2]+a[n-3])<<endl;}else{cout<<a[n-2]<<" "<<-(a[n-1]+a[n-3])<<" "<<a[n-2]<<endl;}}return 0;
}

E. Pchelyonok and Segments

题目

题意
给一个数组a 切成k个非重叠片段 前面的片段比后面相邻的片段长度长1 且片段总和严格递增 问k的最大值

思路
逆序看 是一个 长度不断增加 值不断减小的dp

代码

#include<iostream>
#include<cmath>
#include<cstring>
#define N 100005
using namespace std;
typedef long long ll;ll t,n,te,a[N],sum[N],dp[N][455];
string s;int main()
{ios::sync_with_stdio(false);cin>>t;while(t--){cin>>n;sum[0]=0;a[0]=0;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];}for(int i=1;i<=n+1;i++){for(int j=1;j<450;j++)dp[i][j]=0;}dp[n][1]=a[n];int ans=-1;for(int i=n;i>=1;i--){for(int j=1;j<450;j++){if(i+j-1>n)continue;te=sum[i+j-1]-sum[i-1];if(dp[i+j][j-1]>te||j==1){dp[i][j]=te;ans=max(ans,j);}dp[i][j]=max(dp[i+1][j],dp[i][j]);}}cout<<ans<<'\n';}return 0;}