题目链接:https://codeforces.com/contest/1516
题意:给定一个数组,然后再给定n和k。你可以执行操作如下:
给任意两个不同的元素(下标不同)一个加上1,一个减掉1。
最多执行k次这样的操作,并且序列中不能出现负数。请你给出一个字典序最小的数组。
字典序:参考字符串的字典序比较。
思路:
1.既然要字典序最小,那么 要让前面的数尽可能的小,那么我们就尽可能的减掉当前最前面的数,给最后面的数加1。如果到0了,就下一个数。当然,k次用完了就退出了。然后要保持没有负数。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int N=220;
int n,k;
int a[N];
int t;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
if(a[i]==0||i==n) continue;
while(a[i]>0&&k>0)
{
a[i]--;
a[n]++;k--;
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<endl;
}
return 0;
}
题意:给你一个序列,你可以执行以下操作:把*相邻相邻相相邻的两个数异或(^),然后生成新的数。问你是否能通过一系列这样的操作,使得序列中满足元素都相等,且元素要满足大于等于2。
证明:因为,X^X=0,比如当前长度为4,序列为【X,X,X,X】,我们可以通过把后两个X ^X=0,序列就变成【X,X,0】,然后才把X ^ 0=X,于是,序列就变成了【X,X】 。奇数的情况同理。
2.当序列为偶数的那种情况,我们可以发现,如果序列可以构成相同,即最终状态为偶数个X,那么我们把这么多个X一起异或,即【X^X ^X ^X…】,那么最终一定是0,
所以,当最终异或和为0的序列一定可以。
讨论最终长度为奇数的情况
3,当序列为奇数的情况时,我们可以发现,序列的异或和为一个数Y(n为奇数,即n=2*k+1,k对的偶数异或都为0),所有最终为一堆0和一个数Y,如果序列可以满足,那么最终的数就是Y。
4.又因为最终需要大于等于2个数,相等所以我们只需要判断这里序列是否能够化成长度大于等于2且元素都相等的序列,即是否能找到2个及以上的Y。
前缀异或 ans[i]=ans[i-1]^a[i]。
AC代码:(注释)
#include<bits/stdc++.h>
using namespace std;
int t,n;
int a[2100];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans = 0;
for(int i=0;i<n;i++)
{
ans = ans^a[i];
}
if(ans == 0)
{
cout<<"YES\n";continue;
}else
{
int temp = 0;
int count = 0;
for(int i=0;i<n;i++)
{
temp = temp^a[i];//异或前缀
if(temp == ans)
{
count++;
temp = 0;//满足的时候让他归0,可以理解把奇数凑成偶数,或者当前区间满足,找下个区间的时候从初始态开始异或。
}
}//cnt就是记录最后剩下的数是不是大于2,已知最后一个数是Y,那么最少在前面再找一个Y即可。
if(temp == 0 && count>1 ) cout<<"YES\n";
else cout<<"NO\n";
}
}
return 0;
}
同样的,既然要使最终元素都相同。
那么,一定是若干个区间生成相同的数,组成的序列。
例如一个序列为【A,B,C,D,E,F】
那么在异或计算下可以是【A,B】=X,【C,D,E】=X,【F】=X。
再根据上面所讲,
==类似于前缀和求区间【L,R】的和,区间【L,R】的异或和也可以通过
f[R]^f[L-1]。求得。
所以,我们把前缀异或和数组处理好后,直接枚举区间不就行了。
枚举2个区间1个for,枚举3个区间2个for,我这里一起处理了。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+10;
map<ll,ll> mp;
ll a[N];
ll ans[N];
ll ans2[N];
int t;
int n;
void solve()
{
if(n==1)
{
cout<<"NO"<<endl;return;
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(i==j&&ans[i]==(ans[n]^ans[i])) // [1,i] 和[i+1,n] 这两个区间。
{
cout<<"YES"<<endl;return;
}
if(i!=j&&ans[i]==(ans[n]^ans[j])&&(ans[i]==(ans[i]^ans[j]))) //[1,i] 和 [i+1,j] 和 [j+1,n] 3个区间
{
cout<<"YES"<<endl;
return ;
}
}
}
cout<<"NO"<<endl;
return ;
}
int main()
{
cin>>t;
while(t--)
{
scanf("%d",&n);
ll res=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
res=res*a[i];
ans[i] = ans[i-1] ^ a[i];
}
solve();
}
return 0;
}
C代码
AC代码
:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int f[N];
int a[N];
int t,n;
int sum;
bool check()
{
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=N;j>=0;j--)
{
f[j+a[i]]+=f[j];
}
}
// printf("f[sum/2]===%d \n",f[sum/2]);
if(f[sum/2]) return false;
return true;
}
int main()
{
cin>>n;
//int sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int k=a[1];
for(int i=2;i<=n;i++)
{
k=__gcd(k,a[i]);
}
for(int i=1;i<=n;i++)
{
a[i]/=k;sum+=a[i];
}
// printf("k===%d \n",k);
if(sum%2==1)
{
cout<<"0"<<endl;return 0;
}
else
{
int st;//下标
// printf("st===%d \n",st);
for(int i=1;i<=n;i++)
{
if(a[i]%2==1)
{
st=i;
}
}
// printf("st===%d \n",st);
// printf("chek=== %d\n",check());
if(check()==1)
{
cout<<"0"<<endl;
}
else
{
cout<<"1"<<endl;
cout<<st<<endl;
}
}
return 0;
}
文章浏览阅读4.3k次,点赞4次,收藏14次。原本以为c是跨平台,所以,c在windows下和linux下的程序应该是类似于Java,什么都不用改变的,今儿才恍然大悟,他们的类库不一样啊……下面我贴出来一个windows下的c语言socket通信例子,这里我们客户端传递一个字符串,服务器端进行接收。【实际上我们需要完成的二进制流的传输,需要使用unsignedchar来实现,因为c里没有byte数据类型,这里我们不以byte为例,因为_vsock-listen windows能实现吗
文章浏览阅读119次。今晚鸿蒙OS正式发布,依旧是以往的风格,采用视频录播形式。Harmon OS一生万物,万物归一。华为Harmony OS是多设备多硬件统一的操作系统,Harmony OS,将统一控制中心汇聚在负一屏,便可完成对所有设备的操作,包括但不限于手机与平板,手机与智慧屏,手机与耳机等等。新品汇总华为新款MatePad Pro及MatePad11本次Pro系列共有两个版本,与之前曝光的信息相同,其中10.8..._高通处理器会升级鸿蒙系统么
文章浏览阅读756次。问题:输出新建的DataFrame对象时,DataFrame中各列的显示顺序和DataFrame定义中的顺序不一致。例如:import pandas as pdgrades = [48,99,75,80,42,80,72,68,36,78]df = pd.DataFrame( {'ID': ["x%d" % r for r in range(10)], ..._顺序输出dataframe中的一列
文章浏览阅读1.1w次,点赞11次,收藏6次。 今天使用Python图像处理库ImageGrab,在调用==grabclipboard()==方法获取到剪切板上图片的时候报了这个让我懵圈了的异常~~后来查了官方文档才知道,grabclipboard函数有一个缓存的问题,操作太快,有时候它就会读取上一次的内容,因为第一个没有读取到图像,所以报错了。..._attributeerror: 'nonetype' object has no attribute 'save
文章浏览阅读6.6k次,点赞22次,收藏56次。前两天在看TI官方提供的BasicRF的源码时,发现一个看不懂的地方,就是将一个数组名强制转换为结构体指针,如下所示。在上面的图片中,basicRfPktHdr_t是一个结构体,rxMpdu是一个长度为128个字节的数组名,pHdr是一个结构体指针。这让我很是清楚这么写是什么意思,因为以前从没有遇到,现在遇到了就算是进一步学习C语言了。通过百度查..._数组强制转换为结构体
文章浏览阅读492次。 接通电源之后,系统进行初始化,按下设置键S1或者S2,LCD进入时间设置界面,先使用齿轮确定要设定的位置(时、分、秒),按下s1按键进行确认,开始设置这个位置,可以使用齿轮电位计进行对该位置的数进行加减,设置数值,设置完成之后按下S1键进行确认,然后重新使用齿轮电位计确定要设置的位置,重复上述操作。全部设置完成之后,按下S2确认完成设置时间。接着进入倒计时器界面。计时完成之后,LED闪...___delay_cycles(1000000);
文章浏览阅读754次。首先安装: npm ivuedraggable -s然后引入相对应的组件importDraggablefrom'vuedraggable';在components里面进行注册<!-- group: 如果又相同的组, 则可以互相进行拖拽, tag: 渲染后的标签形式, animation: 过渡动画 --> <draggable class="dra..._vuedraggable 动画
文章浏览阅读1w次,点赞2次,收藏2次。没接触过linux,由于要部署项目,安装的Ubuntu16.04,安装完配置网络接口,遇到的两个问题如下:1 网络接口配置文件:nano/etc/network/interfaces 执行此命令,如果提示bash:/etc/network/interfaces:Permission denied 拒绝访问,没有权限,首先看是不是root用户,是的话执行:chmod_etc/network中interface没有了
文章浏览阅读2.9k次。不小心按快捷键按错了,结果出现这种圈圈叉叉,干扰布线解决方法:关掉这两个结果:解决!参考:参考的这个有点标题和内容不搭配。牛头马嘴,,,找不到component reference point和3D Body reference point..._ad原理图去除交叉点
文章浏览阅读3.3w次,点赞76次,收藏458次。小跳蚤 大用途前言: 算一算时间又快到了一年一度的毕业设计了吧,我也差不多完成我自己的毕业设计一年了,在此推出我的毕业设计成果以供后来的学弟学妹参考。都说站在巨人肩膀上,更上一层楼,在枯燥的编程期间我也有参考CSND大力哥的文章。很多人 把毕业设计应付过去,但是学习终究是自己的,绝知此事要躬行。接下来跟着我学习和分析的思路看一下成果吧!目录第1章 引言.... 5..._基于安卓的跳蚤市场论文
文章浏览阅读685次,点赞4次,收藏14次。文章目录一、什么是 Arthas二、特性一览三、Arthas 能为你做什么?四、快速安装1、前提条件2、一键安装五、快速使用1、启动并连接进程六、使用示例1、dashboard(当前系统的实时数据面板)2、sysprop(查看或修改java属性)3、mbean(实时查看Mbean信息)4、thread(查看线程)5、thread -n(查看占CPU前几的线程栈信息)6、jad(反编译代码)7、sc(查看已经加载的类)8、sm(列出某个类加载的方法)9、trace(跟踪方法的消耗时间)10、stack (查看_[root@localhost ~]# ./as.sh arthas script version: 3.7.2 [info] java_home: /
文章浏览阅读3.8k次。opencv 入门笔记十 图片序列保存为视频_opencv将图片保存为视频