A. Luntik and Concerts
Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming community
https://codeforces.com/contest/1582/problem/A题意:a值为1,b值为2,c值为3,给出abc数量,分成两份,求两份最小的差(绝对值).
思路:直接求总和,奇数输出1,偶数输出0即可.因为321可以随机分配达到平衡(打几个表就知道了).
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
int a,b,c;
cin>>a>>b>>c;
b*=2,c*=3;
int ans=a+b+c;
if(ans%2)
cout<<"1\n";
else
cout<<"0\n";
return;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}B. Luntik and Subsequences
Problem - B - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1582/problem/B题意:给你一个数组,问可以组成多少个特定数组,特定数组满足自己本身的和与原来数组比差一.
思路:数组里有n个1时,我们可以去掉这n个1中任意一个,就有n种选法.当含有0时,不论去掉哪个1,我们对于这个0都是由选与不选两种情况,直接用数组里1的个数乘以2的0的个数次方即可.
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
int x,n,cnt1=0,cnt0=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
if(x==1)
cnt1++;
if(x==0)
cnt0++;
}
int ans=cnt1*pow(2,cnt0);
printf("%lld\n",ans);
return;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}C. Grandma Capa Knits a Scarf
Problem - C - Codeforces
https://codeforces.com/contest/1582/problem/C题意:给你一个字符串,你可以选择一种字符(小写字母),删除字符串中任一个数的该字符,问最少删除几个字符可以让字符串变成回文.
思路:枚举26个小写字母,每次确定要对哪个字母进行删除.然后进行双指针模拟,从两边往中间遍历,当两者指针所指的字母相同就继续遍历,不相同看是否可以删除指定的字母来让它变成相同的.一直模拟完进行判断即可.
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
int f=0;
int n,ans=1e9;
string s,ss;
scanf("%d",&n);
cin>>s;
for(int i=0;i<26;i++)
{
char ch='a'+i;
ss="";
for(int i=0;i<s.size();i++)
{
if(s[i]!=ch)
ss+=s[i];
}
string s1=ss;
reverse(ss.begin(),ss.end());
if(ss!=s1)
{
continue;
}
int tt=0;
int l=0,r=s.size()-1;
while(l<r)
{
while(s[l]!=s[r])
{
if(s[l]!=ch&&s[r]==ch)
r--,tt++;
else if(s[l]==ch&&s[r]!=ch)
l++,tt++;
if(l>r)
break;
}
l++;
r--;
}
ans=min(ans,tt);
f=1;
}
if(f==0)
printf("-1\n");
else
printf("%d\n",ans);
return;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}D. Vupsen, Pupsen and 0
Problem - D - Codeforceshttps://codeforces.com/contest/1582/problem/D题意:给你一个不含有0的数组a,要求再构造一个相同长度的数组b,让a[i]*b[j]求和之后为0.b同样不能含有0.
思路:我们只需要取两个数组元素a[i],a[j],让b[i]=a[j],b[j]=-a[i]即可.但是当出现数组长度是奇数时,要考虑最后剩下或者任取的三个数字的情况,如果我们把三个数中取两个数合并并且按照上文的方法合并要注意,合并的两个数和不能为0!,不然新构造的数组就包含0了.
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
const int N =5e5+10,mod=998244353;
int a[100005];
int b[100005];
void solve()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
if(n%2==0)
{
for(int i=1;i<=n;i+=2)
{
b[i]=-a[i+1];
b[i+1]=a[i];
}
}
else
{
for(int i=1;i<=n-3;i+=2)
{
b[i]=-a[i+1];
b[i+1]=a[i];
}
if(a[n]+a[n-1]!=0)
{
b[n]=-a[n-2];
b[n-1]=-a[n-2];
b[n-2]=a[n]+a[n-1];
}
else if(a[n]+a[n-2]!=0)
{
b[n]=-a[n-1];
b[n-1]=a[n]+a[n-2];
b[n-2]=-a[n-1];
}
else if(a[n-2]+a[n-1]!=0)
{
b[n]=a[n-2]+a[n-1];
b[n-1]=-a[n];
b[n-2]=-a[n];
}
}
for(int i=1;i<=n;i++)
printf("%d ",b[i]);
printf("\n");
// int sum=0;
// for(int i=1;i<=n;i++)
// sum+=a[i]*b[i];
// cout<<"qwq "<<sum<<"\n";
return;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}F1. Korney Korneevich and XOR (easy version)
Problem - F1 - Codeforceshttps://codeforces.com/contest/1582/problem/F1
题意:给你一个数组,要求出取出一个非递减的子数组以后的一个异或和x,求出所有可以得到的x.
思路:求疑惑和,a[i]的值<500,所以异或和最大可以为512.我们只需要开一个f数组,去记录异或和为i(下标)的时候,这个非递减数组的最后一位放得什么即可,然后又枚举暴力,详细注释看代码:
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
int a[100005];
using namespace std;
const int N =5e5+10,mod=998244353;
int f[600];
//下标i表示数组异或和为i,里面存的是该异或和下数组末尾接的最小是多少
vector<int>ans;
void solve()
{
int n;
scanf("%d",&n);
f[0]=0;
for(int i=1;i<=512;i++)
f[i]=1000;
//初始化
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
f[a[i]]=min(f[a[i]],a[i]);
//异或和可以直接是他本身
for(int j=0;j<=512;j++)
{
if(a[i]>=f[j])
f[j^a[i]]=min(f[j^a[i]],a[i]);
//如果当前的数字比异或和为j的数组的末尾还要大,那么就连接上去,并且对末位进行刷新即可,如果异或出来过,就看原来已经异或出来的末尾的数字和a[i]的大小,判断a[i]连接上去了还是不是非递减数组.反之直接连接a[i],因为违背异或出来的肯定是a[i]结尾.
}
}
for(int i=0;i<=512;i++)
{
if(f[i]!=1000)
ans.push_back(i);
}
//把刷新过得异或和存进去
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)
{
printf("%d ",ans[i]);
}
return ;
}
signed main()
{
solve();
return 0;
}刷!